Topdown induction of decision trees: rigorous guarantees and inherent limitations Consider the following heuristic for building a decision tree for a function f : 0,1n to pm 1. Place the most influential variable x_i of f at the root, and recurse on the subfunctions f_x_i0 and f_x_i1 on the left and right subtrees respectively; terminate once the tree is an varepsilonapproximation of f. We analyze the quality of this heuristic, obtaining nearmatching upper and lower bounds:  :66,93,Upper bound: For every f with decision tree size s and every varepsilon in (0,frac12), this heuristic builds a decision tree of size at most sO(log(svarepsilon)log(1varepsilon)).  Lower bound: For every varepsilon in (0,frac12) and s le 2tildeO(sqrtn), there is an f with decision tree size s such that this heuristic builds a decision tree of size stildeOmega(log s).  :126,also obtain upper and lower bounds for monotone functions: sO(sqrtlog svarepsilon) and stildeOmega(sqrt4log s  ) respectively. The lower bound disproves conjectures of Fiat and Pechyony (2004) and Lee (2009).  upper bounds :157,yield new algorithms for properly learning decision trees under the uniform distribution. We show that these algorithmswhich are motivated by widely employed and empirically successful topdown decision tree learning heuristics such as ID3, C4.5, and CARTachieve provable guarantees that compare favorably with those of the current fastest algorithm (Ehrenfeucht and Haussler, 1989). Our lower bounds shed new light on the limitations of these heuristics.  :224,we revisit the classic work of Ehrenfeucht and Haussler. We extend it to give the first uniformdistribution proper learning algorithm that achieves polynomial sample and memory complexity, while matching its stateoftheart quasipolynomial runtime.

An Online TreeBased Approach for Mining NonStationary HighSpeed Data Streams This paper presents a new learning algorithm for inducing decision trees from data streams. In these domains, large amounts of data are constantly arriving over time, possibly at high speed. The proposed algorithm uses a topdown induction method for building trees, splitting leaf nodes recursively, until none of them can be expanded. The new algorithm combines two split methods in the tree induction. The first method is able to guarantee, with statistical significance, that each split chosen would be the same as that chosen using infinite examples. By doing so, it aims at ensuring that the tree induced online is close to the optimal model. However, this split method often needs too many examples to make a decision about the best split, which delays the accuracy improvement of the online predictive learning model. Therefore, the second method is used to split nodes more quickly, speeding up the tree growth. The second split method is based on the observation that larger trees are able to store more information about the training examples and to represent more complex concepts. The first split method is also used to correct splits previously suggested by the second one, when it has sufficient evidence. Finally, an additional procedure rebuilds the tree model according to the suggestions made with an adequate level of statistical significance. The proposed algorithm is empirically compared with several wellknown induction algorithms for learning decision trees from data streams. In the tests it is possible to observe that the proposed algorithm is more competitive in terms of accuracy and model size using various synthetic and real world datasets.