On-line learning of rectangles

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On-line learning of rectangles

Full text

Pdf (1.17 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the fifth annual workshop on Computational learning theory table of contents

Pittsburgh, Pennsylvania, United States

Pages: 16 - 28

Year of Publication: 1992

ISBN:0-89791-497-X

Authors

Zhixiang Chen
Wolfgang Maass

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): 17, Downloads (12 Months): 35, Citation Count: 12

Additional Information:

abstract 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/130385.130387 What is a DOI?

ABSTRACT

This paper solves the following open problem: Is there an algorithm for on-line learning of rectangles i=1

d ai, ai+1,…,bi} over a discrete domain {1,…,n}d whose error bound is polylogarithmic in the size nd of the domain (i.e. polynomial in d and log n )? We give a positive solution by introducing a new design technique that appears to be of some interest on its own. The new learning algorithm for rectangles consists of 2d separate search strategies that search for the parameters a1,b1,…,ad,bd of the target rectangle. A learning algorithm with this type of modular design ends to fail because of the well known “credit assignment problem”: Which of the 2d local search strategies should be “blamed” when the global algorithm makes an error? We overcome this difficulty by employing local search strategies (“error tolerant binary search”) that are able to tolerate certain types of wrong credit assignments. Section 4 contains another application of this design technique: an algorithm for learning the union of two rectangles in the plane.

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.

	A	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	H	D. Haussler, personal communication, 1989.
	KMRSW	D.J. Kleitman, A.R. Meyer, R.L. Rivest, J. Spencer, K. Winklman, "Coping with errors in binary search procedures", J. Comp. Syst. Sci., 1980, 396 - 404.
	L	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]
	MTa	W. Maass, G. Turin, "On the complexity of learning from counterexamples (extended abstract)", Proc of the 30th Annual LE.E.E. Symposium on Foundations of Computer Science, 1989, 262 - 267.
	MTb	W. Maass, G. Turin, "Algorithms and Lower Bounds for On-line Learning of Geometrical Concepts", Report 316 (Oct. 1991), IIG-Report Series, Technische Universitaet Graz;, to appear in Machine Learning.
	MTc	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]
	P	A. Pelc, Searching with known error probability, Theoretical Computer Science, v.63 n.2, p.185-202, Feb. 1989 [doi>10.1016/0304-3975(89)90077-7]
	PV	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
	SW	J. Spencer, P. Winkler, "Three thresholds for a liar", DIMACS Tech. Report 91 - 72 (Oct. 1991).
	V	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]

CITED BY 12

	Peter Auer, On-line learning of rectangles in noisy environments, Proceedings of the sixth annual conference on Computational learning theory, p.253-261, July 26-28, 1993, Santa Cruz, California, United States
	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
	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
	Michael Frazier , Leonard Pitt, CLASSIC learning, Proceedings of the seventh annual conference on Computational learning theory, p.23-34, July 12-15, 1994, New Brunswick, New Jersey, United States
	Tibor Hegedűs, Geometrical concept learning and convex polytopes, Proceedings of the seventh annual conference on Computational learning theory, p.228-236, July 12-15, 1994, New Brunswick, New Jersey, United States
	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
	Shai Ben-David , Nadav Eiron , Eyal Kushilevitz, On self-directed learning, Proceedings of the eighth annual conference on Computational learning theory, p.136-143, July 05-08, 1995, Santa Cruz, California, 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
	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
	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
	Michael Frazier , Sally Goldman , Nina Mishra , Leonard Pitt, Learning from a consistently ignorant teacher, Proceedings of the seventh annual conference on Computational learning theory, p.328-339, July 12-15, 1994, New Brunswick, New Jersey, United States
	Shai Ben-David , Eyal Kushilevitz , Yishay Mansour, Online Learning versus Offline Learning, Machine Learning, v.29 n.1, p.45-63, Oct. 1997