软件学报  2014, Vol. 25 Issue (9): 2149-2159   PDF    
支持向量学习的多参数同时调节
丁立中, 贾磊, 廖士中    
天津大学 计算机科学与技术学院, 天津 300072
摘要:模型选择是支持向量学习的关键问题.已有模型选择方法采用嵌套的双层优化框架,内层执行支持向量学习,外层通过最小化泛化误差的估计进行模型选择.该框架过程复杂,计算效率低.简化传统的双层优化框架,提出一个支持向量学习的多参数同时调节方法,在同一优化过程中实现模型选择和学习器训练.首先,将支持向量学习中的参数和超参数合并为一个参数向量,利用序贯无约束极小化技术(sequential unconstrained minimization technique,简称SUMT)分别改写支持向量分类和回归的有约束优化问题,得到多参数同时调节模型的多元无约束形式定义;然后,证明多参数同时调节模型目标函数的局部Lipschitz连续性及水平集有界性.在此基础上,应用变尺度方法(variable metric method,简称VMM)设计并实现了多参数同时调节算法.进一步地,基于多参数同时调节模型的性质,证明了算法收敛性,对比分析了算法复杂性.最后,实验验证同时调节算法的收敛性,并实验对比同时调节算法的有效性.理论证明和实验分析表明,同时调节方法是一种坚实、高效的支持向量模型选择方法.
关键词核方法     支持向量学习     模型选择     参数调节     序贯无约束极小化技术    
Simultaneous Multiple Parameters Tuning in Support Vector Learning
DING Li-Zhong, JIA Lei, LIAO Shi-Zhong    
School of Computer Science and Technology, Tianjin University, Tianjin 300072, China
Corresponding author: LIAO Shi-Zhong, E-mail: szliao@tju.edu.cn
Abstract: Model selection is critical to support vector learning. Previous model selection methods mainly adopt a nested two-layer framework, where the inner layer trains the learner and the outer one conducts model selection by minimizing the estimate of the generalization error. Breaking from this framework, this paper proposes an approach of simultaneously tuning multiple parameters of support vector learning, which integrates model selection and learning into one optimization process. It first combines the parameters and hyperparameters involved in support vector learning into one parameter vector. Then, using sequential unconstrained minimization technique (SUMT), it reformulates the constrained optimization problems for support vector classification (SVC) and support vector regression (SVR) as unconstrained optimization problems to give the simultaneous tuning model of SVC and SVR. In addition, it proves the basic properties of the simultaneous tuning model of SVC and SVR, including the local Lipschitz continuity and the boundedness of their level sets. Further, it develops a simultaneous tuning algorithm to iteratively solve simultaneous tuning model. Finally, it proves the convergence of the developed algorithm based on the basic properties of the simultaneous tuning model and provides analysis on complexity of the algorithm as compared with related approaches. The empirical evaluation on benchmark datasets shows that the proposed simultaneous approach has lower running time complexity and exhibits similar predictive performance as existing approaches. Theoretical and experimental results demonstrate that the simultaneous tuning approach is a sound and efficient model selection approach for support vector learning.
Key words: kernel method     support vector learning     model selection     parameter tuning     SUMT (sequential unconstrained minimization technique)    

支持向量学习(support vector learning,简称SVL)是一类重要的机器学习方法[1, 2],该方法在核诱导的特征空间中训练线性学习器,并应用泛化性理论来避免过拟合现象.模型选择是支持向量学习的基本问题,对学习的泛化性有着重要影响,包括核函数及其参数的选择、正则化参数的选择以及回归问题中不敏感度参数的选择.典型的,核函数被确定为若干类型,如多项式核、Gaussian核等.在这种情况下,核函数的选择等价于核参数的调节.本文统称核参数、正则化参数和不敏感度参数为超参数(hyperparameter).支持向量学习的模型选择等价于超参数的调节.已有模型选择方法可概括为一个内外双层的优化框架[3]:内层在超参数固定的情况下,通过凸二次优化训练学习器;外层基于内层的优化结果,通过最小化泛化误差来调节超参数.由于数据的潜在分布未知,泛化误差不可直接计算,可通过经验误差(如交叉验证误差)或理论误差界来估计.

k折交叉验证可给出泛化误差较优的估计[4],交叉验证的极端形式——留一法(leave-one-out,简称LOO)能够给出泛化误差几乎无偏的估计[5].然而,基于交叉验证的模型选择方法通常是格搜索整个超参数空间,对每一组候选的超参数向量都进行学习器训练,不可避免地带来了高的计算复杂性[6].为了提高交叉验证效率,Liu等人利用BIF(Bouligand influence function)给出了交叉验证的一种高效近似[7].另一方面,为了避免格搜索的低效性,进化计算[8]、基因算法[9]、粒子群算法[10]等被引入,以实现超参数的启发式搜索.最小化泛化误差的理论估计界是另一类模型选择方法.常见的误差界有支持向量张成(span)界[11]、半径间隔界[5]和特征值扰动界[12]等.整体上,无论经验方法还是理论误差界法,均是设计某种策略来约减超参数搜索空间,进而提高模型选择外层的效率.但搜索方向的确定具有较高的计算代价或有效性难以验证.另一方面,支持向量学习凸二次优化求解的复杂性为O(l3),多核支持向量学习二阶锥规划求解的复杂性为O(Nl3.5)[13],其中,l为样本规模,N为候选核矩阵的个数.对于大规模实际问题,若对每个搜索路径上的模型都进行一次学习器训练,计算代价太高.

本文简化传统的双层优化框架,提出了一种支持向量学习的多参数同时调节模型,将超参数的调节与学习器的训练在同一优化过程中实现.首先,分别重写支持向量分类(support vector classification,简称SVC)和支持向量回归(support vector regression,简称SVR)的凸二次优化形式,给出SVC和SVR的多参数优化形式.利用序贯无约束极小化技术(sequential unconstrained minimization technique,简称SUMT)[14],将SVC和SVR的多参数优化形式改写为多元无约束优化问题,给出SVC和SVR多参数同时调节模型的形式定义.然后,证明了多参数同时调节模型目标函数的局部Lipschitz连续性及其水平集有界性.在此基础上,应用变尺度方法(variable metric method,简称VMM)设计并实现了同时调节算法(simultaneous tuning algorithm,简称STA),该算法较传统参数调节方法具有更低的计算复杂度.进一步证明了算法的收敛性.最后,通过标准数据集上的实验,验证了同时调节算法的收敛性,对比了同时调节算法与其他参数调节方法的有效性.

廖士中等人基于SVC的半径间隔界准则,提出了一种超参数和参数的同时调节方法[15].由于半径间隔界针对分类问题定义并不适用于回归,廖士中等人进一步从支持向量回归的优化问题出发,提出了SVR的多参数同时调节方法[16].整体而言,这两项工作仅从实验上初步验证了同时调节的可行性和正确性,没有给出理论证明.本文推导了一个新的SVC同时调节模型的形式定义,从理论上证明了SVC和SVR同时调节方法的正确性,细化了同时调节算法,提供了系统的比较实验,给出了一种完备的支持向量学习多参数同时调节方法.

1 支持向量学习

本节简述支持向量分类(support vector classification,简称SVC)和支持向量回归(support vector regression,简称SVR).令X表示输入空间,Y表示输出域,通常有XÍ¡p,二分类问题中Y={-1,1},回归问题中YÍ¡.训练集可表示为S=((x1,y1),…,(xl,yl))Î(XxY)l,其中,xi,yi为样例输入及对应的标签,l为训练集规模.本文考虑的核k是从XxX¡的函数,满足对于任意的有限样本{x1,…,xl}ÍX,矩阵是对称半正定的.

1.1 支持向量分类

SVC的基本思想[1]是:将输入空间的点映射到由核函数k隐式定义的特征空间,在特征空间中构造最优线性分类超平面.SVC的分类函数可表示为,其中,Lagrange乘子是通过求解下述凸优化问题得到的:

(1)

SVC的优化问题公式(1)被称作最大间隔分类器,这一分类器仅适用于特征空间中线性可分的数据.对于非线性可分的情况,需要引入软间隔SVC[17].2-范数软间隔SVC的优化形式可表示为

(2)

公式(2)与公式(1)的不同在于核函数形式的不同,公式(2)中的核函数称为修正核函数,其与核函数k的关系为

(3)

其中,C是正则化参数;dij为Kronecker函数,如果i=j,则dij=1,否则dij=0.正则化参数C可看做是修正核的参数.那么,的核参数向量可表示为,其中,q1,…,qd是核k的参数,¡+表示正实数.以Gaussian核为例,的核参数向量为Q=(C,s)T.

1.2 支持向量回归

基于平方e不敏感损失[1]的SVR优化问题可表示为

(4)

其中,e为不敏感度参数,áw×xiñ表示wxi的点积,xi为松弛变量.

优化问题(4)的核化对偶形式为

(5)

其中,,ai为Lagrange乘子,为修正核函数,同SVC.

2 多参数同时调节模型

本节将SVC和SVR中的Lagrange乘子和超参数向量合并,重写对应优化问题,给出SVC和SVR的多参数表示形式;然后,利用序贯无约束极小化技术(SUMT)推导出SVC和SVR多参数同时调节模型的形式定义.

首先简述SUMT.给定如下有约束优化问题:

(6)

公式(6)的解可通过求解一组无约束优化问题来逼近[14]:

(7)

其中,rk称为障碍因子序列,满足{rk|r0>0,rk+1=brk,0<b<1}.当k®¥,问题(7)的解将趋近于原问题(6)的解.

2.1SVC多参数同时调节模型

本节推导SVC多参数同时调节模型的形式定义.令:

(8)

其中,X将作为新的优化变量.

基于公式(8)中定义的新变量,重写SVC优化问题公式(2),可得:

(9)

利用SUMT将公式(9)表示为关于参数rk的无约束优化问题:

(10)

其中,ei表示第i个元素为1其余元素为0的单位列向量.公式(10)为SVC多参数同时调节模型的形式定义.

同时调节模型公式(10)是多变元无约束优化问题,求解得到的X的最优解X*,同时包含了Lagrange乘子a*、正则化参数C*和核函数参数的最优解.

2.2SVR多参数同时调节模型

本节推导SVR多参数同时调节模型的形式定义.令:

(11)

利用公式(11)中定义的新变量,重写SVR优化问题公式(5),可得:

(12)

利用SUMT重写公式(12),可得SVR多参数同时调节模型的形式定义:

(13)

为了表述清晰,将文中的重要符号记录于表 1.

Table 1 Table of notations 表 1 符号表
3 同时调节模型的基本性质

本节研究SVC和SVR多参数同时调节模型的基本性质,包括的局部Lipschitz连续性及其水平集的有界性.这些性质对于分析多参数同时调节模型求解算法的收敛性具有重要作用.

3.1 的基本性质

本节中,简记Jk.Jk的梯度可表示为.基于SVC多参数同时调节模型的形式定义公式(10),可求得ÑJk(X)中的各个分量:

(14)

其中,Kij=k(xi,xj)表示核矩阵Kij元素,表示核矩阵元素对核参数的导数.为了便于分析,对公式(14)中的参数取值范围做出假设.设inf{C}=h>0,sup{C}=l>0;inf{qt}=z>0,sup{qt}=t>0.如果ai=0,则该aiJk的函数值无影响.因此设inf{ai}=V>0,sup{ai}=y>0.记优化变量X所属域为D,满足.令,kmax为核矩阵K中的最大元素.利用上述参数的取值限定,公式(14)中各个偏导的上下界可表述为公式(15), 基于公式(15)的结果,可证明引理1.

(15)

引理1. Jk是局部Lipschitz连续的.

证明:令,其中,W1,…,W6的定义见公式(15).对于任意的,可得:

(16)

因为Jk(X)是上的连续函数,利用Lagrange中值定理可得:对于任意的u,vÎD,都存在rÎ(0,1),使得:

(17)

结合公式(16)与公式(17),有:

那么,|Jk(u)-Jk(u)|≤L||u-v||.因此,Jk是局部Lipschitz连续的.

下一节将给出求解Jk的同时调节算法,该算法是一个迭代算法.下面讨论中,设优化迭代的初始值为(X0,r0),其中,X0=(1T,0T)T,也就是C=q1=…=qt=1且a1=…=al=0;r0表示障碍因子rk的初始值.

为了方便描述,将Jk(X)重记为J(X,rk).下面引理表述了J(X,rk)的水平集有界性.

引理2. 水平集L={X|J(X,rk)≤J(X0,r0)}是有界的.

证明:将(X0,r0)带入公式(10),可得J(X0,r0)=r0(d+1).多参数同时调节模型是最小化过程,故r0(d+1)可看做J(X,rk)的上界.基于各参数设定的取值范围可知:

.

因此,J(X,rk)有上界和下界.因J(X,rk)是关于X的连续函数,故J(X,rk)的上下界将约束X在一定的域内.

3.2 的基本性质

假设对于i=1,…,l,.

X0=(1T,0T,0T)T,即,C=q1=…=qt=e=1,a1=…=al=0,

采用与SVC类似的证明方式,可得如下引理:

引理3. 是局部Lipschitz连续的.

引理4. 水平集L={X|JSVR(X,rk)≤JSVR(X0,r0)}有界.

4 同时调节算法与分析

本节给出同时调节模型的求解算法、理论分析算法收敛性和复杂性,并与已有参数调节方法进行对比.

4.1 算 法

多参数同时调节模型的求解算法见算法1.算法是基于SVC描述的,基本过程同样适用于SVR.

算法1. Simultaneous Tuning Algorithm.

Require: X0Ρl+d+1, r0, e>0, H0=I, k=0;

1. while ||gk=ÑJ(Xk,rk)||>e do

2.     ;

3.     pk=-Hkgk;

4.     Xk+1=Xk+lkpk;

5.     if k=l+d+1 then

6.             X0=Xk, k=0;

7.     else

8.             Dgk=ÑJ(Xk+1,rk+1)-ÑJ(Xk,rk);

9.             DXk=Xk+1-Xk;

10.             sk=HkDgk;

11.             mk=1/(sk)TDgk;

12.             jk=1/(DXk)TDgk;

13.             Ck=mksk(sk)T;

14.             Bk=jkDXk(DXk)T;

15.             Hk+1=Hk+Bk-Ck;

16.             k=k+1;

17.     end if

18. end while

19. return X=Xk

同时调节算法应用了变尺度方法(variable metric method,简称VMM)[18],采用梯度下降的方式最小化目标函数J.在第k步迭代中,更新方向为pk,计算pk要用到Hkgk,Hk为逆Hessian阵的近似形式,初始化为单位矩阵I;gk为当前目标函数梯度值.优化变元Xk的更新步长为lk,lk通过线性规划得到.更新完Xk后,需计算Hk+1的值,用于下次迭代过程.若算法在第k步终止,则返回最优参数向量X*=Xk.

4.2 收敛性

本节分析算法1的收敛性.Vlček和Lukšan分析了一般VMM的收敛性[18]:如果无约束目标函数f(x)是局部Lipschitz连续的且水平集{x|f(x)≤f(x0)}有界,那么VMM方法是收敛的.现给出如下定理:

定理1. 算法1是收敛的.

证明:引理1~引理4表明,SVC和SVR多参数同时调节模型的目标函数满足局部Lipschitz连续性及水平集有界性.由文献[18]的引理3.4可知,算法1中,序列{gk}是有界的.另外,存在点和一个无限集合XÌ{0,1,2,…}满足,使得.这意味着是目标函数的一个驻点.由文献[18]的引理3.6可知:如果迭代步数有限且最后的下降步出现在第k次迭代,那么点Xk+1J的驻点.

4.3 复杂性对比

传统支持向量学习的模型选择方法通过最小化泛化误差的经验或理论估计来进行模型选择,经验估计包括交叉验证误差或LOO误差,理论估计包括半径间隔界和span界[5, 11]等.记泛化误差的某种估计为¡a,Q,支持向量学习的目标函数为G(a,Q).传统模型选择方法采用的双层优化框架如算法2所示:内层固定超参数Qk通过最小化G(a,Qk)计算参数ak;外层利用内层计算的结果ak,通过最小化计算超参数Qk+1.这类方法需要在内层进行多次学习器训练,以迭代地得到¡a,Q的最小值.利用二次规划求解SVC的复杂度为O(l3),若优化¡a,Q所需的迭代步数为S,则总的计算复杂度为O(Sl3).

算法2. Traditional Model Selection Framework.

1. Initialize a, Q0, k=0;

2. repeat

3.         ak=argminG(a,Qk);

4.         Calculate Qk+1 by minimizing ;

5. until ¡a,Q is minimized

6. return ak, Qk

多参数同时调节算法(算法1)中,因优化变量X包括参数向量a和超参数向量Q,可实现多参数在同一优化过程中同时调节.算法的主要计算代价源自Hk+1的计算.每次迭代的计算复杂度为O((l+d+1)2).对于一般的核函数,如Gaussian核和多项式核,核参数个数远小于样本规模,即d<<l,所以可知O((l+d+1)2)O(l2).令S¢为迭代步数,则总的计算复杂度为O(S¢l2).

5 实验结果与分析

本节首先实验验证多参数同时调节算法的收敛性,然后实验对比多参数调节算法(simultaneous tuning algorithm,简称STA)与其他经典的参数调节方法的有效性.对比方法包括5折交叉验证(5-fold cross validation,简称5-fold CV)、半径间隔界(radius margin bound,简称RMB)和span界.

5.1 数据及实验设置

实验数据选自UCI机器学习数据库\StatLog数据库\Delve数据库,详见表 2.每个数据集按照7:3随机分割为训练集和测试集.为了避免随机性的影响,所有实验重复10次.采用的核函数为Gaussian核.

Table 2 Datasets used in our experiments 表 2 实验数据集
5.2 收敛性

本节验证多参数同时调节算法的收敛性.研究目标函数值J随着迭代次数增加的变化规律,以及通过最小化J选择出的最优参数的测试误差随着迭代次数增加的变化规律.实验结果如图 1图 2所示.可以发现:随着迭代次数的增加,目标函数值J呈现出收敛的趋势;最优参数的测试误差逐步减小并趋于稳定.

Fig. 1 Evolution of the values of optimization objective J as iterations increase图 1 目标函数J随着迭代次数增加的变化曲线

Fig. 2 Evolution of the test errors as iterations increase图 2 测试误差随着迭代次数增加的变化曲线
5.3 有效性

本节实验对比同时调节算法与其他参数调节方法的有效性,有效性包括泛化性和效率.泛化性由测试集上的平均测试误差来评估,效率由进行模型选择的平均计算时间来评估.应用不同的模型选择方法在训练集上进行模型选择得到最优超参数,然后在测试集上计算测试误差评估最优超参数的性能.每个数据集重复随机分割10次进行实验,得到的平均测试误差及标准差见表 3.利用5%显著性t检验对实验结果进行分析.在前6个数据集上,4个方法的测试误差没有显著不同;在W1a数据集上,同时调节算法和span界的测试误差显著低于5折交叉验证和RMB.值得指出的是,span界存在局部最小问题且难以实现[5],故不常采用.计算效率方面,所有方法的效率都明显高于5折交叉验证.同时调节算法的效率高于RMB和span界.另外,训练集规模越大,调节算法的效率优势越明显.因此,综合考虑效率和泛化性,同时调节算法的有效性优于其他参数调节方法.

Table 3 Comparison of running time and test errors of different approaches 表 3 不同参数调节方法运行时间和测试误差的比较
6 结 语

本文提出一种支持向量学习的多参数同时调节方法,简化传统的双层迭代框架,为求解支持向量学习的模型选择问题提供了一个新的范型.给出SVC和SVR多参数同时调节模型的形式定义,理论分析模型的局部Lipschitz连续性及其水平集的有界性.设计并实现多参数同时调节算法,证明算法收敛性并对比分析算法复杂性.标准数据集上的实验结果表明,同时调节算法的有效性优于其他参数调节方法.理论证明和实验分析表明,多参数同时调节方法是坚实、高效的支持向量学习模型选择方法.

多参数同时调节模型适用于处理核参数个数较多的情况,因此,进一步工作考虑将这一模型扩展到更复杂情况,包括多核[13, 19, 20]和超核[21].

参考文献
[1] Vapnik V. The Nature of Statistical Learning Theory. 2nd ed., New York: Springer-Verlag, 2000.
[2] Ding SF, Huang HJ, Shi ZZ. Weighted smooth CHKS twin support vector machines. Ruan Jian Xue Bao/Journal of Software, 2013, 24(11):2548-2557 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4475.htm
[3] Guyon I, Saffari A, Dror G. Model selection: Beyond the Bayesian/frequentist divide. Journal of Machine Learning Research, 2010, 11:61-87.
[4] Duan K, Keerthi S, Poo A. Evaluation of simple performance measures for tuning SVM hyperparameters. Neurocomputing, 2003, 51:41-59 .
[5] Chapelle O, Vapnik V, Bousquet O. Choosing multiple parameters for support vector machines. Machine Learning, 2002,46(1-3): 131-159 .
[6] Xu Z, Dai M, Meng D. Fast and efficient strategies for model selection of Gaussian support vector machine. IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009,39(5):1292-1307 .
[7] Liu Y, Jiang SL, Liao SZ. Efficient approximation of cross-validation for kernel methods using Bouligand influence function. In: Xing EP, Jebara T, eds. Proc. of the 31st Int’l Conf. on Machine Learning. New York: ACM Press, 2014. 324-332.
[8] Friedrichs F, Igel C. Evolutionary tuning of multiple SVM parameters. Neurocomputing, 2005,64:107-117 .
[9] Huang C, Wang C. A GA-based feature selection and parameters optimization for support vector machines. Expert Systems with Applications, 2006,31(2):231-240 .
[10] Guo XC, Yang JH, Wu CG, Wang CY, Liang YC. A novel LS-SVMs hyper-parameter selection based on particle swarm optimization. Neurocomputing, 2008,71(16):3211-3215 .
[11] Vapnik V, Chapelle O. Bounds on error expectation for support vector machines. Neural Computation, 2000,12(9):2013-2036 .
[12] Liu Y, Jiang SL, Liao SZ. Eigenvalues perturbation of integral operator for kernel selection. In: He Q, Iyengar A, Nejdl W, Pei J, Rastogi R, eds. Proc. of the 22nd ACM Int’l Conf. on Information and Knowledge Management. New York: ACM Press, 2013. 2189-2198 .
[13] Jia L, Liao SZ, Ding LZ. Learning with uncertain kernel matrix set. Journal of Computer Science and Technology, 2010,25(4): 709-727 .
[14] McCormick G. The projective SUMT method for convex programming. Mathematics of Operations Research, 1989,14(2):203-223 .
[15] Liao SZ, Jia L. Simultaneous tuning of hyperparameter and parameter for support vector machines. In: Zhou ZH, Li H, Yang Q, eds. Proc. of the 11th Pacific-Asia Conf. on Knowledge Discovery and Data Mining. Berlin: Springer-Verlag, 2007. 162-172 .
[16] Liao SZ, Ding LZ, Jia L. Simultaneous tuning of multiple parameters for support vector regression. Journal of Nanjing University (Natural Sciences), 2009,45(5):585-592 (in Chinese with English abstract).
[17] Cortes C, Vapnik V. Support-Vector networks. Machine Learning, 1995,20(3):273-297 .
[18] Vlček J, Lukšan L. Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization. Journal of Optimization Theory and Applications, 2001,111(2):407-430 .
[19] Lanckriet GRG, Cristianini N, Bartlett P. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 2004,5:27-72.
[20] Sonnenburg S, Rätsch G, Schäfer C. Large scale multiple kernel learning. Journal of Machine Learning Research, 2006,7: 1531-1565.
[21] Ong C, Smola A, Williamson R. Learning the kernel with hyperkernels. Journal of Machine Learning Research, 2005,6:1043-1071.
[2] 丁世飞,黄华娟,史忠植.加权光滑CHKS孪生支持向量机.软件学报,2013,24(11):2548-2557. http://www.jos.org.cn/1000-9825/4475.htm
[16] 廖士中,丁立中,贾磊.支持向量回归多参数的同时调节.南京大学学报(自然科学版),2009,45(5):585-592.