机器学习技法笔记(5)-Soft Margin SVM

上节介绍的Kernel SVM的结尾,提到了overfit的问题,那是因为SVM要找到的分类面是必须把所有的训练数据分开,即使有一些噪音数据,或者说是错误标注的数据,也要“坚持”分开,这可能就会形成很复杂的边界,很容易形成overfit,如下:

我们希望的是左边的分类面,而非右边的,虽然右边的\(E_{in} = 0\),也就是说希望对于一些错误的数据忽略掉,前面介绍PLA的变种Pocket的用的就是这种方式:

Pocket找的是分类错误点尽可能少的分类面,不一定必须完全分开,容许错误的发生。而我们之前的SVM均是要求所有的数据都必须分类正确,如果我们将Pocket与SVM结合,即允许发生错误,如下:

上式约束条件中,对于分类正确的点,仍然需要满足\(\geq 1\)的条件,对于当前分类错误的点不加任何限制。所以目标函数中除了原先的margin,还必须加入了分类错误的个数,对整体做最小化。系数\(C\)的作用则是一种对margin和犯错个数的一个折中。\(C\)越大表示犯错误越少越好,犯错误个数重要性大于margin,如果太大了, 就容易过拟合了,反之\(C\)越小表示希望magin 越宽越好,也就是说\(\mathbf{w}\)越小越好,就是说对错误的惩罚很小,这样就会导致分类效果变差。 用\(C\)表示更重视\(margin\)还是重视犯错误的多少, 如下图:

对于新的优化问题。然而由于存在bool的运算\(\neq\),也就是说该问题是离散的,无法用二次规划QP来求解。此外,还有一个缺点,那就是对所有的错误都是一视同仁的,无论是距离边界近还是远,只要分类错误,都计算在内,也就是说无法区分大错小错。

为了解决上述问题,引入变量\(\xi \geq 0\) 表示不满足\(y_n(\mathbf{w}^T\mathbf{z}+b) \geq 1\)的数据距离当前分类边界的距离,用来量化偏离的程度,也就是错误的大小,把原问题转为如下:

\[\begin{align} \min\limits_{b,\mathbf{w},\xi} & \quad \frac{1}{2}\mathbf{w}^T\mathbf{w}+C \cdot \sum\limits_{n=1}^N \xi_n \\ s.t. & \quad y_n(\mathbf{w}^T{\mathbf{z}}_n+b) \geq 1 - \xi_n, for \ all \ n; \\ & \quad \xi_n \geq 0, for \ all \ n\end{align}\]

对于满足margin条件的点其\(\xi =0\), 不满足margin条件的其\(\xi > 0\); 如下图:

图中有除了A,B两点之外的点均满足条件,\(\xi=0\); 而A点属于没有不满足margin条件的,B点属于分类错误,因此\(\xi_{A} >0, \xi_B>0\)

上述的优化问题已经可以使用二次规划问题的解法去求解了,三个自变量:\(b,\mathbf{w},\xi\),一共有\(\tilde{d}+1+N\)维;约束条件的个数为\(2N\)个,按照前面的解法即可。

我们把这种容许犯错的SVM成为Soft-Margin SVM(软间隔SVM),与前面几节的Hard-Margin SVM相对,并且引入的\(\xi\)也叫做 松弛变量,顾名思义,允许数据偏离margin, 例如出现上图中A,B那样的数据。

上述的优化问题是Soft-Margin原始问题,下面考虑Soft-Margin的对偶问题(Dual),同Hard-Margin,只需将两个约束条件加入到Lagrange Function:

\[\begin{align}\mathcal{L}(b, \mathbf{w}, \xi, \alpha, \beta) = &\frac{1}{2}\mathbf{w}^T\mathbf{w}+C \cdot \sum\limits_{n=1}^N \xi_n \\&+ \sum\limits_{n=1}^{N}\alpha_n(1-\xi_n-y_n(\mathbf{w}^T\mathbf{z}_n+b)) \\ & +\sum\limits_{n=1}^{N}\beta_n(-\xi_n) \end{align} \]

然后将原始问题转为如下的对偶问题:

\[\max\limits_{\alpha_n \geq 0,\ \beta \geq 0}\left(\min\limits_{b, \mathbf{w}, \xi} \quad \mathcal{L(b, \mathbf{w}, \xi, \alpha, \beta)}\right)\]

优化思路同Hard-Margin的对偶问题相同,首先对内层最小化部分对变量求微分: \[\begin{align}& \frac{\partial \mathcal{L}}{\partial \xi_n} = C - \alpha_n - \beta_n = 0 \\ & \Rightarrow \beta_n=C-\alpha_n \end{align}\]

这样利用这个条件,就可以向Hard-Margin消去\(b\)一样去掉\(\beta_n\), 同时结合\(\beta_n \geq 0\)可以得到$ 0 _n C$。

整理一下式子,提取出\(\xi\)的部分:\(\sum(C-\alpha_n-\beta_n) \xi_n\),已知最优解满足\(\alpha_n+\beta_n =C\), 因此\(\xi\)部分可以消去,最终如下:

\[\max\limits_{ 0 \leq \alpha_n \leq C}\left(\min\limits_{b, \mathbf{w}} \quad \frac{1}{2}\mathbf{w}^T{\mathbf{w}} + \sum\limits_{n=1}^{N}\alpha_n(1-y_n(\mathbf{w}^T\mathbf{z}+b))\right)\]

除了外层的\(\alpha_n\)多了一个上限之外,与Hard-Margin的对偶问题完全一样,接下来对\(b, \mathbf{w}\)分别求微分,然后去掉\(b,\mathbf{w}\),再将外层最大化稍微化简,最终转为如下的二次规划(QP)问题:(此过程与Dual SVM中完全一样,不再重写一遍):

\[\begin{align} \min\limits_{\alpha} & \quad \frac{1}{2}\sum\limits_{n=1}^N\sum\limits_{m=1}^N \alpha_n\alpha_my_ny_m\mathbf{z}_n^T\mathbf{z}_m - \sum\limits_{n=1}^{N}\alpha_n \\ s.t. & \quad \sum\limits_{n=1}^{N}\alpha_ny_n = 0; \\ & \quad 0 \leq \alpha_n \leq C, \ n = 1,2...N \end{align}\]

当然还有一些中间条件: \(\mathbf{w} = \sum \alpha_ny_n\mathbf{z}_n, \beta_n=C-\alpha_n\)

到这里我们的问题转为了有\(N\)个变量,\(2N+1\)个约束条件的二次规划问题,表示出\(Q,p,A,c\)然后使用某个QP Solver即可得到最优的\(\alpha\):

  • Q矩阵元素: \(q_{n,m} = y_ny_m\mathbf{z}_n^T\mathbf{z}_m\)
  • $ p = -_N$
  • 对于\(A,c\),对应如下:
    • \(a_{\geq} = y, c_{\geq} = 0\)
    • \(a_{\leq} = -y, c_{\leq} = 0\)
    • 对于\(\alpha \geq 0\)\(a_n^T =\) n-th unit dircection, $c_n = 0 $
    • 对于\(\alpha \leq C\)\(a_n^T =\) n-th unit direction, \(c_n = -C\)

到此为止,我们得到了对偶问题的最优的\(\alpha\), 再结合上节的Kernel Trick, 我们得到了 Kernel Soft-Margin SVM,基本流程如下:

这里有一点不一样的地方是对\(b\)的求解,回想之前是利用转化为拉格朗日对偶问题(min(max) \(\Leftrightarrow\) max(min))时候,利用互补条件(complementary slackness),参考Dual SVM, 但是Soft-Margin有两个条件,即:

\[\begin{align} \alpha_n(1-\xi_n-y_n(\mathbf{w}^T\mathbf{z}_n+b)) &=0 \\ \beta_n \xi_n = (C- \alpha_n)\xi_n & =0\end{align}\]

首先对第一个式子,对于SV(\(\alpha_s > 0\)), 那么可以得到 \(b=y_s - y_s\xi_s - \mathbf{w}^T\mathbf{z}_s\),但是里面含有\(\xi\),无法求解。 再看第二个式子,对于\(\alpha_s < C\)的那部分SV(也叫free SV),则有\(\xi_s = 0\),因此利用这部分SV, 加上Kernel Function便可得到\(b\)

\[b=y_s - \mathbf{w}^T\mathbf{z}_s = y_s - \sum\limits_{free \ SV} \alpha_ny_nK(\mathbf{x}_n, \mathbf{x}_s)\]

到这里基本完成了Soft-Margin SVM的算法,集对偶,核,Soft-Margin于一身,可以解决非线性问题,松弛变量允许噪音数据等,在实际分类问题中,应用很广泛。 不过需要注意的是这种SVM也有可能overfit的,因此需要仔细调整参数\(C\),以及Kernel Function的参数,一般使用模型验证(Validation)手段比如交叉验证去选择最好的参数。

最后再提一下Soft-Margin 中的\(\alpha\)的物理意义,看下图:

根据两个互补条件,可以得到三类点点:

  • 非SV(支撑向量): 也就是距离分离面比较远的那些数据,如图中的圈圈叉叉,对应的\(\alpha_n = 0, \xi_n = 0\)
  • free SV: 也就是说\(\alpha_n < C, \xi_n =0\),它们在边界上, 满足条件。图中方框标记的点,我们使用这些点计算的\(b\)
  • bounded SV: \(\alpha_n =C, \xi_n > 0\),这种类型的数据,不满足margin条件,或者分错类别的,如图中三角标记的。