Noise-tolerant parallel learning of geometric concepts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Noise-tolerant parallel learning of geometric concepts

Full text

Pdf (1.01 MB)

Source

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

Santa Cruz, California, United States

Pages: 345 - 352

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Nader H. Bshouty	Department of Computer Science, The University of Calgary, Calgary, Alberta, Canada T2N 1N4
Sally A. Goldman	Dept. of Computer Science, Washington University, St. Louis, MO
H. David Mathias	Dept. of Computer Science, Washington University, St. Louis, MO

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
University of California : University of California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 23, Citation Count: 3

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/225298.225340 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	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	2	J. A. Aslam and S. E. Decatur. General bounds on statistical query learning and PAC leaming with noise via hypothesis boosting. In 34th Ann. Symp. on Foundations of Comp. Sci., pages 282-291, November 1993.
	3	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 [doi>10.1145/168304.168345]
	4	José L. Balcázar , Josep Díaz , Ricard Gavaldà , Osamu Watanabe, An optimal parallel algorithm for learning DFA, Proceedings of the seventh annual conference on Computational learning theory, p.208-217, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181110]
	5	E. B. Baum, On learning a union of half spaces, Journal of Complexity, v.6 n.1, p.67-101, Mar. 1990 [doi>10.1016/0885-064X(90)90012-3]
	6	Eric B. Baum, The perceptron algorithm is fast for nonmalicious distributions, Neural Computation, v.2 n.2, p.248-260, Apr. 1990 [doi>10.1162/neco.1990.2.2.248]
	7	Bonnie Berger , John Rompel , Peter W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, Journal of Computer and System Sciences, v.49 n.3, p.454-477, Dec. 1994
	8	Avrim Blum , Ronald L. Rivest, Training a 3-node neural network in NP-complete, Advances in neural information processing systems 1, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
	9	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]
	10	Nader H. Bshouty, Zhixiang Chen, and Steve Homer. On learning discretized geometric concepts. In 35th Ann. Symp. on Foundations of Comp. Sci., pages 54-63, November 1994.
	11	Nader H. Bshouty and Richard Cleve. On the exact learning of formulas in parallel. In 33rd Ann. Syrup. on Foundations of Comp. Sci., pages 1-15, October 1992.
	12	Nader H. Bshouty, Paul W. Goldberg, Sally A. Goldman, and H. David Mathias. Exact learning of discretized concepts. Tech. Report WUCS-94-19, Washington University, 1994.
	13	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 [doi>10.1145/168304.168342]
	14	Zhixiang Chen and Steven Homer. The bounded injury priority method and the learnability of unions of rectangles. Unpublished manuscript, May 1994.
	15	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]
	16	Scott Evan Decatur, Statistical queries and faulty PAC oracles, Proceedings of the sixth annual conference on Computational learning theory, p.262-268, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168346]
	17	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	18	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]
	19	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 [doi>10.1145/180139.181170]
	20	Yoav Freund, Boosting a weak learning algorithm by majority, Proceedings of the third annual workshop on Computational learning theory, p.202-216, August 06-08, 1990, Rochester, New York, United States
	21	Yoav Freund, An improved boosting algorithm and its implications on learning complexity, Proceedings of the fifth annual workshop on Computational learning theory, p.391-398, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130429]
	22	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 [doi>10.1145/180139.181102]
	23	David Haussler. Generalizing the PAC model: sample size bounds from metric dimension-based uniform convergence results. In 30th Ann. Symp. on Foundations of Comp. Sci., pages 40-45, October 1989.
	24	Steven Homer and Zhixiang Chen. Fast learning unions of rectangles with queries. Unpublished manuscript, July 1993.
	25	Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167200]
	26	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]
	27	Philip M. Long , Manfred K. Warmuth, Composite geometric concepts and polynomial predictability, Proceedings of the third annual workshop on Computational learning theory, p.273-287, August 06-08, 1990, Rochester, New York, United States
	28	Wolfgang Maass and Gy6rgy Turfin. On the complexity of learning from counterexamples. In 30th Ann. Symp. on Foundations ofComp. Sci., pages 262-267, October 1989.
	29	Wolfgang Maass and Gy6rgy Turfin. On the complexity of learning from counterexamples and membership queries. In 31st Ann. Syrup. on Foundations of Comp. Sci., pages 203- 210, October 1990.
	30	Wolfgang Maass and Gydrgy Turfin. Algorithms and lower bounds for on-line learning of geometrical concepts. Tech. Report IIG-Report 316, Technische Universitfit Graz, TU Graz, Austria, October 1991.
	31	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]
	32	Wolfgang Maass and Manfred Warmuth. Efficient learning with virtual threshold gates. Unpublished Manuscript, 1994,
	33	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	34	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]
	35	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.
	36	Jeffrey Scott Vitter , Jyh-Han Lin, Learning in parallel, Proceedings of the first annual workshop on Computational learning theory, p.106-124, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	37	Jeffrey Scott Vitter , Jyh-Han Lin, Learning in parallel, Information and Computation, v.96 n.2, p.179-202, Feb. 1992 [doi>10.1016/0890-5401(92)90047-J]

CITED BY 3

	Nader H. Bshouty , Sally A. Goldman , H. David Mathias , Subhash Suri , Hisao Tamaki, Noise-tolerant distribution-free learning of general geometric concepts, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.151-160, May 22-24, 1996, Philadelphia, Pennsylvania, 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
	Marc Fischlin, Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions, Theoretical Computer Science, v.268 n.2, p.199-219, 17 October 2001