林轩田机器学习技法第四讲-Soft-Margin Support Vector Machine

前面我们学习了Linear Hard-Margin Support Vector Machine、Dual Support Vector Machine和Kernel Support Vector Machine，解决了某些问题。但是这些都是硬间隔支持向量机，即要求每一个点都不能分错，这就可能会导致模型的复杂度提高，从而出现过拟合。而这一讲讲的是，如果我们允许某一些点可以分错，允许噪声的存在，这样的话模型就不必为了最好的效果提高复杂度，从而避免出现过拟合

分析可知导致出现过拟合的原因主要有两个：所使用的模型过于的复杂，转换的新的域的维度过高；所要求的模型效果太好，即不能有分错的点。比如有下图所示的数据分布，如果我们使用线性的形式来划分的话，虽然有一个点被分错了，但是其余的点都是分对的，效果是很不错的。但如果非要要求不能有一个点分错，就可能会使用右图所示的高阶多项式的模型，看似都分对了，但是模型过于复杂了，很容易出现过拟合。所以这就提出了一个问题，我们必须要所有的点都分对吗？

答案当然是：不！在实际中噪声是普遍存在的，所以我们允许有分错的点，但是它的数量不能太多。例如在之前的Pocket算法中，我们不要求将所有的点都分对，而是找到一条犯错尽量少的线即可；在硬间隔SVM中，通过某些限制条件，要求所有的点都分对

所以借助Pocket算法的思想，我们要求有点分错，但是数量要控制在一定范围内。所以根据这种思想将表达式变成了下面的形式：对于正确的点，仍要满足之前的限制yn(xTzn+b)≥1，但是允许分错的点满足yn(xTzn+b)≥-∞，但是数量不能超过N。表达式中的C是所要求的正确性和容忍噪声存在程度的一种权衡，当c小一点时，允许分错的点多一些，反之则要求少一些

将上面的条件进行修正即可得到下面的表达式

但是上面的表达式也存在一些不足，比如它不再是二次规划的形式，我们就无法在使用之前的方法求解；无法衡量犯错的点的错误程度，因为某些点离边界远，有些近。所以引入新的参数ξ≥0来表示每个点错误的程度值，通过错误值得大小来表示是否有错误，ξ=0表示没有错误， ξ越大，表示错误越大，即点距离边界越远。修正后的形式如下所示，这样就重新满足了二次规划的形式，可以使用前面的方法求解

到目前为止的表达式如下所示

C表示尽可能选择宽边界和尽可能不要犯错两者之间的权衡。C越大表示希望分错的点越少，反之容忍分错的点越多与之对应的QP问题中，由于ξ的引入，总共参数个数为d+1+N，限制条件添加了ξ≥0，则总条件个数为2N

为了求解上面的表达式，我们效仿前面的方法，引入αn和βn构造拉格朗日函数如下所示，

接下来，再利用拉格朗日的对偶形式，将其问题转换为如下形式：然后根据KKT条件，对L(b，w，ξ，α，β)计算最小值。那么根据梯度下降算法思想：最小值位置满足梯度为零。我们先对ξn做偏微分，求其偏导数为零的点，得到βn = C - αn。因为βn ≥0，所以0≤αn≤C。

将βn = C - αn带入表达式，消去βn和ξn

得到如下的表达式，它跟Hard-MarginSVM中的dual形式是基本一致的，只是条件不同

分别令拉个朗日函数L对b和w的偏导数为零，分别得到：

经过上面的推导，最终的Soft-Margin Support Vector Machine 的表达式如下所示，和之前的Hard-Margin SVM Dual的形式基本一致，只是限制条件发生了些变化。在QP问题中，Soft-Margin SVM Dual的参数同样是N个，但是，条件由Hard-Margin SVM Dual中的N+1个变成2N+1个，这是因为多了N个αn的上界条件

下面是它的参数的求解过程，同样的使用二次规划的相关工具，找到Q，p，A，c对应的值。Soft-Margin SVM Dual计算的方法过程与Hard-Margin SVM Dual的过程是相同的。但是如何求b呢？

在前面的Hard-Margin SVM中我们可以根据任一个支持向量代入公式求出b。那么在Soft-Margin SVM中，相关的条件有两个，如下图绿框所示，得到支持向量，由于ξ是未知的，所以不能完全计算得到b。根据第二个条件如果括号中的不等于零，即αn≠C，则必有ξn = 0，带入第一个条件，计算可得b如红框所示。这里将满足0<αs < C的称之为弱的支持向量(Soft Suooprt Vector)

在引入核函数后b的计算表达式如下所示

同样的如果我们的核函数使用了高斯核后，不同的C的取值对于模型的效果影响如下所示：C越小Margin越粗，分类错误的点越多；C越大，Margin越细，分类错误的点越少，这和前面C的定义是吻合的。当C很大时，会将噪声的点也强行分对，可能会出现过拟合

所以在Soft-Margin SVM中γ和C的选择同样很重要

我们再来看αn取不同值是对应的物理意义。已知满足两个条件：

若αn = 0，得ξn=0，ξn=0表示该点没有犯错， αn = 0表示该点不是SV。所对应的点在margin之外（或者在margin上），且均分类正确，如下图中远离边界的o和×所示。

若0<αn<C，得ξn=0，且yn(wTzn+b)=1。ξn=0表示该点没有犯错，yn(wTzn+b)=1表示该点在margin上，如下图方框所示。这些点即free SV，确定了b的值。

若α = C，不能确定ξn是否为零，且得到1-yn(wTzn+b) = ξn，表示该点偏离margin的程度，ξn 越大，偏离margin的程度越大。只有当ξn=0时，该点落在margin上。所以这种情况对应的点在margin之内负方向（或者在margin上），有分类正确也有分类错误的，这些点称为bounded SV，如下图三角所示。

故在Soft-Margin SVM Dual中，根据αn的取值，就可以推断数据点在空间的分布情况

上面讲到在Soft-Margin SVM中使用高斯核后，γ和C的选择很重要。如下图所示，不同的取值组合就可以得到不同的Margin，横轴表示C，纵轴表示γ。不同的取值组合就会有不同的效果，那么如何知道哪一个组合更好呢？这时就可以使用之前提到的验证(validation)

比如只需要将由不同C、γ等参数得到的模型在验证集上进行cross validation，选取Ecv最小的对应的模型即可。比如不同的参数组合得到不同的Ecv如下所示：左下角的Ecv值最小，按照这个原则就应该选择它所对应的模型。

通常来说，Ecv(γ，C)并不是(γ，C)的连续函数，很难使用最优化选择（例如梯度下降）。一般做法是选取不同的离散的值(γ，C)进行组合，得到最小的Ecv，其对应的模型即为最佳模型。这就是之前学习的V-fold cross validation

V-Fold cross validation的一种极限就是Leave One Out CV，也就是验证集只有一个样本，其余的都拿去训练。对于SVM问题，它的验证集Error满足如下所示的关系。证明：令样本总数为N，对这N个点进行SVM分类后得到margin，假设第N个点(Xn,Yn)的αn=0，即这个点不是SV，远离margin（正距离）。这时候，如果我们只使用剩下的N-1个点来进行SVM分类，那么第N个点必然是分类正确的点，所得的SVM margin跟使用N个点的到的是完全一致的。这是因为我们假设第N个点是不是支持向量SV，那么他就不影响margin的位置和形状。所以前N-1个点和N个点得到的margin是一样的。

那么，对于非SV的点，它的g- = g，即对第N个点，它的Error必然为零，如下黄框所示：另一方面，假设第N个点αN≠0，即对于SV的点，它的Error可能是0，也可能是1，必然有Esv = 1。这符合我们之前得到的结论，即只有SV影响margin，不是支持向量的点对margin没有任何影响，可以舍弃

根据上面的证明，我们可以根据支持向量的数量来判断模型，数量越多，那么模型可能就越复杂，出现过拟合的可能性就越大。比如在下面的图中橙色的部分数量最小，那么它出现过拟合的概率最小

最后总结一下，这一将引入了Soft-Margin SVM，允许某些点分错，同时推导出了它所对应的QP表达式。介绍了通过αn值的大小，区分图中不同点的物理意义，便于数据分析。介绍了如何根据某些原则选择合适的SVM模型