4.支持向量机(二)

11-10 1,047 views

8 核函数(Kernels)

考虑我们最初在“线性回归”中提出的问题,特征是房子的面积 x,这里的 x 是实数,结果 y 是房子的价格。假设我们从样本点的分布中看到 x 和 y 符合 3 次曲线,那么我们希望 使用 x 的三次多项式来逼近这些样本点。那么首先需要将特征 x 扩展到三维(x, x2, x3),然后寻找特征和结果之间的模型。我们将这种特征变换称作特征映射(feature mapping)。映射 函数称作ϕ,在这个例子中

4-01

我们希望将得到的特征映射后的特征应用于 SVM 分类,而不是最初的特征。这样,我 们需要将前面WT+ b公式中的内积从< x(i), x>,映射到< ϕ(x(i)), ϕ(x ) >。

至于为什么需要映射后的特征而不是最初的特征来参与计算,上面提到的(为了更好地拟合)是其中一个原因,另外的一个重要原因是样例可能存在线性不可分的情况,而将特征 映射到高维空间后,往往就可分了。(在《数据挖掘导论》Pang-Ning Tan 等人著的《支持向量机》那一章有个很好的例子说明)

将核函数形式化定义,如果原始特征内积是< x,  z>,映射后为< ϕ(x), ϕ(z ) >,那么定义核函数(Kernel)为

4-02

到这里,我们可以得出结论,如果要实现该节开头的效果,只需先计算 ϕ(x),然后计 算ϕ(x)Tϕ(z)即可,然而这种计算方式是非常低效的。比如最初的特征是 n 维的,我们将其 映射到n2维,然后再计算,这样需要O(n2)的时间。那么我们能不能想办法减少计算时间呢?

先看一个例子,假设 x 和 z 都是 n 维的,

4-03

展开后,得

4-04

这个时候发现我们可以只计算原始特征 x 和 z 内积的平方(时间复杂度是 O(n)),就等 价与计算映射后特征的内积。也就是说我们不需要花O(n2)时间了。

现在看一下映射函数(n=3 时),根据上面的公式,得到

4-image1

也就是说核函数K (x , z) = (xTz)2只能在选择这样的ϕ作为映射函数时才能够等价于映 射后特征的内积。

再看一个核函数

4-image2

对应的映射函数(n=3 时)是

4-image3

更一般地,核函数 K (x , z) = (xTz + d )2对应的映射后特征维度为(n +d ) /( d)

由于计算的是内积,我们可以想到 IR 中的余弦相似度,如果 x 和 z 向量夹角越小,那 么核函数值越大,反之,越小。因此,核函数值是ϕ(x)和ϕ(z)的相似度。

再看另外一个核函数

4-image4

 

这时,如果 x 和 z 很相近(||x − z|| ≈ 0),那么核函数值为 1,如果 x 和 z 相差很大 (||x − z|| ≫ 0),那么核函数值约等于 0。由于这个函数类似于高斯分布,因此称为高斯核函数,也叫做径向基函数(Radial Basis Function 简称 RBF)。它能够把原始特征映射到无穷维。

既然高斯核函数能够比较 x 和 z 的相似度,并映射到 0 到 1,回想 logistic 回归,sigmoid函数可以,因此还有 sigmoid 核函数等等。

下面有张图说明在低维线性不可分时,映射到高维后就可分了,使用高斯核函数。

4-image5

注意,使用核函数后,怎么分类新来的样本呢?线性的时候我们使用 SVM 学习出 w 和 b,新来样本 x 的话,我们使用wTx + b来判断,如果值大于等于 1,那么是正类,小于等是 负 类 。 在 两 者 之 间 , 认 为 无 法 确 定 。 如 果 使 用 了 核 函 数 后 ,wTx + b 就 变成了 wTϕ(x) + b ,是否先要找到 ϕ(x),然后再预测?答案肯定不是了,找 ϕ(x)很麻烦,回想我们之前说过的

4-image6

只需将< x i ), x >替换成  K( x i ), x),然后值的判断同上。

9 核函数有效性判定

问题:给定一个函数 K,我们能否使用 K 来替代计算 ϕ(x)Tϕ(z),也就说,是否能够找 出一个ϕ,使得对于所有的 x 和 z,都有 K( x, z) = ϕ(x)Tϕ(z)?

比如给出了K( x, z) = ( xTz)2,是否能够认为 K 是一个有效的核函数。

下面来解决这个问题,给定 m 个训练样本{x(1), x(2), … , x(m)},每一个 x(i )对应一个特征向量。那么,我们可以将任意两个 x(i )和 x(j )带入 K 中,计算得到Kij = ( x(i ), x(j))。I 可以 从 1 到 m,j 可以从 1 到 m,这样可以计算出 m*m 的核函数矩阵(Kernel Matrix)。为了方 便,我们将核函数矩阵和K (x, z)都使用 K 来表示。

如果假设 K 是有效的核函数,那么根据核函数定义4-05

可见,矩阵 K 应该是个对称阵。让我们得出一个更强的结论,首先使用符号 ϕk(x)来表 示映射函数ϕ(x)的第 k 维属性值。那么对于任意向量 z,得

4-image7

最后一步和前面计算 K( x, z) = ( xTz)2时类似。从这个公式我们可以看出,如果 K 是个 有效的核函数(即 K( x, z)和 ϕ(x)Tϕ(z)等价),那么,在训练集上得到的核函数矩阵 K 应该 是半正定的(K ≥ 0)

这样我们得到一个核函数的必要条件:

K 是有效的核函数 ==> 核函数矩阵 K 是对称半正定的。

可幸的是,这个条件也是充分的,由 Mercer 定理来表达。

Mercer 定理:

如果函数 K 是ℝn × ℝn → ℝ上的映射(也就是从两个 n 维向量映射到实数域)。那么如果 K 是一个有效核函数(也称为 Mercer 核函数),那么当且仅当对于训练样例{x(1), x(2), … , x(m)},其相应的核函数矩阵是对称半正定的。

Mercer 定理表明为了证明 K 是有效的核函数,那么我们不用去寻找 ϕ,而只需要在训练 集上求出各个 Kij ,然后判断矩阵 K 是否是半正定(使用左上角主子式大于等于零等方法) 即可。

许多其他的教科书在 Mercer 定理证明过程中使用了L2范数和再生希尔伯特空间等概念,但在特征是 n 维的情况下,这里给出的证明是等价的。

核函数不仅仅用在 SVM 上,但凡在一个模型后算法中出现了< x, z >,我们都可以常使 用 (x ,z )去替换,这可能能够很好地改善我们的算法。

10 规则化和不可分情况处理(Regularization and the non-separable case)

我们之前讨论的情况都是建立在样例线性可分的假设上,当样例线性不可分时,我们可以尝试使用核函数来将特征映射到高维,这样很可能就可分了。然而,映射后我们也不能100%保证可分。那怎么办呢,我们需要将模型进行调整,以保证在不可分的情况下,也能够尽可能地找出分隔超平面。

看下面两张图:

4-image8

可以看到一个离群点(可能是噪声)可以造成超平面的移动,间隔缩小,可见以前的模型对噪声非常敏感。再有甚者,如果离群点在另外一个类中,那么这时候就是线性不可分了。

这时候我们应该允许一些点游离并在在模型中违背限制条件(函数间隔大于 1)。我们设计得到新的模型如下(也称软间隔):

4-image9

引入非负参数 后(称为松弛变量),就允许某些样本点的函数间隔小于 1,即在最大间 隔区间里面,或者函数间隔是负数,即样本点在对方的区域中。而放松限制条件后,我们需要重新调整目标函数,以对离群点进行处罚,目标函数后面加上的C ∑mi=1ζi 就表示离群点越多,目标函数值越大,而我们要求的是尽可能小的目标函数值。这里的 C 是离群点的权重,C 越大表明离群点对目标函数影响越大,也就是越不希望看到离群点。我们看到,目标函数 控制了离群点的数目和程度,使大部分样本点仍然遵守限制条件。

模型修改后,拉格朗日公式也要修改如下:

4-image10

这里的αi和γi都是拉格朗日乘子,回想我们在拉格朗日对偶中提到的求法,先写出拉格 朗日公式(如上),然后将其看作是变量 w 和 b 的函数,分别对其求偏导,得到 w 和 b 的表 达式。然后代入公式中,求带入后公式的极大值。整个推导过程类似以前的模型,这里只写 出最后结果如下:

4-image11

此时,我们发现没有了参数 ,与之前模型唯一不同在于αi又多了αi ≤ C的限制条件。 需要提醒的是,b 的求值公式也发生了改变,改变结果在 SMO 算法里面介绍。先看看 KKT条件的变化:

4-image12

第一个式子表明在两条间隔线外的样本点前面的系数为 0,离群样本点前面的系数为 C,而支持向量(也就是在超平面两边的最大间隔线上)的样本点前面系数在(0,C)上。通过 KKT条件可知,某些在最大间隔线上的样本点也不是支持向量,相反也可能是离群点。

11 坐标上升法(Coordinate ascent)

在最后讨论W(α)的求解之前,我们先看看坐标上升法的基本原理。假设要求解下面的 优化问题:

4-image13

这里 W 是α向量的函数。之前我们在回归中提到过两种求最优解的方法,一种是梯度下 降法,另外一种是牛顿法。现在我们再讲一种方法称为坐标上升法(求解最小值问题时,称 作坐标下降法,原理一样)。

方法过程:

4-image14

最里面语句的意思是固定除αi 之外的所有αi ( j≠ i),这时 W 可看作只是关于αi 的函数, 那么直接对αi 求导优化即可。这里我们进行最大化求导的顺序 i 是从 1 到 m,可以通过更改 优化顺序来使 W 能够更快地增加并收敛。如果 W 在内循环中能够很快地达到最优,那么坐标上升法会是一个很高效的求极值方法。

下面通过一张图来展示:

4-image15

椭圆代表了二次函数的各个等高线,变量数为 2,起始坐标是(2,-2)。图中的直线式迭代优化的路径,可以看到每一步都会向最优值前进一步,而且前进路线是平行于坐标轴的,因为每一步只优化一个变量。

12 SMO 优化算法(Sequential minimal optimization)

SMO 算法由 Microsoft Research 的 John C. Platt 在 1998 年提出,并成为最快的二次规划 优化算法,特别针对线性 SVM 和数据稀疏时性能更优。关于 SMO 最好的资料就是他本人写的《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。

我拜读了一下,下面先说讲义上对此方法的总结。

首先回到我们前面一直悬而未解的问题,对偶函数最后的优化问题:

4-image11

要解决的是在参数{x(1), x(2), … , x(m)}上求最大值 W 的问题,至于 x(i)和y(i )都是已知数。C

由我们预先设定,也是已知数。

按照坐标上升的思路,我们首先固定除α1以外的所有参数,然后在α1上求极值。等一 下,这个思路有问题,因为如果固定α1以外的所有参数,那么 α1将不再是变量(可以由其他值推出),因为问题中规定了

4-image16

因此,我们需要一次选取两个参数做优化,比如α1和 α2,此时 α2可以由α1和其他参数 表示出来。这样回带到 W 中,W 就只是关于α1的函数了,可解。

这样,SMO 的主要步骤如下:

4-image17

意思是,第一步选取一对αi和αj,选取方法使用启发式方法(后面讲)。第二步,固定除αi和αj之外的其他参数,确定 W 极值条件下的αi,αj由 表示。

SMO 之所以高效就是因为在固定其他参数后,对一个参数优化过程很高效。

下面讨论具体方法: 假设我们选取了初始值{x(1), x(2), … , x(m)}满足了问题中的约束条件。接下来,我们固定{x(1), x(2), … , x(m)},这样 W 就是α1和 α2的函数。并且α1和 α2满足条件:

4-image18

由于{x(1), x(2), … , x(m)}都是已知固定值,因此为了方面,可将等式右边标记成实数值ζ。

4-image19

当y(1)和y(2)异号时,也就是一个为 1,一个为-1 时,他们可以表示成一条直线,斜率为1。如下图

4-06

横轴是α1,纵轴是α2,α1和α2既要在矩形方框内,也要在直线上,因此

4-07

同理,当y(1)和y(2)同号时,

4-08

然后我们打算将α1用 α2表示:

4-image21

然后反代入 W 中,得

4-image22

展开后 W 可以表示成a α22 + b α2 + c。其中 a,b,c 是固定值。这样,通过对 W 进行求导 可以得到 α2,然而要保证 α2满足L ≤ α2 ≤ H,我们使用 α2 new,unclipped ,表示求导求出来的 α2,然而最后的α 2,要根据下面情况得到:

4-image23

这样得到 α2new后,我们可以得到α1的新值 α1new

下面进入 Platt 的文章,来找到启发式搜索的方法和求 b 值的公式。

这篇文章使用的符号表示有点不太一样,不过实质是一样的,先来熟悉一下文章中符号的表示。

文章中定义特征到结果的输出函数为

4-image24

与我们之前的wTx (i) +b 实质是一致的。

原始的优化问题为,

4-image25

求导得到:

4-image26

经过对偶后为:

4-image27

s.t.

4-image28

这里与 W 函数是一样的,只是符号求反后,变成求最小值了。yi 和y(i)是一样的,都表 示第 i 个样本的输出结果(1 或-1)。

经过加入松弛变量ζ后,模型修改为:

4-image29

由公式(7)代入(1)中可知,

4-image30

这个过程和之前对偶过程一样。

重新整理我们要求的问题为:

4-image31

与之对应的 KKT 条件为:

4-image32

这个 KKT 条件说明,在两条间隔线外面的点,对应前面的系数αi为 0,在两条间隔线里 面的对应αi为 C,在两条间隔线上的对应的系数αi在 0 和 C 之间。

将我们之前得到 L 和 H 重新拿过来:

4-image33

4-image34

之前我们将问题进行到这里,然后说将α1用α2表示后代入 W 中,这里将代入Ψ中,得

4-image35

其中

4-image36

这里的 α1和 α2代表某次迭代前的原始值,因此是常数,而α1和α2是变量,待求。公式 (24)中的最后一项是常数。

由于α1和α2满足以下公式

4-09

因为 αi(i > 2)的值是固定值,在迭代前后不会变。

那么用 s 表示y1y2,上式两边乘以 y1时,变为:

4-image37

其中

4-10

代入(24)中,得

4-image38

这时候只有α2是变量了,求导

4-image39

如果Ψ的二阶导数大于 0(凹函数),那么一阶导数为 0 时,就是极小值了。 假设其二阶导数为 0(一般成立),那么上式化简为:

4-image40

将 w 和 v 代入后,继续化简推导,得(推导了六七行推出来了)

4-image41

我们使用η来表示:

4-image42

通常情况下目标函数是正定的,也就是说,能够在直线约束方向上求得最小值,并且η > 0。

那么我们在(30)两边都除以η可以得到

4-image43

这里我们使用α2new表示优化后的值,α2是迭代前的值,E= uiyi。与之前提到的一样α2new不是最终迭代后的值,需要进行约束:

4-image44

那么

4-image45

在特殊情况下,η可能不为正,如果核函数 K 不满足 Mercer 定理,那么目标函数可能变 得非正定,η可能出现负值。即使 K 是有效的核函数,如果训练样本中出现相同的特征 x,那么η仍有可能为 0。SMO 算法在η不为正值的情况下仍有效。为保证有效性,我们可以推 导出η就是Ψ的二阶导数,η < 0,Ψ没有极小值,最小值在边缘处取到(类比y = − x2),η = 0时 更是单调函数了,最小值也在边缘处取得,而a2的边缘就是 L 和 H。这样将 a2 = L和 a2 = H分别代入Ψ中即可求得Ψ的最小值,相应的 a2 = L还是 a2 = H也可以知道了。具体计算公式如 下:

4-image46

至此,迭代关系式除了 b 的推导式以外,都已经推出。

b 每一步都要更新,因为前面的 KKT 条件指出了ai 和 yiui的关系,而ui和 b 有关,在每 一步计算出ai后,根据 KKT 条件来调整 b。

b 的更新有几种情况:

4-image47

这里的界内指0 <ai < C,界上就是等于 0 或者 C 了。

前面两个的公式推导可以根据

4-11

和对于0 <ai < C 有yiui = 1的 KKT 条件推出。

这样全部参数的更新公式都已经介绍完毕,附加一点,如果使用的是线性核函数,我们就可以继续使用 w 了,这样不用扫描整个样本库来作内积了。

w 值的更新方法为:

4-image48

根据前面的

4-image26

公式推导出。

13 SMO 中拉格朗日乘子的启发式选择方法

终于到了最后一个问题了,所谓的启发式选择方法主要思想是每次选择拉格朗日乘子的 时候,优先选择样本前面系数0 <ai < C的ai作优化(论文中称为无界样例),因为在界上 ( ai为 0 或 C)的样例对应的系数ai一般不会更改。

这条启发式搜索方法是选择第一个拉格朗日乘子用的,比如前面的 a2。那么这样选择 的话,是否最后会收敛?可幸的是 Osuna 定理告诉我们只要选择出来的两个ai中有一个违背 了 KKT 条件,那么目标函数在一步迭代后值会减小。违背 KKT 条件不代表0 <ai < C,在界 上也有可能会违背。是的,因此在给定初始值 ai=0 后,先对所有样例进行循环,循环中碰 到违背 KKT 条件的(不管界上还是界内)都进行迭代更新。等这轮过后,如果没有收敛,第 二轮就只针对0 <ai < C的样例进行迭代更新。

在第一个乘子选择后,第二个乘子也使用启发式方法选择,第二个乘子的迭代步长大致 正比于|E1 − E2|,选择第二个乘子能够最大化|E1 − E2|。即当E1为正时选择负的绝对值最大 的E2,反之,选择正值最大的E2

最后的收敛条件是在界内(0 <ai < C)的样例都能够遵循 KKT 条件,且其对应的ai只在极小的范围内变动。

至于如何写具体的程序,请参考 John C. Platt 在论文中给出的伪代码。

14 总结

这份 SVM 的讲义重点概括了 SVM 的基本概念和基本推导,中规中矩却又让人醍醐灌顶。起初让我最头疼的是拉格朗日对偶和 SMO,后来逐渐明白拉格朗日对偶的重要作用是将 w的计算提前并消除 w,使得优化函数变为拉格朗日乘子的单一参数优化问题。而 SMO 里面迭代公式的推导也着实让我花费了不少时间。

对比这么复杂的推导过程,SVM 的思想确实那么简单。它不再像 logistic 回归一样企图 去拟合样本点中间加了一层 sigmoid 函数变换),而是就在样本中去找分隔线,为了评判哪条分界线更好,引入了几何间隔最大化的目标。

之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中,发现了 w可以由特征向量内积来表示,进而发现了核函数,仅需要调整核函数就可以将特征进行低维 到高维的变换,在低维上进行计算,实质结果表现在高维上。由于并不是所有的样本都可分, 为了保证 SVM 的通用性,进行了软间隔的处理,导致的结果就是将优化问题变得更加复杂, 然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题,也被拉格朗日对偶和 SMO 算法化解,使 SVM 趋向于完美。

另外,其他很多议题如 SVM 背后的学习理论、参数选择问题、二值分类到多值分类等等还没有涉及到,以后有时间再学吧。其实朴素贝叶斯在分类二值分类问题时,如果使用对数比,那么也算作线性分类器。

7.混合高斯模型(Mixtures of Gaussians)和 EM 算法

这篇讨论使用期望最大化算法(Expectation-Maximization)来进行密度估计(density estimation)。 与k-means 一样,给定的训练样本是{x (1), … ,x (m)},我...

阅读全文

6. K-means聚类算法

K-means也是聚类算法中最简单的一种了,但是里面包含的思想却是不一般。聚类属于无监督学习,以往的回归、朴素贝叶斯、SVM等都是有类别标签y的,也就是说样例...

阅读全文

欢迎留言