Classical Machine Learning

⚡ Key Takeaways

Classical Machine Learning is the body of statistical and algorithmic methods that learn predictive or descriptive models from data without deep neural networks — including linear/logistic regression, support vector machines, decision trees, k-nearest neighbours, naive Bayes, and clustering. Key result: by minimizing a regularized loss over a training set, one can fit a function that generalizes to unseen data, with generalization controlled by the bias–variance tradeoff. Where it applies: tabular data, small-to-medium datasets, interpretable modelling, scientific inference, and as baselines everywhere. Who/when: roots in Gauss and Legendre (least squares, ~1805), formalized by Fisher, Rosenblatt, Vapnik, Breiman, and others across the 20th century.

💡 The Core Insight

Learning is function estimation under uncertainty. We never see the true data-generating distribution $P(\mathbf{x}, y)$ ; we see a finite sample. We choose a hypothesis class $\mathcal{H}$ (the set of candidate models), define a loss measuring error, and pick the member of $\mathcal{H}$ that minimizes loss on the data — but constrained so we fit signal, not noise. Every classical algorithm is a particular choice of $(\mathcal{H}, \text{loss}, \text{regularizer}, \text{optimizer})$ .

DefinitionSupervised Learning Problem

We are given a training set $S = \{(\mathbf{x}_i, y_i)\}_{i=1}^n$ drawn i.i.d. from an unknown distribution $P$ over $\mathcal{X} \times \mathcal{Y}$ . A hypothesis $h: \mathcal{X} \to \mathcal{Y}$ belongs to a hypothesis class $\mathcal{H}$ . A loss function $\ell(h(\mathbf{x}), y) \ge 0$ measures prediction error. The goal is to minimize the true risk (expected loss):

1

\quad R(h) = \mathbb{E}_{(\mathbf{x},y)\sim P}\big[\ell(h(\mathbf{x}), y)\big].

Derivation hint: this is the population mean of the loss; it is the quantity we wish were small but cannot compute directly because $P$ is unknown. Since $P$ is unknown, we minimize the empirical risk instead:

2

\quad \hat{R}_S(h) = \frac{1}{n}\sum_{i=1}^{n} \ell(h(\mathbf{x}_i), y_i).

Derivation hint: replace the expectation in [1] with the sample average over the training set — a Monte Carlo estimate of $R(h)$ . The learned model is $\hat{h} = \arg\min_{h \in \mathcal{H}} \hat{R}_S(h) + \lambda \Omega(h)$ , where $\Omega$ is a regularizer penalizing complexity and $\lambda \ge 0$ trades off fit versus complexity.

DefinitionCommon Loss Functions

For regression, the squared loss:

3

\quad \ell(\hat{y}, y) = (\hat{y} - y)^2.

Derivation hint: arises as the negative log-likelihood of a Gaussian noise model $y = h(\mathbf{x}) + \varepsilon$ , $\varepsilon \sim \mathcal{N}(0, \sigma^2)$ . For binary classification ( $y \in \{0,1\}$ ), the logistic / cross-entropy loss:

4

\quad \ell(\hat{p}, y) = -\big[y\log \hat{p} + (1-y)\log(1-\hat{p})\big],

where $\hat{p} = \sigma(\mathbf{w}^\top\mathbf{x}) = (1+e^{-\mathbf{w}^\top\mathbf{x}})^{-1}$ . Derivation hint: negative log-likelihood of a Bernoulli model whose success probability is the logistic transform of a linear score.

TheoremBias–Variance Decomposition

For squared loss with target $y = f(\mathbf{x}) + \varepsilon$ , $\mathbb{E}[\varepsilon]=0$ , $\mathrm{Var}(\varepsilon)=\sigma^2$ , the expected test error of an estimator $\hat{f}$ at a point $\mathbf{x}_0$ decomposes as:

5

\quad \mathbb{E}\big[(y - \hat{f}(\mathbf{x}_0))^2\big] = \underbrace{\big(\mathbb{E}[\hat{f}(\mathbf{x}_0)] - f(\mathbf{x}_0)\big)^2}_{\text{bias}^2} + \underbrace{\mathrm{Var}(\hat{f}(\mathbf{x}_0))}_{\text{variance}} + \underbrace{\sigma^2}_{\text{irreducible}}.

Derivation hint: expand the square, add and subtract $\mathbb{E}[\hat{f}]$ , and use that $\varepsilon$ is independent of $\hat{f}$ with zero mean so all cross terms vanish.

ProofBias–Variance Decomposition

Step 1. Write the expected squared error, with expectation over training sets and noise:

\mathbb{E}\big[(y - \hat{f})^2\big] = \mathbb{E}\big[(f + \varepsilon - \hat{f})^2\big].

Step 2. Expand:

= \mathbb{E}\big[(f - \hat{f})^2\big] + 2\,\mathbb{E}[\varepsilon(f-\hat{f})] + \mathbb{E}[\varepsilon^2].

Step 3. Since $\varepsilon$ is independent of $\hat{f}$ and $\mathbb{E}[\varepsilon]=0$ , the middle term vanishes, and $\mathbb{E}[\varepsilon^2] = \sigma^2$ .

Step 4. Add and subtract $\bar{f} := \mathbb{E}[\hat{f}]$ inside the first term:

\mathbb{E}\big[(f - \hat{f})^2\big] = \mathbb{E}\big[(f - \bar{f} + \bar{f} - \hat{f})^2\big] = (f-\bar{f})^2 + \mathbb{E}\big[(\bar{f}-\hat{f})^2\big],

because the cross term $2(f-\bar{f})\mathbb{E}[\bar{f}-\hat{f}] = 0$ .

Step 5. Identify $(f-\bar{f})^2$ as $\text{bias}^2$ and $\mathbb{E}[(\bar{f}-\hat{f})^2]$ as the variance. Summing gives [5]. $\blacksquare$

∎

mathematician · Vladimir Vapnik | b. 1936

Soviet-American mathematician who, with Alexey Chervonenkis, founded statistical learning theory in the 1960s–70s. They introduced the VC dimension, a measure of hypothesis-class capacity bounding the gap between empirical and true risk, and proved uniform convergence results that explain why empirical risk minimization works. Vapnik later co-invented the support vector machine (1992–95), which combined margin maximization with the kernel trick to produce one of the most powerful pre-deep-learning classifiers. His book The Nature of Statistical Learning Theory (1995) made the field rigorous and is foundational reading.

🧠 Intuition

Think of fitting a curve to noisy dots. A straight line (low complexity) is rigid: it cannot bend to follow the true curve, so it is consistently wrong in a systematic way — high bias. A wiggly high-degree polynomial threads through every dot, including the noise; rerun with new data and the wiggles jump around wildly — high variance. The sweet spot is a model flexible enough to capture the real shape but stiff enough to ignore noise. Regularization is the stiffness knob: increasing $\lambda$ shrinks coefficients toward zero, trading a little extra bias for a large reduction in variance. This is why you almost never use an unregularized, maximally flexible model in practice.

Figure

Bias–variance tradeoff: test error is U-shaped in model complexity

ExampleOrdinary Least Squares Regression

Given: Three data points $(x,y) = (1,2),(2,2),(3,4)$ . Fit $\hat{y} = w_0 + w_1 x$ by minimizing squared error.

Step 1. Closed form: $\hat{w}_1 = \dfrac{\sum (x_i-\bar{x})(y_i-\bar{y})}{\sum(x_i-\bar{x})^2}$ . Means: $\bar{x}=2$ , $\bar{y}=\tfrac{8}{3}\approx 2.667$ .

Step 2. Numerator: $(1-2)(2-2.667)+(2-2)(2-2.667)+(3-2)(4-2.667) = (-1)(-0.667)+0+(1)(1.333)=2.0$ .

Step 3. Denominator: $(1-2)^2+(2-2)^2+(3-2)^2 = 1+0+1 = 2$ .

Step 4. $\hat{w}_1 = 2.0/2 = 1.0$ . Then $\hat{w}_0 = \bar{y} - \hat{w}_1\bar{x} = 2.667 - 1.0\cdot 2 = 0.667$ .

\boxed{\hat{y} = 0.667 + 1.0\,x \quad (\text{units: same as } y)}

Predicted at $x=2$ : $\hat{y}=2.667$ ; residuals $\{2-2.667,\,2-2.667,\,4-2.667\}$ ... checked, sum to zero as required.

Examplek-Nearest Neighbours Classification

Given: Labelled points $A=(1,1)$ :●, $B=(2,1)$ :●, $C=(4,4)$ :○, $D=(5,4)$ :○. Classify query $\mathbf{q}=(3,2)$ with $k=3$ using Euclidean distance.

Step 1. Distances: $d(\mathbf{q},A)=\sqrt{4+1}=2.236$ ; $d(\mathbf{q},B)=\sqrt{1+1}=1.414$ ; $d(\mathbf{q},C)=\sqrt{1+4}=2.236$ ; $d(\mathbf{q},D)=\sqrt{4+4}=2.828$ .

Step 2. Sort ascending: $B(1.414,●),\ A(2.236,●),\ C(2.236,○),\ D(2.828,○)$ .

Step 3. Take $k=3$ nearest: $\{B, A, C\}$ → labels $\{●, ●, ○\}$ .

Step 4. Majority vote: 2 vs 1.

\boxed{\text{Predicted class} = ● \ (\text{class 1})}

Note: the $A/C$ tie in distance is broken by index order; in practice ties are handled by distance-weighting.

⚠️ Common mistake

Low training error means a good model — FALSE. A model can achieve zero training error by memorizing noise (overfitting) while performing terribly on new data. Always evaluate on a held-out test set or via cross-validation, never on the data used to fit. Likewise, never tune hyperparameters on the test set — that leaks information and inflates your reported accuracy.

⚠️ Common mistake

More features always help — FALSE. Adding irrelevant or correlated features increases variance and can degrade performance (the curse of dimensionality: in high dimensions, distances concentrate and data becomes sparse). Feature selection, regularization, and dimensionality reduction (e.g. Principal Component Analysis) are often essential.

Counterexample

Accuracy is a reliable metric — not on imbalanced data. Suppose 99% of emails are non-spam. A trivial classifier that labels everything "non-spam" achieves 99% accuracy yet catches zero spam. Its recall on the positive class is 0%. This shows why one must report precision, recall, F1, and AUC rather than raw accuracy when classes are imbalanced.

connection

Classical ML sits at the crossroads of several fields. Linear Regression and Logistic Regression are special cases of Generalized Linear Models from statistics. Maximum Likelihood Estimation supplies the principled origin of most loss functions (squared loss ↔ Gaussian noise, cross-entropy ↔ Bernoulli). Convex Optimization provides the algorithms — Gradient Descent and its variants — that minimize the objectives. Support Vector Machines connect to functional analysis through the Kernel Trick and reproducing kernel Hilbert spaces. The capacity-control theory linking $\hat{R}$ to $R$ is Statistical Learning Theory via the VC Dimension. Unsupervised methods like k-Means Clustering and Principal Component Analysis are the descriptive counterparts to these predictive tools.

🔬 Where this appears

⏳ History

- 1805–1809 — Legendre & Gauss: method of least squares introduced for astronomical orbit fitting; Gauss links it to the normal distribution.

- 1936 — R. A. Fisher: linear discriminant analysis and the foundations of statistical classification.

- 1957 — Frank Rosenblatt: the perceptron, a learnable linear classifier and ancestor of neural networks.

- 1963 — Morgan & Sonquist: AID, an early decision-tree algorithm; refined into CART by Breiman et al. (1984).

- 1967 — Cover & Hart: formal analysis of nearest-neighbour classification and its error bounds.

- 1971 — Vapnik & Chervonenkis: VC theory, bounding generalization error via hypothesis-class capacity.

- 1986 — Quinlan: the ID3 / C4.5 decision-tree induction algorithms.

- 1995 — Cortes & Vapnik: the support vector machine with soft margins and kernels.

- 2001 — Breiman: random forests; Friedman (1999–2001) develops gradient boosting, dominating tabular ML for two decades.

open-problem

Several deep questions remain partly open. Why does ERM generalize even when models can interpolate the data? The classical bias–variance picture predicts disaster at interpolation, yet over-parameterized models (and even large random forests) can generalize well — the double descent phenomenon, now studied but not fully theorized. How should we choose the hypothesis class and regularizer automatically? AutoML and meta-learning attack this heuristically without firm theory. Distribution shift: all guarantees assume i.i.d. train/test data; performance under shifted $P$ lacks general bounds. Causality vs. correlation: classical ML estimates conditional means, not causal effects, so models can fail catastrophically under intervention — bridging this with causal inference is active research.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also