Stanford CS329H: ML from Human Preferences | Autumn 2024 | Model-based Preference Optimization

This lecture teaches the core ideas behind decision tree learning for supervised classification. A decision tree is a flowchart-like structure that predicts a target label (such as yes/no) by asking a sequence of questions about input attributes. Each internal node asks a question (a test) about one attribute, each branch corresponds to one possible outcome of that test, and each leaf node provides the final predicted class. By following the path from the root to a leaf, the model makes a prediction for any new example. The main goal of the learning algorithm is to grow a tree that separates the training data into increasingly pure groups, where each group mostly contains a single class.

The lecture focuses on how to construct such a tree from labeled data, how to choose which attribute to split on at each step, and when to stop splitting. The process starts at the root with all training examples and proceeds top-down. At every node, the algorithm evaluates each candidate attribute and chooses the one that produces the purest child groups. Two common measures of purity are introduced: entropy (from information theory) and the Gini index. The attribute that maximizes information gain (the drop in entropy) or equivalently reduces Gini impurity the most is selected for splitting.

You will also learn practical decisions every tree builder must make: when to stop growing the tree, how to handle empty branches after a split, how to prune a tree to avoid overfitting, how to deal with missing values, and how to handle continuous (numeric) attributes by discretizing them into ranges. Stopping rules include: all examples in a node share a class, no attributes remain, too few examples remain, or further splits provide negligible improvement. If a branch ends up with no training samples, you label it with the parent node’s most common class. Pruning comes in two flavors—pre-pruning (stop early) and post-pruning (trim after fully growing)—and it helps create a smaller, more generalizable model.

This lecture is for beginners who have basic familiarity with supervised learning terms like features (attributes), labels (classes), and training sets. No advanced math is required beyond understanding averages and logarithms, though the idea of log base 2 appears in the entropy formula. If you know how to count class frequencies in a group and compute proportions, you can follow the impurity calculations. The instructor keeps the concepts grounded with everyday analogies and small, concrete examples, like predicting whether someone will play tennis based on weather conditions such as outlook (sunny, overcast, rainy).

After completing this lecture, you will be able to: describe what a decision tree is; trace how it predicts a class label by following attribute-based questions; compute entropy, information gain, and the Gini index for a node; choose the best attribute to split; apply reasonable stopping criteria; decide what to do with empty branches; explain and apply pre-pruning and post-pruning; handle missing values through simple or model-based imputation; and discretize continuous attributes into useful ranges. These skills transfer directly to practical machine learning projects, where decision trees often serve as strong, interpretable baselines and are central to powerful ensembles like random forests and gradient-boosted trees (even though the lecture focuses on single trees).

The lecture is structured in a clean progression. It begins with the conceptual picture of a decision tree—nodes as questions, branches as answers, and leaves as predictions. Then it presents the top-down training algorithm and the key question: how to pick the best split. Two impurity measures—entropy (with information gain) and the Gini index—are introduced along with their formulas and intuitive meaning. Next, the lecture addresses when to stop splitting, how to handle empty child sets, and how to label leaves. Finally, it covers practical refinements: pruning, strategies for missing values, and discretizing continuous attributes into categories like cold/warm/hot so the same splitting logic applies. By the end, you have a complete, end-to-end understanding of how to build and refine a decision tree classifier from real data.

Overall Architecture/Structure

1. Problem framing

• Input: A labeled training set S of examples, each described by attributes (features) and a class label. Attributes may be categorical (e.g., Outlook ∈ {sunny, overcast, rainy}) or continuous (e.g., Temperature in °C). The goal is to learn a mapping from attributes to a class label.
• Output: A decision tree T whose internal nodes test attributes, branches represent attribute values (or intervals), and leaves output predicted classes.
• Data flow: Start with S at the root. At each node, evaluate candidate attributes to split S into subsets S_v. Choose the attribute that yields the purest children. Recurse on each child with its subset. Stop when a stopping rule applies. For any leaf, predict the majority class of the subset assigned to it.

1. Node anatomy

• Internal node: Stores which attribute is tested and how many branches (one per discrete value or interval). Also stores counts of class labels for impurity and prediction backup.
• Branch: Labeled by one attribute value (for categorical) or by a condition like Temperature ≤ 20°C (for continuous after discretization or thresholding).
• Leaf: Stores the predicted class (usually the majority class) and optionally the class distribution for confidence estimation.

1. Training loop (top-down induction)

• Start at the root with all examples.
• Compute impurity at the node (entropy or Gini) from class proportions.
• For each candidate attribute A:
  • Partition examples by A’s values (categorical) or by chosen thresholds/bins (continuous).
  • Compute the weighted average impurity of child nodes.
  • Compute the improvement (e.g., information gain or Gini reduction) relative to the parent.
• Select the attribute that yields the greatest improvement (equivalently, the smallest weighted child impurity).
• Create child nodes for each attribute value (or interval) and assign the corresponding subsets.
• Recurse on each child until a stop rule triggers.
• If a child subset is empty, assign the leaf the parent’s majority class.

Impurity Measures and Split Selection

1. Entropy (uncertainty of a node)

• Definition: Entropy(S) = −∑_i p_i log2(p_i) where p_i is the fraction of examples in S of class i. For binary classes, entropy ranges from 0 (all one class) to 1 (50/50 split). For more classes, the maximum is log2(K) when all K classes are equally likely.
• Interpretation: Higher entropy = more mixed classes (more uncertainty). Lower entropy = purer node (more certainty).
• Edge cases: If p_i = 0 for any class, define 0·log2(0) = 0 (limit case) to avoid numerical issues.

1. Information Gain (how much entropy is reduced by a split)

• IG(S, A) = Entropy(S) − ∑_v (|S_v|/|S|) · Entropy(S_v), where v ranges over A’s values.
• Weighted averaging reflects the size of each child node. Larger, impure children penalize the gain more than small, impure children.
• Selection: Choose A that maximizes IG(S, A). This prioritizes splits that create children with low entropy, especially if those children hold many samples.

1. Gini Index (alternative impurity)

• Gini(S) = 1 − ∑_i p_i^2. It is 0 if the node is pure and increases as classes mix.
• Gini reduction for attribute A: ΔGini(S, A) = Gini(S) − ∑_v (|S_v|/|S|) · Gini(S_v).
• Equivalent selection rules: either maximize ΔGini(S, A) or minimize the weighted child Gini ∑_v (|S_v|/|S|) · Gini(S_v). Be consistent in code.

1. Multiway vs. binary splits

• Categorical attributes naturally create a branch per category (sunny/overcast/rainy). Continuous attributes are often split by thresholds (e.g., Temperature ≤ 20 vs. > 20) or discretized into bins (e.g., cold/warm/hot). Both approaches reduce the problem to discrete branch choices for the tree.

Stopping Rules and Leaf Labeling

1. Stopping criteria

• Purity: If all examples at a node belong to the same class, stop and make a leaf.
• No attributes: If there are no remaining attributes to split on, stop.
• Minimum samples: If the number of examples is below a threshold (e.g., fewer than 5), stop to avoid noisy splits.
• Minimum improvement: If the best candidate split yields information gain or Gini reduction below a small threshold, stop.

1. Leaf labeling

• Majority class rule: The leaf’s predicted label is the class with the highest count at that node. This minimizes classification error on the node’s training samples.
• Confidence/backup: Optionally store the class distribution to estimate confidence (e.g., 80% yes, 20% no) or to break ties.

Handling Empty Children and Missing Values

1. Empty child sets after a split

• Sometimes no training example exhibits a certain attribute value (e.g., no day was foggy). Create the leaf and label it with the parent’s majority class. This gives a reasonable default for unseen values during prediction.

1. Missing attribute values in the data

• Drop rows: Simple but discards data; use only if missingness is rare and random.
• Mode imputation: Replace missing categorical values with the most common value for that attribute. For numeric, replace with a typical value or bin.
• Model-based imputation: Use a predictive model (e.g., another tree or simple classifier) to infer missing values based on other attributes.
• Rationale: Better imputation preserves dataset size and often improves predictive power compared to dropping rows.

Continuous Attributes and Discretization

1. Why discretize?

• Trees branch on discrete outcomes. Continuous values can be converted to a small number of intervals (bins) like cold/warm/hot so the tree can branch cleanly.

1. How to create intervals

• Simple thresholds: Use domain knowledge or scan candidate thresholds (e.g., midpoints between sorted unique values) to choose splits that maximize gain or Gini reduction.
• Fixed bins: Choose ranges like < 20°C, 20–30°C, > 30°C. Treat the resulting bins as categories for the tree.

1. Trade-offs

• Too many bins create many branches and can overfit. Too few bins may hide useful distinctions. Use validation to pick a sensible binning strategy.

Pruning to Improve Generalization

1. Why prune?

• Fully grown trees can memorize noise. Pruning simplifies the tree, usually improving performance on new data and making the model faster and easier to interpret.

1. Pre-pruning (early stopping)

• Set limits: max depth, min samples per split/leaf, or a minimum gain threshold. If a candidate split fails these rules, stop splitting.
• Pros: Faster training, simpler trees, less overfitting from the start.
• Cons: Risk of stopping too early, missing helpful structure that would appear deeper in the tree.

1. Post-pruning (cut after growing)

• Process: Grow a full tree, then evaluate subtrees on validation data. Replace a subtree with a leaf if it does not improve validation performance.
• Pros: Often finds a better trade-off between fit and simplicity than pre-pruning alone.
• Cons: Requires extra data or cross-validation; more computation.

Implementation Guide (step-by-step) Step 1: Prepare the data

• Ensure each example has attribute values and a class label. Decide which attributes are categorical vs. continuous. Decide how to handle missing values (drop, mode imputation, or model-based imputation). For continuous features, decide whether to discretize into bins or consider simple thresholds.

Step 2: Choose impurity measure

• Pick entropy (with information gain) or Gini. Entropy has a clear information-theory meaning; Gini is often faster. Be consistent across the entire training process.

Step 3: Build the tree (recursive function)

• Base cases: If node is pure, or no attributes remain, or node size < min_samples, or best gain < min_gain, return a leaf labeled by majority class.
• Otherwise: For each candidate attribute:
  • Partition S into subsets S_v according to the attribute’s values (or intervals).
  • Compute weighted child impurity and the improvement (gain or reduction).
• Pick the attribute with the best improvement.
• Create child nodes for each value/interval. For any empty child, create a leaf labeled with the parent’s majority class.
• Recurse on each non-empty child with its subset and the remaining attributes.

Step 4: (Optional) Post-pruning

• Hold out a validation set. For each internal node, consider replacing its subtree with a leaf labeled by its majority class, and measure validation accuracy. If accuracy does not drop (or improves), keep the prune. Repeat bottom-up.

Tools/Libraries (conceptual)

• Although no specific code was shown, most ML libraries (e.g., scikit-learn, R’s rpart) implement decision trees with Gini or entropy, and support pre-pruning via parameters like max_depth, min_samples_split, min_samples_leaf, and min_impurity_decrease. Missing value handling and discretization are usually performed before fitting.

Tips and Warnings

• Be consistent with definitions: If you define “gain” as reduction in impurity, higher is better; if you minimize weighted child impurity directly, lower is better—these are equivalent criteria when implemented correctly, but do not mix them.
• Avoid too many categories in a single split: Very high-cardinality categorical features can create many branches and overfit. Consider grouping rare categories or using thresholds/encoding.
• Watch for tiny leaves: Enforce min_samples_per_leaf to avoid rules learned from very few examples.
• Validate stopping and pruning thresholds: Use a validation set or cross-validation to choose min_gain, max_depth, and other hyperparameters.
• Handle missingness thoughtfully: If missingness is systematic (not random), simple imputation may bias the model; consider model-based imputation or explicit “missing” categories when appropriate.
• Continuous variables: Try several candidate thresholds and pick the one that yields the best impurity reduction, or discretize into a small number of meaningful bins.
• Interpretability: Keep trees reasonably shallow to maintain readability; pruning helps. Document leaf distributions for transparency.

Code/Execution Flow (concept in pseudocode)

• fit(S, Attributes):
  1. If stop_condition(S, Attributes): return Leaf(label=majority(S))
  2. For A in Attributes:
     • Partition S into {S_v}
     • score[A] = impurity(S) − ∑_v (|S_v|/|S|)*impurity(S_v)
  3. A* = argmax_A score[A]
  4. Node = DecisionNode(test=A*)
  5. For each value v of A*:
     • If S_v is empty: Node.child[v] = Leaf(label=majority(S))
     • Else: Node.child[v] = fit(S_v, Attributes − {A*})
  6. Return Node
• predict(x, Node): Traverse from root; at each DecisionNode, read attribute A* from x, follow the branch matching x[A*], continue until a Leaf; return Leaf.label.

By following these steps and principles—impurity-based selection, sound stopping rules, careful handling of empties and missing values, and prudent pruning—you can build decision trees that are both accurate and easy to explain.

This lecture built a complete, practical understanding of decision trees for classification. You learned that a decision tree is a series of attribute-based questions leading from a root to a leaf, where the leaf provides the predicted class. Training proceeds top-down: at each node, choose the attribute that best improves purity, measured by entropy (with information gain) or the Gini index. You saw stopping rules that prevent endless growth and reduce overfitting, rules for labeling leaves and handling empty child sets, and how pruning—either before or after full growth—simplifies trees for better generalization. Real-world issues like missing values and continuous attributes were addressed through imputation and discretization into ranges such as cold/warm/hot.

To practice, start with a small dataset like the play-tennis example. Compute node entropies and Gini values by hand, evaluate information gain for a couple of attributes, and choose the best split. Implement a simple recursive trainer that stops on purity or minimum samples, and add a majority-class label at leaves. Then experiment with pre-pruning settings like max depth and min gain, and try a post-pruning step using a validation set. Test discrete binning on a numeric feature and compare results.

Next steps include exploring decision trees for regression, where splits aim to reduce variance instead of class impurity, and learning about ensembles like random forests and gradient-boosted trees that combine many trees for stronger performance. You might also compare entropy and Gini on your data to see if one works better, and investigate more advanced handling of missing data. Studying feature engineering and category encoding for high-cardinality attributes will further improve tree performance.

The core message is simple and powerful: pick the question that most reduces confusion, stop before noise takes over, and trim branches that don’t help. Decision trees excel because they are both effective and interpretable—turning complex datasets into clear, conditional rules. With careful split selection, sensible stopping, and pruning, you can build trees that perform well on new data and are easy to explain, audit, and trust.