On the complexity of learning from drifting distributions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of learning from drifting distributions

Full text

Pdf (783 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the ninth annual conference on Computational learning theory table of contents

Desenzano del Garda, Italy

Pages: 122 - 130

Year of Publication: 1996

ISBN:0-89791-811-8

Authors

Rakesh D. Barve	Department of Computer Science, Duke University, P.O. Box 90129, Durham, North Carolina
Philip M. Long	ISCS Department, National University of Singapore, Singapore 119260, Republic of Singapore

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 21, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/238061.238077 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Martin Anthony , Norman Biggs , John Shawe-Taylor, The learnability of formal concepts, Proceedings of the third annual workshop on Computational learning theory, p.246-257, August 06-08, 1990, Rochester, New York, United States
	2	P. L. Bartlett and P. M. Long. Prediction, learning, uniform convergence, and scale-sensitive dimensions, 1995. Submitted.
	3	Peter L. Bartlett, Learning with a slowly changing distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.243-252, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130412]
	4	P.L. Bartlett and D.P. Helmbold, 1995. Manuscript.
	5	Shai Ben-David , Gyora M. Benedek , Yishay Mansour, A parametrization scheme for classifying models of learnability, Proceedings of the second annual workshop on Computational learning theory, p.285-302, December 1989, Santa Cruz, California, United States
	6	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]
	7	A. Dawid. Statistical theory: The prequential approach. Journal of the Royal Statistical Society (Series A), pages 278-292, 1984.
	8	R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. Wiley, 1973.
	9	Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
	10	David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
	11	D. Haussler , N. Littlestone , M. K. Warmuth, Predicting {0, 1}-functions on randomly drawn points, Information and Computation, v.115 n.2, p.248-292, Dec. 1994 [doi>10.1006/inco.1994.1097]
	12	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
	13	David P. Helmbold , Philip M. Long, Tracking Drifting Concepts By Minimizing Disagreements, Machine Learning, v.14 n.1, p.27-45, Jan. 1994 [doi>10.1023/A:1022694620923]
	14	Anthony Kuh , Thomas Petsche , Ronald L. Rivest, Learning time-varying concepts, Proceedings of the 1990 conference on Advances in neural information processing systems 3, p.183-189, October 1990, Denver, Colorado, United States
	15	T. Kuh, T. Petsche, and R. Rivest. Mistake bounds of incremental learners when concepts drift with applications to feedforward networks. In NIPS 3. Morgan Kaufmann, 1991.
	16	N. Littlestone. On the derivation and quality of Chernoff bounds, 1990. Submitted.
	17	D. Pollard. Convergence of Stochastic Processes. Springer Verlag, 1984.
	18	N. Sauer. On the density of families of sets. J. Combinatorial Theory (A), 13:145-147, 1972.
	19	Hans Ulrich Simon, General bounds on the number of examples needed for learning probabilistic concepts, Proceedings of the sixth annual conference on Computational learning theory, p.402-411, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168385]
	20	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]
	21	V.N. Vapnik and A.Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971.