Optimal Hyperplane

In Perceptron, we learn that there might be multiple solutions. To decide which one is best, we have the optimal hyperplane.

For sample set $(x_1,y_1),\dots ,(x_l,y_l),x\in {\mathbb{R}}^d,y\in \{+1,-1\}$, that can be separated by a hyperplane $(\mathbf{w}\cdot \mathbf{x})+b=0$, the optimal hyperplane is the function $f(\mathbf{x})=\text{sgn}((\mathbf{w}\cdot \mathbf{x})+b)$ with maximal margin between the samples of the two classes (basically most distance between the two classes), that separate the two classes without error.

Formalizing this, we want to fix the scale by setting it to 1: $(\mathbf{w}\cdot {\mathbf{x}}_i)+b\ge 1.\text{if }{y}_i=1$ $(\mathbf{w}\cdot {\mathbf{x}}_i)+b\le -1.\text{if }{y}_i=-1$ We can do this because we can just freely absorb a scalar to $\mathbf{w}$ and $\mathbf{x}$.

Optimal Hyperplane

\begin{aligned}

&\min \Phi(\mathbf{w}) = \frac{1}{2}(\mathbf{w}\cdot \mathbf{w}) \text{ w.r.t }\mathbf{w}, \ &\text{s.t. } y_{i}(\mathbf{w} \cdot \mathbf{x}{i})+b \geq 1, \quad \text{if }i=1, 2,\dots,l\ &\text{for training samples } (y{1}, \mathbf{x}{1}),\dots,(y{l}, \mathbf{x}_{l}), \quad y \in {-1, 1} \end{aligned}

In plain English, $\Phi (\mathbf{w})=\frac{1}{2}(\mathbf{w}\cdot \mathbf{w})$ is equivalent to maximizing the margin and $y_i(\mathbf{w}\cdot {\mathbf{x}}_i)+b\ge 1$ is the requirement that there is no misclassification.

We have to use Langragian equation to get the solution. This is convex optimization problem. We must find the saddle point.

$$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\underset{\alpha }{\max }L(\mathbf{w},b,\alpha )=\frac{1}{2}(\mathbf{w}\cdot \mathbf{w})-\sum _{i=1}^l{\alpha }_i\left\{\begin{array}{c}[{\mathbf{x}}_i\cdot \mathbf{w}+b]y_i-1\end{array}\right\}\\ & \text{where }{\alpha }_i^0\ge 0,i=1,\dots ,l\end{array}$$

Differentiating with $\mathbf{w}$ and $b$ gives us:

$$\begin{array}{rl}& \frac{\partial L({\mathbf{w}}_0,b_0,{\alpha }^0)}{\partial b}=0\Rightarrow \sum _{i=1}^l{\alpha }_i^0{y}_i=0\\ & \frac{\partial L({\mathbf{w}}_0,b_0,{\alpha }^0)}{\partial \mathbf{w}}=0\Rightarrow {\mathbf{w}}_0=\sum _{i=1}^l{y}_i{\alpha }_i^0{\mathbf{x}}_i\end{array}$$

From here, we get 3 observations

1. For optimal hyperplane, ${\alpha }_i^0$ is:

$$\sum _{i=1}^l{\alpha }_i^0{y}_i=0,{\alpha }_i^0\ge 0,i=1,\dots ,l$$

2. ${\mathbf{w}}_0$ must be the linear combination of the training samples:

$${\mathbf{w}}_0=\sum _{i=1}^l{y}_i{\alpha }_i^0{\mathbf{x}}_i,{\alpha }_i^0\ge 0,i=1,\dots ,l$$

3. Only support vectors have non-zero coefficient of ${\alpha }_i^0$ in ${\mathbf{w}}_0$.
   • This is based on the Kuhn Tucker theorem.

Optimal Hyperplane (Solution)

$${\mathbf{w}}_0=\sum _{SVs}{y}_i{\alpha }_i^0{\mathbf{x}}_i,{\alpha }_i^0\ge 0$$

We sum over $SVs$ only because they are the only non-zeros (3rd observation).

Plugging this back to ${\mathbf{w}}_0^T+b_0$, we get the decision function

$$f(\mathbf{x})=\text{sign}\left(\sum _{SVs}{y}_i{\alpha }_i^0({\mathbf{x}}_i\cdot \mathbf{x})+b_0\right)$$

The threshold $b_0$ can be obtained from the support vectors of the two classes. We pick a support vector $x^{\ast }(+1)$ from the +1 class and $x^{\ast }(-1)$ from the -1 class.

$$\begin{array}{rl}& y=+1,{\mathbf{w}}_0^T{x}^{\ast }(1)+b_0=1\Rightarrow b_0=1-{\mathbf{w}}_0^T{\mathbf{x}}^{\ast }(1)\\ & y=-1,{\mathbf{w}}_0^T{x}^{\ast }(-1)+b_0=-1\Rightarrow b_0=-1-{\mathbf{w}}_0^T{\mathbf{x}}^{\ast }(-1)\end{array}$$

Then we take average (to reduce noise) to find $b_0$.

$$b_0=-\frac{1}{2}[({\mathbf{w}}_0\cdot {\mathbf{x}}^{\ast }(1))+({\mathbf{w}}_0\cdot {\mathbf{x}}^{\ast }(-1))]$$