Decision trees

Linear regressors from X = R to Y = R have a limited expressive power, because they fit K affine functions to the training set. Functions that are more complex than that are approximated poorly. Similarly, K-class linear classifiers partition the data space X into K convex regions. If the true decision regions are not convex, performance suffers. This limited expressive power has also a silver lining: The number m of parameters of linear predictors is relatively small, m = K(d + 1), so that a linear predictor requires fewer training samples to train, relative to a more expressive predictor, in order to achieve a certain value for the training risk: Linear predictors have low sample complexity. As a result, they generalize better than more expressive ones. When we studied linear classifiers, we also saw the advantages of score-based classifiers: The K scores output by a K-class logistic-regression classifier can be interpreted as a probability distribution of the predicted label ŷ = h(x) given the input x, and this distribution can be used to compute some measure of the confidence of the answer. Decision trees combine the advantages of a score-based predictor (for both classifiers and regressors!) with the expressiveness deriving from a very flexible partition of X. Specifically, they recursively split X with hyperplanes, and they assign a single value (real number or label, depending on whether the problem is one of regression or classification) to each subset of the partition. This recursive splitting leads to effectively arbitrary expressiveness, as long as the partition is fine enough. Since the splitting is recursive, the resulting partition of the data space X can be represented by a strictly binary tree. As will be seen in more detail below, the root of the tree represents all of X, and contains the parameters of the hyper-plane used for the first split. The two children of the root represent the two half-spaces that that hyper-plane divides X into. Each of the two children in turn contains an additional hyper-plane that splits the child’s half-space, and the structure continues recursively. The tree can then be used for prediction: Given a data point x, check which side of the root partition it belongs to, and send it to the corresponding child. This check is repeated at every internal tree node encountered in this way, until a leaf is reached. The leaf corresponds to a (possibly small) convex region of X, and a single value is associated to that region. That value is the prediction y = h(x) returned by the tree. We will see in the next section how the hyper-planes are constructed, and how the prediction value at each leaf is computed. Staying at a high level for now, decision trees determine each of the hyper-planes greedily, by choosing the hyper-plane (out of a set of choices that is typically restricted, as we will see) that