Interactive demo · Probability and Statistical Inference · Chapter 22

The hard-margin SVM through its dual: weak duality closing in

The maximum margin hyperplane minimises ½‖a‖² subject to Yi(a0 + aTXi) ≥ 1 (Theorem 22.28). Its dual (22.40) maximises D(α) = ∑αi − ½∑∑αiαkYiYk⟨Xi, Xk⟩ over α ≥ 0 with ∑αiYi = 0. Here the dual is solved by sequential minimal optimisation: each step moves the two multipliers that most violate the optimality conditions. Every iterate brackets the optimal value P* = 1/(2ρ*²) (ρ* the largest margin): D(α) ≤ P* always, and once the direction w = ∑αiYiXi separates the data, rescaling it gives a feasible hyperplane with value U(α) ≥ P*. Step through and watch the bracket close; click a point to remove or restore it.

Data

Kernel K(x, x̃)

Gaussian width σ

Solve

Try these

The offset is chosen for each iterate to make the smallest margin as large as possible, a0 = −(minY=+1 si + maxY=−1 si)/2 with si = wTφ(Xi); the dotted curves are the levels ±γ of that smallest margin (±1 at the optimum). "Solve" stops when the largest violation is below 10−9, or declares the problem unbounded when ∑αi passes 104.

In the lecture notes