chapter 02 / classical-ml · estimated study time 120-150 min

Classical Machine Learning Algorithms
Four Worldviews of Classification

From Regression to Classification: A Seemingly Tiny Change

Chapter 1 predicted a continuous value (house price). Now we switch to predicting a category: Is this email spam or not? Is this tumor benign or malignant? The label $y \in \{0, 1\}$.

Can we just use linear regression and call anything $>0.5$ class 1? In theory yes, in practice terribly: ① the output range is $(-\infty, +\infty)$, with no probability interpretation—what does "predicted value 3.7" even mean? ② MSE also penalizes points that are "too correct," far from the boundary; a single extreme but correctly classified sample can drag the decision boundary out of shape.

We need two new parts: a function that squashes the output into a probability, and a loss function that matches probabilities. These two parts—sigmoid/softmax and cross-entropy—carry all the way to GPT: the pretraining loss of an LLM is exactly softmax + cross-entropy, only the number of classes goes from 2 to about 100,000 (each token in the vocabulary is one class). The derivations in this chapter are the direct foundation for Chapter 7.

Logistic Regression: Sigmoid and the Probability View

Keep the linear skeleton $z = \mathbf{w}^\top\mathbf{x} + b$ (this $z$ has a name you'll use for a lifetime: the logit), then wrap a squashing function around it:

$$\sigma(z) = \frac{1}{1 + e^{-z}}, \qquad \hat{p} = \sigma(\mathbf{w}^\top\mathbf{x} + b) = P(y{=}1 \mid \mathbf{x})$$

The sigmoid monotonically squeezes any real number into $(0,1)$: at $z=0$ it outputs 0.5 (maximally uncertain), and the larger $z$ is, the closer to 1. Its derivative has an elegant form (derivation: apply the chain rule to $\sigma(z)=(1+e^{-z})^{-1}$ and simplify):

$$\sigma'(z) = \sigma(z)\,(1 - \sigma(z))$$

Cross-Entropy Loss: Full Derivation

The loss function isn't picked out of thin air—it follows the maximum-likelihood route you learned in Chapter 1. A single sample $y \in \{0,1\}$ follows a Bernoulli distribution, and the two cases can be written together as a single expression:

$$P(y \mid \mathbf{x}) = \hat{p}^{\,y}\,(1-\hat{p})^{\,1-y}$$

The likelihood of the whole dataset is the product over all samples. Take the log (turning the product into a sum, without changing the optimum), then negate it to make it a "smaller is better" loss, and divide by $n$ to average:

$$L = -\frac{1}{n}\sum_{i=1}^n \Big[ y^{(i)} \ln \hat{p}^{(i)} + (1 - y^{(i)}) \ln (1 - \hat{p}^{(i)}) \Big]$$

This is Binary Cross-Entropy. A sanity check: if the truth is $y=1$, the loss is $-\ln\hat{p}$—as the prediction $\hat{p}\to 1$ the loss goes to 0, and as $\hat{p}\to 0$ the loss explodes to infinity. Unbounded penalty for confident mistakes—exactly the temperament a classification task wants.

Now for the gradient. Apply the chain rule with respect to $z$: $\frac{\partial L_i}{\partial z} = \frac{\partial L_i}{\partial \hat{p}}\cdot\frac{\partial \hat{p}}{\partial z}$. Substitute $\sigma' = \sigma(1-\sigma)$, and a string of seemingly complicated terms magically cancels (strongly recommend deriving this by hand once), leaving:

$$\frac{\partial L_i}{\partial z} = \hat{p}^{(i)} - y^{(i)} \qquad\Longrightarrow\qquad \nabla_\mathbf{w} L = \frac{1}{n}\sum_i \big(\hat{p}^{(i)} - y^{(i)}\big)\,\mathbf{x}^{(i)}$$

If you paired MSE with sigmoid for classification, what would go wrong with the gradient?

$\frac{\partial}{\partial z}\frac{1}{2}(\hat{p}-y)^2 = (\hat{p}-y)\cdot \sigma'(z) = (\hat{p}-y)\cdot\hat{p}(1-\hat{p})$. The extra factor $\hat{p}(1-\hat{p})$ goes to zero when $\hat{p}$ approaches 0 or 1—meaning the more confidently the model is wrong (e.g. $y=1$ but $\hat p \approx 0$), the closer the gradient is to zero, and it can barely learn. Cross-entropy cancels exactly this factor, so the more outrageous the error, the larger the gradient. This is the most vivid counterexample to "the loss function must match the output layer," and one of the reasons early neural networks trained so slowly.

Softmax: Generalizing to Multiclass

For $K$ classes, let the model output $K$ logits $z_1,\dots,z_K$, and normalize them into a probability distribution with softmax:

$$\hat{p}_k = \frac{e^{z_k}}{\sum_{j=1}^{K} e^{z_j}}, \qquad L = -\ln \hat{p}_{y}\ \text{(only penalize the probability of the correct class)}$$

A few details you must know in engineering practice:

• Numerical stability: $e^{z}$ overflows extremely easily. In implementation, first subtract the maximum value, $z_k - \max_j z_j$ (softmax is invariant to shifts, so the result is unchanged). Every deep learning framework does this internally.
• Temperature: $\hat{p}_k \propto e^{z_k / T}$. With $T>1$ the distribution flattens (more random), and as $T\to 0$ it degenerates to argmax. This is the mathematical essence of that temperature parameter you tune when calling an LLM API (sampling strategies are covered in detail in Chapter 9).
• The gradient is still $\hat{p}_k - \mathbb{1}[k{=}y]$—the third member of the "error × input" family.

Decision Trees: Carving Up the World with Questions

Switch to a completely different worldview: don't learn weights, learn a sequence of questions. "Area > 90㎡?" → Yes → "Age < 10 years?" → … Each internal node is one feature split, and each leaf is one prediction. It naturally handles nonlinearity, doesn't care about feature scale, and is human-readable.

How do we pick the "best question"?

Greedily pick the split that makes the child nodes purest. Two purity measures:

$$\text{Entropy: } H(S) = -\sum_k p_k \log_2 p_k \qquad\qquad \text{Gini: } G(S) = 1 - \sum_k p_k^2$$

Both are maximal when "all classes are evenly mixed" and 0 when "only one class remains." Information gain = the entropy of the parent node − the weighted average entropy of the child nodes; the CART algorithm uses Gini (no logarithm, so it computes faster), with results almost indistinguishable from entropy. The search over the split point $t$ is just this: for every candidate threshold of every feature, compute the weighted purity once and take the best—you'll see with your own eyes in the lab the rectangular patchwork boundary that this "axis-aligned splitting" draws.

Interactive Lab: Decision-Boundary Showdown

On the same data, three algorithms see completely different worlds. Logistic regression can only draw straight lines; kNN's boundary follows the data but is jagged and mottled; the decision tree only draws horizontal-and-vertical rectangles. Required experiments: ① compare all three on the two-moons data; ② let logistic regression fail spectacularly on XOR data (the limit of linear models, and the reason neural networks make their entrance in Chapter 3); ③ set tree depth to 12 to see overfitting, dial it back to 2 to see underfitting; ④ compare kNN at k=1 vs k=15 (variance vs bias).

Ensemble Learning: Random Forests and Gradient Boosting

Two scientific versions of "two heads are better than one," pointing in opposite directions:

Bagging → Random Forest: parallel, to reduce variance

Take $B$ bootstrap samples (sampling with replacement) from the training set, train one unpruned deep tree on each, and vote at prediction time. Averaging $B$ estimators each with variance $\sigma^2$ and pairwise correlation coefficient $\rho$, the variance becomes:

$$\rho\sigma^2 + \frac{1-\rho}{B}\sigma^2$$

The second term vanishes as $B$ grows, but the first term is stuck at $\rho\sigma^2$—the more correlated the trees are, the more limited the benefit of averaging. This is where the masterstroke of the random forest comes from: at each split, choose only from a randomly drawn subset of $\sqrt{d}$ features, forcing the trees to "think differently" from one another and pushing $\rho$ down. This is the mathematical expression of "diversity matters more than individual strength."

Boosting → Gradient Boosting: sequential, to reduce bias

Conversely, use a sequence of shallow trees (weak learners), each dedicated to correcting the residual errors of all the trees before it. The clever perspective at step $m$: treat the current model's prediction $F_{m-1}(x)$ as a "parameter," compute the negative gradient of the loss with respect to it $r_i = -\frac{\partial L(y_i, F)}{\partial F}\big|_{F_{m-1}}$, train a small tree to fit this negative gradient, then set $F_m = F_{m-1} + \eta \cdot \text{tree}_m$. Under MSE the negative gradient is exactly the residual $y - F(x)$, so the intuitive version of the story is "each tree learns the residual of the previous round"—but the negative-gradient view is why it's called "gradient boosting": it's doing gradient descent in function space.

XGBoost (2014) pushes this to its industrial extreme: a second-order Taylor expansion of the objective (Newton's method rather than plain gradient), L2 regularization on the leaf weights, automatically learning a default direction for missing values, histogram acceleration and parallelism. On small- to medium-scale tabular data, "XGBoost/LightGBM beats neural networks" remains a basic fact even in 2026—don't finish this course thinking everything is deep learning.

SVM: Maximum Margin and the Kernel Trick

Separable data has infinitely many separating lines—which is best? SVM's answer: the one that is farthest from the nearest samples on both sides—maximize the margin. The geometric derivation: the distance from a point to the hyperplane $\mathbf{w}^\top\mathbf{x}+b=0$ is $\frac{|\mathbf{w}^\top\mathbf{x}+b|}{\|\mathbf{w}\|}$; fixing $|\mathbf{w}^\top\mathbf{x}+b|=1$ at the support vectors, the margin is $\frac{2}{\|\mathbf{w}\|}$. Maximizing the margin is equivalent to:

$$\min_{\mathbf{w},b}\ \frac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.}\quad y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)} + b) \ge 1,\ \forall i \qquad (y \in \{-1,+1\})$$

A convex quadratic program, with a global optimum. Real data is noisy, so introduce slack variables $\xi_i \ge 0$ to let a few points cross the boundary, with the cost controlled by the hyperparameter $C$ (soft margin, 1995). After converting it into the dual problem via Lagrange multipliers, two big things happen:

$$\max_{\alpha}\ \sum_i \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y^{(i)} y^{(j)} \langle \mathbf{x}^{(i)}, \mathbf{x}^{(j)} \rangle$$

• Most of the solved $\alpha_i = 0$; only the support vectors at the margin's edge are nonzero—the model is defined by just a few key samples.
• The data appears only in the form of inner products $\langle \mathbf{x}^{(i)}, \mathbf{x}^{(j)} \rangle$—the door to the kernel trick swings open.

Code in Action: Four Algorithms Compete Head-to-Head

python · classifiers_showdown.py

# Four worldviews face off on two datasets
import numpy as np
from sklearn.datasets import make_moons, make_circles
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier
from sklearn.svm import SVC

datasets = {
    "moons":   make_moons(n_samples=500, noise=0.25, random_state=0),
    "circles": make_circles(n_samples=500, noise=0.1, factor=0.4, random_state=0),
}
models = {
    "LogReg(linear)": LogisticRegression(),
    "Tree(d=4)":      DecisionTreeClassifier(max_depth=4),
    "RandomForest":   RandomForestClassifier(n_estimators=200),
    "GradBoost":      GradientBoostingClassifier(),          # shallow trees in sequence
    "SVM-RBF":        SVC(kernel="rbf", C=1.0, gamma="scale"),
}
for dname, (X, y) in datasets.items():
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0)
    print(f"\n== {dname} ==")
    for mname, m in models.items():
        acc = m.fit(Xtr, ytr).score(Xte, yte)     # Note: evaluate on the test set!
        print(f"  {mname:14s} {acc:.3f}")
# Expected: on moons/circles LogReg clearly lags (the limit of a linear boundary),
# while RBF-SVM and the ensemble methods are near perfect. Crank up noise and rerun—how does the ranking change?

When should you choose a tree model (XGBoost), and when a neural network?

The practical criterion in 2026 is still: tabular data (features are already engineered, semantic columns) → try gradient-boosted trees first; with sample sizes from a few thousand to a few million and feature dimensions from dozens to thousands, tree models are often more accurate, faster, and require less tuning. Perceptual data (images / audio / text—raw signals whose features must be learned) → deep learning is irreplaceable, because its essential advantage is representation learning (Chapters 3 and 4). For mixed scenarios (tabular + text columns), a common practice is to extract features with an LLM/embedding and feed them to XGBoost. This judgment comes up often in both interviews and practice.

Chapter Quiz