Classical Machine Learning

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.

Classical machine learning studies algorithms that build a model $\hat{f}$ mapping inputs $x$ to outputs $y$ by optimizing an objective measured on observed examples ${(x_{i}, y_{i})}_{i = 1}^{n}$ . It matters because most real-world predictive problems involve modest, structured (tabular) data where these methods are faster, more interpretable, and more sample-efficient than deep learning. The discipline rests on a unifying principle: empirical risk minimization regularized to prevent overfitting, justified by statistical learning theory. A surprising fact is that increasing model flexibility does not monotonically improve test performance — there is an optimal complexity at which the sum of bias and variance is minimized, a phenomenon invisible if one looks only at training error.

The Core Insight

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

Formal Statement

Supervised Learning Problem

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

R (h) = E_{(x, y) \sim P} [ℓ (h (x), y)] .

⟳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:

\hat{R}_{S} (h) = \frac{1}{n} i = 1 \sum n ℓ (h (x_{i}), y_{i}) .

⟳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} = ar g min_{h \in H} \hat{R}_{S} (h) + λ Ω (h)$ , where $Ω$ is a regularizer penalizing complexity and $λ \geq 0$ trades off fit versus complexity.

Here the symbols are: $x \in R^{d}$ the feature vector; $y$ the target (continuous for regression, categorical for classification); $h$ a candidate model; $H$ the model family; $ℓ$ the per-example loss; $λ$ the regularization strength; $Ω$ a norm or count of model parameters.

Common Loss Functions

For regression, the squared loss:

ℓ (\overset{y}{^}, y) = (\overset{y}{^} - y)^{2} .

⟳arises as the negative log-likelihood of a Gaussian noise model

y = h (x) + ε

ε \sim N (0, σ^{2})

For binary classification ( $y \in {0, 1}$ ), the logistic / cross-entropy loss:

ℓ (\overset{p}{^}, y) = - [y lo g \overset{p}{^} + (1 - y) lo g (1 - \overset{p}{^})],

where

\overset{p}{^} = σ (w^{⊤} x) = (1 + e^{- w^{⊤} x})^{- 1}

⟳negative log-likelihood of a Bernoulli model whose success probability is the logistic transform of a linear score.

Bias–Variance Decomposition

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

E [(y - \hat{f} (x_{0}))^{2}] = bias^{2} (E [\hat{f} (x_{0})] - f (x_{0}))^{2} + variance Var (\hat{f} (x_{0})) + irreducible σ^{2} .

⟳expand the square, add and subtract

E [\hat{f}]

, and use that

ε

is independent of

\hat{f}

with zero mean so all cross terms vanish.

Why It Holds / Derivation

Bias–Variance Decomposition

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

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

Step 2. Expand:

= E [(f - \hat{f})^{2}] + 2 E [ε (f - \hat{f})] + E [ε^{2}] .

Step 3. Since

ε

is independent of

\hat{f}

and

E [ε] = 0

, the middle term vanishes, and

E [ε^{2}] = σ^{2}

. Step 4. Add and subtract

\overset{ˉ}{f} := E [\hat{f}]

inside the first term:

E [(f - \hat{f})^{2}] = E [(f - \overset{ˉ}{f} + \overset{ˉ}{f} - \hat{f})^{2}] = (f - \overset{ˉ}{f})^{2} + E [(\overset{ˉ}{f} - \hat{f})^{2}],

because the cross term

2 (f - \overset{ˉ}{f}) E [\overset{ˉ}{f} - \hat{f}] = 0

. Step 5. Identify

(f - \overset{ˉ}{f})^{2}

bias^{2}

and

E [(\overset{ˉ}{f} - \hat{f})^{2}]

as the variance. Summing gives [5].

■

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.

Building 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 $λ$ 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.

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

Worked Examples

Ordinary Least Squares Regression

Given: Three data points

(x, y) = (1, 2), (2, 2), (3, 4)

. Fit

\overset{y}{^} = w_{0} + w_{1} x

by minimizing squared error. Step 1. Closed form:

\overset{w}{^}_{1} = \frac{\sum ( x _{i} - x ˉ ) ( y _{i} - y ˉ )}{\sum ( x _{i} - x ˉ ) ^{2}}

. Means:

\overset{x}{ˉ} = 2

\overset{y}{ˉ} = \frac{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.

\overset{w}{^}_{1} = 2.0/2 = 1.0

. Then

\overset{w}{^}_{0} = \overset{y}{ˉ} - \overset{w}{^}_{1} \overset{x}{ˉ} = 2.667 - 1.0 \cdot 2 = 0.667

\overset{y}{^} = 0.667 + 1.0 x (units: same as y)

Predicted at

x = 2

\overset{y}{^} = 2.667

; residuals

{2 - 2.667, 2 - 2.667, 4 - 2.667}

... checked, sum to zero as required.

k-Nearest Neighbours Classification

Given: Labelled points

A = (1, 1)

:●,

B = (2, 1)

:●,

C = (4, 4)

:○,

D = (5, 4)

:○. Classify query

q = (3, 2)

with

k = 3

using Euclidean distance. Step 1. Distances:

d (q, A) = 4 + 1 = 2.236

;

d (q, B) = 1 + 1 = 1.414

;

d (q, C) = 1 + 4 = 2.236

;

d (q, D) = 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.

Predicted class = ● (class 1)

Note: the

A / C

tie in distance is broken by index order; in practice ties are handled by distance-weighting.

Common Misconceptions

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. 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. 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.

Connections

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.

Real-World Applications

Credit scoring (FICO, banks): logistic regression and gradient-boosted trees predict default probability from financial features — interpretability is legally mandated, favouring classical models.
Spam filtering (early Gmail, SpamAssassin): naive Bayes and SVMs classify emails from bag-of-words features.
Medical diagnosis & risk (e.g. Framingham, sepsis early-warning): Cox regression and random forests estimate disease risk from clinical variables.
Recommendation baselines (Netflix Prize era): matrix factorization and k-NN collaborative filtering predicted movie ratings.
Genomics (GWAS, microarray analysis): LASSO regression selects predictive genes from high-dimensional, low-sample data.
Customer churn / marketing (telecom, retail): gradient boosting (XGBoost, LightGBM) on tabular CRM data routinely wins Kaggle competitions.
Fraud detection (credit-card networks): isolation forests and ensemble trees flag anomalous transactions in real time.

Historical Development

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.

Subtleties & Limits

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.

Classical Machine Learning

The Core Insight

Formal Statement

Supervised Learning Problem

Common Loss Functions

Bias–Variance Decomposition

Why It Holds / Derivation

Bias–Variance Decomposition

Vladimir Vapnik | b. 1936

Building Intuition

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

Worked Examples

Ordinary Least Squares Regression

k-Nearest Neighbours Classification

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads