Stanford CS329H: Machine Learning from Human Preferences | Autumn 2024 | Preference Models

This lecture teaches the complete, practical method for learning decision trees—models that transform feature values into clear, discrete decisions like Yes/No. You will learn how a decision tree grows by asking the best question at each step and how to measure what “best” means using information theory. The lecture explains entropy as a measure of uncertainty in your labels and shows how information gain tells you which attribute separates the data most cleanly. A classic, concrete example—deciding whether to play golf—grounds the math with real counts and exact numerical values.

The session begins with what decision trees are, when to use them, and why they are particularly good for discrete target functions, conjunctions (ANDs) and disjunctions (ORs) of attributes, and even noisy or partially missing data. You then see a full end-to-end decision-making path: Outlook at the root; if Sunny, check Humidity; if Rainy, check Wind; and Overcast always leads to Yes. From there, the lecture steps back and asks the crucial question: how did we learn that tree from examples? The answer is a greedy recursive algorithm that stops when a node becomes all positive or all negative, and otherwise picks the attribute with the largest information gain to split the data.

Next, the lecture dives into the core math. Entropy is introduced as a formal way to measure impurity: zero if all labels in a set are the same, and maximal (for two classes) when the set is half positive and half negative. Using this, information gain is defined as the parent node’s entropy minus the weighted average entropy of the children after a split. You compute this for each attribute and choose the one with the largest gain. The golf dataset’s 14-day history is used to show exact entropy values and the resulting gains: Outlook’s 0.246 beats Temperature’s 0.029, Humidity’s 0.151, and Wind’s 0.048, so Outlook is placed at the root.

With the splitting rule established, the lecture explains that the process repeats inside each branch until the tree is complete. It emphasizes that the method is greedy—it optimizes the immediate step rather than planning the whole tree in advance. While this makes the algorithm fast and effective, it can also lead to overfitting, where the tree gets too specific to the training data. To control this, two main strategies are offered: early stopping (stopping when data is pure or splits no longer help) and post-pruning (first grow, then remove branches that hurt validation performance). The lecture favors the idea that post-pruning often works well because it uses a separate validation set to judge usefulness.

The lecture then addresses practical complications you will meet in real data. Many attributes are continuous (like a temperature in degrees), but decision trees need clear branching rules. Two solutions are given: discretize values into bins (e.g., cool/mild/hot) or automatically learn a cut-point by sorting values, finding places where labels change, and testing midpoints as thresholds. The best threshold is the one that gives the highest information gain. Another real-world factor is measurement cost. If some attributes are expensive to gather, you can still rely on information gain to score splits, but then bias your choice toward cheaper attributes when performance is similar.

By the end, you will be able to: compute entropy and information gain; pick the best attribute to split; grow a decision tree recursively; recognize and reduce overfitting with pruning; and handle continuous attributes and attribute costs in a principled way. This makes you capable of building practical, interpretable classifiers that work well on a wide range of tasks. The overall structure starts with an intuitive introduction and example, moves into the math of entropy and information gain, continues through the recursive algorithm, and closes with advanced considerations like overfitting, pruning, continuous splits, and cost-sensitive decisions. The lecture is self-contained and equips you to implement the method and understand the trade-offs involved.