General bounds on the number of examples needed for learning probabilistic concepts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

General bounds on the number of examples needed for learning probabilistic concepts

Full text

Pdf (1.08 MB)

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: 402 - 411

Year of Publication: 1993

ISBN:0-89791-611-5

Author

Hans Ulrich Simon

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): 15, Citation Count: 8

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.168385 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	Naoki Abe , Manfred K. Warmuth, On the computational complexity of approximating distributions by probabilistic automata, Proceedings of the third annual workshop on Computational learning theory, p.52-66, August 06-08, 1990, Rochester, New York, United States
	2	Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	3	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]
	4	Richard O. Duda and Peter E. Hart. Pattern Classification and Scene Analysis. Wiley-Interscience. John Wiley & Sons, New York, 1973.
	5	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]
	6	William Feller. An Introduction to Probability Theory and its Applications, volume 1. John Wiley & Sons, New York, third edition, 1968.
	7	David Haussler. Generalizing the pac model: Sample size bounds from metric-dimension based uniform convergence results. In Proceedings of the SO'th Annual Symposium on the Foundations of Computer Science, pages 40-46, 1989.
	8	Michael J. Kearns and Robert E. Schapire. Efficient distribution-free learning of probabilistic concepts. In Proceedings of the 31'th Annual Symposium on the Foundations of Computer Science, pages 382- 392, 1990.
	9	Philip D. Laird, Learning from good and bad data, Kluwer Academic Publishers, Norwell, MA, 1988
	10	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]
	11	Kenji Yamanishi, A Learning Criterion for Stochastic Rules, Machine Learning, v.9 n.2-3, p.165-203, July 1992 [doi>10.1007/BF00992676]

CITED BY 8

	András Antos , Gábor Lugosi, Strong minimax lower bounds for learning, Proceedings of the ninth annual conference on Computational learning theory, p.303-309, June 28-July 01, 1996, Desenzano del Garda, Italy
	Nicolò Cesa-Bianchi , Eli Dichterman , Paul Fischer , Hans Ulrich Simon, Noise-tolerant learning near the information-theoretic bound, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.141-150, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Scott Decatur , Oded Goldreich , Dana Ron, Computational sample complexity, Proceedings of the tenth annual conference on Computational learning theory, p.130-142, July 06-09, 1997, Nashville, Tennessee, United States
	Nader H. Bshouty , Jeffrey C. Jackson , Christino Tamon, Uniform-distribution attribute noise learnability, Proceedings of the twelfth annual conference on Computational learning theory, p.75-80, July 07-09, 1999, Santa Cruz, California, United States
	David Haussler , H. Sebastian Seung , Michael Kearns , Naftali Tishby, Rigorous learning curve bounds from statistical mechanics, Proceedings of the seventh annual conference on Computational learning theory, p.76-87, July 12-15, 1994, New Brunswick, New Jersey, United States
	Nader H. Bshouty , Jeffrey C. Jackson , Christino Tamon, Uniform-distribution attribute noise learnability, Information and Computation, v.187 n.2, p.277-290, 15 December 2003
	Rakesh D. Barve , Philip M. Long, On the complexity of learning from drifting distributions, Proceedings of the ninth annual conference on Computational learning theory, p.122-130, June 28-July 01, 1996, Desenzano del Garda, Italy
	Fabian M. Suchanek , Georgiana Ifrim , Gerhard Weikum, Combining linguistic and statistical analysis to extract relations from web documents, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA