SVM原理与推导

1. 什么是SVM

SVM中文名是支持向量机，是一个判别模型，主要用于分类任务。SVM旨在在一堆数据点中，找出一个可以将数据点划分为两类的超平面，且要求超平面距离每一类的所有点尽量远。

2. 如何求解

定义一个超平面$\{w,b\}$，对于每一个数据点$(x_i,y_i)$，如果$y_i=1$，则要求$wx_i+b>0$，如果$y_i=-1$，则要求$wx_i+b<0$，所以可以总结成：

$$y_i(wx_i+b)>0$$

对于点$(x_i,y_i)$，向量$x_i$到超平面的距离为$\frac{|wx_i+b|}{\lVert w\rVert}$。SVM要求数据集的点到超平面的最短距离最大，即：

$$\max_{w,b}\min_{x}\frac{|wx+b|}{\lVert w\rVert}$$

对于一个超平面，既可以使用$\{w,b\}$表示，也可以使用$\{2w,2b\}$表示，总之$\{kw,kb\}$表示的是同一个平面，所以为了有唯一解，添加一个约束：

$$\min\{|wx+b|\}=1$$

所以SVM要求数据集的点到超平面的最短距离最大可表示为：

$$\max_{w,b}\frac{1}{\lVert w\rVert}$$

这等价于：

$$\min_{w} \frac{1}{2}\lVert w\rVert^2$$

所以SVM的数学模型可以表示为以下几个式子：

$$\min_{w} \frac{1}{2}\lVert w\rVert^2$$ $$st. y_i(wx_i+b) \ge 1,i=1,2,...$$

使用拉格朗日乘数法消除约束，可以得到：

$$L(w,b,\lambda)=\frac{1}{2}\lVert w\rVert^2+\sum_{i}{\lambda_i(1-y_i(wx_i+b))}$$ $$\lambda_i \ge 0,i=1,2,...$$

现在原问题等于求解：

$$\min_{w,b}\max_{\lambda}L(w,b,\lambda)$$ $$\lambda_i \ge 0,i=1,2,...$$

使用凸优化问题的对偶性质，转化成求对偶问题的解：

$$\max_{\lambda}\min_{w,b}L(w,b,\lambda)$$ $$\lambda_i \ge 0,i=1,2,...$$

使用$L(w,b,\lambda)$对$w,b$求导，令导数为0，可以得到:

$$w=\sum_{i}\lambda_iy_ix_i$$ $$\sum_{i}\lambda_iy_i=0$$

将其代入$L(w,b,\lambda)$可以得到一个关于$\lambda$的式子$f(\lambda)$：

$$f(\lambda)=\sum_{i}\lambda_i-\frac{1}{2}\sum_{i}\sum_{j}\lambda_i\lambda_jy_iy_jx_ix_j$$

现在要求解的问题等价于：

$$\max_{\lambda}f(\lambda)$$ $$st. \lambda_i\ge 0,i=1,2,...$$ $$\sum_{i}\lambda_iy_i=0$$

对$f(\lambda)$使用SMO算法，可以求出$\lambda$的近似解，通过$\lambda$求出$w,b$，从而完成SVM的参数求解过程。

3. 扩展

上述过程是使用SVM求解线性可分问题时的步骤，但很多时候，数据样本不是线性可分的。此时可以有两个技巧：核函数和松弛项。加入松弛项可以要求SVM不用对全部样本正确分类，只需要惩罚分类不正确的样本即可；加入核函数可以将非线性可分的样本映射到高维空间，增加特征，在高维空间可能线性可分。加入松弛项和核函数，SVM要求解的问题变成：

$$\min_{w,b,\xi} \frac{1}{2}\lVert w\rVert^2+C\sum_i\ \xi_i$$ $$st. y_i(w\hat{x}_i+b)\ge 1-\xi_i,i=1,2,...$$ $$\xi_i\ge 0,i=1,2,...$$

其中，$\hat{x}_i$表示将$x_i$映射到高维空间。同样地，使用拉格朗日乘子法求解，求导有：

$$w=\sum_{i}\lambda_iy_i\hat{x}_i$$ $$\sum_{i}\lambda_iy_i=0$$ $$\lambda_i+\mu_i=C,i=1,2,...$$

将上面的求导结果代入目标函数可以得到：

$$f(\lambda)=\sum_{i}\lambda_i-\frac{1}{2}\sum_{i}\sum_{j}\lambda_i\lambda_jy_iy_jK(x_i,x_j)$$

其中$K(x_i,x_j)$表示求高维空间$\hat{x}_i$和$\hat{x}_j$的内积。在这种情况下要求解的问题变为：

$$\max_{\lambda}f(\lambda)$$ $$st. 0\le\lambda_i\le C,i=1,2,...$$ $$\sum_{i}\lambda_iy_i=0$$

对上面的问题使用SMO算法求解，即可求出$\lambda$，进而求出$w$，$b$，最终完成对非线性SVM的求解。

还有SVR模型是SVM模型的回归版本，可以用于回归任务，算法思想是将$wx_i+b$当作回归值。和SVM不同，SVM是要求点在两个支持向量以外，而SVR则要求点在两个支持向量以内，超出的部分需要进行惩罚。在SVR中，两个支持向量与$wx_i+b$的距离并不是一个单位法向量的距离，而是由两个超参数设置的。求解的过程和SVM相似，就是列出式子，使用拉格朗日乘子法和SMO算法求解即可。

4. 优缺点

优点：
(1) 使用核函数和松弛量，SVM可以处理非线性情况
(2) SVM的边界选择只涉及到支持向量的样本，一定程度上提升了鲁棒性
(3) SVM在数据量小的情况下也能保持不错的效果
(4) SVM面对样本的增删改查，具有很好的鲁棒性，因为SVM只会受到支持向量的样本的影响。
缺点：
(1) 在对大数据量的样本学习时，SVM的学习需要较大资源
(2) 如果异常值数量多或者异常值异常程度大，SVM的效果会受到影响
(3) SVM在处理多分类问题时存在困难
(4) SVM受超参数的影响比较大，比如核函数的选取等等