Statistical queries and faulty PAC oracles

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Statistical queries and faulty PAC oracles

Full text

Pdf (870 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: 262 - 268

Year of Publication: 1993

ISBN:0-89791-611-5

Author

Scott Evan Decatur

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

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.168346 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 , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	2	Peter L. Bartlett, Learning with a slowly changing distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.243-252, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130412]
	3	Peter L. Bartlett , Robert C. Williamson, Investigating the distribution assumptions in the Pac learning model, Proceedings of the fourth annual workshop on Computational learning theory, p.24-32, August 05-07, 1991, Santa Cruz, California, United States
	4	Shai Ben-David , Alon Itai , Eyal Kushilevtiz, Learning by distances, Proceedings of the third annual workshop on Computational learning theory, p.232-245, August 06-08, 1990, Rochester, New York, United States
	5	Gyora M. Benedek , Alon Itai, Learnability by fixed distributions, Proceedings of the first annual workshop on Computational learning theory, p.80-90, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	6	Gyora M. Benedek , Alon Itai, Dominating distributions and learnability, Proceedings of the fifth annual workshop on Computational learning theory, p.253-264, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130413]
	7	R. Board , L. Pitt, On the necessity of Occam algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.54-63, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100223]
	8	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]
	9	Merrick L. Furst , Jeffrey C. Jackson , Sean W. Smith, Improved learning of AC0 functions, Proceedings of the fourth annual workshop on Computational learning theory, p.317-325, August 05-07, 1991, Santa Cruz, California, United States
	10	Thomas R. Hancock, Learning 2u DNF formulas and ku decision trees, Proceedings of the fourth annual workshop on Computational learning theory, p.199-212, August 05-07, 1991, Santa Cruz, California, United States
	11	D. Haussler, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, Artificial Intelligence, v.36 n.2, p.177-221, September 1988 [doi>10.1016/0004-3702(88)90002-1]
	12	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]
	13	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
	14	Michael J. Kearns, Computational Complexity of Machine Learning, MIT Press, Cambridge, MA, 1990
	15	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]
	16	Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. In Proceedings of the Thsrtieth Annual Symposmm on Foundations of Computer Science, pages 574-579, Research Triangle Park, North Carolina, October 1989.
	17	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	18	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]
	19	L. G. Valiant. Learning disjunctions of conjunctions. In Proceedings IJCAI 1985, pages 560-566. Morgan Kaufmann, August 1985.

CITED BY 12

	Scott E. Decatur , Rosario Gennaro, On learning from noisy and incomplete examples, Proceedings of the eighth annual conference on Computational learning theory, p.353-360, July 05-08, 1995, Santa Cruz, California, United States
	Javed A. Aslam , Scott E. Decatur, Specification and simulation of statistical query algorithms for efficiency and noise tolerance, Proceedings of the eighth annual conference on Computational learning theory, p.437-446, July 05-08, 1995, Santa Cruz, California, United States
	Avrim Blum , Adam Kalai , Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.435-440, May 21-23, 2000, Portland, Oregon, United States
	Nader H. Bshouty , Sally A. Goldman , H. David Mathias , Subhash Suri , Hisao Tamaki, Noise-tolerant distribution-free learning of general geometric concepts, Journal of the ACM (JACM), v.45 n.5, p.863-890, Sept. 1998
	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
	Wolfgang Maass, Efficient agnostic PAC-learning with simple hypothesis, Proceedings of the seventh annual conference on Computational learning theory, p.67-75, July 12-15, 1994, New Brunswick, New Jersey, 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
	Sally A. Goldman , Stephen D. Scott, A Theoretical and Empirical Study of a Noise-TolerantAlgorithm to Learn Geometric Patterns, Machine Learning, v.37 n.1, p.5-49, Oct. 1999
	Avrim Blum , Adam Kalai , Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Journal of the ACM (JACM), v.50 n.4, p.506-519, July 2003
	Dan Roth, Learning in natural language: theory and algorithmic approaches, Proceedings of the 2nd workshop on Learning language in logic and the 4th conference on Computational natural language learning, September 13-14, 2000, Lisbon, Portugal
	Rocco A. Servedio, Smooth boosting and learning with malicious noise, The Journal of Machine Learning Research, 4, p.633-648, 12/1/2003
	Dan Roth, Learning in natural language, Proceedings of the 16th international joint conference on Artificial intelligence, p.898-904, July 31-August 06, 1999, Stockholm, Sweden