回归型支持向量机的简化算法

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