E. Takimoto et al., Predicting nearly as well as the best pruning of a decision tree through dynamic programming scheme, THEOR COMP, 261(1), 2001, pp. 179-209
Helmbold and Schapire gave an on-line prediction algorithm that, when given
an unpruned decision tree, produces predictions not much worse than the pr
edictions made by the best pruning of the given decision tree. In this pape
r, we give two new on-line algorithms. The first algorithm is based on the
observation that finding the best pruning can be efficiently solved by a dy
namic programming in the "batch" setting where all the data to be predicted
are given in advance. This algorithm works well for a wide class of Loss f
unctions, whereas the one given by Helmbold and Schapire is only described
for the absolute loss function. Moreover, the algorithm given in this paper
is so simple and general that it could be applied to many other on-line op
timization problems solved by dynamic programming. We also explore the seco
nd algorithm that is competitive not only with the best pruning but also wi
th the best prediction values which are associated with nodes in the decisi
on tree. In this setting, a greatly simplified algorithm is given for the a
bsolute loss function. It can be easily generalized to the case where, inst
ead of using decision trees, data are classified in some arbitrarily fixed
manner. (C) 2001 Elsevier Science B.V. All rights reserved.