机器学习:支持向量机4

前面介绍的SVM,无论是线性可分还是非线性可分,称为Hard Margin SVM,都要求对输入数据进行精确划分。我们不难想到这类SVM存在过拟合这个问题。如果输入数据本身就存在误差,精确划分反而是没意义的。本篇文章就如何处理过拟合问题,介绍即所谓的Soft Margin SVM

数学推导

引入衡量误差的变量 $-\xi_i-$。$-\xi_i-$表示不能被正确分类的样本点距离正确一侧边界的距离,距离越大表示错误越大,即$-\xi_i-$越大。如果样本点能被正确分类,则$-\xi_i = 0-$。故有$-\xi_i \ge 0-$。

那么,原来能通过求解函数$-\frac{1}{2}\vec{w}^{2}-$在最小化下的参数$-\vec{\alpha}-$,如今需要增加能够体现误差的约束条件再求解。

可以如下构造函数来描述误差: $$ \frac{1}{2}\vec{w}^{2} + C\sum_{i}^{n}{\xi_i} $$

这个函数把所有输入数据的误差叠加在一起,即$-\sum_{i}^{n}{\xi_i}-$。然后用参数C来控制所有误差的权重。如果C很大,表示即使有很小的误差出现都会严重影响目标函数。

结合之前文章提到的知识,可以构造拉格朗日方程:

$$ L(\vec{w}, b, \vec{\xi}, \vec{\alpha}, \vec{\beta}) = \frac{1}{2}\vec{w}^{T}\vec{w} + C\sum_{i}^{n}{\xi_i} - \sum_{i}^{n}{\alpha_i[y_i(\vec{w}^{T}\vec{x_i}+b)-1+\xi_i]} - \sum_{i}^{n}\beta_i\xi_i
$$ 其中, $$ \alpha_i \ge 0, \beta_i \ge 0, i = 1,2...n $$

然后利用对偶思想求解$-\vec{w}, b, \xi-$的导数,并让他们等于0。如下:

$$ \begin{array}{lcl} \frac{\partial L}{\partial \vec{w}} = \vec{w} - \sum_{i}^{n}\alpha_{i} y_{i} \vec{x}_i = 0 \\ \frac{\partial L}{\partial b} = - \sum_{i}^{n}\alpha_{i} y_{i} = 0 \\ \frac{\partial L}{\partial \xi_{i}} = C - \alpha_{i} - \beta_{i} = 0 \end{array} $$

代入上面的拉格朗日方程,可以得到二项规划方程。最后求解$-\vec{\alpha}-$,可得$-\vec{w}-$和$-b-$。二项规划方程如下: $$ F(\alpha) = \frac{1}{2}\sum_{i}^{n}\sum_{j}^{m}y_{i}y_{j}\alpha_{i}\alpha_{j}\vec{x}_{i}^{T}\vec{x}_{j} - \sum_{i}^{n} \alpha_i, C \ge \alpha_i \ge 0, i = 1,...,n
$$

其中$-\vec{w}-$如下: $$ \vec{w} = \sum_{i}^{n}\alpha_{i}y_{i}\vec{x}_{i} $$

$-b-$可利用落于边界上的支持向量求解。

比较

看到二项规划那一步,我们可以发现Hard Margin SVMSoft Margin SVM的差别仅仅是$-\alpha_i-$的取值范围上有差异。Hard Margin SVM的约束条件是$-\alpha_i \ge 0-$;Soft Margin SVM的约束条件是$-C \ge \alpha_i \ge 0-$。

我们知道$-\alpha_{i}-$仅在$-\vec{x}-$为支持向量时值大于零。而在这里,$-\alpha_{i}-$多了一个上限C。因为$-C = \alpha_{i} + \beta_{i}-$,所以有下面结论:

如果$-\alpha_{i} = 0-$,表示该点为非支持向量。

如果$- 0 \lt \alpha_{i} \lt C-$,则$-\beta_{i} \gt 0-$,对应的$-\xi_{i} = 0-$,表示该点为边界支持向量。如下图: 情况2

如果$-\alpha_{i} = C-$,则$-\beta_{i} = 0-$,对应的$-\xi_{i} \gt 0-$,表示该点违反了最大边界的原则,属于噪声点。 情况3

ChardLau

继续阅读此作者的更多文章