Support Vector Machines

Maximum-margin classification

For linearly separable data there are infinitely many separating hyperplanes $\mathbf w^\top\mathbf x + b = 0$. The SVM picks the one with the largest margin — the widest "street" between the classes — which generalises best and depends only on the hardest points.

Geometry

• Signed distance of $\mathbf x$ from the hyperplane: $\dfrac{\mathbf w^\top\mathbf x + b}{\lVert\mathbf w\rVert}$.
• Scale $\mathbf w, b$ so the closest points satisfy $y_i(\mathbf w^\top\mathbf x_i + b) = 1$. Then the margin width is $\dfrac{2}{\lVert\mathbf w\rVert}$.

Hard-margin SVM

$$\min_{\mathbf w, b}\ \frac12\lVert\mathbf w\rVert^2 \quad\text{subject to}\quad y_i(\mathbf w^\top\mathbf x_i + b) \ge 1\ \ \forall i.$$

A convex quadratic program with a unique solution. The points with equality are the support vectors.

Soft margin: tolerating overlap

Real data overlaps. Introduce slack $\xi_i \ge 0$:

$$\min_{\mathbf w, b, \boldsymbol\xi}\ \frac12\lVert\mathbf w\rVert^2 + C\sum_i\xi_i \quad\text{s.t.}\quad y_i(\mathbf w^\top\mathbf x_i + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0.$$

• $0 < \xi_i \le 1$: inside the margin but correctly classified; $\xi_i > 1$: misclassified.
• $C$ trades margin width against violations: large $C$ → hard-ish margin, low bias, high variance; small $C$ → wide margin, more violations, smoother.

The hinge-loss view

Eliminating $\xi$ gives regularised empirical risk minimisation:

$$\min_{\mathbf w, b}\ \sum_i\max\big(0,\ 1 - y_i(\mathbf w^\top\mathbf x_i + b)\big) + \frac{1}{2C}\lVert\mathbf w\rVert^2.$$

The hinge loss is zero for points beyond the margin — which is why only support vectors matter — and grows linearly for violations (compare the log loss of logistic regression, which is never exactly zero).

The dual problem and support vectors

Using Lagrange multipliers $\alpha_i$:

$$\max_{\boldsymbol\alpha}\ \sum_i\alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,\mathbf x_i^\top\mathbf x_j \quad\text{s.t.}\quad 0 \le \alpha_i \le C,\ \ \sum_i\alpha_iy_i = 0.$$

• $\mathbf w = \sum_i\alpha_iy_i\mathbf x_i$; only support vectors have $\alpha_i > 0$ — the solution is sparse.
• The data appear only through inner products $\mathbf x_i^\top\mathbf x_j$ — the door to kernels.
• Prediction: $f(\mathbf x) = \operatorname{sign}\left(\sum_i\alpha_iy_i\,\mathbf x_i^\top\mathbf x + b\right)$.

The kernel trick

Map inputs to a feature space $\phi(\mathbf x)$ where the classes are separable, and replace every inner product by a kernel $K(\mathbf x, \mathbf z) = \phi(\mathbf x)^\top\phi(\mathbf z)$, computed without forming $\phi$.

A function is a valid kernel iff every Gram matrix $[K(\mathbf x_i, \mathbf x_j)]$ is symmetric positive semi-definite (Mercer's condition). Sums, products and positive scalings of kernels are kernels.

Practical notes

• Scale features — the margin is defined by distances.
• Tune $C$ (and $\gamma$ for RBF) by cross-validation on a log grid.
• Training costs roughly $O(n^2)$–$O(n^3)$ for kernel SVMs — fine for thousands of points, slow for millions (use linear SVMs or approximations there).
• Multi-class: one-vs-rest ($K$ classifiers) or one-vs-one ($\binom K2$ classifiers, majority vote).
• SVR (support vector regression) uses an $\varepsilon$-insensitive loss.

Quick revision