When a decision tree learner has plenty of time

The majority of the existing algorithms for learning de-cision trees are greedy—a tree is induced top-down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally opti-mal. Furthermore, the greedy algorithms require a fixed amount of time and are not able to generate a better tree if additional time is available. To overcome this problem, we present a lookahead-based algorithm for anytime induction of decision trees which allows trad-ing computational speed for tree quality. The algorithm uses a novel strategy for evaluating candidate splits; a stochastic version of ID3 is repeatedly invoked to esti-mate the size of the tree in which each split results, and the split that minimizes the expected size is preferred. Experimental results indicate that for several hard con-cepts, our proposed approach exhibits good anytime behavior and yields significantly better decision trees when more time is available