硬间隔支持向量机 （线性可分的支持向量机）

最大间隔分类器

我们目标是

max ~margin(w, b) \\
s.t. ~~~y_i(w^Tx_i + b) > 0

可知

margin(w, b) = \mathop{min}\limits_{w, b, x_i} ~distance(w, b, x_i) = \mathop{min}\limits_{w, b, x_i}\frac{|w^Tx_i + b|}{||w||}
\\
\Rightarrow max ~margin(w, b) = \mathop{max}\limits_{w,b}\mathop{min}\limits_{x_i}\frac{y_i(w^Tx_i + b)}{||w||}
\\
s.t.~~~ y_i(w^Tx_i + b) > 0
\\
\Rightarrow \mathop{max}\limits_{w,b}\frac{1}{||w||}\mathop{min}\limits_{x_i}{y_i(w^Tx_i + b)}
\\
s.t. ~~~y_i(w^Tx_i + b) > 0
\
\Rightarrow \exists\gamma > 0~~~
s.t.~~~\mathop{min}\limits_{x_i, y_i}{y_i(w^Tx_i + b) = \gamma}

\gamma是一个常数 可以缩放为1

\Rightarrow \mathop{max}\limits_{w, b}\frac{1}{||w||}
\\
s.t. ~~~y_i(w^Tx_i + b) \geq 1
\\
\Rightarrow \mathop{min}\limits_{w, b}\frac{1}{2}||w||^2
\\
s.t. ~~~y_i(w^Tx_i + b) \geq 1 \Leftrightarrow{1 - y_i(w^Tx_i + b) \leq 0}

这是一个凸优化问题
利用拉格朗日乘数法及其拓展KKT条件

L(w, b, \lambda) = \frac{1}{2}ww^T + \sum\limits_{i=1}^{N}\lambda_i(1 - y_i(w^Tx_i + b))
\\
\Rightarrow \mathop{min}\limits_{w,b}\mathop{max}\limits_{\lambda}{L(w,b,\lambda)}
\\
s.t. ~~~\lambda_i \geq 0

对偶问题

\mathop{max}\limits_{\lambda}\mathop{min}\limits_{w,b}{L(w, b, \lambda)}
\\
s.t. ~~~\lambda_i \geq 0 ~~~~~~\sum\limits_{i=1}^{N}\lambda_iy_i = 0
\\
\frac{\partial{L}}{\partial{b}} = 0 \Rightarrow \sum\limits_{i=1}^{N}\lambda_iy_i = 0
\\
\frac{\partial{L}}{\partial{w}} = 0 \Rightarrow w - \sum\limits_{i=1}^{N}\lambda_iy_ix_i = 0

代入得

L(w,b,\lambda) = \frac{1}{2}{\sum\limits_{i=1}^{N}\lambda_iy_ix_i}^T{\sum\limits_{i=1}^{N}\lambda_iy_ix_i} - {\sum\limits_{i=1}^{N}\lambda_iy_i(\sum\limits_{j=1}^{N}\lambda_iy_ix_i)^Tx_i} \ = -\frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\lambda_i\lambda_jy_iy_jx_i^Tx_j + \sum\limits_{i=1}^{N}\lambda_i
\\
\Rightarrow \mathop{max}\limits_{\lambda}-\frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\lambda_i\lambda_jy_iy_jx_i^Tx_j + \sum\limits_{i=1}^{N}\lambda_i
\\
s.t. ~~~\lambda_i \geq 0 ~~~~~~\sum\limits_{i=1}^{N}\lambda_iy_i = 0

KKT条件

\frac{\partial{L}}{\partial{w}} = 0 ~~~\frac{\partial{L}}{\partial{b}} = 0
\\
\lambda_i(1-y_i(w^T_i + b)) = 0
\\
\lambda_i \geq 0
\\
1-y_i(w^T_i + b) \leq 0

软间隔支持向量机

线性可分的支持向量机对线性不可分的数据是不适用的。我们需要修改硬间隔最大化，使其成为软间隔最大化。

假设训练数据集不是线性可分的，数据中有一些特异点，去除这些点后，剩下的样本是线性可分的。

线性不可分意味着某些样本点(x_i, y_i)不能满足函数间隔等于等于1的约束条件，为了解决这个问题，我们对每个样本点(x_i, y_i)引入松弛变量\xi_i \geq 0

使约束条件变为

y_i(wx_i + b) \geq 1 - \xi_i

目标函数变为

\frac{1}{2}{||w||}^2 + C\sum\limits_{i=1}^{N}\xi_i

线性不可分的线性支持向量机的学习问题变成如下凸二次优化问题

\mathop{min}\limits_{w,b,xi}~\frac{1}{2}{||w||}^2 + C\sum\limits_{i=1}^{N}\xi_i

s.t.y_i(wx_i + b) \geq 1 - \xi_i ~~~~~ \xi_i \geq 0

对偶问题

\mathop{max}\limits_{lambda}-\frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\lambda_i\lambda_jy_iy_jx_i^Tx_j + \sum\limits_{i=1}^{N}\lambda_i
\
s.t. \sum\limits_{i=1}^{N}\lambda_iy_i=0 ,~~~
0 \leq \lambda_i \leq C

设\lambda^* = ({\lambda_1}^*, {\lambda_2}^*, \cdots, {\lambda_N}^*)^T 是对偶问题的一个解，若存在一个分量{\lambda_i}^*, 0 \leq {\lambda_i}^* \leq C

则原始问题的解可按下式求得

w^* = \sum\limits_{i=1}^{N}\lambda_iy_ix_i
\
b^* = y_j - \sum\limits_{i=1}^{N}{y_i{\lambda_i}^*\langle x_i, x_j \rangle}