Machine Learning

Imperial College London

Nuri Cingillioglu

Part 5: Decisions, Decisions

The art of separation

How we make decisions?

"If the patient's systolic blood pressure is AND age , order an ECG; otherwise, if troponin is elevated, admit immediately."

Compared to:

• Multiply blood pressure with , then age with , then add them up and pass it through a sigmoid function.

Okay Steve, how do we let machines make decisions in a similar way?

• Discrete, conditional, hierarchical, and rule-based Decision Trees.

Imperial Exam Prep

• Mixed features: continuous (Study Hours) + categorical (Exam Prep).
• Total: 6 Pass, 4 Fail. How do we build a decision tree to classify them?

Decision Trees

Decision Trees mathematically

A decision tree divides feature space into disjoint axis-aligned bounding boxes :

Piecewise-Constant Functions

The tree's prediction for any query is a regional constant :

• Classification: Majority vote where
• Regression: Regional sample mean

Okay Steve, build me some trees

Can We Search All Possible Trees?

• For samples, the number of binary tree topologies grows exponentially...
• Hyafil & Rivest (1976): Finding the globally optimal decision tree is NP-complete.

Top-Down Greedy Induction

Classification and Regression Trees (CART)

Since global search is impossible, we use a greedy divide-and-conquer heuristic:

1. Start at the root node containing all training data .
2. Scan all features and candidate thresholds.
3. Pick the single split that produces the cleanest, most pure children.
4. Partition the data into and .
5. Repeat on and until a stopping criterion is met.

But how do we define "cleanest" or "most pure"?

What Does "Impurity" Mean?

Consider our 10 students at the root node: 6 Pass, 4 Fail.

• If a split creates children that are still 50% Pass and 50% Fail, we gained zero information.
• If a split creates a child with 100% Pass and 0% Fail, that child is pure!

We define an Impurity Measure that:

• Equals when the node is completely pure (all samples belong to one class).
• Is maximised when classes are evenly mixed.

Impurity Reduction (Gain):

where:

• is the impurity of the parent node.
• is the candidate feature, and is the threshold:

• and weight each child's impurity by its sample share.

The Splitting Criteria

For class proportions in a node:

Why does misclassification error fail?

Suppose a node has samples ( Class 1, Class 2). Current error: .

Misclassification error is blind to Split B creating a pure terminal leaf. It is not strictly concave.

Splitting Criteria

Back to exams

Let's calculate the root impurity for our 10 Imperial students (6 Pass, 4 Fail):

Scanning...

For continuous feature Study Hours: .
Candidate split thresholds are the midpoints: .

Comparing all candidate splits

Let's evaluate the candidate splits using Gini impurity ():

Winner: The algorithm chooses Study Hours <= 4.5, well done Steve.

Building the Tree: The Next Step

Following the winning split Study Hours <= 4.5:

• Left Child (): Students S1, S2, S3 (all Fail).
  • Impurity Pure leaf node! Prediction: Fail.
• Right Child (): Students S4 through S10 (6 Pass, 1 Fail).
  • Impurity .
  • The algorithm now recurses on this subset:
  • Scanning candidate splits on the remaining 7 students isolates S5 (who did not attend Exam Prep, Study = 6.0, Fail).
  • Splitting on Exam Prep == Yes separates S5 (, Fail) from the rest (, 100% Pass)!

Decision Tree Demo

What About Regression Trees?

Suppose target is continuous (e.g. Exam Score or Salary in £k).

Toy Example: Experience vs. Salary (£k)

Consider 5 software engineers:

• Parent Node: Mean .
• Parent Variance: .
• Candidate Split at :
  • Left child (): .
  • Right child (): .

Regression = Variance Reduction

Weighted child variance:

Variance reduction (gain):

Here variance is used as a measure of impurity.

Failure Mode 1: The Diagonal Boundary

If the true boundary is diagonal (not axis-aligned). A decision tree becomes a staircase:

Failure Mode 2: High Variance & Instability

When competing splits have similar gain, shifting just 1 data point flips the root cut from vertical () to horizontal ()—rotating the entire partition and altering downstream decisions:

Failure Mode 3: Overfitting Dynamics

If unconstrained, trees split until every leaf contains potentially 1 sample.

Pre-Pruning & The Horizon Effect

To prevent overfitting, can we simply stop growing when ?

The XOR Trap

Consider 4 points: , , , .

• Every single 1-step split yields zero impurity decrease!
• Greedy early stopping halts immediately at the root.
• Yet, splitting to depth 2 achieves 100% purity.

Common Pre-Pruning Heuristics

• Minimum Impurity Decrease ():
  Stops when single-step information gain vanishes.
• Maximum Depth (max_depth):
  Imposes a hard cap on overall tree depth.
• Minimum Leaf Samples (min_samples_leaf):
  Ensures support at every prediction leaf.

Post-Pruning: Minimal Cost-Complexity

Pre-pruning can stop too early (horizon effect). So we take a two-stage approach:

1. Grow Deep: Grow the full unconstrained tree down to purity (uncovering multi-step feature interactions).
2. Prune Back: Retrospectively collapse subtrees that don't justify their complexity.

The Regularised Objective

For any subtree , define the cost:

• : Training error (misclassification rate or MSE).
• : Number of terminal leaf nodes (model complexity).
• : Complexity parameter (the price per leaf).

The Intuition: What is a Branch Worth?

We cannot search all subtrees (combinatorial explosion). So we ask a local question:

"If we collapse an internal branch back into a single leaf , how much accuracy do we lose per leaf saved?"

• Keeping : Contributes error and complexity .
• Collapsing to leaf : Contributes error and complexity .

They have identical cost when , which gives:

• If a branch uses 4 leaves to correct 1 noisy sample, is tiny cheap to prune.
• If a branch separates 50 real samples, is huge expensive to prune (keep it!).

Calculating

An internal node contains training samples ( Pass, Fail) out of total samples:

Weakest Link Collapse:

Calculating

• When : Keeping the 4 leaves is worth the complexity penalty.
• When : The penalty outweighs the gain Subtree collapses into leaf !

# 1. Start with the fully grown tree
T = T_max
trees = [T]
alphas = [0.0]

while len(internal_nodes(T)) > 0:
    # 2. Compute g(t) for every internal node currently in T
    #    g(t) = (error(t) - error(T_t)) / (|T_t| - 1)
    g_scores = { t: compute_effective_alpha(t, T) for t in internal_nodes(T) }
    
    # 3. Find the weakest link (smallest g(t))
    t_star = min(g_scores, key=g_scores.get)
    alpha_next = g_scores[t_star]
    
    # 4. Collapse subtree T_t* into a single leaf node
    T = collapse_subtree(T, t_star)
    
    trees.append(clone(T))
    alphas.append(alpha_next)

# Produces a finite nested sequence: T_0 ⊃ T_1 ⊃ T_2 ⊃ ... ⊃ T_root

When to stop?

Optimal Tree via Cross-Validation

Pruning yields a sequence of nested subtrees: and intervals

• Why not use training error? Training error strictly favours ().
• We evaluate each candidate subtree on a held-out validation set (or via -fold cross-validation) to find the optimal :

The Bridge to Ensembles

Single decision trees have a dilemma:

• Unpruned: Low bias, high variance Overfitting
• Pruned: High bias, low variance Underfitting

Can we combine multiple diverse models to produce a single superior model?

Intuition: Tree Bias vs. Tree Variance

Imagine predicting whether a student passes based on Study Hours and Exam Prep:

Condorcet's Jury Theorem (1785)

Suppose independent voters each have probability of being correct. The majority vote accuracy converges to as :

Bagging (Bootstrap Aggregation)

We don't have infinite voters. We have one dataset of size :

1. Draw bootstrap datasets by uniformly sampling points with replacement.
2. Train an unpruned deep decision tree on each bootstrap sample.
3. Aggregate predictions:
   • Classification: Majority vote.
   • Regression: Average .

Why it works

The probability of omitting a specific sample across draws is:

• In-Bag (): Each tree trains on a distinct random subset ensures diversity.
• Out-of-Bag (OOB, ): Over a third of samples are held out for any given tree.

By forcing each tree to see only of unique points, the trees learn slightly different split boundaries. This drives the correlation between trees () down

The Limit of Bagging

Why doesn't Bagging reduce variance to zero?

For estimators with individual variance and pairwise correlation :

• As , the second term drops to .
• But the first term remains as is!
• The issue: If a dataset has a dominant feature (e.g. Study Hours), every bagged tree splits on it at the root remains high.

Intuition: decorrelation means they predict different things. So they can correct each other's mistakes.

Random Forests: De-Correlating Trees

At each split in every tree:

• Instead of scanning all features, randomly select a subset of features.
• Best split is chosen only from this restricted subset.

That's it...

Standard Heuristics in Practice:

• Classification: (e.g., pick from only random candidate features per split).
  • Why so few? Majority voting is resilient to individual noisy trees; aggressive feature restriction forces exploration, driving correlation .
• Regression: (e.g., pick from random candidate features per split).
  • Why more features? Numerical averaging requires each tree to maintain reasonable predictive accuracy; severe restriction degrades regression fits.

Trade-off (): Smaller lower correlation (lower floor), but higher individual tree bias . These standard heuristics strike a practical balance.

Feature Importance: MDI vs. Permutation

How do we interpret an ensemble of 500 trees?

• The Motivation (Black Box Dilemma): A single tree is transparent, but a 500-tree forest has tens of thousands of splits. In healthcare, lending, or scientific research, we need to know: which features genuinely drive the predictions?

Mean Decrease Impurity (MDI)

• Sum of all impurity drops on feature across all trees, weighted by sample counts.
• Fast & Built-in (rf.feature_importances_).
• Pitfall: Computed on training data; heavily biased towards continuous or high-cardinality noise features!

A feature that offers many splits can have a chance of creating a predictive split more often than it is truly important.

Permutation Importance (PFI)

• Randomly shuffle the feature on test data, breaking its relationship with .
• Measure drop in model score: .

Baseline Test Set:
[ Feature A | Feature B | Feature C ]  ──► Predict ──► Score: 0.92

Permuting Feature B (Shuffling column values across rows):
[ Feature A | Feature B (shuffled) | Feature C ]  ──► Predict ──► Score: 0.74

Importance of Feature B = 0.92 - 0.74 = +0.18

E.g. high cardinality features such as zip-code, transaction_id will score high on MDI but low on PFI.

Bagging vs Boosting

So far we looked at bagging.

The Additive Model

• : Initial base prediction, typically the constant target mean .
• : Weak decision tree trained to predict current residuals .
• : Shrinkage learning rate, scales each tree's update to prevent overfitting.

# Initialise with baseline guess
y_pred = mean(y)

# Sequentially correct errors
for t in range(1, T + 1):
    residual = y - y_pred
    tree = fit_tree(X, target=residual)
    y_pred += eta * tree.predict(X)

Toy Example: Boosting on Residuals

Suppose we want to predict exam scores for 4 students:

• Notice the errors after Step 1: .
• The residual magnitude has halved! Next stump will fit these remaining errors.

Residuals Are Gradients in Disguise

In our toy example, we nudged predictions by fitting errors .

Notice what happens if we take the derivative of Squared Error Loss:

• The residual is literally the negative gradient!
• Nudging predictions by residuals is Gradient Descent in prediction space:

• To generalise to unseen points , we train a tree to predict these gradients:

Gradient Boosted Decision Trees (GBDT)

Because residuals are just negative gradients, this works for any differentiable loss !

Jerome Friedman (2001) generalised boosting by replacing residuals with negative gradients:

The GBDT Principle: We don't differentiate the trees; we differentiate the loss with respect to our predictions, and train trees to point us downhill!

Visualising GBDT for Regression

Toy Example: GBDT for Binary Classification

Suppose we want to predict exam success () from study hours. Initialise with baseline (50/50 prior):

• Stump splits at , predicting optimal leaf step .

Visualising GBDT for Classification

Modern Variants

In practice, competitive tabular ML uses three popular GBDT toolkits:

• XGBoost (2016): Hardware speedups and regularisation; famous for winning Kaggle competitions.
• LightGBM (2017): Feature binning for blazing-fast training on millions of rows.
• CatBoost (2018): Automatic handling of categorical variables with minimal tuning.

Beneath the hood, all three run Gradient Boosting.

Decisions Decisions

Comparison Matrix

Implementation in Python

from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier

# 1. Single Decision Tree with Cost-Complexity Pruning
tree = DecisionTreeClassifier(ccp_alpha=0.02, random_state=42)
tree.fit(X_train, y_train)

# 2. Random Forest (Parallel Variance Reduction)
rf = RandomForestClassifier(
    n_estimators=300, 
    max_features="sqrt",      # Subspace m = sqrt(d)
    oob_score=True,           # Built-in out-of-bag validation
    n_jobs=-1,                # Parallel CPU cores
    random_state=42
)
rf.fit(X_train, y_train)
print(f"OOB Accuracy: {rf.oob_score_:.3f}")

# 3. Gradient Boosted Trees (Sequential Bias Reduction)
gbdt = GradientBoostingClassifier(
    n_estimators=200, 
    learning_rate=0.05,       # Shrinkage eta
    max_depth=3,              # Shallow weak learners
    subsample=0.8,            # Stochastic gradient boosting
    random_state=42
)
gbdt.fit(X_train, y_train)

Practical Guidelines for Tabular ML

1. Need Complete Interpretability / Regulatory Audit:
   • Use a Single Pruned Decision Tree (or shallow tree with max_depth <= 4).
2. Tabular Data with Minimal Tuning Required:
   • Use a Random Forest. Robust to default hyperparameters, immune to catastrophic overfitting with large .
3. Maximum Competitive Predictive Accuracy on Tabular Data:
   • Use Gradient Boosting (LightGBM / XGBoost / CatBoost).
   • Tune learning rate , tree depth (), and early stopping on validation loss.
4. Perceptual Data (Images, Audio, Natural Text):
   • Use Deep Neural Networks (CNNs, Transformers - Parts 4 & 6). Trees cannot exploit translation equivariance or continuous spatial topologies.

Where is my artificial brain?

We wanted to make decisions like humans do, but...

AI ML Numbers game

Next Part: We'll get rid of labels to see if we can learn hidden structures in the data.

Appendix

Bagging Derivation

Expand variance of a sum into all pairs:

Split into diagonal and off-diagonal pairs:

• Diagonal (): terms with variance
• Off-diagonal (): terms with covariance

Simplify algebraically: