Classical Algorithms

Full derivations and theory for each algorithm: assumptions, objective, math, training, prediction, pros/cons.

Table of contents

1. k-Nearest Neighbors (k-NN)
2. Naive Bayes classifiers
3. Decision trees (CART)
4. Support vector machines (SVM)
5. k-Means clustering (Lloyd's algorithm)
6. Gaussian Mixture Models (GMM) and EM

1. k-Nearest Neighbors (k-NN)

1.1 Algorithm

Non-parametric, instance-based learning — no parameters to fit; the training set is the model.

Prediction for a new point $\mathbf{x}$:

1. Compute distance from $\mathbf{x}$ to every training point.
2. Find the $k$ nearest neighbors $\mathcal{N}_k(\mathbf{x})$.
3. Classification: majority vote: $\hat{y} = \text{mode}\{y_i : i \in \mathcal{N}_k(\mathbf{x})\}$.

Regression: average: $\hat{y} = \frac{1}{k}\sum_{i\in\mathcal{N}_k(\mathbf{x})} y_i$.

1.2 Distance metrics

Euclidean (L2): $d(\mathbf{x},\mathbf{x}') = \|\mathbf{x}-\mathbf{x}'\|_2$. Standard; assumes features have similar scales.

Manhattan (L1): $d(\mathbf{x},\mathbf{x}') = \|\mathbf{x}-\mathbf{x}'\|_1$. Robust to outliers.

Minkowski (Lp): $d(\mathbf{x},\mathbf{x}') = \|\mathbf{x}-\mathbf{x}'\|_p = \left(\sum_j |x_j - x'_j|^p\right)^{1/p}$. Generalizes both.

Cosine distance: $1 - \cos\theta$. Useful for high-dimensional sparse data (text).

Mahalanobis: $d(\mathbf{x},\mathbf{x}') = \sqrt{(\mathbf{x}-\mathbf{x}')^\top \boldsymbol{\Sigma}^{-1}(\mathbf{x}-\mathbf{x}')}$. Accounts for feature correlations; scale-invariant.

1.3 Effect of k

Optimal k: use cross-validation. Typical: $k = \sqrt{n}$ as heuristic starting point.

1.4 Complexity

• Training: $O(1)$ (store data).
• Prediction (naive): $O(nd)$ per query — must compare to all $n$ training points in $d$ dimensions.
• Approximate methods: KD-tree ($O(d\log n)$ average for low $d$), ball tree, HNSW (for large-scale approximate NN).

1.5 Characteristics

1.6 k-NN regression: Nadaraya-Watson interpretation

k-NN regression is a special case of kernel regression with a uniform kernel:

where $K$ is uniform over the $k$-NN ball (bandwidth $h$ adapts to local density).

2. Naive Bayes classifiers

2.1 Generative model and Bayes rule

Use Bayes' theorem for classification:

Since $P(\mathbf{x})$ is the same for all classes, predict:

The Naive assumption: features are conditionally independent given the class:

This reduces a $d$-dimensional joint distribution to $d$ univariate distributions — tractable even in high dimensions.

2.2 Training

Prior: $\hat{P}(y=c) = \frac{n_c + \alpha}{n + K\alpha}$ (with Laplace smoothing $\alpha$).

Per-feature likelihoods:

• Gaussian NB (continuous features): assume $x_j|y=c \sim \mathcal{N}(\mu_{cj},\sigma_{cj}^2)$. Estimate $\hat{\mu}_{cj} = \text{mean}\{x_{ij}:y_i=c\}$, $\hat{\sigma}^2_{cj} = \text{var}\{x_{ij}:y_i=c\}$.
• Bernoulli NB (binary features): $P(x_j=1|y=c) = p_{cj}$. Estimate from empirical frequency.
• Multinomial NB (count features): $P(x_j|y=c) \propto \theta_{cj}^{x_j}$. MLE: $\hat\theta_{cj} = (n_{cj}+\alpha)/(\sum_k n_{ck}+d\alpha)$.

2.3 Prediction (log-sum for numerical stability)

Computing in log-space avoids underflow from multiplying many small probabilities.

2.4 Why it often works despite the naive assumption

Even if features are correlated, NB's decision boundary can still be correct. The calibrated probabilities may be off, but the predicted class often isn't.

2.5 Laplace smoothing (additive smoothing)

With zero occurrences in training, $P(x_j|y=c) = 0$ → entire product = 0 regardless of other features. Laplace smoothing adds pseudocount $\alpha$:

where $V$ = vocabulary size.

3. Decision trees (CART)

3.1 Structure

A binary tree where each internal node tests a feature threshold ($x_j \leq t$), each leaf outputs a prediction.

3.2 Impurity measures (classification)

Gini impurity at node $S$:

Entropy:

Information gain: reduction in impurity from a split $S \to S_L, S_R$:

Gini vs Entropy: both work similarly in practice. Gini slightly favors larger partitions; entropy slightly more computationally expensive (log). CART uses Gini by default.

Regression impurity: MSE of node.

3.3 CART algorithm

function BuildTree(S):
  if stopping_criterion(S):
      return Leaf(prediction(S))
  
  (j*, t*) = argmin_{j,t}  [Gini-weighted split of S on (j,t)]
  S_L = {x ∈ S : x_j ≤ t}
  S_R = {x ∈ S : x_j > t}
  
  return Node(feature=j*, threshold=t*,
              left=BuildTree(S_L),
              right=BuildTree(S_R))

Finding the best split: for each feature $j$, sort by $x_j$, try all thresholds between consecutive distinct values. Cost: $O(np \log n)$ per node → $O(np \log^2 n)$ for full tree (average).

3.4 Leaf prediction

• Classification: majority class.
• Regression: mean of targets.

3.5 Stopping criteria (pre-pruning)

• max_depth: maximum tree depth.
• min_samples_split: minimum samples to split a node.
• min_samples_leaf: minimum samples in a leaf.
• min_impurity_decrease: split only if improvement exceeds threshold.

3.6 Pruning (post-pruning)

Cost-complexity pruning (sklearn ccp_alpha): add complexity penalty $\alpha \cdot |T|$ (number of leaves) to training loss. Increasing $\alpha$ prunes more leaves. Select $\alpha$ via cross-validation.

3.7 Bias-variance of trees

• Fully grown tree: high variance, low bias (overfits to training set).
• Shallow tree: low variance, high bias (underfits).
• Regularize with depth, min-samples, or pruning.

3.8 Key properties

4. Support vector machines (SVM)

4.1 Maximum margin classifier (linearly separable case)

For binary labels $y_i \in \{-1,+1\}$, find hyperplane $\mathbf{w}^\top\mathbf{x}+b=0$ that maximizes the margin between classes.

The margin is the perpendicular distance from the hyperplane to the nearest points. For normalized $\|\mathbf{w}\|=1$, the distance from point $\mathbf{x}_i$ to the hyperplane is $y_i(\mathbf{w}^\top\mathbf{x}_i+b)$.

Margin $= 2/\|\mathbf{w}\|$ (when support vectors satisfy $y_i(\mathbf{w}^\top\mathbf{x}_i+b)=1$).

Primal optimization problem:

Quadratic program (QP) with linear constraints → unique solution.

4.2 Lagrangian and dual formulation

Form Lagrangian with multipliers $\alpha_i \geq 0$:

KKT stationarity conditions:

Substituting back, the dual problem:

Prediction:

Support vectors: points with $\alpha_i > 0$. By complementary slackness: $\alpha_i(y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1)=0$, so support vectors lie exactly on the margin boundary. Typically a small fraction of training set. The solution only depends on support vectors.

4.3 Soft margin SVM (non-separable data)

Introduce slack $\xi_i \geq 0$ (allows some misclassification):

C controls tradeoff: large C → penalize violations heavily → smaller margin, fewer support vectors, more overfit. Small C → allow more violations → larger margin, more regularized.

Dual: same structure but $0 \leq \alpha_i \leq C$ (bounded dual variables).

Hinge loss equivalence:

Hinge loss: $\ell(z) = \max(0, 1-z)$. Convex, non-differentiable at $z=1$.

4.4 Kernel trick

In dual problem, data appears only in inner products $\mathbf{x}_i^\top\mathbf{x}_j$. Replace with a kernel function:

We never need to compute $\phi$ explicitly — only the kernel value. This implicitly works in a (possibly infinite-dimensional) feature space at the cost of the inner product.

RBF kernel interpretation: measures similarity as function of Euclidean distance. Hyperparameter $\gamma = 1/(2\sigma^2)$: large $\gamma$ → narrow Gaussian → model fits locally (high variance); small $\gamma$ → broad Gaussian → smoother decision (high bias).

4.5 Mercer's theorem

A function $K$ is a valid kernel iff the kernel (Gram) matrix $\mathbf{K}_{ij} = K(\mathbf{x}_i,\mathbf{x}_j)$ is PSD for any set of inputs. PSD kernels correspond to inner products in some feature space.

4.6 SMO algorithm

Sequential Minimal Optimization (Platt, 1998): solve SVM dual by optimizing over 2 variables at a time (smallest QP with closed form). The standard algorithm for training SVMs. libsvm uses it.

4.7 SVM for multiclass

• OvO: train $\binom{K}{2}$ binary SVMs, majority vote. sklearn default.
• OvR: train $K$ SVMs, pick highest score.

4.8 Properties

5. k-Means clustering (Lloyd's algorithm)

5.1 Objective

Given data $\mathbf{X} = \{\mathbf{x}_i\}_{i=1}^n$ and target clusters $k$, minimize:

where $z_i \in \{1,\ldots,k\}$ is the cluster assignment of point $i$ and $\boldsymbol{\mu}_c$ is the centroid of cluster $c$.

This is NP-hard in general. Lloyd's algorithm finds a local minimum.

5.2 Lloyd's algorithm (alternating optimization)

1. Initialize: choose $k$ centroids.
2. Assignment step: $z_i = \arg\min_c \|\mathbf{x}_i - \boldsymbol{\mu}_c\|^2$. (Assign each point to nearest centroid.)
3. Update step: $\boldsymbol{\mu}_c = \frac{1}{|C_c|}\sum_{i:z_i=c}\mathbf{x}_i$. (Move centroid to mean of assigned points.)
4. Repeat until assignments don't change.

Convergence: objective $J$ decreases or stays constant at each step (both assignment and update are greedy improvements). Converges in finite steps (finite assignments). But converges to a local minimum.

5.3 k-means++ initialization

Standard random init can lead to poor local minima. k-means++ (Arthur & Vassilvitskii, 2007):

1. Choose first centroid uniformly at random.
2. For each subsequent centroid: sample point with probability $\propto d(\mathbf{x}, \text{nearest centroid})^2$.
3. Repeat until $k$ centroids chosen.

Guarantees expected cost $O(\log k)$ times the optimal. sklearn uses k-means++ by default.

5.4 Choosing k

• Elbow method: plot $J$ vs $k$; look for "elbow" where improvement diminishes.
• Silhouette coefficient: $s(i) = \frac{b(i)-a(i)}{\max(a(i),b(i))}$, where $a(i)$ = mean distance to same-cluster points, $b(i)$ = mean distance to nearest-other-cluster points. Range $[-1,1]$; higher = better.
• Gap statistic: compare $\log J$ to $\mathbb{E}[\log J]$ under reference (random) distribution.

5.5 Properties

6. Gaussian Mixture Models (GMM) and EM

6.1 Model

GMM is a probabilistic generative model: data is assumed to be drawn from a mixture of $K$ Gaussians:

where $\pi_k \geq 0$, $\sum_k \pi_k = 1$ (mixing coefficients).

Latent variable formulation: introduce hidden variable $z_i \in \{1,\ldots,K\}$:

6.2 EM algorithm for GMM

Goal: maximize log-likelihood $\ell(\boldsymbol\theta) = \sum_i \log p(\mathbf{x}_i|\boldsymbol\theta)$. Not tractable directly (sum inside log).

Expectation-Maximization (EM):

E-step (soft assignments):

These are responsibilities (soft cluster assignments, $\sum_k r_{ik} = 1$).

M-step (update parameters):

where $N_k = \sum_i r_{ik}$ (effective number of points in cluster $k$).

EM guarantees: log-likelihood is non-decreasing at each step (E then M). Converges to local maximum.

6.3 EM as generalized alternating optimization

E-step: compute lower bound $\mathcal{Q}$ on log-likelihood (tightened at current parameters). M-step: maximize that lower bound.

The lower bound is the ELBO (Evidence Lower Bound): $\ell(\boldsymbol\theta) \geq \mathcal{Q}(\boldsymbol\theta, \boldsymbol\theta_\text{old})$. EM maximizes it iteratively.

6.4 GMM vs k-means

6.5 Covariance types (sklearn)

from sklearn.mixture import GaussianMixture
gmm = GaussianMixture(n_components=3, covariance_type='full', random_state=0)
gmm.fit(X)
labels = gmm.predict(X)          # hard assignments
probs  = gmm.predict_proba(X)    # soft assignments
log_likelihood = gmm.score(X)    # average log-likelihood per sample
bic   = gmm.bic(X)               # use BIC to select number of components

*File: notes/07_classical_algorithms.md — next: notes/08_ensemble_methods.md*