Abstract
We propose a new boosting algorithm. This boosting algorithm is an adaptive version of the boost by majority algorithm and combines bounded goals of the boost by majority algorithm with the adaptivity of AdaBoost.
The method used for making boost-by-majority adaptive is to consider the limit in which each of the boosting iterations makes an infinitesimally small contribution to the process as a whole. This limit can be modeled using the differential equations that govern Brownian motion. The new boosting algorithm, named BrownBoost, is based on finding solutions to these differential equations.
The paper describes two methods for finding approximate solutions to the differential equations. The first is a method that results in a provably polynomial time algorithm. The second method, based on the Newton-Raphson minimization procedure, is much more efficient in practice but is not known to be polynomial.
Article PDF
Similar content being viewed by others
References
Breiman, L. (1992). Probability. SIAM, classics edition. Original edition first published in 1968.
Breiman, L. (1996). Bagging predictors. Machine Learning, 24:2, 123–140.
Dietterich, T. G. (2000). An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization. Machine Learning, 40:2, 139–158.
Freund,Y. (1995). Boosting a weak learning algorithm by majority. Information and Computation, 121:2, 256–285.
Freund, Y., & Opper, M. (2000). Continuous drifting games. In Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (pp. 126–132). Morgan Kaufman.
Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55:1, 119–139.
Friedman, J., Hastie, T., & Tibshirani, R. (1998). Additive logistic regression: A statistical view of boosting. Technical Report.
Mason, L., Bartlett, P., & Baxter, J. (1998). Direct optimization of margins improves generalization in combined classifiers. Technical report, Deparment of Systems Engineering, Australian National University.
Schapire, R. E. (1990). The strength of weak learnability. Machine Learning, 5:2, 197–227.
Schapire, R. E. (2001). Drifting games. Machine Learning, 43:3, 265–291.
Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26:5, 1651–1686.
Schapire, R. E., & Singer, Y. (1999). Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37:3, 297–336.
Stoler, J., & Bulrisch, R. (1992). Introduction to Numerical Analysis. Springer-Verlag.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Freund, Y. An Adaptive Version of the Boost by Majority Algorithm. Machine Learning 43, 293–318 (2001). https://doi.org/10.1023/A:1010852229904
Issue date:
DOI: https://doi.org/10.1023/A:1010852229904