Classical Supervised ML

01Intuition

Every model in this section answers the same question differently: what function shape am I allowed to draw through the data?

Start with the simplest possible answer: a straight line. Linear regression asks for the line (or, with more features, the hyperplane) that comes closest to every training point, where "closest" is measured by squared vertical distance. There's a unique best answer, it has a closed form, and every coefficient tells you exactly how much the prediction moves per unit change in a feature, holding everything else fixed.

That interpretability is the whole appeal, and the whole limitation. A straight line can't bend. So it can't represent a relationship where the effect of one feature depends on the value of another, unless you hand-build that interaction as a new column.

Now suppose the target is a class, such as spam or not spam. You could fit a straight line to 0/1 labels and threshold the output at 0.5, but that breaks immediately.

The raw output is unbounded. A very confident, very correct prediction (say, a score of 4.0 for an obvious spam email) gets penalized by squared error exactly as if it were wrong, because squared error has no idea that "greater than 1" isn't a meaningful direction to keep pushing.

Logistic regression fixes this by squashing the linear output through a sigmoid, which maps any real number into (0, 1) and reads naturally as a probability.

Once the output is a probability, cross-entropy becomes the natural loss in place of squared error. The reason is worked out in 01: cross-entropy is the maximum-likelihood loss for a class label, and it doesn't saturate the way squared error does when the model is confidently wrong. This page applies the same argument without re-deriving it.

Every other model in this page is a variation on "what's the function shape, and how do I fit it." A decision tree's shape is a set of axis-aligned rectangular regions, fit by greedily choosing the split that most improves purity. A support vector machine's shape is a linear boundary (or a nonlinear one, via the kernel trick) chosen to maximize the margin to the nearest points of each class.

A k-nearest-neighbors "model" barely has a function shape at all. It defers the decision to prediction time and asks the neighborhood what it thinks. Keep that framing running underneath everything below: same recipe, different function family, different way of fitting it.

The simplest learning algorithm fits a line. Here it is on five made-up students: hours studied against exam score.

import numpy as np

hours = np.array([1, 2, 3, 4, 5], dtype=float)       # hours studied
score = np.array([52, 55, 61, 64, 70], dtype=float)  # exam score

X = np.column_stack([hours, np.ones_like(hours)])    # slope and intercept
slope, intercept = np.linalg.lstsq(X, score, rcond=None)[0]
pred = slope * hours + intercept

print(f"score = {slope:.2f} x hours + {intercept:.2f}")
print("predictions:", np.round(pred, 1))
print("mean absolute error:", np.round(np.abs(pred - score).mean(), 2))
print("prediction for 6 hours:", round(slope * 6 + intercept, 1))

02Timeline

03The model zoo: how each one decides

Regularization, geometrically

Both linear and logistic regression are usually fit with a penalty added to the loss, because the unpenalized least-squares solution overfits whenever features are correlated or numerous relative to the number of examples. Ridge (L2) adds $\lambda \sum_j \beta_j^2$ to the loss; lasso (L1) adds $\lambda \sum_j |\beta_j|$. Both shrink coefficients toward zero as $\lambda$ grows, but they shrink differently.

Ridge shrinks every coefficient smoothly. Lasso can zero coefficients out entirely, performing feature selection as a side effect of fitting. The geometric reason is worked out in the "why" section below, and it is one of the most commonly asked interview questions on this page.

Polynomial regression and feature engineering

A straight line is a strict function-shape limitation, but it's a limitation you can partially engineer your way around: add $x^2$, $x^3$, or an interaction term $x_1 x_2$ as new columns, and linear regression on the expanded feature set can now fit curves and interactions. It's still linear in the parameters, which is all the closed-form solution requires.

The tradeoff is that you now choose which nonlinear terms to add by hand, and high-degree polynomial terms overfit badly outside the range of the training data: small differences in the fit near the training points can blow up into huge swings just past the boundary. This is the manual-feature-engineering step that tree-based models below make largely unnecessary.

Decision trees: splitting criteria and pruning

A decision tree builds its function shape by repeatedly asking the single best yes/no question about one feature, splitting the training data into two purer subsets, and recursing. "Best" is measured by how much a split reduces impurity. Two criteria dominate:

• Information gain. The drop in entropy, $H(p) = -\sum_i p_i \log p_i$. Literally how much less uncertain you are about the class label after the split.
• Gini impurity. $G = 1 - \sum_i p_i^2$, the probability that two randomly drawn examples from the node would be misclassified if you labeled them according to the node's class distribution.

They're both measuring "how mixed is this node," just with different curvature. In practice they usually produce very similar trees. Gini is marginally cheaper to compute (no logarithm) and is the default in most libraries, but the choice rarely changes the tree's structure or accuracy meaningfully.

Left alone, a tree will keep splitting until every leaf is pure. In the limit that means memorizing individual training points, including their noise. Pruning is the fix, and it comes in two forms.

Stop early (a max depth, a minimum number of samples per leaf, a minimum impurity decrease required to accept a split). Or grow the full tree and then cut back branches whose removal doesn't hurt validation performance (cost-complexity pruning). Either way, the goal is the same: trade a little training accuracy for a tree that generalizes.

Bagging and random forests

A single unpruned decision tree is a low-bias, high-variance model. It can represent almost any function shape, but small changes to the training data produce very different splits, especially near the root.

Bagging (bootstrap aggregating) tackles that variance head-on: train many trees, each on a different bootstrap resample of the training set (sample $n$ rows with replacement), and average their predictions (or vote, for classification). Averaging independent, unbiased estimators reduces variance without touching bias.

Random forests add one more ingredient: at every split, each tree is only allowed to consider a random subset of the features. This matters more than it looks, as the variance formula below shows.

Bootstrapping alone still tends to produce correlated trees. If one feature is unusually predictive, nearly every bootstrap sample will pick it as the very first split, so the trees end up structurally similar near the root and their errors stay correlated.

Boosting: sequential error correction

Boosting starts from the opposite end of the bias-variance spectrum. Instead of averaging many strong, independent, high-variance trees, it chains many weak, high-bias trees (often just a few levels deep) one after another. Each new tree is trained specifically to predict what the current ensemble is still getting wrong. Concretely, for regression with squared-error loss:

1. Start simple. An initial prediction $F_0$, often just the mean of the target.
2. Compute the residual for every training example, $r = y - F_0$.
3. Fit a new small tree to predict that residual, and not the original target.
4. Add a shrunk version of that tree's prediction to the running total, $F_1 = F_0 + \eta \cdot \text{tree}_1$, where $\eta$ (the learning rate) is typically small, 0.01 to 0.3.
5. Recompute the residual against the new, better prediction, and repeat.

Each round, the ensemble's remaining error gets a little smaller. And each new tree only ever has to solve the much easier problem of predicting what's left over.

XGBoost, LightGBM, CatBoost — and why gradient-boosted trees still win on tabular data

XGBoost (Chen & Guestrin, 2016) didn't reinvent gradient boosting so much as engineer it properly. Three changes carried the weight:

• A regularized objective that penalizes tree complexity directly, in addition to shrinkage.
• Native missing-value handling, learning a default split direction so imputation is not required.
• Systems-level optimization (parallel split-finding, cache-aware access patterns) to make it fast at scale.

LightGBM and CatBoost are later, actively used siblings. LightGBM is optimized for speed on very large datasets via histogram-based splitting, and CatBoost for datasets with many categorical features. All three are gradient boosting underneath and differ in engineering.

The deeper question interviewers want answered is why tree ensembles still beat deep neural networks on tabular data, years into the deep learning era. Three reasons, and they all point the same direction.

• No structure to exploit. Tabular features usually have no useful spatial or sequential structure. A CNN's convolution assumes nearby pixels are related; a Transformer's attention assumes tokens form a meaningful sequence. Column order in a spreadsheet is arbitrary, so those inductive biases have nothing to grab onto.
• Mixed types come free. Trees handle mixed feature types and missing values natively. A categorical column, a numeric column, and a sparsely-populated column all just become "is this value above/below/equal to some threshold." No embedding table or imputation pipeline required.
• The error-correction shape fits. Boosting's sequential error-correction is a very good structural fit for the kind of data tabular problems usually present: a moderate number of features with complex but relatively low-order interactions, exactly what a shallow tree can carve out a few splits at a time.

Support vector machines

An SVM's core idea is margin maximization. Among all the lines (or hyperplanes) that separate two classes, pick the one that leaves the widest possible street between the boundary and the nearest point of either class. Those nearest points are the support vectors. They're the only points that determine where the boundary sits, which is why the model can be so much sparser than it looks.

When classes aren't linearly separable, the soft-margin formulation allows some points to sit inside the margin or even on the wrong side, penalized by a cost. That gives you a tunable tradeoff between a wide margin and a few tolerated mistakes.

The kernel trick is what lets SVMs draw nonlinear boundaries without ever leaving linear machinery. Stated plainly: a kernel function computes the similarity two points would have if you'd projected them into some higher-dimensional space, without ever forming that projection. The SVM optimization only ever needs dot products between points, never the raw coordinates in that higher-dimensional space.

So you can substitute a kernel function for the dot product and get the effect of a much richer feature space at the computational cost of the original one.

k-NN and the curse of dimensionality

k-nearest-neighbors defers almost all of the work to prediction time. To classify a new point, find the $k$ closest training points and let them vote. There's no training phase to speak of, which makes it a clean lens for bias-variance intuition.

• Small $k$ (like $k=1$) lets the prediction follow every quirk of the single nearest point. Low bias, high variance, a decision boundary that snakes around individual noisy examples.
• Large $k$ averages over many neighbors, smoothing the boundary out, which gives higher bias and lower variance. In the extreme where $k$ equals the whole training set, the prediction collapses to always guessing the majority class.

The curse of dimensionality is what breaks k-NN in high-dimensional feature spaces. It is worth stating concretely. As the number of dimensions grows, the volume of the space grows so much faster than the data filling it that distances between points stop being informative.

For many common distance metrics, the ratio between the distance to the nearest neighbor and the distance to the farthest neighbor converges toward 1. Everything ends up roughly equidistant from everything else. "Nearest" stops meaning "similar" and starts meaning "arbitrary," and k-NN's entire premise quietly stops holding.

import numpy as np
rng = np.random.default_rng(0)

n = 500                          # 500 points, one query, unit cube
print("    d   nearest  farthest    ratio")
for d in [2, 5, 20, 100, 1000, 10000]:
    P = rng.random((n, d))       # (500, d) the "training set"
    q = rng.random(d)            # (d,)     the point to classify
    dist = np.linalg.norm(P - q, axis=1)    # (500,) one per point
    lo, hi = dist.min(), dist.max()
    print(f"{d:5d} {lo:9.3f} {hi:9.3f} {lo / hi:8.3f}")

print("\nshapes on the last row: P", P.shape, " q", q.shape,
      " dist", dist.shape)

Naive Bayes

Naive Bayes applies Bayes' theorem (see 01) to classification with one deliberate simplification. It assumes every feature is conditionally independent of every other feature, given the class. That assumption is almost always technically false. In a document, the word "loan" and the word "interest" are obviously not independent given the class "finance."

Combined with how cheap and stable it is to fit on high-dimensional, sparse bag-of-words features, that's enough to make naive Bayes a strong, fast baseline.

The perceptron — the bridge to everything in 04

The perceptron (Rosenblatt, 1958) is the historical hinge this whole page pivots on. It's a single linear classifier: weighted sum of inputs plus a bias, passed through a step function, trained with a simple rule that nudges weights toward misclassified points. Structurally it's almost identical to logistic regression.

It differs in two ways. Its output is a hard 0/1 decision and not a smooth probability, and its update rule is not derived from a loss gradient the way logistic regression's is.

Minsky and Papert showed in 1969 that a single perceptron can't learn XOR. It can only separate linearly separable data. That limitation is exactly why nobody stopped there. Stack perceptron-like units into layers, replace the step function with a smooth activation, and add backpropagation to train the whole stack. That's the multilayer perceptron, and it's where 04 (Neural Network Fundamentals) picks up the story directly from here.

04The equations

Least squares: the closed-form solution

Linear regression minimizes the sum of squared residuals, $\|y - X\beta\|^2$. Setting the gradient of that expression with respect to $\beta$ to zero and solving gives the normal equation:

• X the design matrix, shape (n_examples, n_features) — one row per training example, one column per feature (plus a constant column for the intercept).
• y the target vector, shape (n_examples,).
• β̂ the closed-form optimal coefficients — no iteration required, assuming $X^{\top}X$ is invertible.

Sometimes $X^{\top}X$ isn't invertible, or is too large to invert directly (many correlated features, or more features than examples). Then the same objective is minimized iteratively instead, by gradient descent on the mean squared error: $\nabla_\beta \text{MSE} = \frac{2}{n}X^{\top}(X\beta - y)$, followed by the usual $\beta \leftarrow \beta - \alpha \nabla_\beta \text{MSE}$ update. Same objective, two ways to reach the minimum.

Logistic regression: the sigmoid link

The linear part, $w^{\top}x + b$, is unbounded, exactly like linear regression's output. The sigmoid $\sigma$ is the link function that squashes it into $(0,1)$, so the output reads as a genuine probability. Fitting $w$ and $b$ minimizes cross-entropy between this predicted probability and the true label — see 01 for why that loss, specifically, is the right one and how its gradient behaves.

L1 vs. L2 regularization

• λ regularization strength — $\lambda = 0$ recovers plain least squares; larger $\lambda$ shrinks coefficients harder.
• Σβⱼ² the L2 (ridge) penalty — smooth, differentiable everywhere, shrinks every coefficient continuously toward zero.
• Σ|βⱼ| the L1 (lasso) penalty — has a kink at zero for every coefficient, which is exactly what makes it capable of setting coefficients to exactly zero and not just small. The geometric reason is in the next section.

05Why this shape

Why lasso gives you sparsity and ridge doesn't

Both penalties can be understood as the same constrained optimization: minimize squared error subject to the coefficients staying inside some budget region. The region just has a different shape for each.

• Ridge. The constraint $\sum_j \beta_j^2 \le t$ is a circle (a sphere, in higher dimensions).
• Lasso. The constraint $\sum_j |\beta_j| \le t$ is a diamond, with sharp corners sitting exactly on the coordinate axes. Those corners are the points where one or more coefficients are exactly zero.

Picture the unconstrained least-squares solution as the center of a set of elliptical contours of equal squared error, radiating outward. The regularized solution is wherever those growing ellipses first touch the constraint region's boundary.

A circle has no corners. So that first point of contact is, generically, some point on the smooth curve where every coordinate is nonzero. Coefficients get shrunk, but not zeroed. A diamond has corners sticking out right where an ellipse is likely to touch it first, and those corners are exactly the points where one or more coordinates are zero.

Geometrically, the elliptical contours are much more likely to first touch a pointy corner than a smooth curve is to touch anywhere in particular. So lasso routinely zeroes out coefficients entirely, and ridge, no matter how large $\lambda$ gets, almost never does. This is a common interview question because the geometric argument is short and visual, and you can either draw it or you can't.

import numpy as np
rng = np.random.default_rng(0)

n, d, lam = 60, 8, 12.0
X = rng.normal(size=(n, d))
X[:, 3] = X[:, 0] + 0.05 * rng.normal(size=n)   # a near-duplicate
beta = np.array([3., 0., 0., 0., -2., 0., 1.5, 0.])
y = X @ beta + 0.5 * rng.normal(size=n)

# Ridge is smooth everywhere, so there is no kink to land on.
ridge = np.linalg.solve(X.T @ X + lam * np.eye(d), X.T @ y)

# Lasso has no closed form. The max(., 0) below IS the diamond's
# corner: once a feature's pull drops under lam/2, it snaps flat.
lasso = np.zeros(d)
for _ in range(400):
    for j in range(d):
        rho = X[:, j] @ (y - X @ lasso + X[:, j] * lasso[j])
        pull = max(abs(rho) - lam / 2, 0.0)
        lasso[j] = np.sign(rho) * pull / (X[:, j] @ X[:, j])

print("X", X.shape, " truly nonzero:", np.flatnonzero(beta).tolist())
print("ridge:", np.round(ridge, 3) + 0.)
print("lasso:", np.round(lasso, 3) + 0.)
print("exactly 0.0  ->  ridge", int((ridge == 0).sum()),
      " lasso", int((lasso == 0).sum()))

Why boosting and bagging are fundamentally different moves

It's tempting to think of bagging and boosting as two flavors of "combine a bunch of trees." They're attacking opposite ends of the bias-variance tradeoff. Bagging starts from strong, low-bias, high-variance base learners (deep, largely unpruned trees) and averages many independent copies of them.

Averaging is a variance-reduction operation, and it does almost nothing for bias: if every individual tree is systematically wrong in the same direction, averaging them just reproduces that same systematic error.

That's precisely why random feature subsampling matters so much for bagging specifically. It's the mechanism that keeps the trees' errors decorrelated enough for averaging to keep paying off as you add more of them.

Boosting starts from weak, high-bias, low-variance base learners (shallow trees, sometimes just stumps) and chains them sequentially, each one targeting exactly the error the current ensemble hasn't explained yet. This is a bias-reduction operation, and the ensemble's representational capacity grows with every round, letting it fit relationships no single weak learner could capture alone.

The cost shows up when you stop regularizing. Unless you rein it in (small learning rate, limited tree depth, early stopping, row/column subsampling), boosting will keep driving training error toward zero by continuing to fit whatever is left, including noise. That's exactly the overfitting risk bagging mostly doesn't have. Adding more trees to a random forest almost never hurts. Adding more rounds to an unregularized boosted model eventually does.

import numpy as np
rng, n = np.random.default_rng(0), 200
x = np.sort(rng.random(n))
y = np.sin(4 * x) + 0.1 * rng.normal(size=n)   # the target curve

def stump(xs, rs, grid):     # depth-1 tree: one split, two means
    best = (np.inf, None)
    for t in np.quantile(xs, np.linspace(.05, .95, 19)):
        L = xs <= t
        a, b = rs[L].mean(), rs[~L].mean()
        sse = ((rs - np.where(L, a, b)) ** 2).sum()
        if sse < best[0]:
            best = (sse, np.where(grid <= t, a, b))
    return best[1]

# Bagging: 30 stumps on bootstrap resamples, averaged in parallel.
bag = np.array([stump(x[i], y[i], x)
                for i in rng.integers(0, n, (30, n))])

# Boosting: 30 stumps in series, each fitting what is left over.
F = np.full(n, y.mean())
for _ in range(30):
    F = F + 0.3 * stump(x, y - F, x)

print("bag members", bag.shape, " they disagree by",
      round(bag.std(0).mean(), 3))
for tag, p in [("one stump", stump(x, y, x)),
               ("bagged x30", bag.mean(0)), ("boosted x30", F)]:
    print(f"{tag:12s} MSE {((y - p) ** 2).mean():.4f}")

06Tradeoffs, failure modes, and choosing a metric

Failure modes

• Decision trees without pruning. Grown all the way out, a tree can carve a leaf for almost every training point and hit near-zero training error. That is memorization. Max depth, minimum samples per leaf, or cost-complexity pruning are the fix, and any of them trades a bit of training accuracy for real generalization.
• k-NN and the curse of dimensionality. In high-dimensional feature spaces, distances stop discriminating. The nearest and farthest neighbors become nearly equidistant, so the "nearest neighbors" carry almost no signal. Dimensionality reduction or a learned lower-dimensional embedding is usually required before k-NN is useful on anything but a small, carefully chosen feature set.
• Naive Bayes' independence assumption. It's almost always technically wrong, since features are rarely conditionally independent given the class. But classification only needs the correct class ranked first, and a calibrated probability is not required, so the model keeps performing well on tasks like text classification despite the wrong assumption underneath it.
• Data leakage. The single most common way a model looks great offline and fails in production. Two concrete examples:
  • Fitting a scaler or imputer on the entire dataset before splitting into train/test. The training statistics have already "seen" information from the test rows, quietly inflating validation performance.
  • Including a feature that's only populated after the outcome is already known. A "days since last late payment" column will look like an extremely strong predictor of default in historical data, but it isn't available at the moment you'd need to make the prediction.
  The fix is mechanical discipline. Fit every preprocessing step only on the training fold, inside the cross-validation loop, never before it. And audit every feature for whether it could plausibly exist at prediction time.

Choosing a metric

For classification:

• Precision. Of the things I flagged positive, how many were.
• Recall. Of the things that were positive, how many did I catch.
• ROC-AUC. Ranking quality across all thresholds, and a reasonable default.
• PR-AUC. Precision-recall AUC, which ignores true negatives entirely.

The tradeoff between precision and recall is a business decision as much as a modeling one. ROC-AUC can look deceptively good under severe class imbalance, because it's partly driven by the true-negative rate. When negatives vastly outnumber positives, even a mediocre model racks up a huge number of easy true negatives.

PR-AUC focuses on how well the model does specifically on the positive class, which makes it the honest choice whenever positives are rare: fraud, disease screening, defect detection.

For regression:

• MAE. Penalizes every error linearly, so it's robust to outliers but gives no extra urgency to large mistakes.
• MSE / RMSE. Penalizes errors quadratically, so a few large errors dominate the loss. (RMSE is the square root, back in the original units.) Appropriate when big mistakes are disproportionately costly, risky when a few noisy outliers shouldn't be allowed to dominate training.
• Huber loss. It is the compromise: quadratic for small errors and linear beyond a threshold, giving you MSE's smooth gradient near zero without MSE's outlier sensitivity far from it.
• MAPE. Mean absolute percentage error reports error as a percentage of the true value. Easy to communicate, but it behaves badly, or is undefined, when the true value is near zero.

07Build this

Boosting is easy to state and easy to misremember as "average a lot of trees". Watching a stack of stumps eat a residual, one stump at a time, is what makes the sequential part stick.

Where this runs in production

A typical fraud or credit-risk pipeline built on XGBoost has three moving parts:

• Engineer features from transaction and account history. Aggregations over recent activity, velocity features like "transactions in the last hour," categorical merchant and device fields.
• Train a gradient-boosted tree model on these features.
• Evaluate it knowing the positive class, actual fraud, is a small minority of all transactions.

Because positives are rare, ROC-AUC can look reassuringly high while the model is still missing most of the fraud that matters. It's partly propped up by the huge number of easy true negatives. PR-AUC is the honest metric here, because it only credits the model for how well it finds and ranks the rare positive cases.

Class imbalance itself is usually handled with a combination of three levers: class weighting (XGBoost's scale_pos_weight), threshold tuning against the actual business cost of a false positive (blocking a legitimate purchase) versus a false negative (missing real fraud), and sometimes resampling.

Leakage is easy to introduce by accident in a pipeline like this, and a feature derived from data only available after a chargeback is filed is a textbook example. Every preprocessing and feature-engineering step needs to be fit strictly inside the training fold, and audited for whether it could exist at the moment a real prediction has to be made.

08Interview questions

09Go deeper

●Now write it yourself

Reading the derivation and being able to produce it are different skills. These are Deep-ML problems that exercise what this page covers — each one is checked against real test cases, not multiple choice.

Matched to this page from Deep-ML's catalogue of 1,380 problems. More at deep-ml.com, and Where to practise covers the other platforms and what each one trains.

10Related pages