一种快速的svm训练算法—smo-人脸识别算法

《一种快速的svm训练算法—smo-人脸识别算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人脸识别算法一种快速的SVM训练算法—SMO摘要本文提出一种训练SVM的新算法:序贯最小优化，或SMO。训练一个SVM需要解一个非常大的二次规划(QP)优化问题。SMO把这个大QP问题分解为一系列尽可能最小的QP问题。解析地解出这些小QP问题，这样就能避免把耗时多(time-consuming)的数值QP优化过程用作内循环。SMO需要的内存容量与训练集大小成线性关系，这就使得SMO可以处理非常大的训练集。由于避免了矩阵计算，对多种测试问题，SMO的尺度(scales，复杂度,)与训练集大小的关系处于线性

2、和二次方之间，而标准chunkingSVM算法尺度与训练集大小的关系处于线性和三次方之间。SMO的计算时间受控于SVM的评价，因此对线性SVMs和稀疏数据集来说SMO是最快的。在现实稀疏数据集上，SMO可以比chunking算法快1000倍以上。1.简介最近几年，涌现了一股SVMs的热潮。根据经验，SVMs在各种问题上显示出拥有好的泛化(generalization)性能，这些问题诸如手写字符识别、人脸检测、行人检测和文档分类。但是，SVM的使用仍然限于一小群研究者。一种可能的原因是SVMs训练算法很慢

3、，对大问题尤其如此。另一种解释是SVM训练算法对一个平均水平的工程师来说，其实现是复杂的、微妙的和困难的。本文描述了一种新的概念上简单的SVM学习算法，易于实现，并且相对标准SVM训练算法来说，前者更快，在解决困难的SVM问题上具有更好的尺度属性。新的SVM学习算法成为序贯最小优化(SMO)。之前的SVM学习算法将数值二次规划(quadraticprogramming，QP)作为一个内循环，替代地，SMO利用一个解析QP的步骤。本文首次提供了SVMs的概述，并且回顾了当前的SVM训练算法。然后SMO算法

4、详细陈述，包括:解析QP步骤的解法，启发式的选择在内循环需要优化的变量，描述如何设置SVM阈值，对特殊情况的优化，算法的伪代码，以及SMO与其它算法的关系等。SMO已经在两个现实的数据集和两个人工数据集上测试。基于这些数据集，本文给出SMO对比标准chunking算法的计时结果，并且基于这些计时给出结论。最后，附录描述了解析优化的推导过程。1.1SVMs概述VladimirVapnik在1979年发明了SVMs。最简单的线性形式的SVM，就是一个超平面，该超平面以最大间隔(如图1)把正样本集和负样本集分

5、开。在线性的情况下，间隔(margin)被定义为超平面到最近的正负样本的距离。输出一个线性SVM的方程为u,w,x,b，(1)x其中是超平面的法向量(normalvector)，是输入向量。分类超平面是平面u,0。设离w超平面最近的点位于平面u,,1上。因此间隔为m1。(2)m,2w图1一个线性SVM最大化间隔可以表示为以下的优化问题:12(3)minws.t.y(w,x,b),1,,i,iiwb.2其中，(subjectto)是使得的意思，是第个训练样本，而是对应第个训练样本的iis.t.xyiiSV

6、M正确输出。对应正样本的值是+1，对应负样本的值是-1。yi利用拉格朗日方法，这个优化问题可以转换成它的对偶形式—一是一个二次规划(QP),问题，该QP问题的目标函数仅取决于一系列拉格朗日乘子，,iNNN1min,(α),minyy(x,x,),,,,,,，ijijijiαα2iji,,11,1(4)(其中N是训练样本的数量)，使得满足以下约束不等式，，(5),,0,,ii以及一个约束线性等式，N。(6)y,,0,iii,1即,,0,,iiNNN1N,,,min,(),minyy(,),s.t.αxx,

7、,,ijijijiααy,,02i,,11ji,1,iii,1在每个拉格朗日乘子和每个训练样本之间有一个一对一的关系。一旦拉格朗日乘子确定下来，法向量和阈值(threshold)就可以从拉格朗日乘子推导出来:bwN。(7)w,y,x,b,w,x,y对某些,,0,iiikkki,1由于可以通过等式(7)从使用之前的训练样本计算出来，因此用于估计一个线性SVM所需w要的计算量，对非零支持向量的数量而言是固定的。当然，并非所有的数据集都是线性可分的。这样就不存在可以分开正样本和负样本的超平面了。在上面的方程式

8、中，不可分的情况将导致一个无穷解。但是在1995年，Cortes和Vapnik提出对原有优化表达式(3)进行修正，这样做，允许但惩罚了一个样本不能到达正确间隔的行为。该修正是:N12(8)minw，C,s.t.y(w,x,b),1,,,,i,,iiii.wb2,1i其中是松弛变量，其允许间隔失效;是惩罚因子，其利用宽间隔换取少量的间隔失效。C,i当这个新的优化问题被转换到对偶形式时，约束(5)发生了简单的改变，变为区间约束:。(9)0,,,