相关内容
SMO算法求解支持向量机(2) )。
用SMO算法求解支持向量机(SVM ) pythony源代码(3)
支持向量机是一种万能的分类器算法，简称SVM。 他一般是二分类模型，其基本模型被定义为特征空间上间隔最大的线性分类器，其学习策略间隔最大化，最终可以转化为凸二次规划问题的求解。
了解SVM的基本原理1后，您会发现SVM的基本概念我们的目的是根据几何间隔计算“最大间隔”。
1.1函数间隔
对于任意一个数据点(x，y )，|wT*x b|都可以表示从点x到超平面wT*x b=0的距离，可以根据wT*x b的符号与类别标记y的符号是否一致来判断分类是否正确。 因此，可以用y(wt*xb )的正负性判定或表示分类的正确性)，正因此引出了正确的)函数间隔(functional margin )的概念。 将函数间隔定义如下：
超平面所有采样点(xi，yi )的函数间隔最小值是超平面训练数据集的函数间隔(mini(I=1，…n )实际上，函数间隔就是几何上点到面的距离公式。
1.2几何间距
对于给定点x，假设垂直于超平面投影的对应点为x0，w为垂直于超平面的向量，即样本x与分类间隔之间的距离。 请参考下图。
从数据点到超平面的几何间距定义如下：
超平面所有采样点(xi，yi )的几何间隔最小值是超平面训练数据集的函数间隔(min(I=1，…n )几何间隔就是函数间隔除以||w||，可以理解成函数间隔的归一化。
1.3定义最大间隔分类器最大间隔分类器
如上所述，超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大需要选择能够使该“间隔”值最大化的超平面，该间隔为最大间隔。
函数间隔不适合测量最大化间隔的值。 因为超平面固定后，可以通过均匀缩放w的长度和b的值来达到任意大小。 但是，除几何间隔外，放大缩小w和b时，其值不变。 因此，几何间隔仅随超平面的变化而变化，最大间隔分类超平面中的“间隔”用几何间隔来衡量其中，最大间隔分类器(maximum margin classifier )的目标函数可定义如下：
(I=1，2，…，n ) ) )。
根据前面的分析，“使样本中离超平面最近的点到超平面的距离最远”是指转换为公式后的条件：
根据前面的讨论，即使在超平面固定的情况下，的值也可以根据w的变化而变化。 为了简化计算，固定为1(如果公式的两边实质上相同，则wt=wt(=wt/，b=b )=b/)，最大间隔分类器的目标函数进化如下
式中，s.t .在subject to的意义上，推导约束条件。
求出的最大值相当于(这样变换是为了求解上的方便，系数1/2都是为了之后利用导数求出最大值上的方便，没有实质意义)的最小值，因此上述目的函数) w从分母变成分子，成为分子
1.3 SVM优化对偶问题
对于SVM，如上所述，其主探测器的格式如下：
用同样的方法引入拉格朗日乘子，可以得到以下拉格朗日函数：
然后，对l(w、b、)分别求出w和b的极值。 也就是说，l(w，b，)相对于w和b的梯度为l/w=0和l/b=0，http://www.Sina.com /。 现在，求解导数为0的公式如下。
然后代入拉格朗日函数，如下所示。
这就是双探针(如果我们知道，我们就知道w。 相反，如果我们知道w，也可以知道)。 此时，我们求出对的极大，是关于对偶变量的优化问题(变量w、b消失，只有)。 得到最佳后，同样代入上式导出w和b*，最终得到分离超平面和分类决策函数。 也就是说，是训练了SVM。 新的示例x到来后，可以分为以下几类：
其中，许多i实际上为0，也就是说，w仅仅是小样本的线性加权值。 这种“稀疏”表示实际上被认为是KNN数据压缩的版本。 也就是说，今后新分类的样本首先根据w和b进行线性运算，根据求出的结果是大于还是小于0来判断是正例还是负例。 现在有i，不需要要求w，只要将新来的样本与训练数据中的所有样本内积和即可。 也有人说，和前面所有的样本进行运算是不是太费时间了。 否则，KKT条件得到的不仅仅是支持向量的i为0，其他情况下i为0。 因此，我们只需要求出新来的样本和支持向量的内积来进行运算即可。 这种写法经常为下面提到的核函数(kernel )铺好。 如下图所示。
1.4、容错驰豫因子Outlier
p>我们之前讨论的情况都是建立在样本线性可分的假设上，在这种情况下可以找到近乎完美的超平面对两类样本进行分离。但如果遇到下面这两种情况呢？这时候就找不到一条直线来将他们分开了，那这时候怎么办呢？就因为他们的不完美改变我们原来完美的分界面会不会得不偿失呢？但又不得不考虑他们，那怎样才能折中呢？对于上面说的这种偏离正常位置很远的数据点，我们称之为 outlier，它有可能是采集训练样本的时候的噪声，也有可能是某个标数据的大叔打瞌睡标错了，把正样本标成负样本了。那一般来说，如果我们直接忽略它，原来的分隔超平面还是挺好的，但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，同时 margin 也相应变小了。当然，更严重的情况是，如果出现右图的这种outlier，我们将无法构造出能将数据线性分开的超平面来。
为了处理这种情况，我们允许数据点在一定程度上偏离超平面。也就是允许一些点跑到H1和H2之间，也就是他们到分类面的间隔会小于1。如下图：
具体来说，原来的约束条件就变为：
这时候，我们在目标函数里面增加一个惩罚项，新的模型就变成（也称软间隔）：
引入非负参数ξi后（称为松弛变量），就允许某些样本点的函数间隔小于1，即在最大间隔区间里面，或者函数间隔是负数，即样本点在对方的区域中。而放松限制条件后，我们需要重新调整目标函数，以对离群点进行处罚，目标函数后面加上的第二项就表示离群点越多，目标函数值越大，而我们要求的是尽可能小的目标函数值。这里的C是离群点的权重，C越大表明离群点对目标函数影响越大，也就是越不希望看到离群点。这时候，间隔也会很小。我们看到，目标函数控制了离群点的数目和程度，使大部分样本点仍然遵守限制条件。
这时候，经过同样的推导过程，我们的对偶优化问题变成：
此时，我们发现没有了参数ξi，与之前模型唯一不同在于αi又多了αi<=C的限制条件。需要提醒的是，b的求值公式也发生了改变，改变结果在SMO算法里面介绍。
文中部分文字图片参考了http://blog.csdn.net/suipingsp/article/details/41645779/
https://www.cnblogs.com/nolonely/p/6541527.html