《支持向量机的模型选择研究》由会员分享，可在线阅读，更多相关《支持向量机的模型选择研究（41页珍藏版）》请在金锄头文库上搜索。
1、工学硕士学位论文支持向量机的模型选择研究硕 士 研 究 生 ： 林沂蒙导申 请师： 杨苏教授学 位： 工学硕士学 科 、 专 业： 计算机科学与技术所 在 单 位： 深圳研究生院答 辩 日 期： 2006 年 6 月授予学位单位： 哈尔滨工业大学Classified Index: TM151.3 U.D.C: 621.3Dissertation for the Master Degree of EngineeringRESEARCH ON MODEL SELECTION OFSUPPORT VECTOR MACHINECandidate:Supervisor:Academic Degree A
2、pplied for:Specialty:Affiliation:Date of Defence:Degree-Conferring-Institution:Lin Yimeng Prof. Daniel YeungMaster of EngineeringComputer Science and Technology Shenzhen Graduate School June, 2006Harbin Institute of Technology哈尔滨工业大学工学硕士学位论文摘要支持向量分类中 , 高斯核不区分样本中各个特征的重要性 . 显然 , 各个 特征对分类的贡献一般是不相同的 , 为
3、了体现这种差别从而提高支持向量 机的泛化能力, 文中提出了多宽度高斯核的概念. 多宽度高斯核增加了支持 向量机的超级参数, 针对这一情况, 文中提出了支持向量机的多参数模型选 择的算法 , 该算法利用半径 -间隔的泛化误差期望界自动实现模型选择 . 通 过实验验证了多宽度高斯核和多参数模型选择算法在提高支持向量分类中的有效性.高斯核是支持向量机优先选择的核函数, 其宽度参数定义了核函数的泛 化规模. 由于样本分布的不均匀性, 单一宽度的高斯核会在样本空间的稠密 区域产生过学习现象 , 在稀疏区域产生欠学习现象 , 即存在局部泛化风险 . 针对于此, 文中构造了一个“全局性”的次核去降低高斯核产
4、生的局部泛化 风险, 次核是为了拟补主核的不足, 这里高斯核称为主核, 构造的新核称为 主次核. 文中利用幂级数构造性的给出并证明了次核的正定性条件. 进一步 提出了基于遗传算法的两阶段模型选择去解决主次核的模型选择问题 , 该 算法通过最小化泛化误差界, 首先选择主核的模型参数, 然后再选择次核的 模型参数, 实验证明, 这一策略是非常有效和鲁棒的.关键词主次核 ; 高斯核 ; 泛化误差界 ; 支持向量分类 ; 多宽度高斯核 ; 多 参数模型选择;I哈尔滨工业大学工学硕士学位论文AbstractTo improve the generalizationperformance of suppo
5、rt vector classification, the Gaussian kernel with multiple widths is proposed to emphasize the different contributions of features to classification. With this kernel, the related model selection scheme is designed which can automatically tune multiple parameters for support vector machines by mini
6、mizing the radius margin bound on error expectation of L1-SVM. The ideas are validated via experiments. In SVM classification, Gaussian kernel is firstly selected with high performance and its width defines the generalization scale. However, Gaussian kernel is not well adaptive everywhere in the pat
7、tern space if the patterns are unevenly distributed. That is, the over-fitting learning will appear in dense areas and otherwise under-fitting learning in sparse areas, and consequently, both will cause local risks. To reduce such local risks, a secondary kernel with global character is introduced w
8、hich can enhance globality for Gaussian kernel. Gaussian kernel with local character is used as primary kernel. The constructed kernel is called the primary-secondary kernel(PSK). The positive definiteness of the secondary kernel with given constraints is proved by virtue of power series. Besides, t
9、wo-stage model selection based on genetic algorithms is proposed to tune hyper-parametersfor PSK. The algorithms first optimize the parameters of the primary kernel and then the ones of the secondary kernel. The objective function to be minimized is the radius-margin bound of L1-SVM. Experiments dem
10、onstrate that PSK performs better than Gaussian kernel and also validate the efficiency of the proposed algorithms.Keywords support vector classification; Gaussian kernel with multiple widths; model selection with multiple parameters; bound on error expectation Primary-secondary kernel; Gaussiankern
11、el; positivedefiniteness; generalization error bound; genetic algorithms; two stage modelII哈尔滨工业大学工学硕士学位论文目 录摘要 I Abstract II 第 1 章绪论 11.1 课题背景 . 11.2 本课题研究的目的及意义 . 2 1.3 支持向量机研究及发展现状 . 2 1.4 本文主要研究内容 . 3 第 2 章支持向量机原理 . 42.1 支持向量机基本思想 . 42.2 线性可分情况 5 2.3 线性不可分情况 6 2.4 核函数的选择 7 第 3 章SVM多参数模型选择 . 93.1
12、 多宽度高斯核 . 93.2 前人及相关的工作 10 3.3 多参数模型选择 11 3.3.1 计算期望误差界的梯度 12 3.3.2算法实现的一些观点 14 3.3.3 实验 14 3.4 本章小结 . 17 第 4 章基于遗传算法的两阶段模型选择 184.1 遗传算法 184.2 遗传算法应用于核参数选择 20 4.3 SVM的形式化 224.4 K DG (X, Y)核的正定性证明 22 4.5 基于遗传算法的两阶段模型选择的具体实现 25 4.6 实验 . 26 4.7 本章小结 . 28 参考文献 31 哈尔滨工业大学硕士学位论文原创性声明 36 致 谢 371哈尔滨工业大学工学硕士
13、学位论文第1章 绪论1.1 课题背景本课题属于计算机科学中机器学习领域的面向应用的理论研究。支持向量机( Support Vector Machine ,简称 SVM)是 Vapnik 及其合作 者发明，在 1992 年计算学习理论的会议上介绍进入机器学习领域，之后受 到了广泛的关注。在 20 世纪 90 年代中后期得到了全面深入的发展，现在已 经成为机器学习和数据挖掘领域的标准工具。 支持向量机是机器学习领域若干标准技术的集大成者。他继承了最大间 隔超平面、Mercer 核、吐二次规划、稀疏解和松弛变量等多项技术。在若 干挑战性个应用中，获得了目前为止最好的性能。在美国科学杂志上，支持 向量
14、机以及和学习方法被认为是“机器学习领域非常流行的方法和成功的例 子，并是一个十分令人瞩目的发展方向”。支 持 向 量 机 是 近 年 来 机 器 学 习 研 究 的 一 项 重 大 成 果 . 根 据 Vapnik 而要求分类线对所有样本正确分类,就是要 求其满足:yi(wxi)+b10,(i=1,2,n) (2-2) 因此,满足上述条件且使w 2最小的分类面就是最优分类面。这两类 样本中离分类面最近的点且平行于最优分类面的超平面上的训练样本就是 使式(2-2)中等号成立的那些样本,他们叫做支持向量(Support Vectors)。 根据上面的讨论,最优分类面问题可以表示成如下的约束优化问题
15、,即在式 (2-2)的约束下,求函数:(w)=1 2w 2=12(ww)(2-3)的最小值。这是一个二次规划问题,可定义以下的拉格朗日函数:L(w,b,a)=1 2(ww)ni1i i i(2-4)其中:ai0 为Lagrange系数。求式(2-3)的极小值就是对w和b求拉氏函数的极 小值。求L对w和b的偏微分，并令其等于 0,可转化为对偶问题:5a y =0,a 0,i=1,2,n之下对a 求式(2-5)的最大值:f(x)=sgn(w x)+b =sgn a哈尔滨工业大学工学硕士学位论文在约束条件ni1i i i iW(a)=ni1ai -12ni , jaiajyiyj(xi.xj)(2-
16、5)由 KhnTucker 定理可知,最优解满足: yi(wx+b)-1=0i (2-6)显然,只有支持向量的系数ai不为 0,即只有支持向量影响最终的划分结 果。于是w可表示为:w=SurpportVectorsaiyixi(2-7)即最优分类面的权系数向量是训练样本向量的线性组合。若ai *为最优解,求解上述问题后得到的最优分类函数是:* *ni1i*y i(xix)+b*(2-8)其中:sgn()为符号函数,b*是分类的阈值,可以由任意一个支持向量用 式(2-7)求得,或通过两类中任意一对支持向量取中值求得。对于给定的未知 样本x,只需计算sgn(wx+b),即可判定x所属的分类。2.3 线性不可分情况对于线性不可分的样本,希望使误分类的点数最小,为此在式(2-2)中引 入松弛变量 i0,即：yi(wxi)+b-1+
