一种训练支撑向量机的改进贯序最小优化算法

《一种训练支撑向量机的改进贯序最小优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1000-9825/2002/13(10)2007-07©2002JournalofSoftware软件学报Vol.13,No.10一种训练支撑向量机的改进贯序最小优化算法Ã孙剑,郑南宁,张志华(西安交通大学人工智能与机器人研究所,陕西西安710049)E-mail:sj@aiar.xjtu.edu.cn;nnzheng@xjtu.edu.cnhttp://www.aiar.xjtu.edu.cn摘要:对于大规模问题,分解方法是训练支撑向量机主要的一类方法.在很多分类问题中,有相当比例的支撑向量对应的拉格朗日乘子达到惩罚上界,而且在训练过程中

2、到达上界的拉格朗日乘子变化平稳.利用这一统计特性,提出了一种有效的缓存策略来加速这类分解方法,并将其具体应用于Platt的贯序最小优化(sequentialminimizationoptimization,简称SMO)算法中.实验结果表明,改进后的SMO算法的速度是原有算法训练的2~3倍.关键词:支撑向量机;模式分类;二次规划;缓存策略;贯序最小优化算法中图法分类号:TP181文献标识码:A支撑向量机(supportvectormachine,简称SVM)源于线性可分问题的最优分类超平面,即以最大间隔将数据分开.对于线性不可分问题,通过选择某

3、种非线性映射,将输入空间映射到一个维数更高的特征空间,在这个空[1,2]间构造最优分类超平面.SVM是基于统计学习理论中的结构风险最小(structureriskminimization,简称SRM)归纳原理,能有效地避免经典学习方法中过学习、维数灾难、局部极小等非常棘手的问题,在小样本条件下仍然具有良好的范化能力.有关SVM的详细论述可以参阅文献[3].SVM在解决分类、回归和密度函数估计等机器学习问题方面获得了非常好的结果,并且已经应用于手写体字符识别、人脸检测、文本、语音分类等实际问题.但是,训练时间长仍是SVM目前的一大缺点.对于大规

4、模问题(样本大于104),目前的SVM训练算法速度都比较慢,尤其对于M类问题,最少需要训练M−1个分类器(按一对多方式),增加新类别时,又需要全部重新训练.所以,在SVM的研究中,如何提高训练速度,减少训练时间,建立实用的学习算法,仍是一个亟待解决的问题.d给定训练样本{(xi,yi)

5、i=1,…,N;xi∈R,yi∈{−1,+1}},SVM实现下面的决策函数:Nf(x)=sign∑yiαik(xi,x)−b,(1)i=1其中α是每个样本对应的拉格朗日乘子,b是阈值.i首先通过选择满足Mercer条件的核函数k(x,y),确定

6、输入空间到特征空间的某种映射φ(x),k(x,x)等于ij该映射φ(x)构成的特征空间上的内积,即k(x,x)=(φ(x)⋅φ(x)),这样甚至不需要知道映射φ(x)的具体形式,也ijij能在输入空间简单地计算特征空间上的内积,有关核空间的理论可以参阅文献[2].训练一个SVM相当于解一个凸二次规划(quadraticprogramming,简称QP)问题:NN1maxLD=∑αi−∑αiQ(i,j)αj,(2)α2i=1i=1,j=1Ã收稿日期:2000-12-07;修改日期:2001-11-05基金项目:国家自然科学基金资助项目(6017

7、5006;60024301);国家创新研究群体科学基金项目(60024301)作者简介:孙剑(1976－),男,山东单县人,博士生,主要研究领域为计算机视觉,机器学习;郑南宁(1952－),男,江苏南京人,博士,教授,博士生导师,中国科学院院士,主要研究领域为模式识别与智能系统;张志华(1971－),男,湖北阳新人,博士生,主要研究领域为模式识别与智能系统.2008JournalofSoftware软件学报2002,13(10)N其中Q(i,j)=yiyjk(xi,xj),0≤αi≤C,∑αiyi=0.Q为N×N矩阵,)k(xi,xj是核函数

8、.i=1对于小规模的QP问题,经典最优化算法,如牛顿法、拟牛顿法等都可以较好地求解,但当训练集很大,特别是支撑向量数目也很大时,多数算法需要的内存与Q矩阵的大小成比例.例如,假设Q矩阵的元素用四字节的浮点数表示,N=20000,需要1.5GBytes内存,N=50000,需要9.5TBytes内存,解QP问题的经典方法不再可行.分解算法(将大的QP问题分解成一系列小的QP子问题进行迭代求解)是目前有效解决大规模问题的主要方法.[4]Chunking算法是首先被提出来的一种分解算法:从训练样本中任意选择一个小的子集,求解这个子集的最优,保留这个

9、子集的支撑向量,在剩余的样本中启发式地加入若干样本构成新的子集,再求解新子集的最优,[5]反复迭代直至收敛.但当问题的支撑向量数也很大时,子问题的求解也很困难.Os