Lower bounds for PAC learning with queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for PAC learning with queries

Full text

Pdf (776 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: 384 - 391

Year of Publication: 1993

ISBN:0-89791-611-5

Author

György Turán

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): 15, Downloads (12 Months): 28, Citation Count: 2

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.168382 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	H. Aizenstein, L. ttellerstein, L. Pitt (1992): Read-thrice DNF is hard to learn with membership and eqmvalence queries, 33. FOCS (1992), 523-532.
	2	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	3	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	4	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129746]
	5	Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
	6	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
	7	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]
	8	B. Bollob/z (1985): Random Graphs, Academic Press (19ss).
	9	Imre Csiszar , Janos G. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, Inc., Orlando, FL, 1982
	10	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]
	11	Bonnie Eisenberg , Ronald L. Rivest, On the sample complexity of pac-learning using random and chosen examples, Proceedings of the third annual workshop on Computational learning theory, p.154-162, August 06-08, 1990, Rochester, New York, United States
	12	David Haussler, Learning Conjunctive Concepts in Structural Domains, Machine Learning, v.4 n.1, p.7-40, October 1989 [doi>10.1023/A:1022601210986]
	13	D. Hauuler (1990): Probably approximately correct learning, Eighth National AI Conference, AAAI'90 (1990), 1101-1108.
	14	Tibor Hegedüs, Can Complexity Theory Benefit from Learning Theory?, Proceedings of the European Conference on Machine Learning, p.354-359, April 05-07, 1993
	15	W. Maa~, Gy. Turin (1989): On the complexity of learning with counterexamples, 30. FOCS (1989), 262-267.
	16	W. Muss, Gy. Turin (1990}: On the complexity of learning from counterexaanples and membership queries, 31. FOCS (1990), 203-210.
	17	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]
	18	S. Muggleton, ed. (1992): Inductive Logic Programming, Academic Press (1992).
	19	Balas Kausik Natarajan, Machine learning: a theoretical approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	20	A. R/nyi (1970): Foundations of Probability, Holden-Day (197o).
	21	György Turán, A Survey of Some Aspects of Computational Learning Theory (Extended Abstract), Proceedings of the 8th International Symposium on Fundamentals of Computation Theory, p.89-103, September 09-13, 1991
	22	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 2

	Claudio Gentile , David P. Helmbold, Improved lower bounds for learning from noisy examples: an information-theoretic approach, Proceedings of the eleventh annual conference on Computational learning theory, p.104-115, July 24-26, 1998, Madison, Wisconsin, United States
	Peter Auer , Philip M. Long, Simulating access to hidden information while learning, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.263-272, May 23-25, 1994, Montreal, Quebec, Canada