机器学习之软间隔支持向量机（机器学习技法） - 好文

为什么要软间隔SVM

硬边距SVM <http://blog.csdn.net/qq_34993631/article/details/79326926>的过拟合

对于硬边距SVM产生过拟合的原因主要有两点：①我们选用的模型复杂度太高 ②我们坚持要将资料严格的分开。如下：

从直觉来说Φ1虽然有一些犯错的地方但是它的模型复杂度较低不容易过拟合。我们不在执着于将资料严格分开（容忍一些小错误），我们想要的是较低的复杂度的模型
来降低过拟合的危险。

软边距SVM的诞生

在pocket算法中我们的思想是找到犯错误最小的模型，它不执著与将资料严格的分开，同时pocket是一个NP-Hard问题。硬边距SVM要求所有的资料点都分对，而且还要选择最胖的边距。
我们试图将原来的SVM放松一点让它能够容忍一些错误，所以我们就将pocket算法与硬边距SVM结合起来。

在新的算法中我们要求：

①在不犯错的资料上还保持原来硬边距SVM的要求。

②在犯错的资料上我们不在追究。

但是光有这两点还是不够的，因为②既然做错没有关系那么我们的算法会表现的很差。因此我们又加了一个参数C放在我们的最小化的函数中用来调节我们更在意：

①在对的资料上有较宽的边界即使多犯一点错误。

②我们不想犯错误即使是让边界更窄一点也行。

当C较大的时候我们更在意②，当C较小时我们更在意①。于是就诞生了软边距SVM。

软间隔SVM问题的变换

软间隔SVM算法的问题

将硬边距SVM与pocket算法结合起来的软间隔SVM算法如上图，在实际解决起来会遇到一些麻烦：

①在软间隔SVM算法中含有boolean（是非）运算，所以最小化的式子不是线性的，所以不能使用QP（二次规划）的工具来解决它。

②在软间隔SVM算法中我们只能定性的知道是否犯错，但事实上我们更加注重于对错误的定性分析我们需要知道小错还是大错。

软间隔问题的变换

我们不在将错误进行非黑即白的分类，而是将错误的大小封装到ξ这个变量中。ξ越大说明这个资料点离我们的边界越远。

改版之后的最优化问题中包含ξ项的是一次式，总体来说是二次式。我们终于能够用QP的工具距解决这个问题了。这个问题也变得简单了不是一个NP-Hard的问题了。

ξ的几何意义

如图黑色圆圈圈起来的点就是一个犯错误的点，它与边界的距离就是犯错误的值的大小也就是ξ的大小。

C的意义更加明确：

大C：我们宁愿边界小一点也要尽量不犯错误（ξ小一点）。

小C：我们宁愿犯一点错误（ξ大一点）也要边界胖一点。

变量与约束条件

变量：

在维度转换之后会到达d+1维，再加上N个错误衡量的变量ξ。

约束：

①我们要记录犯的错误离我们想要的边界隔多远。

②我们要求ξ>0我们才记录错误,ξ<0我们就不计错误了。

软间隔SVM的拉格朗日对偶问题

软间隔SVM的拉格朗日函数

软间隔SVM的原始问题如下：

然后使用拉格朗日乘子法将带有条件的问题转化成拉格朗日函数如下：

同时我们实行一个特殊的最佳化过程让拉格朗日函数具有选择在满足条件下才计算的功能，最佳化过程如下：

这里的α和β都是拉格朗日乘子。

用KKT条件去解决拉格朗日对偶问题

在最佳解的条件下α，b，W，ξ都会满足一些关系，这些关系就叫做KKT条件。

①满足最原始标准问题的条件。

②满足对偶问题的基本条件。

③最佳化解时候（梯度为0）b与W与ξ的条件。

④SVM对偶问题中的隐含条件。
利用在最佳解时梯度为0，也就是ξ的偏导数等于0会得到如下结果：

我们可以将β用C-α来代替这样我们就可以消掉β这个参数。通过这个条件进一步推导我们会将ξ也消掉得到上图中的式子，将其简化如下：

这个式子与硬边距对偶问题 <http://blog.csdn.net/qq_34993631/article/details/79332870>
的解法相同，只是有不同的约束条件而已。将问题具体化如下：

我们可以将这个问题丢到一个QP（二次规划）的工具里去解决，同时在此情况下我们任然有N个变量，由于0<=α<=C所以约束条件的个数变成了2N+1。

核函数软间隔SVM

基本步骤与遇到的问题

软间隔的SVM的解决与硬边距的SVM一样，而且比硬边距SVM更加灵活。求解的基本步骤如下：

由于相比以前的SVM软间隔SVM多了一些参数所以b的算法与以前不同。计算步骤如下：

在KKT条件下我们希望带入一个支持向量的值来求出b，但是求解b的值需要ξ的帮助而想要求出ξ的值需要b的帮助这样的话就形成了死锁什么值都求不出来。恰好我们有另外一个条件的支撑向量（α<C的情况下，我们称之为自由支持向量），这种支持向量的ξ值为0。这样我们可以利用自由支持向量来求出b的值。

在求出b之后我们可以得到ξ的值。这样就求出了我们的软间隔SVM，由于在实务上我们通常就使用软间隔的SVM所以我们直接叫它为SVM。

SVM的表现

在上图中我们看到即使是软间隔的SVM在模型复杂度高的情况下也会发生过拟合现象。所以我们需要谨慎的选择参数比如说（γ，C）。

α的物理意义

根据α值的不同会得到不同的资料点：

①0<α<C

这个时候ξ的值为0，1-y(WZ + b) = 0这些点也就是支持向量。（图中的□）

②0 =α

这个时候ξ的值为0，也就是这些点没有违反边界。但它们不是支持向量机（不满足0<α）。

③α = C

这个时候ξ等于1-y(WZ + b)也就是资料点与边界相违反的值，这是犯错误的资料点。（图中的△）

通过交叉验证法选择模型
选择方法
通常我们判断一个模型表现好坏的工具就是模型检验（validation）。比如通过带入不同的参数会得到不同的模型用validation检验如下：

我们试图对我们的交叉验证的错误函数（Ecv）进行优化，但是Ecv不是一个凸的易于优化的函数。所以我们只能分别的进行检验最后选择出最好的模型。

一个好的过滤器

在对SVM模型进行N折交叉验证时会有错误率Eloocv<= (支持向量个数/样本总数)证明如下：

SVM只与支持向量有关与其它的资料点无关，所以有两种情况：

①当前用于检验的不是支持向量

那么去掉这个资料点的模型与原来的模型一模一样，所以对于当前点的预测不会出错。

②当前用于检测的是支持向量

那么去掉支持向量的这个模型与原来的模型会不一样，所以对于这个点的预测可能会错可能会对。E = 0或1总的来说是E<=1。

总结：只有支撑向量当做验证资料的时候模型才会犯错，所以总的来说会有错误率Eloocv<= (支持向量个数/样本总数)
。事实上这只是一个上限我们并不能准确的知道错误率是多少。有了这个结论我们可以做安全检查，直接将那些支撑向量的占比过大的过滤掉，这样会省一些力气。

热门工具换一换