Abstract
We improve the analysis of the decision tree boosting algorithm proposed by Mansour and McAllester. For binary classification problems, the algorithm of Mansour and McAllester constructs a multiway branching decision tree using a set of multi-class hypotheses. Mansour and McAllester proved that it works under certain conditions. We give a much simpler analysis of the algorithm and simplify the conditions. From this simplification, we can provide a simpler algorithm, for which no prior knowledge on the quality of weak hypotheses is necessary.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam’s razor. Information Processing Letters, 24:377–380, April 1987.
L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth International Group, 1984.
Carlos Domingo and Osamu Watanabe. MadaBoost: A modification of AdaBoost. In Proceedings of 13th Annual Conference on Computational Learning Theory, pages 180–189. Morgan Kaufmann, San Francisco, 2000.
Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256–285, September 1995.
Yoav Freund and Robert E. Schapire:. A decision-theoretic generalization of online learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997.
M. Kearns and Y. Mansour. On the boosting ability of top-down decision tree learning algorithms. Journal of Computer and System Sciences, 58(1):109–128, 1999.
Y. Mansour and D. McAllester. Boosting with multi-way branching in decision trees. In Advances in Neural Information Processing Systems, volume 12, pages 300–306. The MIT Press, 2000.
J. Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197–227, 1990.
Robert E. Schapire. Using output codes to boost multiclass learning problems. In Proc. 14th International Conference on Machine Learning, pages 313–321. Morgan Kaufmann, 1997.
Robert E. Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3):297–336, 1999.
Eiji Takimoto and Akira Maruoka. On the boosting algorithm for multiclass functions based on information-theoretic criterion for approximation. In Proceedings of the 1st International Conference on Discovery Science, volume 1532 of Lecture Notes in Artificial Intelligence, pages 256–267. Springer-Verlag, 1998.
L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, November 1984.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hatano, K. (2001). A Simpler Analysis of the Multi-way Branching Decision Tree Boosting Algorithm. In: Abe, N., Khardon, R., Zeugmann, T. (eds) Algorithmic Learning Theory. ALT 2001. Lecture Notes in Computer Science(), vol 2225. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45583-3_8
Download citation
DOI: https://doi.org/10.1007/3-540-45583-3_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42875-6
Online ISBN: 978-3-540-45583-7
eBook Packages: Springer Book Archive