Article

On the Boosting Pruning Problem

Authors:

Christino Tamon,

Jie XiangAuthors Info & Claims

ECML '00: Proceedings of the 11th European Conference on Machine Learning

Pages 404 - 412

Published: 31 May 2000 Publication History

Abstract

Boosting is a powerful method for improving the predictive accuracy of classifiers. The ADABOOST algorithm of Freund and Schapire has been successfully applied to many domains [2, 10, 12] and the combination of ADABOOST with the C4.5 decision tree algorithm has been called the best off-the-shelf learning algorithm in practice. Unfortunately, in some applications, the number of decision trees required by ADABOOST to achieve a reasonable accuracy is enormously large and hence is very space consuming. This problem was first studied by Margineantu and Dietterich [7], where they proposed an empirical method called Kappa pruning to prune the boosting ensemble of decision trees. The Kappa method did this without sacrificing too much accuracy. In this work-in-progress we propose a potential improvement to the Kappa pruning method and also study the boosting pruning problem from a theoretical perspective. We point out that the boosting pruning problem is intractable even to approximate. Finally, we suggest a margin-based theoretical heuristic for this problem.

References

[1]

Y. Freund and R.E. Schapire. A decision-theoretic generalization of online learning and an application to boosting. J. Comp. System Sciences, 55(1):119-139, 1997.

Crossref

Google Scholar

[2]

Y. Freund and R.E. Schapire. Experiments with a New Boosting Algorithm. Proc. 13th Int. Conf. on Machine Learning, 148-156, 1996.

Google Scholar

[3]

M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.

Crossref

Google Scholar

[4]

D. Hochbaum. Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997.

Crossref

Google Scholar

[5]

W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. J. American Stat. Assoc., 58:13-30, 1963.

Google Scholar

[6]

V. Kann. Polynomially bounded minimization problems that are hard to approximate. Nordic Journal of Computing, 1:317-331, 1994.

Crossref

Google Scholar

[7]

D. Margineantu and T.G. Dietterich. Pruning Adaptive Boosting. Proc. 14th Int. Conf. Machine Learning, 211-218, 1997.

Crossref

Google Scholar

[8]

C.J. Merz and P.M. Murphy. UCI Repository of Machine Learning Databases. Tech. Report, U.C. Irvine, CA.

Google Scholar

[9]

J.R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.

Crossref

Google Scholar

[10]

J.R. Quinlan. Bagging, Boosting, and C4.5. Proc. 13th Nat. Conf. Artificial Intelligence, 725-730, 1996.

Crossref

Google Scholar

[11]

R.E. Schapire, Y. Freund, P. Bartlett, and W.S. Lee. Boosting the Margin: a new explanation of the effectiveness of voting methods. The Annals of Statistics, 26(5):1651-1686, 1998.

Google Scholar

[12]

R.E. Schapire and Y. Singer. Improved Boosting Algorithms using Confidence-rated Predictions. Proc. 11th Ann. Conf. Comp. Learning Theory, 80-91, 1998.

Crossref

Google Scholar

Cited By

View all

AL-Qutami TIbrahim RIsmail IIshak M(2018)Virtual multiphase flow metering using diverse neural network ensemble and adaptive simulated annealingExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.10.01493:C(72-85)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.eswa.2017.10.014
Wang HBlanton R(2016)Ensemble Reduction via Logic MinimizationACM Transactions on Design Automation of Electronic Systems10.1145/289751521:4(1-17)Online publication date: 27-May-2016
https://dl.acm.org/doi/10.1145/2897515
Bhardwaj MBhatnagar VSharma K(2016)Cost-effectiveness of classification ensemblesPattern Recognition10.1016/j.patcog.2016.03.01757:C(84-96)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.patcog.2016.03.017
Show More Cited By

Index Terms

On the Boosting Pruning Problem
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by classification
    2. Machine learning approaches
      1. Classification and regression trees

Recommendations

On the boosting pruning problem
ECML'00: Proceedings of the 11th European Conference on Machine Learning

Boosting is a powerful method for improving the predictive accuracy of classifiers. The ADABOOST algorithm of Freund and Schapire has been successfully applied to many domains [2, 10, 12] and the combination of ADABOOST with the C4.5 decision tree ...
Boosting recombined weak classifiers

Boosting is a set of methods for the construction of classifier ensembles. The differential feature of these methods is that they allow to obtain a strong classifier from the combination of weak classifiers. Therefore, it is possible to use boosting ...
Using boosting to prune bagging ensembles

Boosting is used to determine the order in which classifiers are aggregated in a bagging ensemble. Early stopping in the aggregation of the classifiers in the ordered bagging ensemble allows the identification of subensembles that require less memory ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ECML '00: Proceedings of the 11th European Conference on Machine Learning

May 2000

452 pages

ISBN:3540676023

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 31 May 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

AL-Qutami TIbrahim RIsmail IIshak M(2018)Virtual multiphase flow metering using diverse neural network ensemble and adaptive simulated annealingExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.10.01493:C(72-85)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.eswa.2017.10.014
Wang HBlanton R(2016)Ensemble Reduction via Logic MinimizationACM Transactions on Design Automation of Electronic Systems10.1145/289751521:4(1-17)Online publication date: 27-May-2016
https://dl.acm.org/doi/10.1145/2897515
Bhardwaj MBhatnagar VSharma K(2016)Cost-effectiveness of classification ensemblesPattern Recognition10.1016/j.patcog.2016.03.01757:C(84-96)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.patcog.2016.03.017
Galar MFernández ABarrenechea EBustince HHerrera F(2016)Ordering-based pruning for improving the performance of ensembles of classifiers in the framework of imbalanced datasetsInformation Sciences: an International Journal10.1016/j.ins.2016.02.056354:C(178-196)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.ins.2016.02.056
(2016)Decision forestInformation Fusion10.1016/j.inffus.2015.06.00527:C(111-125)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.inffus.2015.06.005
Ma ZDai Q(2016)Selected an Stacking ELMs for Time Series PredictionNeural Processing Letters10.1007/s11063-016-9499-944:3(831-856)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s11063-016-9499-9
Ma ZDai QLiu N(2015)Several novel evaluation measures for rank-based ensemble pruning with applications to time series predictionExpert Systems with Applications: An International Journal10.1016/j.eswa.2014.07.04942:1(280-292)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.eswa.2014.07.049
Sheen SAnitha RSirisha P(2013)Malware detection by pruning of parallel ensembles using harmony searchPattern Recognition Letters10.1016/j.patrec.2013.05.00634:14(1679-1686)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1016/j.patrec.2013.05.006
Mendes-Moreira JSoares CJorge ASousa J(2012)Ensemble approaches for regressionACM Computing Surveys10.1145/2379776.237978645:1(1-40)Online publication date: 7-Dec-2012
https://dl.acm.org/doi/10.1145/2379776.2379786
Ulaş AYıLdıZ OAlpaydıN E(2012)Eigenclassifiers for combining correlated classifiersInformation Sciences: an International Journal10.1016/j.ins.2011.10.024187(109-120)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1016/j.ins.2011.10.024
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations