（通信与信息系统专业论文）svm理论其应用的研究.pdf

生里型堂垫查盔兰竖主堡塞j j ! ! 堑垒 第一章绪论 1 1 有限样本的预测学习方法及其s v m 算法 预测学习方法是机器学习的一个重要研究领域，绝大部分机器学习算法的 应用都涉及到对数据的预测性学习，目的是从已知数据中估计相关性以达到准 确预测将来数据变化。经典的模式识别方法，各种统计方法以及近些年来出现 的各种神经网络算法都被应用于估计这种数据中固有的相关性，试图建立一个 能预测未来数据的模型。虽然，这些应用在一些特殊的领域取得了一定的进展， 并且提出了一些新的概念和方法，但是，这些方法有其固有的算法缺陷：由于 不知道数据的分布密度以及有限的训练数据，常常导致了病态的训练结果，预 测效果往往不尽人意。人们迫切需要关于预测学习算法共同的概念和理论框架 以及更高效的预测学习方法。 到目前为止，几乎所有的预测学习算法都可以归结为以下三类 c h e r k a s s k y 1 9 9 9 1 ： 传统的统计预测方法 这类方法是在参数结构形式已知的前提下，通过训练数据，预测各参数的 值，例如：最小二乘法。应用这些预测方法除了需要很强的先验知识外，还需 预先知道模型的结构形式。但是，在处理大量的实际预测问题时，常常不知道 背景知识，面对大堆采样来的数据，也不知道模型的结构形式。由于传统统 计学研究的前提是样本数目趋于无穷大时的渐近理论，而参数预测方法几乎都 是建立在这一前提基础之上的。因此只有当采样数据趋于无穷时，参数方法的 训练结果才趋于真实的模型。由于实际样本数目是有限的，很难满足这一前提。 经验非线性预测方法 8 0 年代发展起来的人工神经网络和柔性统计方法就属于这一类。虽然，这 些新的方法克服了参数预测方法的部分弱点，能够依照需要，假设数据内在相 关性而构造非线性模型。然而，这些非线性方法缺乏统一的数学理论基础，通 常是从生物学的理论和一些学术流派中得到灵感，对于诸如神经网络中的结构 选择和权重的初值设定，仍需要借助于经验，得到的模型通常是局部最优解， 而非全局最优。 统计学习理论 早期的统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 是从6 0 年代发展起来的 【v a p n i k1 9 6 3 】，直到9 0 年代，它一直是作为一种针对有限样本的函数预测问题 的纯理论分析工具 v a p n i k1 9 9 1 1 。虽然，早期的统计学习理论提出了v c 维 ( v a p n i k c e r v o n e n k i s ) 理论 v a p n i k1 9 7 1 1 ，为衡量预测模型的复杂度，提出了 有效的理论框架。但是，它仍然是建立在经验风险最小化原则基础之上，即： 以训练的平均误差为最小的模型作为期望的最终模型。所以，早期的统计学习 理论一直停留在抽象的理论和概念的探索之中，直到9 0 年代初期，v c 维理论 还没有得到很好的应用c h c r k a s s k y1 9 9 9 。 生星型堂垫查盔兰苎主堕塞 一皇i 二曼! 自! 鱼 9 0 年代中期，v a p n i k 和他的a t & tb e l l 实验室小组提出了s v m 算法，进 一步丰富和发展了统计学习理论，使它不仅是一种理论分析工具，还是一种能 构造具有多维预测功能的预测学习算法的工具，使抽象的学习理论能够转化为 通用的实际预测算法。 在统计学习理论基础之上发展起来的s v m 算法，是一种专门研究有限样本 预测的学习方法。与传统统计学相比，s v m 算法没有以传统的经验风险最小化 原则作为基础，而是建立在结构最小化原理基础之上，发展成为一种新型的结 构化学习方法。它能很好的解决有限数量样本的高维模型的构造问题，而且所 构造的模型具有很好的预测性能。s v m 算法有很多应用例子，如：人脸识别， 手写体的识别，信号处理，k d d 的应用等。上述成功的应用都说明了这种基于 v c 维理论而发展起来的结构化学习方法的潜在优势。 更重要的是：作为s v m 算法基础的v c 维理论和结构最小化原则也为进一 步完善传统的统计预测方法和经验非线性预测方法提供了理论基础和统一的理 论框架。如何在此框架下重新构建各类预测方法，解决许多原来难以解决的问 题，进一步发展和完善s v m 算法是当前亟待解决的个问题。国际上已有许 多学者为此做了大量的工作。本文也正是基于这一出发点，提出了一些新的改 进算法和评价方法。 1 2s v m 机器学习算法的发展历史、现状及其不足 ( 一) s v m 及其学习算法的历史和现状 作为s v m 的奠基者v v a p n i k 早在6 0 年代就开始了统计学习理论的研究 v v a p n i k ，1 9 6 3 】，1 9 7 1 年，v v a p n i k 和a c h e r v o n e n k i s 在”t h en e c e s s a r ya n d s u f f i c i e n tc o n d i t i o n sf o r t h eu n i f o r m sc o n v e r g e n c e o f a v e r a g e s t oe x p e c t e dv a l u e s ” 一文中，提出了s v m 的个重要的理论基础v c 维理论。 1 9 8 2 年，在”e s t i m a t i o no fd e p e n d e n c e sb a s e do ne m p i r i c a ld a t a 一书 中，v v a p n i k 进一步提出了具有划时代意义的结构风险最小化原理堪称为 s v m 算法的基石。 l9 9 2 年，b o s e r ，g u y o na n d v a p n i k ，在“at r a i n i n ga l g i r i t h m f o ro p t i m a l m a r g i n c l a s s i f i e r s ”一书中，提出了最优边界分类器 b o s e r , 1 9 9 2 1 。 1 9 9 3 年，c o r t e s 和v a p n i k ，在”t h es o f tm a r g i nc l a s s i f i e r 一文中，进一步探讨 了非线性最优边界的分类问题 c o r t e s ，1 9 9 3 】。 1 9 9 5 年，v a p n i k 在”n l en a t u r eo fs t a t i s t i c a ll e a r n i n gt h e o r y ”一书中，完整地 提出了s v m 分类。 1 9 9 7 年，v v a p n i k ，s g o k o w i c h 和a s m o l a ，发表的”s u p p o r tv e c t o rm e t h o d f o rf u n c t i o n a p p r o x i m a t i o n ，r e g r e s s i o n e s t i m a t i o n ， a n d s i g n a l p r o c e s s i n g ”一文中，详细介绍了基于s v m 方法的回归算法和信号处理方法 由于s v m 算法的潜在的应用价值，吸引了国际上众多的知名学者，近几年 出现了许多发展和改进的支持向量算法( s v m ) ，其势如雨后春笋一般。如：s m o l a 和s c h o l k o p f , 1 9 9 8 a ，s m o l a1 9 9 8 ，s c h o k o p f , 1 9 9 8 a ，1 9 9 6 ，b e r m e t t ，1 9 9 9 ，w e s t o n 等 1 9 9 9 。有关非线性s v m 中核的研究方法，如： s c h o l k o p f 等1 9 9 8 a b u r g e s ， s c h o k o p f , 1 9 9 7 。值得一提的是：1 9 9 8 年：s m o l a 在他的博士论文中详细研究了 s v m 算法中各种核的机理和应用，为进步完善s v m 非线性算法做出了重要 的贡献。 垦型兰垫查盔兰堡主篓塞笪二! 咝 在s v m 的应用方面，目前，m i t , b e l ll a b 和微软研究所等已成功地将s v m 算法匠用于动态图像的人脸跟踪，手写体数字识别，信号处理，语音识别，图像 分类，k d d 和控制系统等诸多领域 c o r t e s1 9 9 5 ，g u y o n1 9 9 7 ，e o s u n a1 9 9 7 ，v a p n i k ， 1 9 9 7 。 ( 二- ) s v m 算法研究中的不足 目前，很多关于s v m 和v c 的理论和应用问题都亟待研究。一方面，这种 基于统计学原理的理论思路对新的学习算法的提出很有启发，另一方面，由于 s v m 出现不久，其理论依据和算法实现尚有大量问题有待于发展和完善。在上 述问题中，我们认为下面几个问题尤其值得研究： 1 完善s v m 方法。s u p p o r tv e c t o r s 的确定可转化为约束的优化问题，但当训 练集的规模很大时，传统的优化方法难以满足实时性要求，如何设计快速有 效算法是s v m 中的重要问题之一； 2 基于s v m 算法的多类问题分类算法。 3 对非线性分类问题，s v m 的核方法仍有一些理论缺陷。 4 在s v m 的应用研究方面，由于s v m 算法是对神经网络学习算法、最j , z 乘法的改良，尚需要大量应用到实际问题中去，如建模、参数辨识和自适应 控制等问题，并将它与已有的处理结果进行比较和分析，以便进一步深入研 究。 5 把v c 理论和结构风险最小原理等理论框架进一步推广，产生新的学习算法 或改进算法。 、 1 3 本文的研究目标与动机 蔫 1 7 3 l 每 s v m 算法是种新型的结构化机器学习算法，它是将分类问题和回归问题 化成为二次规划问题。这种转化的优点是：使分类更加精确，克服了神经网 诸多的缺点，如结构和权重的不确定性。但是，也带来了计算量增大等缺点。 了克服上述缺点，更好地发挥s v m 的算法优势，对以下问题做了深入探讨： 充分利用s v m 的几何特征，改进传统的预测学习算法，如：遗传算法 f a n 2 0 0 0 a ，f a n 2 0 0 0 b 】。 利用s v m 算法中的理论框架改进经典的模式识别理论，如：模式识别中特 征提取和特征选择的评价标准 f a n2 0 0 0 c 1 。 克服s v m 固有的缺点，结合其他算法的优势，实现分类算法的快速性和准 确性，同时，解决多类问题的分类精度。如：与粗集理论结合，形成一种优 势互补的多类问题的组合分类器 f a n 2 0 0 0 d ，f a n2 0 0 0 e 1 。 进一步完善s v m 算法，如：s v m 非线性算法中核的选择方法。 1 4 本文的内容安排与贡献 ( 一) 内容安排： ( 1 ) 理论准备 里型兰垫查盔堂竖圭笙奎兰二! ! ! 堕 为了让读者更好地理解本文所提出的方法和评价标准- 在第三警! 咎寸堂 霖蹇童銎器簇端粼谍淼篙溅嚣耆箬裔篓称作是一种新型的结构化机器学习算法，以及它是如伺将分芡j 列咫丰口凹归j 口j 是| ! 转化成为二次规划问题，同时讨论了s v m 算法中核的选择问题。 ( 2 1 第三章基于s v m 理论优化感知器的遗传算法 在这一章中，提出一种基于s v m 理论优化感知器的遗传方法。利用s v m 的几何特征指导遗传算法优化分类器的过程，该方法将遗传算法和神经网络相 结合，进化传统的感知器，克服感知器分类结果的偏向性、连接权的局部收敛 性和误识率高等弱点；并借助于遗传算法全局寻优的特点，使改进后的算法， 具有自进化、自适应能力，以及很好的数据推广性能和抗干扰性，提高了神经 网络的整体性能。可作为标准的s v m 算法的替代算法。 ( 3 1 第四章基于粗集理论和s v m 算法的组合分类器 这一章提出一种将粗集方法与s v m 算法结合起来的组合分类器。借助于粗 集理论与s v m 算法的优势互补，设计了一种新型组合分类器，它能提高多类 问题分类精度和分类的快速性。利用粗集理论在处理大数据量、消除冗余信息 等方面优势，减少s v m 训练数据，克服s v m 算法因为数据量太大，处理速度 慢等缺点；同时，借助s v m 良好的分类性能，针对粗集约简后的最小属性集， 实现精确分类。在这一章中，以手写体汉字的识别为例，说明本算法的实用性。 ( 4 ) 第五章基于遗传规划指导s v m 算法中核的进化， s v m 算法的核函数的选择一直困扰着s v m 非线性算法的应用。国际上许 多学者针对不同类型或同一类型不同特例的问题，提出某种核的选择依据。这 里，我们针对更一般的情况，提出一种利用遗传规划和c b r ( c a s eb a s e r e a s o n i n g ) 技术，来指导核函数的进化和选择过程。遗传规划是一种用以解决 函数表达式和计算机程序进化的优化工具，为我们选择核提供了一种很好的优 化方法，同时，c b r 技术能将进化基本单元作为案例( c a s e ) 加以处理，使 遗传规划更具有指导性。 ( 5 ) 第六章特征选择和提取要素的分析及其评价 这章将s v m 理论应用于特征选择和提取方法的分析，研究了影响特征 选择和提取的因素，并给出了正、负边缘距离的定义和特征选择、提取的评价 方法。以往的特征分类评价和分类方法多是建立在传统的统计学基础之上，前 提是要有足够多的样本，但当样本有限时难以获得理想的效果。本文以研究小 样本统计估计和预测的理论统计学习理论框架为指导，研究基于小样本所 选择和提取的特征的分类评价，提出了衡量特征推广性能的正边缘距离概念和 衡量类交叠情况的负距离概念，并在此基础上，进一步提出了特征选择和提取 的最大正边缘距离评价、最小负距离评价、最小维评价和最小误识率评价。本 文以相似的手写汉字的识别为例，说明所提出的定义和评价方法的实用性。 ( 二) 本文贡献 1 利用s v m 几何特征指导遗传算法进化感知器，实现线性和非线性分类 旦型堂蕉查盔兰竖主堡塞堡二j ! 壅坠 翼黧羹篓蓑凳裁算法结合成为组合分类器，提出了针对该组合分 翼曼鞴黥篓藉瀚差尊霁喜髀暑喜鬟箍群尊翟翥季蓦篡 类器输出的冲突消解方法，并将这种组合分类器_ 匝用于大子弹刚于与件 汉 将 于 根 最 并 字c b 识r 另竖术、遗传规划方法综合地应用到s v m 的核的选择中，并在基技术、遗传规划方法综合地应用到 的核的远弹甲，开仕量 图像内容的分类仿真实验中，取得了很好的效果。 据s v m 几何特征，提出了特征选择和特征提取的四个基本评价标准： 小正边缘评价最小负边缘评价，最小v c 维评价，最小误识率评价， 且提出了基于s v m 几何特征的正边缘和负边缘的概念和定义。 主曼登堂塾查丕堂竖圭堡奎 墨三重兰望兰羔型里垒墨翌垡型墅墨! 塑 第二章统计学习理论及s v m 算法介绍 机器学习是人工智能的一个重要研究领域，绝大部分机器学习算法的应用 都涉及到对数据的预测性学习，目的是从已知数据中估计相关性以达到准确预 测将来。近些年来，基于神经网络、柔性统计和统计力学的学习算法都取得了 一定的进展，各自提出了一些新的概念和方法，表面上看这些概念和方法有一 定的联系，但实际上它们之间还存在很多差异，人们迫切需要关于预测学习算 法共同的概念和理论框架。 包括模式识别、神经网络等理论在内的现有机器学习方法，其重要理论基 础之一是统计学，而传统统计学研究基础是样本数目趋于无穷大时的渐近理论 ( 见文【z _ h a n g ，2 0 0 0 】) 。现有学习方法也多是基于这一假设，但在实际应用 中，样本的数目往往是有限的，因此些理论上很优秀的学习方法在实际中表 现的却不尽人意。 与传统统计学相比，统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 是一种专 门研究小样本情况下机器学习规律的理论。v v a p n i k 等人从六、七十年代开始 致力于此方法的研究( 见文 v a p n i k ，1 9 8 2 1 ) ，到九十年代中期，随着其理论的 不断发展和成熟，也由于神经网络缺乏实质的进展，统计学习理论开始受到越 来越广泛的重视。 统计学习理论是建立在一套坚实理论基础之上的，为解决有限样本学习问 题提供的一个统一的理论框架。它能将很多现有的方法纳入其中，有望帮助解 决许多原有难以解决的问题。同时，在这一理论基础之上建立起的一种通用学 习方法支持向量机( s u p p o a v e c t o rm a c h i n e 或s v m ) 2 1 、机器学习的基本问题 2 1 1 问题的表示 机器学习的e t 的是根据给定的训练样本求对某系统输入、输出之间依赖关 系的估计，使它能够对未知输出做出尽可能准确的预测，可以一般地表示为： 变量y 与x 存在一定的未知依赖关系。即遵循某一未知的联合概率f ( x ，夕) ( x - 与y 之间的确定性关系可以看作是其特例) ，机器学习问题就是根据n 个独立同分布 观测样本： ( x l ，y 1 ) ，( x 2 ，y 2 ) ，( x 。，y 。) ( 2 1 1 ) 生垦型堂垫查：苎；堂蔓圭堡塞一一e 蔓l 竺盐兰翌里笪垦墅尘壁e i i ! 塑 在一组函数 厂( x ，w o ) 中求一个最优的函数厂( x ，) 对依赖关系进行估计，使期 望风险最小：，一一、 e ( w ) = i l ( y ，f ( x ，w ) ) d f ( x ，y ) ( 2 - 1 - 2 ) 其中， ，( x ，w 。) ) 称作预测函数集，w 为函数的广义参数， ，( x ，w o ) 可以表示 任何函数集，( _ y ，( 墨w ) ) 为由于用f ( x ，w ) 对y 进行预测而造成的损失，不同类 型的学习问题有不同的损失函数，预测函数也称作学习函数、学习模型或学习 机器。 有三类基本的机器学习问题：模式识别、函数逼近和概率密度估计a 对模 式识别问题，输出y 可分别表示为：y = 0 ，1 ) 或 1 , - 1 。预测函数称作指示函 数，损失函数可以定义为： 三( y ，厂( z ，w ) ) = 暑箩y y = ，f ( ( ，x ，, w w ； ( 2 1 3 ) 使风险最小就是b a y e s 决策中错误率最小。 在函数逼近问题中，y 是连续变量，损失函数可定义为 l ( y ，f ( x ，w ) ) = ( y f ( x ，w ) ) 2 ( 2 - l 4 ) 即采用最小平方误差准则。 对于概率密度估计问题，学习的目的是根据训练样本确定z 的概率密度，记 估计的密度函数为p ( x ，w ) ，则损失函数可以定义为 f y ，f ( x ，w ) ) = 一l o g ( p “，w ) ) ( 2 1 5 ) 2 1 2 经验风险最小化 在上面的问题表述中，学习的目的在于使期望风险最小。但是，我们可以 利用的信息只有( 2 - 1 1 ) ，( 2 - 1 2 ) 式的期望风险无法计算，因此传统的学习 方法采用了所谓的经验风险最小化原理( e r m ) ，假设概率分布是均匀的，即 用样本定义经验风险：在决策函数集中寻求函数九，最小化期望风险 r 扭) = 厶b ) 一y l p ( x ，y ) 出痧。 ( 2 一l 一6 ) 这里厶：r “一 一1 ，1 ) 称为假设函数，集合h = 兀b ) ：五a ) 称为假设空间。所谓 经验风险是指 r 。 ) = 壹阮o ，) 一y i = l ( 2 。1 7 ) 由于分布p ( x ，y ) 未知，实际上r o ) 无法计算，因而也就无法最小化期望风险。 但由于已知p ( x ，y ) 的一些样本点，且当样本点的个数f 趋于无穷大时，经验风险 趋于期望风险。很多函数逼近算法，如神经网络的学习算法和最小二乘法正是 基于所谓经验风险最小化原理，即最小化经验风险可使期望风险最小化。 主璺型堂垫查盔兰堡主堡苎 一塑三童塑型兰竺韭墅垒垦墅尘塑堕! ! 塑 2 1 3 复杂性和推广性能 经验风险最小原理不成功的一个例子是神经网络的过学习问题。开始，很 多注意力都集中在如何使r e m p ( 更小，但很快发现，训练误差小并不能导致好 的预测效果，某些情况下，训练误差过小反而导致推广能力下降，即真实误差 增加。 之所以出现过学习现象，一是因为样本不充足，二是学习机器设计不合 理。这两个问题是相互关联的，设想一个简单的例子，假设有一组实数样本 ( x ，y ) ，y 取值在【0 ，1 】之间，那么不论样本是依据什么模型产生的，只要用 f ( x ，口) = s i n ( a x ) 去拟合它们( 盯是待定参数) ，总能够找到一个口使训练误差为 零，但显然得到的“最优”函数并不正确代表真实的模型。究其原因，是试图 用一个十分复杂的模型去拟合有限的样本，导致丧失了推广能力。神经网络 中，若对有限的样本来说，网络学习能力过强，足以记住每个样本，此时，经 验风险很快就可以收敛到很小甚至为零，但却根本无法保证它对未来样本能给 出好的预测。学习机器的复杂性与推广性之间的这种矛盾同样可以在其他学习 方法中看到。 文献 c h e r k a s s k y1 9 9 7 1 给出了一个实验例子，在有噪声条件下用模型y = z 2 产生1 0 个样本，分别用一个一次函数和一个二次函数根据e r m 原则去拟合，结 果显示，虽然真实模型是二次的，但由于样本数有限且受噪声的影响，用一次 函数预测的结果更好，同样的实验进行1 0 0 次，7 1 的结果是一次拟合好于二次 拟合。 由此可看出，有限样本情况下，1 ) 经验风险最小并不一定意味着期望风险 最小；2 ) 学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目的 样本相适应，我们需要一种能够指导我们在小样本情况下建立有效的学习和推 广方法的理论。 2 2 统计学习理论 统计学习理论就是研究小样本统计估计和预测的理论，主要包括以下四方面 内容 v a p n i k ，1 9 9 5 ： 1 ) 经验风险最小化准则下统计学习致性的条件： 2 ) 在这些条件下关于统计学习方法推广性的界的结论； 3 ) 在这些界的基础上建立的小样本归纳推理准则； 4 ) 实现新的准则的实际方法； 2 2 1v c 维 v c 维理论是统计学习理论的最重要的理论基础 v a p n i k 1 9 7 1 ，1 9 8 2 ， 1 9 9 1 1 ，v c 维是一种定量反映函数集学习能力的概念。n 维线性空间的指示集函 数的v c 维等于n + i ，这种线性空间中指示函数集的v c 维定义如下：如果存在维 数为”的点集 x ) 。，由 x ) 。可构造2 n 种模式，指示函数集完全能够分开所有 的可能模式；但当点集维数m r l ，上述指示集函数便不再能够把2 “m 完全分开， 于是1 3 被称为指示函数集的v c 维。若对任意数目的样本所构成的各种模式都能 被函数集分开，则该函数集的v c 维是无穷大。v c 维越大则学习机器越复杂，所 以，v c 维又是学习机器复杂程度的一种衡量。 图2 a v c 维示意图 圈2 bv c 维示意图 图2 a 7 个样本能完全被包含3 个分类超平面的函数集分开，所以该函数集的 v c 维等于7 。而图2 b 中4 个样本没有完全分开，图中函数集只能分开2 个样本， 所以它的v c 维等于2 。 2 2 2 推广性的界 早在1 9 7 1 年，v a p n i k 就指出经验风险的最小值未必收敛于期望风险的最小 值 v a p n i k1 9 7 1 】，即经验风险最小化原理不成立，并且证明了经验风险的最小 值收敛于期望风险的最小值当且仅当r 以) 依概率一致收敛于矗n ) ，并且当且 仅当假设空间 ( x ) ：五e a 的v c 维是有限的 v a p n i k1 9 8 2 。 v a p n i k 和c h e r v o n e n k i s 深入研究后得出如下结论：概率经验风险r ( 五) 和实 际风险r 恤) 之间以( 1 一叩) 概率关系，满足如下关系 v a p n i k1 9 9 5 ： 矗以) sr , m p 以) +( 2 、2 1 ) 这里h 是假设空间h 的v c 维，为样本数。显然， ( 2 - 2 1 ) 式中经验风险 r e m p ( 五) 最小并不能保证期望风险r ( ) 最小。为了克服这一缺陷，v 印n i k 提出 了结构化风险最小原理：为了达到期望风险最小，设法使( 2 - 2 一1 ) 式右边两项 同时最小，即v c 维 和经验风险r 一( 五) 同时最小，如式( 2 2 2 ) 。 r ( w ) sr 。( w ) + q k ( h n ) ( 2 2 2 ) 通过上面分析，我们可以看出：在有限的训练样本情况下，学习机器的v c 维越 高( 即：学习机器复杂性越高) ，则置信范围越大，导致真实风险与经验风险 之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程 不但要使经验风险最小，还要使v c 维尽量小，以缩小置信范围，才能取得较小 的实际风险，即对未来样本有较好的推广性。 2 2 3 结构风险最小化原理 从上面的结论看到，e r m 原则在样本有限时是不合理的，我们需要同时最 小化经验风险和置信范围。其实，在传统方法中，由于缺乏理论指导，我们是 根据先验知识和经验，人为地一次一次的修改学习模型和算法，以期望调整置 信范围，这种手工的方法比较适合现有样本的离线训练，当样本数目变化且样 本更新时常常出现所选择的模型又出现较大的偏差，需要进一步调整，于是 出现了自适应算法等各种修正方法，但问题的根结却未得到解决。 统计学习理论提出了一种新的策略，即把函数集构造为一个函数子集序 列，使各个子集按照v c 维的大小排列：在子集中选择经验风险r ( 五) 和置信 范围( ( a n ) ) 同时最小的子集，作为期望风险最小的函数模型。这种思想称 做结构风险最小化原理( s t r u c t u r a lr i s km i n i m i z a t i o n ) ，如图3 中的所对应s 2 的 函数子集所示。 受 函散集子集s i cs 2 cs 3 v c 缝h l i h 2 i h 3 图3 结构风险最小化原理示意图 堂堕登壁查兰堕主堡塞 苎三童塑堡堕兰墨堡鲨堡翌鱼堕蔓妻! ! 翌 另外，统计学习理论还给出了合理的函数子集结构应满足的条件，及其在结 构最小化原理下( s r m ) ( 如：图3 中s 3 ) 原理下实际风险收敛的性质。实现 s r m 原则可以有两条思路：一是在每个子集中求最小经验风险，然后，选择使 最小经验风险和置信范围之和最小的子集。显然，对于子集数目不大的情况 _ f ，这种方法尚能应付，当子集数日趋于无穷时，这种方法是不可行的。第二 种思路是：设计函数集的某种结构使每个子集中都能取得最小的经验风险( 如 经验风险为o ) ，然后，只需选择适当的子集使置信范围最小，则这个子集同时 使经验风险和置信范围同时最小。支持向量机方法( s v m ) 就是利用了这一原 理，成功地实现了上述思想。 2 3 、s v m 分类算法 s v m 算法是结构化风险最小原理的近似实现i v a p n i k1 9 9 5 1 ，这里，重点介绍 s v m 分豢算法和s v m 算法中的最大边缘慰想。 2 3 1 s v m 线性分类算法和它的最人边缘思想 设数据集合c k i s s l 和c k i s 8 2 是线性町分的，即存在( 眠b ) 使 w z 。+ b j l ，v x c l a s s l2 - 3 - l a ) w r + b 一一l ，v x 。c a a ：， s 2( 2 3 - l b ) 分类的目的是寻求( b ) ，它最佳分离c l a s s l 1 1 c l a s s 2 ，此时假设空间由所有的指 小函数集j 。= s t g n ( w z b ) 组成。为减少分类平面的重复，对( 引进行如下 约束： ，揪w t + 6 j 2 l ( 2 - 3 2 ) 椭足( 2 3 - 2 ) 的超平面称为媳型超平面，可以证明典型超平面集合的v c 维是 | v i - l ，即所有自由参数的数目。妇果，x ，a ，q 位于 ，维单位球内 o s u n a 1 9 9 7 ， j ，。= = s 渺( w r + 6 ) ：删i a f 2 3 3 ) 集合( 2 - 3 3 ) f 搀v c 维h 满足 o s u n a , 1 9 9 7 ： h 蔓m i f l 臼2 ， + l( 2 3 4 ) 当数据点z ，x 。，a ，- 位于半径为r 的球内时，( 2 - 3 4 ) 式变为： h f m i n 扛2 4 2 ，n q - 1 ( 2 3 5 ) 注意到点x 到( w ，6 ) 确定的超平面的距离为 ，、f w r + b i d ( t w 6 ) 。一( 2 - 3 - 6 ) 圭受型堂垫查杰兰堕主丝塞 苎三兰壁丝笙瑾噬望璺堡壁堕! ! 墨 对线性可分的情形( 即经验风险为零) ，求最佳“，6 ) 归结为下列二次规划问 题： m i 1 2 | 1 w l | i 2 j t y ，( w x ，+ 6 ) 1 ，i = 1 , 2 ，a a ， ( 2 3 7 ) ( 2 - 3 7 ) 式的约束条件也可以表示为 y ，( w 工，+ 6 ) 一l 0 ( 2 3 8 ) 利用l a g r a n g e 优化方法在约束条件( 2 3 8 ) 下，构造l a g r a n g e 项式： l ( w ，b ，a ) = 去i 叫1 2 - z 旯， y ，( ，+ 6 ) 一1 】 ( 2 3 9 ) 这里a = ， ) 是对应于约束条件( 2 - 3 8 ) 的l a g r a n g e 多项式的非负向量。 二次规划的最优解是( 2 - 3 9 ) 的鞍点，这样，我们可以找到对应鞍点的 ( w ，b ，a ) ，对( 2 - 3 9 ) 求偏导，得到： _ o l ( w , b , a ) ：w 一圭砂一：o 却 智 掣= 妻仙= 。 由( 2 - 3 1 0 ) 可求得最优的w 。： w = x ；y ( 2 - 3 一i 2 ) 和( 2 - 3 1 1 ) 代入( 2 - 3 - 9 ) 得到： ，( a ) ： 一黝w r ：圭 一号圭圭五- 只乃v 一 式( 2 - 3 1 3 ) 可以转化为对偶的二次规划问题， m a x i m & e f ( a ) = a 1 一；人d a s u b j o c tt o a y = 0 人0 这里y = ( y ，m ) ，d 。= 儿乃x ：x ，是，阶矩阵。 注意到( 2 3 9 ) 中的松弛条件在最优解条件下为： z 【，( w + - x ，+ b ) 一1 】= 0i = 1 ，f 从式( 2 3 1 5 ) 中，我们得到： ( 2 3 1 0 ) ( 2 3 一1 1 ) ( 2 - 3 - 1 4 ) b = y 。一w x 。( 2 - 3 - 1 6 ) 满足约束条件的向量 x ? ，_ y 1 被称为5 劝d ，v o c t o _ r s ，即分类边界上的点，如图 3 所示的位于平行线上的分类边缘点。这些点决定了分类的边界和分类器的性 能。分类超平面可以写作： 弛冲讲妻y ，a t ( x _ + 厂( x ) = s 刮y ，_ ) + 6 + f i _ l 满足( 2 3 8 ) 式的点集( x ，y ) ，表示线性可分，即经验风险为零。 ( 2 3 3 ) 、 ( 2 3 5 ) 、( 2 3 7 ) 式可推导出：在经验风险为零的情形下( 2 3 8 ) ，i i 叫1 2 最小可 使v c 维的上界最小( 2 3 5 ) ，从而最小化v c 维，这正是结构风险最小化原理的应 用。而点集( t ，y ) 中满足( 2 - 3 - 8 ) 式为零的点是一些距离超平面最近的点( 2 - 3 6 ) ，正是这些点决定了数据集合c l a s s l 和c l a s s 2 凸包之间的距离。而将( 2 3 7 ) 代入( 2 3 6 ) 式可得： m a x ( d ( x w ，6 ) ) = 赢硼翘( 2 - 3 - 1 8 ) ( 们，a 2 ) 见图3 。( 2 3 一】8 ) 式可得出的结论是：最小化f j 训2 等价于寻找使不同类集 间距离最大的分类超平面，它使数据集合c l a s s l 和c l a s s 2 凸包之间沿垂直于自己 方向的距离最大，且超平面距离两类相邻点集的距离相等。故上述算法 ( s v m ) 有时也称为最大边缘( m a x i m u mm a r g i n ) 算法，从图3 中可以看到，s v m 分类超平面到相邻点集的距离远大于分类超平面和分类超平面二至相邻点集 的距离。最大边缘思想实质上就是对推广能力的控制，实现在未知分布p ( 置y ) 情况下，小样本的最优分类与预测，保证预测误差最小( 2 2 1 ) 。 图3 标7 佳s v m 算法与普通感知器的分类超平面比较 2 3 2 s 坦非线性分类算法 我们在得出线性分类的s v m 算法基础上，对算法做进一步的扩展，将线性 不可分的输入向量映射到高维的特征空间中，在高维的空间中，对映射后的向 量进行线性分类。被映射的高维空间可能是有限维的，也可能是无限维的。这 种映射可以表示为： ! 璺盟堡奎兰堕圭鲨壅生三童- 墅主兰旦里堡垦翌旦堕壁墨! 上旦 这里， 刍是一些实数，而 九 ：。是一些吏函数。对于s v m 非线性分类( 软边 界1 的算法，可以通过以特征向量丸p ) 替代输入向量石，则s 讧算法变成了以 f 形式： i z ) - s 喈n ( 必z ) w 。十6 ) js i g n ( y 。x t o ( x ) - 西t x 。) 6 1 ) ( 2 - 3 1 9 ) 于是，s v m 的一个关键属性就是内积计算( z ) 乒p ) ，这里，可以很方便的构造 恢函数： k ( x ，y ) = 砂( x ) - 乒( y ) = “飘( x ) 。( y ) ( 2 3 2 0 ) r l 这样，式( 2 3 2 0 ) 可以表示为： i z ) 一s t g n ( ”一舶x ，x b ) ( 2 _ 3 - 2 1 、 2 3 。3 核函数 ：一3 2 0 ) 给出了核函数的定义，o ；s v m 算法中不同的内积函数将形成不同 的算法。 j 前，研究最多的卜鬻有三炎，是多项式按函数， k ( x ，x 。) = f - x 。) 1 r ；2 - 3 - 2 2 ) 足￥阶多项式的核函数，将( 2 - 3 2 2 ) 阶：移项式的分类器；第二类是径向基函数( i u 弭) 、，f 卜一 引矗一r q 砷r 一一j ( 2 - 3 2 2 ) 代入( 2 - 3 - 2 1 ) ，便得到q ( 2 3 2 3 ) 所得的分类器与神经网络r 1 3 f 算法根本的区别：每个径向基函数的中心列应 一r 支持向量，网络结构及其网络权值由算法自动确定。第三类孩函数称作 s i g m o i d 函数，即 k ( x ，* ) = = t a n h ( v ( x - z ，) 十g 】 ( 2 - 3 2 4 ) 这时的s v m 算法中包含了个隐层的多层感知器，隐层结点数是由算法自动 确定的，而且算法不存在困扰神经网络的局部极小点的问题。 s v m 核函数方法给了我们乍、非常重要的启示：用内积运算实现某种非 线性运算。核函数的种类很多，上面提到的只是最基本的三种，还有很多非 常有用的核函数将在以后章节中陆续介绍。 关于按函数的选择，一直是困扰s v m 算法发展的一大障碍，很多文章都 是针对具体问题提出核函数的选择方法，虽然很有价值，但难以推广到一般 性的问题，本文将在最后一章，提出一种利用遗传规划( g e n e t i c p r o g r a m m i n g ) 选择核函数的一般性方法，作为探讨性的研究。 生里整兰塾查查兰堡主堡塞j 鳖望l 丝生兰翌堡垒垦墅垡堡! 鎏! 丝 2 4 本章小结 s v m 是一种基于结构化风险原理的新的学习算法，它比基于经验风险原理 的神经网络学习算法具有更强的理论依据和更好的推广性能，对线性可分问题 的应用充分说明了这一点。另外对非线性问题的处理，s v m 也有自己较完整的 理论。由于分类问题是人工智能领域最基本的问题之一，我们相信s v m 以及v c 理论必将对人工智能的众多学科产生重要影响a ! 旦型兰塾查查堂竖主笙塞蔓三兰墨王坠尘垡堂堂丝堕塾墨盟垫焦墨鳖 第三章基于s v m 理论优化感知器的 遗传算法 3 1 引言 如何构造合理的分类超平面是推动模式识别发展的最终动力 v a p n i k 1 9 8 2 p 3 6 4 。感知器和b p 网络的问世奠定了神经网络发展的基础。但 是，感知器和b e n 络及其它的神经网络都有其算法自身难以克服的致命弱 点：如隐单元的个数难以确定，网络的最终权值受初始值影响大。数据处理 能力差，片面强调克服训练错误，忽视了泛化性能的定量研究，且人工神经 网络是建立在经验非线性模型基础之上，缺乏统一的数学理论框架 v a p n i k ， 1 9 9 5 ，模型结构及其参数常常会随初值及人为的因素变化而变化，令使用者 无从选择，而且，因为过分地强调分类错误，造成模型的预测性能降低。这 种训练过分强调克服学习错误，而忽略了数据的预测和推广性能，使神经网 络陷入局部收敛之中，直接影响了网络的整体性能，这是目前神经网络所暴 露的一个致命弱点。 建立在传统的统计学基础之上的其他分类算法，只有在足够多的样本前 提下，其算法才是合理的。而当训练的是小样本数据集时，再沿用相应的分 类算法显然缺乏严格的理论依据 v a p n i k ，1 9 9 5 3 ； 与传统统计学相比，统计学习理论( 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 ) 是 一种专门研究小样本情况下机器学习规律的理论 v a p n i k ，1 9 9 5 ：v a p n i k 。1 9 9 8 1 。v v a p n i k 等人从六、七十年代开始致力于此方面 的研究 v a p n i k ，1 9 6 3 ：v a p n i k ，1 9 6 8 ，到九十年代中期，其理论不断发展和成 熟，并在此理论框架下，v v a p n i k 等人提出了一种新的通用算法一s v m ( s u p p o r tv e c t o rm a c h i n e s ) 算法。该算法有效地改善了传统分类方法的缺陷 ( 比如神经网络结构选择问题、局部极小点问题) ，它巧妙地解决了统计学 习理论中结构风险最小化原理和v c 维( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) 理论 的算法具体实现问题 v a p n i k ，1 9 7 1 ，具有较强的理论依据。 但是，经典的s v m 算法是将分类问题转化为二次规划问题f v a p n i k1 9 9 5 1 来 实现分类超平面的优化。由于二次规划的计算量随着变量的增加而呈指数增 加，且有正定、闭凸集的约束要求，这就限制了s v m 算法的应用。对于大数 据量的模式分类问题，如何提高它的数据处理的实时性、缩短训练样本的时 间，仍是亟待解决的问题。 借助于s v m 理论所特有的几何特征，本文提出一种遗传算法，将感知器 的分类算法与遗传算法的全局寻优有效地结合起来，利用s v m 理论的几何特 征来构造遗传算法的适应度函数，用统计学习理论来指导遗传算法的优化过 程。通过遗传算法优化感知器分类算法中的连接权，避免了传统的感知器分 类的偏向性，连接权的局部收敛性，以及误识率高等弱点；借助于遗传算法 主旦型堂垫查盔兰竖主堕塞 至三童董主! 旦型墅垒垡丝堕塑墨堕望堡苎生 全局寻优的特点【c h e n ，1 9 9 6 1 ，使改进后的算法，具有自进化、自适应能力，以 及很好的数据推广性能和抗干扰性，提高了神经网络的整体性能。同时本文 提出的算法继承了s v m 算法的理论依据和现有的感知器算法。与标准的感知 器算法相比，它提高了泛化性能；与s v m 算法相比，可以不受正定、闭凸集 的约束要求的限制，扩大的应用范围，可获得线性及非线性分类问题的近似 最优解。 神经网络与遗传算法相结合早已受到人们的普遍重视，这两种方法都是 效仿生物处理模式以获取智能信息处理功能的理论 c h e n ，1 9 9 6 。其中，神经网 络方法着眼于人脑的微观网络结构，通过大量神经元网络的复杂连接，采用 自底至顶的方法，通过自学习、自组织和非线性动力系统的并行方式，来处 理难以语言化的模式信息，且具有很好的局部收敛性能。目前，各种标准的 神经网络算法已非常成熟，并广泛应用于各个领域。遗传算法则是模拟生物 的进化现象( 自然淘汰、交叉、变异等) ，并采用自然进化机制来表现复杂 现象的一种概率搜