Support Vector Machine

A support vector machine finds the boundary that leaves the widest possible gap between two classes. With a kernel, that boundary can bend into curves and rings.

The idea

Picture building a road between two villages and making it as wide as you can without bulldozing any houses. The houses touching the kerb fix where the road goes; every other house could move and nothing would change. Those kerb houses are the support vectors.

A kernel lets the SVM measure similarity in a richer way, as if the points had been lifted into extra dimensions where a straight road works. Back on the flat canvas, that straight road shows up as a curve.

How it learns

  1. Give every point a weight αi\alpha_i, starting at zero.
  2. Pick a pair of points that break the optimality conditions.
  3. Adjust their two weights together so the margin improves while the constraints still hold (this is SMO).
  4. Repeat until a few full passes make no changes.
  5. Points left with non-zero weight are the support vectors; only they shape the boundary.

Reading the picture

The solid line is the decision boundary. With Show margins on, two fainter lines mark the edges of the street, where the decision score is +1+1 and −1-1. Support vectors are the points on or inside those edges, and the stats count them.

The background colour shows which side you are on, shaded by how far from the boundary. With the Linear kernel the stats also report the margin width.

Try this

  1. Switch to Separable and set Kernel to Linear. Drag a point that is far from the boundary: nothing changes. Drag a support vector and the whole street moves.
  2. On Circles, compare Linear with RBF (Gaussian). The RBF boundary wraps neatly around the inner ring.
  3. With RBF, push Gamma (γ\gamma) up to 50. Each point gets a tiny bubble of influence and the boundary turns blobby and overfitted.
  4. Lower CC (softness) to 0.05 on Moons. The street widens and lets some points sit inside it. Raise CC to 100 and it fights every mistake.

The maths

Decision

f(x)=∑iαiyiK(xi,x)+b,y^=sign⁡f(x)f(x) = \sum_i \alpha_i y_i K(x_i, x) + b, \quad \hat{y} = \operatorname{sign} f(x)

Constraints

0≤αi≤C,∑iαiyi=00 \le \alpha_i \le C, \quad \sum_i \alpha_i y_i = 0

RBF kernel

K(x,x′)=exp⁡(−γ∥x−x′∥2)K(x, x') = \exp\left(-\gamma \lVert x - x'\rVert^2\right)

Polynomial kernel

K(x,x′)=(γ x⊤x′+1)dK(x, x') = (\gamma\, x^\top x' + 1)^d

Margin width

2∥w∥,w=∑iαiyixi(linear kernel)\frac{2}{\lVert w\rVert}, \quad w = \sum_i \alpha_i y_i x_i \quad (\text{linear kernel})

Strengths and weaknesses

Good at

  • Maximum margin gives good generalisation.
  • Kernels give flexible boundaries without explicit features.
  • Only the support vectors matter at prediction time.

Struggles with

  • CC and γ\gamma need careful tuning.
  • Training scales poorly to very large datasets.
  • No native probabilities, and this version is two-class only.