Support Vector Machine

Definition

Hard-Margin Support Vector Machine

Assume that we have a learning set $\mathcal{L}=\{({\mathbf{x}}_i,y_i)|i=1,2,\dots ,n\},{\mathbf{x}}_i\in {\mathbb{R}}^p,y_i\in \{-1,+1\}$ Suppose given two classes of data can separate by a Hyperplane without error. The hyperplane is called a separating hyperplane (SH)

Define $d_{-}:=\underset{i}{\min }\mathrm{dist}(\text{SH},{\mathbf{x}}_i),{\mathbf{x}}_i\in \{{\mathbf{x}}_i|y_i=-1\}$, $d_{+}:=\underset{i}{\min }\mathrm{dist}(\text{SH},{\mathbf{x}}_i),{\mathbf{x}}_i\in \{{\mathbf{x}}_i|y_i=+1\}$, and the margin of SH $d:=d_{-}+d_{+}$ A SH which maximizes its margin ($d$) is called an optimal separating hyperplane (OSH). To find OSH, set linear constraints ${\beta }_0$ and $\mathbf{\beta }$ satisfy $\{\begin{array}{ll}{\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i\ge +1& y_i=+1\\ {\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i\le -1& y_i=-1\end{array}\iff y_i({\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i)\ge +1,i=1,\dots ,n$ where the minimum distance $1$ is arbitrary and may differ.

Let $H_{+}:{\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i=+1$ and $H_{-}:{\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i=-1$. Then the points lying either on $H_{+}$ or $H_{-}$ are called support vectors. If ${\mathbf{x}}_{+}\in H_{+}$ and ${\mathbf{x}}_{-}\in H_{-}$, then $d_{+}=d_{-}=\frac{1}{||\mathbf{\beta }||}$ and $d=\frac{2}{||\mathbf{\beta }||}$

Therefore, the OHS can be obtained by a Convex Optimization problem. It can be solved by Method of Lagrange Multipliers $L_P(\mathbf{\beta },{\beta }_0,\mathbf{\alpha })=\frac{1}{2}||\mathbf{\beta }|{|}^2-{\sum }_{i=1}^n{\alpha }_i[y_i({\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i)-1]$ with $0\le \mathbf{\alpha }$

By Duality of optimization problem, we have the dual optimization problem is defined as ${\max }_{\mathbf{\alpha }}{L}_D(\mathbf{\alpha })\text{subject to}0\le \mathbf{\alpha },{\mathbf{\alpha }}^{⊺}\mathbf{y}=0$ where $\mathbf{H}=(y_i{y}_j{\mathbf{x}}_i^{⊺}{\mathbf{x}}_j)$

And the dual Lagrangian function is defined as $L_D(\mathbf{\alpha })={\sum }_{i=1}^n{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^n{\sum }_{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^{⊺}{\mathbf{x}}_j=1_n^{⊺}\mathbf{\alpha }-\frac{1}{2}{\mathbf{\alpha }}^{⊺}\mathbf{H}\mathbf{\alpha }$

The primal optimization problem is convex and satisfies KKT Conditions. Thus, holds Strong Duality and the solution of the dual problem is the same as the primal problem.

The optimal parameter is obtained as $\hat{\mathbf{\beta }}=\sum _{i\in \text{sv}}{\hat{\alpha }}_i{y}_i{\mathbf{x}}_i,{\hat{\beta }}_0=\frac{1}{|\text{sv}|}\sum _{i\in \text{sv}}\left(\frac{1-y_i{\mathbf{x}}_i^{⊺}\hat{\mathbf{\beta }}}{y_i}\right)$ where $\text{sv}$ is an index set of support vectors

The optimal hyperplane can be written as $\hat{f}(\mathbf{x})={\hat{\beta }}_0+{\hat{\mathbf{\beta }}}^{⊺}\mathbf{x}$ and the classification rule is given by $C(\mathbf{x})=\mathrm{sign}(\hat{f}(\mathbf{x}))$

Soft-Margin Support Vector Machine

$\min \frac{1}{2}||\mathbf{\beta }|{|}^2+C\sum _{i=1}^n{\xi }_i\text{subject to}{y}_i({\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i)\ge +1-{\xi }_i,{\xi }_i\ge 0,i=1,\dots ,n$ where $C$ is the regularization parameter, and $\mathbf{\xi }$ is called a slack variable. If ${\xi }_i=0$, the point is out of margin. On the other hand, if ${\xi }_i>0$, then the point is within the margin.

The Lagrangian primal function is defined as $L_P(\mathbf{\beta },{\beta }_0,\mathbf{\alpha },\mathbf{\eta })=\frac{1}{2}||\mathbf{\beta }|{|}^2+C\sum _{i=1}^n{\xi }_i-{\sum }_{i=1}^n{\alpha }_i[y_i({\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i)-(1-{\xi }_i)]-{\sum }_{i=1}^n{\eta }_i{\xi }_i$ with $0\le \mathbf{\alpha }$ and $0\le \mathbf{\eta }$.

And the dual function is defined as $L_D(\alpha )={\sum }_{i=1}^n{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^n{\sum }_{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^{⊺}{\mathbf{x}}_j=1_n^{⊺}\mathbf{\alpha }-\frac{1}{2}{\mathbf{\alpha }}^{⊺}\mathbf{H}\mathbf{\alpha }$ with ${\mathbf{\alpha }}^{⊺}\mathbf{y}=0$ and $0\le \mathbf{\alpha }\le C{1}_n$ where $\mathbf{H}=(y_i{y}_j{\mathbf{x}}_i^{⊺}{\mathbf{x}}_j)$

and the dual optimization problem is defined as ${\max }_{\mathbf{\alpha }}{L}_D(\mathbf{\alpha })\text{subject to}{\mathbf{\alpha }}^{⊺}\mathbf{y}=0,0\le \mathbf{\alpha }\le C{1}_n$ The primal optimization problem is convex and satisfies KKT Conditions. Thus, holds Strong Duality and the solution of the dual problem is the same as the primal problem.

The optimal parameter is obtained as $\hat{\mathbf{\beta }}=\sum _{i\in \text{sv}}{\hat{\alpha }}_i{y}_i{\mathbf{x}}_i,{\hat{\beta }}_0=\frac{1}{|\text{sv}|}\sum _{i\in \text{sv}}\left(\frac{1-y_i{\mathbf{x}}_i^{⊺}\hat{\mathbf{\beta }}}{y_i}\right)$ where $\text{sv}$ is an index set of support vectors.

Non-Linear Support Vector Machine

Non-linear SVM finds an optimal separating Hyperplane in high-dimensional feature space $\mathcal{H}$. It accomplished by the kernel trick. The kernel trick is that instead of computing inner products in $\mathcal{H}$, compute them using a non-linear Kernel Function in input space.

Hard-Margin Non-Linear Support Vector Machine

If the data can be separated in $\mathcal{H}$, then the dual optimization problem is defined as ${\max }_{\mathbf{\alpha }}\left(1_n^{⊺}\mathbf{\alpha }-\frac{1}{2}{\mathbf{\alpha }}^{⊺}\mathbf{H}\mathbf{\alpha }\right)\text{subject to}0\le \mathbf{\alpha },{\mathbf{\alpha }}^{⊺}\mathbf{y}=0$ where $\mathbf{H}=(y_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j))$

The optimal separating Hyperplane in the $\mathcal{H}$ is $\hat{f}(\mathbf{x})={\hat{\beta }}_0+\sum _{i\in \text{sv}}{\hat{\alpha }}_i{y}_{i}K({\mathbf{x}}_i,{\mathbf{x}}_j)$

and the decision rule is defined as $C(\mathbf{x})=\mathrm{sign}(\hat{f}(\mathbf{x}))$

Soft-Margin Non-Linear Support Vector Machine

In the non-separable case, the dual problem is defined as ${\max }_{\mathbf{\alpha }}\left(1_n^{⊺}\mathbf{\alpha }-\frac{1}{2}{\mathbf{\alpha }}^{⊺}\mathbf{H}\mathbf{\alpha }\right)\text{subject to}0\le \mathbf{\alpha }\le C{1}_n,{\mathbf{\alpha }}^{⊺}\mathbf{y}=0$ where $\mathbf{H}=(y_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j))$

The optimal separating Hyperplane in the $\mathcal{H}$ is $\hat{f}(\mathbf{x})={\hat{\beta }}_0+\sum _{i\in \text{sv}}{\hat{\alpha }}_i{y}_{i}K({\mathbf{x}}_i,{\mathbf{x}}_j)$

and the decision rule is defined as $C(\mathbf{x})=\mathrm{sign}(\hat{f}(\mathbf{x}))$