Learning with a slowly changing distribution

ABSTRACT

In this paper, we consider the problem of learning a subset of a domain from randomly chosen examples when the probability distribution of the examples changes slowly but continually throughout the learning process. We give upper and lower bounds on the best achievable probability of misclassification after a given number of examples. If d is the VC-dimension of the target function class, t is the number of examples, and &Ugr; is the amount by which the distribution is allowed to change (measured by the largest change in the probability of a subset of the domain), the upper bound decreases as d/t initially, and settles to O(d2/3&Ugr;1/2) for large t. These bounds give necessary and sufficient conditions on &Ugr;, the rate of change of the distribution of examples, to ensure that some learning algorithm can produce an acceptably small probability of misclassification. We also consider the case of learning a near-optimal subset of the domain when the examples and their labels are generated by a joint probability distribution on the example and label spaces. We give an upper bound on &Ugr; that ensures learning is possible from a finite number of examples.

REFERENCES

• ABST90: M. Anthony, N. Biggs, and J. Shawe.Taylor. Learnability and formal concept analysis. Technical Report CSD-TR-624, UCL, 1990.
• AST90: M. Anthony and J. Shawe-Taylor. A result of Vapnik with applications. Technical port CSD-TR-628, UCL, 1990.
• BEHW89: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• Hal50: P.R. Halmos. Measure Theory. Van Nostrand, 1950.
• HKLW88: David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• HL9l: David P. Helmbold , Philip M. Long, Tracking drifting concepts using random examples, Proceedings of the fourth annual workshop on Computational learning theory, p.13-23, August 05-07, 1991, Santa Cruz, California, United States
• HLW90: D. Haussler , N. Littlestone , M. K. Warmuth, PREDICTING {0,1}-FUNCTIONS ON RANDOMLY DRAWN POINTS, University of California at Santa Cruz, Santa Cruz, CA, 1990
• Kra88: A.H. Kramer. Learning despite distribution drift. In Proceedings of the Connectionist Models Summer School, pages 201-210. Morgan Kaufmann, San Mateo, CA, 1988.
• Kul67: S. Kullbaek. A lower bound for discrimination information in terms of variation. IEEE Transactions on Information Theory, IT-13:126-127, 1967.
• Ren61: A. Renyi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 547-561. University of California Press, 1961.
• Val84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• Vap82: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• VC71: V.N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, XVI(2):264-280, 1971.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Theory, Verification