Maximum margin classifier

SSU

Given linearly separable data $T_m=\{(x,y)\in {\mathbb{R}}^d\times \{-1,+1\}\}$, finds a linear classifier

$$h(x;w,b)=\{\begin{array}{l}+1\text{if }⟨x,w⟩+b\ge 0\\ -1\text{if }⟨x,w⟩+b<0\end{array}$$

We can find infinitely many classifiers minimizing the distance between the hyperplane and training data $T_m$, given by

$$y_i\frac{⟨x,w⟩+b}{||w||},$$

which is an unsigned distance. Maximum margin classifier finds parameters $(w^{\ast },b^{\ast })$ by maximizing the margin, where margin is the minimal distance from hyperplane.

$$(w^{\ast },b^{\ast })=\text{arg}\underset{w\in {\mathbb{R}}^d\setminus \{0\},b\in \mathbb{R}}{\max }\left[\underset{i=1,\cdots ,m}{\min }{y}_i\frac{⟨x,w⟩+b}{||w||}\right]$$