Stanford CME295 Transformers & LLMs | Autumn 2025 | Lecture 1 - Transformer

This lecture teaches the core ideas behind decision trees, one of the most widely used and practical machine learning models. A decision tree predicts a target by asking a series of simple questions about the input’s features—like “Is age ≤ 30?” or “Is credit rating fair?”—and following branches down the tree until it reaches a leaf that contains the final prediction. The model is non-parametric, which means it does not assume a fixed form (like a line or a curve) in advance. Instead, the tree’s structure—what feature to split on and where—is discovered from the data itself. Decision trees work for both classification (choosing a category) and regression (predicting a number), and they form the backbone of powerful ensemble models like random forests and gradient boosting.

The lecture is aimed at beginners to intermediate learners who are familiar with basic supervised learning ideas: features, labels, classification vs. regression. If you know what it means to train a model on labeled data and evaluate it on a test set, you’re ready. No advanced math is required beyond understanding proportions, logs (for entropy), and averages. The lecture goes step-by-step from definitions and intuition to calculating impurity, information gain, and choosing splits, and ends with practical tips like pruning and handling missing values.

After finishing this lecture, you will be able to: explain what a decision tree is and how it makes predictions, compute Gini impurity and entropy for any node, calculate information gain for a proposed split, and describe common stopping criteria. You will also be able to articulate the main advantages (interpretability, mixed data types, low prep) and disadvantages (overfitting, instability, category bias). You’ll understand how pruning and hyperparameter constraints help prevent overfitting. Lastly, you’ll grasp how trees fit into ensembles, especially how random forests reduce overfitting by averaging many trees.

The lecture is structured in a practical flow. It starts with the high-level definition of a decision tree and a relatable example predicting whether someone will buy online based on age, student status, and credit rating. It introduces key terms—root node, internal node, leaf—and explains how the tree grows by recursively splitting the data to create increasingly homogeneous nodes. It then formalizes impurity with two metrics, Gini impurity and entropy, and shows how to compute each with a concrete numerical example (0.6/0.4 split). With impurity in hand, it defines information gain as the reduction in impurity after a split and walks through a worked calculation. Next, it covers when to stop splitting: pure leaves, maximum depth, minimum samples, and minimal information gain. The lecture closes with a balanced discussion of pros and cons, how to avoid overfitting with pruning and hyperparameters, handling missing data, model instability, and a brief comparison to random forests as an ensemble of many trees trained on different subsets of data and features.

Overall, the lesson combines intuition (trees ask simple questions to sort data), precise math (measures of impurity and gains), and practical guidance (stopping rules, pruning, cross-validation) so that you can not only understand the model but also apply it responsibly. You will leave with a complete mental model of how decision trees are constructed, evaluated, constrained, and used in real projects, as well as how they serve as the foundation for more advanced ensemble methods.

Overall Architecture/Structure

• Data flow: A decision tree takes an input vector of features (e.g., age, student status, credit rating) and predicts a target (class label or numeric value). Training begins with all training samples at the root node. The algorithm evaluates candidate splits on each feature to find the split that most reduces impurity (i.e., maximizes information gain). The dataset is partitioned into child nodes based on that split. The process repeats recursively for each child until stopping criteria are met. Leaves store the final prediction—either a class (or class probabilities) for classification or an average value for regression.

• Roles of components:

  • Root node: Entry point containing all training samples.
  • Internal nodes: Decision points defined by a rule (e.g., feature ≤ threshold for numeric, feature ∈ subset for categorical).
  • Edges/branches: Outcomes of the rule (true/false or category branches) that route samples to children.
  • Leaf nodes: Terminal nodes that output predictions (most frequent class for classification, mean for regression).

• Prediction path: To predict for a new sample, start at the root and apply the node’s rule. If true, go left; if false, go right (for binary trees). Repeat until reaching a leaf, then return the leaf’s stored prediction (and class probabilities if needed by using the class frequencies at that leaf).

Core Computations

1. Node impurity (classification):

   • Gini impurity: G = 1 − Σ_i p_i^2, where p_i is the proportion of class i in the node. G ∈ [0, 1 − 1/C], where C is the number of classes. Pure nodes have G = 0.
   • Entropy: H = −Σ_i p_i log2 p_i. H ∈ [0, log2 C]. Pure nodes have H = 0; maximum H occurs when classes are equally likely.

2. Information gain (classification):

   • Gain(Split) = Imp(parent) − [ (N_L/N) Imp(left) + (N_R/N) Imp(right) ] for binary splits, where Imp is Gini or entropy, N is parent sample count, and N_L/N_R are child sample counts. For multiway splits (e.g., categorical with many values), sum over all children.

3. Impurity (regression):

   • Commonly variance or mean squared error (MSE). For node with values y_1..y_n and mean μ, variance = (1/n) Σ (y − μ)^2. Split quality is measured by reduction in variance (or MSE): Var(parent) − [ (N_L/N) Var(left) + (N_R/N) Var(right) ]. Leaves predict μ of their samples.

4. Candidate splits:

   • Numeric features: Try thresholds between sorted unique values (midpoints). For feature x with sorted values v1 ≤ v2 ≤ …, evaluate splits x ≤ t for t between adjacent unique values.
   • Categorical features: Depending on implementation, either try multiway splits (one branch per category) or binary splits using subsets (e.g., x ∈ S vs. x ∉ S). Some libraries binarize categories or require one-hot encoding; others natively handle categories.

Worked Numerical Examples from the Lecture

• Gini example: Node with 60% class A and 40% class B: Gini = 1 − (0.6^2 + 0.4^2) = 1 − (0.36 + 0.16) = 1 − 0.52 = 0.48.
• Entropy example: Same node: H = − [0.6 log2 0.6 + 0.4 log2 0.4] ≈ − (0.6 × −0.737 + 0.4 × −1.322) ≈ 0.971.
• Information gain example: Parent impurity = 0.5. Children impurities: left 0.3 with 60% of samples; right 0.4 with 40% of samples. Weighted child impurity = 0.6 × 0.3 + 0.4 × 0.4 = 0.18 + 0.16 = 0.34. Gain = 0.5 − 0.34 = 0.16. The lecture rounded to 0.2 for illustration; the key idea is the parent minus weighted children impurities.

Greedy, Recursive Tree-Building Algorithm

• High-level steps:

  1. Start with all training samples at the root.
  2. If the node meets a stopping criterion (pure, too small, too deep, or no gain), make it a leaf and set its prediction (majority class or mean value).
  3. Otherwise, for each feature, consider candidate splits and compute information gain (classification) or variance reduction (regression).
  4. Choose the split with the highest improvement.
  5. Partition data into children according to the chosen split and recurse on each child.

• Why greedy? The algorithm chooses the best split at each node locally rather than searching all possible trees globally (which is computationally infeasible). This local optimization typically works well in practice and is the standard approach.

Stopping Criteria (Pre-Pruning)

• Purity stop: If all samples at a node belong to the same class, it is pure—stop splitting.
• Max depth: Limit the depth of the tree (e.g., depth ≤ 5). Deeper trees can capture more patterns but risk overfitting.
• Min samples per split/leaf: Require a minimum number of samples to attempt a split or to be at a leaf (e.g., min_samples_split = 10, min_samples_leaf = 5). This prevents brittle rules based on tiny sample counts.
• Min impurity decrease (or min information gain): Only split if the impurity reduction is above a threshold. This avoids pointless splits that do not help generalization.

Post-Pruning

• Concept: Grow a large tree (possibly to pure leaves) and then cut back branches that do not help validation performance. This is often guided by a validation set or cross-validation.
• Benefit: Can simplify the model after fully exploring the structure, improving generalization and interpretability. Although the lecture emphasized pruning in general, practical implementations include cost-complexity pruning that balances accuracy vs. tree size.

Advantages of Decision Trees

• Interpretability: Paths are human-readable rules. Stakeholders can understand and audit decisions.
• Minimal feature engineering: No need for scaling/normalization; trees can naturally handle mixed feature types.
• Flexibility: Applicable to classification and regression; can model nonlinear boundaries and interactions.
• Speed at prediction time: Traversing a tree is fast (logarithmic in the number of leaves), suitable for real-time decisions.

Disadvantages and Caveats

• Overfitting: Deep trees can memorize noise. Constraining growth and pruning are essential.
• Instability (high variance): Small changes in data can alter splits, leading to very different trees.
• Bias toward high-cardinality categorical features: Features with many categories can create many partitions that look purer by chance. Mitigations include regularization, careful encoding, and using validation-based criteria.

Handling Missing Data

• Implementation-dependent options:
  • Imputation: Fill missing values with mean/median (numeric) or mode/special category (categorical) before training.
  • Surrogate splits: Learn backup splits that mimic the primary split; if the primary feature is missing for a sample, use the surrogate to route it.
  • Missing-as-category: Treat “missing” as its own category for categorical features.
• Importance: Real-world datasets often contain missing entries; robust handling improves performance and usability.

Practical Tips for Choosing Gini vs. Entropy

• Gini: Slightly faster, often similar results; tends to favor the most frequent class separation.
• Entropy: Information-theoretic; can sometimes produce slightly more balanced trees. In practice, accuracy differences are usually minor.

Using Decision Trees in Practice

• Training pipeline:

  1. Clean data: Handle missing values (as per implementation), unify data types, check for obvious errors.
  2. Split into train/validation/test (or use cross-validation).
  3. Train a baseline tree with default hyperparameters.
  4. Evaluate and then tune max_depth, min_samples_split, min_samples_leaf, and min_impurity_decrease.
  5. Consider post-pruning if available.
  6. Assess stability and consider ensembles (random forests) if variance is high.

• Evaluation metrics:

  • Classification: Accuracy, precision, recall, F1, ROC-AUC; analyze confusion matrix.
  • Regression: Mean squared error (MSE), mean absolute error (MAE), R².

• Feature importance:

  • Many implementations compute feature importance as the total impurity reduction contributed by splits on that feature, averaged over the tree. While informative, it can be biased toward high-cardinality features; use with caution and validate with permutation importance when possible.

Hands-On Implementation Guide (Conceptual)

• Step 1: Prepare data.

  • Ensure features and target are correctly typed (numeric/categorical). Decide how to handle missing values (impute or use implementation that supports missing). For categorical variables, check if your library needs one-hot encoding or can split on categories directly.

• Step 2: Choose split criterion.

  • Classification: Gini or entropy (information gain).
  • Regression: Variance reduction (often MSE).

• Step 3: Fit the tree.

  • At the root, compute impurity. For each feature, enumerate candidate splits (thresholds for numeric; subsets or categories for categorical) and compute information gain. Select the highest-gain split.
  • Partition the data into left/right child nodes (binary trees) or multiple children (multiway, if supported). Recurse on each child, applying stopping criteria.

• Step 4: Set stopping rules.

  • Use sensible defaults (e.g., max_depth 5–10 for small/medium datasets; min_samples_leaf 5–20). Monitor validation performance as depth increases; stop when adding depth does not improve validation score.

• Step 5: Prune (optional / if supported).

  • If your library supports post-pruning (e.g., cost-complexity pruning), search over pruning strengths with cross-validation and choose the best generalization score.

• Step 6: Evaluate and interpret.

  • Report metrics on a held-out test set. Visualize the tree to verify sanity (are the first splits plausible?). Extract and discuss the top decision paths for stakeholder clarity.

• Step 7: Consider ensembles.

  • If the single tree overfits or is unstable, use random forests (bagging with feature subsampling) to reduce variance and improve accuracy.

Debugging and Common Pitfalls

• Poor generalization (overfitting): Tree too deep or leaves too small. Fix by lowering max_depth, increasing min_samples_leaf, or pruning. Validate changes with cross-validation.
• Underfitting: Tree too shallow or constraints too strict. Slightly increase max_depth or decrease min_samples_leaf; verify improvements.
• High-cardinality categorical features dominate: Try encoding strategies, regularization, or switch to an implementation with balanced split handling. Validate with permutation importance.
• Missing data mishandled: Ensure consistent imputation strategy or leverage surrogate splits. Inspect distributions before and after imputation to avoid bias.
• Instability: Use ensembles or set random seeds for reproducibility. Report variability across folds.

Tools/Libraries (General Guidance)

• Many practitioners use standard libraries that implement efficient, battle-tested tree learners. For Python, scikit-learn’s DecisionTreeClassifier and DecisionTreeRegressor are common: they support Gini/entropy, max_depth, min_samples_leaf, and more. For R, rpart and partykit are popular. While the lecture did not depend on a specific tool, these libraries embody the same principles discussed: greedy splitting to maximize impurity reduction, with user-controlled stopping criteria and pruning in some cases.

Data and Model Interpretability

• Rule extraction: Each path to a leaf is a human-readable rule (e.g., if age ≤ 30 and student = yes then Buy). Listing top rules can help explain model behavior.
• Leaf probabilities: For classification, a leaf can store class counts, allowing predictions with probabilities (counts normalized by leaf size). These probabilities can be calibrated further if needed.

From Single Trees to Ensembles

• Random forests: Train many trees on bootstrap samples (bagging) and consider random subsets of features at each split. Average their predictions (majority vote for classification, mean for regression). This reduces variance and usually improves generalization.
• Gradient boosting: Sequentially build trees that correct the errors of previous ones. Though beyond the lecture’s main scope, it relies on the same tree building blocks.

Ethical and Practical Considerations

• Interpretability aids accountability: Because trees are readable, they’re suitable where explanations are required.
• Beware data leakage: Ensure that features used in splits are available at prediction time and do not leak future information.
• Fairness: Splits can inadvertently encode biases present in data. Monitor disparate impact across groups and consider constraints or preprocessing to mitigate harms.

In summary, decision trees operate by greedy, recursive partitioning of data to create pure, interpretable decision rules. Their key computations—impurity (Gini/entropy) and information gain—provide a principled way to choose splits. With sensible stopping criteria and pruning, trees become robust, understandable models and serve as the cornerstone for powerful ensembles like random forests.

Decision trees learn to predict by asking a sequence of simple, human-readable questions about input features and following the answers down to a leaf. They are non-parametric models whose structure is discovered from data, making them flexible for both classification and regression. The heart of tree building is choosing splits that make nodes purer: we measure impurity with Gini or entropy (for classification) and variance or MSE (for regression), and we select the split that maximizes information gain. This process repeats recursively until stopping rules say “enough,” producing a model that is easy to trace and explain.

Despite their strengths—interpretability, minimal data prep, and broad applicability—single decision trees can overfit, become unstable, and sometimes prefer features with many categories. Practical usage, therefore, depends on wise regularization: set maximum depth, require minimum samples per leaf, apply minimum impurity decrease, and use pruning when available. Cross-validation should guide these choices so the model generalizes well beyond the training data. Handling missing values is another key step, whether by imputing or using implementations that support missing-aware splits.

In the real world, trees are not just end models but also fundamental building blocks of ensembles. Random forests, for example, train many slightly different trees and average their predictions to reduce variance and improve accuracy. Understanding single trees makes it much easier to grasp why and how these ensembles work. After mastering impurity, information gain, and stopping/pruning strategies, you can confidently deploy trees as clear baselines, interpret their decisions for stakeholders, and scale up to ensembles when you need extra performance.

The core message to remember is simple: a decision tree breaks a hard problem into a set of small, easy choices. If you make each choice reduce uncertainty (maximize information gain) and stop before the model memorizes noise (prune and constrain), you’ll build robust, understandable predictors. From there, ensembles like random forests offer a path to greater stability and accuracy while keeping the intuitive building blocks you now understand.