Phase 11 - Lesson 11.6

Trees, Ensembles, Boosting, and Support Vector Machines

Greedy recursive partitions, the variance-cut of bagging and random forests, the bias-cut of boosting, and the max-margin idea with kernels.

⏱ 55 min● Intermediate🔗 Prereqs: 11.1, 11.3, 11.5

↖ Phase 11 hub

Builds on: Bias-variance (11.1) and CV (11.3) explain why ensembles work; logistic loss (11.5) is a boosting surrogate.
Leads to: Gradient boosting is a standard baseline in quant feature research; margins recur in kernel methods.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Explain how CART grows a tree by greedily minimizing an impurity (Gini/entropy/RSS).
Contrast bagging and random forests as variance-reduction ensembles of high-variance trees.
Describe boosting as sequential, bias-reducing additive modeling (forward stagewise / gradient boosting).
Derive the max-margin hyperplane and the role of the hinge loss and kernel trick in SVMs.
Judge when each method is appropriate for noisy, low-signal financial data.

Key Vocabulary

CART: Classification And Regression Trees: recursive binary splits chosen to most reduce an impurity measure.

Impurity: A node's heterogeneity: Gini \(\sum_k \hat p_k(1-\hat p_k)\) or entropy for classification, RSS for regression.

Bagging: Bootstrap AGGregatING: average many trees fit on bootstrap resamples to cut variance.

Random forest: Bagging plus random feature subsampling at each split, decorrelating the trees for extra variance reduction.

Boosting: Sequentially adding weak learners, each fit to the current residuals/gradient, reducing bias.

Margin: The distance from the decision hyperplane to the nearest training point; SVMs maximize it.

Kernel trick: Replacing inner products \(x^\top x'\) with a kernel \(K(x,x')\) to fit nonlinear boundaries without explicit features.

Intuition & Motivation

Intuition

A single decision tree is a game of twenty questions: at each node pick the split that most purifies the two children, and recurse. Trees are wonderfully flexible and interpretable but high variance - nudge the data and the whole tree can reorganize. Two opposite cures exist. Bagging/forests average many independent-ish deep trees to cancel their variance (the ensemble is smoother than any member). Boosting instead grows many shallow trees in sequence, each patching the errors of the last, driving down bias.

Support vector machines take a geometric route: of all separating hyperplanes, choose the one with the widest safety margin to the nearest points. Only those nearest points - the support vectors - matter. Swap inner products for a kernel and the same linear machinery draws curved boundaries in the original space. All of these are powerful, and all of them overfit noisy financial data enthusiastically unless disciplined by cross-validation and strong regularization.

Trees: greedy recursive partitioning

A regression tree partitions feature space into boxes \(R_1,\dots,R_M\) and predicts the mean of \(y\) in each box. Finding the optimal partition is NP-hard, so CART is greedy: at each node choose the split variable \(j\) and threshold \(s\) that most reduce the objective. For regression that is the residual sum of squares,

\[\min_{j,s}\Big[\sum_{x_i\in R_L}(y_i-\bar y_L)^2+\sum_{x_i\in R_R}(y_i-\bar y_R)^2\Big];\] (11.14)

for classification it is impurity, e.g. Gini \(\sum_k \hat p_{k}(1-\hat p_{k})\) or cross-entropy \(-\sum_k \hat p_k\log\hat p_k\). Grow deep, then prune back using cost-complexity \(R_\alpha(T)=\text{RSS}(T)+\alpha|T|\) with \(\alpha\) chosen by CV - the same complexity-penalty idea as 11.3.

Ensembles: averaging vs sequencing

Worked Example - Why bagging reduces variance

Take \(B\) bootstrap resamples, fit a deep tree \(\hat f_b\) on each, and average: \(\hat f_{\text{bag}}=\tfrac1B\sum_b \hat f_b.\)

If the trees were independent each with variance \(\sigma^2\), the average has variance \(\sigma^2/B\) - a pure variance cut with no bias change.

Real trees are positively correlated (\(\rho\)), so the variance floors at \(\rho\sigma^2+\tfrac{1-\rho}{B}\sigma^2\to\rho\sigma^2\); reducing \(\rho\) is the key.

Random forests lower \(\rho\) by considering only a random subset of features at each split, decorrelating the trees for a further variance drop.

Boosting goes the other way. Forward stagewise additive modeling builds \(F_M(x)=\sum_{m=1}^M \nu\,h_m(x)\), where each weak learner \(h_m\) is fit to the negative gradient of the loss at the current model (for squared loss, the residuals) and \(\nu\) is a small learning rate. Each step reduces bias; the ensemble of shallow trees becomes a strong learner. AdaBoost is the special case using the exponential loss.

Method	Base learner	Fights	Trees are	Main knob
Bagging	deep trees	variance	parallel, independent-ish	#trees \(B\)
Random forest	deep trees	variance	parallel, decorrelated	features/split, \(B\)
Boosting	shallow trees	bias	sequential	learning rate \(\nu\), #trees

Support vector machines and the margin

For separable classes \(y_i\in\{-1,+1\}\), the max-margin hyperplane solves

\[\min_{w,b}\tfrac12\|w\|^2 \ \text{ s.t. } \ y_i(w^\top x_i+b)\ge 1\ \forall i,\] (11.15)

whose margin width is \(2/\|w\|\). Non-separable data use a soft margin with slack, equivalently minimizing hinge loss \(\sum_i\max(0,1-y_i(w^\top x_i+b))+\tfrac{\lambda}{2}\|w\|^2\) - a regularized convex program. Only the support vectors (points on or inside the margin) determine \(w\). Replacing \(x_i^\top x_j\) by a kernel \(K(x_i,x_j)\) (e.g. RBF) fits nonlinear boundaries without ever forming the feature map - the kernel trick.

Key Idea

Every method here is a knob on the bias-variance dial: prune/limit depth, add trees, subsample features, set a learning rate, or tune \(\lambda\) and the kernel bandwidth. In low signal-to-noise finance the right setting is aggressively regularized - shallow trees, few features, heavy shrinkage - and validated strictly out of time.

Interactive: the best split of a decision stump

Common Mistakes to Avoid

Reading a single tree's splits as stable ‘insights’ - trees are high variance and reorganize under tiny data changes.
Letting boosting run too long with a large learning rate; it overfits, and on noisy returns it memorizes noise fast.
Judging feature importance from one model as causal; correlated predictors trade importance arbitrarily.
Using an RBF SVM without scaling features or tuning the bandwidth - results become meaningless.
Applying powerful nonlinear learners to tiny, low-signal financial samples and trusting the in-sample fit.

Quant Practitioner Tips

Random forests are a strong, low-tuning baseline; gradient boosting usually wins with careful learning-rate/depth/early-stopping tuning.
Use a small learning rate with early stopping (validated out of time) - the single most important boosting discipline.
Prefer shallow trees (stumps to depth-3) for noisy financial targets; deep interactions rarely survive out of sample.
For SVMs, standardize features and tune \((C,\gamma)\) jointly by CV; report support-vector counts as a complexity check.

Knowledge Check

Q1 Medium

Bagging improves a single deep tree primarily by:

Reducing bias

Reducing variance by averaging many high-variance trees

Making the tree deeper

Removing the need for cross-validation

Q2 Medium

Boosting differs from bagging in that it:

Fits trees in parallel on bootstrap samples

Fits shallow trees sequentially, each to the current residuals/gradient

Always uses deep trees

Cannot overfit

Q3 Medium

In a soft-margin SVM, the decision boundary is determined by:

All training points equally

Only the support vectors (points on or inside the margin)

The class means

The most distant points

Practical Exercise

You must predict the sign of next-day returns (near-zero signal, heavy noise) with 1500 daily observations and 40 features. (a) Would you reach first for a deep single tree, a random forest, or gradient boosting, and why? (b) List three regularization/validation controls you would impose. (c) How do you guard against fooling yourself?

▶ Show full solution

(a) Not a deep single tree - far too high variance for this noise. A random forest is a sensible, low-tuning baseline (variance reduction, decorrelated trees). Gradient boosting can do better but only with disciplined tuning; with signal this weak, its bias-cutting power is a double-edged sword and it overfits readily.

(b) (i) Shallow trees (depth 1–3) and a small learning rate with early stopping; (ii) feature subsampling and row subsampling; (iii) an explicit complexity/CV budget - tune by walk-forward CV, not random K-fold.

(c) Validate strictly forward in time with purge/embargo; hold out a final out-of-time set never used in tuning; count how many model/feature configurations you tried and deflate the reported Sharpe accordingly; and sanity-check that a linear/logistic baseline is actually beaten - if the fancy model barely edges a shrunken linear model, prefer the simpler one.

After the reveal, answer for yourself: With near-zero signal, model selection is where most of the overfitting happens - discipline the search, not just the model.

Lesson Summary

Trees greedily split feature space to reduce impurity but are high variance. Bagging and random forests average many decorrelated deep trees to cut variance; boosting sequences many shallow trees, each fit to the gradient, to cut bias. SVMs pick the max-margin hyperplane, depend only on support vectors, and use kernels for nonlinearity. All are bias-variance knobs that overfit low-signal financial data unless heavily regularized and validated strictly out of time.

Formula Sheet Additions

Bagged variance

\[\Var\approx\rho\sigma^2+\tfrac{1-\rho}{B}\sigma^2\]

Averaging cuts the \(1/B\) term; decorrelation (forests) cuts \(\rho\sigma^2\).

SVM margin

\[\min\tfrac12\|w\|^2\ \text{s.t.}\ y_i(w^\top x_i+b)\ge1\]

Margin width \(2/\|w\|\); soft version = hinge loss + \(\ell_2\).

Error Log Checklist

Did I choose depth/learning rate to control variance for this noise level?
Did I validate boosting with early stopping on an out-of-time set?
Am I over-interpreting unstable single-model feature importances?
Did I standardize features and tune the kernel before trusting an SVM?

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: How do bagging and boosting each attack the bias-variance decomposition?
A: Bagging averages high-variance deep trees to cut variance; boosting sequences shallow trees fit to residuals/gradient to cut bias.

Q: What extra step turns bagging into a random forest and why does it help?
A: Randomly restricting the candidate features at each split decorrelates the trees, lowering \(\rho\) so the ensemble variance \(\to\rho\sigma^2\) falls further.

Q: What points determine an SVM boundary, and what does the kernel trick buy?
A: Only the support vectors (on/inside the margin); kernels replace inner products to fit nonlinear boundaries without explicit feature maps.

Flashcards

Click to flip. These feed the site-wide spaced-repetition queue.

CART split

Greedily minimize weighted child impurity (Gini/entropy) or RSS; prune by cost-complexity \(R_\alpha=\text{RSS}+\alpha|T|\).

Bagging vs boosting

Bagging: parallel deep trees, cut variance. Boosting: sequential shallow trees on gradients, cut bias.

SVM

Max-margin \(\min\tfrac12\|w\|^2\) s.t. \(y_i(w^\top x_i+b)\ge1\); hinge loss soft margin; kernels for nonlinearity.

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

The Elements of Statistical Learning (Hastie, Tibshirani & Friedman, 2nd ed.) current - ESL 9,10,12,15 - Ch. 9 (trees), 8/15 (bagging, random forests), 10 (boosting), 12 (SVMs and kernels).
Additional Exercises for Convex Optimization (Boyd & Vandenberghe, 2016) current - Boyd 8 - The SVM soft-margin problem as a convex quadratic program with hinge loss.

← 11.5 Next: 11.7 →