(计算机应用技术专业论文)支持向量机参数选择的组合方法.pdf_第1页
(计算机应用技术专业论文)支持向量机参数选择的组合方法.pdf_第2页
(计算机应用技术专业论文)支持向量机参数选择的组合方法.pdf_第3页
(计算机应用技术专业论文)支持向量机参数选择的组合方法.pdf_第4页
(计算机应用技术专业论文)支持向量机参数选择的组合方法.pdf_第5页
已阅读5页,还剩38页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

中文摘要 支持向量机的参数选择直接决定着支持向量机的训练效率和应用效果,是 支持向量机模型选择研究的重要问题。现有的支持向量机参数选择方法采用嵌 套的两层循环优化过程,计算过程中,首先训练分类器,然后更新参数。这类方 法存在迭代次数多、选择效果差等问题。 针对支持向量机参数选择存在的这一问题,提出并实现了参数选择的组合 方法,具体工作包括: 1 提出了同时调节参数和分类器的组合优化框架。该框架应用启发式搜索方 法搜索参数空间,并在同一迭代过程中调节分类器,实现了参数与分类器 的组合优化。 2 推导出一个新的半御间隔界。该界是统计学习理论中的半径间隔界的一 个近似,可在保证学习精度的前提下有效地提高计算效率。 3 给出了初始参数的选择方法。从理论上分析了核函数参数在两种极端情形 下的渐近性质,讨论了参数选择原则,并给出了参数初始点选择方法。 4 设计并实现了组合参数调节算法。该算法应用新推导的半径间隔界,结合 了序贯无约束最小化和变尺度法两个优化算法,能有效地给出参数的最优 解。, 5 开展了实验研究。在u c i 数据库h e a r t ,d i a b e t e s ,a 2 a ,聊口和s t a t l o g 数 据库g e r m a n n u m e r 五个标准数据集上,测试并比较了所提出的组合参数 调节方法与传统的交叉验证、梯度下降等方法的性能。实验结果充分显示 了组合方法的有效性。 关键词:支持向量机;模型选择;半径间隔界;参数调节 a b s t r a c t a u t o m a t i ct u n i n go f ( h y p e r ) p a r a m e t e r si sa l le s s e n t i a li n g r e d i e n ta n di m p o r t a n t p r o c e s sf o rl e a r n i n ga n da p p l y i n gs u p p o r tv e c t o rm a c h i n e s ( s v m ) t h ee x i s t i n gt u n i n gm e t h o d sc h o o s e ( h y p e r ) p a r a m e t e r sa n dc l a s s i f i e rs e p a r a t e l yi nd i f f e r e n ti t e r a t i o n p r o c e s s e s ,a n du s u a l l ys e a r c he x h a u s t i v e l yi np a r a m e t e rs p a c e s i nt h i st h e s i s ,w e p r o p o s ea n di m p l e m e n tan e wt u n i n ga l g o r i t h mt h a tc h o o s e s ( h y p e r ) p a r a m e t e r sa n d c l a s s i f i e rf o rs v ms i m u l t a n e o u s l ya n ds e a r c ht h ep a r a m e t e rs p a c ee t f i c i e n t l yw i t ha d e l i b e r a t ei n i t i a l i z a t i o no fap a i ro fs t a r t i n gp o i n t s f i m tw ed e r i v ea na p p r o x i m a t eb u t e f f e c t i v er a d i u sm a r g i nb o u n df o rs o f tm a r g i ns v m t h e nw ec o m b i n em u l t i p a r a m e t e r so fs v mi n t oo n ev e c t o r , c o n v e r t i n gt h et w os e p a r a t et u n i n gp r o c e s s e si m oo n e o p t i m i z a t i o np r o b l e m f u r t h e rw ed i s c u s s et h ei m p l e m e n t a t i o ni s s u ea b o u tt h en e w t u n i n ga l g o r i t h m ,a n dt h a to fc h o o s i n gi n i t i a lp o i n t sf o ri t e r a t i o n f i n a l l yw ec o r n p a r et h en e wt u n i n ga l g o r i t h mw i t ht h eg r a d i e n tb a s e dm e t h o da n dc r o s sv a l i d a t i o no n f i v eb e n c h m a r kd a t as e t s t h ee x p e r i m e n m lr e s u l t sd e m o n s t r a t et h a tt h en e wt u n i n g a l g o r i t h mi se f f e c t i v e ,a n du s u a l l yo u t p e r f o r m st h o s ec l a s s i c a lt u n i n ga l g o r i t h m s k e yw o r d s :s u p p o r tv e c t o rm a c h i n e s ;m o d e ls e l e c t i o n ;r a d i u s m a r g i nb o u n d ;t u n i n ga l g o r i t h m 插图索弓 插图索引 图2 1支持向量机3 图3 1s v m 参数模型选择归类- 1 5 图3 23 个样本以2 3 = 8 种方式分开1 7 图4 1新决策量的归类2 l 图4 2 分类精度与l o g 仃的关系2 6 图5 - 1新半径间隔界等值线2 9 图5 2迭代步数对比3 0 图5 3g e r m a n 数据分布形态3 3 3 5 表格索弓 表格索引 表3 1现有s v m 参数调节方法分类2 0 表5 1分类精度比较3 0 表5 2传统s v m 模型选择问题3 0 表5 3s i m u l t u n i n g s v m 模型选择问题3 1 表5 - 4计算复杂性比较。3 2 表5 5近似函数集分类3 2 3 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表 或撰写过的研究成果,也不包含为获得墨鲞盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名:铱签字日期:司年乡月心日 学位论文版权使用授权书 本学位论文作者完全了解苤洼盘堂有关保留、使用学位论文的规定。 特授权墨注盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索,并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名: 签字日期: 汐d 年 铜 叶日 导师签名: 签字日期: 与鸳钟 1 年石月旷日 第一章绪论 第一章绪论 本章概述论文的研究背景和主要工作。 1 1 工作背景 支持向量机是一种新的学习机器,是在v a p n i k 等人建立的以解决有限样本 机器学习为目标的统计学习理论基础上发展起来的。支持向量机以结构风险最 小化为基础,根据有限样本信息在模型复杂性与学习能力之间寻求最佳折衷。由 于在解决小样本、非线性及高维机器学习问题中表现出许多特有的优势,支持 向量机已逐渐成为机器学习领域的研究热点。人们经常拿支持向量机与其他机 器学习方法,如人工神经网络,作对比。一般认为支持向量机的最大优点是对问 题模块化的解决方案,即把问题划分成核函数与分类器两个不同的模块,但这种 优势只有在核函数及其参数确定的前提下才有意义。 参数选择直接决定着支持向量机的训练效率和应用效果。c h e r k a s s k y 认 为:“支持向量机模型的质量依赖于参数的设置,如何选择参数是应用支持向量 机的主要i 口- j 题。 1 】c h a p e l l e 和v a p n i k 也指出:“学习算法决定于参数,参数控制 着假设空间的规模以及假设空间的搜索方式。 圆因此,参数选择是支持向量机 模型选择的关键【3 - 5 】。 主要的参数选择策略包括格搜索,交叉验证等【6 ,7 】。c h a p e l l e 和v a p n i k 提出 的基于梯度下降的搜索方法能大幅度降低迭代次数 2 】,k e e r t h i 详细讨论了这种 方法的实现问题 8 】。国内学者也做了大量的研究工作【9 - l o ,如基于凸包估计的核 参数选择方法【l l 】,并对支持向量机参数选择的决策量作了较全面的概述【1 2 】。 现有支持向量机参数选择方法的一般框架可概括为: 1 初始化参数, 2 优化某个决策量, 3 更新参数, 4 返回步骤2 。 第一章绪论 该框架是两层嵌套的优化问题,将参数和分类器分开调节,无论步骤3 以什 么样的方式更新参数,步骤2 的决策量都必须在参数更新前单独计算,暴露出迭 代速度慢、运算量大等不足。 1 2 本文工作 针对以上问题,本文提出了一种组合参数调节方法,该方法包含两个核心部 分: 新的决策量:近似的半径间隔界 新的调节算法:s i m u l t u n i n g 新决策量是统计学习理论中的半径间隔界的一个近似,与现有决策量相比, 能在保证学习精度的前提下有效提高计算效率。 依据新提出的决策量设计了s i m u l t u n i n g 调节算法,算法框架可概括为: 1 初始化参数, 2 计算目标函数值, 3 更新参数, 4 返回步骤2 。 与已有方法不同,s i m u l t u n i n g 采用组合调节的思想,只包含单层优化问题, 能有效地提高运算速度和选择效果。 2 第二章支持向量机 第二章支持向量机 本章简介支持向量机和核函数的基本概念。 2 1 线性s v m 假设有个训练数据点 ( 工1 ,y 1 ) ,( x 2 ,耽) ,似,胁) ) ,其中x f 彤,弘 土1 ) ,如图2 - 1 所示,s v m 算法得到分类f 日 n l 大的超平面f ( x ) = s g n ( w x 一6 ) , 即得到分类面h :w x b = 0 ,同时还有两个与之平行且距离相等的超平面 h 1 :w x b = + l ,飓: w x b = 一1 ,约束条件为凰,总间没有样本点。 其它形式的分类面日7 及相应的纠和目可以归一化为上述表示形式。假 设叫:a x b l = 0 ,琏:a x b 2 = 0 ,令b 7 = 组,6 = b 1 一b 7 ,则有b 1 :6 7 + 6 ,b 2 = b 7 6 ,h 17 和h 2 7 可重写如下: q :口工一( 6 7 + 6 ) = 0 , q :口x - - ( b 7 6 ) = 0 。 图2 - 1 支持向量机 3 x 一6 = + 1 b = 0 - 1 也即 叫:口x b 7 = 6 , 型:口x - b 7 = 一6 。 因为b l b 2 ,所以6 0 ,两边同除以6 ,得到 彳口。x 一万。+ 1 16 7 否口j 否。- 1 再令w = 吉口,6 = 等就得到了上面的标准形式。 处在日l ,仍上的样本即为支持向量,这些样本确定了分类面。硒,地上的点 到分类面的距离为与铲= 由,局与飓之间的距离为丽2 。由统计学习理论 可知r 尺唧+ 毒,为包含所有样本点的超球半径,为分类间隔( 此处为m 2 ) 。因此,要想使经验风险r 唧更接近实际风险r ,必须使南最大,也即令1 1 w l i 最小,同时约束条件为、 i i y i ( w x i b ) 1 。 综上,s v m 可归结为下面的优化问题 r a i n 妻y w t w , 百乞 w , 。w , b ( 2 一i ) s t y i ( w 柳一b ) q - 1 。 这是一个凸二次规划( q p ) 问题,未知量是w 和b 。引入l a g r a n g e 乘子 2 1 ,观,蛳0 ,建立l a g r a n g e 方程 l ( w , b ,a ) = 毒w t w zt 2 i y i ( w x 一6 ) + 嘶, 分别对w 和6 求偏导数,并使之为0 , 丝:o ,:一2u 擎:。, a 6 4 第二章支持向量机 得到 w = y i x i ,嘞= 0 , f = lf = l 代入到l ( w , b ,a ) 中,得到原问题的对偶问题 lo=嘶一言eotiotjyiyjxfxjv , 1 f = i 。l , j 其中不包含未知量w 和b ,只包含l a g r a n g e 乘子嘶。 2 2 软间隔s v m 标准s v m 不允许凰,趣间有样本存在。当局,飓允许噪声存在时,引入松 弛变量台0 ,有 y i ( w x i b ) 1 一考f ,岛0 。 同时在目标函数中增加一个惩罚项,得 n m i n i l w 7 w + c 昏, 。 f = 1 s t y i ( w x i b ) + 善f 一1 】0 , 考f 0 。 引入两个l a g r a n g e 乘子,口,届0 ,建立拉氏方程 l ( w , b ,a ,1 3 ) = 毒w r w + c 辱一q f 【( w x i - b ) + 考i 一1 】一卢f f = lf = 1f = i 1 n = 吉w r w + ( c 一嘶一肪) 考f 一( 唧 ) w 一( 唧f ) 6 + 嘶, 。 f = 1f = l i = 1i = 1 分别对w , b ,毒f 求偏导并使之为0 ,得到 w a z y i f = 1 g t i y i x i , f = 1 0 , c 一嘶一廖= 0 , 5 第二章支持向量机 又a ,j i b 0 ,所以0 a ,1 3 c , 优化问题变为 l ( w , b ,台;仅,卢) = 一丢w r w + n 嘶 1 。 f = l 2 ,兰嘶一三否哕炒巧。 :n 一:1 m i n l d o 自 o t j y i y j x i 巧,= 一:乏: 石, f 2 1 巧 s t 0 嘶 0 ,由式2 - 3 知磊= 0 ,得 y i ( w t x i b ) 一1 0 , 2 如果0 啦 0 ,由式2 - 3 知考f = 0 ,得 y i ( w t x i b ) 一i = 0 , 6 ( 2 2 ) ( 2 - 3 ) 一釜三童塞量旦量垫 3 如果嘶= c ,则岛= c 一= 0 ,由式2 - 3 知鲁0 ,得 进一步变形, 其中,月= aw t x f y f ,- 则有 令 有 y i ( w r z i b ) 一1 0 。 y i ( w r x i b ) 一1 y i ( w t x i - b ) 一拜 - - y i ( w t x i - - y i - - b ) = y i 一b ) , 嘶= 0 兮y i 一b ) 0 , 0 嘶 c = 争y i 一b ) = 0 , 啦= c 兮y f ( 巧一b ) 0 。 i o 三 f :0 a i 珂,在高维特征空间,对偶l a g r a n g e 函数变为 。 n1 l d = 一寺嘶q 此 中 f ) 中( 巧) , f 5 1 。t , j 再令中( 王f ) o ( x j ) = k ( x i ,x j ) ,得到 n 、1 幻= 啦一言x o t j y i y j k ( x i ,x j ) 。 定义2 1 :核是一个函数k ,对所有x ,z x ,满足:k ( x ,z ) = ,从 中到x 内积空间f 的映射。 常见的核函数有以下几种: 1 线性核:x y , 2 多项式核:k ( x , y ) = y + 1 ) p , 3 高斯核:k ( x ,) ,) = e - i i x - y l l 。2 旷, 4 s i g m o i d 核:k ( x ,y ) = m h ( r x 少一6 ) 。 这几类核函数可应用于大部分实际问题,并能获得较好的分类效果。 核函数的构造目前尚没有通用的理论可遵循,从不同角度出发可以得到不 同的核函数的学习和构造方法,如通过黎曼几何分析【13 】,通过元学习啊,通过 模型选择 5 】,等等。 核函数需要具备两个基本性质: 1 对称性:x ( x ,y ) = k ( y ,x ) , 2 c a u c h y - s c h w a r z 不等式:k ( x ,y ) 2 k ( x ,x ) k y ) 。 这些条件只是必要条件,不是充分条件。设输入空间,x = x l ,x 2 ,x n ,k ( x ,z ) 是k 上的对称函数,考虑矩阵k = k ( x i ,x j ) 7 , j :1 ,因为k 是对称的,则必存在一 个正交矩阵y 使得k = v a v t ,其中,人是包含k 的特征值九的对角矩阵,特征 值九对应特征向量v t = ( f ) 冬1 ,即人的列。假定所有特征值非负,考虑特征映像 8 第二章支持向量机 m x ih ( 佤f ) 冬1e r 刀,则有( 中) ,中( 巧) ) = 九v f f = ( v a v 7 ) = k ( x i ,巧) 。 也就是说k 仅,z ) 是真正对应于特征映像。的核函数。k 的特征值非负这 个条件是必要的,否则设z s 陀i n f + ) = 0 。 月_ r f , 机器学习的目的是最小化期望错误,由于数据的分布p ( z ) 未知,大多数机 器学习算法围绕经验错误最小化的原则来构造,以期达到算法泛化性与一致性 的目的。泛化性和一致性的定义要求刀_ 一,而实际训练样本集的大小是有限 的,往往会出现过拟合或欠拟合的现象,即由经验错误最小化得到的居不一定 能在未知数据的预测中表现最好。比如,考虑厂l ,厂2 h ,假设真实函数为广, 用i 卅来表示函数的复杂度,假设i 厂1 i i 广i i 尸i ,则一个基于经验错误最小 的学习算法工更易把f s = 厂1 作为输出,因为复杂度高的函数有更强的拟合能 力,厂1 能更好地拟合训练集s 。但实际上尸要比厂1 更接近真实函数广,却被经 验最小化原则排除了。所以在刀有限的前提下,需要对目标函数的复杂度进行控 制,一般认为对于给定训练集si s i = 以,都存在一个复杂度最佳的目标函数。综 上可以得到如下结论: 经验风险( 或者说训练误差) 对学习机器的性能有一定的影响,但不起决 定作用,执行经验风险最小化原则( 即最小化训练误差) ,并不总能提高学 习机器的推广能力。 1 2 第三章支持向量机参数选择 复杂度高的学习机器,往往具有较低的经验风险,经验风险最小化原则的 结果,将使学习机器变得越来越复杂( 比如神经网络的隐层节点数增多) 。 学习机器的复杂度对其性能有较大影响,推广性能好的学习机器应该具有 与实际面对的问题相对应的复杂度。 因此,如何根据实际问题,在学习机器的经验风险和模式复杂度之间取得合理的 折中,从而使学习机器具有更高的推广能力就显得至关重要,模型选择的工作就 是研究怎样对复杂度进行控制。 模型选择的问题可分为两大类: 参数的 非参数的 这两类问题的区别在于,参数模型选择问题认为数据是由具有特定参数族 的分布函数生成的,而非参数模型选择问题相反,不假定某个特定分布函数族。 参数问题还可继续分为: 贝叶斯过程 非贝叶斯过程 贝叶斯过程把模型选择放入决策理论框架中,并引入关于模型参数的先验 知识。这类方法把模型选择看成在给定的数据样本和相关参数信息的条件下,寻 找具有最大后验概率的模型。在给定的样本d 下。某一模型m 的后验概率与m 的先验概率和似然函数的乘积成比例,因而模型选择问题可以表示成下面的优 化问题 a r g m a x p ( m l d ) = a r g m a x p ( d i m ) 尸( , m m 贝叶斯方法下的模型选择通过选取适当的模型先验分布尸( m ,可以将人类专家 的知识和给定的样本数据中提供的信息结合在一起。在没有任何先验信息的情 况下,可以采用贝叶斯假设将爿m 看作均匀分布,模型选择问题可以进一步化 简为似然函数尸l m 的优化问题 a r g m a x p ( m 1 d ) = a r g m a x p ( d i , mm 1 3 第三章支持向量机参数选择 为了比较不同模型的优劣,通常采用贝叶斯因子b 1 2 ( b a y e s i a nf a c t o r ) , ,一p ( d i 尬) b1 , 22 2p ( d i m 2 ) 非贝叶斯过程又可分为两类: 决策的 非决策的 决策的模型选择同样把模型选择放入决策理论框架,但不引入参数的先验 知识,决策是基于某种损失函数或某种差别度量而不是贝叶斯风险来作出,所采 用的差别度量称为标准。 按上面的分类方式,s v m 中的模型选择属于参数非贝叶斯决策理论模型选 择,见图3 - 1 ,采用的决策量主要有两种: 预测风险的某个估计量:标准 训练集收敛率 预测风险的某个上界 横向从参数选择理论来看,有三大类重要的参数选择方法,分别是: 1 解析方法一标准_ 渐进一致理论 2 取样方法一收敛率_ 收敛率理论 3 统计学习方法_ 界一渐进一致理论 下面分别予以介绍,进一步的讨论参见 2 l 】。 3 2 解析法 如上所述,机器学习的目的是最小化期望错误,而不是经验错误,需要对经 验错误进行修正来估计期望错误。解析方法就是基于这样的思路,用一个偏置 函数对经验错误进行修正,这个偏执函数同时考虑函数的复杂度以及样本规模 来达到模型选择的目的。比如在线性回归模型中,解析法的选择标准或者说对 期望错误的估计采用这样的一般形式 e s t i m a t o r 一一( 等) 三茎h ) 2 , p - ) 1 4 第三章支持向量机参数选择 图3 - ls v m 参数模型选择归类 其中d 为模型复杂度,g ( ) 为d n 上的单调增函数,一般称g ( ) 为惩罚因数,正 比于d 使复杂模型的误差平方更加显著化。g ( ) 有以下常见的形式 f i n a lp r e d i c t i o ne r r o r ( f p e ) 2 2 】 g c o ) = ( 1 + p ) ( 1 - p ) , ( 3 - 2 ) s c h w a r t z sc r i t e r i a ( s c ) 2 3 】 g ( p ,r ) :1 + 挈p ( 1 一p - - l , ( 3 3 ) g e n e r a l i z e dc r o s s v a l i d a t i o n ( g c v ) 2 4 】 g ( p ) = ( 1 一p ) 一,( 3 - 4 ) s h i b a t a sm o d e ls e l e c t o rf s m s ) 2 5 】 g p ) = 1 + 2 p 。 ( 3 - 5 ) 这类模型选择方法均假设噪声独立同分布,且l i mg ( p ) = l 式,所以 3 2 ,3 3 ,3 - 4 ,3 5 都是对期望错误的渐进无偏估计。当训练集规模较大时,这 类方法能表现出很好的控制效果,且各式得到的学习结果很相近。而当训练集 规模较小且噪声独立同分布的假设不满足时( 实际问题大多如此) ,解析法得到 学习结果大相径庭,且往往都不是最佳结果 2 6 1 。 1 5 第三章支持向量机参数选择 解析法模型选择的主要不足在于这类方法需要对模型的复杂度进行表示, 而实际情况中除了线性估计可以用自由参数的个数表示模型复杂度之外,对模 型复杂度很难有一般化的定义,即使有定义也很难有量化的表示。目前一种比 较通用和广泛认可的复杂度表示是由v a p n i k 等人出的函数的v c 维【1 7 , 2 7 , 2 8 】,后 面章节将详细介绍v c 维的概念。 3 3 取样法 取样模型选择方法把训练集s 看作真实世界的全体数据乳的“缩影 ,并 在s 中生成子训练集s 和测试集,这样学习并测试一个模型所需要的统计量均 已具备,可以通过测试集来估计一个模型的期望错误。取样法是基于这样的假 设,即训练集s 的数据分布与岛一致,在此假设下且训练集较大时s 与s 的关 系可以泛化成s 与& 的关系。 。 取样法的基本思路是将训练数据s 分割为两部分:训练集s ,验证集 s ,s v = s s 。s 用于训练,& 用来估计模型的期望错误。s 的划分方法有三类: 简单验证( s i m p l ev a l i d a t i o n ) :将训练集s 随机划为两部分,7 0 用于训 练,3 0 用于验证。 剩余1 交叉验证( l e a v e o l l e o u tc r o s s v a l i d a t i o n ) :从s 中选择一个样本z f 用于测试,用s s = s z f 作为训练集;从f = l 到i = i sj 重复这个过程,计 算平均错误,得到期望错误的估计。 k 倍交叉验证( 尼f o l dc r o s s v a l i d a t i o n ) :k 倍交叉验证源于剩余l 交叉验证 的思想,区别是此方法将s 等分成k 个子集,每次用一个子集作验证集, 其余的样本用于训练,重复这个过程k 次,取平均错误来估计期望错误。 与解析模型选择相比,取样模型选择不依赖于拟合函数本身的性质,绕过 了对模型复杂度表示这一难题,因此取样模型选择方法不仅可以应用于线性估 计,也可以应用于非线性估计等更广泛的领域,比如多层感知机等。取样模型选 择方法的最大不足是计算代价一般情况下都比较高,在样本规模较大时,这类方 法能取得很好的选择效果,当样本规模较小时,由于各个样本间的差距,模型选 择的效果也会相应降低。 1 6 第三章支持向量机参数选择 父。 3 4 统计学习法 , , l o 、0形 i 1 统计学习法是以统计学习理论【2 8 】为基础的,上述两类方法在样本集较小时 都不能实现很好的控制效果,统计学习理论为研究小样本下的模型选择问题提 供了坚实的理论基础。统计是机器学习的基础,研究当样本无穷多时的统计规 律,即渐进特性,并利用渐进特性来近似样本有限时的情况,但是样本无穷多 时的特性在样本有限时经常得不到体现,例如某个神经网络,如果训练样本足 够多则性能表现良好,但当训练样本有限时,虽然在学习过程中能很好的收敛, 但预测能力却可能很差。统计学习理论是专门研究有限样本下统计学习规律的 理论,建立了一个一般化且非常有效的模型复杂度控制框架,称为结构风险最 小( s t r u c t u r er i s km i n i m u m ) 。统计学习理论中,模型的复杂度用v c 一维来描述。 要定义v c 维,首先定义打散( s h a t t e r ) 的概念,如果h 个样本能被一个指示 函数集h k = ( 工,w ) ,w q 七 以所有2 可能的方式分开,则称这个h 个样本被 打散。比如规模为3 的样本被打散是指这3 个样本能够被协按以下2 3 = 8 种方式分开,见图3 2 。 定义3 1 :指示函数集凤的v c 维是指,能被珥打散的样本向量的最大数目 。 如果一个凰的v c 维是,则一定存在一个缸大小的样本集能够被峨打 散,同时一定不存在一个规模h 七的样本集能够被风打散。对于实值函数集 雕,w ) ) ,假设a f ( x ,w ) b ,可以引入阈值变量p s 卢b ) 将实值函数转 化为指示函数 一 ,( 工w 卢) = i ( f ( x ,w ) 一卢) , 1 7 。i 第三章支持向量机参数选择 实值函数集的v c 维就等于参数为w p 的指示函数集的v c 维。 v ,n 如果| ,个向量的集合能被凰打散,则函数集风的v c 维就是 h k = 一。函数集的v c 维是存在性定义,假设,函数集风的v c 维是,并不意 味着v x l ,x 2 ,x s ( s 0 。 其中,考f 表示训练误差,c 称为惩罚因子。令三= ( g f ) 7 ,p f 而) 7 ,自是长度 为z 且第i 个元素为1 的o 向量,长度为这样软间隔s v m 可以变形为标准s v m 的形式 曲妒讥 s t y i ( w r 磊+ 6 ) 1 。 其中,访= ( w t ,倔考) r 。由对偶问题的解可以得到 仍= a i y i t l ) ( z i ) , 再令,:21 = = ,霞可以用k 表示为 10 :i j g ( x i ,即) = k + s c 。 对偶为题变为 m i n i - , d :喜a j y 辨 + 芦i ) 一啦, u 。 i ( 4 1 ) 乩t a t y i = 0 ,嘶0 。 s v m 以统计学习理论 2 8 为基础,统计学习给出的泛化界为r 21 1 w l l 2 ,其中,r 为 包含样本点的超球半径。按照b u r g c s 3 2 】给出的公式 r = 廖助k g f ,巧) 一2 卢 f ,即) + k ,柳) 。 ( 4 2 ) 与分类间隔一样,r 也由核函数决定,有如下定理。 n 吾 “ 第四章组合方法 定理4 1 :泛化界是仃的连续函数【3 3 】。 因为式4 2 需要复杂的矩阵运算,在应用当中并不实用,需要找到r 2 的一 个更易计算的表达形式。包含样本点的超球的直径受样本中距离最远的两个样 本点影响,故可令d 表示超球直径,有 d 2 = 忡k ) 一k ) 1 1 2 且 伽,g ) = a r g 1 n a xl i g r ) 一( 巧) 旷。 f f ,e l l a r g m i ni i x i - 工:1 1 2 :, 如刀卜濮甜g m 店m :7 i x i 俨:。 li 一圳2 :。 l f ) f ,- ,e l 则r 2 = ( r ( o ) 一k k ,x q ) ) 1 2 。如果使用g a u s s 核,则有 尺2 :1 - k _ ( x p , x q ) 。( 4 - 3 ) 尺2 只由核函数决定,且不需要知道特征映射:西:r _ r 所,m 刀。显然,式4 - 3 比4 - 2 更加易计算,同时p ,q 常常来自不同的类别,计算复杂性一般情况下会减 半。 这样得到的d 和月2 的表达形式是不精确的,是对计算复杂性与训练精度折衷做的选择。精确计算r 2 要根据4 2 。第5 章将通过实验讨论由于不精确计算导致的误差。 第四章组合方法 在软间隔优化中,k = k + i c ,则 拈掣+ 壶, 等价于 辰2 = r 2 + 苑1 ,( 4 - 4 ) 半径间隔界变为 ( 1 一砀+ 训1 形1 1 2 。( 4 - 5 ) 与未变形情况相比,式4 - 5 的形式更易计算。s h s l k o p f 在【3 4 】中讨论了核函 数与半径间隔界的关系,c h u n g 在【3 5 证明了半径间隔界的一些性质。 从式4 5 可得 m i n = k 2 如, s t , a i y i = 0 ,嘶0 ,c 0 ,仃2 0 。 合并c ,仃2 ,和a 于一个向量x = ( c ,仃2 ,a7 ) r ,再构造向量p = ( o ,0 ,y r ) 7 ,其 中y = l 一,m ) 。,新的参数调节模型如下 。 m i n 肛,= ( 一勘+ 丢) 陲嘶咿僻+ 石1 ,一列, s t x 7 ,= 0 ,x 0 。 新调节模型基于近似的半径间隔界4 5 ,同时考虑了超球半径和分类间隔, 只包含一个优化过程,可同时得到最优分类面和参数向量。 4 3 初始点选择 仍以高斯核k g f ,即) 亍e x p ( 一i i x - x j l l 2 2 0 r 2 ) 作为讨论对象, 定理4 3 :当仃_ 0 时,所有样本点都成为支持向量。 2 4 第四章组合方法 躲k ( 即) = 1 x i = x j , 假设训练集规模为,其中类别号 y i = + 1 或m = 一1 的样本数分别为,+ 和,一。 再假设l a g r a n g e 乘子九是 九= 三二i 羔三二: 。 m a x 2 l 一t ,2 l + l ,结论成立。 2 5 ( 4 - 7 ) ( 4 8 ) 口 第四章组合方法 定理4 4 :当仃_ ,s v m 将所有样本归为同一类。 证明:当仃_ ,l i mk ( x i ,x ,) = 1 ,决策函数为 f r 。7 f ( x )l t i y i k ( x i ,x ) + 6 l = l , 枷f + b = b 。 图4 - 2 分类精度与l o g 的关系 口 因此一个恰当的仃值既不能太大,又不能过于小,分类精度与l o g a 的关系见图 4 2 。能明显的看到当仃0 训练精度接近1 0 0 ,而当仃一即l l 时,测试精 度趋近于常数g : , g : + ,:6 0 , i ,卜1 7 :b ,1 户 产 0 ,_ 0 ,去一一。 按照上面方法式4 - 6 变形为 曲啦仆(-一砀+啡否嘶缈辨+丢)一列件9,l + ;,( x 7 p ) 2 + 产;面1 a 令w ,产) 为式4 - 9 的梯度,有 v j ( x * = ( 嘉,豢,瓦o j ,豢) 2 ,、 券= 士( 撕2 手砰一 丢啦咿叻 十丢) 一手嘶) + , 豢= 手万1 一锝, , 等= 存1 一x q l l 2 砀( x 。,o 白a j y i y j ( k + 丢) 一手嘶) + 2 r 2 z一2+,o句ayiyjllxi x j l lk z d 。 老= 2 詹2 ( ;手嗍僻+ 丢) 一1 ) + 譬+ 。 2 7 第四章组合方法 其中詹2 = 上笋+ 去( 见式4 - 4 ) 。 令py gx k = x k t , 声) 丁第七次搜索方向,又令 那么 矿= w 畔1 ) 一w 渺) , z k = h k 醇, 卢七= l ( 彬) 7 矿, 七= 1 ( 砂) 7 矿, b k = p k 蚁慷哈x 垤、l , 萨= u 七砂( 砂) 1 , h k + 1 :h k + 萨一c k :h k + a n k l p = 一日七w ) 。 式4 - 9 的解,就是式4 - 6 的解 3 6 】。c h a p e l l e 等人给出了计算梯度与搜索方向 的重要结论 2 】。 有了初始点和搜索策略,式4 - 9 的解法见算法1 。 算法1 :s i m u l t u n i n g 1 :初始化x , o r n , 0 ,俨= 1 ,k = 0 。 2 :d ,q ) = a r g m a xi i x i - x j l l 2 。 0 ,j i ,j l 3 :w h i l e 矿= w 七) d o 电p k = 一h k 寸,九k = a r g m i n j q f k 七九n ,x l k 斗1 = x 咄+ 九p k o a 5 :i f k = 刀t h e n 6 :x , o :行。 7 :e l s e 8 : 计算扩1 ,型一,萨,萨,胪1 = + 胪一c k ,k = 尼+ l 。 9 :e n di f 1 0 :e n dw h i l e 1 1 :r e t u r nf = x 住, 2 8 第五章实验分析 第五章实验分析 本章实验研究s i m u l t u n i t l g 算法的收敛性、迭代次数和分类精度,并与梯度 下降和交叉验证方法进行对比。 5 1 实验设计 实验选取五个标准数据集,分别是u c i 数据库h e a r t ,d i a b e t e s ,a 2 a ,s t a t l o g 数据库g e r m a n n u m e r ,以及w l a 。首先对算法1 的收敛性进行了测试,图5 1 显示了算法1 的寻优路径。由图可知,算法l 是沿着等值线的脊线搜索最优值, 保证了算法的收敛性。接着对比了算法1 与5 一倍交叉验证在迭代效率上的优劣, 如图5 2 所示进行了5 次实验,其中4 次算法1 的迭代步数均少于交叉验证。最后 把算法1 的训练效果与交叉验证、梯度下降方法作了详细的对比,包括分类精 度、目标函数值、最优参数值等等,算法1 在5 个实验中均表现出了较好的训练 效果,见表5 - 1 。 图5 - 1 新半径间隔界等值线,其中用+ 表示( c ,仃) 的寻优路径 第五章实验分析 图5 - 2 迭代步数对比,s t - s i m u l t u n i n g ,5 - f o l d :5 倍交叉验证 表5 - 1 s i m u l t u n i n g ( s t ) ,梯度下降( g r a d ) 和交叉验证( 5 f o l d ) 的训练效果比较。 = 样本维数,= 样本集规模,t t e s t = 测试集规模,l o g c 和仃是由s i m u l t u n i n g 选择得到的 最优值。最佳测试精度由黑体标出 5 2 结果分析 表5 2 传统s v m 模型选择问题 第五章实验分析 表5 2 是对传统的s v m 模型选择问题的界定。假设目标分类器为 , 八x ) = 册( e 五t i y i k ( x i ,z ) + 6 ) , f = l 丘通过求解肘的过程得到,的值受晚,允影响,但由训练数据本身决定 的。s i m u l t u n i n g 方法与传统方法的第一个不同之处在于将a 与瞰,如同时视 作s v m 的参数,并一起作为模型选择的对象,为了统一把a 表示为如,见表 5 3 。参数的不同也决定了近似函数集的不同( 用s t - s v m 表示新的近似函数集 表5 - 3 s i m u l t u n i n g s v m 模型选择问题 厂( 0 ,x k ) ) 另外本文也给出了一个求解6 的算法,即s i m u l t u n i n g 算法,用来验证 s t - s v m 近似函数集的有效性。综上,得到 s v m 一 6 : 反,晚) 一h = r 2 m 2 交叉验证或基于梯度 上l上 s t s v m 叫6 : 晚,良,允 - 一h = r 2 m 2 s i m u l t u n i n g 虽然需要调节的参数看似增加了一组如,但在s v m 里是同样需要计算气, 因为如也是未知量,每调节一次参数都要先计算一次如,这里把如从在s v m 里的单独计算拿出来,把所有的未知量进行统一的参数模型选择,假设 i o a i = ,l o k i = d ,i o c l = l , 则在第i 次迭代中有表5 - 4 。 可见s t - s v m 并没有增加

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论