The kernel trick, support vector machines, kernel ridge and decision trees, with worked numbers

The maximum-margin classifier

Among all the lines that separate two classes without error, the SVM keeps the one that stays as far as possible from the closest points on each side.

When two classes can be separated by a straight line, infinitely many lines do it with zero training error. Logistic regression picks one through the likelihood. The support vector machine (SVM) asks a geometric question instead: which boundary leaves the widest empty band between the classes? A new client resembles a known one plus a little noise, so a boundary that grazes a training point misclassifies its noisy neighbours.

Code the classes as $y_i \in \{-1, +1\}$ and write $f(x) = w^{\top}x + b$. Rescaling $w$ and $b$ together leaves the boundary unchanged, so we set $|f| = 1$ at the nearest points. Since a point lies at distance $|f(x)| / \lVert w \rVert$ from the hyperplane, the band is $2/\lVert w \rVert$ wide, and widening it means shrinking $\lVert w \rVert$. The result is a convex quadratic problem with a unique minimum (Cortes and Vapnik, 1995):

The solution, which scikit-learn's SVC with a linear kernel and a very large $C$ also returns, has $\lVert w \rVert = 2\sqrt2/3 \approx 0.943$, so the band is $2/\lVert w \rVert = 3/\sqrt2 \approx 2.12$ wide: exactly the gap between the two dashed lines, measured along the normal $(1, 1)/\sqrt2$. Three clients touch the band; they are the support vectors. The other three could move, or disappear, without the boundary changing.

Back to contents.

Soft margin, hinge loss and the price C

Real data are never perfectly separable, so the SVM lets some points cross into the band and charges a fixed price for each unit of trespass.

On credit data, no line separates the defaulters from the sound clients. Cortes and Vapnik (1995) give each point a slack variable $\xi_i \ge 0$, the amount by which it breaks the margin, and add $C \sum_i \xi_i$ to the objective. At the optimum each slack equals $\max(0, 1 - y_i f(x_i))$, so the constraints can be removed altogether:

The summand is the hinge loss: zero for a point on the right side with a lead of at least 1, then growing linearly as the point moves into the band or across the boundary. Read this way, the soft-margin SVM is a loss plus a penalty on $\lVert w \rVert^{2}$, the same shape as ridge, with $C$ playing the role of $1/\lambda$. A small $C$ gives a wide margin and strong regularisation (risk of underfitting), a large $C$ a narrow margin and a risk of overfitting, as with the C of LogisticRegression.

Back to contents.

The dual problem: only the support vectors count

Rewritten with one price per constraint, the SVM shows that points far from the boundary get a price of zero, so deleting them changes nothing.

Attach a Lagrange multiplier $\alpha_i \ge 0$ to each constraint and subtract the constraints from the objective. Setting the gradient in $w$ to zero, then the derivative in $b$, gives two identities. Substituting them back removes $w$ and $b$ and leaves a problem in $\alpha$ alone:

With a soft margin, the only change is a cap $\alpha_i \le C$. Complementary slackness, one of the Karush-Kuhn-Tucker (KKT) conditions, gives $\alpha_i\,[\,y_i f(x_i) - 1\,] = 0$, so either the price is zero or the constraint is tight. A point classified correctly and outside the band has $\alpha_i = 0$ and vanishes from $w$ and from every prediction. That sparsity is why SVC keeps only its support_ points to predict.

Worked example: four clients on a line

1. Data. Sound clients at $x = -3$ and $x = -1$, defaults at $x = 2$ and $x = 4$. The two inner points are the closest to the other class.
2. Supports on the edge. Writing $y\,f(x) = 1$ at $x = -1$ and $x = 2$ gives $w - b = 1$ and $2w + b = 1$. Adding them, $3w = 2$, so $w = 2/3$, $b = -1/3$, and the boundary sits at $x = 1/2$.
3. Outer points. At $x = -3$ and $x = 4$ the lead is $7/3 > 1$, so the constraint is slack and, by complementary slackness, their price is zero.
4. Prices. The condition $\sum_i \alpha_i y_i = 0$ forces the two remaining prices to be equal, say $a$. Then $w = a(-1)(-1) + a(+1)(2) = 3a = 2/3$, hence $a = 2/9$.
5. Check. The primal value $\tfrac12 w^{2} = 2/9$ equals the dual value $\sum_i \alpha_i - \tfrac12 w^{2} = 4/9 - 2/9$, and the margin $2/w = 3$ is the distance from $-1$ to $2$. Moving the point at $-3$ to $-10$ changes nothing; moving the point at $-1$ changes everything.

Back to contents.

The kernel trick: polynomial and RBF kernels

The dual touches the data only through similarities between pairs of points, so swapping the dot product for a richer similarity bends the boundary without extra work.

Look again at the dual: training needs only the $n \times n$ table of dot products $x_i^{\top}x_j$, the Gram matrix, and prediction only $x_i^{\top}x$. Points on a line with one class at both ends and the other in the middle cannot be split by one threshold, but after $x \mapsto (x, x^{2})$ a horizontal line does it. A curved boundary is a flat one after a transformation $\varphi$, the feature map. The kernel trick computes $\varphi(x)^{\top}\varphi(z)$ straight from $x$ and $z$, without building $\varphi$ (Boser, Guyon and Vapnik, 1992).

For the degree-2 polynomial kernel in two dimensions, expanding the square and splitting the cross term into $\sqrt2 \cdot \sqrt2$ reveals the hidden map:

Check with $x = (1, 2)$ and $z = (3, -1)$. The kernel side needs two products, a sum and a square: $x^{\top}z = 1$, so $k = 1$. The feature side builds $\varphi(x) = (1, 2\sqrt2, 4)$ and $\varphi(z) = (9, -3\sqrt2, 1)$, whose dot product is $9 - 12 + 4 = 1$. The general kernel $(x^{\top}z + c)^{d}$ contains every interaction up to degree $d$ for the price of one dot product and a power.

The Gaussian or RBF kernel (radial basis function) is 1 for identical points and fades with distance; $\gamma$ sets how far each training point's influence reaches. For two points at squared distance 5, it is $e^{-0.5} \approx 0.607$ with $\gamma = 0.1$ and about 0.082 with $\gamma = 0.5$. Expanding the exponential as a power series shows that its feature map has infinitely many coordinates. With a small $\gamma$ the boundary is nearly straight; with a large one it draws islands around single points.

Back to contents.

Kernel ridge, and kernels in practice

Kernel ridge is ridge regression rewritten with one weight per training point, which lets a kernel replace the dot product and still gives a closed-form answer.

Start from the closed-form ridge. The identity $(X^{\top}X + \lambda I_p)X^{\top} = X^{\top}(XX^{\top} + \lambda I_n)$ shows that $\hat\beta = X^{\top}\alpha$ with one weight per training point. Predictions then involve only dot products $x_i^{\top}x$, which a kernel replaces (the representer theorem, Kimeldorf and Wahba, 1971):

Unlike the SVM there is no sparsity: the loss is squared, so in general every $\alpha_i$ is non-zero and the whole training set is kept. In exchange, fitting is one linear system, solved with np.linalg.solve rather than by inverting the matrix; with a linear kernel it must reproduce ridge to machine precision. In scikit-learn, KernelRidge calls $\lambda$ alpha and fits no intercept.

The two points with target 0 get negative weights: they pull the fit down around them. At $x = 1$ the target is 1, but the penalty shrinks the fit to 0.576.

Raising $C$ pushes in the same direction as raising $\gamma$, and both are chosen by cross-validation on a grid in powers of 10. Standardise first: an RBF kernel adds squared gaps in each variable's units, so a credit limit in tens of thousands of dollars drowns an age in years and $K$ collapses to the identity. The scaler goes inside the pipeline, fitted on the training folds.

The price of the trick is the $n \times n$ matrix: 32 MB in double precision for 2,000 rows, 2.6 GB for the 18,000 training rows of the credit dataset, and a solve in about $n^{3}$ operations. For large $n$, random Fourier features (Rahimi and Recht, 2007) build $D$ random cosine columns whose dot products approximate the RBF kernel; a logistic regression on them scales in $O(nD)$ and, unlike SVC or KernelRidge, returns probabilities.

Back to contents.

Decision trees: the split that purifies most

A decision tree asks a chain of yes-or-no questions, one variable at a time, choosing each question so that the groups it creates are as homogeneous as possible.

A decision tree plays Guess Who: was the client at least two months late last month? Then a question on the credit limit, and so on, until a leaf predicts the share of defaults among the training clients that reach it. CART (Breiman, Friedman, Olshen and Stone, 1984) grows the tree greedily from the top: at each node it tries every variable and every threshold (the midpoints between sorted values), keeps the split that most lowers the weighted impurity of the children, then recurses.

The Gini impurity $G$ measures how mixed a node is: pick two of its clients at random, with replacement, and it gives the chance that their classes differ; with two classes it equals $2p(1-p)$, zero on a pure node and at most $1/2$. Shannon entropy $H$, in bits, comes from Quinlan's ID3 (1986) and C4.5 (1993); its reduction is the information gain. The two curves have the same shape and almost always choose the same split. scikit-learn uses Gini by default.

Worked example: the gain of each split

1. Parent. Four defaults out of ten, so $p = 0.4$ and $G = 1 - 0.16 - 0.36 = 0.48$.
2. Children of A. Three defaults out of four on the left, $G = 1 - 9/16 - 1/16 = 6/16 = 0.375$, and one out of six on the right gives $G = 10/36 \approx 0.278$.
3. Weighted average. By counts, $0.4 \times 0.375 + 0.6 \times 0.278 \approx 0.317$, so split A gains $0.48 - 0.317 = 0.163$. With entropy, the gain is $0.971 - (0.4 \times 0.811 + 0.6 \times 0.650) \approx 0.256$, so A wins on both criteria.
4. Split B. Each side has two defaults out of five, the parent's proportion, so both children have the parent's impurity and the gain is zero. A question that reproduces the parent's mix teaches nothing, whatever the variable.
5. Check. DecisionTreeClassifier(max_depth=1) picks PAY_0 at the threshold 1.5, the midpoint between 1 and 2, and reports the same three impurities.

Back to contents.

Depth, pruning, instability and the bias of MDI

Left alone, a tree grows until it memorises the training set, so it has to be stopped or pruned, and its built-in importance scores must be read with suspicion.

By default (max_depth=None) scikit-learn grows the tree until every leaf is pure. A maximum depth, a minimum leaf size (min_samples_leaf) or a minimum gain stop it earlier; small leaves also give coarse probabilities.

The deck's simulation makes the point: one binary variable sets the default probability at 0.7 or 0.3, two others are noise, 1,000 rows to train and 1,000 to test, so no classifier can beat 0.70. A tree of depth 1 or 2 reaches 0.683 on test; an unlimited one scores 1.000 on train with 397 leaves and 0.549 on test, barely better than a coin.

Rather than stopping early, CART grows the full tree and then prunes it: $R(T)$ is the training error, $|T|$ the number of leaves and $\alpha$ a price per leaf, chosen by cross-validation (ccp_alpha in scikit-learn). The optimal subtrees are nested, so only a handful need testing.

With the largest price, two leaves remain: one split, on the only useful variable. A short tree can be read aloud as a rule that a client can contest, which regulated credit values. It is also unstable: refit a depth-3 tree after dropping 5 % of the rows at random and the second level jumps to noise variables and new thresholds. Breiman's bagging (1996) starts from that observation and leads to the random forests and boosting of the next session.

scikit-learn's feature_importances_ is the mean decrease in impurity (MDI): the size-weighted gains of the splits on each variable, normalised to 1. It is free but biased twice over. It is measured on the training data, so splits that fitted noise count too; and a continuous variable offers hundreds of thresholds where a binary one offers one, hence many more lucky splits. On the unlimited tree of the simulation, MDI puts the continuous noise first (0.754) and the useful variable second (0.206); permutation importance on held-out data restores the order (Strobl et al., 2007).

Back to contents.

Key takeaways

1. The SVM keeps the boundary with the widest margin, $2/\lVert w \rVert$, by minimising $\tfrac12 \lVert w \rVert^{2}$ under one constraint per point; the soft margin adds a hinge loss priced by $C$.
2. In the dual, $w = \sum_i \alpha_i y_i x_i$ and points outside the band have $\alpha_i = 0$, so only the support vectors shape the boundary.
3. Because the dual sees the data only through dot products, any kernel with positive semi-definite Gram matrices can replace them; the RBF kernel's $\gamma$ sets each point's reach.
4. Kernel ridge solves $\alpha = (K + \lambda I)^{-1} y$ in one linear system but keeps every training point; standardise first, and approximate the kernel when $n$ is large.
5. A tree picks each split by the largest drop in weighted impurity; a split that copies the parent's proportions gains nothing.
6. An unlimited tree learns the noise, a short one is readable but unstable, and impurity-based importance favours variables with many thresholds.

Glossary

Support vector machine (SVM)

A classifier that keeps the boundary with the widest margin, softened by a price on violations.

Support vectors

The training points on or inside the margin; the only ones with a non-zero dual weight.

Hinge loss

The loss $\max(0, 1 - y f(x))$, zero for a point on the right side with a lead of at least 1.

Kernel trick

Replacing every dot product by a kernel, a dot product in a larger space computed without building it.

Gram matrix

The $n \times n$ matrix of kernel values on all pairs; positive semi-definite for a valid kernel.

Kernel ridge regression

Ridge in dual form with a kernel, one weight per training point.

Decision tree

A model of nested threshold questions on one variable at a time; each leaf is a box of the input space.

Gini impurity

The quantity $1 - \sum_k p_k^{2}$, the chance that two points drawn from a node have different classes.

Cost-complexity pruning

Growing the full tree, then keeping the subtree that minimises training error plus a price per leaf.

Mean decrease in impurity (MDI)

A tree's built-in importance, biased towards variables with many thresholds.

The other notes of the course

One public summary per deck, in the order of the course.

Previous: A defensible baseline modelNext: Forests, boosting, honest comparison

1. IntroductionAI winters, jobs and method
2. ToolsKaggle, GitHub, Python: the tools
3. Session 1Project framing and least squares
4. Session 2Maximum likelihood and logistic regression
5. Session 3Gradient descent, ridge and lasso
6. Session 4Decision threshold and reproducible ML
7. HomeworkA defensible baseline model
8. Session 5Kernels, SVM and decision trees
9. Session 6Forests, boosting, honest comparison
10. Session 7SHAP, fairness, PCA and clustering
11. HomeworkA documented champion model
12. Session 8Neural networks, drift, conformal prediction
13. HomeworkA delivered machine learning project
14. Session 9Defending a machine learning project
15. ReferenceCredit default scoring project
16. ReferenceAsset returns: XGBoost and sentiment
17. ReferencePython code for every ML model
18. ReferenceDeep learning essentials
19. ReferenceOpen data ML projects by sector
20. ReferenceData and AI engineer handbook
21. ReferenceData engineering, SRE and cloud
22. ReferencePanorama of machine learning models

All the notes, as a reading list

Attention and transformers, step by step

About these notes

Written by the lecturer from the slides of the deck, as a public summary: the key ideas, the formulas and one worked example. The exercises, their solutions, the tests and the grading stay in the deck, for the students of the course.

Revision: 16 October 2026.