Experiences with OB1, An Optimal Bayes Decision Tree Learner

In machine learning, algorithms for inferring decision trees typically choose a single #best" tree to describe the training data, although recent research has shown that classi#cation performance can be signi#cantly improved by voting predictions of multiple, independently produced decision trees. This paper describes a new algorithm, OB1, that weights the predictions of any scheme capable of inferring probability distributions. We described an implementation, OB1, that includes all decision trees, as well as naiveBayesian models. Results indicate that OB1 is a very strong robust learner and makes plausible the claim that it successfully subsumes other techniques such as boosting and bagging that attempt to combine many models into a single prediction