支持向量机svm(下)


支持向量机 SVM(下) JerryLead csxulijie@gmail.com 2011 年 3 月 17 日星期四 7 核函数(Kernels) 考虑我们最初在“线性回归”中提出的问题,特征是房子的面积 x,这里的 x 是实数, 结果 y 是房子的价格。假设我们从样本点的分布中看到 x 和 y 符合 3 次曲线,那么我们希望 使用 x 的三次多项式来逼近这些样本点。那么首先需要将特征 x 扩展到三维(x, 푥2, 푥3),然后 寻找特征和结果之间的模型。我们将这种特征变换称作特征映射(feature mapping)。映射 函数称作ϕ,在这个例子中 ϕ(x) = [ 푥 푥2 푥3 ] 我们希望将得到的特征映射后的特征应用于 SVM 分类,而不是最初的特征。这样,我 们需要将前面 푥 公式中的内积从< 푥( ),푥 >,映射到< 휙(푥(푖)), 휙(푥) >。 至于为什么需要映射后的特征而不是最初的特征来参与计算,上面提到的(为了更好地 拟合)是其中一个原因,另外的一个重要原因是样例可能存在线性不可分的情况,而将特征 映射到高维空间后,往往就可分了。(在《数据挖掘导论》Pang-Ning Tan 等人著的《支持向 量机》那一章有个很好的例子说明) 将核函数形式化定义,如果原始特征内积是< x,푧 >,映射后为< 휙(x), 휙(푧) >,那么 定义核函数(Kernel)为 퐾(푥, 푧) = 휙(푥) 휙(푧) 到这里,我们可以得出结论,如果要实现该节开头的效果,只需先计算휙(푥),然后计 算 휙(푥) 휙(푧)即可,然而这种计算方式是非常低效的。比如最初的特征是 n 维的,我们将其 映射到n2维,然后再计算,这样需要O(n2)的时间。那么我们能不能想办法减少计算时间呢? 先看一个例子,假设 x 和 z 都是 n 维的, 퐾(푥, 푧) = (푥 푧)2 展开后,得 퐾(푥, 푧) = (푥 푧)2 = (∑ 푥푖푧푖 푛 푖=1 )(∑ 푥푗푧푗 푛 푗=1 ) = ∑ ∑ 푥푖 푛 푗=1 푥푗푧푖푧푗 푛 푖=1 = ∑ ∑(푥푖 푛 푗=1 푥푗)(푧푖푧푗) 푛 푖=1 = 휙(푥) 휙(푧) 这个时候发现我们可以只计算原始特征 x 和 z 内积的平方(时间复杂度是 O(n)),就等 价与计算映射后特征的内积。也就是说我们不需要花O(n2)时间了。 现在看一下映射函数(n=3 时),根据上面的公式,得到 也就是说核函数퐾(푥, 푧) = (푥 푧)2只能在选择这样的ϕ作为映射函数时才能够等价于映 射后特征的内积。 再看一个核函数 对应的映射函数(n=3 时)是 更一般地,核函数퐾(푥, 푧) = (푥 푧 푐)푑对应的映射后特征维度为(n d 푑 )。(这个我一直 没有理解)。 由于计算的是内积,我们可以想到 IR 中的余弦相似度,如果 x 和 z 向量夹角越小,那 么核函数值越大,反之,越小。因此,核函数值是휙(푥)和휙(푧)的相似度。 再看另外一个核函数 这时,如果 x 和 z 很相近(||x − z|| ≈ 0),那么核函数值为 1,如果 x 和 z 相差很大 (||x − z|| ≫ 0),那么核函数值约等于 0。由于这个函数类似于高斯分布,因此称为高斯核 函数,也叫做径向基函数(Radial Basis Function 简称 RBF)。它能够把原始特征映射到无穷维。 既然高斯核函数能够比较 x 和 z 的相似度,并映射到 0 到 1,回想 logistic 回归,sigmoid 函数可以,因此还有 sigmoid 核函数等等。 下面有张图说明在低维线性不可分时,映射到高维后就可分了,使用高斯核函数。 来自 Eric Xing 的 slides 注意,使用核函数后,怎么分类新来的样本呢?线性的时候我们使用 SVM 学习出 w 和 b,新来样本 x 的话,我们使用 푥 来判断,如果值大于等于 1,那么是正类,小于等 于是负类。在两者之间,认为无法确定。如果使用了核函数后, 푥 就变成了 휙(x) ,是否先要找到휙(x),然后再预测?答案肯定不是了,找휙(x)很麻烦,回想我 们之前说过的 只需将< 푥(푖), 푥 >替换成퐾(푥(푖), 푥),然后值的判断同上。 8 核函数有效性判定 问题:给定一个函数 K,我们能否使用 K 来替代计算 휙(푥) 휙(푧),也就说,是否能够找 出一个휙,使得对于所有的 x 和 z,都有퐾(푥, 푧) = 휙(푥) 휙(푧)? 比如给出了퐾(푥, 푧) = (푥 푧)2,是否能够认为 K 是一个有效的核函数。 下面来解决这个问题,给定 m 个训练样本*푥(1), 푥(2),…, 푥(푚)+,每一个푥(푖)对应一个特征 向量。那么,我们可以将任意两个푥(푖)和푥(푗)带入 K 中,计算得到퐾푖푗 = 퐾(푥(푖), 푥(푗))。I 可以 从 1 到 m,j 可以从 1 到 m,这样可以计算出 m*m 的核函数矩阵(Kernel Matrix)。为了方 便,我们将核函数矩阵和퐾(푥, 푧)都使用 K 来表示。 如果假设 K 是有效的核函数,那么根据核函数定义 퐾푖푗 = 퐾(푥(푖), 푥(푗)) = 휙(푥(푖)) 휙(푥(푗)) = 휙(푥(푗)) 휙(푥(푖)) = 퐾(푥(푗), 푥(푖)) = 퐾푗푖 可见,矩阵 K 应该是个对称阵。让我们得出一个更强的结论,首先使用符号휙푘(푥)来表 示映射函数휙(푥)的第 k 维属性值。那么对于任意向量 z,得 最后一步和前面计算퐾(푥, 푧) = (푥 푧)2时类似。从这个公式我们可以看出,如果 K 是个 有效的核函数(即퐾(푥, 푧)和휙(푥) 휙(푧)等价),那么,在训练集上得到的核函数矩阵 K 应该 是半正定的(K ≥ 0) 这样我们得到一个核函数的必要条件: K 是有效的核函数 ==> 核函数矩阵 K 是对称半正定的。 可幸的是,这个条件也是充分的,由 Mercer 定理来表达。 Mercer 定理: 如果函数 K 是ℝn × ℝn → ℝ上的映射(也就是从两个 n 维向量映射到实数域)。那么如果 K 是一个有效核函数(也称为 Mercer 核函数),那么当且仅当对于训练样例*푥(1), 푥(2),…, 푥(푚)+, 其相应的核函数矩阵是对称半正定的。 Mercer 定理表明为了证明 K 是有效的核函数,那么我们不用去寻找휙,而只需要在训练 集上求出各个퐾푖푗,然后判断矩阵 K 是否是半正定(使用左上角主子式大于等于零等方法) 即可。 许多其他的教科书在 Mercer 定理证明过程中使用了L2范数和再生希尔伯特空间等概念, 但在特征是 n 维的情况下,这里给出的证明是等价的。 核函数不仅仅用在 SVM 上,但凡在一个模型后算法中出现了< x, z >,我们都可以常使 用퐾(푥, 푧)去替换,这可能能够很好地改善我们的算法。 9 规则化和不可分情况处理(Regularization and the non-separable case) 我们之前讨论的情况都是建立在样例线性可分的假设上,当样例线性不可分时,我们可 以尝试使用核函数来将特征映射到高维,这样很可能就可分了。然而,映射后我们也不能 100%保证可分。那怎么办呢,我们需要将模型进行调整,以保证在不可分的情况下,也能 够尽可能地找出分隔超平面。 看下面两张图: 可以看到一个离群点(可能是噪声)可以造成超平面的移动,间隔缩小,可见以前的模 型对噪声非常敏感。再有甚者,如果离群点在另外一个类中,那么这时候就是线性不可分了。 这时候我们应该允许一些点游离并在在模型中违背限制条件(函数间隔大于 1)。我们 设计得到新的模型如下(也称软间隔): 引入非负参数휉푖后(称为松弛变量),就允许某些样本点的函数间隔小于 1,即在最大间 隔区间里面,或者函数间隔是负数,即样本点在对方的区域中。而放松限制条件后,我们需 要重新调整目标函数,以对离群点进行处罚,目标函数后面加上的C ∑ 휉푖 m 푖=1 就表示离群点越 多,目标函数值越大,而我们要求的是尽可能小的目标函数值。这里的 C 是离群点的权重, C 越大表明离群点对目标函数影响越大,也就是越不希望看到离群点。我们看到,目标函数 控制了离群点的数目和程度,使大部分样本点仍然遵守限制条件。 模型修改后,拉格朗日公式也要修改如下: 这里的훼푖和훾푖都是拉格朗日乘子,回想我们在拉格朗日对偶中提到的求法,先写出拉格 朗日公式(如上),然后将其看作是变量 w 和 b 的函数,分别对其求偏导,得到 w 和 b 的表 达式。然后代入公式中,求带入后公式的极大值。整个推导过程类似以前的模型,这里只写 出最后结果如下: 此时,我们发现没有了参数휉푖,与之前模型唯一不同在于훼푖又多了훼푖 ≤ C的限制条件。 需要提醒的是,b 的求值公式也发生了改变,改变结果在 SMO 算法里面介绍。先看看 KKT 条件的变化: 第一个式子表明在两条间隔线外的样本点前面的系数为 0,离群样本点前面的系数为 C, 而支持向量(也就是在超平面两边的最大间隔线上)的样本点前面系数在(0,C)上。通过 KKT 条件可知,某些在最大间隔线上的样本点也不是支持向量,相反也可能是离群点。 10 坐标上升法(Coordinate ascent) 在最后讨论W(α)的求解之前,我们先看看坐标上升法的基本原理。假设要求解下面的 优化问题: 这里 W 是α向量的函数。之前我们在回归中提到过两种求最优解的方法,一种是梯度下 降法,另外一种是牛顿法。现在我们再讲一种方法称为坐标上升法(求解最小值问题时,称 作坐标下降法,原理一样)。 方法过程: 最里面语句的意思是固定除훼푖之外的所有훼푗(𝑗 ≠ ),这时 W 可看作只是关于훼푖的函数, 那么直接对훼푖求导优化即可。这里我们进行最大化求导的顺序 i 是从 1 到 m,可以通过更改 优化顺序来使 W 能够更快地增加并收敛。如果 W 在内循环中能够很快地达到最优,那么坐 标上升法会是一个很高效的求极值方法。 下面通过一张图来展示: 椭圆代表了二次函数的各个等高线,变量数为 2,起始坐标是(2,-2)。图中的直线式迭代 优化的路径,可以看到每一步都会向最优值前进一步,而且前进路线是平行于坐标轴的,因 为每一步只优化一个变量。 11 SMO 优化算法(Sequential minimal optimization) SMO 算法由 Microsoft Research 的 John C. Platt 在 1998 年提出,并成为最快的二次规划 优化算法,特别针对线性 SVM 和数据稀疏时性能更优。关于 SMO 最好的资料就是他本人写 的《 Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。 我拜读了一下,下面先说讲义上对此方法的总结。 首先回到我们前面一直悬而未解的问题,对偶函数最后的优化问题: 要解决的是在参数*훼1, 훼2,…, 훼푛+上求最大值 W 的问题,至于푥(푖)和y(푖)都是已知数。C 由我们预先设定,也是已知数。 按照坐标上升的思路,我们首先固定除훼1以外的所有参数,然后在훼1上求极值。等一 下,这个思路有问题,因为如果固定훼1以外的所有参数,那么훼1将不再是变量(可以由其 他值推出),因为问题中规定了 因此,我们需要一次选取两个参数做优化,比如훼1和훼2,此时훼2可以由훼1和其他参数 表示出来。这样回带到 W 中,W 就只是关于훼1的函数了,可解。 这样,SMO 的主要步骤如下: 意思是,第一步选取一对훼푖和훼푗,选取方法使用启发式方法(后面讲)。第二步,固定 除훼푖和훼푗之外的其他参数,确定 W 极值条件下的훼푖,훼푗由훼푖表示。 SMO 之所以高效就是因为在固定其他参数后,对一个参数优化过程很高效。 下面讨论具体方法: 假设我们选取了初始值*훼1, 훼2,…, 훼푛+满足了问题中的约束条件。接下来,我们固定 *훼3, 훼4,…, 훼푛+,这样 W 就是훼1和훼2的函数。并且훼1和훼2满足条件: 由于*훼3, 훼4,…, 훼푛+都是已知固定值,因此为了方面,可将等式右边标记成实数值ζ。 当y(1)和y(2)异号时,也就是一个为 1,一个为-1 时,他们可以表示成一条直线,斜率为 1。如下图: 横轴是훼1,纵轴是훼2,훼1和훼2既要在矩形方框内,也要在直线上,因此 퐿 = 푚𝑎푥(0, 훼2 − 훼1),퐻 = 푚 푛(퐶, 퐶 훼2 − 훼1) 同理,当y(1)和y(2)同号时, 퐿 = 푚𝑎푥(0, 훼2 훼1 − 퐶),퐻 = 푚 푛(퐶, 훼2 훼1) C C 훼2 훼1 L1 H1 L2 H2 2 (ζ, 0) (퐶, 퐶 − ζ) 훼1 − 훼2 = ζ 훼1 − 훼2 = ζ (퐶 ζ, 퐶) (0, −ζ) 然后我们打算将훼1用훼2表示: 然后反代入 W 中,得 展开后 W 可以表示成a훼22 훼2 푐。其中 a,b,c 是固定值。这样,通过对 W 进行求导 可以得到훼2,然而要保证훼2满足L ≤ 훼2 ≤ 퐻,我们使用훼2푛푒푤,푢푛푐푙푖푝푝푒푑表示求导求出来的훼2, 然而最后的훼2,要根据下面情况得到: 这样得到훼2푛푒푤后,我们可以得到훼1的新值훼1푛푒푤。 下面进入 Platt 的文章,来找到启发式搜索的方法和求 b 值的公式。 这篇文章使用的符号表示有点不太一样,不过实质是一样的,先来熟悉一下文章中符号 的表示。 文章中定义特征到结果的输出函数为 与我们之前的 푥( ) 实质是一致的。 原始的优化问题为: 求导得到: 经过对偶后为: s.t. 这里与 W 函数是一样的,只是符号求反后,变成求最小值了。y 和y( )是一样的,都表 示第 i 个样本的输出结果(1 或-1)。 经过加入松弛变量휉푖后,模型修改为: 由公式(7)代入(1)中可知, 这个过程和之前对偶过程一样。 重新整理我们要求的问题为: 与之对应的 KKT 条件为: 这个 KKT 条件说明,在两条间隔线外面的点,对应前面的系数훼푖为 0,在两条间隔线里 面的对应훼푖为 C,在两条间隔线上的对应的系数훼푖在 0 和 C 之间。 将我们之前得到 L 和 H 重新拿过来: 之前我们将问题进行到这里,然后说将훼1用훼2表示后代入 W 中,这里将代入Ψ中,得 其中 这里的훼1∗和훼2∗代表某次迭代前的原始值,因此是常数,而훼1和훼2是变量,待求。公式 (24)中的最后一项是常数。 由于훼1和훼2满足以下公式 푦1훼1 ∗ 푦2훼2 ∗ = − ∑ 푦푖훼푖 ∗ = 푦1훼1 푛 푖=3 푦2훼2 因为훼푖∗(i > 2)的值是固定值,在迭代前后不会变。 那么用 s 表示푦1푦2,上式两边乘以푦1时,变为: 其中 = −푦1 ∑ 푦푖훼푖 ∗ 푛 푖=3 代入(24)中,得 这时候只有훼2是变量了,求导 如果Ψ的二阶导数大于 0(凹函数),那么一阶导数为 0 时,就是极小值了。 假设其二阶导数为 0(一般成立),那么上式化简为: 将 w 和 v 代入后,继续化简推导,得(推导了六七行推出来了) 我们使用η来表示: 通常情况下目标函数是正定的,也就是说,能够在直线约束方向上求得最小值,并且 η > 0。 那么我们在(30)两边都除以η可以得到 这里我们使用훼2푛푒푤表示优化后的值,훼2是迭代前的值,퐸푖 = 푢푖 − 푦푖。 与之前提到的一样훼2푛푒푤不是最终迭代后的值,需要进行约束: 那么 在特殊情况下,η可能不为正,如果核函数 K 不满足 Mercer 定理,那么目标函数可能变 得非正定,η可能出现负值。即使 K 是有效的核函数,如果训练样本中出现相同的特征 x, 那么η仍有可能为 0。SMO 算法在η不为正值的情况下仍有效。为保证有效性,我们可以推 导出η就是Ψ的二阶导数,η < 0,Ψ没有极小值,最小值在边缘处取到(类比y = −푥2),η = 0时 更是单调函数了,最小值也在边缘处取得,而훼2的边缘就是 L 和 H。这样将훼2 = 퐿和훼2 = 퐻分 别代入Ψ中即可求得Ψ的最小值,相应的훼2 = L还是훼2 = 퐻也可以知道了。具体计算公式如 下: 至此,迭代关系式除了 b 的推导式以外,都已经推出。 b 每一步都要更新,因为前面的 KKT 条件指出了훼푖和푦푖푢푖的关系,而푢 和 b 有关,在每 一步计算出훼푖后,根据 KKT 条件来调整 b。 b 的更新有几种情况: 来自罗林开的 ppt 这里的界内指0 < 훼푖 < 퐶,界上就是等于 0 或者 C 了。 前面两个的公式推导可以根据 푦1훼1∗ 푦2훼2∗ = − ∑ 푦푖훼푖∗ = 푦1훼1 푛 푖=3 푦2훼2 和对于0 < 훼푖 < 퐶有푦푖푢푖 = 1的 KKT 条件推出。 这样全部参数的更新公式都已经介绍完毕,附加一点,如果使用的是线性核函数,我们 就可以继续使用 w 了,这样不用扫描整个样本库来作内积了。 w 值的更新方法为: 根据前面的 公式推导出。 12 SMO 中拉格朗日乘子的启发式选择方法 终于到了最后一个问题了,所谓的启发式选择方法主要思想是每次选择拉格朗日乘子的 时候,优先选择样本前面系数0 < 훼푖 < 퐶的훼푖作优化(论文中称为无界样例),因为在界上 (훼푖为 0 或 C)的样例对应的系数훼푖一般不会更改。 这条启发式搜索方法是选择第一个拉格朗日乘子用的,比如前面的훼2。那么这样选择 的话,是否最后会收敛?可幸的是 Osuna 定理告诉我们只要选择出来的两个훼푖中有一个违背 了 KKT 条件,那么目标函数在一步迭代后值会减小。违背 KKT 条件不代表0 < 훼푖 < 퐶,在界 上也有可能会违背。是的,因此在给定初始值훼푖=0 后,先对所有样例进行循环,循环中碰 到违背 KKT 条件的(不管界上还是界内)都进行迭代更新。等这轮过后,如果没有收敛,第 二轮就只针对0 < 훼푖 < 퐶的样例进行迭代更新。 在第一个乘子选择后,第二个乘子也使用启发式方法选择,第二个乘子的迭代步长大致 正比于|E1 − E2|,选择第二个乘子能够最大化|E1 − E2|。即当E1为正时选择负的绝对值最大 的E2,反之,选择正值最大的E2。 最后的收敛条件是在界内(0 < 훼푖 < 퐶)的样例都能够遵循 KKT 条件,且其对应的훼푖只 在极小的范围内变动。 至于如何写具体的程序,请参考 John C. Platt 在论文中给出的伪代码。 13 总结 这份 SVM 的讲义重点概括了 SVM 的基本概念和基本推导,中规中矩却又让人醍醐灌顶。 起初让我最头疼的是拉格朗日对偶和 SMO,后来逐渐明白拉格朗日对偶的重要作用是将 w 的计算提前并消除 w,使得优化函数变为拉格朗日乘子的单一参数优化问题。而 SMO 里面 迭代公式的推导也着实让我花费了不少时间。 对比这么复杂的推导过程,SVM 的思想确实那么简单。它不再像 logistic 回归一样企图 去拟合样本点(中间加了一层 sigmoid 函数变换),而是就在样本中去找分隔线,为了评判 哪条分界线更好,引入了几何间隔最大化的目标。 之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中,发现了 w 可以由特征向量内积来表示,进而发现了核函数,仅需要调整核函数就可以将特征进行低维 到高维的变换,在低维上进行计算,实质结果表现在高维上。由于并不是所有的样本都可分, 为了保证 SVM 的通用性,进行了软间隔的处理,导致的结果就是将优化问题变得更加复杂, 然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题,也被拉格朗日 对偶和 SMO 算法化解,使 SVM 趋向于完美。 另外,其他很多议题如 SVM 背后的学习理论、参数选择问题、二值分类到多值分类等 等还没有涉及到,以后有时间再学吧。其实朴素贝叶斯在分类二值分类问题时,如果使用对 数比,那么也算作线性分类器。
还剩12页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

baifengbai

贡献于2016-05-09

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf