Improved AdaBoost.M1 of decision trees with confidence-rated predictions

ABSTRACT

This paper proposes an algorithm to integrate AdaBoost.M1 with the decision trees that output confidence-rated predictions, which is done by transforming decision trees from "expert" models to "specialist" models that may abstain when the confidence is less than 1/2. The confidence is used to update the instance weights during the boosting process, and it is also used to determine the vote weights of base classifiers in decision process. This makes the algorithm a "dynamic" one, in that: (1) for a given test instance, only those whose confidences are higher than 1/2 can vote on the decision making; and (2) the vote weight of each base classifier is dependent on the confidence that the classifier has on the target instance. Experimental results with C4.5 decision tree learner as the base learning algorithm have shown that this algorithm has significantly outperformed both the base algorithm and the AdaBoost.M1 of the C4.5 decision trees with simple predictions.

REFERENCES

• 1: Blake, C., Keogh, E., & Merz, C. J. UCI Repository of Machine Learning Databases. http://www.ics.uci.edu/~mlearn/MLRepository.html. Irvine, CA: University of California, Department of Information and Computer Science, 1998
• 2: Avrim Blum, Empirical Support for Winnow and Weighted-MajorityAlgorithms: Results on a Calendar Scheduling Domain, Machine Learning, v.26 n.1, p.5-23, Jan. 1997 [doi>10.1023/A:1007335615132]
• 3: Freund, Y. and Schapire, R. E. Experiments with a new boosting algorithm. In Machine Learning: Proceedings of the Thirteenth International Conference, 148--156, 1996
• 4: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 5: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 6: Quinlan, J. R. Bagging, Boosting, and C4.5. Proceedings of the Thirteenth National Conference on Artificial Intelligence, pp. 725--730, 1996.
• 7: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]
• 8: Schapire, R. E. The boosting approach to machine learning: An overview. In D. D. Denison, M. H. Hansen, C. Holmes, B. Mallick, B. Yu, editors, Nonlinear Estimation and Classification. Springer, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

General Terms:
Algorithms

Keywords:
AdaBoost, confidence-rated predictions, decision trees