Decision trees, bagging and random forests

A decision tree classifies an example by walking it from the top of the tree to the bottom, answering one question at each step. The professor's everyday example (slide 3): "Work to do?" If yes, stay in. If no, look at the outlook, and so on.

The vocabulary from slide 4, using the PlayTennis example that runs through the deck:

• An attribute (feature) is a question like Outlook. Its values are the possible answers: Sunny, Overcast, Rain. Each internal node tests one attribute and has one branch per value.
• A leaf assigns a class (PlayTennis = Yes or No). "The nodes for decisions are always leaf nodes, because we never make another decision based on this one" (05:58).
• To classify a new day, start at the root, follow the branch that matches its value, and repeat until you reach a leaf.

Trees are rules. Every root-to-leaf path is an AND of conditions, so a tree converts directly into a rule list (slide 22), e.g. "If Outlook = Sunny AND Humidity = High then No". The professor stresses that this is the main selling point: "if, let's say, for your applications the explanation is very important, then the first algorithm you should think about is the decision tree" (16:30). His example is a hospital's COVID triage flowchart: patients and doctors can see exactly why a decision was made. Géron calls this a white-box model, in contrast to black boxes like random forests and neural networks.

When trees fit well (slide 9, from Mitchell Ch. 3): examples are described by attribute–value pairs, the target is discrete (a class), the training data may be noisy or have missing values, and the target concept may need a disjunction (an OR of conditions).

The second deck (6b slide 2) lists the trade-offs, which drive everything in the second half of the lecture:

Many trees fit the same training data perfectly (6b slide 3 shows a 3-leaf tree and a 6-leaf tree that both have zero training error). We'd like the smallest tree that fits, but finding it is computationally intractable: Géron notes that finding the optimal tree is NP-complete. So every practical algorithm builds the tree top-down and greedily:

1. Pick the "best" attribute for the current node, the one whose split gives the purest children (the next two sections define "purest").
2. Split. Make one child per value of and send each training example down the branch matching its value.
3. Recurse on each child with only the examples that reached it.
4. Stop (make a leaf) when all examples at the node have the same label, when no attributes are left (or all remaining examples have identical features), or when no examples reached the node. A leaf predicts the majority label of its examples (for an empty node, the parent's majority).

This template is ID3 (Quinlan, 1986) when "best" means largest information gain. "Most decision tree learning algorithms follow this template, but with different choices of heuristics" (6b slide 5). The professor says ID3 and C4.5 are the ones to remember (41:31). The differences:

A node is pure if all its examples have the same class and impure if the classes are mixed. An impurity measure turns that into a number that is 0 for a pure node and largest for a 50/50 mix. Let be the fraction of the node's examples in class (the slides write for node ), with classes.

What entropy means (slides 12–13). Entropy is the average number of bits needed to encode the class of a randomly drawn example using the best possible code. A message with probability gets a code of bits; averaging over classes gives . A pure node needs 0 bits (you already know the answer). A 50/50 node needs 1 bit. "If the distribution is flat, the entropy is maximized" (20:01): the flatter the class distribution, the more uncertain and the higher the entropy, for any number of classes.

Why not use misclassification error to grow trees? Slide 8 says it's "less sensitive to changes in the class probabilities" and recommends it only for pruning. Here's a concrete case. A node has [4+, 4−]. Split A gives [3+, 1−] and [1+, 3−]. Split B gives [2+, 4−] and [2+, 0−]. Split B creates a pure node, so it's clearly more useful. But:

Error can't tell them apart because it only counts majority mistakes. Entropy and Gini are curved (strictly concave), so they reward pushing a child toward purity.

To score a candidate split, compare the parent's impurity with the size-weighted average impurity of the children. The drop is the information gain (when the impurity is entropy):

ID3 picks the feature with the largest gain. Since is the same for every candidate, that's the same as picking the split with the smallest weighted child impurity, which is how Géron writes CART's cost function (Eq. 6-2): minimize . 6b slide 6 writes the same formula as .

The professor's reading of the gain: "if you maximize information gain, then from the same node the decision we make will be much easier" (22:11). The children should be closer to "one class has all the probability", where entropy is 0.

The classic 14-day dataset (slide 16, originally Mitchell Table 3.2). The task: predict PlayTennis from four attributes.

Step 1: the root. The whole set is [9+, 5−] with . Score all four attributes:

For example,

Outlook wins under both criteria. (Slide 17 prints 0.151 for Humidity because it uses rounded entropies; the exact value is 0.152.) Overcast is already pure [4+, 0−], so it becomes a Yes leaf.

Step 2: the Sunny branch, = {D1, D2, D8, D9, D11} = [2+, 3−], . Outlook is used up, so score the other three on just these five days:

Step 3: the Rain branch (not shown on the slides), {D4, D5, D6, D10, D14} = [3+, 2−]: Wind gives Weak [3+, 0−] and Strong [0+, 2−], gain 0.971 − 0 = 0.971, since both children are pure. (Temperature and Humidity each give only 0.020.) The leaves are now all pure, so ID3 stops.

As rules (slide 22): R1 Sunny ∧ High → No; R2 Sunny ∧ Normal → Yes; R3 Overcast → Yes; R4 Rain ∧ Strong → No; R5 Rain ∧ Weak → Yes.

Continuous features are handled by thresholding: turn temperature into the yes/no question "temperature > ?" (slide 29). Which ? Sort the examples by the feature and only consider thresholds halfway between neighbors whose labels differ (Mitchell shows the best threshold is always at such a boundary). Then score each candidate by information gain like any other attribute.

The picture for two continuous features. Each split "" is a line perpendicular to one axis, so a tree carves the plane into axis-aligned rectangles, one per leaf. This is what CART does (always binary, one feature and one threshold per node), and the threshold search above happens at every node for every feature.

Missing values (slide 30). If an example lacks the value of attribute at a node that tests , the options are: fill in the most common value of among the examples at that node; or the most common value among examples with the same label; or, as in C4.5, split the example into fractions sent down every branch in proportion to how common each value is (e.g. 0.6 of it down High, 0.4 down Normal), and classify new examples the same way. The professor's summary: "You need to make an estimation… it's not accurate, but it's probably better than nothing" (40:28).

Occam's razor (slide 23): "If two theories explain the facts equally well, the simpler one is preferred." The argument for it: there are far fewer short hypotheses than long ones, so a short tree that fits the data is unlikely to do so by coincidence, while a long one easily can. The professor ties this to week 5: among the many separating lines, the SVM picks the one with smallest , a "smaller" model, and that's the idea behind regularization in general. "When you have some models that can work equally well, then you should pick the model with minimal size" (34:19). (Slide 23 also notes the counterargument: there are many ways to define "small", so "simple" isn't uniquely defined.)

Overfitting is "one of the biggest problems with decision trees" (slide 24). A tree can keep splitting until every leaf is pure, fitting the training set perfectly including its noise. 6b slide 4 phrases the cure as regularization: minimize training error subject to "size of tree ≤ C". Solving that exactly is intractable, so in practice we use the heuristics below.

Two ways to keep a tree small (slides 25–26):

• Pre-pruning (stop early): don't split a node when the split isn't statistically significant or the node is too small. The professor's example: a node with 100 positives and 1 negative is good enough as a leaf (35:56). In scikit-learn this is max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes.
• Post-pruning (grow, then cut back): grow the full tree, then replace subtrees by leaves when that doesn't hurt. Subtree replacement (slide 27) swaps an entire subtree for a single leaf predicting the majority class of the examples that reached it. Reduced-error pruning (Mitchell) prunes a node whenever doing so does not lower accuracy on a separate validation set.

Picking the best tree (slide 25): measure accuracy on a separate validation set (or by cross-validation, as in week 2) for different sizes and keep the best; or minimize size(tree) + misclassifications(tree), which charges for size like a regularization term (this is Mitchell's minimum description length idea).

The professor skips the review slides at the start of deck 6b and goes straight to this point: "Remember, decision trees have high variance" (43:44). High variance means a small change in the training data gives a very different learned model. Slides 8–9 change a single label in a 16-row commuting table (Metro → Drive) and the learned tree changes completely: a different root attribute and a different shape.

Why so unstable? Each split is a hard, greedy choice. If two attributes have nearly equal gain, a tiny change can swap which one wins, and everything below that node is then grown on different subsets of data. Errors at the top cascade down.

Bias and variance, done carefully. At 52:04 the professor switches to Wikipedia's dartboard figure. Imagine retraining the model on many different training sets drawn from the same source, and look at its prediction for one test point each time:

• Bias is how far the average prediction is from the truth: a systematic error that more data of the same kind doesn't fix. Simple models (a depth-1 "stump", a line) have high bias.
• Variance is how much the predictions spread from one training set to another. Flexible models (fully grown trees) have high variance.

6b slide 17 puts the two extremes side by side: a fully grown tree is low-bias and high-variance; a decision stump (one split) is high-bias and low-variance. The next sections exploit the first: a high-variance, low-bias model is exactly what averaging can fix.

An ensemble combines several trained models into one. If none of them is good enough on its own, maybe their combination is. Each is a weak learner: "a little bit better than the random classifier, for example 60 or 55 percent" (45:55). The goal is a strong learner from many weak ones. Ways to combine (slide 13):

Stacking (mentioned, not covered): feed the predictions as a feature vector into another model, e.g. a linear classifier, trained to combine them. Slide 15 shows two pictures of aggregation: averaging many separating lines gives a stable middle line, and combining several axis-aligned stumps gives a staircase boundary that no single stump could draw.

When does voting help? Only when the models are diverse and each is better than chance (slide 16). "If all classifiers have a large overlap with each other, then averaging doesn't make any difference" (49:58). The ideal case is independent errors, where majority voting is spectacularly effective:

So the question becomes how to get diverse models from one dataset. Two families (slide 16): bagging (this lecture; random forests are the main example) and boosting (AdaBoost; the professor says it's not covered in this course and suggests a tutorial if you're interested).

Slide 19 recalls the week-2 picture: fit a line to 2 points of a sine curve, repeat on many datasets, and each fit is wild, but their average is stable. Averaging reduces variance. The catch: "We only have one dataset in practice!"

Bootstrapping fakes many datasets from one. From , draw points uniformly at random with replacement. Some points are drawn twice or more and others not at all, so each bootstrap set is a slightly different version of . "Several keywords: uniformly, with replacement. These are the two keywords" (58:46).

Bagging (bootstrap aggregating, Breiman 1996): make bootstrap sets, train one model on each, and aggregate by majority vote (classification) or average (regression):

Why it works (slide 23). If are independent, each with variance , their average has variance . Bagging averages many low-bias, high-variance models: averaging keeps the bias about the same and divides the variance. Low bias plus low variance is a strong learner.

Slide 24 poses an exercise: when you draw points with replacement from , what's the probability that a particular point is never drawn? Each draw misses it with probability , and the draws are independent:

So each bootstrap set contains only about 63% of the distinct original points, and the other ~37% are out of bag (OOB) for that model. Note they're a different 37% for each model.

The OOB error (slides 26–27). A point that never saw is a free validation point for . For each training point , let be the vote of only the models for which was out of bag. Then

It estimates the ensemble's test error with no separate validation set and no extra training: the lecture calls it "basically doing cross-validation" (1:01:26). The difference is that cross-validation retrains on fixed folds, while OOB reuses the randomness bagging already created.

In scikit-learn: BaggingClassifier(..., oob_score=True) or RandomForestClassifier(oob_score=True), then read oob_score_ (an accuracy, i.e. ).

A random forest is bagging with decision trees, plus extra randomness to make the trees more different from each other (slide 30):

1. Bootstrap a dataset for each tree and grow it to full depth (no pruning: we want low bias and accept high variance).
2. Random feature subsets: at every split, consider only a random subset of of the features and pick the best split among those. A common default for classification is (scikit-learn's max_features="sqrt").
3. Aggregate: majority vote for classification, average for regression.

Slide 30 mentions one more option from Breiman's paper: randomly project the features (use random linear combinations) for each tree.

Here's that trade-off measured. Same data for all three: 1,000 training and 2,000 test points, 30 features (8 informative), 300 trees per ensemble, scikit-learn defaults ( for the forest):

• Extra-Trees (Géron): also pick the threshold at random instead of searching for the best one. Even more diversity, and faster to train.
• Feature importance (Géron): average how much each feature reduces impurity across all the forest's splits, weighted by how many samples reach each split. A cheap way to see which features matter.
• The professor's practical note: "the concept is simple, but while you're doing implementation… what's the depth" and similar details matter, so use the library (sklearn.ensemble.RandomForestClassifier) rather than writing your own (1:03:04).
• The price: a forest of 300 trees is no longer a readable set of rules. You trade the white box for accuracy.