一种快速的SVM训练算法—SMO-人脸识别算法.docx

人脸识别算法一种快速的SVM训练算法SMO 摘要 本文提出一种训练SVM的新算法:序贯最小优化，或SMO。训练一个SVM需要解一个非常大的二次规划(QP)优化问题。SMO把这个大QP问题分解为一系列尽可能最小的QP问题。 解析地解出这些小QP问题，这样就能避免把耗时多(time-consuming)的数值QP优化过程用作内循环。SMO需要的内存容量与训练集大小成线性关系，这就使得SMO可以处理非常大的训练集。由于避免了矩阵计算，对多种测试问题，SMO的尺度(scales，复杂度,)与训练集大小的关系处于线性和二次方之间，而标准chunking SVM算法尺度与训练集大小的关系处于线性和三次方之间。SMO的计算时间受控于SVM的评价，因此对线性SVMs和稀疏数据集来说SMO是最快的。在现实稀疏数据集上，SMO可以比chunking算法快1000倍以上。 1. 简介 最近几年，涌现了一股SVMs的热潮。根据经验，SVMs在各种问题上显示出拥有好的泛化(generalization)性能，这些问题诸如手写字符识别、人脸检测、行人检测和文档分类。 但是，SVM的使用仍然限于一小群研究者。一种可能的原因是SVMs训练算法很慢，对大问题尤其如此。另一种解释是SVM训练算法对一个平均水平的工程师来说，其实现是复杂的、微妙的和困难的。 本文描述了一种新的概念上简单的SVM学习算法，易于实现，并且相对标准SVM训练算法来说，前者更快，在解决困难的SVM问题上具有更好的尺度属性。新的SVM学习算法成为序贯最小优化(SMO)。之前的SVM学习算法将数值二次规划(quadratic programming，QP)作为一个内循环，替代地，SMO利用一个解析QP的步骤。 本文首次提供了SVMs的概述，并且回顾了当前的SVM训练算法。然后SMO算法详细陈述，包括:解析QP步骤的解法，启发式的选择在内循环需要优化的变量，描述如何设置SVM阈值，对特殊情况的优化，算法的伪代码，以及SMO与其它算法的关系等。 SMO已经在两个现实的数据集和两个人工数据集上测试。基于这些数据集，本文给出SMO对比标准chunking算法的计时结果，并且基于这些计时给出结论。最后，附录描述了解析优化的推导过程。 1.1 SVMs概述 Vladimir Vapnik在1979年发明了SVMs。最简单的线性形式的SVM，就是一个超平面，该超平面以最大间隔(如图1)把正样本集和负样本集分开。在线性的情况下，间隔(margin)被定义为超平面到最近的正负样本的距离。输出一个线性SVM的方程为 u,w,x,b， (1) x其中是超平面的法向量(normal vector)，是输入向量。分类超平面是平面u,0。设离w超平面最近的点位于平面u,1上。因此间隔为 m1 。 (2) m,2w图1 一个线性SVM 最大化间隔可以表示为以下的优化问题: 12 (3) minws.t.y(w,x,b),1,i,iiwb.2其中，(subject to)是使得的意思，是第个训练样本，而是对应第个训练样本的iis.t.xyiiSVM正确输出。对应正样本的值是+1，对应负样本的值是-1。 yi利用拉格朗日方法，这个优化问题可以转换成它的对偶形式一是一个二次规划(QP),问题，该QP问题的目标函数仅取决于一系列拉格朗日乘子， ,iNNN1min,(),minyy(x,x,), ， ijijiji2iji,11,1(4) (其中N是训练样本的数量)，使得满足以下约束不等式， ， (5) ,0,ii以及一个约束线性等式， N。 (6) y,0,iii,1即 ,0,iiNNN1N, min,(),minyy(,),s.t.xx,ijijijiy,02i,11ji,1,iii,1在每个拉格朗日乘子和每个训练样本之间有一个一对一的关系。一旦拉格朗日乘子确定下来，法向量和阈值(threshold)就可以从拉格朗日乘子推导出来: bwN。 (7) w,y,x,b,w,x,y对某些,0,iiikkki,1由于可以通过等式(7)从使用之前的训练样本计算出来，因此用于估计一个线性SVM所需w要的计算量，对非零支持向量的数量而言是固定的。 当然，并非所有的数据集都是线性可分的。这样就不存在可以分开正样本和负样本的超平面了。在上面的方程式中，不可分的情况将导致一个无穷解。但是在1995年，Cortes和Vapnik提出对原有优化表达式(3)进行修正，这样做，允许但惩罚了一个样本不能到达正确间隔的行为。该修正是: N12 (8) minw，C,s.t.y(w,x,b),1,i,iiii.wb2,1i其中是松弛变量，其允许间隔失效;是惩罚因子，其利用宽间隔换取少量的间隔失效。C,i当这个新的优化问题被转换到对偶形式时，约束(5)发生了简单的改变，变为区间约束: 。 (9) 0,C,ii变量则完全没有出现在对偶方程式中。 ,iSVMs甚至可以一般化为非线性分类器。一个非线性SVM的输出由拉格朗日乘子明确计算得到: Nu,yK(x,x),b, ， (10) ,jjj,1jxKx其中是一个核函数，它由于度量输入向量与存储的训练向量之间的相似性或距离。jKK的例子包括高斯型、多项式型和神经网络非线性型。如果是线性的，则方程(10)就还原到线性SVM方程(1)的样子。 拉格朗日乘子仍然通过一个二次规划过程来计算。非线性改变了二次形式，但对偶,i,目标函数对仍然是二次的: ,NNN1,xxmin,(),minyyK(,),ijijiji2i,11ji,1s.t. (11) ,0,C,iiNy,0,iii,1上述等式(11)中的二次规划(QP)问题，就是SMO算法要解决的QP问题。为了使得上述QP问题是正定的(positive definite)，核函数K必须满足Mercer条件4。 KKT条件对一个正定QP问题的一个优化点来说，是充要条件。QP问题(11)的KKT条件特别简单。QP问题可解，当对所有满足: i,0,yu,1iii,0,C,yu,1 ， (12) iii,C,yu,1iii其中是SVM对第个训练样本的输出。注意到KKT条件可以在一个样本上评估一次，这iui样就有利于构造SMO算法。 1.2 以往训练SVMs的方法 由于太大，来自SVMs的QP问题(11)无法轻易利用标准QP技术解决。方程(11)中的二次形式涉及一个矩阵，该矩阵拥有的元素数量等于训练样本数量的平方。如果训练样本数量超过4000，则矩阵占据内存的容量将超过128MB。 Vapnik19描述了一种解决SVM QP的方法，它就是已知的chunking算法。chunking算法利用了以下事实，即如果你把矩阵中对应于零值拉格朗日乘子的行和列去掉，二次形式的值也保持不变。因此，大QP问题可以分解成一系列较小的QP问题，其最终目的是识别出所有的非零拉格朗日乘子，并抛弃所有的零值拉格朗日乘子。在每一步，chunking算法解一个QP问题，该问题由以下样本组成:来自上一步的每个拉格朗日乘子，以及违反KKT条件(12)4的M个最差样本，M是某个固定值(见图2)。如果在某一步中违反KKT条件的样本数小于M，则所有违反的样本都要加入到下一步。每一个QP子问题的初始化都利用了前一步子问题的结果。在最后一步，全部的非零拉格朗日乘子都识别出来了，因此最后一步解一个大的QP问题。 chunking算法大大减小了矩阵的大小。但是，chunking算法仍然难以处理大数量训练问题，因为即使矩阵减小了，内存还是容不下这么多。 在1997年，Osuna等人16证明了一个理论，该理论提出一套全新的SVMs QP算法。该理论证明了大QP问题可以分解为一系列较小QP问题。只要至少有一个违反KKT条件的样本加入到前一个子问题的样本，则每一步将减少全部目标函数，并获得一个满足所有约束的稳定点。因此，一序列总是加入至少一个违反样本的QP子问题，可以保证收敛。注意到chunking算法满足该理论的条件，因此也是收敛的。 Osuna等人提出对每个QP子问题保持一个固定大小的矩阵，这表明需要在每一步加入和删除同等数量的样本16。使用一个固定大小的矩阵将允许训练任意大小的数据集。Osuna的论文16给出的算法建议，每一步加入一个样本并且减去一个样本。显然这样做效率低，因为它将利用一整个数值QP优化步骤，以产生一个满足KKT条件的样本。实际操作时，研究员们根据unpublished试探的方式17加入和去除多个样本。无论如何(In any event)，对所有这些方法来说，一个数值QP解法是需要的。数值QP总是不好搞定，并且有很多数值精度问题需要处理。 图2. 三个训练SVMs的可选方法:Chunking，Osuna的算法，以及SMO。对每一种方法，图示出3步。每一步中的水平细线表示训练集，而那些较厚的条块表示这一步中将要优化的拉格朗日乘子。对Chunking而言，每一步都加入定量的样本，并抛弃每一步的零值拉格朗日乘子。因此，每一步训练的样本数量趋于增加。对Osuna的算法而言，每一步都优化定量的样本:即在每一步问题加入和抛弃同等数量的样本。对SMO而言，每一步仅解析地优化两个样本，所以每一步都非常快。 2. 序贯最小优化 SMO是一种可以快速解SVM QP问题的简单算法，它不需要存储任何额外的矩阵，也完全不需要用到数值QP优化步骤。SMO将整个QP问题分解为若干QP子问题，利用Osuna的理论确保算法收敛。 与之前的方法不同，SMO选择在每一步解尽可能小的优化问题。对标准SVM QP问题，最小的优化问题包含两个拉格朗日乘子，因为拉格朗日乘子必须满足一个线性等式约束。在每一步，SMO选择两个拉格朗日乘子一起优化，给这些乘子找到优化值，并更新SVM以反映(reflect 翻译不一定准)新的优化值(见图2)。 SMO的进步源于以下事实，即解两个拉格朗日乘子可以解析地完成。因此可以完全避免数值QP优化。SMO算法的内循环可用少量C代码表示出来，而不是调用一整个QP程序库的例程。即使在算法过程中解更多的优化子问题，由于每个子问题解得很快，整个QP问题解得也快。 另外，SMO完全不用存储额外的矩阵。因此，即使非常大的SVM训练问题也可以放到个人电脑或工作站的内存里。因为SMO不用矩阵算法，所以它不易受到数值精度的影响。 总之，SMO有两部分:对两个拉格朗日乘子的解析解法，以及启发式地选择需要优化的乘子。 2.1 两个拉格朗日乘子的解法 图3. 两个拉格朗日乘子必须满足完整问题(full problem)的所有约束条件。不等式约束条件导致拉格朗日乘子落在方框里面。而线性等式约束导致他们落在一条斜线上。因此，SMO的一步必须在斜线段上找到目标函数的最优点。 为了解两个拉格朗日乘子，SMO首先计算这些乘子上的约束条件，然后解出约束极小值。为方便起见，所有涉及第一个乘子的变量将赋予下标1，而所有涉及第二个乘子的变量将赋予下标2。因为只有两个乘子，约束条件可以轻易以二维方式图示出来(见图3)。边界约束条件(9)导致拉格朗日乘子落在方框里，而线性等式约束(6)导致拉格朗日乘子落在一条斜线上。因此，目标函数的约束极小值必然落在一条斜线段上(如图3所示)。这个约束解释了可以优化的拉格朗日乘子的最小数目是两个:如果SMO只优化了一个乘子，它并不能在每一步都满足线性等式约束条件。 斜线段的两端可以很简单地表示。为不失一般性，算法首先计算第二个拉格朗日乘子，并根据计算斜线段的两端。如果类标(类别标号,target=label)不等于，则以,yy2212下边界(13)用于: ,2， 。 (13) L,max(0,)H,min(C,C，,)2121如果等于，则以下边界(14)用于: yy,122， 。 (14) L,max(0,，,C)H,min(C,，,)2121目标函数沿斜线的二阶导数可以表达为: 。 (15) ,K(x,x)，K(x,x),2K(x,x)112212, 在通常情况下，目标函数将是正定的，沿线性等式约束条件方向将有一个极小值，且将大于0。在这种情况下，SMO沿约束条件方向计算极小值: y(E,E)new212, ， (16) ,，22,其中是第个训练样本的误差值。接下来，约束极小值将在以下范围查找，iE,u,yiii即剪掉(clipping)斜线端点以外的非约束剩下的部分: new,Hif,H2,new,clippednewnew,ifL,H 。 (17) ,222new,Lif,H2,现在令。的值从新的、剪切的(clipped)计算得到: s,yy,1221newnew,clipped 。 (18) ,，s(,)1122在非常情况下，,将不是正的。如果核函数K不满足Mercer条件，则会出现负的,，从x而导致目标函数无定义。如果多于一个训练样本具有相同的输入向量，则会出现零值的,。无论如何，即使当,非正，SMO也会工作，这种情况下目标函数,应该评估斜线段的每一端: ,f,y(E，b),K(x,x),sK(x,x)111111212,f,y(E，b),sK(x,x),K(x,x)222112222,L,，s(,L)112H,，s(,H), 1121122,Lf，Lf，LK(x,x)，LK(x,x)，sLLK(x,x)L11211122112221122,Hf，Hf，HK(x,x)，HK(x,x)，sHHK(x,x)H1121112211222(19) SMO将把拉格朗日乘子移动至末点，该末点具有目标函数最小值。如果目标函数在两端都相同(指相差一个很小的误差)，且核函数服从Mercer条件，则联合最小化将不能进,行。这种情况在下文描述。 2.2 选择需要优化的乘子的启发式方法(heuristics) 只要在每一步(every step)，SMO总是优化和改变两个拉格朗日乘子，且至少有一个乘子在前一步(before the step)违反了KKT条件，则根据Osuna的理论16，每一步都会减小目标函数。从而保证了算法收敛。为了加速收敛，SMO利用启发式方法选择联合优化的两个乘子。 分别有两种可选的启发式方法:一种用于第一个拉格朗日乘子，另一种用于第二个拉格朗日乘子。第一种启发式方法提供SMO算法的外循环。外循环首先循环遍历整个训练集，确定每一个样本是否违反KKT条件(12)。如果一个样本违反了KKT条件，那么它就是需要优化的对象(be eligible for optimization)。遍历完整个训练集之后，外循环遍历所有的非边界样本(the non-bound examples)，这些非边界样本的拉格朗日乘子不等于0或C。同样，每个非边界样本都要检查是否违反KKT条件，如果违反了，它就是需要优化的对象。外循环不断重复进行，并且逐渐忽略(pass over)非边界样本，直到所有非边界样本都以误差满足,KKT条件为止。然后，外循环返回再循环遍历整个训练集。这时外循环交替地做两件事:一是对整个训练集按单个(single)样本进行忽略处理，二是对非边界样本子集按一次多个(multiple)样本进行忽略处理，直到整个训练集都以误差满足KKT条件，于是SMO算,法终止。 这第一种启发式方法把CPU的计算时间集中在那些最有可能违反KKT条件的样本身上:即非边界样本子集。在SMO算法运行时，那些原来就在边界上的样本很可能继续待在边界上，而那些非边界样本将随着其它样本的优化而移动。因此SMO算法将循环遍历非边界子集，直到该子集自一致(self-consistent，不懂其具体含义)，然后SMO将扫描整个数据集，以查找由于非边界子集优化过程，而变得违反KKT条件的那些边界样本。 注意，这里检查KKT条件只要求满足在一定误差以内(即无需完全精确)。典型地，,310设为。典型的识别系统不需要高精度满足KKT条件:样本在正间隔(positive margin)上有0.999到1.001之间的输出是可以接受的。如果要求产生非常高输出精度，SMO算法(以及其他SVM算法)将不会快速收敛。 一旦选出第一个拉格朗日乘子，SMO就会选择第二个，以最大化联合优化过程中调用K的步骤的大小(the size of the step)。现在，核函数的评估过程是耗时较多的，因此SMO以方程(16)中分子的绝对值E,E来粗略估计步骤的大小。SMO对训练集中的每一个非12E边界样本保存了一个初始误差值(cached error value)，然后选择一个误差来尽量最大化步骤的大小。如果是正的，SMO选择一个具有最小误差的样本。如果是负的，SMOEEE211选择一个具有最大误差的样本。 E2在非常情况下(under unusual circumstances)，SMO利用上述的第二种启发方法不能取得积极进展(positive progress)。例如，如果第一和第二训练样本共享同一个输入向量，则不x能取得积极进展，同时将导致目标函数变为半定(semi-definite)。在这种情况下，SMO利用第二种启发方法的一层(hierarchy，难道是把第二种启发方法用于一层内循环,)，直到SMO找到一对可以取得积极进展的拉格朗日乘子。积极进展可以确定为，在两个拉格朗日乘子的联合优化之上，取得一个非零步骤大小。第二种启发方法的一层由以下步骤组成。如果上述启发方法不能取得积极进展，则SMO开始循环遍历非边界样本集，查找第二个可以取得积极进展的样本。如果没有一个非边界样本可以取得积极进展，则SMO开始循环遍历整个训练集，直到一个样本可以取得积极进展。对非边界样本集和整个训练集的循环遍历，都设置从随机位置开始，以免偏爱倾向训练集开始的那些样本。在极端退化的情况下，适合作为第二个取得积极进展的样本不存在。若此事真的发生，则跳过第一样本，且SMO继续选择另一个第一样本。 2.3 计算阈值 每一步之后阈值都重新计算，因此两个优化样本同时满足KKT条件。以下的是有bb1效的，仅当新的不在边界上，因为当输入为时它强迫SVM的输出为: ,xy111newnew,clipped(20) b,E，y(,)K(x,x)，y(,)K(x,x)，b111111122212以下的是有效的，仅当新的不在边界上，因为当输入为时它强迫SVM的输出为b,x222: y2newnew,clipped(21) b,E，y(,)K(x,x)，y(,)K(x,x)，b221111222222当和同时有效，它们就相等。当两个新的拉格朗日乘子都在边界上，且L不等于H时，bb12和之间的区间都是满足KKT条件的。SMO选择和之间的一半作为阈值。 bbbb12122.4 线性SVMs的优化 为了计算线性SVM，只需要存储一个权向量，而不是存储所有对应于非零拉格朗日w乘子的训练样本。如果联合优化成功了，存储的权向量需要更新，以反映新的拉格朗日乘子的值。权向量的更新很容易，由于SVM的线性: newnewnew,clipped (22) w,w，y(,)x，y(,)x111122222.5 代码细节 整个SMO算法的伪代码描述如下: target = desired output vector / target是样本类标的数组，正样本的类标是+1，负样本的类标是-1 / 每个输入样本都有一个已知类标，target数组的长度等于训练样本数量 point = training point matrix / 训练数据点组成的矩阵，每个点是个向量 procedure takeStep(i1,i2) / 函数声明，i1和i2是输入样本数据点的索引号 / 该函数的作用是获得一对优化的拉格朗日乘子 if (i1 = i2) return 0 / 不得两次输入同一个样本 alph1 = Lagrange multiplier for i1 / ，第一样本的乘子 ,1y1 = targeti1 / 索引第一样本的类标 E1 = SVM output on pointi1 y1 (check in error cache) / ，是输入第一样本后SVM产生的输出 E,u,yu1111s = y1*y2 / 注意y2 = targeti2 Compute L, H via equations (13) and (14) / 按照方程(13)(14)计算L和H，计算前首先判断y1和y2是否相等 if (L = H) return 0 k11 = kernel(pointi1,pointi1) / 计算 K(x,x)11k12 = kernel(pointi1,pointi2) / 计算 K(x,x)12k22 = kernel(pointi2,pointi2) / 计算 K(x,x)22eta = k11+k22-2*k12 / 计算, ,0 if (eta 0) / 是一般情况 a2 = alph2 + y2*(E1-E2)/eta new / a2就是，见方程(16) ,2if (a2 H) a2 = H new,clipped / 以上两条语句对应方程(17)，计算 ,2 ,0 Else / 是非常情况，under unusual circumstances，见方程(19) Lobj = objective function at a2=L Hobj = objective function at a2=H / Lobj和Hobj分别是方程(19)中的和 ,HLif (Lobj Hobj+eps) a2 = H else a2 = alph2 if (|a2-alph2| eps*(a2+alph2+eps) return 0 a1 = alph1+s*(alph2-a2) / 对应方程(18) Update threshold to reflect change in Lagrange multipliers / 更新阈值，见2.3节 bUpdate weight vector to reflect change in a1 & a2, if SVM is linear / 更新权向量，见2.4节 Update error cache using new Lagrange multipliers / 见2.2节第4段的初始误差值，用新的乘子更新 EEStore a1 in the alpha array Store a2 in the alpha array / alpha array就是存储优化的拉格朗日乘子的数组 return 1 / return 1 说明优化成功 endprocedure / 函数takeStep( , )声明完毕 procedure examineExample(i2) / 对应2.2节最后一段，查找取得积极进展的第二样本 y2 = targeti2 alph2 = Lagrange multiplier for i2 E2 = SV