（计算机应用技术专业论文）基于凸包估计的svm核参数选择方法研究.pdf

摘要 支撑向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是近年来受到广泛关注 的一类学习机器，它以统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y , s l t ) 为基础，具有简洁的数学形式、标准快捷的训练方法和良好的泛化性能， 已广泛应用于模式识别、函数估计和时间序列预测等数据挖掘问题。目 前s v m 的研究热点主要有：s v m 的模型选择、快速学习算法研究等。 由于支撑向量机是一种基于核的学习方法，所以核及相关参数的选取对 泛化能力有着重要的影响，进而对支撑向量机的性能也有着重要的影响。 如何有效地进行核及相关参数的选择是支撑向量机研究领域的一个重要 问题。本文对于s v m 的核及相关参数的选择问题进行了系统的研究，主 要内容如下： ( 1 ) 对现有核选择方法进行了详细的分析和研究。 ( 2 ) 提出了基于r2 a 2 最小化估计的泛化误差界非优化估计方法。目前 大多数的核参数选择方法都是通过极小化r2 a 2 来得到最优参数值，但是 求解优化问题的计算代价相当的大，并且不能很好地体现数据的分布特 征。本文采用非优化技术，通过极小化泛化误差来优化核及相关参数， 由于直接计算最小半径和最大间隔，避免了对优化问题的直接求解，因 此可以很好地降低计算代价。并且该方法直接从样本出发，可以很好地 体现数据的分布特征，不管数据分布是否均匀都可以适用。 ( 3 ) 给出了基于凸包估计的r2 a 2 的近似表达。本文利用分类问题的 t 几何意义直接从数据集出发，按照样本与样本集重心的夹角来分割样本 集，以得到样本集的近似凸包，从而分别给出r z 和2 的近似表达，为基 于凸包估计的核选择方法提供了实现的基础。 ( 4 ) 给出了基于凸包估计的s v m 核选择的模型及实现算法。论文分 别选取了高斯核和多项式核函数作为研究对象，在人工数据集和真实数 据集上进行了测试，验证了本文所提出方法的可行性和有效性。 本文研究的内容是s v m 研究中的热点问题之一，研究结果不仅具有 重要的理论意义，而且对于实际问题具有直接的应用价值。 关键词：统计学习理论；支撑向量机；核选择；泛化误差界；凸包估计 法；分类 中图分类号：t p l 8 1 i i a b s t r a c t s u p p o r tv e c t o rm a c h i n e ( s v m ) i so n et y p eo fl e a r n i n gm a c h i n e st h a ti s p a i dw i d ea t t e n t i o ni nr e c e n ty e a r s b a s e do ns t a t i s t i c a ll e a r n i n gt h e o r y ( s l t ) ， s v mp o s s e s s e sm a n ym e r i t ss u c ha sc o n c i s em a t h e m a t i c a lf o r m ，s t a n d a r d f a s tt r a i n i n ga l g o r i t h ma n de x c e l l e n tg e n e r a l i z a t i o np e r f o r m a n c e ，s oi th a s b e e nw i d e l ya p p l i e di nd a t am i n i n gp r o b l e m ss u c ha sp a t t e r nr e c o g n i t i o n f u n c t i o ne s t i m a t i o na n dt i m es e r i e sp r e d i c t i o n ，e ta 1 a tp r e s e n t ，t h e r ea r e s o m eh o tt o p i c si ns v mr e s e a r c h e s ，f o re x a m p l e ，m o d e ls e l e c t i o n ，f a s t l e a r n i n ga l g o r i t h m s e ta 1 b e c a u s es u p p o r tv e c t o rm a c h i n ei sak i n d o f l e a r n i n gm a c h i n e sb a s e d o nk e r n e l t h ek e r n e lp a r a m e t e rs e l e c t i o nw i l l i m p a c tg r e a t l yo nt h eg e n e r a l i z a t i o na b i l i t y , a n dt h e no nt h ep e r f o r m a n c eo f s v m t h e r e f o r eh o wt os e l e c tt h ek e r n e lp a r a m e t e ri sa l li m p o r t a n ti s s u ei n t h es v mr e s e a r c h i nt h et h e s i s ，t h es e l e c t i o n so fk e r n e lf u n c t i o na n dr e l a t i v e p a r a m e t e rf o rs v ma r ei n v e s t i g a t e ds y s t e m a t i c a l l y t h em a i na c h i e v e m e n t s a r ec o n c l u d e di nt h ef o l l o w i n g ： ( 1 ) a n a l y z e st h ee x i s t i n gm e t h o d sf o rk e r n e ls e l e c t i o no fs v m ( 2 ) p r o p o s e sa nu n o p t i m a lw a yt o c a l c u l a t et h eg e n e r a l i z a t i o ne r r o r b o u n d sb a s e do nt h ee s t i m a t i o no fa p p r o x i m a t ec o n v e x m o s to ft h ee x i s t i n g k e r n e ls e l e c t i o nm e t h o d sg a i nt h eo p t i m a lk e r n e lp a r a m e t e rb ys o l v i n gt h e o p t i m i z a t i o np r o b l e m ，i e ，m i n i m i z a t i o no ft h e r 2 2 h o w e v e rt h i sk i n do f m e t h o d sw i l ls p e n dg r e a tc o m p u t a t i o nc o s t ，a n dc a n tr e f l e c tt h ed i s t r i b u t i o n i i i o ft r a i n i n gd a t a t h em e t h o dp r e s e n t e di nt h et h e s i sc o m p u t e st h er a d i u sa n d m a r g i nd i r e c t l y , s oi tc a na v o i dt h es o l u t i o no ft h eo p t i m i z a t i o np r o b l e ma n d r e d u c et h ec o m p u t a t i o n c o s t m o r e o v e r , i tc a nb eu s e dn om a t t e rw h e t h e rt h e d a t a s e ti sd e n s eo rw h e t h e rt h ed i s t r i b u t i o ni su n i f o r m ( 3 ) d e v e l o p sa na p p r o x i m a t ee x p r e s s i o nm e t h o df o r r2 a 2b a s e do n c o n v e xa p p r o x i m a t e a c c o r d i n gt ot h e g e o m e t r i cs e n s eo fc l a s s i f i c a t i o n p r o b l e ma n ds t a r t i n gf r o md a t a s e t ，t h et r a i n i n gd a t aa r ed i v i d e db yt h ed e g r e e o fas a m p l ea n dc e n t e ro ft h ed a t a s e t t h e nt h ea p p r o x i m a t ec o n v e xa r e o b t a i n e d ，a n dt h ea p p r o x i m a t eo fr 2 a 2i ss oe x p r e s s e d a l lt h e s ep r o v i d e d t h eb a s i so f f o l l o w i n g k e r n e ls e l e c t i o n a p p r o a c h b a s e do nc o n v e x a p p r o x i m a t e ( 4 ) p r o v i d e st h es v m k e r n e ls e l e c t i o nm o d e la n di m p l e m e n ta l g o r i t h m b a s e do nc o n v e xe s t i m a t i o na l g o r i t h m t h ep o l y n o m i a lk e r n e la n dg a u s s k e r n e l ，a st w og e n e r a lk e r n e lf u n c t i o n sa r et e s t i f i e do nt h ea r t i f i c i a ld a t a s e t a n dr e a ld a t a s e tr e s p e c t i v e l y t h er e s e a r c h e si nt h et h e s i sa r et h eo n eo fk e yp r o b l e m t h er e s e a r c h r e s u l t sn o to n l yh a v e i m p o r t a n tt h e o r e t i c a ls i g n i f i c a n c e ，b u ta l s o d i r e c t a p p l i c a t i o nv a l u ef o rr e a l w o r l dp r o b l e m s k e y w o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r y ；s u p p o r tv e c t o rm a c h i n e ；k e r n e l s e l e c t i o n ；g e n e r a l i z a t i o n e r r o rb o u n d s ；c o n v e x e s t i m a t i o n ； c l a s s i f i c a t i o n i v 第一章引言 第一章引言 本章主要介绍论文的研究背景、所论及问题的研究现状及本文所取得的主要成 果。 1 1 研究背景 基于数据的机器学习是机器智能研究的重要方面，它研究从数据( 样本) 中寻 找规律，并利用这些规律对新数据或无法规则的数据进行预测。迄今为止，关于机 器学习还没有公认的理论框架，目前广泛使用的研究方法大致可分为以下三类： 第一，经典的( 参数) 统计学方法。现有的机器学习共同的理论基础之一是统 计学，参数统计方法是基于传统统计学的机器学习方法。在这种方法中，参数的相 关形式是已知的，训练样本用以估计参数的值，该方法有很大的局限性，首先，它 需要知道已知样本的分布形式，这在大多数应用中是不现实的。其次，传统统计学 研究的样本是趋于无穷时的渐近理论( 即大样本学习) ，现有的学习方法也大多基于 此。而对于实际问题，样本的数目往往是有限的，因此，一些理论上很优秀的学习 方法却可能表现出很差的应用性能。 第二，经验非线性方法。这类方法或通过对已有的基于传统统计学原理的方法 进行修正，或利用启发式方法设计某些巧妙的算法，对己知样本建立非线性模型。 这类方法克服了传统参数估计方法的困难，可以解决许多实际问题，但该方法缺乏 统一的数学理论，使得其表现时好时坏无法控制。 第三，统计学习理论【l 。4 1 。这是一种专门研究小样本情况下机器学习规律的理论， 该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下统计推理规则 不仅考虑了对渐近性能的要求，而且追求在现有有限信息条件下达到最优。v v a p n i k 等人从上世纪六、七十年代开始致力于此方面的研究，直到九十年代中期，随着学 习理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展， 统计学习理论及其在此理论上发展起来的支撑向量机( s u p p o r tv e c t o rm a c h i n e ， s v m ) 便迅速得到人们的重视。 由于统计学习理论为系统研究有限样本情况下的机器学习问题提供了坚实的理 论基础，支撑向量机方法常表现出令人向往的优良特征。越来越多的学者认为，关 于统计学习理论和支撑向量机的研究将出现飞速发展的阶段，而且由于其出发点更 符合实际情况( 有限样本假设) ，有理由相信这个研究热潮将会持续升温，并对机器 基于凸包估计的s v m 核参数选择方法研究 智能研究产生具有深远意义的影响。 统计学习理论由于最初解决模式识别、回归估计等问题时趋于保守且数学上比 较艰涩，而且没有能够将其理论用于实践的较好的方法，发展到目前在有限样本情 况下的机器学习理论研究逐渐成熟，已经形成了一个完善的理论体系，使得人们能 够很好地理解机器学习的本质。在此基础上所发展的支撑向量机方法，在解决小样 本、非线性及高维问题中所表现出许多特有的优势，其特点主要表现在以下方面： ( 1 ) 算法专门针对有限样本设计，其目标是获得现有信息下的最优解而不是样本 趋于无穷时的最优解。 ( 2 ) 算法最终转化为求解一个二次凸规划问题，因而能求得理论上的全局最优解， 解决了一些传统方法无法避免的局部极值问题。 ( 3 ) 算法将实际问题通过非线性变换到高维特征空间，在高维特征空间中构造线 性最佳逼近来解决原空问中的非线性逼近问题。这一特殊性质保证了学习机器具有 良好的泛化能力，同时，巧妙地解决了维数灾难问题( 特别的，其算法复杂性与数 据维数无关) 。 由于具有坚实的理论基础，支撑向量机在应用中常表现出颇具有竞争力的优势。 手写体识别是支撑向量机最早的应用之一 5 7 】，在m n i s t 数据库上，结合了平移不 变性的支撑向量机的测试误差已经达到o 5 6 【8 】，与其他方法相比，这一识别率已达 到非常高的程度；在文本分类、目标识别、甚至基因分析等生物信息领域的实际应 用中，支撑向量机也取得了极大成功【皿1 3 】；基于支撑向量机的回归估计也已成功地应 用到许多实际问题中，比如波士顿住房问题14 l ，时间序列预测问题等。在这些应 用中，所有获得的结果达到或超过了其它方法的水平。另外由于支撑向量机需要调 整的参数较少，使用也非常方便。 尽管统计学习理论已经成为目前机器学习方法的主流，支撑向量机也已成为目 前通用有效的机器学习方法，但在统计学习理论与支撑向量机方法研究中还存在许 多需要解决的问题，例如：如何将现有机器学习方法纳入统一的学习理论框架；统 计学习理论与其他理论体系之间的关系；支撑向量机算法在解决实际问题中的效率 评价及与其他学习方法的比较；支撑向量机学习算法的进一步加速；如何选择核函 数；如何将领域知识融入到支撑向量机以进一步提高其性能等。所有这些问题成为 目前统计学习理论和支撑向量机研究所关注的焦点。本文针对其中的s v m 核选择方 法进行研究。 笫一章引言 1 2 国内外研究现状 模型选择是任何机器学习必须面对的重要而困难的问题。在支撑向量机中模型 选择主要涉及核函数及其相关参数选择【l 睨1 1 。对于分类问题，核函数的选择方法已 有很多研究【2 2 2 8 1 ，这些方法大致可以归纳为两类：基于数据独立的方法和基于数据 依赖的方法。基于数据独立的方法不考虑数据的统计信息，而是利用关于问题的先 验信息来指导核选择，其代表性方法有三种：第一种是基于数据平滑性假设的核选 择方法 2 2 2 3 1 。这种方法对数据作平滑性假设( 如利用图像数据的局部结构信息) ，它 对特殊问题如图像识别非常有效，但对一般问题并不适用。第二种是基于v c 维界的 估计方法【3 1 。这种方法根据统计学习理论导出模型泛化误差的个上界r2 2 ( 这个 上界通常是v c 维的一个函数) ，并利用s v m 训练使v c 维的上界估计最小，以此为 准则确定核函数的参数。这种方法是有效的但需要多次重复训练s v m ，计算代价非 常大。第三种方法是留一交叉校验法( 1 e a v e o n e o u tc r o s sv a l i d a t i o n ) 2 4 - 2 5 和自举法 ( b o o t s t r a p i n g ) 26 l 。这类方法的基本原理是定义训练集、确认集和测试集，对每一 个给定的核参数，由训练集中的数据训练分类器，然后在确认集中测试其性能，其 中“留法”被认为是一种有效的且比较精确的方法。对于给定的包含，个数据的样 本集，“留一法”首先根据实验确定一个近似最优参数的范围，对其中的每一个参数， 任选训练集中的一个数据作为确认集，其他，一1 个数据作为训练集，选择其中使确认 集中测试误差最小的一组参数作为最优的参数。因为在一个参数点上就要迭代，次， 计算代价非常大，当数据集较大时核选择的速度会非常慢，所以并不实用，但它常 作为与其他方法相比较的一个参考标准【2 4 1 。 数据依赖的核优化方法仅根据给定的训练样本选择核函数，基于这些先验数据， 核及相关参数在s v m 训练之前被优化，或在学习过程中通过有限步迭代来逐步调整 以达到最优【2 7 _ 2 引，或利用b a y e s i a n 方法将核函数的选择与所处理的学 - 3 问题的先验 假设相对应，以逐步修正优化核函数 2 9 - 3 0 】。这些方法中，周伟达等川给出了尺2 2 的 个近似表示，并通过极小化这个表达式提出了一种核选择的方法，但所给出的 尺2 2 的近似表示只对均匀分布的数据有效。a m a r i 和w u l 2 7 。2 8 1 等基于由核函数导出 的黎曼几何结构，提出一种保形变换方法，将核函数的优化分为两步迭代：s v m 的 训练和核函数的修正。在核函数的修正阶段，利用前一步训练所获得的支撑向量， 用数据依赖的方法对核函数作保形变换，最后得到一个最优的结果。这方法有较 高精度，但结果稳定性较差，需反复迭代。b a y e s i a n 方法将核选择和“超参数”选 基于凸包估计的s v m 核参数选择方法研究 择融为一体，但计算复杂性极高【2 9 3 0 1 。 与数据独立的方法相比，数据依赖的方法一般需要较少的计算代价，也不需要 关于数据的先验假设，因而是一种一般的方法，可用于解决任何领域的任何问题， 但是这种方法可能会产生过拟合问题，从而导致泛化能力较差。 1 3 论文的主要工作 本文主要针对基于分类的s v m ，系统研究了核及相关参数的选择方法。全文共 分为六章，各章主要研究内容如下： 第一章引言介绍了本文研究的背景，提出了本文研究的主要内容。 第二章给出了统计学习理论和s v m 的基本原理。 第三章叙述了现有的参数选择的方法。 第四章给出了基于凸包估计的参数选择方法的实现。 第五章通过数据实验来验证本文所提出模型及方法的有效性。 第六章总结了论文的主要工作，提出了有待进一步研究的问题。 4 第二章统计学习理论和支撑向量机 第二章统计学习理论和支撑向量机 本章主要介绍统计学习理论，以及基于统计学习理论的机器学习方法一支撑向 量机，所有这些是本论文工作的基础。 2 1 统计学习理论 本节简要介绍统计学习理论等预备知识。 2 1 1 学习问题的一般表示 从样本学习的一般模型【4 1 包括三个部分如图2 1 ： 图2 1 学习问题模型 y y ( 1 ) 产生器( g ) ，产生随机向量x r ”，它们是从固定但未知的概率分布函数 f ( x 1 中独立抽取的。 ( 2 ) 训练器( s ) ，对每个输入向量x 返回一个输出值y ，产生输出的根据是同样 固定但未知的条件分布函数f ( yx ) 。 ( 3 ) 学 - j 机器( l m ) ，它能实现一定的函数集f ( x ，口) ，口人，其中人是参数集合。 学习问题就是从给定的f ( x ，口) ，a 人中选择出能最好逼近训练器响应的函数。 这种选择是基于训练集的，训练集由根据联合分布f ( x ，y ) = f ( x ) f ( yx ) 抽取出的， 个独立同分布观测( x 。，y 1 ) ，( _ y ，) 组成。 为了选择所得到的对训练器响应最好的逼近，就要度量在给定输入x 下训练器响 应y 与学习机器给出的响应f ( x ，a ) 之间的损失或差异4 y ，f ( x ，位) ) 。考虑损失的数学 期望值 r ( a ) = i 三( y ，f ( x ，a ) ) d f ( x ，y ) ( 2 1 ) 气 基于凸包估计的s v m 核参数选择方法研究 r ( a ) 又称为风险泛函。学习的目标就是，在联合概率分布函数f ( x ，y ) 未知，所 有可用的信息都包含在训练集中的情况下，寻找f ( x ，a 。) ，使风险泛函r ( a ) 最小化。 令z 代表数据对( x ，y ) ，将l ( y ，f ( x ，口) ) 表示为q ( z ，口) ，由于我们对联合分布函数 f ( x ，y ) 未知，所以在通常情况下通过最小化经验风险泛函： 1， 尺唧( 口) = q ( z ，口) ( 2 - 2 ) i = 1 来代替风险泛函r ( a ) 的最小化，进而使经验风险泛函r ( 口) 最小的q ( z ，口，) 来逼近 使期望风险泛函r ( a ) 最小的函数q ( z ，瓯) 。这就是著名的经验风险极小化( e m p i r i c a l r i s km i n i m i z a t i o n ，e r m ) 原则。 2 1 2 学习机器泛化能力的界 使经验风险最小化的函数不一定能够使实际风险最小化。v a p n i k 的统计学习理 论【3 j 给出了在什么条件下，使经验风险最小化的函数能够同时使实际风险最小化的条 件，即保证了学习过程的一致性。 定义2 1 如果下面两个序列依概率收敛于同一个极限，即 r ( a ，) 与i n fr ( a ) ，j 0 0 ， d e 几 r o m p ( 口，) 与i n f 尺( a ) ，j 。o ( 2 3 ) c t a 则我们说e r m 原则对函数集q ( z ，口) 口人和概率分布函数f ( z ) 是一致的。 定理2 1 被称为学习理论的关键定理。 定理2 1 ( 关键定理) 3 1 设函数集q ( z ，口) 口人满足条件 a i q ( z ，a ) d f ( z ) b ， ( a r ( 口) b ) ， ( 2 4 ) 那么，e r m 原则一致性的充分必要条件是：经验风险r e i n p ( a ) 在函数集q ( z ，口) ， 仗人上在如下意义下一致收敛于期望风险r ( a ) ： ；i m p s u p ( r ( a ) 一r 。p ( 口) ) 占) = o ，v 占 0 ( 2 5 ) o a e a 同时有定理2 2 成立： 定理2 2 【3 】 p s u p ( r ( 矿如，( 嗍 邮4 e x p ( 华) f ) ( 2 6 ) 口f 其中g a ( ，) 是生长函数。 第二章统计学习理论和支撑向量机 由定理2 1 和定理2 2 可知，学习过程一致性的条件： l i m 里盟：o( 2 7 ) - 一 ，m z - 。 定理2 3 【3 1 任何生长函数，它或者满足等式 g a ( ，) = l l n 2 ， ( 2 8 ) 或者受下面不等式约束： ， g ( ，) 五( 1 n + 1 ) ( 2 9 ) ，2 其中 是一个整数，使得当，= h 时，有 g ( h ) = h i n 2 ( 2 1 0 ) 或 g a ( h + 1 ) - y f a 。k ( x f ，z ) 一b 。) ( 2 2 7 ) i e s v 定理2 6 给出了一个函数是核函数的充要条件。 定理2 6 ( m e r c e r 定理) 【3 1 要保证三2 下的对称函数k ( “，1 ，) 能以正的系数口t o r k ( u ，v ) = 以。纨( “) 吼( v ) k = l ( 即k ( u ，v ) 描述了在某个特征空间的一个内积) ，其充分必要条件是，对使得 的所有g 0 ，条件 肛( ) g ( “) g ( v ) d u d v 0 ( 2 2 8 ) 成立。 根据以上定理，可以得到一些常用的核函数： 高斯径向基函数核：k ( x ，工) = e x p ( - l l x - x l l o r 2 ) 多项式核： k ( x ，x ) = ( ( x x ) + c ) 4 s i g m o i d 核： k ( x ，x ) = t a n h ( k ( x x ) + v ) 由上面核函数的形式可以看到，每个核函数里都有参数需要设定，这些参数选 择的好坏直接关系到s v m 的性能，因此如何有效的选择核参数是s v m 应用重要的 一步，论文后面的章节将对这一问题展开讨论。 第三章核参数选择方法的分析与研究 第三章核参数选择方法的分析与研究 ，s v m 是一种基于核的机器学习方法，原则上只要满足m e r c e r 定理的函数都可作 为核函数，但不同的核函数对s v m 的泛化能力有重要的影响，所以要构造s v m ，首 先要选择核函数及相关参数，这就是s v m 的核选择的问题。从本质上讲，支撑向量 机的参数选择是从低层次上进行优化( 选择最合适的核参数，即选择适当的特征空 间) ，而支撑向量机的训练则是从高层次上进行优化( 即固定了核参数以后，在选定 的特征空间求解最优的超平面) 。因此支撑向量机的核选择是使用支撑向量机算法 的第一个重要然而十分困难的步骤，如何有效的进行核及相关参数的选择是s v m 的 一个重要研究内容。对于一个给定的核函数，参数选择的目的就是要最小化泛化误 差，但是由于无法直接得到泛化误差的显示表示，因此如何寻找泛化误差上界是进 行参数选择的核心。 本章主要针对核函数及相关参数的选择这一问题，分析和研究目前国内外学者 的研究工作，并对这些方法作出评价。 3 1 泛化误差上界的估计方法 3 1 1 验证集估计( v a l i d a t i o ne s t i m a t e ) 【3 2 】 该方法的基本原理很简单，就是将训练样本集划分成两个部分，一部分用于训 练s v m ，另一部分作为验证集( v a l i d a t i o ns e t ) ，在验证集上评价s v m 的性能。该方 法用下式估计： t = 二甲( 一y l f ( x ；) ) ( 3 1 ) nu 、 pi = 1 其中 ( x ：，y ；) 恐为验证集，甲( z ) = 1 ，当工 o 时，否则甲 ) = 0 。 这种估计误差界方法的特点是简单、易于计算，但是误差界的精确程度严重依 赖于对训练样本集的划分，如何能够很好的对样本集进行划分是一个难以解决的问 题。在实际应用中，通过最小化该误差上界来寻找最优参数的方法很少被用到。 3 1 2 留一法( 1 e a v e o n e o u t ) 上界【3 2 】 该方法的基本原理是：给定一个，个样本的训练集，将其中一个移除，然后在剩 下的，一1 个样本上训练s v m ，将得到的s v m 在移除的样本上进行测试。对，个样本， 都要进行相同的操作，并用l ( x 。，y 。，x iy ，) 标识被错分的样本数。直接使用留一法 基于凸包估计的s v m 核参数选择方法研究 的计算泛化误差在实际中并不适用，因为留一法要多次训练支撑向量机，计算代价 相当大。一般，留一法常作为与其他方法相比较的一个参考标准，因为留一法可以 得到一个对泛化误差的几乎无偏估计( a l m o s tu n b i a s e de s t i m a t e ) 。 1 e p ：r 7 = e ( 三( x l ，y 。，x ，y ，) ) ( 3 2 ) 其中p 。l ，- i 是在，一1 个样本上得到的误差概率，e 为在概率在样本空间求期望。 由于这种估计的几乎无偏性，常常通过寻找留一法的界来替代真实的泛化误差 界。用厂。标识在所有样本上得到的s v m 决策函数，厂9 为在移除样本p 后得到的决 策函数，则有： ， l ( x 。，m 一，x y ) = w ( - y p f 9 ( x ，) ) ( 3 3 ) p = l ( 1 ) 支撑向量数 在s v m 中，根据k k t 条件，只有支撑向量对最后决策函数起作用，而其他样本 点对决策函数则没有贡献。对于留一法，当被移除点不是支撑向量时，决策函数并 不会发生改变，因此被误分的样本一定是属于支撑向量集。由上述分析，可以得到 如下一个泛化误差的一个最简单的粗略上别2 9 】： 丁：生( 3 4 ) f 其中。为支撑向量个数。该上界易于计算，常常在数值实验中被作为泛化误差的近 似估计。 ( 2 ) r a d i u s m a r g i nb o u n d 对于两类样本完全可分的情形，v a p n i k 蝴留一法过程泛化误差的上界1 2 4 】： 丁：4 1 墅( 3 5 ) l 醚 其中，尺是包含所有样本数的最小超球半径，是两类样本的间隔。 ( 3 ) s p a nb o u n d 在r a d i u s m a r g i nb o u n d 基础上，v a p n i k 和c h a p e l l e 进一步改进了留一法泛化误差 界，引入了支撑向量s p a i l 的概念【3 3 】。他们证明如果等式 1 4 第三章核参数选择方法的分析与研究 j ，p ( 厂。( 工，) - f 9x p ) ) = 口：s ； ( 3 6 ) 成立的话，则去掉第p 个支撑向量伊 。) 后和去掉之前所得到决策函数不发生改变， 即该样本可以被正确的分类。其中f o 。) 为在z 个样本上训练得到的决策函数在样本 缈o p ) 上的取值，口；为样本妒( x p ) 对应的拉格朗日乘子，厂p o p ) 为去掉样本妒 p ) 后 在，一1 个样本上训练得到的决策函数在样本p 上的取值，y ，为样本缈0 ，) 的类标识， s p 为妒o ，) 和集合人，的距离，其中，人p 为： f a p = 丑烈一) ，以= 1 ( 3 7 ) 注意到y p f 。( x ，) = 1 ，则留一法的泛化误差界为： t = 甲( a 瓣一1 ) ( 3 8 ) 1 j、pp ( 4 ) g a c v ( g e n e r a l i z e da p p r o x i m a t ec r o s sv a l i d a t i o n ) g c k l 的定义如下， g c k l = 喜( 强肌= 妻卅+ + ( 1 强) ( 1 圳+ ) 9 ， 它被认为是留一法的泛化误差，其中p j 是样本属于正类的概率，1 一p ，为样本属 于负类的概率，其中( 厂) + 的定义等同于甲( x ) 。但是由于无法事先知道概率p ，所有 g c k l 并不能直接计算。w a h b a 等人给出了一个近似的计算公式，即g a c v 荆3 4 1 ： ，”= = g a c v = ； ；| ；，+ 2 ，z 。一，c z i k i i + y ，正z 。卜c ，。( ，i j 。 c 3 t 。， 其中f 是s v m 的松弛变量，a 是它的拉格朗日乘子。该界主要是通过b a y e s i a n 后验概 率的方法得到。 ( 5 ) x f a l p h a b o u n d j o a c l l i m 给出了一个留一法泛化误差界【3 5 】： f ：竺! 丝塑! 三丛：堕! ( 3 ，= 一 j 1 l ， 基于凸包估计的s v m 核参数选择方法研究 其中0 k ( x f ，x f ) r 2 。 除了上述比较常见的方法之外，j a a k k o l a 和o p p e r 等人也分别从不同的角度上给 出了留一法误差上界【3 6 3 7 1 。 虽然从形式上来看上面的各种界的关联度不是太大，但是我们知道，对于s v m 有以下的等式和不等式成立： 口；5 万1 ，并且k ( x i ，x j ) d 2 = 4 r 2 ( 3 - 1 2 ) 将上述两个关系代入到各种留一法界中，可以看出：它们又都以关于d 2 2 的 函数为上界，d 2 2 是最具有普遍性的留一法上界。根据统计学习理论，函数集的v c 维也是和这个量是相关的，因此它们是一致的。s p a n 界是以s p a n 距离代替了d ，g a c v 界则是用k ( x i ，x ，) 来替代d ，由于它们都要比d 小，因此得到的留一法界也比d 2 a 2 要紧。在相关文献的实验中也分析了这现象，但是同时它们的计算也相对复杂， 直观意义也不是很强。本文在3 2 节将讨论对于一个给定的核函数，其最优参数的选 择就是通过r2 2 的极小化来得到。 3 2 最优参数的选取 得到泛化误差的界后，现有的参数选择方法可以分为如下几种： ( 1 ) 根据问题的先验信息来指导核参数选择。这种方法对数据作平滑性假设( 如 利用图像数据的局部结构信息) ，它对特殊问题如图像识别非常有效，但对一般问题 并不适用 2 2 - 2 3 】。 ( 2 ) 通过梯度下降法最小化泛化误差来进行核参数选取。由于核函数k 的性能是 由参数臼决定的，所以判决函数可以写为如下形式： 丘a 日( x ) = s g g n ( z o r f y f k 日( z ，x f ) + 6 ) ( 3 1 3 ) 核参数选择就是要求解下面的优化问题， 0 。= a r g m i n t ( a 0 目1( 3 1 4 ) 梯度下降法求解最优核参数算法的主要步骤为： s t e p l ：给定一个初始的核参数0 ： s t e p 2 ：使用标准的s v m 算法求解如下优化问题： 口o ( 秒) = a r g m a x w ( a ，0 ) 1 6 第三章核参数选择方法的分析与研究 即求解对偶问题，得到对应的口。值； s t e p 3 ：通过梯度下降法根据0 0 = a r g m i n r ( 口0 臼) 更新9 ，使t 的值变小； s t e p 4 ：转至l j s t e p 2 ，直到满足停机条件。 类似的方法在c r i s t i a n i n i ，c a m p b e l l ，b e n g i o 等的文献中都有提到【1 6 ，1 7 1 。 ( 3 ) 直接从样本集出发，利用构造性的方法给出对应的泛化误差上界，然后最小 化该上界，寻找最优的参数。这些方法中，周伟达等【3 1 1 给出了r 2 2 的一个近似表 示，并通过极小化这个表达式提出了种核选择的方法。这一类方法是一种数据依 赖的方法，能够很好地体现样本集的分布特征，一般需要较少的计算代价，也不需 要关于数据的先验假设，因而是一种一般的方法。这种方法对于均匀分布的数据十 分有效。 另外还有一些其它的核参数选择方法，如基于b a y e s i a n 方法 35 】的参数选择，它 将核选择和“超参数”选择融为一体，但计算复杂性极高。a m a r i 和w u 【2 7 。2 8 1 等基于 由核函数导出的黎曼几何结构，提出种保形变换方法，将核函数的优化分为两步 迭代：s v m 的训练和核函数的修正。在核函数的修正阶段，利用前一步训练所获得 的支撑向量，用数据依赖的方法对核函数作保形变换，最后得到一个最优的结果。 这一方法有较高精度，但结果稳定性较差，需反复迭代。 本文基于对上述现有文献和资料的分析和研究，给出了一种基于数据依赖的构 造性误差上界r 2 2 估计方法一凸包估计法来选取最优核参数与周伟达等人所提出 的方法相比，本文提出的方法不论数据分布是否均匀都可获得较好的结果。 基于凸包估计的s v m 核参数选择方法研究 第四章基于凸包估计的核及参数选择方法 对于任何一个学习问题，模型选择都是一个不可回避且非常困难的问题，它通 常指学习机的构建或拓扑结构的设定。在支撑向量机学习中，同样面临着模型选择 这一问题。对于s v m ，模型选择主要是指核函数及相关参数的选择。目前大多数的 核选择方法都是通过求解优化问题来得到最优的参数值，但是求解优化问题的计算 相当的大，在实际应用中比较困难。 本章提出一种基于凸包估计的核选择方法及实现算法。采用非优化技术，通过 极小化泛化误差界来进行核及相关参数的选择，可以有效地克服求解优化问题计算 量大的问题，并且能够较好的体现数据的分布特征。 4 1 基于凸包估计的核选择方法 对于给定的训练数据集 ( x ，y j ) ) ：- j ，由支撑向量机所得的解具有如下形式： 厂( x ) = s g n ( y ，a ? k ( x ，z ) - b 。) ( 4 1 ) i j ” 这里口。是通过学习得到的参数集( 记为人) ，核函数k 具有如下形式： k ( x ，x f ) = ( 缈( x ) ，妒( 石，) ) ( 4 2 ) 一旦核函数选定，参数人可以通过求解一个标准的凸规划问题得到，但由此所 得的学习机泛化能力将在很大程度上依赖于所选的核函数。 核选择的目的是在给定的核函数k ( z ) ( 是核参数的集合) 中按照一定的准则 选择一个合适的核函数，k ( z ) 可以包含无穷多的候选核函数( 例如满足m e r c e r 条件 的函数的全体) 。但在实际应用中，k ( z ) 通常包含有限个核函数，如： k ( ) = 诼即。( 仃) ，k 删( d ) ，k 。，( 尼，v ) ，k 。( p ，目) j ， ( 4 3 ) 其中： n n 亥k 舻。( 仃) ：k ( x ，x ) = e x p ( 一8 工一x l l 仃2 ) ； 多项式核k 蒯( d ) ：k ( x ，x ) = ( x x ) + c ) 。； s i g r n o i d 核k ，( 尼，1 ，) ：k ( x ，j c ) = t a n h ( k ( x x ) + 力； 神经网络核k 。( p ，0 ) ：k ( x ，x ) = t a n h ( p x7 y + 0 ) 。 在这一情况下，核选择不仅要选择核函数的类型，而且要选择相应的参数，当k 只包含一类核函数时，核选择就是通常所指的核参数选择。 第四章基于凸包估计的核及参数选择方法 首先考虑给定核函数求其最优参数。这时进行核选择的主要目的就是要最小化 泛化误差，但是由于泛化误差通常不能显示地求得，因而一般只能得到个近似的 泛化误差上界。对于分类问题，给定一个核函数，根据统计学习理论和第三章的分 析，s v m 的泛化误差与r 2 2 有关，尺2 2 越小，其泛化误差上界越小。因此如果 选定一个核参数能使r 2 2 的值最小，那么它即为最优核参数，换言之我们可以通 过极小化尺2 2 来选择参数。现有的方法大多数是通过求解一个最优化问题的方法 来进行参数的选取，但是由于求解优化问题计算复杂性比较大，与训练样本集的规 模有关，因而在实际问题中效率比较低。 本章提出一种构造性的基于几何解释的核参数选择方法。这种方法从数据集出 发，直接计算r 和的值，求出对应r2 2 值最小的核参数作为最优参数值。 图4 1凸包估计示意图 不失一般性，我们讨论两类样本分类问题。如图4 1 所示，对于a 类样本与b 类 样本，c o y a 与c o v b 分别为它们的凸包，可以看出最小的超球半径月就是c o v a 与 c o v b 中距离最远的两个凸包点_ 和乃的距离的半，即 尺= m a x 2 忙一 ，x f c o va ，y i c o v b ( 4 4 ) 最大间隔就是c