核方法 和 SMO

上一部分介绍了硬间隔和软间隔支持向量机，本部分介绍非线性支持向量机（核方法）和序列最小最优化算法。

核方法

核方法主要针对非线性可分问题，给定数据集 T = {(x1, y1), ..., (xn, yn)} 其中 xi ∈ R^n，对应的标记为 yi= {-1, +1}，如果能用 R^n 中一个超曲面将正负例正确分开，则称该问题为非线性可分问题。

用通俗的话来说，非线性可分问题就是有非常多的错误（而不是软间隔的一点点错误），完全无法线性可分的问题。

对于这类问题有两种思路：

  • 感知机 PLA：大于一层隐层 + 非线性变换可以拟合任意曲线。
  • 非线性可分，经过一个非线性转换将原空间的数据映射到新空间，变为线性可分（高维比低维更易线性可分）。核技巧属于这样的方法。

核函数与核技巧

频率派的优化问题最后都可以使用拉格朗日转为对偶问题进行求解，而对偶问题中有一项是 x 的内积：

那么对于非线性问题，上式的内积就变成了非线性转换的内积：

实际问题中，φ(x) 有时候可能维度很高，导致很难求解（更不用说还要求解内积）。是否有种方法能够不求解 φ 而直接获得内积呢（因为我们实际上并不关心 φ 是什么，而只关心它的内积）？核函数就是这样的方法：

则称 K 是一个核函数。

此时，假设我们已经找到一个 K，那么可以直接使用 K 得到 φ 的内积，这种取巧的方法称为核技巧。

使用了核方法的 SVM 则称为核 SVM，其基本模型不变（硬间隔或软间隔），只是将其中的内积变为核函数即可求解。

正定核

使用核技巧的一个很重要的问题就是：能否直接判断一个给定的函数 K 是不是核函数，或者说 K 满足什么条件才能成为核函数。通常所说的核函数就是正定核函数。

正定核函数的充要条件（另一个定义）为：

k 为对称函数。如果 K 满足以下性质：

  • 对称性：K(x,z) = K(z,x)
  • 正定性：任取 N 个元素，x, x2, ..., xn ∈ X，对应的 Gram 矩阵是半正定的

那么称 K(x,z) 为正定核函数。

回到本节开始的问题，其实就是要证明：

必要性证明：

已知 K(x,z) = <φ(x), φ(z)>，证 Gram 矩阵半正定，且 K 对称。

根据内积的对称性可知 K 满足对称性。

要证明正定性，只需要证：存在 α ∈ R^n，α^T · K · α ≥ 0。
左边展开结果为一个实数：

所以 K 是半正定的。

充分性证明：

已知 K 对称且 Gram 矩阵半正定，证 K(x,z) = <φ(x), φ(z)>。以下内容来自李航老师《统计机器学习》。

定义映射：

定义线性组合：

由 f 组成的集合 S，由于 S 对加法和数乘封闭，所以 S 构成一个向量空间。

在集合 S 上定义点乘运算：

证明过程可以参考李航老师《统计机器学习方法》，不再赘述。由此可得：

此时 S 为再生核希尔伯特空间，因为核 K 具有再生性（满足上面两个条件）。

因此，给定对称函数 K，K 关于 x 的 Gram 矩阵是半正定的，可对 K 构造从 X 到希尔伯特空间 H 的映射：

再根据第二个条件可得：

这个证明感觉不是特别理解，然后又看到有用矩阵分解证明的方法：

因为 K 对称，所以

其中 V 是由特征向量组成的正交矩阵，Λ 是特征值组成的对角矩阵。

不过这块整体有点迷，没有弄得特别清晰，后来看到一个 MIT 的 Lecture Notes 觉得比较清楚，推荐阅读。

【希尔伯特空间】：完备的、可能是无限维的、被赋予内积的线性空间。

  • 线性空间：向量空间（满足加法和数乘）
  • 完备：可理解为对极限操作封闭（存在极限且极限也属于 Hilbert 空间）
  • 内积，满足三个特征：
    • 对称性：<f, g> = <g, f>, f,g ∈ H
    • 正定性：<f, f> ≥ 0, "=" <=> f=0
    • 线性：<r1f1 + r2f2, g> = r1<f, g> + r2<f2, g>

常用核函数

多项式核函数：

对应的支持向量机是一个 p 次多项式分类器。

高斯核函数：

对应的支持向量机是高斯径向基函数分类器。

字符串核函数：

定义在离散集合上的核函数。字符串核是定义在字符串集合上的核函数。

考虑有限字符集 Σ，字符串 s 是从 Σ 中取出的有限个字符序列，s 的长度为 |s|，元素记为 s(1)s(2)…s(|s|)。所有长度为 n 的字符串集合记为 Σ^n，所有字符串的集合记为：

假设 S 是长度大于或等于 n 的字符串集合，s ∈ S，字符串集合 S 到特征空间 的映射为 φn(s)。 表示定义在 Σ^n 上的实数空间，其每一维对应一个字符串 u ∈ Σ^n，映射 φn(s) 将字符串 s 对应于空间 R 的一个向量，在 u 维上的取值为：

其中，0 ≤ λ ≤ 1 是一个衰减参数，l(i) 表示字符串 i 的长度，求和在 s 中所有与 u 相同的子串上进行。

两个字符串 s 和 t 上的字符串核函数是基于映射 φn 的特种空间中的内积：

上式给出了字符串 s 和 t 中长度等于 n 的所有子串组成的特征向量的余弦相似度。相同的子串越多，s 和 t 越相似。

算法

  • 输入：数据集 T = {(x1,y1), (x2, y2), ..., (xn, yn)}，其中 xi ∈ R^n, yi ∈ {+1, -1} , i=1,2,...,N
  • 输出：分类决策函数

利用对偶问题求解算法如下：

  • 选择适当的核函数 K 和 惩罚参数 C，构造并求解最优化问题：

    得到最优解 α* = (α1*, α2*, ..., αN*)^T

  • 根据 KKT 计算 w*，并选择 α* 的一个分量 0 < αj* < C 计算 b*:

  • 构造决策函数：

SMO

SMO（Sequential minimal optimization）是一种启发式算法，主要用于解决训练样本很大时，高效地实现支持向量机的学习问题，具体看就是要解决式（1）的凸二次规划对偶问题。

在正式开始之前需要介绍一种优化方法： Coordinate Ascent，假设我们要解决如下优化问题：

Coordinate ascent 的解决思路如下：

1
2
3
4
5
Loop until convergence: {
	For i = 1,...,n {
        α_i := arg min_α W(α1, α2, ..., αn)
    }
}

在内循环中，固定住除了 ai 的所有元素，通过调整参数 ai 重新优化 W，优化完每个 a 后就能得到最终的最优解。

SMO 的基本思路如下：

  • 如果所有变量的解都满足 KKT 条件，那么这个解就是问题的最优解（KKT 是该最优化问题的充要条件）。
  • 否则选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。

这里第二步用到的就是 Coordinate Ascent，不过需要注意的是，因为有（1）式的约束条件，所以如果只留一个自由变量而固定住其他变量其实等于固定了所有变量。这里选择两个变量其实也只有一个是自由变量。比如假设 α1 和 α2 为两个变量，α3, α4, …, αn 固定，根据约束条件可得：

如果 α2 确定，α1 自然也就确定了。

这样就将原始的优化问题变成一个个子问题，因为二次规划问题也是求极小，所以子问题的解应该能更接近原始问题的解。而且子问题可以通过解析法直接求得，这就提高了速度。

SMO 包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。

两个变量二次规划求解

假设选择的变量为：α1 和 α2，其他变量固定，原始的优化问题（1）可以写为：

该问题即为有约束的二次规划问题，可以求得极值。

根据约束条件可知， α1 和 α2 一定在下面这个正方形区域中：

图片来自 Stanford CS229（第二个参考文献）

同时，α1 也可以表示为：

于是，目标函数可以写为：

假设式（2）的初始可行解为 ，最优解为 ，沿着约束方向未剪辑时 α2 的最优解为 ，那么：

为了记录方便，记：

于是目标函数可以表示为：

对 α2 求导并令其等于 0：

将 以及 v 代入得：

于是得：

其中：

φ 是输入空间到特征空间的映射。

进而可得：

变量选择

每个子问题要选择两个变量，其中至少有一个不满足 KKT 条件（如果两个变量都满足 KKT 条件的话，最优解已经得到了）。

第一个变量的选择为外循环，选择违反 KKT 最严重的点。具体地，根据对偶互补条件：

可得：

然后检验样本点（xi, yi）是否满足上面的条件。

在检验过程中，外循环在首先遍历所有满足条件 0<αi<C 的样本点（间隔边界上的支持向量点），检验它们是否满足上述（KKT）条件。如果这些点都满足，则遍历整个数据集，检验它们是否满足。

第二个变量的选择为内循环，假设外循环已经找到了第一个变量 α1，现在要找第二个变量，选择的标准是希望 α2 有足够大的变化（有助于快速收敛）。因为 α1 已定，E1 也已定，根据式（5），要使 α2 最大，如果 E1>0，选择最小的 Ei 作为 E2，如果 E1<0，选择最大的 Ei 作为 E2。

如果按照上面方法找到的 α2 不能使目标函数有足够的下降，则采用启发式方法继续选择 α2：

  • 遍历在间隔边界上的点，依次将其对应的变量作为 α2，直到目标函数有足够的下降
  • 如果找不到合适的 α2，就遍历数据集
  • 如果还是找不到就放弃第一个 α1，重新选择一个

每次完成两个变量的优化后都要重新计算 b，当 时，由上面的条件可知：

于是：

再根据 E 的定义：

进而可得：

同理，如果 可得：

如果新的 α1 和 α2 都满足条件 0<α<C，那么新的 b1=b2；如果新的 α1 和 α2 是 0 或 C，新的 b1 和 b2 以及它们之间的数都是符合 KKT 条件的阈值，此时选择中点作为新 b。

完成两个变量的优化后，还需更新对应的 Ei 值：

其中 S 是所有支持向量 xj 的集合。

算法

  • 输入：数据集 T = {(x1,y1), (x2, y2), ..., (xn, yn}，其中 xi ∈ R^n, yi ∈ {+1, -1} , i=1,2,...,N，精度 ε
  • 输出：近似解 α

步骤如下：

  • 取初始值 α0 = 0，令 k = 0

  • 选取优化变量 ，解析求解最优化问题（2），得到最优解 ，更新 α 为

  • 如果在精度 ε 内满足停机条件：

    则转下一步，否则令 k=k+1，回到第二步

  • 取近似解

实现

具体实现可以参考这里，本文主要梳理一下主要的流程。

  • 首先是初始化参数，主要包括 α，b 和 E（也就是 error）
  • 接下来就是初始化 α1，根据 SMO 算法，首先选择满足条件 0<αi<C 的样本点，即间隔边界上的支持向量点，检验它们是否满足 KKT 条件。如果这些点都满足，则遍历整个数据集，检验它们是否满足。
  • 找到 α1 后，可以根据 E 的差距最大选择 α2，进而可以求得新的 α，b，E 和支持向量。如果 α2 不能使目标函数有足够的下降，则根据启发式规则重新选择 α2，即：
    • 遍历在间隔边界上的点，依次作为 α2 直到目标函数有足够的下降
    • 再不行就遍历数据集
    • 还是不行就放弃第一个 α1，重新选择一个
  • 直到计算完所有 α 或达到最大迭代次数为止。

参考资料