您还未登录，请登录后再进行相关操作！博主最新文章
博主热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)第十一课 贝叶斯统计正则化 - 简书
第十一课 贝叶斯统计正则化
**就是要找更好的估计方法来减少过度拟合情况的发生。 **
贝叶斯统计及正则化
如何使用机器学习算法解决具体问题：诊断算法，销蚀分析，过早优化
如果选取的特征太少，欠拟合，对于训练集的拟合效果不好，对于测试集的预测效果应该也不会好；但是如果选取的特征太多，过拟合，对于训练集的拟合效果非常好，但是对于测试集的集合效果会变差。
合适的拟合
解决过拟合的方法：
减少特征的数量：
-人工的选择保留哪些特征；
-模型选择算法（上一讲）
-保留所有的特征，但是降低参数的量/值；
-正则化的好处是当特征很多时，每一个特征都会对预测y贡献一份合适的力量；
1. 贝叶斯统计及其正则化
贝叶斯公式(用来求后验概率的)：
贝叶斯公式
对于参数theta的值
频率学派认为这个值是固定的，我们可以通过极大似然估计去猜测这个值。MLE：最大似然估计
贝叶斯学派认为这个值是一个随机变量。服从某个先验分布(实际应用中一般是自然分布作为先验分布)，theta-p(theta)。后验概率可以用贝叶斯公式求出 MAP：maximum a posteriori 最大后验估计：
这个公式的计算量其实很大，所以实际应用中一般都用最大化后验概率来求出theta，然后带入假设模型htheta(x)中预测：
最大化后验概率
可以与极大似然估计求theta的公式比较一下：
极大似然估计
发现其实用贝叶斯法求theta只是在末尾加了一个p(theta).
用后验概率法得到的参数theta更不容易拟合，从而降低了过拟合的概率。
模型选择的典型方法是正则化。正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项(regularizer)或罚项(penalty term)。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。比如，正则化项可以是模型参数向量的范数。
对于代价函数：
最大似然估计法是用最小二乘的原理
后验概率分布估计则是又引入了一个相当于惩罚项的正则项
这样就可以使得高次项的贡献权重降低，减少过拟合的可能性。
线性回归的正则化
逻辑回归的正则化
2. 在线学习
什么是在线学习？
之前学习的算法都属于批量学习（batch learning），一次性批量输入给学习算法，可以被形象的称为填鸭式学习。
在线学习（online learning），按照顺序，循序的学习，不断的去修正模型，进行优化。
在线学习首先有一个初始的分类器，当第一个样本到来时，对该样本进行预测，得到预测结果，然后利用该样本的信息对分类器进行更新(比如，考虑感知器算法的更新规则，见笔记
1-2)；然后第二个样本到来时做同样的操作，以此类推。这样，我们就对 m 个样本都有一个预测值，只不过它们都是在训练的过程中得到的，对这些预测值进行统计，就得到了在线训练误差。这就是过程上在线学习与批处理的不同之处。
就是二类分类的线性分类模型，其输入为样本的特征向量，输出为样本的类别，取+1和-1二值，即通过某样本的特征，就可以准确判断该样本属于哪一类。顾名思义，感知机能够解决的问题首先要求特征空间是线性可分的，再者是二类分类，即将样本分为{+1, -1}两类。
对于感知器算法来说，若正负样本线性可分，那么在线学习算法也是收敛的。
3. 算法的改进方法
a. 算法诊断
如果现存算法的预测效果比较差，可以考虑的改进因素一般有：
怎么去选择最有效的改进算法是这部分的目的。
方差/偏差分析
高方差--过拟合，训练误差很小但泛化误差很大。
需要更多的数据解决或者更少的特征解决。
高方差的误差率
高偏差--模型本身不合适，比如特征数目过少，表现是训练误差和泛化误差都很大。
需要更多的特征或者更复杂的模型来解决。
高偏差的误差率
是否收敛和目标函数是否正确的判断*
可以画出迭代次数和目标函数的趋势图，但一般很难判断，因为每次优化的只是一小部分。
(这部分还不太懂)
b. 销蚀分析
比如对于垃圾邮件分类器来说，先构建一个初始分类器，然后考虑一些比较高级的特征，比如邮件的语法风格、邮件的主机信息、邮件标题等。先将所有特征全加入到分类器中，然后逐个剔除，观察性能的下降幅度，将那些没有使性能下降或下降很少的特征删去。
机器学习是做NLP和计算机视觉这类应用算法的基础，虽然现在深度学习模型大行其道，但是懂一些传统算法的原理和它们之间的区别还是很有必要的。可以帮助我们做一些模型选择。本篇博文就总结一下各种机器学习算法的特点和应用场景。本文是笔者结合自身面试中遇到的问题和总结网络上的资源得到的...
文章作者：Tyan博客：noahsnail.com | CSDN | 简书 1. 统计学习方法概论 本文是统计学习方法（李航）第一章的学习总结。 1.1 统计学习 1.统计学习的特点 统计学习（statistical learning）是关于计算机基于数据构建概率统计模型并...
首页 资讯 文章 资源 小组 相亲 登录 注册 首页 最新文章 IT 职场 前端 后端 移动端 数据库 运维 其他技术 - 导航条 -首页最新文章IT 职场前端- JavaScript- HTML5- CSS后端- Python- Java- C/C++- PHP- .NE...
A 准确率（accuracy） 分类模型预测准确的比例。在多类别分类中，准确率定义如下： 在二分类中，准确率定义为： 激活函数（Activation function） 一种函数（例如 ReLU 或 Sigmoid），将前一层所有神经元激活值的加权和输入到一个非线性函数中，...
谷歌开发者机器学习词汇表：纵览机器学习基本词汇与概念 姓名：钟航 转载自：http://mp.weixin.qq.com/s?__biz=MzA3MzI4MjgzMw==&mid=&idx=1&sn=4bbdc85b363d50ceaff...
8月14日至16日的朗程思维导图作文与思维导图阅读培训花絮。 经过两天半的培训，各位参会校长、老师在总部教研管理中心两位讲师的悉心指导下，认真学习了思维导图作文、思维导图阅读的课程体系；了解项目的优势、学习思维导图理论并实际动手绘制。 老师们深切感受到了思维导图作为工具的优...
这段时间，发生最大的事儿就是团队分课题了吧。我还算是幸运的，起码在最一开始，可以选择自己选择的。说到这，我自己也要反省一下自己，有自己的想法，想说什么，一定要自己争取早说，不要等。机不可失失不再来，这次的事儿，可能没有涉及到我自己的利益，但是，以后谁知道呢。机会有时候是给准...
目录上一回第二十四回 张濬献策盐池导火 河北出兵意在沛公 京畿。长安。 日落时分，士农工商纷纷回到自家坊中。随着余晖点点散尽，武侯们驱赶着还未入坊的百姓。 坊门渐次关闭，夜禁开始了。 光德坊东南隅，两道影子从侧面闪进京兆尹府。入了中堂，二人叉手行礼，映出杜让能和张濬的面庞，...
1 “妈，我回来了！”当我兴冲冲的回到家里，发现妈妈不在家里。 四处寻找后，邻居大妈告诉我，妈妈在村口的菜苔地里。 我兴奋地一路小跑，来到满眼的紫色菜苔地里。只见母亲身在其中，弯着腰、低着头摘下一根一根的菜苔，理成一把后放在大筐里。 这时，大筐里面已经整整齐齐的摆满了新鲜的...
提起手镯大家都不陌生，玉手镯作为一种常见的玉器饰品由来已久，如今更是女性必不可少的饰品之一，通常我们在市场上见到的手镯都是已经制成的成品，很难见识手镯的加工过程。
每当经过朋友玉器行时，都会进去欣赏一下，柜台里琳琅满目的玉器看得眼花缭乱，品品都是晶莹剔透，拿起爱不释手。...&&&&2014, Vol. 25 Issue (9):
丁立中, 贾磊, 廖士中. 支持向量学习的多参数同时调节[J].软件学报,): .http://www.jos.org.cn/50.html &&
DING Li-Zhong, JIA Lei, LIAO Shi-Zhong. Simultaneous Multiple Parameters Tuning in Support Vector Learning[J]. Ruan Jian Xue Bao/ Journal of Software, ): .http://www.jos.org.cn/50.html &&
支持向量学习的多参数同时调节
丁立中, 贾磊, 廖士中&&&&
天津大学 计算机科学与技术学院, 天津 300072
基金项目:国家自然科学基金()
作者简介：丁立中(1986－),男,内蒙古呼和浩特人,博士生,CCF学生会员,主要研究领域为核方法模型选择.
E-mail: dinglizhong@tju.edu.cn贾磊(1981－),男,博士,主要研究领域为机器学习,模型选择,核方法.
E-mail: ljia@tju.edu.cn
通讯作者：廖士中(1964－),男,博士,教授,博士生导师,CCF会员,主要研究领域为人工智能应用基础,理论计算机科学.
E-mail: szliao@tju.edu.cn
摘要：模型选择是支持向量学习的关键问题.已有模型选择方法采用嵌套的双层优化框架,内层执行支持向量学习,外层通过最小化泛化误差的估计进行模型选择.该框架过程复杂,计算效率低.简化传统的双层优化框架,提出一个支持向量学习的多参数同时调节方法,在同一优化过程中实现模型选择和学习器训练.首先,将支持向量学习中的参数和超参数合并为一个参数向量,利用序贯无约束极小化技术(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)是一类重要的机器学习方法[, ],该方法在核诱导的特征空间中训练线性学习器,并应用泛化性理论来避免过拟合现象.模型选择是支持向量学习的基本问题,对学习的泛化性有着重要影响,包括核函数及其参数的选择、正则化参数的选择以及回归问题中不敏感度参数的选择.典型的,核函数被确定为若干类型,如多项式核、Gaussian核等.在这种情况下,核函数的选择等价于核参数的调节.本文统称核参数、正则化参数和不敏感度参数为超参数(hyperparameter).支持向量学习的模型选择等价于超参数的调节.已有模型选择方法可概括为一个内外双层的优化框架[]:内层在超参数固定的情况下,通过凸二次优化训练学习器;外层基于内层的优化结果,通过最小化泛化误差来调节超参数.由于数据的潜在分布未知,泛化误差不可直接计算,可通过经验误差(如交叉验证误差)或理论误差界来估计.
k折交叉验证可给出泛化误差较优的估计[],交叉验证的极端形式——留一法(leave-one-out,简称LOO)能够给出泛化误差几乎无偏的估计[].然而,基于交叉验证的模型选择方法通常是格搜索整个超参数空间,对每一组候选的超参数向量都进行学习器训练,不可避免地带来了高的计算复杂性[].为了提高交叉验证效率,Liu等人利用BIF(Bouligand influence function)给出了交叉验证的一种高效近似[].另一方面,为了避免格搜索的低效性,进化计算[]、基因算法[]、粒子群算法[]等被引入,以实现超参数的启发式搜索.最小化泛化误差的理论估计界是另一类模型选择方法.常见的误差界有支持向量张成(span)界[]、半径间隔界[]和特征值扰动界[]等.整体上,无论经验方法还是理论误差界法,均是设计某种策略来约减超参数搜索空间,进而提高模型选择外层的效率.但搜索方向的确定具有较高的计算代价或有效性难以验证.另一方面,支持向量学习凸二次优化求解的复杂性为O(l3),多核支持向量学习二阶锥规划求解的复杂性为O(Nl3.5)[],其中,l为样本规模,N为候选核矩阵的个数.对于大规模实际问题,若对每个搜索路径上的模型都进行一次学习器训练,计算代价太高.
本文简化传统的双层优化框架,提出了一种支持向量学习的多参数同时调节模型,将超参数的调节与学习器的训练在同一优化过程中实现.首先,分别重写支持向量分类(support vector classification,简称SVC)和支持向量回归(support vector regression,简称SVR)的凸二次优化形式,给出SVC和SVR的多参数优化形式.利用序贯无约束极小化技术(sequential unconstrained minimization technique,简称SUMT)[],将SVC和SVR的多参数优化形式改写为多元无约束优化问题,给出SVC和SVR多参数同时调节模型的形式定义.然后,证明了多参数同时调节模型目标函数的局部Lipschitz连续性及其水平集有界性.在此基础上,应用变尺度方法(variable metric method,简称VMM)设计并实现了同时调节算法(simultaneous tuning algorithm,简称STA),该算法较传统参数调节方法具有更低的计算复杂度.进一步证明了算法的收敛性.最后,通过标准数据集上的实验,验证了同时调节算法的收敛性,对比了同时调节算法与其他参数调节方法的有效性.
廖士中等人基于SVC的半径间隔界准则,提出了一种超参数和参数的同时调节方法[].由于半径间隔界针对分类问题定义并不适用于回归,廖士中等人进一步从支持向量回归的优化问题出发,提出了SVR的多参数同时调节方法[].整体而言,这两项工作仅从实验上初步验证了同时调节的可行性和正确性,没有给出理论证明.本文推导了一个新的SVC同时调节模型的形式定义,从理论上证明了SVC和SVR同时调节方法的正确性,细化了同时调节算法,提供了系统的比较实验,给出了一种完备的支持向量学习多参数同时调节方法.
1 支持向量学习
本节简述支持向量分类(support vector classification,简称SVC)和支持向量回归(support vector regression,简称SVR).令X表示输入空间,Y表示输出域,通常有X&I&p,二分类问题中Y={-1,1},回归问题中Y&I&.训练集可表示为S=((x1,y1),…,(xl,yl))&I(XxY)l,其中,xi,yi为样例输入及对应的标签,l为训练集规模.本文考虑的核k是从XxX到&的函数,满足对于任意的有限样本{x1,…,xl}&IX,矩阵是对称半正定的.
1.1 支持向量分类
SVC的基本思想[]是:将输入空间的点映射到由核函数k隐式定义的特征空间,在特征空间中构造最优线性分类超平面.SVC的分类函数可表示为,其中,Lagrange乘子是通过求解下述凸优化问题得到的:
SVC的优化问题公式(1)被称作最大间隔分类器,这一分类器仅适用于特征空间中线性可分的数据.对于非线性可分的情况,需要引入软间隔SVC[].2-范数软间隔SVC的优化形式可表示为
公式(2)与公式(1)的不同在于核函数形式的不同,公式(2)中的核函数称为修正核函数,其与核函数k的关系为
其中,C是正则化参数;dij为Kronecker函数,如果i=j,则dij=1,否则dij=0.正则化参数C可看做是修正核的参数.那么,的核参数向量可表示为,其中,q1,…,qd是核k的参数,&+表示正实数.以Gaussian核为例,的核参数向量为Q=(C,s)T.
1.2 支持向量回归
基于平方e不敏感损失[]的SVR优化问题可表示为
其中,e为不敏感度参数,áw×xi&表示w与xi的点积,xi和为松弛变量.
优化问题(4)的核化对偶形式为
其中,,ai为Lagrange乘子,为修正核函数,同SVC.
2 多参数同时调节模型
本节将SVC和SVR中的Lagrange乘子和超参数向量合并,重写对应优化问题,给出SVC和SVR的多参数表示形式;然后,利用序贯无约束极小化技术(SUMT)推导出SVC和SVR多参数同时调节模型的形式定义.
首先简述SUMT.给定如下有约束优化问题:
公式(6)的解可通过求解一组无约束优化问题来逼近[]:
其中,rk称为障碍因子序列,满足{rk|r0&0,rk+1=brk,0&b&1}.当k&&,问题(7)的解将趋近于原问题(6)的解.
2.1SVC多参数同时调节模型
本节推导SVC多参数同时调节模型的形式定义.令:
其中,X将作为新的优化变量.
基于公式(8)中定义的新变量,重写SVC优化问题公式(2),可得:
利用SUMT将公式(9)表示为关于参数rk的无约束优化问题:
其中,ei表示第i个元素为1其余元素为0的单位列向量.公式(10)为SVC多参数同时调节模型的形式定义.
同时调节模型公式(10)是多变元无约束优化问题,求解得到的X的最优解X*,同时包含了Lagrange乘子a*、正则化参数C*和核函数参数的最优解.
2.2SVR多参数同时调节模型
本节推导SVR多参数同时调节模型的形式定义.令:
利用公式(11)中定义的新变量,重写SVR优化问题公式(5),可得:
利用SUMT重写公式(12),可得SVR多参数同时调节模型的形式定义:
为了表述清晰,将文中的重要符号记录于表 1.
表 1(Table 1)
Table 1 Table of notations 表1 符号表
训练集((x1,y1),…,(xl,yl))&I(XxY)l,其中,X和Y分别为输入输出空间
预测函数f:X&Y
核矩阵,其中,k为从XxX到&的核函数
修正核函数
修正核的参数,其中,C为正则化参数,q1,…,qd为核k的参数
SVR不敏感度参数
Lagrange乘子向量
障碍因子序列{rk|r0&0,rk+1=brk,0&b&1}
多参数同时调节模型的优化变量,包括Lagrange乘子向量和超参数
SVC与SVR多参数同时调节模型的目标函数
核矩阵元素Kij对核参数qt的偏导数
h, l, z, t, V, y
超参数和Lagrange乘子取值的上下确界
同时调节模型目标函数偏导的上下界
Table 1 Table of notations 表 1 符号表
3 同时调节模型的基本性质
本节研究SVC和SVR多参数同时调节模型和的基本性质,包括和的局部Lipschitz连续性及其水平集的有界性.这些性质对于分析多参数同时调节模型求解算法的收敛性具有重要作用.
3.1 的基本性质
本节中,简记为Jk.Jk的梯度可表示为.基于SVC多参数同时调节模型的形式定义公式(10),可求得&NJk(X)中的各个分量:
其中,Kij=k(xi,xj)表示核矩阵K的ij元素,表示核矩阵元素对核参数的导数.为了便于分析,对公式(14)中的参数取值范围做出假设.设inf{C}=h&0,sup{C}=l&0;inf{qt}=z&0,sup{qt}=t&0.如果ai=0,则该ai对Jk的函数值无影响.因此设inf{ai}=V&0,sup{ai}=y&0.记优化变量X所属域为D,满足.令,kmax为核矩阵K中的最大元素.利用上述参数的取值限定,公式(14)中各个偏导的上下界可表述为公式(15), 基于公式(15)的结果,可证明引理1.
引理1. Jk是局部Lipschitz连续的.
证明:令,其中,W1,…,W6的定义见公式(15).对于任意的,可得:
因为Jk(X)是上的连续函数,利用Lagrange中值定理可得:对于任意的u,v&ID,都存在r&I(0,1),使得:
结合公式(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 同时调节算法与分析
本节给出同时调节模型的求解算法、理论分析算法收敛性和复杂性,并与已有参数调节方法进行对比.
多参数同时调节模型的求解算法见算法1.算法是基于SVC描述的,基本过程同样适用于SVR.
算法1. Simultaneous Tuning Algorithm.
Require: X0&I&l+d+1, r0, e&0, H0=I, k=0;
1. while ||gk=&NJ(Xk,rk)||&e do
3. &&&&pk=-Hkgk;
4.&&&& Xk+1=Xk+lkpk;
5.&&&& if k=l+d+1 then
6.&&&&&&&&&&&& X0=Xk, k=0;
7.&&&& else
8. &&&&&&&&&&&&Dgk=&NJ(Xk+1,rk+1)-&NJ(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)[],采用梯度下降的方式最小化目标函数J.在第k步迭代中,更新方向为pk,计算pk要用到Hk和gk,Hk为逆Hessian阵的近似形式,初始化为单位矩阵I;gk为当前目标函数梯度值.优化变元Xk的更新步长为lk,lk通过线性规划得到.更新完Xk后,需计算Hk+1的值,用于下次迭代过程.若算法在第k步终止,则返回最优参数向量X*=Xk.
4.2 收敛性
本节分析算法1的收敛性.Vlček和Lukšan分析了一般VMM的收敛性[]:如果无约束目标函数f(x)是局部Lipschitz连续的且水平集{x|f(x)≤f(x0)}有界,那么VMM方法是收敛的.现给出如下定理:
定理1. 算法1是收敛的.
证明:引理1~引理4表明,SVC和SVR多参数同时调节模型的目标函数满足局部Lipschitz连续性及水平集有界性.由文献[]的引理3.4可知,算法1中,序列{gk}是有界的.另外,存在点和一个无限集合X&I{0,1,2,…}满足,使得.这意味着是目标函数的一个驻点.由文献[]的引理3.6可知:如果迭代步数有限且最后的下降步出现在第k次迭代,那么点Xk+1为J的驻点.
4.3 复杂性对比
传统支持向量学习的模型选择方法通过最小化泛化误差的经验或理论估计来进行模型选择,经验估计包括交叉验证误差或LOO误差,理论估计包括半径间隔界和span界[, ]等.记泛化误差的某种估计为&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;
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核.
表 2(Table 2)
Table 2 Datasets used in our experiments 表2 实验数据集
Breast cancer
Table 2 Datasets used in our experiments 表 2 实验数据集
5.2 收敛性
本节验证多参数同时调节算法的收敛性.研究目标函数值J随着迭代次数增加的变化规律,以及通过最小化J选择出的最优参数的测试误差随着迭代次数增加的变化规律.实验结果如图 1和图 2所示.可以发现:随着迭代次数的增加,目标函数值J呈现出收敛的趋势;最优参数的测试误差逐步减小并趋于稳定.
图 1Fig. 1Fig. 1 Evolution of the values of optimization objective J as iterations increase图 1 目标函数J随着迭代次数增加的变化曲线
图 2Fig. 2Fig. 2 Evolution of the test errors as iterations increase图 2 测试误差随着迭代次数增加的变化曲线
5.3 有效性
本节实验对比同时调节算法与其他参数调节方法的有效性,有效性包括泛化性和效率.泛化性由测试集上的平均测试误差来评估,效率由进行模型选择的平均计算时间来评估.应用不同的模型选择方法在训练集上进行模型选择得到最优超参数,然后在测试集上计算测试误差评估最优超参数的性能.每个数据集重复随机分割10次进行实验,得到的平均测试误差及标准差见表 3.利用5%显著性t检验对实验结果进行分析.在前6个数据集上,4个方法的测试误差没有显著不同;在W1a数据集上,同时调节算法和span界的测试误差显著低于5折交叉验证和RMB.值得指出的是,span界存在局部最小问题且难以实现[],故不常采用.计算效率方面,所有方法的效率都明显高于5折交叉验证.同时调节算法的效率高于RMB和span界.另外,训练集规模越大,调节算法的效率优势越明显.因此,综合考虑效率和泛化性,同时调节算法的有效性优于其他参数调节方法.
表 3(Table 3)
Table 3 Comparison of running time and test errors of different approaches 表3 不同参数调节方法运行时间和测试误差的比较
Table 3 Comparison of running time and test errors of different approaches 表 3 不同参数调节方法运行时间和测试误差的比较
本文提出一种支持向量学习的多参数同时调节方法,简化传统的双层迭代框架,为求解支持向量学习的模型选择问题提供了一个新的范型.给出SVC和SVR多参数同时调节模型的形式定义,理论分析模型的局部Lipschitz连续性及其水平集的有界性.设计并实现多参数同时调节算法,证明算法收敛性并对比分析算法复杂性.标准数据集上的实验结果表明,同时调节算法的有效性优于其他参数调节方法.理论证明和实验分析表明,多参数同时调节方法是坚实、高效的支持向量学习模型选择方法.
多参数同时调节模型适用于处理核参数个数较多的情况,因此,进一步工作考虑将这一模型扩展到更复杂情况,包括多核[, , ]和超核[].
Vapnik V. The Nature of Statistical Learning Theory. 2nd ed., New York: Springer-Verlag, 2000.
Ding SF, Huang HJ, Shi ZZ. Weighted smooth CHKS twin support vector machines. Ruan Jian Xue Bao/Journal of Software, ): (in Chinese with English abstract).
Guyon I, Saffari A, Dror G. Model selection: Beyond the Bayesian/frequentist divide. Journal of Machine Learning Research, -87.
Duan K, Keerthi S, Poo A. Evaluation of simple performance measures for tuning SVM hyperparameters..
Chapelle O, Vapnik V, Bousquet O. Choosing multiple parameters for support vector machines..
Xu Z, Dai M, Meng D. Fast and efficient strategies for model selection of Gaussian support vector machine. IEEE Trans..
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, 2.
Friedrichs F, Igel C. Evolutionary tuning of multiple SVM parameters..
Huang C, Wang C. A GA-based feature selection and parameters optimization for support vector machines..
Guo XC, Yang JH, Wu CG, Wang CY, Liang YC. A novel LS-SVMs hyper-parameter selection based on particle swarm optimization..
Vapnik V, Chapelle O. Bounds on error expectation for support vector machines..
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. .
Jia L, Liao SZ, Ding LZ. Learning with uncertain kernel matrix set..
McCormick G. The projective SUMT method for convex programming..
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. .
Liao SZ, Ding LZ, Jia L. Simultaneous tuning of multiple parameters for support vector regression. Journal of Nanjing University (Natural Sciences), ):585-592 (in Chinese with English abstract).
Cortes C, Vapnik V. Support-Vector networks..
Vlček J, Lukšan L. Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization..
Lanckriet GRG, Cristianini N, Bartlett P. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, -72.
Sonnenburg S, R&tsch G, Sch&fer C. Large scale multiple kernel learning. Journal of Machine Learning Research, 31-1565.
Ong C, Smola A, Williamson R. Learning the kernel with hyperkernels. Journal of Machine Learning Research, 3-1071.
丁世飞,黄华娟,史忠植.加权光滑CHKS孪生支持向量机.软件学报,):.
廖士中,丁立中,贾磊.支持向量回归多参数的同时调节.南京大学学报(自然科学版),):585-592.