02 — Classical Models

This chapter covers six model families: linear regression, logistic regression, decision trees, k-nearest neighbours, support vector machines, and naive Bayes.

Each one gets the same three questions:

1. What is it actually optimizing?
2. What must be true of your data for that objective to make sense?
3. What visibly breaks when it isn’t true?

Two more topics fall out along the way. Regularization is the penalty that stops a model chasing noise. Generalized linear models are the framework that shows linear and logistic regression to be one machine with two settings.

The goal is to pick a family for a new tabular problem, state which assumption you are betting on, and name the failure mode before it reaches production.

Most classical ML interview questions are question 3 in disguise. “Why does L1 give sparsity?” asks whether you can read a constraint region. “Why not MSE for classification?” asks whether you can differentiate a composition.

This chapter derives the answers rather than listing them. Where it needs a result about features, it restates that result in a sentence and links to chapter 01 for the full derivation.

What goes in, what comes out, and the words used throughout

Every model here shares one input/output shape and one working vocabulary. Both are worth pinning down before any model appears.

Every model here does supervised learning: it is shown examples that are already labelled with the right answer, and it learns to produce that answer for examples it has not seen. The input and output are concrete.

TRAINING INPUT                          TRAINING OUTPUT
  X : a matrix, n rows x p columns        a fitted model — a set of numbers
      one row = one example                (weights, split thresholds, stored
      one column = one feature             points) that the model saved
  y : a vector of n true answers

SERVING INPUT                           SERVING OUTPUT
  x : one new row, p numbers              regression   -> y_hat, one real number
      (no label — that is the point)      classification -> a class label, and
                                            usually p_hat, a probability in (0,1)

So: a table of numbers goes in, one number per row comes out.

• A feature is one column of X. The target is y.
• Regression means the target is a real number — a price, a duration.
• Classification means the target is one of a fixed set of classes — spam or not, one of five tiers.
• n is always the number of rows and p is always the number of features. Every formula below uses those two letters that way.

The terms that recur in every section

These come up in six of the ten sections that follow.

Loss function. A formula that scores how wrong one prediction is.

Objective. The total loss summed over the whole training set. “Fitting” means searching for the weights that make the objective smallest.

Gradient descent. The standard way to run that search. The gradient is the vector of partial derivatives, one per weight, pointing in the direction that increases the loss fastest. Gradient descent computes it and steps the opposite way, over and over.

Convex. An objective is convex when it is bowl-shaped: draw a straight line between any two points on the surface and the line stays above the surface. That shape guarantees exactly one bottom, so gradient descent cannot get stuck anywhere else. Convexity is why some of the models below have a single right answer and others do not.

Overfitting. When a model memorizes the noise in the training rows, so it scores well on them and badly on new ones.

Bias and variance. Overfitting decomposes into two error sources. Bias is error from a model too rigid to represent the true pattern. Variance is error from a model so flexible that its fit moves a lot when you resample the training data. Making a model more flexible trades one for the other — that is the bias-variance tradeoff.

Hyperparameter. A knob you set before fitting rather than something the fit learns. Tree depth and penalty strength are hyperparameters; the weights w are not.

Cross-validation. The standard way to choose a hyperparameter. Repeatedly hold out a slice of the training data, fit on the rest, score on the held-out slice, and keep the setting with the best average score.

One more piece of notation, used from section 2 onward. X^T is the transpose of X: the same table with rows and columns swapped, so an n × p matrix becomes p × n. It appears constantly because X^T X is how you multiply a data matrix by itself in a way whose shapes line up.

1. Picking one

Which family do you reach for on a new problem? The answer fits in one flowchart, and the rest of the chapter justifies its branches.

Read the flowchart top to bottom: the first question is about the shape of your data, the second about its size, and the dotted arrow at the bottom is an override that ignores both. The three green boxes are the most common answers.

flowchart TD
    S{"Tabular data?"} -->|No, text| TXT["Linear SVM / logistic<br/>on TF-IDF"]
    S -->|No, images| IMG["Pretrained backbone<br/>+ linear head"]
    S -->|Yes| N{"n rows"}
    N -->|"under ~1,000"| SMALL{"Need a<br/>probability?"}
    N -->|"1k .. 10M"| GBDT["Gradient boosting<br/>the default"]
    N -->|"over ~10M"| LIN["Linear / logistic<br/>with SGD"]
    SMALL -->|Yes| LR["Regularized logistic"]
    SMALL -->|No| SVM["Kernel SVM"]
    GBDT -.->|"must explain<br/>every coefficient"| LR2["Regularized linear/logistic"]

    style GBDT fill:#2d6a4f,color:#fff
    style LR fill:#40916c,color:#fff
    style LIN fill:#40916c,color:#fff

The first question: is the data tabular?

Tabular means a rectangle of rows and columns — the shape described above. The other two shapes have settled answers, which is why the flowchart disposes of them immediately.

For text, the strong baseline is a linear support vector machine (SVM) or logistic regression on TF-IDF. TF-IDF stands for term frequency–inverse document frequency: a representation that gives each word a weight rising with how often it appears in this document and falling with how many documents contain it at all. Common words get small weights; distinctive ones get large weights.

For images, the answer is a pretrained backbone plus a linear head. You take a network already trained on a large image collection, freeze its learned representation, and fit only a small linear model on top of it.

The second question: how many rows?

For tabular data the branch is set by n, the number of rows.

Under roughly 1,000 rows, the next question is whether you need a probability.

• If yes, use regularized logistic regression. It emits a calibrated number in (0,1), meaning that among the cases it scores 0.30, close to 30% really are positive.
• If no, a kernel SVM is the stronger classifier in that regime.

Between about 1,000 and 10 million rows, gradient boosting is the default. That is an ensemble which fits many small trees in sequence, each one correcting the errors of the ones before it.

Above roughly 10 million rows, use linear or logistic regression fitted with SGD. SGD is stochastic gradient descent: gradient descent that estimates the gradient from a small random batch of rows at a time instead of all n, so it never needs the whole dataset in memory at once.

The override

The dotted arrow is the exception that ignores n entirely. When you must explain every coefficient to a regulator or a clinician, you step off gradient boosting and back to a regularized linear or logistic model no matter how many rows you have.

On tabular data, gradient boosting is the default and everything else needs a reason — small n, a hard interpretability requirement, an extreme latency budget, or a genuine need for calibrated extrapolation outside the training range (Decision trees). Boosting itself is chapter 03; this chapter is the base learners and the models that are not ensembles at all.

2. Linear regression: the fit

This is the one model whose fit can be written down in a line of algebra. The closed form raises two questions — when you can afford to use it, and why library code never computes it the way the formula is written — and both have exact answers.

Linear regression assumes the target is a weighted sum of the features plus noise:

y = Xw + e        w : the vector of p weights being learned
                  e : the noise, the part of y no weighted sum can explain

The objective is to minimize the sum of squared errors, written min_w ||y - Xw||^2. The notation ||v||^2 is shorthand for the sum of the squares of the entries of v — so ||y - Xw||^2 is exactly “add up the squared prediction errors over all n rows.”

Squared error is convex in w (bowl-shaped, per the definition above), so the one place the surface bottoms out is where the gradient is zero. Setting it to zero solves the problem outright, with no iteration:

d/dw ||y - Xw||^2 = -2 X^T (y - Xw) = 0    ->    X^T X w = X^T y
w = (X^T X)^-1 X^T y

Two steps in that line are worth spelling out. The derivative -2 X^T (y - Xw) is the chain rule applied to a squared quantity: the outer square contributes the 2, and differentiating y - Xw with respect to w contributes the -X, which lands transposed so the shapes match. Then dropping the -2 (zero divided by anything is still zero) and multiplying out X^T y - X^T X w = 0 gives X^T X w = X^T y. Multiplying both sides by the inverse of X^T X isolates w.

Those are the normal equations, and their solution is called ordinary least squares (OLS). Because they solve for w in one shot rather than stepping toward it, linear regression is the only model in this chapter with no iteration and no learning rate.

The formula on actual numbers

Three rows, one feature plus an intercept column of ones — small enough that every symbol above becomes a table you can multiply by hand.

        [1  1]          [2]
X   =   [1  2]    y  =  [4]        (column 1 = intercept, column 2 = the feature)
        [1  3]          [7]

X^T X = [3   6]         X^T y = [13]
        [6  14]                 [31]

solve  [3  6][w0]   [13]     ->   w0 = -2/3,  w1 = 5/2
       [6 14][w1] = [31]

predictions:  -0.667 + 2.5·1 = 1.833      -0.667 + 2.5·2 = 4.333
              -0.667 + 2.5·3 = 6.833
residuals:    +0.167, -0.333, +0.167      they sum to 0, as OLS forces

The residuals summing to zero is not a coincidence — it is the first normal equation. The row of X^T (y - Xw) = 0 belonging to the intercept column says exactly “the residuals sum to zero,” and the row belonging to the feature column says “the residuals are uncorrelated with that feature.”

Closed form vs SGD, decided by arithmetic

The closed form is not always affordable. Which method wins is decided by counting operations, not by taste.

The comparison is between solving the normal equations directly and running stochastic gradient descent. One term in the table needs fixing first: an epoch means one full pass over all n rows.

Read the table row by row. The first row is the one that decides most cases — notice that p appears squared and cubed on the left but only linearly on the right.

Two terms from that table need glosses. QR and SVD are two numerically safer ways to solve the same least-squares problem without ever forming X^T X; SVD is the singular value decomposition, and the reason to prefer either is derived in the next subsection. The p × p matrix X^T X is the Gram matrix, the table of inner products between every pair of feature columns, and it is the object that has to fit in memory.

Now hold n fixed at a million and vary p, using 8 bytes per float64 number. The decision makes itself:

n = 1e6, p = 100      X^T X: 1e10 flops, 80 KB memory     ->  closed form, seconds
n = 1e6, p = 10,000   X^T X: 1e14 flops, 800 MB           ->  borderline
n = 1e6, p = 100,000  p^2 · 8 bytes = 80 GB                ->  SGD is the only option

Check the middle line so the pattern is visible. Flops are n · p^2 = 1e6 · (1e4)^2 = 1e14. Memory is p^2 · 8 = 1e8 · 8 = 8e8 bytes, which is 800 MB. Now raise p by one more factor of ten: memory goes to 80 GB, and no amount of patience fixes that.

The crossover is set by p, not n — n enters linearly in both methods, p enters cubically in one of them.

Why nobody actually computes the inverse

Even when the closed form is affordable, writing it out literally destroys the answer. The reason is a property of finite-precision arithmetic, not of statistics.

Three definitions, then the arithmetic.

Condition number. kappa(X) measures how much a matrix amplifies small errors in its input. A large condition number means the columns of X are nearly redundant, so the solution is delicately balanced and a tiny wobble in the data swings it a long way.

Float64. The 64-bit binary floating-point format that NumPy, pandas, and every BLAS routine use for real numbers by default. It carries about 16 significant decimal digits.

Machine epsilon. The smallest relative rounding error a format can represent. For float64, eps ≈ 2.2e-16 — which is just another way of saying “16 digits.”

The two facts that combine: forming X^T X squares the condition number, kappa(X^T X) = kappa(X)^2, and the relative error in a solve grows like kappa · eps. So take a matrix with kappa(X) = 1e8, which is unremarkable for real wide data:

kappa(X) = 1e8  ->  normal equations: 1e16 · 2.2e-16 ≈ 2.2   no digits survive
                ->  via QR, kappa stays 1e8: 2.2e-8          8 digits survive

Read the first line as: squaring 1e8 gives 1e16, and 1e16 × 2.2e-16 = 2.2. A relative error of 2.2 means the computed answer is 220% off — further from the truth than simply returning zero would have been. The second line never squares anything, so 1e8 × 2.2e-16 = 2.2e-8 and eight digits survive.

QR factorization avoids ever forming X^T X and therefore never squares the conditioning. That is the whole difference. It is why np.linalg.lstsq and sklearn’s LinearRegression use SVD, and why inv(X.T @ X) @ X.T @ y is a code-review finding rather than a style preference.

3. Linear regression assumptions, and what actually breaks

The closed form in Linear regression the fit says how the weights are computed; it says nothing about whether they mean anything. That depends on a list of assumptions the model is making on your behalf — a list that is usually recited, when what matters is the last column of the table below: does the violation move the coefficients, or only their error bars?

Three terms in the table need defining before it can be read.

Exogeneity. The requirement that the noise is unrelated to the features. Knowing X tells you nothing about which way the error points. Written E[e | X] = 0, where E[...] means “average value of” and the bar means “given” — so: whatever the features are, the average error is zero.

Homoscedastic. Errors whose spread is the same everywhere. Heteroscedastic errors fan out instead, typically getting larger for larger predictions — think of predicting house prices, where a $2M house misses by more dollars than a $200k house.

Standard error (SE). The estimated standard deviation of a fitted coefficient: how much that number would bounce around if you refit on a fresh sample. Every p-value and confidence interval is computed from it.

Four more terms appear in the middle column of that table.

Residual. The gap between an observed y and the model’s prediction for it. So “residuals show curvature” means the errors bend systematically — all positive in the middle, all negative at the ends — instead of scattering randomly.

Autocorrelation. Consecutive errors being related. It is the norm in time series, where a bad month is followed by another bad month. It makes the data carry less independent information than its row count suggests, which is why the standard errors come out too small: the model thinks it has n independent observations when it effectively has far fewer.

CLT. The central limit theorem: averages of many independent terms tend toward a normal distribution regardless of the shape of the individual terms. That is why normally distributed errors stop mattering once n is large — the coefficient estimates are themselves averages, so they go normal even when the errors are not.

Minimum-variance. In the homoscedasticity row, “OLS is no longer minimum-variance” means some other unbiased estimator would give you tighter error bars on the same data. OLS still lands on the right answer on average; it just stops being the most efficient way to get there. t/F inference in the next row refers to the t-tests and F-tests that produce a coefficient’s p-value.

Collinearity. One feature being a linear combination of others. If it is exact, X^T X is singular — it has no inverse — and infinitely many weight vectors fit the data equally well, so there is no unique answer to return.

Now the takeaway from the last column:

Only the first two assumptions break the coefficients. The rest break only the standard errors.

That distinction tells you what to do, and the answer depends entirely on what you are using the model for.

• If you are predicting, heteroscedasticity and autocorrelation cost you a little efficiency and nothing else. Ignore them.
• If you are making a claim about an effect size, they invalidate the p-value. Use HC3 robust or Newey-West standard errors — two recipes that recompute the SEs from the observed residual pattern instead of assuming constant, independent noise. Both leave the coefficients themselves untouched, which is exactly what the table’s last column predicts.

Multicollinearity, quantified

Perfect collinearity is rare. Near-collinearity is everywhere, and it has a closed-form cost that tells you exactly how much to care.

The variance of a fitted coefficient is:

Var(beta_j) = sigma^2 / [ (n-1) · Var(x_j) · (1 - R_j^2) ]

Each symbol in that formula:

• sigma^2 is the noise variance — the variance of the error term e in y = Xw + e, the part of y that no linear combination of the features can account for. It is the same sigma^2 the homoscedasticity assumption above says is constant across rows.
• Var(x_j) is how much feature j itself varies. A feature that barely moves gives you almost no information about its own effect, which is why it sits in the denominator.
• R_j^2 comes from regressing x_j on all the other predictors. It is the fraction of feature j that the others can already reconstruct, running from 0 (fully independent) to 1 (fully redundant).

The last term is the one that matters here. Define the variance inflation factor:

VIF_j = 1 / (1 - R_j^2)          and the SE inflates by sqrt(VIF_j)

VIF is literally the multiple by which redundancy inflates that coefficient’s variance. Since a standard error is a standard deviation, it inflates by the square root. Substituting three values of R_j^2:

R_j^2 = 0.50 -> VIF   2 -> SE  1.41x        R_j^2 = 0.99 -> VIF 100 -> SE 10.0x
R_j^2 = 0.90 -> VIF  10 -> SE  3.16x

Check the last one: 1/(1 - 0.99) = 1/0.01 = 100, and sqrt(100) = 10. A feature that the others reconstruct 99% of gets an error bar ten times wider than it would have had on its own.

Here is what that looks like in a fitted model. These are illustrative figures — invented, but with the shape a real fit shows — for two features correlated at 0.998:

an ILLUSTRATIVE trace -- invented figures with the shape a real fit shows --
two features correlated at 0.998:
    coef(total_spend)     = +847.3  (SE 402.1)
    coef(spend_last_year) = -843.1  (SE 401.8)
    R^2 = 0.91, predictions fine, both t-stats ~2.1

Notice what is and is not wrong there. The two coefficients are enormous and nearly cancel: +847.3 and -843.1 sum to about 4. The model’s R^2 is a healthy 0.91 and the predictions are fine. The individual numbers are nonsense.

Collinearity does not hurt prediction at all — the fitted values are unaffected. It destroys the interpretation of individual coefficients. The data cannot separate two nearly identical directions, so the fit is free to put an enormous positive weight on one and cancel it with the other, and every such pair fits the data equally well.

Confirm it by refitting on a bootstrap sample — a resample of the same size drawn with replacement, used to see how much an estimate moves under resampling. The signs flip.

If you only need y_hat, ignore all of this. If you need to say “spend drives churn,” you cannot.

4. Regularization: why L1 zeroes and L2 does not

The single most-asked question about regularization is why one penalty drives coefficients to exactly zero while the other never does. It deserves two answers — a geometric one for intuition and an algebraic one for proof — but first, what regularization is.

Regularization means adding a penalty on the size of the weights to the objective, so the fit has to trade goodness-of-fit against weight magnitude.

The point is to combat overfitting. Unconstrained weights can grow large to chase noise in the training rows; a penalty makes that expensive.

The two standard penalties are named for the norm they use.

• L2, called ridge, penalizes the sum of squared weights.
• L1, called lasso, penalizes the sum of absolute weights.

lambda (the Greek letter lambda, written out because these files are plain text) sets how expensive weight is. lambda = 0 recovers plain OLS; large lambda crushes everything toward zero.

Each penalized objective has an equivalent constraint form: instead of paying for weight, you minimize the original error subject to the weights staying inside a region of size t. The two forms give the same solutions, and the constraint form is what makes the geometric argument below possible.

Ridge   min ||y - Xw||^2 + lambda·||w||_2^2         constraint form: ||w||_2^2 <= t
Lasso   min ||y - Xw||^2 + lambda·||w||_1          constraint form: ||w||_1  <= t

The L2 constraint region is a ball; the L1 region is a diamond (in higher dimensions, a cross-polytope) with corners on the axes. That difference is the entire story.

The geometric argument

The first derivation reads the two constraint regions as shapes and asks where a growing error surface first touches each of them.

The RSS — residual sum of squares, the ||y - Xw||^2 being minimized — has contours that are ellipses centered on the OLS solution. Each ellipse is a set of weight vectors that all produce the same error, and the ellipses grow outward from the unpenalized best fit at the center.

Picture the constraint region as a fixed shape sitting near the origin, and the ellipse expanding from the OLS point until it first makes contact. That first point of contact is the regularized solution: the lowest-error weight vector that is still legal.

The two figures below show that contact for each penalty, in two dimensions. w1 and w2 are the two weights. Note where the * lands: on the L2 ball it is a generic boundary point, on the L1 diamond it is a corner where w1 is exactly zero.

   L2 ball,  ||w||_2^2 <= t   --  a smooth boundary (ridge)

             w2
             |
        .----+----.
      ,'     |     `.
     /       |       *   <- the growing RSS ellipse touches
    |        |        |     a GENERIC boundary point: w1 =/= 0
 ---+--------+--------+--- w1
    |        |        |
     \       |       /
      `.     |     ,'
        `----+----'
             |


   L1 ball,  ||w||_1 <= t    --  corners sitting ON the axes (lasso)

             *   <- the ellipse touches AT the corner,
            /|\     where w1 = 0 exactly
           / | \
          /  |  \
         /   |   \
 -------+----+----+------- w1
         \   |   /
          \  |  /
           \ | /
            \|/
             +

Two terms are needed to say precisely what the pictures show.

Outward normal. The direction pointing straight out of the boundary at a given point. A touching ellipse must meet the boundary with its gradient pointing along that direction — otherwise it would still be cutting into the region and could shrink further.

Measure zero. The precise version of “infinitely unlikely.” A set so thin that a randomly drawn direction lands in it with probability zero, the way a randomly drawn point on a plane never lands exactly on a given line.

Now read the two pictures against each other.

Every point on the L2 ball is smooth, so it has exactly one outward normal. For the ellipse to touch down where w_1 = 0 — that is, at the very top or bottom of the circle, not at the * where the picture shows it landing — the RSS gradient there would have to be exactly axis-aligned. That is one direction out of a continuum of them: a measure-zero coincidence. Which is why ridge does not produce exact zeros in practice.

The L1 ball’s boundary has corners, and its top corner is a point where w_1 = 0 exactly. A corner is non-differentiable, so instead of one outward normal it has a whole cone of them. Every gradient direction lying anywhere inside that cone touches down on that same corner.

That is the asymmetry. The corner catches a whole fan of incoming directions; a smooth point catches exactly one.

So sparsity is not about the L1 ball being “pointy” in the aesthetic sense. It is that a non-differentiable point absorbs a full-dimensional set of gradient directions, while a smooth point absorbs a measure-zero set.

The picture generalizes past two dimensions. In p dimensions the L1 ball has 2p vertices — each one a point where a single coefficient is nonzero and every other is zero — plus faces of every dimension in between. So any level of sparsity, from one surviving feature to all of them, is reachable at some face.

The algebraic argument, which settles it

The geometric picture persuades. This one proves, by reducing the problem to one coordinate at a time and solving each in closed form.

The simplifying assumption that makes it tractable

The reduction needs an orthonormal design: the condition X^T X = I, meaning the feature columns are mutually perpendicular and each has unit length.

That condition is what makes the coordinates decouple. Normally every weight depends on every other weight, because correlated columns fight over the same signal. Under X^T X = I they do not, so each weight can be solved on its own.

Assume it, and write z_j = (X^T y)_j for the OLS solution in coordinate j. From here on z is the unpenalized answer for one coefficient, and the question is what each penalty does to it.

A convention that has to be stated

Both derivations below carry the same 0.5 in front of the squared-error term. That is deliberate: it makes the lambda in the ridge line the same lambda as in the lasso line, so the table at the end compares like with like.

Drop that 0.5 from the ridge line only — as the more common textbook spelling of ridge does — and ridge shrinks by z/(1 + lambda) while lasso still thresholds at lambda. Printing those two side by side under one heading compares two different penalty scales, and it is the easiest way to misuse this table.

Ridge, one coordinate

Minimize 0.5·(z - w)^2 + lambda·w^2.

Take the derivative with respect to w and set it to zero:

-(z - w) + 2·lambda·w = 0
-z + w + 2·lambda·w = 0
w·(1 + 2·lambda) = z
w_ridge = z / (1 + 2·lambda)

That is multiplicative shrinkage: divide by a constant greater than 1. Dividing a nonzero number by a finite constant never produces zero, which is the entire reason ridge cannot select features.

Lasso, one coordinate

Minimize 0.5·(z - w)^2 + lambda·|w|.

The problem is that |w| has no derivative at w = 0 — it has a sharp kink there. The tool for that is the subgradient: the set of slopes of all lines that touch the function at a point and stay below it. At a smooth point that set has one member and equals the ordinary derivative. At a kink it is a whole interval.

At w = 0 the subgradient of lambda·|w| is the entire interval [-lambda, +lambda], because every slope between the left arm’s -lambda and the right arm’s +lambda touches the V at its tip without crossing it.

Zero is therefore optimal whenever -z lands inside that interval, which happens when |z| <= lambda. Away from zero the kink is irrelevant and ordinary stationarity gives w = z - lambda·sign(z).

Putting both cases together gives soft thresholding:

w_lasso = sign(z) · max(|z| - lambda, 0)

In words: move every coefficient a fixed distance lambda toward zero, and if it would have crossed zero, leave it at zero. Substituting lambda = 0.5 into both rules:

Read the rows top to bottom. For the large coefficient z = 3.0, ridge cuts it in half while lasso barely touches it — losing 0.5 out of 3.0. For the small coefficients 0.5, 0.2 and -0.4, ridge keeps a shrunken nonzero value while lasso sets all three to exactly zero. Notice the reversal: ridge hurts big coefficients more, lasso hurts small ones more.

The one-line mechanism behind both columns: the L1 penalty’s gradient has constant magnitude lambda all the way down to zero, while the L2 penalty’s gradient is 2·lambda·w, which vanishes exactly as w approaches zero.

So L2’s pull toward the origin dies out precisely where it would need to be strongest. L1’s does not: it keeps pushing with the same force, drives small coefficients through zero, and the subgradient interval holds them there.

Each rule is one line of code. The assertions below reproduce the table exactly:

import numpy as np


def ridge_1d(z, lam):                      # 0.5*(z-w)**2 + lam*w**2
    return z / (1.0 + 2.0 * lam)


def lasso_1d(z, lam):                      # 0.5*(z-w)**2 + lam*abs(w), soft threshold
    return np.sign(z) * np.maximum(np.abs(z) - lam, 0.0)


z = np.array([3.0, 1.0, 0.5, 0.2, -0.4])
assert np.allclose(ridge_1d(z, 0.5), [1.5, 0.5, 0.25, 0.1, -0.2])
assert np.allclose(lasso_1d(z, 0.5), [2.5, 0.5, 0.0, 0.0, 0.0])
assert np.count_nonzero(ridge_1d(z, 0.5)) == 5      # ridge zeroes nothing

Note what ridge’s 0.100 costs you in production even though it is small: a column to compute at serving time, a dependency to keep alive, and a row in the model card. Sparsity is an engineering property, not only a statistical one.

Elastic net, and why correlated features need it

The lasso’s selection behaviour has a failure mode that shows up precisely when people most want to read the selection as a result. Elastic net is the fix.

Take two features that are perfectly correlated — say the same measurement in two units. The lasso objective is then minimized along a whole segment of the constraint boundary rather than at one point, because shifting weight from A to B costs nothing. The solution is not unique, and the solver picks a vertex essentially arbitrarily.

The block below shows what that looks like across 100 refits on resampled data. The counts are illustrative — a roughly even split follows by construction from the symmetry, not from a measurement.

ILLUSTRATIVE counts -- the split is roughly even by construction, not measured:

lasso,      100 bootstrap resamples:  A selected ~51x, B selected ~49x, both 0x
elastic net (l1_ratio 0.5):           both selected 100x, weights split ~50/50

The lasso line is the problem: it never keeps both, and which one it keeps is a coin flip. If you hand that output to a stakeholder as “the model selected feature A,” you have reported a coin flip.

Elastic net uses both penalties at once, with l1_ratio setting the mix. Adding an alpha·||w||_2^2 term makes the objective strictly convex — bowl-shaped with no flat directions anywhere — so no segment of equally good solutions can exist. The solution becomes unique, and correlated features share weight instead of one evicting the other. That shared-weight behaviour is called the grouping effect.

Use elastic net whenever the feature set has correlated blocks and you intend to read the selection as a finding.

The one place scaling is never optional

Every penalized fit inherits one hard prerequisite from the way the penalty is written, and skipping it silently changes which features survive.

The penalty applies to raw coefficient magnitudes, so it is unit-dependent. Work through what that means with one column measured two ways. The magnitudes below are illustrative — there is no fit behind them — but the unit arithmetic connecting them is exact.

income in dollars:     coefficient ~ 2e-5      (a small effect per single dollar)
income in $thousands:  coefficient ~ 2e-2      (the same effect, per 1000 dollars)

soft threshold at lambda = 1e-3:
    |2e-5| = 0.00002 <= 0.001   ->  zeroed, feature dropped
    |2e-2| = 0.02    >  0.001   ->  survives, shrunk to 0.019

The two coefficients differ by exactly 1,000 because the unit did: the same effect measured against a thousand-times-smaller unit is a thousand-times-bigger number.

Identical information, identical model, opposite selection decision — determined by a unit choice.

The fix is one line. Standardize before any penalized fit: replace each column by (x - mean)/sd so every feature has mean 0 and standard deviation 1, putting all coefficients on a comparable scale (Scaling which models care and exactly why).

One exception: exclude the intercept from the penalty. Shrinking it would encode an arbitrary claim that the mean response is near zero.

What has to be true for a penalized linear model to work. Everything Linear regression assumptions and what actually breaks requires, plus two more.

1. The features must be on comparable scales. Standardizing guarantees it. Skip it and selection becomes a function of measurement units, as just shown.
2. lambda must be chosen on data the model was not fitted on, by cross-validation. Training error falls monotonically as lambda goes to zero, so tuning lambda on training error always picks no penalty at all — reducing regularization to a no-op.

What interviewers probe: “Why does L1 give sparsity?” Give the subgradient version — |w| is non-differentiable at 0, its subgradient is the interval [-lambda, lambda], so zero is optimal for a whole range of gradients rather than a single value — then draw the diamond. Reciting “the corners touch the axes” without either mechanism invites a follow-up you cannot answer.

5. Logistic regression

Linear regression predicts a number; the natural next demand is a probability. Logistic regression is the standard answer for binary classification, and three things about it repay a close look: its particular S-shaped squashing function is a principled choice rather than a convenient one, fitting it with squared error fails for derivable reasons, and its coefficients are misread in almost every model readout.

Logistic regression takes the same linear score w·x that linear regression produces, squashes it into a probability, then fits the weights to maximize the likelihood of the observed labels — that is, it picks the weights under which the labels you actually saw were most probable.

input:   one row, p numbers
score:   w·x, any real number from -inf to +inf
output:  a single probability in (0,1) that the row is the positive class

Apply a threshold to that probability and the feature space splits into two regions. The surface between them — the set of points where the model is exactly undecided — is the decision boundary.

For logistic regression that boundary is a flat hyperplane (a flat surface one dimension lower than the space: a line in 2-D, a plane in 3-D). It has to be, because the model is undecided exactly where w·x = 0, and that equation describes a flat surface.

The link, and why it is the logit

You need a function mapping a real-valued linear score to (0, 1). Infinitely many S-shaped curves would do that, so the real question is why this particular one.

The answer is that the logit — the log of the odds — is not an arbitrary choice. It is the canonical link for the Bernoulli distribution in the exponential family. Three definitions unpack that sentence:

• The Bernoulli distribution is the coin-flip distribution over a 0/1 outcome, parameterized by one number p.
• The exponential family is a large class of distributions — normal, Bernoulli, Poisson, gamma and more — that all share one common algebraic form. Generalized linear models uses this class in full.
• The canonical link is the one function of the mean that this common form singles out. Every member of the family has one, and it falls out of the algebra rather than being chosen.

Picking the canonical link buys a concrete payoff. It is what makes the score equations — the equations saying the gradient of the log-likelihood is zero at the optimum — come out as X^T (y - p) = 0. That is residual times feature: exactly the same shape as the normal equations in Linear regression the fit.

Here is the link and its inverse:

logit(p) = log( p / (1-p) ) = w·x            p = sigmoid(w·x) = 1 / (1 + e^-(w·x))

Odds are the ratio of the probability of the event to the probability of its complement. So p = 0.5 is odds 0.5/0.5 = 1, and p = 0.9 is odds 0.9/0.1 = 9. Odds run from 0 to infinity, and taking their log stretches that to the full real line — which is exactly the range a linear score lives on.

The sigmoid is the inverse of the logit, running the other way: it takes any real number and returns a probability, mapping large negative scores near 0 and large positive scores near 1. Substituting w·x = 0 gives 1/(1+1) = 0.5, the undecided point that defines the decision boundary above.

Why not MSE — two mechanisms

Fitting a classifier by minimizing squared error is the natural thing to try, and it is wrong for two separate reasons. Both are about the optimization, not the statistics. (MSE is mean squared error, the average of (prediction - truth)^2.)

Reason 1: non-convexity

Set up the one-point case. The true label is y = 1, the score is z = w·x, the predicted probability is s = sigmoid(z), and the loss is L = (1 - s)^2. The one fact you need about the sigmoid is that its derivative is s' = s(1-s).

Differentiate twice with respect to z:

L'  = -2 s (1-s)^2
L'' = -2 s (1-s)^2 (1 - 3s)      negative -- CONCAVE -- whenever s < 1/3
                                 check: s=0.1 -> -0.113 ;  s=0.5 -> +0.125

Check the sign by hand. At s = 0.1, the factor (1 - 3s) = 0.7 is positive, so L'' = -2(0.1)(0.81)(0.7) = -0.113, negative. At s = 0.5, (1 - 3s) = -0.5 flips the sign, so L'' = -2(0.5)(0.25)(-0.5) = +0.125, positive. The switch happens at s = 1/3.

A negative second derivative means the surface curves downward — concave, the opposite of the bowl shape gradient descent relies on.

MSE over a sigmoid is non-convex exactly in the region of confidently wrong predictions (s < 1/3), which is the worst possible place for it. Gradient descent can stall on a plateau there instead of being pulled out of it.

Log loss has no such region. Log loss is the negative log-likelihood, -log(s) when the true label is 1, and its second derivative is L'' = s(1-s) > 0 everywhere. That gives convexity in z, and since z = w·x is affine in w (linear plus a constant, a transformation that preserves convexity), convexity in z gives convexity in w. One global optimum, no sensitivity to where you initialize.

Reason 2: the gradient vanishes where you need it most

A vanishing gradient is a gradient so close to zero that the update step barely moves the weights, so learning stalls.

Evaluate both losses at s = 0.01 with y = 1 — the model is as confidently wrong as it can get, and this is precisely the point you most want it to move:

log loss:  dL/dz = s - y       = -0.99
MSE:       dL/dz = -2s(1-s)^2  = -0.0196          50x smaller

Substituting: log loss gives 0.01 - 1 = -0.99. MSE gives -2(0.01)(0.99)^2 = -0.0196. The ratio is 0.99 / 0.0196 ≈ 50.

The cause is that the sigmoid’s derivative s(1-s) appears as a factor in the MSE gradient, and it is tiny in the saturated tails — saturated meaning the sigmoid has been pushed so far toward 0 or 1 that its slope is nearly flat. Log loss escapes this because -log(s) blows up exactly as s -> 0, and that blow-up cancels the vanishing derivative, leaving the clean residual s - y.

What this argument is not

It is not a claim that squared error is a dishonest way to score probabilities. The Brier score (MSE on probabilities) is a proper scoring rule, where a scoring rule is proper when it is minimized by reporting your true belief, so it cannot be gamed by shading your numbers.

So this is not a calibration argument. It is entirely about optimization geometry: MSE is a fine way to evaluate a probability and a bad way to fit one.

Reading the coefficients

A logistic regression’s coefficients do not mean what a linear regression’s coefficients mean, and the gap between those two readings is the most common error in a model readout.

• beta_j is the change in log-odds per unit of x_j.
• exp(beta_j) is the odds ratio: the multiplicative factor by which the odds change per unit.

Neither of those is “the change in probability.” Work an example to see why that matters. Take beta = 0.693, which is log(2), so exp(beta) = 2.0 and the odds exactly double:

beta = 0.693  ->  exp(beta) = 2.0  ->  the odds double

baseline p = 0.10:  odds 0.111 -> 0.222  ->  p = 0.182    (+8.2 points)
baseline p = 0.50:  odds 1.000 -> 2.000  ->  p = 0.667    (+16.7 points)

Follow the first line through. At p = 0.10 the odds are 0.10/0.90 = 0.111. Doubling gives 0.222. Converting back with p = odds/(1+odds) gives 0.222/1.222 = 0.182. So the probability moved 8.2 points.

Now the second line. At p = 0.50 the odds are 1, doubling gives 2, and 2/3 = 0.667. The same coefficient moved the probability 16.7 points — twice as far.

The odds ratio is constant across the range; the probability change is not. “Doubling the odds” moves a 10% risk to 18%, not to 20%. This is the single most common misstatement in a model readout, and catching it is a cheap credibility win.

Two more properties worth knowing

Non-collapsibility. Adding a genuinely independent covariate changes the odds ratios of the other features, which a linear model’s coefficients do not do. So logistic coefficients are not comparable across model specifications — an odds ratio of 1.4 in a three-feature model and 1.4 in a ten-feature model are not the same claim.

Complete separation. This is when some feature splits the classes perfectly, with no overlap at all. It sends the maximum-likelihood estimate — the MLE, the weight vector maximizing the probability of the observed labels — to infinity, because pushing that weight higher always improves the likelihood and nothing stops it.

You will recognize it in output as coef = 24.7 next to a ConvergenceWarning. Regularization fixes it by bounding ||w||, which is why you rarely see it in sklearn: LogisticRegression applies L2 by default with C=1.0, where C is the inverse of the penalty strength — so a smaller C means more regularization, the opposite direction from lambda.

What has to be true for logistic regression to work

1. The log-odds must be roughly linear in the features. The model can bend probability but not the score, so a genuine interaction or a U-shaped effect has to be entered as a feature you built yourself.
2. Observations must be independent, or the standard errors understate the uncertainty exactly as in Linear regression assumptions and what actually breaks.
3. Classes must overlap at least somewhat, since perfect separation has no finite solution.
4. The features you need must be present. An omitted confounder biases logistic coefficients as surely as it biases OLS coefficients.

What breaks when these fail: a wrong functional form shows up as systematically miscalibrated probabilities in one region of feature space rather than as a visibly bad fit. That is why it survives an accuracy check and only fails a calibration plot.

6. Decision trees

Trees abandon the linear score entirely and ask yes/no questions instead. That single change of form determines everything else about them: how a split is chosen, why they overfit for two independent reasons rather than the one usually cited, and two structural properties — no scaling required, no extrapolation possible — that no hyperparameter can alter.

A decision tree takes a row and routes it down a series of yes/no tests of the form “is feature j at most t?” until it reaches a leaf — a terminal node holding no test.

The prediction is whatever the training rows that landed in that leaf averaged (regression) or voted (classification).

Training is a recursive search. At each node: try every feature and every threshold, keep the split that most improves a purity score, then recurse into both children.

Split criteria

The purity score is what makes one split better than another. There are three standard ones, and they differ less than their reputations suggest.

Gini      G = 1 - sum_k p_k^2                    Entropy  H = -sum_k p_k · log2(p_k)
Variance  weighted MSE of the children (regression)

In both formulas p_k is the fraction of the node’s rows belonging to class k, and the sum runs over classes. Both classification criteria measure how mixed a node’s labels are, and both are zero when a node contains one class only.

• Gini impurity is the probability that two rows drawn at random from the node have different labels.
• Entropy is the average number of bits needed to encode a label drawn from the node. A 50/50 node costs a full bit; a pure node costs none.
• The gain from a split is the parent’s impurity minus the row-count-weighted average of the children’s impurities. Weighted by row count, so a split that purifies three rows is not credited the same as one that purifies three hundred.

Scoring two candidate splits by hand

The parent node holds 100 rows, 60 of them positive, so p = 0.6 for the positive class and 0.4 for the negative. Substituting into both formulas gives the parent impurity, and then two candidate splits are scored the same way.

G_parent = 1 - (0.6^2 + 0.4^2) = 0.480      H_parent = 0.971 bits

Split A:  left 50 (45+/5-)   right 50 (15+/35-)
  G:  0.5·0.180 + 0.5·0.420 = 0.300   ->  gain 0.180
  H:  0.5·0.469 + 0.5·0.881 = 0.675   ->  gain 0.296

Split B:  left 20 (20+/0-)   right 80 (40+/40-)
  G:  0.2·0.000 + 0.8·0.500 = 0.400   ->  gain 0.080
  H:  0.2·0.000 + 0.8·1.000 = 0.800   ->  gain 0.171

Trace one number so the rest are readable. Split A’s left child holds 45 positives and 5 negatives, so p = 0.9 and 0.1, giving G = 1 - (0.81 + 0.01) = 0.180. Its right child holds 15 and 35, so G = 1 - (0.09 + 0.49) = 0.420. Both children hold 50 of the 100 rows, so the weighted average is 0.5(0.180) + 0.5(0.420) = 0.300, and the gain is 0.480 - 0.300 = 0.180.

Now compare the two splits in words. Split A sends 45 of the 60 positives one way and leaves a 15/35 mix the other way. Split B carves off a perfectly pure block of 20 rows but leaves the remaining 80 exactly balanced at 40/40 — the worst possible state.

That is why B scores worse despite containing a pure child: a pure child is worthless if it comes at the price of a maximally mixed sibling.

Both criteria rank A above B, and that agreement is typical. Gini and entropy disagree on well under 5% of splits, so the criterion is not a hyperparameter worth tuning. Gini is the default because it avoids computing a logarithm for every candidate split. Entropy’s steeper curve near the class extremes makes it marginally more eager to isolate a pure region.

The same arithmetic in code. The comments carry the gini values computed above; the assertion is the ranking they produce.

import numpy as np


def gini(counts):
    p = np.asarray(counts, dtype=float)
    p = p / p.sum()
    return 1.0 - np.sum(p ** 2)


def weighted_child_gini(left, right):
    nl, nr = sum(left), sum(right)
    n = nl + nr
    return (nl / n) * gini(left) + (nr / n) * gini(right)


parent = gini([60, 40])                              # 0.480
gain_a = parent - weighted_child_gini([45, 5], [15, 35])   # 0.180
gain_b = parent - weighted_child_gini([20, 0], [40, 40])   # 0.080
assert gain_a > gain_b

Why trees overfit — and it is not just “unlimited depth”

Trees overfit through two mechanisms that operate independently, and the usual explanation captures only the second.

The diagram below traces both paths. They start at the same box — the node search — then fork left and right, and rejoin at the red box, the same failure. The orange box on the left branch is the one people miss.

flowchart TD
    A["At each node, search<br/>p features × up to n-1 thresholds"] --> B["Take the MAXIMUM gain<br/>over ~p·n candidates"]
    B --> C["Max of many noise draws<br/>is positive by construction:<br/>over 4 sd at p·n = 50,000"]
    C --> D["Every split looks informative<br/>even when nothing is"]
    A --> E["Each level halves the rows<br/>reaching a node"]
    E --> F["Depth 10 on n=1000<br/>-> ~1 row per leaf"]
    D --> G["Deep tree, zero training error,<br/>no generalization"]
    F --> G

    style C fill:#bc6c25,color:#fff
    style G fill:#9d0208,color:#fff

Mechanism 1: the search takes a maximum over many candidates

This is the left branch of the diagram, and it is the one people miss.

The node search takes the maximum gain over roughly p·n candidate splits — every feature crossed with every threshold. Now suppose no feature carries any signal at all. The individual gains are then just noise, scattered around zero. But you are not reporting an individual gain; you are reporting the largest of p·n of them, and the maximum of many noise draws is positive by construction.

Put numbers on it. At p = 50 features and n = 1,000 rows there are 50,000 candidates. The maximum of 50,000 draws from a standard normal lands over 4 standard deviations above zero — about 4.23 in expectation.

One warning about a formula you will see quoted for that number. sqrt(2·ln m) gives 4.65 at m = 50,000, but that is only the leading term of the Gumbel approximation and it overstates the expectation. The next term in the expansion subtracts; the corrected expansion gives 4.25, and direct simulation gives 4.23. Quote sqrt(2·ln m) as a ceiling, never as the mean. The argument here only needs “over 4.”

A tree does not need a real signal to find a “highly significant” split. It needs only enough candidates.

That is the same multiple-comparison mechanism you know from statistics — test enough hypotheses and some pass by luck alone. It is also why tree gain importance is biased toward high-cardinality features, meaning features with many distinct values and therefore many candidate thresholds to try (Feature selection).

Mechanism 2: the data runs out

This is the right branch, and it is the usual explanation.

Each level of the tree roughly halves the rows reaching a node, so a balanced leaf at depth d holds about n / 2^d rows. At n = 1,000 and d = 10 that is 1000 / 1024 ≈ 1 row per leaf — the box reading Depth 10 on n=1000 -> ~1 row per leaf.

A leaf holding one row is not an estimate; it is a memory of that row. So the prediction gets noisier exactly as the number of decisions needed to reach it grows.

Both branches arrive at the red box: a deep tree with zero training error and no generalization.

The four controls

Four hyperparameters push back on this, and they are not interchangeable — each one attacks a different part of the mechanism, which is what the middle column records.

Three things in that table need unpacking.

Greedy. The search takes the best split available right now, without looking ahead. That is why XOR defeats a depth cap. XOR is the exclusive-or pattern, where the answer depends on two features jointly and neither one alone carries any signal — think “the row is positive when exactly one of A and B is true.” Split on A alone and the classes stay 50/50 on both sides, so the split looks worthless and a pre-pruned tree stops before ever reaching the second split that would have paid off.

R(T) and |T|. In the ccp_alpha row, R(T) is the tree’s training error and |T| is its number of leaves. So the objective R(T) + alpha·|T| charges alpha in rent per leaf, and pruning removes any subtree not earning its rent.

Pre-pruning versus post-pruning. max_depth and min_samples_leaf stop the tree while it grows (pre-pruning). ccp_alpha grows the tree fully and then collapses subtrees (post-pruning).

ccp_alpha generally beats max_depth at the same effective size, because pre-pruning is greedy and post-pruning is not. The fully grown tree has already discovered the two-level interaction that a depth cap would have prevented it from ever reaching, so pruning gets to decide with that information in hand.

Two properties that follow from the split rule

Two of the most practically important facts about trees are consequences of the split form x <= t rather than separate design choices, which is why no hyperparameter can change either one.

No scaling needed. Splits are x <= t, and any transform that preserves order — a log, a square root, a change of units — moves the threshold but not which rows fall on each side, so the fitted tree is unchanged. That is derived in Scaling which models care and exactly why.

No extrapolation. Extrapolation is predicting outside the range of the training data. A tree’s prediction is a leaf mean — an average of rows it actually saw — so it is constant outside the training range no matter how far outside you go.

The cleanest case: train on a perfectly linear relationship and then ask for a point beyond the data.

train on x in [0, 10] with y = 2x
the highest leaf covers x in [9, 10];  its rows average y = 2 · 9.5 = 19.0
predict at x = 20:   tree -> 19.0  (that leaf's mean)      linear -> 40.0

Step through it. Trained on x in [0, 10], the topmost leaf covers the interval [9, 10] — the top tenth of the range, whichever split schedule produced it. Its rows sit at an average x of 9.5, so with y = 2x they average y = 19.0.

Ask for x = 20 and every test in the tree routes the row into that same top leaf, so the answer is 19.0. Ask for x = 2,000 and the answer is still 19.0. A linear model carries the slope out and returns 40.0, which is correct.

This is the reason trending features destroy tree models in production. A monotonically rising days_since_signup or cumulative_spend walks off the end of the training range within weeks of deployment, and the model flatlines — silently, with no error and no warning.

Fix it at the feature level: difference it, ratio it, or window it (Temporal features and lookahead leakage). No tree hyperparameter can help, because the flatlining follows from the split form itself.

What has to be true for a tree to work

1. The relationship must be well approximated by axis-aligned rectangles. Every split cuts perpendicular to one feature, so a boundary running diagonally through two features has to be approximated by a staircase, and each step costs depth.
2. The training data must cover the range you will predict over, because of the extrapolation result above.
3. You need enough rows per leaf for a leaf mean to be an estimate rather than a memory.

What breaks: diagonal structure produces a tree that is deep and unstable for no gain, and shifting feature ranges produce silent flatlining rather than an error.

7. kNN and the curse of dimensionality

k-nearest neighbours barely qualifies as a model, and that simplicity is what makes it the clearest lens on the curse of dimensionality: from first principles, distance stops carrying information as the number of features grows — and yet vector search over 1,024-dimensional embeddings works anyway. Both halves of that apparent contradiction are derived below.

k-nearest neighbours (kNN) has no training step at all. It stores the training rows. To predict for a new row it finds the k stored rows closest to it and returns their majority vote (classification) or their mean (regression).

Brute force costs O(n·d) per query, where d is the number of features.

A notation warning, because this section is the one place the chapter switches. Everywhere else the feature count is p. From here to the end of this section it is d, which is what the curse-of-dimensionality literature uses and what you will see in every paper on the subject. They are the same number.

KD-trees — k-dimensional trees, an index that recursively partitions space so most of it can be skipped during a search — give O(log n) per query in low dimensions. Above roughly d = 20 they degrade to a full scan. That degradation is the first symptom of the problem this section derives.

The arithmetic

The failure is not about compute. It is that “nearest” stops meaning anything, and two moments of a one-line distribution are enough to show it.

Set it up. Take n points drawn uniformly in [0,1]^d, the d-dimensional unit cube. Pick two of them and ask how far apart they are.

Work one coordinate first. The squared gap Z = (U1 - U2)^2 between two independent uniform draws on [0,1] has E[Z] = 1/6 and Var(Z) = 7/180.

Squared distance is the sum of d such gaps, one per coordinate, and they are independent. So means add and variances add:

E[D^2]  = d/6                sd(D^2) = sqrt(7d/180) = 0.197·sqrt(d)
relative spread = sd/mean = 0.197·sqrt(d) / (d/6) = 1.183 / sqrt(d)

Check the second line: sqrt(7/180) = 0.197, and dividing 0.197·sqrt(d) by d/6 gives 6 · 0.197 / sqrt(d) = 1.183/sqrt(d).

Relative spread is the standard deviation divided by the mean: how wide the distribution of distances is compared with how far apart points typically are. It is the quantity that matters here, because kNN needs distances to differ from each other, not to be large.

The mean grows like d while the standard deviation grows only like sqrt(d), so the ratio shrinks like 1/sqrt(d). The table below evaluates it. The first column is the spread of squared distance, straight from the formula; the second is the spread of the distance itself, which is what kNN compares. They are not alternatives — read both, and mind which one a claim refers to.

Why the second column is half the first

Compare the two columns at d = 100: 0.1185 and 0.0594, a factor of two to within a fraction of a percent. At d = 1,000: 0.0373 and 0.0187, again a factor of two. At d = 1 the relationship fails — 1.183 against 0.707, not the 0.592 that halving would predict.

The reason is the square root. D = sqrt(D^2), and differentiating a square root halves the relative change: dD/D = (1/2)·d(D^2)/D^2.

That is the delta method — the standard trick of approximating how a function of a random quantity varies by using its derivative at the mean. Like every derivative-based approximation, it holds only for small perturbations.

So the halving needs the wobble to be small. By d = 100 the spread is around 10%, small enough that the approximation is off by well under a percent. At d = 1 the spread is order 1, the approximation breaks, and the true value is sqrt(1/18)/(1/3) = 0.707 rather than the predicted 0.592. The rows carrying the argument are the large-d ones, and there the halving holds.

What the numbers mean for the algorithm

At d = 1,000 every pair of points is within about 2% of the same distance. That 2% is the table’s second column, 0.019 — the relative spread of the distance itself, not of its square.

Now ask what “nearest” means in a cloud that tight. The nearest of 4,000 such points sits only about 6% below the mean pairwise distance. The minimum of a distribution this concentrated is barely a minimum, so the word “nearest” stops carrying information — and with it goes the entire premise of the algorithm.

That ~6% is the number the whole section turns on, so here is the derivation.

1. Fix a query point. Its distances to the other 4,000 points are 4,000 draws from a distribution whose relative spread is 1.183/(2·sqrt(1000)) = 0.0187 — the second-column value for d = 1,000.
2. The expected minimum of 4,000 standard normal draws is 3.62 standard deviations below the mean.
3. So the nearest neighbour sits about 3.6 × 0.0187 ≈ 6.7% below the mean distance.

The normal approximation in step 2 runs a little high, because the left tail of a distance distribution is thinner than a normal’s. Simulating 4,000 points in [0,1]^1000 directly gives 6.3-6.4%. Call it 6%.

The trap inside that derivation, which this chapter fell into once already. Do not substitute sqrt(2·ln 4,000) = 4.07 for the 3.6. That expression is the leading Gumbel term and it overstates the expected extreme; using it turns the answer into 7.6% and puts you 20% off. It is the same error as reading sqrt(2·ln 50,000) = 4.65 as the expected maximum split gain in Decision trees, where the truth is 4.23.

Three more calculations say the same thing from different angles. Each is a different way of noticing that high-dimensional space is almost entirely empty and almost entirely boundary. The lines to stare at are the d=100 ones.

Neighborhood size.  Enclosing 1% of the volume needs edge length e = 0.01^(1/d):
    d=1 -> 0.010    d=10 -> 0.631    d=100 -> 0.955
    At d=100 a "local" neighborhood holding 1% of your data spans 95.5% of the
    range of EVERY feature. Nothing about it is local.
Where the mass lives.  Fraction of a unit ball in the outer 10% shell = 1 - 0.9^d:
    d=10 -> 65%     d=100 -> 99.997%    every point is on the boundary
Sample requirement.  At fixed density n scales like k^d: matching 100 points
    in 1-D requires 100^10 = 1e20 points in 10-D.

Why vector search works anyway

The arithmetic above should make approximate nearest-neighbour search over 1,024-dimensional embeddings sound impossible. It works in production every day. Explaining that contradiction is the point of this subsection.

Two definitions first. An embedding is a learned vector representation of an item — a document, a product, an image — placed so that similar items land near each other. ANN (approximate nearest-neighbour) search is the technique of finding a query’s closest embeddings without scanning all of them.

The resolution: real embeddings do not fill their ambient space. They lie on a much lower-dimensional manifold, and the concentration arithmetic depends on the intrinsic dimension, not the ambient one.

• The ambient dimension is the length of the vector — 1,024.
• The intrinsic dimension is how many independent directions the data actually varies along.
• A manifold is the lower-dimensional surface the data is confined to. A sheet of paper crumpled inside a room is two-dimensional data living in a three-dimensional ambient space; nothing about its being in a room makes it three-dimensional.

Uniform points in [0,1]^1024 would defeat any index, exactly as the table predicts. Embeddings with an intrinsic dimension of 10-30 do not, because the d in 1.183/sqrt(d) is the intrinsic one. That is the reconciliation between this section and Embeddings and why dense search misses err_4021.

Making kNN work in practice

Four steps, in this order, each fixing something derived above.

1. Standardize first. Rescale every column to mean 0 and standard deviation 1 (Scaling which models care and exactly why). Skip it and the feature with the largest raw units dominates every distance, so you have a one-feature model wearing a kNN costume.
2. Reduce dimension, for the concentration reasons just derived.
3. Choose k by cross-validation. Small k gives low bias and high variance: each prediction follows a handful of neighbours closely and moves a lot when they change. At the other extreme k = n collapses to returning the global mean for every query.
4. Distance-weight the votes, so a neighbour twice as far away counts less than one right next door.

What has to be true for kNN to work

1. Distance in your feature space has to mean similarity in the target. That requires both a sensible scaling and a modest number of informative features. Irrelevant features add noise to every distance and are never voted out, because kNN has no mechanism at all for ignoring a column.
2. The training set must be dense enough that the k nearest rows really are nearby.

What breaks: past roughly 20-30 features, distances concentrate as derived above and the neighbours returned are effectively arbitrary. The model keeps returning confident answers the whole time, which is why this failure is easy to miss.

8. SVM

Where kNN trusts every nearby point equally, the support vector machine trusts only the difficult ones. The whole model unfolds from a single idea — a separating gap as wide as possible — and out of that idea come a property that makes it behave unlike every other model here, a trick you can verify by hand, and the reason the family lost its default status without losing its niche.

A support vector machine (SVM) is a classifier that draws the decision boundary as far as possible from the nearest training points of either class, rather than merely somewhere that separates them.

The margin, derived

The whole model follows from writing “as far as possible” down precisely. Four steps.

Step 1: label the classes -1 and +1. This is a convention, not a result, and it exists to make the next step compact.

Step 2: write down “correctly classified with room to spare” as y_i·(w·x_i + b) >= 1. Because y_i is -1 or +1, that product is positive exactly when the score has the same sign as the label. Requiring it to reach 1 rather than 0 demands a unit of slack, not just a correct side. Here b is the intercept.

Step 3: measure the distance from a point to the boundary. The boundary is the flat hyperplane w·x + b = 0, and the distance from a point to it is |w·x + b| / ||w||. Combined with step 2, the closest points sit at distance 1/||w||, so the margin — the total width of the empty corridor, counting both sides — is 2/||w||.

Step 4: maximize that. Maximizing 2/||w|| is the same as minimizing ||w||, which for convenience is written as minimizing 0.5·||w||^2 (same minimizer, nicer derivative).

min  0.5·||w||^2       s.t.  y_i·(w·x_i + b) >= 1                    hard margin
min  0.5·||w||^2 + C·sum_i xi_i    s.t.  y_i·(w·x_i + b) >= 1 - xi_i  soft margin

The first line is the hard margin. It demands the corridor be completely empty, which is impossible whenever the classes overlap at all — and real classes always overlap.

The second line is the soft margin. It adds a slack variable xi_i >= 0 per point (xi is the Greek letter xi), which is the amount by which that point is allowed to violate the corridor, and then charges C per unit of violation.

C is therefore the price of a violation, and it is the inverse of a regularization strength. Large C makes violations expensive, approaches a hard margin, and overfits. Small C buys a wide margin at the cost of tolerating more violations.

Hinge loss, and the property that defines the model

Rewriting the soft-margin objective as a per-point loss exposes the one behaviour that separates an SVM from every other classifier in this chapter. Compare the two lines below, where f(x) = w·x + b is the score:

hinge     max(0, 1 - y·f(x))          exactly ZERO once the margin exceeds 1
logistic  log(1 + e^(-y·f(x)))        never zero, always positive

The difference is the max(0, ...). Once a point is correctly classified with y·f(x) > 1, the expression inside goes negative and hinge loss clips it to exactly 0. Logistic loss never reaches zero — at y·f(x) = 5 it is still log(1 + e^-5) = 0.0067, small but nonzero.

Because hinge loss is identically zero for comfortably-correct points, the solution depends only on the support vectors — the points on or inside the margin. They are the only ones with nonzero loss, so they are the only ones exerting any pull on the boundary.

The consequence is stark: add a million more easy, obviously-correct points and the SVM boundary does not move at all. A logistic regression boundary does move, because every one of those points still contributes some gradient. That is the sharpest one-line contrast between the two models.

The kernel trick, computed

An SVM as written is linear. The kernel trick is how it becomes nonlinear without paying for the nonlinearity.

It rests on one structural fact. The dual form of the optimization — the equivalent problem written in terms of one weight per training point rather than one per feature — involves the data only through inner products x_i · x_j. The individual coordinates never appear; only the pairwise dot products do.

A kernel K(x, z) is a function that returns the inner product of x and z after both have been mapped into some richer feature space, without ever building that space. So if you can compute K directly, you can replace every inner product with K(x_i, x_j) and never construct the feature map phi at all.

A degree-2 polynomial kernel in two dimensions makes this concrete. Expand the square and see what the terms turn out to be:

K(x, z) = (x·z + 1)^2
        = x1^2·z1^2 + x2^2·z2^2 + 2·x1x2·z1z2 + 2·x1z1 + 2·x2z2 + 1
        = phi(x) · phi(z)   with   phi(x) = (x1^2, x2^2, sqrt2·x1x2, sqrt2·x1, sqrt2·x2, 1)

Expanding the square produces exactly the terms of a dot product between two 6-dimensional vectors of squares, cross-products and originals, which is what the third line names. Verify the identity numerically with x = (1, 2), z = (3, 4), computing it both ways:

kernel:   x·z = 11    ->    K = (11 + 1)^2 = 144
explicit: phi(x) = (1, 4, 2.828, 1.414, 2.828, 1)
          phi(z) = (9, 16, 16.971, 4.243, 5.657, 1)
          dot    = 9 + 64 + 47.99 + 6.00 + 16.00 + 1 = 144.0        identical

Both routes return 144. The kernel route got there with a two-term dot product and one squaring; the explicit route needed a 6-dimensional map and a 6-term dot product.

At two dimensions that gap is nothing. It explodes with dimension. A degree-3 map on 1,000 features has C(1003,3) = 167,668,501 monomials to build and store, while the kernel is still one 1,000-length dot product followed by a cube.

The extreme case: RBF, K(x,z) = exp(-gamma·||x - z||^2), corresponds to an infinite-dimensional map, because the exponential’s series expansion contains every polynomial degree. RBF stands for radial basis function — the similarity it reports depends only on the distance between two points, decaying smoothly, with gamma setting how fast. “Working in a space you could not write down” is literally true here, not a flourish: the explicit phi has infinitely many components and the kernel evaluates in microseconds.

Why SVMs stopped being the default

The kernel trick avoids building the feature space. It does not avoid building the matrix of pairwise kernel values, and that matrix is what ended the family’s dominance.

The kernel matrix holds K(x_i, x_j) for every pair of training points, so it is n × n — it grows with the square of the row count, not with the feature count.

kernel matrix is n × n, training cost O(n^2) to O(n^3)
n =  10,000  ->  1e8 entries  =  0.8 GB      fine
n = 100,000  ->  1e10 entries =   80 GB      not fine

At 8 bytes per entry: 10,000^2 = 1e8 entries is 800 MB, which fits. Multiply n by ten and the matrix grows by a hundred, to 80 GB, which does not.

Kernel SVMs lost to boosted trees on tabular data because datasets outgrew n^2, not because the margin idea was wrong. Linear SVMs (liblinear, or SGD with hinge loss) skip the kernel matrix entirely, scale linearly in n, and are still excellent.

Where a kernel SVM still wins

The regime is p > n: more features than rows, with n in the low thousands. There the margin is a genuinely good inductive bias — a built-in preference that substitutes for data you do not have — and boosting has too little data to work with.

Concrete cases: high-dimensional biology (n = 200, p = 20,000), small well-separated image sets, and text with TF-IDF, where a linear SVM remains a top-tier baseline.

The cost of choosing one: no probabilities. An SVM outputs a signed distance from the boundary, and a distance is not a probability.

Platt scaling is the standard conversion. Fit a one-dimensional logistic regression that maps those signed distances to the observed 0/1 labels, then use it to translate any future distance into a probability. It bolts a probability layer onto a model that has none.

One trap in it: Platt scaling needs an extra internal cross-validation to fit. Otherwise the distances it calibrates on are the ones the SVM already saw during training, those distances are optimistically large, and the resulting probabilities come out overconfident.

What has to be true for an SVM to work

1. The classes must be separable with a reasonable margin in whatever space the kernel implies. That is the inductive bias you are buying: a good one when the true boundary really is a wide clean gap, a poor one when classes overlap heavily.
2. Features must be standardized. Both the margin and every distance-based kernel are unit-dependent in exactly the way Regularization why l1 zeroes and l2 does not described.
3. n must be small enough that an n × n matrix fits in memory.

What breaks: heavy class overlap forces C small and turns the model into an expensive linear classifier, and unscaled features make the RBF kernel respond almost entirely to whichever column happens to have the largest units.

9. Naive Bayes

Naive Bayes is built on an assumption known to be false in every real application — and it classifies well anyway. The reason is precise, and so are the circumstances in which it stops holding.

Naive Bayes takes a row of features, multiplies together the probability of each feature value under each class, weights by how common the class is, and picks the winner:

P(y | x) proportional to  P(y) · prod_j P(x_j | y)

In that formula, P(y) is how common the class is before you see anything, and prod_j P(x_j | y) multiplies together one probability per feature.

That product is only valid if the features are conditionally independent given the class: once you know the class, knowing one feature tells you nothing about another.

The assumption is false in every real application. “New” and “York” are not independent given the class — see one and you can bet on the other. So why does the model work?

The mechanism: argmax survives what calibration does not

The assumption breaks the probabilities badly while leaving the ranking of the classes intact. And the argmax — the class with the highest score, which is all a classifier actually reports — depends only on the ranking.

Here is that happening on a concrete case. A spam classifier sees three correlated tokens: free, free!!!, and FREE. Each has a likelihood ratio (LR) of 4 for spam, meaning the token is four times as probable in spam as in non-spam. They are one signal counted three times.

Compare what the truth would say against what naive Bayes says:

truth (one signal, LR 4):   posterior odds = 0.25 · 4    =  1.0   ->  p = 0.500
naive Bayes (LR 4^3 = 64):  posterior odds = 0.25 · 64   = 16.0   ->  p = 0.941

Read the pieces. The 0.25 is the prior odds — the odds of spam before seeing any token, here 1-to-4. Multiplying prior odds by the likelihood ratio gives the posterior odds, the odds after seeing the evidence. Converting back with p = odds/(1+odds) gives 1/2 = 0.500 on the first line and 16/17 = 0.941 on the second.

Naive Bayes multiplied the LR three times instead of once, so it used 4^3 = 64 where the truth is 4.

The posterior odds are wrong by a factor of 16. The probability moves from 0.50 to 0.94, a factor of 1.9. And the classification at threshold 0.5 is identical.

That is the whole explanation, and it generalizes. Correlated evidence inflates the magnitude of the log-odds, but it inflates it in the same direction the true evidence pointed. As long as the inflation does not reorder the classes — and it usually does not, because the dependence structure is similar within each class and largely cancels when you take the ratio — the argmax is unchanged.

The consequences are precise and asymmetric. They determine whether you may use the output number or only the label:

Monotone means the distortion preserves order, so ranking survives it. Isotonic regression is the standard fix: fit a step function, constrained only to be non-decreasing, from raw scores to observed frequencies on held-out data, and use it to translate scores into honest probabilities.

Smoothing is not optional

One structural weakness of the product form has nothing to do with independence, and leaving it unaddressed makes the model catastrophically brittle.

A token the model never saw in class y during training gets P(x_j | y) = 0. And a single zero factor annihilates the entire product — the other 200 tokens, however informative, are multiplied by zero.

Laplace smoothing fixes it by pretending every possible token was seen alpha extra times before any real data arrived:

P(w | y) = (count(w, y) + alpha) / (total_count(y) + alpha·V)

V is the vocabulary size, the number of distinct tokens the model knows. It appears in the denominator because you added alpha to each of V numerators, so you must add alpha·V to the denominator to keep the probabilities summing to one.

Substitute alpha = 1, V = 50,000, and a class with 1,000,000 total tokens. A never-seen word gets (0 + 1) / (1,000,000 + 50,000) = 9.5e-7 instead of 0 — small enough to count as evidence against, large enough not to be a veto.

One never-before-seen word should not be able to overrule 200 informative ones, and without smoothing it does.

The three variants

They differ only in what distribution they assume for P(x_j | y).

• Multinomial — token counts. The default for text.
• Bernoulli — presence or absence only. Better on very short documents, where a repeated word carries little extra information.
• Gaussian — continuous features, with one mean and one variance fitted per feature per class.

Why it is still worth knowing

Training is a single counting pass costing O(n · nnz), where nnz is the number of non-zero entries — for text, the number of words actually present in a document rather than the full vocabulary. It streams, it updates online, and it needs no iteration at all.

When the question is “40M documents, 10 minutes, what do you run first,” the answer is naive Bayes. It also gives you the baseline number every later model has to beat.

What has to be true for naive Bayes to work

1. Strictly, conditional independence. Practically, only that the dependence is similar enough across classes to cancel in the ratio — which is why it survives on text.
2. Every feature value you will meet must have nonzero estimated probability. Smoothing guarantees this.
3. You must be using the output as a label or a rank, not as a probability.

What breaks: heavily duplicated features push the score toward 0 or 1, and the model becomes confidently wrong at any fixed probability threshold while its accuracy still looks fine.

10. Generalized linear models

Linear regression, logistic regression, and several models not yet mentioned are one framework with three interchangeable parts. Saying so is what turns a list of models into a system — and the framework has two spots where practitioners most often go wrong.

The diagram below is that framework. Four boxes, left to right: the features get combined into one number, that number gets mapped onto the scale the response lives on, and a distribution around it generates y. Only the two coloured boxes change between models.

flowchart LR
    X["Features x"] --> ETA["Linear predictor<br/>eta = w · x"]
    ETA --> G["Inverse link<br/>mu = g^-1(eta)"]
    G --> D["Response distribution<br/>from the exponential family"]
    D --> Y["y"]

    style ETA fill:#40916c,color:#fff
    style G fill:#bc6c25,color:#fff

The three interchangeable components:

• A response distribution from the exponential family. This is what generates y around its mean.
• A linear predictor eta = w·x (eta is the Greek letter). It is the raw weighted sum, and it can be any real number from -inf to +inf.
• A link g(mu) = eta connecting the two, where mu (mu) is the mean of the response.

The inverse link g^-1 is the direction the diagram actually travels. It converts the unconstrained eta back into a legal mean: a probability in (0,1), a positive count, a positive cost. That constraint is the whole reason links exist — a weighted sum will happily return -3.2, and you cannot have -3.2 orders.

Two design choices, and it helps to keep them separate: choosing the distribution is choosing what kind of noise you believe in; choosing the link is choosing what scale effects are additive on.

Six standard combinations. The first two rows are models you already met in this chapter, so read those first to confirm the framework reduces to what you know.

Two entries in that table need a gloss. The identity link is no transformation at all, mu = eta, which is why the first row is ordinary linear regression. Softmax is the multi-class generalization of the sigmoid: it exponentiates each class score and divides by the total, producing k probabilities that sum to 1.

Why counts get a log link

Three reasons, all pointing the same way.

1. It guarantees mu > 0 for any eta, because exp of anything is positive. Counts cannot be negative.
2. It makes effects multiplicative, which is how counts actually behave. A campaign raises orders by 12%, not by 4.3 orders.
3. It keeps effects on a scale where a fixed coefficient means a fixed percentage, so the same coefficient is meaningful for a small store and a large one.

Now note what is not a reason, because this is a common confusion. The log is not the variance-stabilizing transform for a Poisson.

A variance-stabilizing transform (VST) is one that makes the spread of the response the same everywhere. It matters because most inference assumes constant noise.

The VST is given by ∫dmu/sqrt(V(mu)), where V(mu) is how variance depends on the mean. For a Poisson, V(mu) = mu, so the integral gives sqrt, not log. You can see the log fails directly: by the delta method Var(log y) ≈ 1/mu, which keeps shrinking as mu grows rather than staying constant.

The log is the VST for V(mu) ∝ mu^2, which is the sd = c·E[y] case that Log box cox and when a transform is doing real work derives — a different assumption, and an easy one to conflate with this one.

Offsets

When the quantity you care about is a rate rather than a count, the exposure has to enter the model as a fixed term rather than as something to be estimated.

Modeling claims per policy-year, put log(exposure) in with its coefficient fixed at 1, not as a free feature. That is called an offset.

Fixing the coefficient at 1 asserts that doubling exposure doubles expected claims, which is exactly what “rate” means. Estimate it instead and you are fitting an elasticity — a free percentage-response-per-percentage-change — that you did not intend to fit, and it will absorb signal that belongs to your real features.

Check overdispersion

Poisson assumes Var = mean. Real counts routinely violate that, and the violation corrupts every standard error in the model. Overdispersion is the name for variance exceeding the mean.

The diagnostic is the ratio of residual deviance (the model’s goodness-of-fit statistic) to degrees of freedom (n minus the number of fitted parameters). When the Poisson assumption holds, that ratio sits near 1.

Suppose it comes back at 4.2. Then:

SEs are understated by  sqrt(4.2) = 2.05
a reported t = 2.5 is really 2.5 / 2.05 = 1.22   ->  not significant

A t of 2.5 clears the usual threshold of 2 and a t of 1.22 does not, so this single ratio flips the conclusion on every borderline coefficient in the model.

The fixes: switch to negative binomial or quasi-Poisson, both of which let variance exceed the mean. For a mass of exact zeros plus a continuous positive tail — insurance pure premium, revenue per user — use Tweedie, a distribution built for exactly that shape.

What has to be true for a GLM to work

1. The response distribution must plausibly describe the noise.
2. The link must put effects on a scale where they really are additive.
3. Observations must be independent, and the generic linear-model requirements from Linear regression assumptions and what actually breaks all still apply — on the link scale, not the response scale.

What breaks depends on which one you got wrong, and the two failures look completely different:

• The wrong distribution leaves the coefficients roughly right and the standard errors badly wrong. That is the overdispersion case above.
• The wrong link biases the coefficients themselves, because it misstates the shape of the effect rather than its uncertainty.

11. Choosing, with the tradeoffs made explicit

Everything derived above now compresses into a lookup: every family in the chapter, side by side, on the dimensions that actually decide a choice.

The table is wide; scroll it. The columns that decide most real choices are Works at n, Interpretable, and Extrapolates. Bold entries are the ones that will surprise you or bite you.

Four abbreviations appear only here.

• GBDT is gradient-boosted decision trees, the ensemble from chapter 03.
• T is the number of trees in that ensemble, which is why it multiplies both the train and inference costs.
• LGBM and CatBoost are two GBDT implementations that accept categorical columns directly, without one-hot encoding them first.
• #SV is the number of support vectors an SVM kept. Prediction cost scales with it, which is why a model that keeps half its training set is slow at serving time.

“Native missing” means the model handles missing values itself rather than requiring you to fill them in first.

Reconciling this table with the flowchart in §1

Two rows look like they contradict Picking one. The difference is “feasible” versus “default.” This table’s Works at n column says what a family can still be trained on. The flowchart in §1 says what you should reach for first.

GBDT. This table says 1e3 to 1e8; the flowchart hands off to linear/SGD above ~10M rows. Both are correct. Boosting keeps working at 1e8 rows — it simply stops being worth the training hours once a linear model fitted by SGD gets close enough on the same data.

Kernel SVM. Three different numbers appear for it across the chapter, each answering a different question:

• The flowchart says under ~1,000 rows — that is where it is the default.
• Svm says “low thousands” — that is where it is still the best choice given p > n.
• This table says ~1e4 — that is where the n × n kernel matrix stops fitting in memory.

Read as one sentence: default under 1,000 rows, competitive into the low thousands, infeasible past roughly 10,000.

The pattern in the columns

“Interpretable” and “extrapolates” are the only pair of columns where one family scores top marks on both, and that family is linear and logistic regression. Trees match them on interpretability. Linear SVMs match them on extrapolation. Nothing else does both.

Two consequences follow directly. It is why linear and logistic regression survive in credit, insurance, and clinical settings that could easily afford boosting. And it is why a time-trending target is a linear-model problem no matter how tabular it looks — the extrapolation column, not the interpretability column, is what decides that one.

What interviewers probe: “You have 50,000 rows and 200 features, tabular, and you need it explainable to a regulator.” The junior answer picks one model. The senior answer is two: fit gradient boosting to establish the achievable ceiling, then fit a regularized logistic regression with the interactions the boosted model found, and report the accuracy gap explicitly as the price of interpretability. If the gap is 0.004 AUC — area under the receiver-operating-characteristic curve, the standard threshold-free measure of how well a classifier ranks positives above negatives — ship the linear model and you have the evidence for why.

Cheat sheet

Each row is a symptom you can observe, the mechanism from the section above that produces it, and the fix that follows from the mechanism.

The Nystroem approximation in the kernel-SVM row builds a low-rank stand-in for the n × n kernel matrix from a random subset of rows, which recovers most of the kernel’s benefit at linear cost.

The one thing to carry out of this chapter

Every model in this chapter is an objective plus a bet, and the bet is the part that decides whether minimizing the objective was worth anything.

OLS bets the target is a weighted sum of your columns. When that bet is wrong it pays in the coefficients themselves, not in the standard errors.

The penalties bet that most true weights are small — L2 that they are merely small, L1 that most are exactly zero. Which is why choosing lambda is stating a belief about your feature set, not turning a knob.

A tree bets the answer is a union of axis-aligned rectangles. That one bet buys scale-invariance and forbids extrapolation in the same breath: the same property that lets you skip standardizing is the property that flatlines the model on a trending feature.

kNN bets that distance means similarity, and loses that bet somewhere past thirty dimensions. By then every pair of points is nearly equidistant and “nearest” has stopped being a fact about the data.

The SVM bets there is a wide clean gap, and discards every point that is not near it. Which is why a million easy rows cost it nothing and heavy class overlap costs it everything.

Naive Bayes bets on an independence it demonstrably does not have, and survives because argmax is a coarser question than probability. It needs the ranking, not the number.

So the useful question about a new tabular problem is not “which model is best” but “which of these bets would I defend on this data.” Answer that and you have named your model and its failure mode in the same sentence.

Next: 03 — Ensembles & Boosting — why combining these base learners beats tuning any one of them.