资源描述：
《回归型支持向量机的简化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1000-9825/2002/13(06)1169-04©2002JournalofSoftware软件学报Vol.13,No.6回归型支持向量机的简化算法Ã田盛丰,黄厚宽(北方交通大学计算机与信息技术学院,北京100044)E-mail:sftian@center.njtu.edu.cnhttp://www.njtu.edu.cn摘要:针对支持向量机应用于函数估计时支持向量过多所引起的计算复杂性,提出一种简化算法,可以大幅度地减少支持向量的数量,从而简化其应用.采用简化算法还可以将最小平方支持向量机算法和串行最小化算法
2、结合起来,达到学习效率高且生成的支持向量少的效果.关键词:支持向量机;回归;机器学习;计算复杂性;算法中图法分类号:TP181文献标识码:A[1]自从Vapnik等人引入支持向量机(SVM)理论以来,支持向量机在模式识别和函数估计方面取得了越来越多的应用.支持向量机是在统计学习理论的基础上形成的,力图实现结构风险的最小化,从而提高了学习机的泛化能力.与人工神经网络的方法相比,由于支持向量机没有局部最优问题,并且提高了泛化能力,因此有较大的优越性.但是,人工神经网络的复杂度是由神经元的个数决定的,而支持向量机的复杂度是由具
3、有非零权值的样本即支持向量的个数决定的,对于大规模样本数据的情况而言,支持向量机的计算量是比较大的,因此限制了它的应用.为了简化支持向量机,降低其计算复杂度,已有了一些研究成果.比如,Burges提出根据给定的支持向量机生[2]成缩减的样本集,从而在给定的精度下简化支持向量机,但生成缩减样本集的过程也是一个优化过程,计算比[3]较复杂;Schölkopf等人在目标函数中增加了参数ν以控制支持向量的数目,称为ν-SVR,证明了参数ν与支持向量数目及误差之间的关系,但支持向量数目的减少是以增大误差为代价的.本文提出的简化回归
4、型支持向量机的算法克服了上述方法的不足,在不需要其他优化算法的情况下,可以在容许的误差范围内大幅度地减少支持向量的数目,从而减小计算的复杂度.下面各节分别给出了简化算法、大规模数据情况下的高效学习算法及实验结果.1回归型支持向量机及其简化算法设给定的输入样本x为n维向量,k个样本及其输出值可表示为n(x1,y1),…,(xk,yk)∈R×R,(1)则回归型支持向量机的学习问题就是一个二次规划问题,通常采用Vapnik的ε-不敏感损失函数,即指定容许误差ε,若样本x误差为ξ,则当
5、ξ
6、≤ε时不计损失,否则损失计为
7、ξ
8、−ε
9、.回归函数可表示为k*f(x)=∑(αi−αi)K(x,xi)+b,(2)i=1其中α和α*为求解的k维向量,K(xi,xj)=ϕ(xi)⋅ϕ(xj)称为核函数,ϕ(x)为从样本空间到高维特征空间的映射函数,核Ã收稿日期:2000-08-23;修改日期:2001-04-03基金项目:国家铁道部科技研究开发项目(2000X030-A)作者简介:田盛丰(1944－),男,北京人,教授,主要研究领域为模式识别,人工智能;黄厚宽(1940－),男,四川遂宁人,教授,博士生导师,主要研究领域为人工智能,知识工程,KDD.1170J
10、ournalofSoftware软件学报2002,13(6)函数表示为两个ϕ(x)的点积,核函数的采用使得映射函数ϕ(x)不必明确求出,因此,求解非线性回归成为可能.式*(2)中对应于权值(αi−αi)不为0的样本xi称为支持向量.显然,支持向量的数目决定了计算的复杂度.对上述回归*型支持向量机而言,当
11、f(xi)−yi
12、≥ε时,权值(αi−αi)非零,因此当噪声较大时,支持向量的比例是相当大的.例如,对于噪声在±1范围内均匀分布的情况,若取ε=0.1,则支持向量约占样本总数的90%.选取大的ε值将减少支持向量数目,但将
13、增加误差.下面描述的简化算法可以在误差容许的范围内大幅度地减少支持向量数目.首先,对上述支持向量机,利用式(2)对每个样本xi计算1当f(xi)≥yizi=,i=1,…,k.(3)−1其他新的回归函数也用f(x)表示:f(x)=w⋅ϕ(x)+b,(4)其中w为权向量,b为标量,“⋅”表示向量的点积,ϕ(x)为一个非线性映射.优化问题可表示为最小化目标函数:1kR(w,ξ)=w⋅w+C∑ξi,(5)2i=1其约束条件为zi(w⋅ϕ(xi)+b−yi)≥ε−ξi,ξi≥0,i=1,…,k.(6)其中式(5)的第1项使函
14、数更为平坦,提高了泛化能力,第2项则为减少误差,常数C对两者作出折衷,ε为一个正常数.这是一个二次优化问题,引入拉格郎日函数1kkkL(w,b,ξ,α,γ)=w⋅w+C∑ξi−∑αi[zi(w⋅ϕ(xi)+b−yi)−ε+ξi]−∑γiξi,(7)2i=1i=1i=1其中αi≥0,γi≥0,i=1,…,k.函数L应对
