To appear in ICML97 Option Decision Trees with Majority Votes

We describe an experimental study of Op-tion Decision Trees with majority votes. Op-tion Decision Trees generalize regular deci-sion trees by allowing option nodes in addi-tion to decision nodes; such nodes allow for several possible tests to be conducted instead of the commonly used single test. Our goal was to explore when option nodes are most useful and to control the growth of the trees so that additional complexity of little utility is limited. Option Decision Trees can reduce the error of decision trees on real-world prob-lems by combining multiple options, with the motivation similar to that of voting algo-rithms that learn multiple models and com-bine the predictions. However, unlike vot-ing algorithms, an Option Decision Tree pro-vides a single structured classier (one deci-sion tree), which can be interpreted more eas-ily by humans. Our results show that for the tested problems, we can achieve signicant reduction in error rates for trees restricted to two levels of option nodes at the top. When very large Option Decision Trees are built, Option Decision Trees outperform Bagging in reducing error, although the trees are much larger and cannot be reasonably interpreted by humans.