Some weak learning results

ABSTRACT

An algorithm is a weak learner if with some small probability it outputs a hypothesis with error slightly below 50%. This paper presents sufficient conditions for weak learning. Our main result requires a “consistency oracle” for the concept class F which decides for a given set of examples whether there is a concept in F consistent with the examples. We show that such an oracle can be used to construct a computationally efficient weak learning algorithm for F if F is learnable at all. We consider consistency oracles which are allowed to give wrong answers and discusses how the number of incorrect answers effects the oracle's use in computationally efficient weak learning algorihms. We also define “weak Occam algorithms” which, when given a set of m examples, select a consistent hypothesis from some class of 2m-(1/p(m)) possible hypotheses. We show that these weak Occam algorithms are also weak learners. In contrast, we show that an Occam style algorithm which selects a consistent hypothesis from a class of 2m+1-2 hypotheses is not a weak learner.

REFERENCES

• AHW87: N. Alon , D. Haussler , E. Welzl, Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension, Proceedings of the third annual symposium on Computational geometry, p.331-340, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41994]
• BEHW87: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• BEHW89: 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]
• Bon72: J. A. Bondy. Induced subsets. Journal of Combtnatorzal Theory, 12( B):21)1-202, 1972.
• Fre90: Yoav Freund, Boosting a weak learning algorithm by majority, Proceedings of the third annual workshop on Computational learning theory, p.202-216, August 06-08, 1990, Rochester, New York, United States
• HKLW91: David Haussler , Michael Kearns, Equivalence of models for polynomial learnability, Information and Computation, v.95 n.2, p.129-161, Dec. 1991 [doi>10.1016/0890-5401(91)90042-Z]
• HKS91: David Haussler , Michael Kearns , Robert Schapire, Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension, Proceedings of the fourth annual workshop on Computational learning theory, p.61-74, August 05-07, 1991, Santa Cruz, California, United States
• HLW: D. Haussler , N. Littlestone , M. K. Warmuth, Predicting {0, 1}-functions on randomly drawn points, Information and Computation, v.115 n.2, p.248-292, Dec. 1994 [doi>10.1006/inco.1994.1097]
• HW92: D. Helrnbold and M. K. Warmuth. On weak learning. In Proceedings of the Third NEC Research Symposium on Computational Learning and Cognition, SIAM, 3600 University City Science Center, Philadelphia, PA 19104-2688, May 1992.
• KV89: Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994 [doi>10.1145/174644.174647]
• Sau72: N. Sauer. On the density of families of sets. Journal of Combinatorial Theory (Series A), 13:145-147, 1972.
• Sch90: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• Val84: 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]
• VC71: V. N. Vapnik and A. Ya. Chervonenlkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Pro babtltty and its Application, 16(2):264-280, 1971.
• Vov90: Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification