Generalized Optimal Hyperplane

Following Optimal Hyperplane, we have generalized optimal hyperplane that deals with non-separable cases.

Actually, we just need to add a slack / error variable ${\xi }_i\ge 0$ to relax the constraint:

$$y_i((\mathbf{w}\cdot {\mathbf{x}}_i)+b)\ge 1-{\xi }_i,i=1,2,\dots ,l$$

We then define a function $F_{\sigma }(\xi )={\sum }_{i=1}^l{\xi }_i^{\sigma }\sigma >0$ , which reflects how much of the original constraints are violated.

Generalized Optimal Hyperplane

\begin{align} &\min \Phi(\mathbf{w}, \boldsymbol{\xi}) = \frac{1}{2}(\mathbf{w}\cdot \mathbf{w}) + C\left( \sum_{i=1}^l \xi_{i} \right) \quad \text{w.r.t } \mathbf{w} \\ &\text{s.t. } y_{i}((\mathbf{w} \cdot \mathbf{x}_{i}) + b) \geq 1-\xi_{i}, \quad i=1,2,\dots,l

\end{align}

Where parameter $C$ controls the penalty on errors.

I am kinda too tired to derive everything like we did in Optimal Hyperplane, but we need to use Kuhn Tucker theorem as well, but with the error term ${\xi }_i$.

Here are the revised theorem:

Primal Problem

\begin{align} &\min \psi(\mathbf{w}, \boldsymbol{\xi}) = \frac{1}{2}(\mathbf{w}\cdot \mathbf{w}) + C\left( \sum_{i=1}^n \xi_{i} \right) \\ &\text{s.t. } y_{i}[(\mathbf{w}\cdot \mathbf{x}_{i})+b] -1 + \xi_{i} \geq 0, \quad \xi_{i} \geq 0, \quad i=1,..,l

\end{align}

Dual Problem

$$\underset{\alpha }{\max }W(\alpha )=\sum _{i=1}^l{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^l{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)$$

s.t. ${\sum }_{i=1}^l{y}_i{\alpha }_i=0,$ and $0\le {\alpha }_i\le C,i=1,\dots ,l$

The decision function solution:

$$f(\mathbf{x})=\text{sgn}\left(\sum _{i=1}^n{\alpha }^{\ast }{y}_i({\mathbf{x}}_i\cdot \mathbf{x})+b^{\ast }\right)$$