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.

Overall Architecture/Structure

1. Problem Setup and Goals

• Input: A set of training examples, each with attribute values and a class label (e.g., Yes/No). Attributes may be discrete (e.g., Sunny/Overcast/Rainy) or continuous (e.g., temperature in degrees). The target function is discrete, meaning we classify into categories.
• Output: A decision tree where internal nodes test a single attribute, branches correspond to attribute values (or thresholds), and leaves hold final class labels.
• Objective: Build a tree that generalizes well—accurate on new data—and is as simple as possible while still capturing the signal in the training set.

1. Data Flow Through the Algorithm

• Start with the full training set at the root. Compute the entropy of the labels to measure uncertainty.
• For each candidate attribute, pretend to split the data by that attribute’s values (or threshold) and compute the weighted average child entropy. Subtract this from the parent entropy to get information gain.
• Choose the attribute with the highest information gain. Create child nodes for each attribute value (or for ≤ threshold and > threshold), passing the corresponding subset of examples to each child.
• Recurse: repeat the scoring-and-splitting process for each child until a stopping condition is met (e.g., a node’s examples are all the same label).
• Output the final tree. For new examples, route from root to leaf by following attribute tests, then return the leaf’s label.

1. Role of Each Component

• Entropy: Quantifies how mixed the labels are at a node. It is 0 if completely pure (all one class) and up to 1 for a 50/50 split in a two-class problem.
• Information Gain: Scores how much a candidate split reduces entropy. The higher the gain, the better the split at making child nodes purer.
• Greedy Recursion: Efficiently builds the tree by making the best local decision at each step without global lookahead.
• Stopping Criteria: Prevent endless growth and help reduce overfitting by terminating when purity or utility conditions are met.
• Pruning: Post-process that simplifies the tree to improve generalization based on validation performance.

Mathematical Foundations

1. Entropy (Binary Case) Let S be a set of examples with p+ the fraction of positive labels and p− the fraction of negative labels (p+ + p− = 1). Entropy(S) = −p+ log2(p+) − p− log2(p−).

• Edge cases: • If p+ = 1 and p− = 0 (all positive), Entropy(S) = 0 (complete certainty). • If p+ = 0.5 and p− = 0.5, Entropy(S) = 1 (maximum uncertainty for binary labels).
• Interpretation: Entropy measures the average number of bits needed to encode the label under the data’s own distribution; lower is better (more predictable).

1. Information Gain Given an attribute A with discrete values v ∈ Values(A), and subsets Sv = {x ∈ S | A(x) = v}, define: Gain(S, A) = Entropy(S) − Σv (|Sv|/|S|) Entropy(Sv).

• Weighted average child entropy: sums each child’s entropy weighted by its relative size. High gain means the attribute meaningfully reduces uncertainty.
• Goal: Choose the attribute A with maximal Gain(S, A).

Worked Example: Golf Dataset

• Dataset: 14 examples with labels Yes (9) and No (5). Entropy(S) = −(9/14) log2(9/14) − (5/14) log2(5/14) ≈ 0.94.
• Attribute Outlook with values {Sunny, Overcast, Rainy}: • Sunny subset: 5 examples (2 Yes, 3 No) → Entropy(SSunny) = −(2/5) log2(2/5) − (3/5) log2(3/5) ≈ 0.971. • Overcast subset: 4 examples (4 Yes, 0 No) → Entropy(SOvercast) = 0. • Rainy subset: 5 examples (3 Yes, 2 No) → Entropy(SRainy) ≈ 0.971. • Weighted child entropy = (5/14)*0.971 + (4/14)*0 + (5/14)*0.971 ≈ 0.694. • Gain(S, Outlook) = 0.94 − 0.694 = 0.246.
• Other attributes (given): Gain(S, Temperature) = 0.029; Gain(S, Humidity) = 0.151; Gain(S, Wind) = 0.048. Outlook has the maximum gain, so it becomes the root.
• Recursion: • Overcast branch is pure (all Yes) → leaf Yes. • Sunny branch: choose best among Temperature, Humidity, Wind. The learned tree uses Humidity: High → No; Normal → Yes (pure or nearly pure splits). • Rainy branch: choose best attribute, learned tree uses Wind: Strong → No; Weak → Yes.

Algorithm (Step-by-Step)

1. Base Cases at Node N with subset S:

• If S is empty: create a leaf with the majority class from the parent or a default class.
• If all labels in S are the same (entropy = 0): create a leaf labeled with that class.
• If no attributes remain (or all remaining attributes have zero useful gain): create a leaf with the majority class in S.

1. Recursive Case:

• For each candidate attribute A still available: • Compute Gain(S, A).
• Let A* = argmaxA Gain(S, A). Create a decision node at N testing A*.
• For each value v of A*, create child Nv with subset Sv = {x ∈ S | A*(x) = v}. Recurse on each child with the reduced attribute set (if attributes are single-use; if multi-use is allowed for continuous thresholds, handle accordingly).

1. Prediction Phase:

• For a new example x, start at root and evaluate the test. Follow the branch that matches x’s attribute value (or threshold region). Repeat until reaching a leaf. Output the leaf’s label.

Handling Continuous Attributes

1. Discretization (Preprocessing):

• Define bins like: Temperature < 70 (Cool), 70–80 (Mild), > 80 (Hot). Treat the resulting categories like discrete values during tree building. Pros: simplicity and stability. Cons: may lose fine-grained information.

1. Learn Thresholds at Split Time:

• Procedure at a node for attribute A (continuous): • Sort examples in S by their A values. • Scan adjacent examples; whenever labels differ, consider the midpoint between their A values as a candidate threshold t. • For each candidate t, split S into S≤t and S>t, compute Gain(S, A ≤ t), and pick the t with the highest gain.
• This yields clear binary branches and often better accuracy than coarse bins.

Overfitting and Pruning

1. Overfitting Risks:

• Deep trees can model noise or rare quirks in the training set, harming test performance. This happens especially when leaves contain very few examples or when many attributes exist.

1. Early Stopping:

• Stop splitting when: • Node is pure (entropy = 0), or • The best information gain is below a small threshold, or • The number of examples in the node is below a minimum.
• Pros: Simple and fast. Cons: May stop too soon and miss helpful splits or still overfit in other parts.

1. Post-Pruning (Preferred in Lecture Context):

• Grow the full tree (or nearly full) first. Use a validation set to test accuracy.
• Bottom-up, consider replacing a subtree with a leaf labeled by the majority class of its node’s examples.
• If validation accuracy improves or stays the same, keep the prune. Repeat until no prune helps.
• Benefit: Removes branches that only fit training noise, improving generalization.

Attributes with Costs

• Some features are expensive to measure (e.g., lab tests, specialized sensors) or slow to acquire.
• Strategy: • Compute information gain as usual. • When multiple attributes deliver similar gain, prefer the cheaper one (cost-sensitive splitting).
• This balances performance and real-world constraints, especially in production systems.

Noisy Data and Missing Values

• Decision trees are tolerant to noise because splits are chosen by aggregate separation power, not perfect consistency.
• Missing attribute values can be handled in simple ways, such as: • Use available attributes to route as far as possible; if a split attribute is missing, fallback to the majority branch or assign by the most common value at that node. • Alternatively, impute missing values before training (mean/mode or domain-specific methods).
• These approaches keep learning feasible even when data quality is imperfect.

Implementation Details (Conceptual/Pseudocode)

1. Entropy Function (Binary Labels):

• Input: counts of positives (pos) and negatives (neg). Let n = pos + neg. If pos==0 or neg==0, return 0.
• p+ = pos/n; p− = neg/n; entropy = −p+ * log2(p+) − p− * log2(p−).
• Return entropy.

1. Information Gain for Discrete Attribute A:

• For each value v in Values(A): • Build Sv = {examples with A = v}. • Compute entropy(Sv).
• WeightedEntropy = Σv (|Sv|/|S|) * entropy(Sv).
• Gain = entropy(S) − WeightedEntropy.
• Return Gain.

1. Best Split Selection:

• For each attribute in candidate set: • If discrete: compute Gain(S, A). • If continuous: generate candidate thresholds and compute Gain(S, A ≤ t) for each; keep the best Gain and threshold.
• Choose the attribute (and threshold, if applicable) with maximal Gain.

1. BuildTree(S, Attributes):

• If all labels in S are identical: return Leaf with that label.
• If Attributes is empty or no split gives positive gain: return Leaf with majority label in S.
• A* = argmaxA Gain(S, A). Create Node testing A*.
• For each child branch b of A* (each value or threshold side): • Sb = subset of S consistent with b. • Child = BuildTree(Sb, Attributes \ {A*} or Attributes if continuous with multiple thresholds allowed at deeper nodes). • Attach Child to Node via branch b.
• Return Node.

1. Prediction(x, Tree):

• Start at root. While at internal node: • Evaluate node’s test on x. • Follow matching branch. If attribute value missing, follow majority branch or use default.
• Return label at leaf.

Tips and Warnings

• Data Balance: Highly imbalanced classes can skew majority leaves; consider using class-weighted evaluation or minimum leaf sizes.
• Tie-Breaking: If two attributes have the same gain, prefer the one with more interpretable values or lower measurement cost.
• Minimum Samples per Leaf: Enforce a minimum to avoid very small, unstable leaves.
• Validation Strategy: Keep a separate validation set for pruning; do not tune on test data.
• Feature Engineering: Thoughtful discretization for continuous attributes can simplify trees and improve interpretability.
• Numerical Stability: When computing entropy, handle p log p with care for p=0 (treat 0 log 0 as 0 by limit).
• Performance: Precompute counts for faster gain calculations; sorting once per node per continuous attribute is usually the main cost.

Practical Workflow Summary

• Step 1: Collect labeled data with clear attributes (discrete or continuous).
• Step 2: If needed, clean data, handle missing values, and decide whether to discretize continuous attributes or choose thresholds during splitting.
• Step 3: At the root, compute entropy and information gain for all attributes; pick the best one.
• Step 4: Split data accordingly; recurse on each child subset.
• Step 5: Stop when nodes are pure or no useful split remains.
• Step 6: Optionally apply post-pruning using a validation set to simplify the tree and improve generalization.
• Step 7: Evaluate on a separate test set and interpret root-to-leaf rules for insight.

End-to-End Result

• The learned decision tree offers a set of easy-to-understand rules that map attributes to outcomes. Because splits are chosen by maximizing information gain, early decisions typically remove a lot of uncertainty. Post-pruning refines the tree to balance simplicity and accuracy. The final model is both interpretable and effective for discrete classification problems like the golf example.

This lecture delivered a complete, practical path to learning decision trees: from intuition and structure to the precise math of entropy and information gain. You saw how trees map attribute values to decisions by asking the best question first and then continuing in each branch until the answer becomes clear. The core scoring method, information gain, comes from information theory and is grounded in entropy, which measures how mixed or pure the labels are. Using the golf example with 14 days of data, the lecture walked through exact numbers, showing why Outlook belongs at the root and how Humidity and Wind drive splits in the Sunny and Rainy branches.

Because the algorithm is greedy, it runs fast and produces interpretable rules, but it can overfit if allowed to grow unchecked. The lecture introduced two defences: early stopping (ending growth when nodes are pure or gains are negligible) and post-pruning (growing first, then simplifying with a validation set). Post-pruning often yields better generalization by trimming branches that only match training noise. Real-world complications—continuous attributes, missing values, and different attribute costs—were addressed with practical strategies like thresholding, simple missing-value routing, and cost-sensitive biasing when gains are similar.

After this lecture, you can compute entropy and information gain, choose the best attribute at each step, build a decision tree recursively, and apply pruning to improve robustness. You also know how to handle continuous features and factor in measurement costs. For practice, try computing gains by hand on small datasets and then implement the algorithm to solidify your understanding. The core message to remember is simple: choose the split that most reduces uncertainty, keep the tree as simple as possible, and validate by pruning to ensure your model performs well on new data.