Stanford CS329H: Machine Learning from Human Preferences | Autumn 2024 | Introduction

This lecture teaches the fundamentals of decision trees, a widely used and very interpretable machine learning algorithm. A decision tree makes predictions by asking a sequence of feature-based questions at its internal nodes and using the answers to follow paths down to leaves, where class labels (for classification) or values (for regression) are assigned. The lecture walks through how trees are structured, how to classify an instance by traversing the tree, and—most importantly—how to learn a decision tree automatically from data rather than hand-designing it. The key mathematical ideas come from information theory: entropy is used to measure uncertainty in class labels, and information gain measures how much a feature split reduces that uncertainty. The lecture anchors these ideas in a concrete example: deciding whether to wait for a restaurant table based on features like whether there are alternates, whether it's Friday or Saturday, whether we're hungry, and especially the number of patrons present (none, some, or full).

The talk is aimed at learners who have basic familiarity with supervised learning—knowing that we have input features and a target label—and a willingness to learn a little bit of math notation. No deep prerequisites are required; the lecture defines entropy and information gain from scratch and shows exactly how to compute them. Even if you’ve never built a model before, the step-by-step approach is clear: choose the best feature using information gain, split the data, and recurse until you should stop. The lecture briefly mentions that trees can also do regression, but the focus is on classification and the entropy-based learning process.

By the end, you will be able to explain what a decision tree is, read and interpret a decision path, compute entropy for a dataset, compute information gain for potential splits, and decide the best feature to split on at each step. You’ll also understand how to handle continuous attributes—either by discretizing into bins or by choosing an optimal threshold—and how to control tree complexity to avoid overfitting through pruning. You’ll be able to follow a complete example end-to-end, including a worked calculation showing why splitting on 'patrons' is the best first move in the restaurant dataset.

The lecture is structured as follows. It starts with the intuition and structure of decision trees, using the restaurant example to show how a manually crafted tree works in practice. It then moves to learning trees automatically using entropy and information gain, defining these concepts clearly and giving numeric examples. Next, it shows how to choose splits for continuous features using discretization or thresholding—often by sorting values and testing midpoints. Finally, it explains overfitting and two main strategies to prevent it: pre-pruning (stopping early) and post-pruning (growing fully, then cutting back), including reduced error pruning on a validation set. The session closes by summarizing why decision trees remain useful: they are simple, powerful, and highly interpretable.

1. Overall Architecture/Structure

• Model structure: A decision tree is a rooted tree where each internal node tests a feature (attribute) and each outgoing branch corresponds to an outcome of that test. Leaves store predictions: either a class label or a class probability distribution for classification, and a numeric value for regression (though this lecture focuses on classification).
• Data flow during prediction: To classify an instance, start at the root. Evaluate the node’s condition on the instance (e.g., patrons = full?). Follow the matching branch to the next node. Repeat until reaching a leaf. Output the leaf’s label. This deterministic path is the model’s explanation for its prediction.
• Data flow during training: Given a labeled dataset S, choose the feature A that best separates classes according to information gain. Split S into subsets S_v by A’s values v (for continuous features, the values correspond to whether the feature is below or above a chosen threshold). Recurse on each subset, choosing the next best feature within that subset. Stop when nodes are pure, no features remain, or a stopping rule triggers. Optionally, prune the tree to improve generalization.

1. Entropy and Information Gain

• Entropy (uncertainty): For a dataset S with class proportions p1, p2, ..., pC, entropy(S) = -Σ_i p_i log2 p_i. Intuition: entropy is 0 when there is no uncertainty (all examples share the same label). For binary classification, entropy is 1 when p1 = p2 = 0.5 (maximum uncertainty). Entropy smoothly increases as labels become more mixed.
• Computing entropy: Suppose S has 12 examples: 6 positive (wait) and 6 negative (don’t wait). Then p_pos = 0.5 and p_neg = 0.5. Entropy(S) = - (0.5 log2 0.5 + 0.5 log2 0.5) = - (-0.5 - 0.5) = 1.
• Information gain (IG): For feature A with possible outcomes v in Values(A), let S_v be the subset where A = v. Then IG(S, A) = Entropy(S) − Σ_v (|S_v|/|S|) Entropy(S_v). Interpretation: IG is how much the split reduces uncertainty, on average weighted by subset sizes. Choose the feature with the highest IG at each node.

1. Worked Example: Restaurant Dataset

• Dataset summary: 12 examples with features: alternates, bar, Friday/Saturday, hungry, patrons (none/some/full), price, rain, reservation, type. Target: wait (yes/no). Overall entropy is 1 as labels are evenly split.
• Split on 'patrons': Values are none, some, full. Compute entropies per value: • patrons = none: 2 examples, both negative → p_neg = 1, entropy = 0. • patrons = some: 4 examples, all positive → p_pos = 1, entropy = 0. • patrons = full: 6 examples, with 2 positive and 4 negative → p_pos = 2/6 = 1/3, p_neg = 4/6 = 2/3. Entropy = - (1/3 log2 (1/3) + 2/3 log2 (2/3)) ≈ 0.918.
• Weighted post-split entropy: (2/12)*0 + (4/12)*0 + (6/12)*0.918 = 0.5 * 0.918 = 0.459.
• Information gain: IG(S, patrons) = 1 − 0.459 = 0.541. This is the largest among tested features, so patrons is chosen as the root.
• Recursion after first split: For patrons = none and patrons = some, entropy is 0 → make leaves (don’t wait, wait). For patrons = full, continue splitting using the same IG calculation on remaining features within that subset.

1. Building a Tree: Step-by-Step Algorithm (ID3-style by concept, without naming)

• Input: Training set S of examples with features X and class labels Y.
• Step A: Compute entropy(S) using class proportions. If entropy(S) = 0, return a leaf with that class.
• Step B: For each candidate feature A, split the dataset and compute the weighted average entropy after the split. Compute IG(S, A) = Entropy(S) − weighted entropy.
• Step C: Choose the feature A* with the highest information gain. Create an internal node that tests A*.
• Step D: For each outcome v of A*, form subset S_v. If S_v is empty, create a leaf with the parent’s majority label. Else, recursively call the algorithm on S_v using the remaining features.
• Step E: Apply stopping rules: stop when entropy is 0 (pure), when no features remain (assign majority class), or when other limits (max depth, minimum samples per leaf) are reached. Optionally, after the full tree is built, apply pruning.

1. Handling Continuous Attributes

• Discretization approach: Define intervals (bins) over the numeric range—e.g., <100, 100–200, >200—and treat the attribute as categorical with those interval labels. Then compute IG as with any categorical feature. Pros: simple, yields multi-way splits; cons: may be coarse and not adaptive.
• Threshold (binary split) approach: Convert the numeric feature to a binary question at the node: is value ≤ t (left) or > t (right)? To select t, sort training examples by the feature and consider candidate thresholds at midpoints between adjacent unique values. For each candidate t, split the data and compute IG; choose t that maximizes IG. Pros: data-driven and fine-grained; cons: requires scanning multiple thresholds per node.
• Practical tip: When labels do not change across adjacent values, midpoints between those values need not be tested; evaluate only where label identity changes to reduce computation.

1. Overfitting and Pruning

• Overfitting definition: A tree that keeps splitting to fit idiosyncrasies in the training set can achieve very low training error but poor test performance. Symptoms include deep trees with leaves that cover very few examples and rules that mirror noise rather than meaningful patterns.
• Pre-pruning (early stopping): Impose constraints during training to limit complexity. Common constraints include a maximum depth, a minimum number of examples required to split a node further, or a minimum information gain threshold to justify a split. If a split fails these checks, make the node a leaf with the majority class.
• Post-pruning (simplification after growth): Grow the full tree (or a large tree), then consider removing subtrees and replacing them with leaves. Use a validation set to test if pruning a subtree reduces accuracy; if not, keep it pruned. Reduced error pruning is a straightforward method: prune any subtree whose removal does not decrease validation accuracy.
• Trade-off: Pre-pruning may stop too early and miss useful splits; post-pruning may initially overfit but can find better simplifications guided by validation performance. In practice, even simple pruning heuristics often yield much better generalization than unpruned trees.

1. Interpreting and Using Trees

• Interpretability: Every root-to-leaf path is a human-readable rule, composed of feature tests. For auditing, you can list these paths and inspect where certain decisions come from.
• Determinism and speed: Classification involves a small number of feature checks along a path, making inference fast and predictable.
• Dealing with ties in IG: If multiple features share nearly equal IG, pick any consistently (e.g., by a fixed feature order). Subsequent recursion often resolves remaining uncertainty.

1. Implementation Guide (no code required)

• Preparation: Ensure features are in a suitable format. Categorical features should have well-defined values; continuous features must be either binned (discretized) or prepared for threshold search.
• Core functions: • Entropy(S): Count labels in S, convert counts to probabilities p_i, compute -Σ p_i log2 p_i. • Split(S, A): For categorical A, group examples by each value v. For continuous A with threshold t, split into ≤t and >t. Return subsets and their sizes. • InformationGain(S, A): Compute entropy(S), compute weighted entropy after splitting on A, return the difference. • BestSplit(S): For each candidate A (and for continuous A, each candidate t), compute IG and return the best A (and t, if applicable). • BuildTree(S, features, depth): If stop condition met, return leaf with majority label (and optionally class distribution). Else choose best split, create node, and recurse on child subsets.
• Stopping conditions to implement: • Node is pure (entropy = 0). • No remaining features. • Max depth reached. • Node size below a minimum threshold. • Information gain below a small threshold (split not worth it).
• Post-processing: • If using post-pruning, hold out a validation set. Consider replacing subtrees with leaves if validation accuracy doesn’t drop (reduced error pruning). Iterate until no further beneficial pruning is possible.

1. Tips and Warnings

• Data fragmentation: Each split reduces the number of examples per child. Be cautious of deep trees where many leaves have very few examples; this is a red flag for overfitting.
• Feature engineering: Categorical values with many rare categories can lead to brittle splits. Consider grouping rare categories if appropriate.
• Continuous thresholds: Always consider candidate thresholds derived from sorted data; testing arbitrary thresholds (e.g., every 10 units) is less effective and can miss better cut points.
• Class imbalance: If one class dominates, entropy will be low even without good separation. Be mindful when interpreting IG and consider whether features meaningfully reduce uncertainty for minority classes.
• Validation strategy: Keep a dedicated validation set or use cross-validation to evaluate pruning decisions; relying solely on training metrics will not reveal overfitting.
• Reproducibility: Fix the order of features for tie-breaking and document stopping/pruning rules so others can replicate your tree.

1. Putting It All Together on the Restaurant Data

• Start: S has 12 examples, 6 positive and 6 negative, so entropy(S) = 1.
• Evaluate features: Compute IG for alternates, bar, Friday/Saturday, hungry, patrons, price, rain, reservation, type. The lecture shows 'patrons' has the highest IG ≈ 0.541.
• First split: Create a root node testing patrons with branches none, some, full. • none: 2 examples, both negative → make a 'don’t wait' leaf. • some: 4 examples, all positive → make a 'wait' leaf. • full: 6 examples with 2 positive, 4 negative → continue splitting.
• Recursion: Within 'full', choose the next feature by recomputing IG with only these 6 examples and the remaining features. Continue until subsets are pure or a stopping rule applies.
• Result: A readable, rule-based model that explains 'wait' vs 'don’t wait' decisions using intuitive restaurant cues. The dominant early split on 'patrons' captures the key intuition that crowd level strongly predicts waiting.

In summary, decision trees combine a clear structure (feature tests leading to labeled leaves) with a principled learning method based on entropy and information gain. They handle both categorical and continuous features (via discretization or thresholding), and they require safeguards—stopping rules and pruning—to avoid overfitting. The restaurant example shows exactly how to compute entropies, pick the best split, and grow a tree that is both effective and interpretable.

This lecture presented decision trees as a simple yet powerful model for classification, grounded in clear, step-by-step logic. The core ideas are that each internal node tests a feature, each branch represents a test outcome, and each leaf produces a prediction. We learned how to grow trees from data using entropy to measure uncertainty and information gain to pick the most helpful features to split on. A detailed, numeric walk-through with the restaurant dataset demonstrated that 'patrons' provides the greatest reduction in uncertainty at the root, leading to immediate pure leaves for 'none' and 'some' and a recursive split for 'full'.

Continuous attributes were addressed with two mainstream strategies: discretization into bins and threshold-based binary splits. Thresholds can be selected efficiently by sorting the values and evaluating midpoints between adjacent unique values, choosing the one that maximizes information gain. The lecture stressed the danger of overfitting—trees that are too complex and overly tailored to training noise—and introduced pruning as the antidote. Pre-pruning stops early using rules like maximum depth or minimum samples per leaf, while post-pruning grows a fuller tree and then removes branches that don’t help on a validation set, with reduced error pruning as a straightforward method.

Practically, decision trees are easy to interpret, debug, and deploy. Their decisions are transparent: each path reveals exactly which conditions led to a prediction. After this lecture, you should be able to compute entropy and information gain, select splits, handle continuous features, and implement stopping and pruning strategies. To deepen your understanding, practice by building a small tree on a toy dataset, compute all entropies and gains by hand once, and then implement a simple recursive learner that includes stopping rules and a basic pruning pass.

The key message to remember is balance: use information-theoretic splitting to carve out structure, but apply sensible stopping and pruning to avoid overfitting. With these principles, decision trees deliver both clarity and solid predictive performance on many real-world problems.