在不同机器学习教材上多次看到支持向量机,但是我并没有很好地掌握其对偶形式的推导以及求解对偶形式问题的序列最小化算法,所以就在本文中详细推导一下支持向量机的对偶问题以及实现序列最小优化算法。

支持向量机

线性可分形式

支持向量机尝试使用一个超平面将样本从样本空间中分开,样本中距离超平面最近的样本称为支持向量,支持向量机需要保证这个超平面到所有支持向量的距离最大化。

对于超平面,某样本到超平面的距离就是:

如果可以将空间中的样本正确划分,那么就有:

这个不等式中,1的作用用于保证两侧的支持向量到超平面的距离相等,而其具体的大小没有实际意义。于是,支持向量机的间隔就是,支持向量机的学习过程就是最大化间隔,因为倒数的性质不是非常好,因为最大化等价于最小化,最终的优化目标就是:

使用拉格朗日乘子法,将问题转换为,要求拉格朗日乘子

对L关于w和b求偏导后令偏导为0

从上面可以得到,将其代入

最终得到支持向量机的对偶形式

当求解得到拉格朗日乘子后,可以通过计算得到w

计算b需要借助支持向量,所有的支持向量满足

得到,

线性不可分形式

如果样本无法被超平面完美分离,那么需要允许一些样本位于间隔之间或者位于超平面的另外一侧。

利用拉格朗日乘子法得到

拉格朗日乘子需要满足

对L关于w和b求偏导后的结果和线性可分情况是一样的,另外需要

代入

最终得到支持向量机的对偶形式

卡罗需-库恩-塔克条件

KKT条件是在满足一些有规则的条件下,一个非线性规划题能有最优化解法的一个充要条件。根据KKT条件,当得到最优解时,约束问题中的不等式约束满足

还有一个非常有用的东西就是,以上条件可以得出以下结论:

  • 时:此时也有,所以以及,于是就有,样本就是支持向量;
  • 时:此时,所以以及,于是就有,样本落在支持向量机正确分类区域内;
  • 时:此时,所以以及,于是就有.样本位于支持向量机间隔中或者另外。

序列最小优化

序列最小优化算法是目前最广泛使用的支持向量机二次规划问题求解算法。序列最小优化算法将整个二次规划问题分解为多个小问题,通过求解每个小问题的最优解得到全局最优。在每一步优化过程中,算法优化一对拉格朗日乘子,之所以优化一对而不是一个,那是因为优化过程中需要满足线性等式约束。

拉格朗日乘子对优化

算法每一步都需要优化一对拉格朗日乘子,为了描述方式,命名它们为

png

的约束如上图所示,其中正方形来自,两个乘子对应的点必须位于这个正方形之中,而其中的直线来自,两个乘子对应的点必须在这条直线之上。因此,位于正方形中的线段就是两个拉格朗日乘子在优化步骤中的取值范围。当时,的取值范围是:

时,的取值范围:

序列最小优化的一个特点就是每步优化可以直接得到解析解,而不再需要进行高时间复杂度的数值计算。回到本文上半部分推导出的对偶问题,如果支持向量机使用了核函数,那么,优化目标函数就是:

由于我们固定了除了之外的变量,所以目标函数和其他变量无关,于是可以写成:

其中,

始终需要满足线性等式约束,于是可以使用来表示

令导数为零求解获得极值点

如果二次导数恒为正数的话,那么极值点的就是最优问题的解

展开s以及k,得到

因此的更新公式就是

其中。由于乘子必须位于约束对应的线段之上,如果乘子超过了约束范围,那么就将约束中距离乘子最近的值作为最优值。

根据线性约束可以得到

如果训练数据中存在相同的样本,那么可能为零。如果矩阵K不是正定的,那么可能为正数,那么这时目标函数就是凹函数。对于的情况下,最优解就是约束的两个端点之一,端点目标函数值计算方法为

如果仔细检查上面的目标函数估值,可以发现被省略了,毕竟作为常数对于比较来说没有意义。

拉格朗日乘子对选择

为了能够让算法快速收敛,需要启发式选择每次优化的乘子,选择的内容包括如何选择第一个乘子以及如何选择第二个乘子。序列最小优化算法的最外层循环选择需要优化的第一个乘子,算法扫描整个训练样本集合。如果一个样本不符合KKT条件,那么它对应的乘子一定需要被优化。在第一次遍历之后,扫描整个训练样本集合,如果某个乘子在0到C之间(不在约束边界),算法反复遍历不在边界的乘子,直到扫描不出结果为止。算法将反复执行以上两个遍历过程,直到不再有乘子可以优化为止。

当第一个乘子选中后,算法选择第二个乘子,目标是尽量最大化优化步长,步长近似为

在某些不正常的情况下,算法采用上述的启发式选择并不能实现优化。例如,当两个样本在空间中重叠的时候,那么就无法做到优化。在这种情况之下,序列最小优化算法需要第二种备选的方案来寻找可以优化的乘子。算法首先在约束内寻找可以优化的另外一个乘子,其次在整个训练数据集中寻找。如果以上的策略都没能找到合适的优化乘子,那么放弃寻找,回到上层循环。

阈值计算

根据KKT条件,如果不在约束边界,那么对应的就是支持向量机的支持向量,对应的阈值计算方法为

如果两个乘子对应的样本都是支持向量,那么两个乘子对应的阈值是相等的,可以将阈值设置为任意一个。当两个乘子都不是支持向量,那么之间的任意取值都满足KKT条件,那么最终阈值

线性核权重优化

如果支持向量机使用了线性核,那么对应的权重是可以显式计算出来的。这样一来,计算支持向量机输出的时候就需要遍历整个样例集合了。和阈值类似,权重同样可以在每一步优化过程中更新

潜在的问题

当我编写好上述代码之后,在《机器学习》的西瓜数据集进行测试发现,算法根本不能收敛,这就涉及到了原版序列最小化算法中存在的一个问题。假设数据集包含了三个样例:

算法最初会将拉格朗日乘子和阈值初始化为,也就会有。假设算法首先选择了样例1和样例2进行优化,得到。此时,新阈值。如果接下来优化样例3的时候可以发现,最优解总是位于约束之外导致最终剪切回到原先的值。关于这个问题的详细描述和改进可见Keerthi的文章

现实中一般使用的支持向量机实现是LIBSVM,LIBSVM中序列最小优化算法也是改进版而不是原版。对于算法改进本文不再深入,在掌握优化技术之前看优化方向的论文实在太痛苦,我在测试过程解决上述问题的一种办法就是想办法增大防止乘子过早到达边界,但是这样没能从根本上解决问题。

参考文献

  1. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines
  2. Improvements to Platt’s SMO algorithm for SVM classifier design
  3. 机器学习