A Simple Algorithm for Predicting Nearly as Well as the Best Pruning Labeled with the Best Prediction Values of a Decision Tree

Abstract

Given an unpruned decision tree, Helmbold and Schapire gave an on-line prediction algorithm whose performance will not be much worse than the predictions made by the best pruning of the given decision tree. In this paper, based on the observation that finding the best pruning can be efficiently solved by a dynamic programming in the “batch” setting where all the data to be predicted are given in advance, a new on-line prediction algorithm is constructed. Although it is shown that its performance is slightly weaker than Helmbold and Schapire's algorithm with respect to the loss bound, it is so simple and general that it could be applied to many on-line optimization problems solved by dynamic programming. We also explore algorithms that are competitive not only with the best pruning but also with the best prediction values. In this setting, a greatly simplified algorithm is given, and it is shown that the algorithm can easily be generalized to the case where, instead of using decision trees, data are classified in some arbitrarily fixed manner.