Support Vector Machines (SVMs)

a linearly separable dataset admits infinitely many separating hyperplanes, and the perceptron will happily hand you whichever one it trips over first. 𐃏 the support vector machine asks a better question: of all the hyperplanes that separate the data, which one is farthest from everybody? the answer — the maximum-margin hyperplane — is determined by a handful of boundary points (the support vectors), drops out of a beautiful convex dual, and generalises via the kernel trick from lines to nearly anything.

the maximum-margin primal#

setup#

labels \(y_i \in \{-1, +1\}\), linear score \(f(x) = w^\top x + b\), classification by \(\operatorname{sign} f(x)\). the euclidean distance from a point \(x_i\) to the hyperplane \(\{x : w^\top x + b = 0\}\) is

\begin{equation} \frac{\lvert w^\top x_i + b \rvert}{\lVert w \rVert} = \frac{y_i (w^\top x_i + b)}{\lVert w \rVert} \quad \text{when correctly classified.} \end{equation}

the geometric margin of a separating hyperplane is the smallest such distance over the training set. maximise it:

\begin{equation} \max_{w,\,b}\; \min_i\; \frac{y_i(w^\top x_i + b)}{\lVert w\rVert}. \end{equation}

normalising the scale away#

\((w, b)\) and \((cw, cb)\) describe the same hyperplane, so we may fix the scale by demanding \(\min_i y_i(w^\top x_i + b) = 1\). the closest points then sit on the two margin hyperplanes \(w^\top x + b = \pm 1\), the geometric margin is \(1/\lVert w\rVert\), and maximising it is minimising the norm (Deisenroth, Marc Peter and Faisal, A. Aldo and Ong, Cheng Soon, 2020):

\begin{equation} \boxed{\;\min_{w,\,b}\; \tfrac{1}{2}\lVert w \rVert^2 \quad \text{s.t.} \quad y_i(w^\top x_i + b) \ge 1, \; i = 1,\dots,n.\;} \end{equation}

a quadratic objective with affine constraints: a convex QP with a unique solution — no local minima, no initialisation folklore.

the lagrangian dual, carefully#

building the lagrangian#

introduce a multiplier \(\alpha_i \ge 0\) for each inequality constraint:

\begin{equation} \mathcal{L}(w, b, \alpha) = \tfrac{1}{2}\lVert w\rVert^2 - \sum_{i=1}^{n} \alpha_i \big[ y_i(w^\top x_i + b) - 1 \big]. \end{equation}

the primal problem is \(\min_{w,b} \max_{\alpha \ge 0} \mathcal{L}\); the dual swaps the order. because the objective is convex and the constraints affine, slater’s condition holds and strong duality applies — the swap costs nothing (Deisenroth, Marc Peter and Faisal, A. Aldo and Ong, Cheng Soon, 2020).

eliminating the primal variables#

\(\mathcal{L}\) is convex in \((w, b)\), so minimise by stationarity:

\begin{align*} \nabla_w \mathcal{L} = w - \sum_i \alpha_i y_i x_i = 0 \quad &\Longrightarrow \quad w = \sum_i \alpha_i y_i x_i, \\ \frac{\partial \mathcal{L}}{\partial b} = -\sum_i \alpha_i y_i = 0 \quad &\Longrightarrow \quad \sum_i \alpha_i y_i = 0. \end{align*}

the optimal \(w\) is a linear combination of training points. substitute both back in; the \(b\) term dies by the second condition, and after collecting terms:

\begin{equation} \boxed{\;\max_{\alpha}\; \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j\, x_i^\top x_j \quad \text{s.t.} \quad \alpha_i \ge 0,\;\; \textstyle\sum_i \alpha_i y_i = 0.\;} \end{equation}

a QP in \(n\) variables in which the data enter only through inner products \(x_i^\top x_j\) — remember this, it becomes the kernel trick.

kkt conditions and support vectors#

at the joint optimum the karush–kuhn–tucker conditions hold (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome, 2009):

• stationarity — \(w = \sum_i \alpha_i y_i x_i\), \(\sum_i \alpha_i y_i = 0\).
• primal feasibility — \(y_i(w^\top x_i + b) \ge 1\).
• dual feasibility — \(\alpha_i \ge 0\).
• complementary slackness — \(\alpha_i \big[ y_i(w^\top x_i + b) - 1 \big] = 0\) for every \(i\).

the last line is the punchline. for each point, either \(\alpha_i = 0\) or the constraint is active, \(y_i(w^\top x_i + b) = 1\). so:

• points strictly outside the margin have \(\alpha_i = 0\) — they contribute nothing to \(w\). delete them and the solution does not move. 𐃏
• the support vectors — the points on (or later, inside) the margin — carry all the \(\alpha\) mass and alone determine the boundary.
• \(b\) is recovered from any margin support vector via \(y_s(w^\top x_s + b) = 1\), i.e. \(b = y_s - w^\top x_s\) (numerically: average this over all margin svs).

soft margins: the c-formulation#

real data overlap. give each point a slack \(\xi_i \ge 0\) measuring how far it fails the margin, and charge for the total (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome, 2009):

\begin{equation} \min_{w,\,b,\,\xi}\; \tfrac{1}{2}\lVert w\rVert^2 + C \sum_{i=1}^n \xi_i \quad \text{s.t.} \quad y_i(w^\top x_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0. \end{equation}

running the same lagrangian machinery (multipliers \(\alpha_i\) for the margin constraints, \(\mu_i\) for \(\xi_i \ge 0\); stationarity in \(\xi_i\) gives \(\alpha_i = C - \mu_i\)) yields the identical dual with one change — the box constraint:

\begin{equation} 0 \le \alpha_i \le C. \end{equation}

the \(\alpha\) value now reads as a diagnosis:

\(C\) is the inverse-regularisation dial: \(C \to \infty\) recovers the hard margin (violations infinitely expensive, low bias, high variance); small \(C\) buys a wide, calm margin that tolerates violations. choose it by cross validation.

the hinge-loss view#

move the constraints into the objective: at the optimum \(\xi_i = \max(0,\, 1 - y_i f(x_i))\), so the soft-margin svm is exactly

\begin{equation} \min_{w,\,b}\; \sum_{i=1}^{n} \underbrace{\max\big(0,\, 1 - y_i(w^\top x_i + b)\big)}_{\text{hinge loss}} \;+\; \frac{\lambda}{2}\lVert w\rVert^2, \qquad \lambda = 1/C, \end{equation}

which is empirical risk minimisation with an \(\ell_2\) penalty — the svm rejoins the regularised-loss family alongside ridge and logistic regression (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome, 2009). the hinge is a convex upper bound on the 0–1 loss that is exactly zero past the margin — that flat region is why solutions are sparse in the data. the comparative anatomy of hinge vs log vs exponential loss lives on the loss functions page.

the kernel trick#

the dual objective and the decision function touch data only through inner products:

\begin{equation} f(x) = \sum_{i \in \mathrm{sv}} \alpha_i y_i\, x_i^\top x + b. \end{equation}

replace every \(x_i^\top x_j\) with a positive-definite kernel \(k(x_i, x_j) = \langle \phi(x_i), \phi(x_j)\rangle\) and you have silently run the svm in the feature space of \(\phi\) — without ever computing \(\phi\), which may be infinite-dimensional (Deisenroth, Marc Peter and Faisal, A. Aldo and Ong, Cheng Soon, 2020):

• polynomial \(k(x, z) = (1 + x^\top z)^d\): feature space of all monomials up to degree \(d\).
• rbf/gaussian \(k(x, z) = \exp(-\gamma \lVert x - z\rVert^2)\): infinite-dimensional feature space; \(\gamma\) plays bandwidth, and with it the usual bias-variance dial returns.
• the margin story survives untouched because it only ever needed a geometry of inner products.

which functions are legal kernels (mercer’s condition), what the feature spaces look like, and the representer theorem that explains why \(w\) was always going to be a combination of training points — all on the kernel methods page.

solving it: an smo sketch#

the dual is a QP in \(n\) variables with a box constraint and a single linear equality. off-the-shelf QP solvers scale poorly in \(n\); sequential minimal optimisation exploits the structure:¹

• observation the equality \(\sum_i \alpha_i y_i = 0\) means you cannot move one \(\alpha\) alone — the smallest working set is a pair.
• pair solve fix all but \((\alpha_i, \alpha_j)\). the equality pins their weighted sum, so the subproblem is one-dimensional: a parabola in \(\alpha_j\) over a box-induced interval \([L, H]\). the unconstrained optimum is

\begin{equation} \alpha_j \leftarrow \alpha_j - \frac{y_j (E_i - E_j)}{\eta}, \qquad \eta = 2k_{ij} - k_{ii} - k_{jj} \le 0, \end{equation}

where \(E_i = f(x_i) - y_i\) is the current error; clip to \([L, H]\), then update \(\alpha_i\) to preserve the equality, then refresh \(b\) from the kkt conditions.

• loop choose pairs (heuristically: biggest kkt violators first), solve analytically, repeat until every point satisfies kkt within tolerance.
• no matrix inversions, no line searches — each step is exact and closed-form. this is what made svms practical on large datasets in the pre-gpu era.

in code#

a “simplified smo” (random second choice, linear kernel) from scratch on two overlapping gaussian blobs:

import numpy as np

rng = np.random.default_rng(3)
# two gaussian blobs, slightly overlapping
n_half = 30
Xp = rng.normal([2.0, 2.0], 1.0, (n_half, 2))
Xm = rng.normal([-1.0, -1.0], 1.0, (n_half, 2))
X = np.vstack([Xp, Xm])
y = np.hstack([np.ones(n_half), -np.ones(n_half)])

def smo(X, y, C=1.0, tol=1e-4, max_passes=30, seed=0):
    """platt's simplified SMO, linear kernel."""
    rng = np.random.default_rng(seed)
    n = len(y)
    K = X @ X.T
    alpha, b = np.zeros(n), 0.0
    f = lambda i: (alpha * y) @ K[:, i] + b
    passes = 0
    while passes < max_passes:
        changed = 0
        for i in range(n):
            Ei = f(i) - y[i]
            if (y[i] * Ei < -tol and alpha[i] < C) or (y[i] * Ei > tol and alpha[i] > 0):
                j = rng.integers(n - 1)
                j += (j >= i)                      # pick j != i
                Ej = f(j) - y[j]
                ai, aj = alpha[i], alpha[j]
                if y[i] != y[j]:
                    L, H = max(0, aj - ai), min(C, C + aj - ai)
                else:
                    L, H = max(0, ai + aj - C), min(C, ai + aj)
                if L == H:
                    continue
                eta = 2 * K[i, j] - K[i, i] - K[j, j]
                if eta >= 0:
                    continue
                alpha[j] = np.clip(aj - y[j] * (Ei - Ej) / eta, L, H)
                if abs(alpha[j] - aj) < 1e-5:
                    continue
                alpha[i] = ai + y[i] * y[j] * (aj - alpha[j])
                b1 = b - Ei - y[i]*(alpha[i]-ai)*K[i,i] - y[j]*(alpha[j]-aj)*K[i,j]
                b2 = b - Ej - y[i]*(alpha[i]-ai)*K[i,j] - y[j]*(alpha[j]-aj)*K[j,j]
                if 0 < alpha[i] < C:   b = b1
                elif 0 < alpha[j] < C: b = b2
                else:                  b = (b1 + b2) / 2
                changed += 1
        passes = passes + 1 if changed == 0 else 0
    return alpha, b

C = 1.0
alpha, b = smo(X, y, C=C)
w = (alpha * y) @ X
sv = alpha > 1e-6
margin_sv = sv & (alpha < C - 1e-6)          # on the margin (0 < a < C)
pred = np.sign(X @ w + b)

print(f"support vectors : {sv.sum()} of {len(y)} (on margin: {margin_sv.sum()}, "
      f"inside/violating: {(alpha > C - 1e-6).sum()})")
print(f"w = [{w[0]:.4f}, {w[1]:.4f}],  b = {b:.4f}")
print(f"geometric margin 1/||w|| = {1/np.linalg.norm(w):.4f}")
print(f"training accuracy: {(pred == y).mean():.3f}")
print(f"dual constraint sum(alpha_i y_i) = {alpha @ y:.2e}")
# kkt spot check: margin svs should have y_i f(x_i) ~ 1
fx = X @ w + b
print("margin svs, y_i f(x_i):", np.round((y * fx)[margin_sv], 3))

support vectors : 7 of 60 (on margin: 3, inside/violating: 4)
w = [1.4140, 1.2298],  b = -1.5447
geometric margin 1/||w|| = 0.5336
training accuracy: 1.000
dual constraint sum(alpha_i y_i) = -2.00e-15
margin svs, y_i f(x_i): [1.    1.    0.885]

reading the output against the theory:

• sparsity: 60 training points, 7 support vectors — the other 53 have \(\alpha_i = 0\) exactly and could be deleted without moving the boundary.
• the box in action: 3 svs sit on the margin (\(0 < \alpha < C\)), 4 have hit the ceiling \(\alpha = C\) — the blobs overlap, so the soft margin absorbs them as paid violations.
• the equality constraint \(\sum_i \alpha_i y_i = 0\) holds to machine precision.
• kkt check: margin svs should satisfy \(y_i f(x_i) = 1\); two do exactly, one reads \(0.885\) — the honest cost of the simplified pair-selection heuristic and loose tolerance. full smo with proper working-set selection drives every violation below \(10^{-4}\).

see also#

• the perceptron — finds a separating hyperplane; the svm finds the best one
• kernel methods — the machinery that turns this linear method nonlinear
• loss functions — hinge loss among its rivals
• logistic regression — the smooth-loss sibling that keeps probabilities but loses sparsity
• bias-variance decomposition — what \(C\) and \(\gamma\) are really negotiating

References#

Deisenroth, Marc Peter and Faisal, A. Aldo and Ong, Cheng Soon (2020). Mathematics for Machine Learning, Cambridge University Press.

Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome (2009). The Elements of Statistical Learning, Springer.