ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Efficient noise-tolerant learning from statistical queries
Full text PdfPdf (1.50 MB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents
San Diego, California, United States
Pages: 392 - 401  
Year of Publication: 1993
ISBN:0-89791-591-7
Author
Michael Kearns
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 19,   Citation Count: 50
Additional Information:

references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167200
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
Eric B. Baum , Yuh-Dauh Lyuu, The transition to perfect generalization in perceptrons, Neural Computation, v.3 n.3, p.386-401, Fall 1991
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
A. Ehrenfeucht , David Haussler , Michael Kearns , Leslie Valiant, A general lower bound on the number of examples needed for learning, Proceedings of the first annual workshop on Computational learning theory, p.139-154, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
 
5
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
 
6
E. Gardner and B. Derrida. Three unfinished works on the optimal storage capacity of networks. 3. Phys. A: Math. Gen., 22:1983-1994, 1989.
 
7
Thomas Hancock , Yishay Mansour, Learning monotone ku DNF formulas on product distributions, Proceedings of the fourth annual workshop on Computational learning theory, p.179-183, August 05-07, 1991, Santa Cruz, California, United States
 
8
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]
 
9
David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning integer lattices, SIAM Journal on Computing, v.21 n.2, p.240-266, April 1992  [doi>10.1137/0221019]
 
10
Michael J. Kearns, Computational Complexity of Machine Learning, MIT Press, Cambridge, MA, 1990
11
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]
12
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]
 
13
Michael Kearns , Leonard Pitt, A polynomial-time algorithm for learning k-variable pattern languages from examples, Proceedings of the second annual workshop on Computational learning theory, p.57-71, December 1989, Santa Cruz, California, United States
 
14
Michael J. Kearns , Robert E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, v.48 n.3, p.464-497, June 1994  [doi>10.1016/S0022-0000(05)80062-5]
 
15
Philip D. Laird, Learning from good and bad data, Kluwer Academic Publishers, Norwell, MA, 1988
 
16
Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform, and learnability. In 6!Oth Annual Symposium on Foundations of Computer Science, pages 574-579, October 1989.
 
17
Marvin L. Minsky , Seymour A. Papert, Perceptrons: expanded edition, MIT Press, Cambridge, MA, 1988
18
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]
 
19
Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987  [doi>10.1023/A:1022607331053]
 
20
Yasubumi Sakakibara. Algorithmic Learning of Formal Languages and Decision Trees. PhD thesis, Tokyo Institute of Technology, October 1991. Research Report IIAS-RR-91- 22E, International Institute for Advanced Study of Social Information Science, Fujitsu Laboratories, Ltd.
 
21
Robert E. Schapire, Learning probabilistic read-once formulas on product distributions, Proceedings of the fourth annual workshop on Computational learning theory, p.184-198, August 05-07, 1991, Santa Cruz, California, United States
 
22
Robert E. Schapire, The design and analysis of efficient learning algorithms, MIT Press, Cambridge, MA, 1992
 
23
H.S. Seung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Physical Review A, 45(8):6056-6091, April 1992.
 
24
Robert Sloan, Types of noise in data for concept learning, Proceedings of the first annual workshop on Computational learning theory, p.91-96, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
25
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]
 
26
L. G. Valiant. Learning disjunctions of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, pages 560-566, August 1985.
 
27
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.

CITED BY  50
John Langford , Avrim Blum, Microchoice bounds and self bounding learning algorithms, Proceedings of the twelfth annual conference on Computational learning theory, p.209-214, July 07-09, 1999, Santa Cruz, California, United States
 
Avrim Blum , Adam Kalai, A Note on Learning from Multiple-Instance Examples, Machine Learning, v.30 n.1, p.23-29, Jan. 1998
 
Philip M. Long , Lei Tan, PAC Learning Axis-aligned Rectangles with Respect toProduct Distributions from Multiple-Instance Examples, Machine Learning, v.30 n.1, p.7-21, Jan. 1998
 
Avrim Blum , John Dunagan, Smoothed analysis of the perceptron algorithm for linear programming, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.905-914, January 06-08, 2002, San Francisco, California
Yishay Mansour , Mariano Schain, Learning with maximum-entropy distributions, Proceedings of the tenth annual conference on Computational learning theory, p.201-210, July 06-09, 1997, Nashville, Tennessee, United States
 
Yishay Mansour , Mariano Schain, Learning with Maximum-Entropy Distributions, Machine Learning, v.45 n.2, p.123-145, November 2001
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, Simple learning algorithms using divide and conquer, Proceedings of the eighth annual conference on Computational learning theory, p.447-453, July 05-08, 1995, Santa Cruz, California, United States
Tom Bylander, Learning linear threshold functions in the presence of classification noise, Proceedings of the seventh annual conference on Computational learning theory, p.340-347, July 12-15, 1994, New Brunswick, New Jersey, United States
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 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
Dana Ron , Ronitt Rubinfeld, Learning fallible finite state automata, Proceedings of the sixth annual conference on Computational learning theory, p.218-227, July 26-28, 1993, Santa Cruz, California, 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, 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
 
Ke Yang, New lower bounds for statistical query learning, Journal of Computer and System Sciences, v.70 n.4, p.485-509, June 2005
Andreas Birkendorf , Eli Dichterman , Jeffrey Jackson , Norbert Klasner , Hans Ulrich Simon, On restricted-focus-of-attention learnability of Boolean functions, Proceedings of the ninth annual conference on Computational learning theory, p.205-216, June 28-July 01, 1996, Desenzano del Garda, Italy
Yoav Freund, Self bounding learning algorithms, Proceedings of the eleventh annual conference on Computational learning theory, p.247-258, July 24-26, 1998, Madison, Wisconsin, United States
Avrim Blum , Merrick Furst , Jeffrey Jackson , Michael Kearns , Yishay Mansour , Steven Rudich, Weakly learning DNF and characterizing statistical query learning using Fourier analysis, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.253-262, May 23-25, 1994, Montreal, Quebec, Canada
 
Adam R. Klivans , Alexander A. Sherstov, Unconditional lower bounds for learning intersections of halfspaces, Machine Learning, v.69 n.2-3, p.97-114, December 2007
 
Jeffrey Jackson, On the Efficiency of Noise-Tolerant PAC Algorithms Derived from Statistical Queries, Annals of Mathematics and Artificial Intelligence, v.39 n.3, p.291-313, November 2003
Leslie G. Valiant, A neuroidal architecture for cognitive computation, Journal of the ACM (JACM), v.47 n.5, p.854-882, Sept. 2000
Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States
Sally A. Goldman , Stephen S. Kwek , Stephen D. Scott, Agnostic learning of geometric patterns (extended abstract), Proceedings of the tenth annual conference on Computational learning theory, p.325-333, July 06-09, 1997, Nashville, Tennessee, United States
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
 
François Denis , Rémi Gilleron , Fabien Letouzey, Learning from positive and unlabeled examples, Theoretical Computer Science, v.348 n.1, p.70-83, 2 December 2005
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
 
Pabitra Mitra , C. A. Murthy , Sankar K. Pal, A Probabilistic Active Support Vector Learning Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.3, p.413-418, March 2004
Nader H. Bshouty , Christino Tamon, On the Fourier spectrum of monotone functions, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.219-228, May 29-June 01, 1995, Las Vegas, Nevada, United States
 
Nader H. Bshouty , Nadav Eiron , Eyal Kushilevitz, PAC learning with nasty noise, Theoretical Computer Science, v.288 n.2, p.255-275, 16 October 2002
Nader H. Bshouty , Christino Tamon, On the Fourier spectrum of monotone functions, Journal of the ACM (JACM), v.43 n.4, p.747-770, July 1996
 
Dana Angluin , Mārtiņš Kriķis , Robert H. Sloan , György Turán, Malicious Omissions and Errors in Answers to Membership Queries, Machine Learning, v.28 n.2-3, p.211-255, Aug./Sept. 1997
 
Alexander A. Sherstov, Halfspace Matrices, Computational Complexity, v.17 n.2, p.149-178, May 2008
Michael Kearns , Yishay Mansour , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, On the learnability of discrete distributions, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.273-282, May 23-25, 1994, Montreal, Quebec, Canada
 
Nader H. Bshouty , Vitaly Feldman, On using extended statistical queries to avoid membership queries, The Journal of Machine Learning Research, 2, p.359-395, 3/1/2002
Elchanan Mossel , Sébastien Roch, Learning nonsingular phylogenies and hidden Markov models, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
 
Ghaith Hammouri , Erdinç Öztürk , Berk Sunar, A tamper-proof and lightweight authentication scheme, Pervasive and Mobile Computing, v.4 n.6, p.807-818, December, 2008
 
Min-Ling Zhang , Zhi-Hua Zhou, Adapting RBF Neural Networks to Multi-Instance Learning, Neural Processing Letters, v.23 n.1, p.1-26, February 2006
 
Andreas Birkendorf , Eli Dichterman , Jeffrey Jackson , Norbert Klasner , Hans Ulrich Simon, On Restricted-Focus-of-Attention Learnability of Boolean Functions, Machine Learning, v.30 n.1, p.89-123, Jan. 1998
Nader H. Bshouty , Jeffrey C. Jackson, Learning DNF over the uniform distribution using a quantum example oracle, Proceedings of the eighth annual conference on Computational learning theory, p.118-127, 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
Peter Auer , Philip M. Long , Aravind Srinivasan, Approximating hyper-rectangles: learning and pseudo-random sets, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.314-323, May 04-06, 1997, El Paso, Texas, United States
 
Amir Globerson , Naftali Tishby, Sufficient dimensionality reduction, The Journal of Machine Learning Research, 3, 3/1/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, On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm, Proceedings of the twelfth annual conference on Computational learning theory, p.296-307, July 07-09, 1999, Santa Cruz, California, United States
Dilek Hakkani-Tür , Giuseppe Riccardi , Gokhan Tur, An active approach to spoken language processing, ACM Transactions on Speech and Language Processing (TSLP), v.3 n.3, p.1-31, October 2006
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
 
Paul W. Goldberg, Learning fixed-dimension linear thresholds from fragmented data, Information and Computation, v.171 n.1, p.98-122, November 25, 2001
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
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
 
Foster Provost , Venkateswarlu Kolluri, A Survey of Methods for Scaling Up Inductive Algorithms, Data Mining and Knowledge Discovery, v.3 n.2, p.131-169, June 1999

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING


General Terms:
Algorithms, Theory, Verification

Collaborative Colleagues:
Michael Kearns: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player