支持向量机的算法研究极其发展

《支持向量机的算法研究极其发展》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、支持向量机的算法研究及其发展赛燕燕（中国海洋大学信息科学与工程学院电子系，青岛264005）摘要:支持向量机是在统计学习理论基础上发展起来的一种新的机器学习方法，同时也是到目前为止统计学习理论最成功的实现。支持向量机在模式识别、冋归佔计、函数逼近等领域有了广泛的应用。论述了支持向量机的研究、发展状况，指出了支持向量机研究和发展中待解决的一些问题和今后进一步的研究方向。关键词:支持向量机;优化算法;训练;发展一、引言支持向量机SVM（SupportVectorMachine）是在统计学习理论基础匕发展起來的一种新的机器学习方法。支持向量

2、机乂称为支持向量网络，具有理论完备、适应性强、全局优化、训练时间短、泛化性能好等优点，已经成为目前国际、国内研究的热点。支持向量机的核心内容从1992年才开始提出，是到口前为止统计学习理论最成功的实现，目前仍处于不断发展阶段。据统计,1999年以前国际上公开发表的冇关统计学习理论的文章不足50篇，但1999年以后这方面的文章有数千篇之多，其应用范围和成果不断扩大。近年来专门或相关的国际、国内会议也都列有统计学习理论和支持InJ量机的专题。本文将在对支持向量机分类机理分析的革础上,对支持向量机冃前的研究、应用作一综述，授后指出对支持向量

3、机进一步研究和应用亟待解决的一•些重要问题。二、SVM的算法研究对SVM本身性质的研究是SVM的一个重要研究内容。木文以下就SVM的训练算法、分类算法、多类算法、核函数及选择等热点问题分别加以讨论。2.1SVM训练算法传统的利用标准二次型优化技术解决对偶问题的方法，是SVM训练算法慢及受到训练样本集规模制约的主要原因。目前已提出了许多解决方法和改进算法，主要是从如何处理人规模样木集的训练问题、提高训练算法收敛速度等方面改进。以下分为分解方法、修改优化问题法、增屋学习法、几何方法等分别讨论。2.1.1分解方法分解方法是SVM训练一般采用

4、的途径。块算法、固定工作变量集方法、顺序最小优化方法等最为常见。考虑到去掉Lagrange乘子等于零的训练样本不会影响原问题的解，块算法的出发点就是在迭代过程屮按照某种准则逐步排除非支持向量。当支持向量数目远小于训练样本数目时，块算法的效率较高。固定工作变量集方法思想是在迭代过程中，当前求解了问题的优化变屋数冃不变,即参与训练的样木集（T作变最集）规模固定。工作样本集大小固定在算法速度可以容忍的限度内，迭代过程选择一种合适的换入换出策略，将剩余样木屮的一部分与工作样本集小的样本进行等量交换。Osuna针对SVM训练速度慢及吋间空间复杂

5、度大的问题，最早提出了该分解算法，并用于了人脸检测。工作样本集大小的确定、如何确定工作样本集、如何确定合适的迭代策略是固定工作样本集方法的主要问题。SVMlight[l]中做了以下改进：在工作样木集的选择上,SVMlight中是沿着最速下降可行方向d,由非零元素对应的q个优化变量构成工作样木集。已经证明了只要最速下降可行方向d存在,则用相应子集构成的子问题可以进一步优化，而子问题的町行解也是原问题的可行解。这就解决了工作样本集不能包括所有支持向量的问题。顺序最小优化方法SMO[2]可以说是Osuna分解算法的极端特例,英工作样木集中只

6、有两个样本。它把二次型寻优算法简化为线性寻优问题oSMO特别适合稀疏样木。具工作集的选择采用启发式，而不是传统的最陡下降法。算法主要耗时是在蚁优条件的判断上。2.1.1修改优化问题法通过修改冃标函数、约束条件来简化优化问题木身,是提高SVM算法效率的途径之0由SVM原理可知，对于错分样本,SVM的惩罚项是对松弛因子的累加，但这种累加不必一定是线性的。因此，最近点算法的基本思想是将SVM原问题的惩罚项由线性累加C工ni=lgi改为二次累加CXni=1i2。通过这样修改，可以将CU作为w的一个分量，同时将样木维数增加一维并规定新的一维为常

7、数yi/C,改写后的目标两数屮将不再包含惩罚项，而约束条件中也没有了松弛因了，从而使问题转化为无错分情况下求最大边际的问题。连续超松弛方法［3］通过在原目标函数中加一项b2,从而使其对偶问题第3期王晓丹等:支持向量机研究与应用51多出一项(Sni=la2i)/2，而约束条件则少了一项等式约束。修改后的对偶问题变为边界约束条件下的二次规划问题，适合迭代求解。同时应用矩阵分解技术,每次只更新Lagrange乘子的一个分量，从而不需将所有样木放入内存，人人提高了收敛速度。最小二乘支持向量机将最小二乘引入到SVM中，其目标函数为minw,b,

8、eJLS(w,b,e)=12wTW+Y12Sni=lei,纟勺束条件为:yi［wT<(xi)+bJ=1-ei,i=1,2,n。定义和应的Lagrange函数,并运用KT最优条件，可得到一组线性方程。通过解线性方程组可得到