支持向量机SVM——原理及相关数学推导系列二

作者: 7NIC7 | 来源:发表于2019-04-11 22:30 被阅读0次

（一）前言

在系列一中，我们推导的是一个线性可分的SVM，也可以叫做hard margin SVM；但是事情往往不是那么简单，有的时候两个类是很难区分的，或者即使可以线性区分，但是受到噪声点的影响，SVM分割线为了能够正确对噪声点的分类从而偏离了正确的位置，会使得模型过拟合。基于这些原因，我们希望让SVM可以容忍错误，也就是soft margin SVM——线性不可分的SVM

（二）线性不可分的SVM

基本原理

如果将系列一的推导弄懂了，这里只是对于原来的定义2.3（系列一）一个非常简单的加工。即加上了一个松弛变量 $\xi_i$ ，这个代表我们对错误的容忍度。
1）当 $\xi_i = 0$ ，代表着这个点没有被SVM分错，且在分割线外边（也有可能在分割线上）；
2）当 $0 <\xi_i <1$ ，代表着这个点跑到了分割线里面了，但是SVM也是正确分对了的；
3）当 $\xi_i>1$ ，代表着这个点被分错了。
$C$ 是一个权衡分割线宽度和分错点个数的一个参数，当 $C$ 较大时，意味着我们希望SVM尽量不要犯错；当 $C$ 较小时，我们希望SVM的分割线宽度越大越好。

定义2.1
$\begin{align*} &\min_{w,b}\ \frac{1}{2}w^Tw + C\sum_{i=1}^{N}\xi_i\\ s.t. \ &y_i(w^Tx_i + b) \geq 1 - \xi_i \\ &\xi_i \geq 0 \end{align*}$
其中， $i=1,2,\dots,N$

对偶问题

转为对偶问题和系列一的步骤基本一致，这里就省略一些步骤啦。

定义2.2
$\begin{align*} \max_{\alpha_i \geq 0,\beta_i \geq 0 }\min_{w,b,\xi_i}L = \max_{\alpha_i \geq 0,\beta_i \geq 0 }\min_{w,b,\xi_i} \frac{1}{2}w^Tw+C\sum_{i=1}^{N}\xi_i \\ + \sum_{i=1}^{N}\alpha_i\left[1-\xi_i - y_i(w^Tx_i + b)\right] -\sum_{i=1}^{N}\beta_i\xi_i \end{align*}$
解内部的最小化问题就是求解其导数，并让导数为0。
$\begin{align*} &\frac{\partial L}{\partial w} = w - \sum_{i=1}^{N}\alpha_iy_ix_i = 0 \\ & \frac{\partial L}{\partial b} = -\sum_{i=1}^{N}\alpha_iy_i = 0 \\ & \frac{\partial L}{\partial \xi_i} = C - \alpha_i - \beta_i = 0 \\ \end{align*}$
将式子代入带定义2.2中，我们将得到定义2.3。
定义2.3
$\min_{C\geq \alpha \geq 0}\frac{1}{2}\sum_{j=1}^{N}\sum_{i=1}^{N}\alpha_i y_i \alpha_j y_j x_i^T x_j - \sum_{i=1}^{N}\alpha_i$

如果你还记得系列一中我们推导出来的对偶式子，你一定会惊叹于数学的玄妙，这个不就是和线性可分的SVM一模一样的式子吗，只不过对于 $\alpha$ 的限制增加了，从原来的 $\alpha \geq 0$ 到这里的 $C \geq \alpha \geq 0$ 。
当然这里依旧需要满足KKT条件：

1. $y_i(w^T x_i + b) \geq 1 - \xi_i$
2. $\alpha \geq 0$ ， $\beta \geq 0$ ， $\xi \geq 0$
3. $w= \sum_{i=1}^{N}\alpha_iy_ix_i$ , $\sum_{i=1}^{N}\alpha_iy_i =0$ , $\alpha_i+\beta_i = C$
4. $\alpha_i(1-\xi_i - y_i(w^T x_i + b)) = 0$ ， $\beta_i\xi_i = 0$

Bounded Vector 以及超平面求解

实际上，根据KKT中第4个条件，我们可以将数据分为三个部分：

$\alpha_i = 0$ 。那么可以推出 $\xi_i = 0$ ， $y_i(w^T x_i + b) > 1$ ，说明这些数据是被分类正确，且在分割线外的，可以叫做Free Vector。
$0<\alpha_i<C$ 。推出 $\xi_i=0$ ， $y_i(w^T x_i + b) = 1$ ，说明这些数据被正确分类，但是在分割线上。
$\alpha_i = C$ 。推出 $\xi_i = 1 - y_i(w^T x_i + b)$ ，其中 $\xi_i$ 度量了这个点犯错误的程度，可能是分类正确的点但是在分割线内，也可能是分类错误的点。
那么上面的2、3中的数据就是Bounded Vector。这些点在求解参数的时候是有用的。
参数 $w$ 的求解很简单，在KKT条件3中也指明了。下面主要说明参数 $b$ 的求解，这个和线性可分的情形稍有不同，若数据都在第3类中，求解参数 $b$ 会很复杂。但是大部分的情况下，总会有数据在第2类中，那么 $b = y_i - w^Tx_i$ 。