Hard-Margin SVM

In this lesson, we explore Hard-margin SVM, a type of support vector machine designed to perfectly separate two classes with a maximum margin hyperplane. Hard-margin SVM is ideal for datasets that are linearly separable and free of outliers. We’ll start by understanding the concept of a linearly separable dataset and the idea of maximizing the margin. Then, we’ll carefully derive the equivalent optimization problem, discuss the critical role of support vectors, and implement hard-margin SVM using cvxpy to visualize the decision boundary and the support vectors.

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 is complex. Here is the derivation of the equivalent, simplified optimization problem:

$$\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{.}t\mathrm{.}}\end{array}$$ ...