An improved boosting algorithm and its implications on learning complexity

ABSTRACT

In this work we present some improvements and extensions to previous work on boosting weak learners [Sch90, Fre90]. Our main result is an improvement of the boosting-by-majority algorithm. One implication of the performance of this algorithm is that if a concept class can be learned in the PAC model to within some fixed error smaller than 1/2, then it can be learned to within an arbitrarily small error &egr; > 0 with time complexity 0((1/&egr;)(log 1/&egr;)2) (fixing the sample space and concept class and the required reliability). We show that the majority rule is the optimal rule for combining general weak learners. We also extend the boosting algorithm to concept classes that give multi-valued labels and real-valued labels.

REFERENCES

• AHS85: D.H. Ackley, G. E. Hinton, and T. J. Sejnowski. A learning algorithm for Boltzmann machines. Cognitive Science, 9:147- 169, 1985.
• BEHW86: A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12158]
• 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]
• HLW88: David Haussler, Nick Littlestone, and Manfred Warmuth. Predicting 0,1-functions on randomly drawn points. In Proceedings of the ~gth Annual Symposium on the Foundations of Computer Science, pages 100-109. IEEE, 1988.
• KV89: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• LW89: Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. In 30th Annual IEEE Symposium on Foundations of Computer Science, pages 256-261, 1989.
• 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]
• Sch91: Robert Elias Schapire, The design and analysis of efficient learning algorithms, Massachusetts Institute of Technology, Cambridge, MA, 1992
• Sch92: Robert E. Schapire. private correspondence, January 1992.
• 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]

INDEX TERMS

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

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

General Terms:
Algorithms, Performance, Theory, Verification