SVM原理深入理解

以前看统计学习方法这本书虽然将其中的公式都推导了一遍，但是仍然没有理解其中的算法原理，如今面试发现频频被问到，而且非常深入，准备花点时间好好捋一捋，现在发现对一个算法的深入理解比起简单的调用和之前的理解来说太难了，而且包括知乎上的讲解也很难有一篇文章能够将原理讲的明明白白的，读起来总是觉得欠缺点什么，自己将学习过程记录下来，或是借鉴别人的思想，或是自己的理解，希望能即简明又尽诉其理。

感知机原理浅析

感知机是二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，也就是说找出一个超平面，使得这个超平面能够将正负样本分在其两侧。
给定数据集

$$T=\{(x_1,y_1),...(x_N,y_N)\}\\ 其中 x_i \in R^n,y_i \in \{+1,-1\}$$

即对于某个超平面$S$

$$w \cdot x +b=0$$

能够将数据集中的正实例点和负实例点完全正确的划分到超平面的两侧，即对所有的$y_i$=+1的实例i，有$w \cdot x_i+b>0$，对所有$y_i=-1$的实例i，有$w \cdot x_i+b<0$，可以看出感知机的目的是找出一个超平面，将两类样本尽可能的正确分到超平面的两侧，也就是说尽量少的误分类，那么如何衡量呢，即损失函数是什么呢，这里使用的是点到直线的距离，可以知道误分类的样本特点是：

$$-y_i(w \cdot x_i +b)>0$$

即所有误分类点到超平面S的距离和为：

$$-\frac{1}{||w||}\sum_{x_i \in M}y_i(w \cdot x_i+b)$$

其中M为误分类点的集合，而感知机的损失函数并没有考虑$\frac{1}{||w||}$，其损失函数如下：

$$L(w,b)=-\sum_{x_i \in M}y_i(w \cdot x_i+b)$$

至于为什么不考虑$\frac{1}{||w||}$，我觉得感知机的目的只是区分正负样本，而$\frac{1}{||w||}$可以看成常数，和正负没有关系，而且计算量也会增大，$\frac{1}{||w||}$的含义在SVM中会有解释。
那么有了损失函数，进行梯度求导更新就能解出最优解：

$$\frac{\partial L(w,b)}{\partial w} = -\sum_{x_{i} \in M}{y_{i} x_{i}} \\ \frac{\partial L(w,b)}{\partial b} = -\sum_{x_{i} \in M}{y_{i}} \\ w^{t+1} = w^{t} + \sum_{x_{i} \in M}{y_{i} x_{i}} \\ b^{t+1} = b^{t} + \sum_{x_{i} \in M}{y_{i}}$$

至于梯度更新部分会涉及到批梯度下降，随机梯度下降等等就不展开了。

SVM优化问题引出

SVM是建立在感知机的基础上的，这一点和LR也是相似的【这一块以后也会进行详细的对比】，感知机只是找出一个可以分离正负样本的超平面就可以了，但是问题是如果有多个可以将正负样本分离的超平面该怎么选择，或者说存在一个噪声点，可能会导致超平面的误判，这里就涉及到模型的鲁棒性和泛化能力。SVM的目的是找出能够正确划分训练数据集并且几何间隔最大的分离超平面。如下图所示：

几何间隔：对于给定的数据集 T 和超平面$w\cdot x+b=0$，定义超平面关于样本点$\left( x_i,y_i \right)$ 的几何间隔为

$$\gamma _i=y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert} \right)$$

超平面关于所有样本点的几何间隔的最小值为

$$\gamma =\underset{i=1,2...,N}{\min}\gamma _i$$

也就是让$\gamma$最大，且所有的点都满足其几何间隔大于$\gamma$:

$$\underset{\boldsymbol{w,}b}{\max}\ \gamma \\ s.t.\ \ \ y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert} \right) \ge \gamma \ ,i=1,2,...,N$$

这里需要讲一下函数间隔，函数间隔就是不带$||w||$，即：

$$\hat{\gamma _i}=y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right)$$

函数间隔的变化对优化问题没有影响，也就是说我们关心的间隔是$||w||$，即可以令$\hat{\gamma _i}=1$，那么优化问题就变为：

$$\underset{\boldsymbol{w,}b}{\min}\ \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2 \\ y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1,\ i=1,2,...,N$$

如上，SVM要优化的问题出来了，接下来就是如何进行优化了

拉格朗日乘子法

对于无约束的优化问题来说：

$$\min f(x)$$

直接求导，让偏导数为0，解方程组即可，对于一般的问题直接使用这种方程求解析解就可以了，但是也有很多问题解不出解，所以需要用到梯度下降法，牛顿法，坐标下降法的数值迭代算法。

进一步，对于满足一定约束条件下的最小化目标函数，比如下面：

$$\min f(x)\\ s.t. \,\,h(x)=0$$

这个问题就不能单独的去求f(x)的极值点了，假设f(x)和h(x)如下图所示，f(x)显示的是投影在平面上的等值线

取得极值点的情况只有一种，也就是h(x)和f(x)相切，因为如果相交，说明后面一定还有更小/大的值，这样就有如下条件：

$$∇f(x,y)=λ∇h(x,y)$$

然后和原来非方程h(x)=0联立起来就是在高等数学上看到的拉格朗日解法了。
那么更进一步，如果问题中既有等式约束，又有不等式约束呢，如下：

$$\min f(x)\\ s.t.\,\,h(x)=0\\ \,\,\,\,\,\,\,\,g(x)≤0$$

即可行域由原来的一条线变成了一块区域，那么能取得到的极值点的地方可能有两种情况：

1. 在h(x)和等值线相切的地方
2. f(x)的极值点本身就在可行域里面

如下图：

这里的h(x)理解为可行区域的边界，可以是h(x)本身，也可以是g(x)=0的情况。

对于第一种情况，不等式约束就变成等式约束了，对$f(x)+λh(x)+μg(x)$用拉格朗日乘子法：

$$∇f(x)+λ∇h(x)+μ∇g(x)=0\\ h(x)=0\\ g(x)=0\\ μ≥0$$

这部分解释$μ≥0$没有看懂。。。
对于第二种情况，不等式约束就相当于没有，对$f(x)+λh(x)$用拉格朗日乘子法：

$$∇f(x)+λ∇h(x)=0\\ h(x)=0\\ g(x)≤0$$

综合可得：

$$∇f(x)+λ∇h(x)+μ∇g(x)=0\\ μg(x)=0\\ μ≥0\\ h(x)=0\\ g(x)≤0$$

这就是KKT条件

对偶问题

一个优化问题可以使用两个角度来考虑，即主问题和对偶问题，在约束最优化问题中，常常利用拉格朗日对偶问题将原始问题转换为对偶问题，通过解对偶问题来得到原始问题的解。这样做是因为对偶问题的复杂度往往低于主问题。
这一部分看不懂，详见参考4
摘抄一句话吧：对于一般的优化问题，强对偶性通常不成立，但是若主问题是凸优化问题，如式中 f(x) 和 $g_j(x)$ 均为凸函数，$h_i(x)$为仿射函数，且其可行域中至少有一点使不等式约束严格成立，则此时强对偶性成立。

SVM优化问题求解

SVM最优化问题使用前面提到的拉格朗日乘子法，得到：

$$L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =\frac{1}{2}\lVert \boldsymbol{w} \rVert ^2-\sum_{i=1}^N{\alpha _i\left( y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1 \right)}$$

SVM满足前面说道的强对偶性(满足KKT条件，且优化问题是凸优化问题)，即有：

$$\underset{\boldsymbol{w,}b}{\min}\underset{\alpha _i\ge 0}{\max}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right)= \underset{\alpha _i\ge 0}{\max}\underset{\boldsymbol{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right)$$

即将主问题（最小最大）变为对偶问题（最大最小），接下来求解对偶问题：
对$L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right)$ 中的$\boldsymbol{w}$ 和 b 的求偏导，并令其等于0，可得

$$\boldsymbol{w}=\sum_{i=1}^N{\alpha _iy_i\boldsymbol{x}_{\boldsymbol{i}}} \\ \sum_{i=1}^N{\alpha _iy_i}=0$$

将以上两个等式带入拉格朗日目标函数，消去$\boldsymbol{w}$和 b ， 得

$$L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}-\sum_{i=1}^N{\alpha _iy_i\left( \left( \sum_{j=1}^N{\alpha _jy_j\boldsymbol{x}_{\boldsymbol{j}}} \right) \cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) +}\sum_{i=1}^N{\alpha _i} \\ =-\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}+\sum_{i=1}^N{\alpha _i}$$

即

$$\underset{\boldsymbol{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =-\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}+\sum_{i=1}^N{\alpha _i}$$

然后解外层，即：

$$\underset{\boldsymbol{\alpha }}{\max}\ -\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}+\sum_{i=1}^N{\alpha _i} \\ s.t.\,\,\,\,\sum_{i=1}^N{\alpha _iy_i}=0 \\ \,\,\,\,\,\,\,\,\alpha _i\ge 0,\ i=1,2,...,N$$

把目标式子加一个负号，将求解极大转换为求解极小

$$\underset{\boldsymbol{\alpha }}{\min}\ \frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}-\sum_{i=1}^N{\alpha _i} \\ s.t.\,\,\,\,\sum_{i=1}^N{\alpha _iy_i}=0 \\ \,\,\,\,\,\,\,\,\alpha _i\ge 0,\ i=1,2,...,N$$

至于这个问题该如何求解呢，SMO算法

SMO算法

这里只是简单提一下，详细参考8或其它。
由前面的推导我们得到如下表达式：

$$min \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y^{i}y^{j}K(X^{i}.X^{j})-\sum_{i=1}^{m}\alpha_{i}\\ s.t. \sum_{i=1}^{m}\alpha_{i}y^{i}=0\\ 0\le \alpha_{i}\leq C$$

SMO在整个二次规划的过程总共干了两件事：

• 选取一对参数$\left( \alpha _i,\alpha _j \right)$
• 固定$\vec \alpha$向量的其他参数，将$\left( \alpha _i,\alpha _j \right)$代入上述表达式进行求最优解获得更新后的$\left( \alpha _i,\alpha _j \right)$

SMO不断执行这两个步骤直至收敛。
我们最终优化的是权重w，因为w的值是受$\alpha _i$的控制的，因此需要求解$\alpha _i$。

问题又来了，为什么要使用SMO算法，一般的优化问题不都是使用梯度下降吗？
可以使用梯度下降训练SVM，不过SVM的目标函数是一个凸优化问题，利用凸优化理论求解训练速度更快。(参考9)
又有问题了，既然使用SMO算法更快，那么为什么SVM和LR相比，都说LR更快，LR到底快在哪里呢？

软间隔

实际情况下几乎不存在完全线性可分的数据，为了解决这个问题，引入软间隔这个概念，即允许某些点不满足约束：

$$y_j\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{j}}+b \right) \ge 1-\xi _i$$

采用hinge损失，将原优化问题改写为

$$\underset{\boldsymbol{w,}b,\xi _i}{\min}\ \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2+C\sum_{i=1}^m{\xi _i} \\ s.t.\,\,\,\, y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1-\xi _i \\ \,\,\,\,\xi _i\ge 0\ ,\ i=1,2,...,N$$

即对每个松弛变量$\xi _i$，支付一个代价$\xi _i$，其中C>0称为惩罚参数。C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。
具体就不展开了。。。

核函数

上面在求解SVM的最优问题都是针对线性可分的，对于输入空间中非线性分类问题，可以通过非线性变换将它转换为某个维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。在解完对偶问题后，目标函数中只涉及到样本之间的内积，而核函数就是使用某种映射替换其内积。
其中$K\left( x,z \right)$是一个函数，或正定核，意味着存在一个从输入空间到特征空间的映射 $\phi \left( x \right)$ ，对任意输入空间中的 x,z ，有

$$K\left( x,z \right) =\phi \left( x \right) \cdot \phi \left( z \right)$$

也就是将原来的

$$\underset{\boldsymbol{\alpha }}{\min}\ \frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}-\sum_{i=1}^N{\alpha _i}$$

变换为：

$$\underset{\boldsymbol{\alpha }}{\min}\ \frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_jK\left( \boldsymbol{x}_{\boldsymbol{i}},\boldsymbol{x}_{\boldsymbol{j}} \right)}}-\sum_{i=1}^N{\alpha _i}$$

上面就是核函数的定义，将一个低维空间映射到高维空间。
这里有两个问题需要解决：

1. 为什么核函数要将低维空间映射到高维空间，核函数的目的，也就是为什么使用核函数后线性可分
2. 核函数如何选择

关于低维向高维扩展，也就是增加维度信息(便于超平面区分)
知乎上有一篇讲的还算比较直观，如下：
kernel 的作用就是把你的数据集上下左右前后拉扯揉捏，直到你一刀下去正好把所有的0分到一边，所有的1分到另一边。这个上下左右前后拉扯揉捏的过程就是你的kernel. 不管是svm还是cnn，都可以这样来解释[摘抄自5]

比如上面这个例子，右边的红蓝点无法直接一刀切开。那如果你把所有的蓝色点往下拉，把所有的红色点往上推，那你就可以一刀把他们从中间劈开了。那这个推拉的过程就是kernel干的事。
在这个例子里，这个函数如下

$$[x_1,x_2]=[x_1,x_2,x_1^2+x_2^2]$$

再有一个例子如下图：

将其映射到三维空间上，新坐标如下计算：

$$x_1=x_1^2\\ x_2=x_2^2\\ x_3=\sqrt{2}x_1x_2$$

映射后的结果如下图：

SVM中常用的核函数

【补充LibSVM和LibLinear
LIBSVM是一套完整的SVM模型实现，用户可以在LIBSVM中使用核函数来训练非线性分类器，也可以使用更基础的线性SVM，而LIBLINEAR是一个针对线性分类场景而设计的工具包，除了支持线性SVM外，还支持线性Logistic Regression
区别如下：

1. 凡是确定使用线性分类器的场景，一定使用LIBLINEAR而不是LIBSVM
2. 如果样本量较大，比如达到10万以上规模，LIBSVM很难处理了，如果线性分类器的效果实在不好，只能采用人工构造特征+LIBLINEAR方式，或者采用其他分类器，如神经网络，随机森林
3. 对于高维稀疏数据，典型的如文本向量空间表示，一般采用线性分类器
4. 对于样本量和维度都不算太大的问题，且没有对预测的效率过分要求，都可以使用LIBSVM，一般其能够达到更高的精度

】

这里参考6翻译过来[英文文章的严谨性中文简直无法相比…，以后再也不看中文的了]
SVM要求优化如下问题：

其中$x_i$通过使用函数$\phi$被映射到更高维度的空间，$K(x_i,x_j)=\phi(x_i)^T\phi(x_j)$被叫做核函数，一般核函数有如下几种：

关于如何选取核函数有如下几条：

1. 如果特征比较大，我们不需要将数据映射到一个更高维的空间，因此，非线性映射不能提高其表现，使用线性核就足够了，我们仅需要选择参数C。
2. 当特征数量远大于样本数量时（经常出现在生物信息学中），同时使用RBF和linear kernels，得出的结论是两者是可比较的，因此不需要去映射数据。
3. 当特征数量和样本数量都很大时（经常出现在文档分类），一般使用LIBLINEAR，因为LIBSVM非常耗时。
4. 当样本数量远大于特征数量时，经常会将数据映射到高维空间中去，如果你更喜欢使用线性核，可以使用LIBLINEAR

SVM n问

1. SVM的损失函数？
   合页损失函数：

   $$\sum_{i=1}^{N}max(0,1-y_i(wx_i+b))+\lambda ||w||^2$$

2. 支持向量机(support vector machine)为什么叫支持向量机
   从损失函数的角度出发，如上式，可以看到并不是所有的样本都参与损失函数的计算，当样本点在间隔外就不参与计算，这就是支持向量机的来源

3. SVM为什么比LR慢

思考

其实即便是这样花很多时间去看SVM这一部分，仍然感觉有好多东西无法理解，而且越往深里看，需要掌握的东西越多，先攻克一点，后续慢慢琢磨

1. 为什么SVM要用拉格朗日，能不能直接找出损失函数，使用梯度下降法求解不就完了
2. 最后需要使用SMO算法的那步优化的式子中的x内积的含义是什么，为什么要在那一步使用核函数？
3. 。。。

参考

1. 统计学习方法
2. 支持向量机—-原理篇
3. 真正理解拉格朗日乘子法和KKT条件
4. SVM详解(1)SVM基本型
5. 机器学习有很多关于核函数的说法，核函数的定义和作用是什么
6. A Practical Guide to Support Vector Classification
7. LIBSVM与LIBLINEAR
8. SMO算法是干什么的？有什么作用？
9. 用梯度下降训练SVM会有什么问题？