Support Vector Machine: SVM

Support vector machine is particularly powerful and flexible class of the supervised learning algorithms for both classification and   regression.  Main aim in SVM is to find a separating hyperplane in such a way that it maximizes the margin on both sides of the hyperplane.  

Let us consider that we have data points belonging to two classes say w₁ and w₂. Let\[a^Tx +b=0\]

be equation of the hyperplane. Then for one class data points $a^Tx+b > 0$ and for other class data points   $ a^Tx+b>0 $ where b is bias (Position of the plane) and gives the orientation of the plane. 

Let M be margin and we want to maximize the margin subject  to some constraints.

i.e. \[y_i(x_i^T\beta+\beta_0 ) \geq N\]

for I = 1,2,3, . . . . . , N. We have the constraint that ||β|| should be one that because we do not want the solution to blow up arbitrarily.

Every data point must be at-least M distance away from hyper-plane.

So the condition will be\[\frac{y_i(x_i^T\beta+\beta_0 )}{||\beta||} \geq M\]
here i can remove condition that ||β||=1.

So here I can arbitrary set $||\beta|| = \frac{1}{M} $ then I can say that $ y_i(x_i^T\beta+\beta_0 ) \geq 1 $ and margin will be $M = \frac{1}{||\beta||}$.

Then I am left with constraint $ y_i(x_i^T\beta+\beta_0 )  $  that minimize $\frac{||\beta||^2}{2}$.

The constraints define the margin around the linear decision boundary of thickness $\frac{1}{||\beta||}$.

 Hence we choose β and β₀ to maximize its thickness. The Lagrangian Function that is to be minimized w.r.t. β  and β₀ is \[L_p = \frac{1}{2}||\beta||^2 - \Sigma_{i=1}^{N}\alpha_i[y_i(x_i^T\beta+\beta_0)-1]\]

Setting the derivatives to zero, we obtain: \[\beta = \Sigma_{i=1}^N \alpha_iy_ix_i,\]

\[0 = \Sigma_{i=1}^N \alpha_iy_i\]

Then substituting these values in the above equation(1), then we obtain the so-called WOLFE DUAL subject to constraint α_i ≥ 0. \[L_D = \Sigma_{i=1}^N \alpha_i - \frac{1}{2}\Sigma_{i=1}^N\Sigma_{k=1}^N\alpha_i\alpha_ky_iy_kx_i^Tx_k\]

The solution is obtained by maximizing L_D in the positive orthant.