1 引言

经过前面几节内容的介绍,我们已经知道了支持向量机背后的原理。同时,为了求解SVM中的目标函数,笔者还在前面两节内容中陆续介绍了拉格朗日乘数法和对偶性问题。接下来,在这篇文章中将开始正式介绍SVM的求解过程。同时,为了便于各位读者朋友循序渐进的了解整个求解过程,下面笔者会依次先后介绍硬间隔和软间隔中目标函数的求解步骤。

2 构造硬间隔广义拉格朗日函数

由前面几篇文章的内容可知,SVM硬间隔最终的优化目标为[1]

由此可以得到广义的拉格朗日函数为

其中为拉格朗日乘子,且同时记

进一步可得原始问题的对偶优化问题为

所以,为了求得对偶问题的解,需要按照式中的顺序进行求解。

2.1 关于参数w,b求的极小值

为了求解式中的对偶优化问题,首先需要最小化式,即分别对求偏导数并令其为0有

进一步有

到此便得到了权重的解析表达式,而它对于理解SVM中核函数的利用有着重要作用。接着将式带入式可得

化简得到式的具体步骤为

将式带入

到此,便得到了参数的解析式。

2.2 关于参数的极大值

由式可以得出如下优化问题

之所以式中最后一个等式也会成为约束条件,是因为是通过式求解得到是存在的前提。

进一步, 假设为对偶优化问题的解,那么为了使得对偶优化问题与原始优化问题同解需要满足如下KKT条件

根据式可得

从式可以看出,至少存在一个。因为如果所有的均为0,那么由式可知此时的也为0,而这显然不是原始优化问题的解[2]。

同时,由式可知,若存在,那么必有

根据式可知,此时的样本点是一个支持向量,而这也显示出的一个重要性质是超平面仅仅与支持向量有关。

进一步,将式代入式并注意可得

综上所述,对于任意给定线性可分数据集,首先可以根据式中的优化问题求解得到;然后再利用式分别求解得到;最后即可得到分离超平面。

2.3 硬间隔求解计算示例

为了使各位读者更加清楚SVM中硬间隔决策面的求解步骤,下面笔者将以一个实际的数据集来进行计算示例。现有数据集一共包含7个样本点,其中,为负样本,为正样本。黑色实现为决策面,黑色虚线为间隔边界,带圈的样本点为支持向量,如图1所示。

图 1. SVM硬间隔示例图

由给定数据集以及式可知,对偶问题为

注意

此时由约束条件可知,将其代入目标函数并记为

分别求偏导并令其为0可得

不过根据式中的3个等式联立求解后发现,同时满足这3个式子的解并不存在,也就是说最终的解只能可在约束条件的边界出产生。因此,在式中需要考虑如下边界情况:

①当时,根据式中后两个等式可求得不满足式中的约束条件;

②当时,根据式中第1个和第3个等式可求得,也不满足约束条件;

③当时,根据式中前两个等式求解后发现同样不满足约束条件;

④最后,只有当时,才能求得满足约束条件的解,即此时。对于其它情况,大家可以自行验算。

进一步,根据上述求得的结果通过式便可求得决策面中

同时,根据式并任取其中一个作为即可求得

最后,可以得到决策面方程为

3 构造软间隔广义拉格朗日函数

由前面几篇文章的内容可知,SVM软间隔最终的优化目标为

由此可以得到广义的拉格朗日函数为

其中为拉格朗日乘子,且同时记

进一步可以得到原始问题的对偶优化问题为

所以,为了求得对偶问题的解,需要按照式中的顺序进行。

3.1 关于参数的极小值

首先需要最小化式,即分别对求偏导数并令其为0有

进一步有

接着,将式到代入式

此时可以发现,式化简后已经消去了。

3.2 关于参数的极大值

由式的极大可以得出如下优化问题

接着,将式代入式便可得到化简后的约束条件

最后便可得到最终的对偶优化问题

从式可以发现,SVM软间隔的对偶优化问题同硬硬间隔的对偶优化问题仅仅只是在约束问题上发生了变化。

现在假设为对偶优化问题的解,那么为了使得对偶优化问题与原始优化问题同解需要满足如下KKT条件

因此,根据式可得

从式可以看出,至少存在一个。因为如果所有的均为0,那么由式可知此时的同样为0,而这显然不是原始优化问题的解。进一步,若存在,那么由式知,此时对应的;再由式可知,此时必有;所以最后由式可知,此时必有

进一步,将式代入式可得

综上所述,对于任意给定数据集,首先可以根据式中的优化问题求解得到;然后再利用式分别求解得到;最后即可得到分离超平面。

3.3 软间隔中的支持向量

在前面多篇文章的内容中,笔者都提到了“支持向量”这个词,并且还介绍到位于间隔边界上的样本点就是支持向量。不过那到底支持向量是什么呢?直白点说,能够影响决策面形成样本点就是支持向量。例如从图1可以看出,对于影响最后决策面形成的就只有这两个样本点。同时,从硬间隔的定义可以看出,在求解得到决策面后所有样本点的分布只存在两种情况。第一种是位于间隔边界上,而另外一种就是在间隔边界以外。因此,在硬间隔中影响决策面形成的就只有位于间隔边界上的样本点,即支持向量。

但是从软间隔的定义可以看出,由于软间隔允许样本点被错误分类,并且其程度可用通过惩罚系数来进行控制。因此可以得出在软间隔中,可以影响决策面的位置,并且支持向量也不仅仅只会位于间隔边界上,如图2所示。

图 2. 软间隔示例图

从图2可以看出,为了增强模型最终的泛化能力,软间隔目标函数在求解过程将这两个样本点划分到了间隔边界以内,并且样本点还被错误的划分到了另外一个类别中(当然本身也可能是异常样本)。因此可以得出,在SVM软间隔的建模过程中,影响决策面位置的除了位于间隔边界上的样本还有位于间隔边界内的样本点,所以这些都被称之为支持向量。因为如果去掉这个被错分类的样本点,那么最终得到的决策面会更加趋于水平。

同时,由式可知,当时,则,此时支持向量将位于间隔边界上;当时,则分类正确,此时支持向量将位于间隔边界与决策面之间;当时,此时支持向量将位于决策面上;当时,则分类错误,此时支持向量将位于决策面的另一侧[2]。进一步,可以总结得到

4 总结

在这篇文章中,笔者首先介绍了在求解SVM模型中如何构造硬间隔的广义的拉格朗日函数以及其对应的对偶问题;接着通过求解对偶问题中的极小值得到了的计算解析式,需要提醒的是的表达式也是理解SVM核函数的关键;然后介绍了以一个实际