Decision Trees and Ensemble Learning

A decision tree classifies an example by asking a sequence of simple questions about its features, one at a time, following a path down the tree until it reaches a leaf that assigns a label. The classic procedure for growing such a tree from data, described in Tan, Steinbach, and Kumar's widely used textbook Introduction to Data Mining as Hunt's algorithm, is recursive and greedy: at any node t holding a set of training records Dt, if every record in Dt already belongs to the same class, the algorithm stops and turns t into a leaf labeled with that class; otherwise, since Dt "contains records that belong to more than one class," the algorithm selects a single attribute test condition, such as whether income is above some threshold, to split Dt into smaller child subsets, one per outcome of the test, and then applies the exact same procedure recursively to each child. Because this process is greedy, it commits to whichever split looks best at the current node without ever reconsidering that choice in light of splits made later in the tree, and because it is recursive, an entire tree, potentially with many layers of nested questions, emerges from repeatedly applying one simple splitting rule at each level. The central design question this leaves open is how, exactly, the algorithm should decide which attribute test condition, among all the ones available at a given node, is best.

Tan, Steinbach, and Kumar's text answers this by defining node impurity, a measure of how mixed together the classes are within a node's records, and choosing whichever candidate split reduces impurity the most. Three impurity measures are commonly used. Entropy is defined as Entropy(t) = −Σᵢ p(i|t) log₂ p(i|t), summing over classes i, where p(i|t) is the fraction of node t's records belonging to class i; it is zero when a node is perfectly pure and largest when the classes are evenly mixed. The Gini index is defined as Gini(t) = 1 − Σᵢ [p(i|t)]², and classification error is defined as 1 − maxᵢ [p(i|t)], the error rate if the node simply predicted its own majority class; all three share the same basic shape, minimized at purity and maximized at an even class split, but weight intermediate mixtures somewhat differently. Given an impurity measure I, the quality of a candidate split into k child nodes v₁, ..., vₖ is scored by the gain criterion, Δ = I(parent) − Σⱼ [N(vⱼ)/N] I(vⱼ), which is the parent node's impurity minus the weighted average impurity of the resulting children, weighted by how many of the parent's records end up in each child; the algorithm greedily selects, at every node, whichever available attribute test maximizes this gain, meaning it produces the largest possible drop in weighted impurity from parent to children.

A single decision tree grown all the way down tends to have low bias, since it can carve out an arbitrarily complex decision boundary, but high variance, since a small change in the training data, even removing or adding just a few records, can change which attribute looks best at the very first split and cascade into a completely different tree. Leo Breiman's 1996 paper "Bagging Predictors" proposes a direct way to reduce this variance without touching bias: bootstrap aggregating, or bagging. Bagging generates many alternate training sets, each drawn by sampling from the original training set at random "with replacement," so that some original records appear multiple times in a given bootstrap sample and others do not appear at all, then fits an identical learning procedure, such as a full decision tree, separately on each bootstrap sample. To make a final prediction, Breiman's paper specifies that the predictions of these many trees are aggregated by different rules depending on the type of output: for a numerical target, an obvious procedure is to replace a single tree's prediction by the average of the predictions across all the bootstrap-trained trees, while for a class-label target, where each tree predicts a discrete label, one method of aggregating the individual predictions "is by voting," assigning the class that receives the most votes across all the trees.

Leo Breiman's 2001 paper "Random Forests" extends bagging with one further source of randomness. A random forest is formally defined, in Breiman's own words, as "a classifier consisting of a collection of tree-structured classifiers {h(x,Θk), k=1, ...} where the {Θk} are independent identically distributed random vectors and each tree casts a unit vote for the most popular class at input x"; concretely, each tree is grown on its own bootstrap sample exactly as in bagging, but at every single split within every tree, only a small random subset of the available features is even considered as a candidate for that split, rather than all of them, which forces different trees to rely on different features and decorrelates the resulting ensemble more than bootstrap resampling alone would. Breiman shows mathematically, via a strong-law-of-large-numbers argument over the sequence of random vectors Θ₁, Θ₂, ..., that the generalization error of this voting ensemble converges as more trees are added rather than continuing to change unpredictably, a result he uses to explain why "random forests do not overfit as more trees are added, but produce a limiting value of the generalization error." Because each individual tree in the forest is left unpruned and deep, and therefore has low bias on its own bootstrap sample, while the combination of bootstrap resampling and random feature selection sharply reduces the variance that a single such tree would otherwise have, random forests are able to achieve both properties, low bias and low variance, simultaneously in a way a lone decision tree of comparable depth cannot.

Where bagging and random forests train many independent models in parallel and only combine them at the very end, boosting builds its ensemble sequentially, with each new model specifically targeting the mistakes of the ones trained before it. Yoav Freund and Robert Schapire's 1997 paper "A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting" introduced AdaBoost, the foundational algorithm in this family. AdaBoost maintains a distribution of weights over the training examples, initially uniform, and on each round trains a new weak hypothesis, a classifier required only to do slightly better than random guessing, using the current weights; after each round, the paper describes an update rule under which the weight distribution "reduces the probability assigned to those examples on which the hypothesis makes a good prediction and increases the probability of the examples on which the prediction is poor," so that every subsequent weak learner is forced to pay more attention to the examples the ensemble so far still gets wrong. After a fixed number of rounds, the final combined classifier is not a simple average of the weak hypotheses but a weighted vote, in which more accurate weak hypotheses are given proportionally larger votes and less accurate ones are given smaller ones; the paper describes this final hypothesis as one that "combines the outputs of the T weak hypotheses using a weighted majority vote," with weights derived directly from each hypothesis's error rate on the weighted training distribution it saw.

AdaBoost's weighted majority vote and a random forest's per-tree vote both combine model outputs by a fixed, predetermined rule, whether uniform or error-weighted, decided in advance of seeing which specific examples any given base model happens to be good or bad at. Stacked generalization, introduced by David Wolpert in 1992 and analyzed further in later work, takes a different approach by learning the combination rule itself. As one paper analyzing the technique summarizes it, stacking first collects the predictions of several already-trained base models into a new dataset, one row per original training example, where "this data set represents every model's prediction of that instance's class, along with its true classification"; in a second stage, "the new data is treated as the data for another learning problem," and a separate meta-model is trained on it, learning, in effect, how much to trust each base model, and under which circumstances, rather than weighting or voting them by a rule fixed in advance. This makes stacking strictly more flexible than either a simple majority vote, of the kind Breiman's random forests use when each tree "casts a unit vote for the most popular class," or AdaBoost's fixed error-derived weights, at the cost of needing enough additional data and computation to train that second-level model without simply overfitting it to the base models' behavior on the training set.