Stanford CS230 | Autumn 2025 | Lecture 6: AI Project Strategy

This lecture teaches the fundamentals of decision trees and random forests, two of the most widely used supervised learning methods. Supervised learning means we train a model on labeled examples so that it can predict labels for new inputs. Decision trees build a set of simple if-then rules to split data into smaller and purer groups, eventually ending at leaves that make predictions. Random forests take this a step further by combining many trees trained on different slices of data and features to produce a stronger, more stable model.

The lecture starts with the big picture: most supervised learning algorithms aim to minimize a loss function, which measures how wrong predictions are. While algorithms differ in how they search for the best model, their core goal is the same. Decision trees are highlighted as being interpretable, easy to visualize, and usable for both classification (predicting categories) and regression (predicting numbers). Their structure is intuitive: nodes ask questions about feature values, edges route data according to answers, and leaves store final predictions.

You learn how to construct a decision tree by repeatedly choosing the best split. The best split is defined using impurity measures like Gini impurity or entropy, which quantify how mixed the classes are in a node. The split that maximizes information gain (the drop in impurity from parent to children) is chosen. This greedy process is applied recursively until stopping criteria signal that the model should stop growing to avoid overfitting. Stopping can be enforced by limits on tree depth or minimum samples required for splits and leaves.

Random forests are introduced as an ensemble method—an approach that combines multiple models to improve performance. Each tree in a random forest is trained on a bootstrapped sample (sampling with replacement) of the training data. Additionally, at each node, a random subset of features is considered for splitting. These two sources of randomness decorrelate trees so that their errors don’t line up. Final predictions are aggregated: majority vote for classification or averaging for regression.

The lecture explains why random forests are so effective: they reduce variance, which is the tendency of a model to change a lot in response to small changes in the training data. A single tree is a high-variance model and can be unstable. Averaging many high-variance models dramatically stabilizes predictions without increasing bias too much. As a result, random forests usually generalize better than a single tree and are more robust to overfitting.

You also learn pros and cons. Decision trees are interpretable, handle both numeric and categorical features, and are easy to implement. But they can overfit, be biased toward features with many levels, and be sensitive to small data changes. Random forests are more accurate and robust, offer feature importance measures, but are less interpretable, more computationally expensive, and require careful hyperparameter tuning like selecting the number of trees.

The lecture covers practical questions: how to pick the number of trees (start with hundreds and grow until validation performance plateaus), other ensemble methods (gradient boosting, AdaBoost, bagging without feature subsampling, and stacking across different model types), and how to handle missing data (impute, add a missing-value branch, or skip the feature, depending on implementation). These details anchor the theory in everyday modeling choices.

By the end, you understand the mechanics and motivations behind decision trees and random forests. You can explain how impurity, information gain, and stopping rules guide tree growth; how bootstrapping and feature subsampling build diverse forests; and how averaging reduces variance. You also gain practical wisdom about interpretability trade-offs, hyperparameters, and data issues like missing values. The lecture equips you to confidently build, tune, and evaluate trees and forests for both classification and regression tasks.

Overall Architecture/Structure

• Problem framing: Decision trees and random forests are supervised learning methods for classification and regression. Training data consists of feature vectors X and labels y. The learning goal is to produce a function f(x) that predicts y with minimal error on new, unseen data.
• Decision tree structure: A binary decision tree consists of internal nodes (decision points), edges (routing according to a condition), and leaves (final predictions). At each internal node, a split rule tests a single feature against a threshold (for numeric features) or a subset of categories (for categorical features). Data reaching a node is partitioned into left and right child nodes according to the rule. This recursive partitioning continues until stopping criteria are met, at which point leaves store the prediction for any future sample routed there.
• Random forest structure: A random forest is an ensemble of many decision trees. Each tree is trained on a different bootstrapped sample (sampling with replacement) of the original training set, introducing diversity in training data. During training of each tree, at every node, only a random subset of features is considered for splitting; this further diversifies trees. At inference, the forest aggregates predictions across trees—majority vote for classification or mean for regression—to form the final output.

Data Flow

1. Input data: Start with a dataset containing rows (examples) and columns (features), plus labels. Preprocess as needed (e.g., encode categories numerically if required by your library; many tree implementations handle categorical splits directly or via encoding).
2. Training decision tree: Route all data to the root. Evaluate candidate splits (feature, threshold) by measuring impurity reduction (information gain). Choose the best split and partition data into left/right child nodes. Repeat recursively for each child until stopping rules apply. Assign predictions to leaves (majority class or average value).
3. Training random forest: For each tree, sample a bootstrap dataset from the training data (same size as the original but drawn with replacement). Train a decision tree on this bootstrap, but at each split consider a random subset of features (e.g., sqrt(M) features for classification, where M is total features). Repeat for T trees. Store all trained trees.
4. Inference: For a new input, push it down each tree to reach a leaf prediction. Aggregate across trees: majority vote (classification) or average (regression). Return the aggregated prediction.

Split Criteria and Impurity

• Impurity motivation: A useful split creates child nodes where labels are more homogeneous than in the parent. Homogeneity means the node contains mostly a single class. Impurity quantifies the lack of homogeneity.
• Gini impurity: Gini(node) = 1 − Σ_i p_i^2, where p_i is the proportion of class i in the node. Properties: 0 when a single class has probability 1; maximum occurs for balanced classes (e.g., two classes at 0.5 each give Gini = 0.5). Computationally efficient and commonly used in practice.
• Entropy: Entropy(node) = − Σ_i p_i log2 p_i. Properties: 0 for pure nodes; higher values for more uniform class mixes (two classes at 0.5 each give entropy = 1 bit). Has information-theoretic interpretation; often used with information gain.
• Information gain (IG): IG = Impurity(parent) − [ (N_L/N) * Impurity(left) + (N_R/N) * Impurity(right) ], where N is parent size, N_L and N_R are child sizes. The best split maximizes IG. For multiway splits (e.g., category branches), apply the same weighting across all children.

Algorithm for Building a Decision Tree (Greedy, Top-Down)

1. Initialization: Start with all training samples at the root.
2. Stopping check: If stopping conditions hold (max depth reached, samples fewer than min_samples_split, or node is already pure), make this node a leaf and assign prediction (majority class or average target).
3. Candidate splits: For each feature, enumerate possible thresholds. For numeric features, potential thresholds often come from midpoints between sorted unique values. For categorical features, consider binary partitions of categories (implementation-dependent; often restricted for efficiency).
4. Evaluate splits: For each candidate, compute child impurities and information gain. Choose the feature and threshold with the highest IG.
5. Split and recurse: Partition data accordingly and create left/right child nodes. Recursively apply steps 2–5 on each child.
6. Leaf assignment: For classification, store class proportions (for probabilities) and majority class (for hard prediction). For regression, store average target value.

Stopping Criteria (Regularization within Trees)

• Max depth (max_depth): Limit how many levels the tree can grow. Prevents overly complex, deep trees prone to overfitting.
• Minimum samples to split (min_samples_split): Do not split nodes with fewer than this number of samples. Forces splits to be statistically meaningful.
• Minimum samples per leaf (min_samples_leaf): Ensure each leaf holds at least this number of samples. Avoids tiny leaves that memorize noise.
• Pure node or no improvement: Stop if all samples are the same class or if no split reduces impurity.

Prediction Mechanics

• Routing: A test sample traverses the tree by evaluating split rules at each node until reaching a leaf.
• Classification output: Hard label via majority class. Probabilities via class distribution stored at the leaf.
• Regression output: Predicted value equals the mean of training targets in that leaf.

Random Forest Training Details

• Bootstrapping: For each tree, sample N examples with replacement from the original N. On average, about 63.2% of unique examples appear at least once in a bootstrap sample. Duplicates are allowed, which gives each bootstrap its own emphasis and omissions.
• Feature subsampling at splits: At each node, consider only m randomly chosen features (m < M). Typical defaults: m = sqrt(M) for classification. This prevents dominant features from being chosen by all trees, increasing diversity.
• Diversity and decorrelation: Two trees trained on the exact same data and features tend to look similar and make similar errors. Bootstrapping and feature subsampling force trees to explore different partitions, so their errors are less correlated. Lower error correlation makes averaging more effective at variance reduction.
• Aggregation: After training T trees, prediction for a new sample aggregates across trees. For classification, the predicted class is the mode of tree votes. For regression, the predicted value is the mean of tree outputs.

Why Random Forests Reduce Variance

• Single decision trees are high-variance estimators; small perturbations in data (e.g., adding/removing a few samples) can significantly change splits and structure. This instability leads to fluctuating test performance. Ensembles average across many such unstable learners, canceling out idiosyncratic errors while preserving common signal. The result is a model that generalizes better than any single tree.

Advantages and Disadvantages

• Decision trees advantages: Interpretability (readable if-then rules), support for categorical and numeric features, applicability to classification and regression, fast inference, easy visualization.
• Decision trees disadvantages: Overfitting risk without strong stopping or pruning, instability (sensitive to small data changes), bias toward features with many levels (more potential split points lead to higher apparent information gain), and potentially suboptimal global structure due to greedy splitting.
• Random forests advantages: Higher accuracy and better generalization than single trees, robustness to overfitting through averaging, built-in feature importance via split usage or impurity reduction, and strong performance with minimal preprocessing.
• Random forests disadvantages: Reduced interpretability (must inspect many trees), higher computational and memory cost, sensitivity to hyperparameters like number of trees and feature subsampling size, and longer training time as trees increase.

Hyperparameter Tuning (Random Forest Focus)

• Number of trees (n_estimators): Increasing T usually improves performance up to a plateau; beyond that, gains vanish but compute cost rises. Practical approach: start with a few hundred and grow until validation accuracy stabilizes.
• Feature subset size (max_features): Controls m, the number of features considered at each split. Smaller m increases diversity but may miss strong features; larger m makes trees more similar and can reduce ensemble benefit.
• Tree depth and leaf sizes: Even in forests, excessively deep trees can overfit bootstraps; gentle constraints (max_depth, min_samples_leaf) can improve stability and speed.
• Evaluation strategy: Use cross-validation to compare settings and pick the sweet spot between accuracy and cost.

Handling Missing Data

• Imputation: Replace missing numeric values with mean or median and categorical values with mode. Simple and widely supported.
• Missing branch: Create a special route when the splitting feature is missing, keeping that uncertainty explicit. Some implementations support this natively.
• Skip feature if missing: When evaluating a sample, if a feature needed for a node is missing, some libraries can default to other behavior; check documentation.
• Library behavior: Different libraries vary; always confirm defaults and options to avoid unintended routing of missing values.

Bias Toward Features with Many Levels

• Phenomenon: Features with many distinct values offer many possible split points, making it easier (by chance) to achieve large apparent impurity reductions. The greedy algorithm may overuse such features even if they aren’t truly most predictive.
• Mitigation: Use strong validation, constrain tree depth, and consider feature engineering or grouping categories. Random forests reduce the impact by feature subsampling, which limits repeated selection of such features across trees.

Computation and Performance Considerations

• Training complexity (trees): Evaluating all candidate splits can be costly, especially with many features and large datasets. Efficient implementations sort values once per feature per node and reuse scan-based computations.
• Training complexity (forests): Scales roughly linearly with the number of trees; parallel training helps because trees are independent. Memory usage rises with more trees and deeper structures.
• Inference: Prediction is fast: routing down O(depth) nodes per tree and aggregating across T trees. Depth control keeps inference predictable.

Step-by-Step Implementation Guide Step 1: Prepare data

• Gather training features X and labels y. Handle categorical data as required by your chosen library (some support categorical splits directly; others require encoding). Decide how to handle missing values: impute, special branch (if supported), or leave to library defaults.

Step 2: Train a decision tree (baseline)

• Choose impurity metric: Gini or entropy for classification. Set stopping criteria: max_depth (e.g., 5–15), min_samples_split (e.g., 2–20), min_samples_leaf (e.g., 1–10). Fit the tree on (X, y). Inspect the learned structure and evaluate on validation data.

Step 3: Train a random forest

• Choose number of trees (start with 200–500). Choose max_features (e.g., sqrt(M) for classification). Optionally set gentle depth/leaf constraints for stability. Fit the forest on (X, y). Evaluate validation performance and adjust n_estimators upward until performance plateaus.

Step 4: Interpret and diagnose

• Feature importance: Review which features are used often or reduce impurity the most. Stability: Compare validation to training performance to check overfitting. Speed: Measure training and inference time as trees increase.

Step 5: Handle practical issues

• Missing data: Apply imputation or choose library options for missing split handling. Class imbalance: Although not a primary topic here, ensure evaluation metrics reflect class ratios. Reproducibility: Set random seeds for bootstrapping and feature subsampling.

Tips and Warnings

• Don’t overgrow trees: Deep, unconstrained trees memorize noise; set reasonable depth and leaf sizes.
• Prefer validation curves over guessing: Increase n_estimators until improvements flatten, then stop to save compute.
• Beware feature leakage: If a feature encodes target information improperly (e.g., post-outcome data), trees will exploit it aggressively; clean data carefully.
• Understand defaults: Libraries differ on impurity metrics, handling categorical splits, and missing values; always check documentation.
• Expect interpretability trade-offs: If explainability is key, a single, well-regularized tree is easier to communicate than a forest; if accuracy is key, prefer the forest.

By following these technical steps and considerations, you can build decision trees that are transparent and random forests that are robust, tuning them to your data’s size, complexity, and accuracy needs.

This lecture built a complete understanding of decision trees and random forests by grounding them in supervised learning and loss minimization. Decision trees split data into purer groups using impurity measures (Gini or entropy) and choose splits that maximize information gain. The tree grows recursively until stopping rules like max depth or minimum samples prevent overfitting, and leaves make predictions by majority class or average value. Random forests then combine many such trees trained on bootstrapped data and random feature subsets, aggregating predictions to reduce variance and improve generalization.

The main trade-offs are clear: decision trees offer interpretability and simplicity but can overfit and be unstable; random forests deliver higher accuracy and robustness but at the cost of interpretability and greater computational load. Practical tuning focuses on the number of trees—growing until validation performance plateaus—and sensible constraints on tree depth and leaf sizes. The lecture also connected these models to the broader ensemble landscape (bagging, boosting, stacking) and addressed everyday issues like handling missing data via imputation, missing branches, or skipping features depending on library support.

To practice, start by fitting a single decision tree with Gini impurity and experiment with max_depth, min_samples_split, and min_samples_leaf to observe overfitting and generalization. Next, train a random forest, increase n_estimators stepwise (e.g., 200 → 400 → 800), and track validation accuracy to find the plateau. Inspect feature importance to understand which inputs drive predictions, and test different missing-data strategies to see their effects. A small project could compare a single tree and a forest on the same dataset, documenting interpretability vs. accuracy and computing cost.

Your next steps include exploring other ensembles like gradient boosting and AdaBoost, which build trees sequentially and often reach state-of-the-art accuracy on tabular tasks. Deepen your understanding of cross-validation for reliable model selection and practice fair comparisons across hyperparameters. The core message to remember is this: trees convert complex patterns into simple rules, and forests turn many such rules into a stable, accurate predictor. Use trees when clarity is essential, forests when performance is paramount, and always validate your choices with data.