支持向量机预测模型支持向量机( 七 )

SVM算法的核心就是设计最大化决策边界边缘的分类器，以保证最坏情况下泛化误差最小。
假设有一个包含个训练样本的二元分类问题，每个样本表示为一个二元组, 其中，对应于第i个样本的属性集（一个样本有多个属性/特征）,设y有-1和1两个类别，则一个线性分类器的决策边界可以写成如下形式：
其中的为参数，是法向量（垂直于决策边界）的向量，代表着超平面的方向，而代表超平面与原点之间的距离（可以用一次函数的公式来理解）。
为什么一定会垂直于决策边界呢？我们设有两个点是决策边界上的两点，那么有：
二者相减有：
因为肯定是平行于决策边界的，那么为了保证内积为0，肯定要垂直于决策边界。
根据以上的决策边界，则肯定有：
如果上方的点是1类，下方是-1类，则有：
如果我们能得到，那么就可以用这个公式对未知点进行预测分类。代入公式，如果就是1类，反之则为-1类。
接下来我们的任务就是如何求这两个参数，首先，既然是求最大边缘超平面，我们要把决策边界的边缘算出来。
根据上图，考虑那些离决策边界最近的方形和圆形，我们可以得到两个平行的超平面表示如下：
决策边界的边缘就是这两个超平面的距离。
参考上图的，不难得出边缘为：
其中是w的2范数。
很显然，我们想要让这个最大，那么就要让最小。
于是，接下来我们的求参数目标就明确了。
由于肯定是非负的，我们可以改写一下
这个式子，让它变成求的最小值。
既然要求最小值，就需要有另外一个约束条件，否则是没办法求的，我们来看之前总结的线性SVM分类器的公式：
由于和是决策边界的两个超平面，我们从上图中可以看出，所有的点（除了这两个超平面经过的点以外，经过的点是离决策边界最近的点），都肯定有和。
我们把y引入进来，那么这两个式子就能合到一起写为：
注意不要和之前总结的公式中的弄混，那个条件是最终预测分类的公式，也就是表明只要在决策边界的上方就可以进行分类，而现在的=1是在已知训练集的情况下求模型的参数。
综合以上的式子，我们可以得到求参数的基本式：
目标函数是二次的，而约束在参数和上是线性的，因此这是一个凸优化问题，不存在局部优化的问题。
求这一套公式的最小值，需要用到拉格朗日乘数法，这个我也不是很明白，就按照百度百科的定义往里套：
虽然我们这里的附加条件是大于等于1的，不过不妨改写一下试试，则有：
其中的就是拉格朗日乘子，理论上来说，拉格朗日乘子可以为任何值。
如果约束条件是=0的话，我们就可以直接对和求偏导数，让他们等于0，就能求得参数。
但是目前条件并不是等于0的，而是大于等于0的。
处理不等式约束一种方法就是变换成一组等式约束，根据KKT条件，可以限制拉格朗日乘子飞赴，把之前的约束变换为：
该约束表明，除非训练样本满足方程，否则拉格朗日乘子必须为0 。
结合上面展示决策边界和超平面的图，我们可以想到，满足这个方程的样本，肯定都在决策边界生成的两个超平面上。这些样本处的拉格朗日乘子肯定够大于0，而其他样本的拉格朗日乘子，肯定等于0，因此问题得到简化。因为参数的确定仅依赖于这些在超平面上的样本。
这些在超平面上的样本，被称作支持向量，这也就是支持向量机的命名缘由。
有了以上的修改后的约束，我们可以在对和求偏导，并让他们等于0.
我们已知，这个时候的和是有满足条件的最优解的，把这两个式子代入原公式，就能得到的最小值（当然此时因为不知道拉格朗日乘子，我们是求不出来的），代入公式可得：
该函数叫做对偶拉格朗日函数。
用这个函数，就是把之前求w和b的公式变换成了求拉格朗日乘子的公式，同时需要注意，这个式子中是求拉格朗日对偶函数的最大化问题。
我们可以用二次规划法或者SMO方法来求拉格朗日乘子。
二次规划算法比较通用，但是计算量比较大，SMO算法的核心就是把复杂的式子变换成比较简易的之后，用二次规划来计算。
SMO的基本思路是：先固定之外的所有参数，然后求上的极值，由于存在约束，如果固定了之外的其他变量，则能求出。
那么对偶函数里有两个λ，我们就可以固定这两个λ之外的参数，之后求解。

支持向量机预测模型 支持向量机( 七 )

秒懂生活扩展阅读

支持向量机预测模型支持向量机( 七 )