Top-Down Decision Tree Boosting and Its Applications

Top-down algorithms such as C4.5 and CART for constructing decision trees are known to perform boosting, with the procedure of choosing classification rules at internal nodes regarded as the base learner. In this work, by introducing a notion of pseudo-entropy functions for measuring the loss of hypotheses, we give a new insight into this boosting scheme from an information-theoretic viewpoint: Whenever the base learner produces hypotheses with non-zero mutual information, the top-down algorithm reduces the conditional entropy (uncertainty) about the target function as the tree grows. Although its theoretical guarantee on its performance is worse than other popular boosting algorithms such as AdaBoost, the top-down algorithms can naturally treat multiclass classification problems. Furthermore we propose a base learner LIN that produces linear classification functions and carry out some experiments to examine the performance of the top-down algorithm with LIN as the base learner. The results show that the algorithm can sometimes perform as well as or better than AdaBoost.