SMO实现SVM的步骤及证明.pdf-资料库

SMO 方法的实现及证明 1．问题的阐述 SVM 是从线性可分情形下的最优分类面发展而来。基本思想可以用图 (2-16)的二维情况说明。图 2-16 线性可分情况下的最优分类线图中实心点和空心点代表两类样本，H 为分类线 H1,H2 分别为过各类中离分界线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔 (margin)。所谓最优分类线就是要求分类线不仅能将两类正确分开 (训练错误率为 0)，而且使分类间隔最大。推广到一般线性可分情形，假设分类方程为 ix n , ( ,2,1 yi ), = K i , , ωx b , 0 =+> < ，对其进行归一化，样本集 Rd x y 1,1{ } , −+∈ ∈ ωxi yi b ( , < ≥−+> 01) ，满足 (1) 构造损失函数作为目标函数及约束条件，即： minimize W : ( ) α = subject to ( xwy T i i + 2 w 2 ) b ∑+ C ξ i i i ∀−≥ ξ 1 , i i ∀≥ ,0ξ i (2-a) (2-b) (2-c) 经过拉格朗日变换以及 KKT 定理推导，式子变为： minimize : W ) ( α = subject to 0 ≤ α i ≤ ∑ i C 1 2 α i ∑ i , y = i j 0 α i − ∑ i αα j i xxyy i i j j (3) 引入核函数，最后的目标函数变为：

maximize : W ) ( α = n ∑ i 1 = α i − 1 2 n n ∑∑ i 1 = j 1 = αα j i Kyy i j ( i x,x j ) (4) subject to n ∑ i 1 = α i y i = 00 ≤ α i iC ∀≤ , 改写为矩阵相乘的格式，得到： min f α )( subject to = 1 2 αy T α T Qα − αe T = 00 ≤ α i ≤ iC , = ,...., 1 l (5) 其中 e 为全 1 向量，为所有变量的上界，为 Q l × 的半正定矩阵。训 l C 练向量通过ix φ函数被映射到更高维的空间(可能为无穷维)， KyyQ ij ≡ j i xx ,( i j ) ， K ( ( ) xφyx, = ) (yφT ) 为核函数。简言之，即通过训练样本寻找 α ，使得其中 1 2 2. 最小贯序列方法(SMO：Sequential Minimal Optimization) 最小。 Te− Qα αT α SMO 是改进的 SVM 训练算法。同其他 SVM 训练算法一样，SMO 将一个大的 QP 问题分解为一系列小的 QP 问题。与其他算法不一样的是，SMO 处理的是规模最小的 QP 问题，因此能够快速解决并获得解析解，能够有效的改善空间和时间复杂度。 SMO 的优点： 1. 即使很多拉格朗日乘子在界上，SMO 仍然能够较好地处理； 2. SMO 训练线性核 SVM 时性能优异，因为 SMO 的计算时间主要集中在 SVM 的计算上，而线性核 SVM 的计算可以表示为简单的内积，而非线性核的和； 3. SMO 能够很好地处理输入为稀疏向量的情形，因为核计算时间的减少使 SVM 训练过程加速。因为块分解法花费的时间主要在跑 QP 代码上，因此无法有效利用 SVM 的线性特性或者输入向量的稀疏性。 4. SMO 最大的优点在于能够有效处理大规模 QP 问题，因为它减小训练集规模优于块分解方法。使用最小贯序列方法（ SMO）每次仅选择两个元素共同优化，在其他参数固定的前提下，找到这两个参数的最优值，并更新相应的α向量，而这两个点乘子的优化可以获得解析解。尽管需要更多的迭代才收敛，每次迭代需要很少的操作，因此算法在整体上的速度上有数量级的提高。包括

收敛时间在内，算法其他特征没有矩阵操作，它不需要存储核矩阵，所需要的内存大小和训练数据集的大小线性增长，因此也有效降低了空间复杂度。通常来说，获得精确的最优值是不太现实的，因此需要定义近似最优条件，因此后面提及优化一词时，将代表近似最优解。实现技术主要考虑两个步骤：如何选择工作集；如何更新两个点乘子。 2.1 工作集选择因为 SMO 方法每一步选择和更新两个拉格朗日乘子，并且至少有一个拉格朗日乘子在更新前违背了 KKT 条件，因此根据 Osuna 原理每一步能够减小目标函数值。因此迭代收敛能够得到保证。为了能够快速收敛，SMO 启发式地选择两个拉格朗日乘子进行优化。 2.1.1 Platt 方法[1] 根据 KKT 条件，可以得出：其中， α i ⇔= 0 xfy ( i i 1) ≥ 0 < Cα ⇔< i xfy ( i i 1) = Cα ⇔= i xfy ( i i 1) ≤ ( xf ) = ∑ =1 l j i y xα ( j K j ⋅ x j i ) + b （6a）（6b）（6c）（7） Platt 方法通过式（6）检测 iα 是否满足 KKT 条件。它将启发式选择第一个和第二个拉格朗日乘子视为独立的过程。选择第一个乘子作为 SMO 算法的外层循环。任何违反 KKT 条件(6)的乘子（或样本）都是合法的第一个拉格朗日乘子。外层循环中分两种情况选择第一个乘子： A. 在所有乘子中选择（第 1 次或者 i ∈α ,0( C 没有违反 KKT 条件乘子的情 ) 形）； B. 在界内 i ∈α ,0( C 中选择（其它情形，这是常规情况）。 ) 外层循环分两种情况选择第一个乘子的理由：当 SMO 算法有进展时，界上的乘子（即等于 0 或者 C 的乘子）更新后很有可能仍然停留在界上，界内的乘子才发生改变，因此首先在界内乘子中选择，可以加快算法的运行时间。界上乘子更新后很有可能仍然停留在界上的解释：

上图红点表示待更新的两个乘子的对应坐标，其中 2α 在界上设核矩阵正定，根据 2 =α ，假 0 old αα 2 new 2 = + ( Ey − 1 2 η E 2 ) 0>η ,因此若 2α 更新后值发生变化，必须 ( Ey ，而在后面的工作集选 1 2 择并不能够确保该式成立，若 ( ) 0 Ey ≤ ，则 2α 的值保持不变，因此更新失 1 2 败，仍然留在界上。其他情形依次类推。 ) 0 > − E − E 2 2 总言之，外循环首先对整个训练集进行迭代，确定是否每一个实例都违背 KKT 条件。如果一个实例违背了 KKT 条件，它就作为待优化的候选乘子。遍历一次整个训练集后（最多在整个训练集寻找一次违背 KKT 条件的 2α ），外循环对所有拉格朗日乘子既非 0 也非 C(non-bound，注意 non-bound 这一约束条件而言的)的例子进行迭代，重复进行，每个例是针对 ≤α0 Ci ≤ 子检查是否满足 KKT 条件，违背该条件的实例作为优化的候选实例。外循环不断重复对这些非边界实例的遍历直到所有的实例在 ε内满足 KKT 条件。外循环返回并对整个训练集进行迭代。需要注意的事 KKT 条件是在精度ε内检查的。一般来说，ε设为。 310 − 识别系统一般不要求在较高精确度上检查 KKT 条件：例如正界输出 0.999 到 1.001 之间的数是可接受的。如果要求很高的输出精度，SMO 算法将无法快速收敛。一旦第一个乘子被选中，SMO 以最大化优化时的步长为目标来选择第二个乘子。现在计算核函数 K 需要一定的时间花销，根据

old αα 2 new 2 = + ( Ey − 1 2 η E 2 ) 其中 E i F i = = = ∑ n α j j 1 = n ∑ α j j 1 = xf )( − i xKy ( j j , x i ) − y i xKy ( j E y = i i −+ b y i j x ) , i b + 2 1E E − ，因此应选择第二个乘子最大化 1 E 1E 第二个乘子的迭代步长大致正比于 E − ，即当为正时最小化，当为负时最大化。 1 E 使用上述第二个乘子的启发式选择在一些特殊的情况，SMO 无法有正的进展（positive progress）。例如，第一个和第二个乘子指向同一个输入向量。在这种情况，SMO 对第二个乘子的启发式选择使用分层的方法指导它寻找到一个拉 2E 2E 2 格朗日乘子对能够实现正的进展，所谓正的进展通过乘子优化后两个乘子的增量非零。分层的启发式选择第二个乘子的方法描述如下，如果上述的启发式选择无法实现正的进展，SMO 开始在非边界实例中迭代，寻找能够实现正的进展的实例，如果没有非边界实例能够实现正的进展，SMO 开始在整个训练集中迭代指导寻找到能够实现正的进展的实例。为了避免 SMO 倾向于训练集中位置靠前的训练集，在非边界实例中和在整个训练集中寻找都从一个随机位置开始。在一些极其特殊的情形，没有实例能够满足要求，此时，第一个实例将被忽略，SMO 继续寻找第一个实例。的更新： Fxfb , ( i ), （1） b 的更新为使乘子 1α 或者 2α 的 KKT 条件成立。若 new 1α 在界内，则有 E1 =new 0 根据 + b new 1 − y i = 0 1 j −+ b y i j n j α j 1 = α j 1 = Ky j Ky j 1 n j = = new F 1 F old 1 ∑ ∑ 可以得到： b −= b new 1 F old 1 − y 1 ( old αα 1 new 1 − ) xxK , 1 ( 1 ) − y 2 ( old αα 2 new 2 − ( xK ) , )1 x 2 同理，若在界内，则有 new 2α b new 2 −= b F old 2 − y 1 ( old αα 1 new 1 − ) xK ( , x 1 ) 2 如果和都在界内，根据 new 1α new 2α old αα 2 new 2 = + ( old αα 2 − ) − 2 new 2 FFy 2 2 y ( ) − 1 κ = old α 2 + 2 , x ( )2 xK ( EEy − 2 2 1 κ ) 不难得出

b new 1 = b new 2 ，则有 A. 若 new 1α 和 new 2α 有一个在界内，b 取对应 new ib （i=1,2）的，如 new 1α 在界内，b 取 newb1 ； B. 若 new 1α 和 new 2α 都在界上，那么 newb1 和 newb2 之间的任意数都满足 KKT 条件，都可作为b 的更新值，一般取 newb = newb 1 newb + 2 。 2 下面给出 b new = tb new 1 + 1( − bt ) new 2 , t ∈ )1,0( 满足 KKT 条件的证明。由于两个乘子都在界上，因此经过了裁剪，令 new 2α 化简得 i. 若 new 1α λαα + = new 2 old 2 F 2 ) ( Fy − 2 1 η , λ ∈ )1,0[ (*) F new 1 F new 2 1( = t −= − 1( Ft F )( 1)( − − λ 1 2 F F ( ) − − ）λ 1 2 ) λ ∈ ),1,0[ t ∈ )1,0( new 2α= （同为 C 或者 0） 1) 2) ( Fy 1 2 0 0 new 可得 − F 2 y 2 2y ii. 若 new 1α new 2α≠ （一个为 0，另一个为 C） y = 不妨令 1 0 y 2 newFy 1 1 ,0 α new = 1 0 ，由于（*）式，所以，则，因此更新的两个乘子都满足 KKT 条的情形。 − F 2 0 C ( Fy 1 2 ) 0 > new α 2 , 2 2 , y = = new 2 new 1 newFy 1 与 newFy αααα 1 y ≠ ，同号，不可能同时满足 KKT 1 条件。根据（16-a）计算 L 和 H，可得到 L=H，因此遇到该情形时，将不会进行后面的更新。 ( )i f x 的更新 1 2 2

f ( ) ∑ = x new i = n j new α j 1 xKy ( j j , x i ) + b new （3） ( )i F x 的更新 F ( ) x new i = f ( ) x new i − y i procedure examineExample(i2) y2 = target[i2] alph2 = Lagrange multiplier for i2 F2 = SVM output on point[i2] – y2 (check in error cache) r2 = F2*y2 if ((r2 < -tol && alph2 < C) || (r2 > tol && alph2 > 0)) { if (number of non-zero & non-C alpha > 1) { i1 = result of second choice heuristic (section 2.2) if takeStep(i1,i2) return 1 } loop over all non-zero and non-C alpha, starting at a random point { i1 = identity of current alpha if takeStep(i1,i2) return 1 } loop over all possible i1, starting at a random point { i1 = loop variable if (takeStep(i1,i2) return 1

} } return 0 endprocedure main routine: numChanged = 0; examineAll = 1; while (numChanged > 0 | examineAll) { numChanged = 0; if (examineAll) loop I over all training examples numChanged += examineExample(I) else loop I over examples where alpha is not 0 & not C numChanged += examineExample(I) if (examineAll == 1) examineAll = 0 else if (numChanged == 0) examineAll = 1 } 该工作集选择方法存在一些不足，导致算法效率较低。因为它计算和使用一个单一阈值(b)的方式，可能会带来一些不必要的低效。在任何情况，SMO 根据两个已经优化的乘子来修改 b。但是，当算法检查剩下的实例是否违背 KKT 条件时，很有可能存在一个不同的 b 值能够工作得更好。 b ≥ up 所以在 SMO 算法中，很有可能存在这种情况，尽管α已经迭代得到了一个满的值，SMO 却因为当前的 b 值不合适而无法检测到该情况。在足这种情况下，SMO 为了进行更新步骤不得不付出大量且不必要的资源以搜索第二个乘子。 2.1.2 Keerthi 方法[2] b low

资料库

SMO实现SVM的步骤及证明.pdf

相关推荐

后端

热门标签

最新资料