Hard-Margin SVM

Hard-margin SVM

Hard-margin SVM is a type of support vector machine that aims to find the maximum margin hyperplane that perfectly separates the two classes without allowing any misclassification. It’s useful when the dataset is linearly separable and there are no outliers.

Linearly separable case

Given a binary classification dataset $D=\{(\bold x_1, y_1), (\bold x_2, y_2), \dots,(\bold x_n, y_n)\}$, where $\bold x_i \in \R^d$ and $y_i \in \{-1, 1\}$, if a hyperplane $\bold w^T\phi(\bold x)=0$ exists that separates the two classes, the dataset is said to be linearly separable in the feature space defined by the mapping $\phi$. We’ll assume for now that the dataset $D$ is linearly separable. The goal is to find the hyperplane with a maximum margin by optimizing the following objective:

$$\max_{\bold w}\bigg[\frac{1}{\|\bold w\|}\min_{i}\big(y_i\bold w^T\phi(\bold x_i)\big)\bigg]$$

The direct optimization of the above objective can be very complex. Here’s a derivation of an equivalent optimization problem which is easier to solve:

$$\begin{array}{rl}{\displaystyle \underset{\mathbf{w}}{\max }\left[\frac{1}{\mathrm{\parallel }\mathbf{w}\mathrm{\parallel }}\underset{i}{\min }\right(y_i{\mathbf{w}}^T\varphi ({\mathbf{x}}_i)\left)\right]}& {\displaystyle =\underset{\mathbf{w}}{\max }\frac{1}{\mathrm{\parallel }\mathbf{w}\mathrm{\parallel }}\left[\underset{i}{\min }\right(y_i{\mathbf{w}}^T\varphi ({\mathbf{x}}_i)\left)\right]}\\ {\displaystyle }& {\displaystyle =\underset{\mathbf{w},\gamma }{\max }\frac{\gamma }{\mathrm{\parallel }\mathbf{w}\mathrm{\parallel }}s\mathrm{.}t\mathrm{.}{y}_i{\mathbf{w}}^T\varphi ({\mathbf{x}}_i)\ge \gamma {\mathrm{\forall }}_i}\\ {\displaystyle }& {\displaystyle =\underset{\mathbf{w},\gamma }{\max }\frac{1}{\mathrm{\parallel }\mathbf{w}\mathrm{/}\gamma \mathrm{\parallel }}s\mathrm{.}t\mathrm{.}{y}_i(\mathbf{w}\mathrm{/}\gamma {)}^T\varphi ({\mathbf{x}}_i)\ge 1{\mathrm{\forall }}_i}\\ {\displaystyle }& {\displaystyle =\underset{{\mathbf{w}}^{{}^{\mathrm{\prime }}}}{\max }\frac{1}{\mathrm{\parallel }{\mathbf{w}}^{{}^{\mathrm{\prime }}}\mathrm{\parallel }}s\mathrm{.}t\mathrm{.}{y}_i({\mathbf{w}}^{{}^{\mathrm{\prime }}T}\varphi ({\mathbf{x}}_i)\ge 1{\mathrm{\forall }}_i}\\ {\displaystyle }& {\displaystyle =\underset{{\mathbf{w}}^{{}^{\mathrm{\prime }}}}{\min }\mathrm{\parallel }{\mathbf{w}}^{{}^{\mathrm{\prime }}}\mathrm{\parallel }s\mathrm{.}}\end{array}$$ ...