机器学习笔记7: 支持向量机(下)

上一篇文章中我们已经根据拉格朗日对偶性推导出了SVM最优化公式。而在这一篇文章中，我们将会从SVM最优化公式中引出核函数(kernels)的概念，由此给出在高维空间下更高效应用SVM的算法，然后利用正则化解决线性不可分与异常点的问题，最后介绍用于高效实现SVM的序列最小优化(sequential minimal optimization)算法。

核函数

在线性回归的问题中，我们曾举过预测房价的例子，输入特征x是住房面积。假设我们为了提高预测准确性，希望用x²，x³作为特征来建模。为了区别这两类变量，我们把原始的输入变量称为属性(attribute)，对原始变量映射后的项叫做特征(feature)。定义φ为特征映射(feature mapping)函数，在这个例子中，我们有：

为了应用SVM算法，我们需要将算法中出现x的地方替换成φ(x)。由于算法可以被完全写成向量内积的形式<x, z>，这意味着我们可以将其替换为<φ(x), φ(z)>。给定一个特征映射函数，我们定义核函数(kernels)为：

因此，在算法中我们可以把<x, z>都替换成K(x, z)。给定φ，我们通过求φ(x)和φ(z)的内积来计算K(x, z)。有趣的是，即使φ(x)可能因为维度较高导致计算起来比较耗时，而计算K(x, z)并不是很耗时。在这种情况下，通过在算法中引入K(x, z)，可以使得SVM算法的计算量大大减少。

我们来举个例子看一下，假设

我们可以计算出：

对比K(x, z)的定义，可得到特征映射函数φ为(当n=3时)：

可见计算φ(x)的时间复杂度是O(n²)，而计算K(x, z)的时间复杂度是O(n)。

再考虑一个例子，假设

对比K(x, z)的定义，可得到特征映射函数φ为(当n=3时)：

推广到更一般的形式，假设K(x, z) = (x^Tz + c)^d，计算φ(x)的时间复杂度是O(n^d)，而计算K(x, z)的时间复杂度仍旧是O(n)。当维度较高时，核函数的优势更加明显。

另一个常用的核函数是高斯核(Gaussian kernel)，其特征映射函数φ可以映射到无限维。高斯核函数为：

我们接下来的一个问题就是给定一个函数K，它是否能成为一个合法的核函数，也就是说是否存在一个映射函数φ使得K(x, z) = <φ(x), φ(z)>?

假设K是一个合法的核函数，对于一个包含有限个点的集合{x⁽¹⁾, x⁽²⁾, ..., x^(m)}，定义核矩阵(Kernel matrix)K，矩阵的每个元素K_ij = K(x⁽ⁱ⁾, x^(j))。注意由于核函数和核矩阵的关系密切，我们使用了相同的符号K来表示它们。

当K是合法的核函数时，可证明K_ij = K_ji，因此K是对称矩阵。此外，定义φ_k(x)表示向量φ(x)的第k个元素，我们也能证明：

综上我们可得出结论，如果K是合法的核函数，那么对应的核矩阵K是对称半正定(symmetric positive semidefinite)矩阵。这个结论反过来也成立，即“K是合法的核函数”是“核矩阵K是对称半正定矩阵”的充分必要条件，这个结论被称为Mercer定理(Mercer Theorem)。

核函数在机器学习中有广泛的应用。比如在数字识别问题中，我们需要根据一张图片(16*16像素)识别出数字(0-9)。如果把每个像素作为特征值，那么会有256个特征值，使用核函数(K(x, z) = (x^Tz)^d或者高斯核)后可以使SVM的性能大大提升。

正则化与线性不可分的情况

到目前为止，我们在推导SVM过程中都是基于“数据是线性可分的”这个假设。尽管用函数φ将特征映射到高维可以增加数据线性可分的可能性，但这个假设不能保证总是成立。此外，还有一种情况是如果数据里有异常点(outlier)，那么得到的超平面可能并不是我们想要的结果。比如左下图显示了一个最优超平面，右下图里增加了一个异常点使得最优超平面的间隔变小了，影响了分类器的性能。

为了使SVM算法在线性不可分的情况下正常工作，并且对异常点不那么敏感，我们采用l1正则化(l1 regularization)方法修改优化目标为：

通过增加ξ_i项，我们允许函数间隔小于1，并且当函数间隔小于1的时候，我们在目标函数增加Cξ_i的代价。

同样，我们对该问题构造拉格朗日算子：

其中α_i和r_i是拉格朗日乘数。我们不详细展开推导了，最后我们可以得到对偶问题为：

通过求解该最大化问题可以得到α^*，然后代入回原始问题可得到其他参数。另外由于采用了l1正则化，原来α_i >= 0的限制变成了 0 <= α_i <= C。此外，该问题的KKT对偶互补条件为：

最后我们还剩下一个问题没有讲，那就是如何求解最大化W(α)的方法，这个是我们下面要介绍的内容。

坐标上升算法

首先我们考虑没有任何约束条件的优化问题：

其中W是以α为参数的函数。之前在优化问题中我们介绍过梯度下降法和牛顿方法，在这个问题里我们使用坐标上升(coordinate ascent)算法。

算法的核心思想是，每次固定一个参数α_i，然后使W关于α_i作优化调整。在这个算法里，我们依次选取α₁到α_m作优化，然后不断循环直到结果收敛为止。这个算法的一个优化方向是，调整α_i参数选取的顺序，每次选择使得W(α)增加幅度最大的α_i作为下一个参数。

上图是一个优化二次函数的等高线示意图。坐标初始点在(-2, 2)，可以看到每次优化只在一个维度方向上进行优化。

序列最小优化算法

回到我们SVM的对偶问题上来，我们要求解的优化问题为：

利用坐标上升算法的思想，我们每次固定一个参数α_i进行优化是否可行？答案是不可行，假设我们固定α₁，根据约束条件(19)，可得：

两边都乘以y⁽¹⁾，可得：

所以α₁受到其余α_i参数的控制，当α₂, ..., α_m不变时，α₁也不会改变。

因此如果我们要使用坐标上升算法的话，需要一次更新两个参数。具体来说就是，每次选取两个参数α_i和α_j进行更新，使W关于α_i和α_j作优化调整，然后不断循环直到结果收敛为止。

这个算法被称为序列最小优化(sequential minimal optimization, SMO)算法，最早由John Platt提出，相关论文可以在这里找到。

为了判断算法的收敛性，我们可以检查KKT条件是否满足tol参数，具体方法在John Platt关于SMO的论文里有阐述。

SMO算法之所以高效就在于每次更新两个参数α_i和α_j的操作本身就很高效，我们具体来描述一下。

根据等式(19)，我们有：

既然等式右边的参数是固定的，我们就用一个常量ζ来表示：

我们可以把α₁和α₂的约束条件画成下面的图。

根据约束条件(18)，α₁和α₂必须限制在[0,C]×[0,C]的方块内。另外α₁和α₂必须满足图中直线的约束。α₂要满足L ≤ α₂ ≤ H的条件，其中L, H是α₂的上下边界。

根据等式(20)，我们把α₁写成是关于α₂的函数:

那么目标函数W可以表示为：

把α₃, ..., α_m视为常量，可以看出W是关于α₂的二次函数。如果我们不考虑限制条件(18)，那么通过求导就可以求出使这个二次函数最大化的参数，记为α₂^{new, unclipped}。再把限制条件(18)考虑进来，我们可以得到：

最后，根据α₂^new的值以及等式(20)，可以求得α₁^new的值。

关于这个算法还有其他一些细节，但我们不会在这里一一阐述，有兴趣的读者可以自行查看Platt的论文。

总结

• 引入核函数的概念后，通过把数据映射到高维空间，有概率可解决原始空间中线性不可分的问题，并且可以使SVM算法更高效
• Mercer定理：“一个核函数是合法的”是“核函数对应的核矩阵是对称半正定矩阵”的充分必要条件
• 为了使SVM算法在线性不可分的情况下正常工作，并且对异常点不那么敏感，可以采用l1正则化的方法
• John Platt提出的SMO算法，可以高效求解SVM的对偶问题，其基本思想是利用了坐标上升算法

参考资料

• 斯坦福大学机器学习课CS229讲义 pdf
• 网易公开课：机器学习课程 双语字幕视频