SVM总结一

SVM算法认为图1中的分类器A在性能上优于分类器B，其依据是A的分类间隔比B要大。

这里涉及到第一个SVM独有的概念“分类间隔”。

在保证决策面方向不变且不会出现错分样本的情况下移动决策面，会在原来的决策面两侧找到两个极限位置（越过该位置就会产生错分现象），如虚线所示。虚线的位置由决策面的方向和距离原决策面最近的几个样本的位置决定。而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的最优决策面。

两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔。

这个真正的最优解对应的两侧虚线所穿过的样本点，就是SVM中的支持样本点，称为“支持向量”。

表面上看，我们优化的对象似乎是这个决策面的方向和位置。但实际上最优决策面的方向和位置完全取决于选择哪些样本作为支持向量。而在经过漫长的公式推导后，你最终会发现，其实与线性决策面的方向和位置直接相关的参数都会被约减掉，最终结果只取决于样本点的选择结果。

如果我们的决策面方程能够完全正确地对图2中的样本点进行分类，就会满足下面的公式

 (2.8)

如果我们要求再高一点，假设决策面正好处于间隔区域的中轴线上，并且相应的支持向量对应的样本点到决策面的距离为d，那么公式(2.8)就可以进一步写成：

 （2.9）

一个最优化问题通常有两个最基本的因素：1）目标函数，也就是你希望什么东西的什么指标达到最好；2）优化对象，你期望通过改变哪些因素来使你的目标函数达到最优。在线性SVM算法中，目标函数显然就是那个“分类间隔”，而优化对象则是决策面
 

 

这里是向量的模，表示在空间中向量的长度，就是支持向量样本点的坐标。就是决策面方程的参数。而追求的最大化也就是寻找的最大化。看起来我们已经找到了目标函数的数学形式（max）。

 （2.12）

###约束条件

1）并不是所有的方向都存在能够实现100%正确分类的决策面，我们如何判断一条直线是否能够将所有的样本点都正确分类？

2）即便找到了正确的决策面方向，还要注意决策面的位置应该在间隔区域的中轴线上，所以用来确定决策面位置的截距也不能自由的优化，而是受到决策面方向和样本点分布的约束。

3）即便取到了合适的方向和截距，公式(2.6)里面的不是随随便便的一个样本点，而是支持向量对应的样本点。对于一个给定的决策面，我们该如何找到对应的支持向量？

 

 （2.11）      

另外我们还可以尝试将公式(2.11)给出的约束条件进一步在形式上精练，把类别标签和两个不等式左边相乘，形成统一的表述：

 （2.13）

好了，到这里我们可以给出线性SVM最优化问题的数学描述了：

 （2.14）

显然，这是一个具有多个不等式约束条件的优化问题，其拉格朗日函数可以写为：

 （3.21）

这里  ，  。该拉格朗日函数最优化的原始问题和对偶问题分别为：

原始问题：  （3.22）

对偶问题：  （3.23）

我们对拉格朗日对偶问题进行求解，根据公式（3.23）首先求解

 （3.24）

为了求拉格朗日函数的极小值，分别令函数  对  求偏导，并使其等于0。

 （3.25）

 （3.26）

这里要特别提到的是，由于参数向量  是一个d维矢量，因此公式3.24是一个矢量方程，相当于d个标量方程。将公式（3.25）带入到公式（3.24）可以得到：

（3.27）

这里要特别提到的是，由于参数向量  是一个d维矢量，因此公式3.24是一个矢量方程，相当于d个标量方程。将公式（3.25）带入到公式（3.24）可以得到：

（3.27）

根据多项式乘法的基本规律（所有项和的积等于所有项积的和），不难明白（注意向量  是列向量）：

 （3.28）

所以公式(3.27)可以化简为：

 （3.29）

将(3.29)带入对偶问题的公式(3.23)，同时考虑公式(3.26)给出的约束，可以将SVM的优化问题转变为：

 （3.30）

 前面讲到，SVM的学习问题可以转化为下面的对偶问题：

       需要满足的KKT条件：

也就是说找到一组αi可以满足上面的这些条件的就是该目标的一个最优解。所以我们的优化目标是找到一组最优的αi*。一旦求出这些αi*，就很容易计算出权重向量w*和b，并得到分隔超平面了。

#####SMO求解

https://blog.****.net/zouxy09/article/details/17292011

 假设要求解下面的优化问题：

      在这里，我们需要求解m个变量αi，一般来说是通过梯度下降（这里是求最大值，所以应该叫上升）等算法每一次迭代对所有m个变量αi也就是α向量进行一次性优化。通过误差每次迭代调整α向量中每个元素的值。而坐标上升法（坐标上升与坐标下降可以看做是一对，坐标上升是用来求解max最优化问题，坐标下降用于求min最优化问题）的思想是每次迭代只调整一个变量αi的值，其他变量的值在这次迭代中固定不变。

最里面语句的意思是固定除αi之外的所有αj(i不等于j)，这时W可看作只是关于αi的函数，那么直接对αi求导优化即可。这里我们进行最大化求导的顺序i是从1到m，可以通过更改优化顺序来使W能够更快地增加并收敛。如果W在内循环中能够很快地达到最优，那么坐标上升法会是一个很高效的求极值方法。

SMO算法的思想和坐标下降法的思想差不多。唯一不同的是，SMO是一次迭代优化两个α而不是一个。为什么要优化两个呢？

假设我们首先固定除α1以外的所有参数，然后在α1上求极值。但需要注意的是，因为如果固定α1以外的所有参数，由上面这个约束条件可以知道，α1将不再是变量（可以由其他值推出），因为问题中规定了：

因此，我们需要一次选取两个参数做优化，比如αi和αj，此时αi可以由αj和其他参数表示出来。这样回代入W中，W就只是关于αj的函数了，这时候就可以只对αj进行优化了。

总结下来是：

重复下面过程直到收敛{

（1）选择两个拉格朗日乘子αi和αj；

（2）固定其他拉格朗日乘子αk(k不等于i和j)，只对αi和αj优化w(α);

（3）根据优化后的αi和αj，更新截距b的值；

}

#SMO算法的伪代码
#创建一个alpha向量并将其初始化为0向量
#当迭代次数小于最大迭代次数时(w外循环)
    #对数据集中每个数据向量(内循环):
    #如果该数据向量可以被优化：
        #随机选择另外一个数据向量
        #同时优化这两个向量
        #如果两个向量都不能被优化，退出内循环
#如果所有向量都没有被优化，增加迭代次数，继续下一次循环