Calculus×Computing
ES

Support vector machines

Level AdvancedDifficulty ★★★★★Application⌖ Open in the map

What is it?

Find the separating hyperplane with the largest margin: a convex quadratic program whose Lagrangian dual involves the data only through dot products — hence the kernel trick.

Formulas

min⁡w,b 12∥w∥2,yi(w⋅xi+b)≥1  ∀i\min_{w,b}\ \tfrac12\norm w^2, \qquad y_i(w\cdot x_i + b) \ge 1\ \ \forall i
max⁡α∑iαi−12∑i,jαiαjyiyj k(xi,xj),αi≥0, ∑iαiyi=0\max_\alpha \sum_i\alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\,k(x_i, x_j), \quad \alpha_i \ge 0,\ \sum_i\alpha_i y_i = 0
the dual: only kernels k(xi,xj)k(x_i, x_j) appear

The mathematics behind it

  • Convexity and concavity★★★★★fundamental

    Training an SVM is a convex quadratic program: a unique global optimum.

  • Lagrange multipliers★★★★★fundamental

    The SVM dual is obtained with Lagrange multipliers; only points with αi>0\alpha_i > 0 (support vectors) matter.

  • KKT conditions★★★★★fundamental

    Complementary slackness is why only the support vectors (points on or inside the margin) get non-zero weight.

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.

↑ ↓ to navigate · ↵ · Esc