The complexity of learning according to two models of a drifting environment

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The complexity of learning according to two models of a drifting environment

Full text

Pdf (1.03 MB)

Source

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

Madison, Wisconsin, United States

Pages: 116 - 125

Year of Publication: 1998

ISBN:1-58113-057-0

Author

Philip M. Long

ISCS Department, National University of Singapore, Singapore 119260, Republic of Singapore

Sponsors

University of Wisconsin : University of Wisconsin
UC @ Santa Cruz : UC @ Santa Cruz
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): 2, Downloads (12 Months): 11, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/279943.279968 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. Auer , M. K. Warmuth, Tracking the best disjunction, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.312, October 23-25, 1995
	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	Peter L. Bartlett , Shai Ben-David , Sanjeev R. Kulkarni, Learning changing concepts by exploiting the structure of change, Proceedings of the ninth annual conference on Computational learning theory, p.131-139, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238080]
	5	P. L. Bartlett and D. P. Helmbold, 1995. Manuscript.
	6	Rakesh D. Barve , Philip M. Long, On the complexity of learning from drifting distributions, Information and Computation, v.138 n.2, p.170-193, Nov. 1, 1997 [doi>10.1006/inco.1997.2656]
	7	Avrim Blum , Prasad Chalasani, Learning switching concepts, Proceedings of the fifth annual workshop on Computational learning theory, p.231-242, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130411]
	8	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]
	9	Yoav Freund , Yishay Mansour, Learning Under Persistent Drift, Proceedings of the Third European Conference on Computational Learning Theory, p.109-118, March 17-19, 1997
	10	Yoav Freund , Dana Ron, Learning to model sequences generated by switching distributions, Proceedings of the eighth annual conference on Computational learning theory, p.41-50, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225303]
	11	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]
	12	David Haussler, Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension, Journal of Combinatorial Theory Series A, v.69 n.2, p.217-232, Feb. 1995 [doi>10.1016/0097-3165(95)90052-7]
	13	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]
	14	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]
	15	M. Herbster and M. K. Warmuth. Tracking the best expert. Proceedings of of the Twelvth International Conference on Machine Learning, 1995.
	16	Mark Herbster , Manfred K. Warmuth, Tracking the best regressor, Proceedings of the eleventh annual conference on Computational learning theory, p.24-31, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279949]
	17	Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward Efficient Agnostic Learning, Machine Learning, v.17 n.2-3, p.115-141, Nov./Dec. 1994 [doi>10.1007/BF00993468]
	18	A. N. Kolmogorov and V. M. Tihomirov. c-entropy and c-capacity of sets in functional spaces. American Mathematical Society Translations (Set. 2), 17:277- 364, 1961.
	19	A. Kuh. Comparison of tracking algorithms for single layer threshold networks in the presence of random drift. IEEE Trans. on Signal Processing, 45(3):640- 650, 1997.
	20	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
	21	A. Kuh, T. Petsche, and R. Rivest. Mistake bounds of incremental learners when concepts drift with applications to feedforward networks. In NIPS 4. Morgan Kaufmann, 1991.
	22	Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
	23	Philip M. Long, On the sample complexity of learning functions with bounded variation, Proceedings of the eleventh annual conference on Computational learning theory, p.126-133, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279970]
	24	D. Pollard. Convergence of Stochastic Processes. Springer Verlag, 1984.
	25	D. Pollard. Empirical Processes: Theory and Applications, volume 2 of NSF-CBMS Regional Conference Series in Probability and Statistics. Institute of Math. Stat. and Am. Star. Assoc., 1990.
	26	Shaibal Roy, Semantic complexity of classes of relational queries and query independent data partitioning, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.259-267, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113437]
	27	H. L. Royden. Real Analysis. Macmillan, 1963.
	28	N. Saner. On the density of families of sets. J. Combinatorial Theory (A), 13:145-147, 1972.
	29	S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41:247-261, 1972.
	30	Hans Ulrich Simon, General bounds on the number of examples needed for learning probabilistic concepts, Journal of Computer and System Sciences, v.52 n.2, p.239-254, April 1996 [doi>10.1006/jcss.1996.0019]
	31	M. Talagrand. Sharper bounds for Gaussian and empirical processes. Annals of Probability, 22:28-76, 1994.
	32	Xiaodong Tian , Anthony Kuh, Performance bounds for single layer threshold networks when tracking a drifting adversary, Neural Networks, v.10 n.5, p.897-906, July 1997 [doi>10.1016/S0893-6080(96)00118-9]
	33	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.

CITED BY 4

	Peter L. Bartlett , Shai Ben-David , Sanjeev R. Kulkarni, Learning Changing Concepts by Exploiting the Structure of Change, Machine Learning, v.41 n.2, p.153-174, November 2000
	Philip M. Long, On the sample complexity of learning functions with bounded variation, Proceedings of the eleventh annual conference on Computational learning theory, p.126-133, July 24-26, 1998, Madison, Wisconsin, United States
	Yi Li , Philip M. Long , Aravind Srinivasan, Improved bounds on the sample complexity of learning, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.309-318, January 09-11, 2000, San Francisco, California, United States
	Philip M. Long, Efficient algorithms for learning functions with bounded variation, Information and Computation, v.188 n.1, p.99-115, 10 January 2004