Efficient noise-tolerant learning from statistical queries

ABSTRACT

In this paper, we study the problem of learning in the presence of classification noise in the probabilistic learning model of Valiant and its variants. In order to identify the class of “robust” learning algorithms in the most general way, we formalize a new but related model of learning from statistical queries. Intuitively, in this model a learning algorithm is forbidden to examine individual examples of the unknown target function, but is given acess to an oracle providing estimates of probabilities over the sample space of random examples.One of our main results shows that any class of functions learnable from statistical queries is in fact learnable with classification noise in Valiant's model, with a noise rate approaching the information-theoretic barrier of 1/2. We then demonstrate the generality of the statistical query model, showing that practically every class learnable in Valiant's model and its variants can also be learned in the new model (and thus can be learned in the presence of noise). A notable exception to this statement is the class of parity functions, which we prove is not learnable from statistical queries, and for which no noise-tolerant algorithm is known.

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: ASLAM, J. A., AND DECATUR, S.E. 1993. General bounds on statistical query learning and PAC learning with noise via hypothesis boosting. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. pp. 282-291.
• 3: 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 [doi>10.1145/225298.225351]
• 4: Eric B. Baum , Yuh-Dauh Lyuu, The transition to perfect generalization in perceptrons, Neural Computation, v.3 n.3, p.386-401, Fall 1991
• 5: A. Blum , A. Frieze, A polynomial-time algorithm for learning noisy linear threshold functions, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.330, October 14-16, 1996
• 6: 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 [doi>10.1145/195058.195147]
• 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: E. Cohen, Learning noisy perceptrons by a perceptron in polynomial time, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.514, October 19-22, 1997
• 9: 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
• 10: Paul Fischer , Hans Ulrich Simon, On learning ring-sum-expansions, SIAM Journal on Computing, v.21 n.1, p.181-192, Feb. 1992 [doi>10.1137/0221014]
• 11: 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
• 12: GARDNER, E., AND DERRIDA, B. 1989. Three unfinished works on the optimal storage capacity of networks. J. Phys. A: Math. Gen. 22, 1983-1994.
• 13: 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
• 14: 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]
• 15: 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]
• 16: Michael J. Kearns, Computational Complexity of Machine Learning, MIT Press, Cambridge, MA, 1990
• 17: Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
• 18: 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]
• 19: 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
• 20: 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]
• 21: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 22: Philip D. Laird, Learning from good and bad data, Kluwer Academic Publishers, Norwell, MA, 1988
• 23: LINIAL, N., MANSOUR, Y., AND NISAN, N. 1989. Constant depth circuits, Fourier transform, and learnability. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 574-579.
• 24: MINSKY, M., AND PAPERT, S. 1988. Perceptrons: An Introduction to Computational Geometry (Expanded Edition). The MIT Press, Cambridge, Mass.
• 25: 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]
• 26: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• 27: SAKAKIBARA, Y. 1991. Algorithmic learning of formal languages and decision trees. Ph.D. dissertation. Tokyo Institute of Technology. Res. Rep. IIAD-RR-91-22E. International Institute for Advanced Study of Social Information Science, Fujitsu Laboratories, Ltd., Tokyo, Japan.
• 28: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 29: Robert E. Schapire, The design and analysis of efficient learning algorithms, MIT Press, Cambridge, MA, 1992
• 30: SEUNG, H.S., SOMPOLINSKY, H., AND TISHBY, N. 1992. Statistical mechanics of learning from examples. Phys. Rev. A 45, 8 (Apr.), 6056-6091.
• 31: 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
• 32: 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]
• 33: VALIANT, L.G. 1985. Learning disjunctions of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial Intelligence (Aug.). Morgan-Kaufmann, Los Altos, Calif., pp. 560-566.
• 34: VAPNIK, g. N., AND CHERVONENKIS, A. YA. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory Prob. Appl. XVI, 2, 264-280.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
  I.5 PATTERN RECOGNITION

General Terms:
Theory

Keywords:
computational learning theory, machine learning