机器学习技法 Lecture4: Soft-Margin Support Vector Machine

Motivation and Primal Problem

Hard-Margin SVM有个缺点那就是它依然会过拟合。原因一部分是映射函数$\Phi$Φ造成的，而另一部分原因是它对于线性可分的要求。

为了缓解过拟合的情况，可以放松对于线性可分的要求。也就是可以让部分样本点分错。对于这种情况之前讲过一个算法很相似，那就是pocket PLA算法。pocket算法里对于不可分的点的做法是最小化分错的数量。可以把这种做法与Hard-Margin SVM结合一下，把原来的最小化目标加上一个分错数量的部分：

对应的限制条件也要改。对于分对的要大于1，分错的就不管了。不过这个方式得到的这种算法有个很大的问题，那就是判断分对分错的函数是个非线性的函数，不再是二次规划可解的问题。而且这种只判断分对分错的方式也无法区分出错误的点错误的程度。

于是可以使用一种新的目标函数，能够方便得看出分错的程度，而且能够使最终的目标函数是二次规划可解的。

使用了一个新的变量$\xi$ξ来代表每个点到边界$(y_{n}(w^{T}z_{n}+b) = 1)$(yn​(wTzn​+b)=1)的距离。这样目标函数和限制条件都做了对应改变，整个问题又变成一个二次规划可解的问题。

其中变量$C$C代表的是对于比较大的边际以及比较小的分错距离的tradeoff。这个问题最终是一个$\widehat{d}+1+N$d+1+N个变量，$2N$2N个限制条件的QP问题。

Dual Problem

同样的，这个QP问题也有它的拉格朗日对偶问题，推导的过程与Hard-Margin时候的过程类似。

先用拉格朗日乘子把限制条件写到目标函数里，然后用maxmin的结果来代替minmax对应的结果，最终满足KKT条件时两个结果同时最优。

首先在括号里对$\xi$ξ求导得到拉格朗日系数之间的关系$C-\alpha_{n}-\beta_{n}=0$C−αn​−βn​=0。这样就能把系数$\beta_{n}$βn​替换掉。代入目标式子发现$\xi$ξ变量系数为0，也能不考虑这个变量了。

依然继续求导，对系数$w$w和$b$b求导也得到对应的约束条件。

这样就得到了最后的soft-margin问题的对偶形式：

变成了一个带有$N$N个变量和$2N+1$2N+1个限制条件的凸QP问题。而且与hard-margin的对偶问题几乎没有区别，除了系数$\alpha_{n}$αn​多了上限的限制。

Messages behind Soft-Margin SVM

把核函数方法也应用到其中，限制得到对应的算法流程为：

几乎与hard-margin时候一样，但是比hard-margin时候更灵活。但是还剩下其中第三步系数$b$b的求解还没有得到。

来看一下在这个问题里如何得到系数b：

先回顾一些hard-margin的时候，我们对于support vector有一个对应的限制条件，在知道系数$\alpha_{s}&gt;0$αs​>0时对应的支持向量的时候就能够得到系数b。但是在soft-margin里要复杂一些。虽然支持向量对应的$\alpha_{s} &gt; 0$αs​>0的情况依然有一个等式，但是等式中还有个未知变量$\xi_{s}$ξs​。但是soft-margin里还多了一个限制条件，如果我们能够找到$\alpha_{s}$αs​对应的点，那么$xi_{s}$xis​就能够去掉，得到一个具体的解。但是如果不存在$\alpha_{s}&lt;C$αs​<C，那么最终的b会是一个可行的范围。

观察一下使用了高斯核的soft-margin SVM算法的分类效果。

可以看到对于C的调整会增大模型overfit的可能性。因为C越大对应的它对于margin voilation的容忍度就越小，就会导致模型结果越复杂。因此即使是soft-margin也有过拟合的风险，因此还是需要仔细的调参。

有两个关于松弛变量的限制条件，能够看出其对应的不同的样本点：

其中，如果$\alpha_{n}=0$αn​=0，那么对应的$\xi_{n}=0$ξn​=0，也就是这个点是完全分对的，分布在分类界限分对的一边。

对于$0 &lt; \alpha_{n} &lt; C$0<αn​<C的情况，对应的$\xi_{n} = 0$ξn​=0，表明这是个支持向量，而且正好落在分类界限上。

而对于$\alpha_{n}=C$αn​=C的情况，$\xi_{n}&gt;=0$ξn​>=0，也就是这个点会落在两条边界之内，对应的$\xi_{n}$ξn​就是它到己方边界的距离。

Model Selection

因为实际使用时依然有可能过拟合，因此还需要进行一些模型的选择：

我们可以使用交叉验证的方式来选择模型。因为$E_{cv}(C,\gamma)$Ecv​(C,γ)是个无法直接优化的问题，因此只能直接进行比较。常用的是使用V-fold验证的方法。

在这里有一个假设，那就是留一法交叉验证的结果会小于等于支持向量所占的比例：

可以来证明这个命题。假如留一法留下做验证的那个点不是支持向量，那么这个点就不会影响到结果，也就是$g^{-}=g$g−=g，因此在这个点上两个模型都会将其分对。$e_{non-SV}=err(g^{-},non-SV) = err(g,non-SV) = 0$enon−SV​=err(g−,non−SV)=err(g,non−SV)=0，而且对于支持向量来说每个点贡献的$e_{sv} \leq 1$esv​≤1，也就是说分错的$E_{in}$Ein​加起来的结果也会小于等于支持向量所占的比例。

但是这样一个命题只是说明了交叉验证时候的一个上限，有时候无法直接判断出结果：

但是根据上限也可以去除掉一些明显错误率偏高的模型。