On-line learning of rectangles in noisy environments

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On-line learning of rectangles in noisy environments

Full text

Pdf (646 KB)

Source

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

Santa Cruz, California, United States

Pages: 253 - 261

Year of Publication: 1993

ISBN:0-89791-611-5

Author

Peter Auer

Sponsors

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): 0, Downloads (12 Months): 11, Citation Count: 10

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/168304.168345 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.

	AL88	Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	Ang88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	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]
	CM92	Zhixiang Chen , Wolfgang Maass, On-line learning of rectangles, Proceedings of the fifth annual workshop on Computational learning theory, p.16-28, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130387]
	DGW92	Aditi Dhagat , Peter Gács , Peter Winkler, On playing “Twenty Questions” with a liar, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.16-22, September 1992, Orlando, Florida, United States
	KL88	Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62238]
	Lit88	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	Lit89	N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
	LW91	N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Technical Report UCSC-CRL-91-28, UC Santa Cruz, 1991. An extended abstract appeared in: Proceedings of the 30th Annual Symposium on the Foundations of Computer Science..
	MT89	W. Maass and G. Turin. On the complexity of learning from counterexamples. In $Oth Annual IEEE Symposium on Foundations of Computer Science, pages 262-267, 1989.
	MT91	Wolfgang Maazs and Gy/Srgy Turan. Algorithms and lower bounds for on-line learning of geometrical concepts. IIG-Report 316, Technische Universitgt Graz, TU Graz, Austria, 1991.
	MT92	Wolfgang Maass , György Turán, Lower Bound Methods and Separation Results for On-Line Learning Models, Machine Learning, v.9 n.2-3, p.107-145, July 1992 [doi>10.1007/BF00992674]

CITED BY 10

	Nader H. Bshouty , Sally A. Goldman , H. David Mathias, Noise-tolerant parallel learning of geometric concepts, Proceedings of the eighth annual conference on Computational learning theory, p.345-352, July 05-08, 1995, Santa Cruz, California, United States
	Nader H. Bshouty, A new composition theorem for learning algorithms, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.583-589, May 24-26, 1998, Dallas, Texas, United States
	Stephen Kwek , Leonard Pitt, PAC learning intersections of halfspaces with membership queries (extended abstract), Proceedings of the ninth annual conference on Computational learning theory, p.244-254, June 28-July 01, 1996, Desenzano del Garda, Italy
	Amos Beimel , Francesco Bergadano , Nader H. Bshouty , Eyal Kushilevitz , Stefano Varricchio, Learning functions represented as multiplicity automata, Journal of the ACM (JACM), v.47 n.3, p.506-530, May 2000
	Paul W. Goldberg , Sally A. Goldman , H. David Mathias, Learning unions of boxes with membership and equivalence queries, Proceedings of the seventh annual conference on Computational learning theory, p.198-207, July 12-15, 1994, New Brunswick, New Jersey, United States
	Zhixiang Chen, Learning unions of two rectangles in the plane with equivalence queries, Proceedings of the sixth annual conference on Computational learning theory, p.243-252, July 26-28, 1993, Santa Cruz, California, United States
	Shai Ben-David , Nader H. Bshouty , Eyal Kushilevitz, A composition theorem for learning algorithms with applications to geometric concept classes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.324-333, May 04-06, 1997, El Paso, Texas, United States
	Nader H. Bshouty , Nadav Eiron, Learning monotone dnf from a teacher that almost does not answer membership queries, The Journal of Machine Learning Research, 3, p.49-57, 3/1/2003
	Peter Auer , Manfred K. Warmuth, Tracking the Best Disjunction, Machine Learning, v.32 n.2, p.127-150, Aug. 1998
	Peter Auer , Nicolò Cesa-Bianchi, On-line learning with malicious noise and the closure algorithm, Annals of Mathematics and Artificial Intelligence, v.23 n.1-2, p.83-99, 1998