（应用数学专业论文）新的支持向量机增量学习算法.pdf

摘要 由v a p n i k 等人所提出的支持向量机自1 9 9 2 年在计算学习理论会议上进入机 器学习领域之后，便受到了不少业内学者的密切关注。支持向量机是建立在统计 学习理论和结构风险最小化原则基础上的一种全新的机器学习方法，集优化、核、 最佳推广能力等特点于一身，有着很好的学习性能和泛化能力，目前已经成功并 广泛的应用于许多领域，现已成为机器学习和数据挖掘领域的标准学习工具。 但是在实际问题中，样本的采集及对样本的认知都是一个逐步积累的过程， 因此新增训练样本对于实际问题来说是常见而又合理的。增量学习技术是一种得 到广泛应用的智能化数据挖掘与知识发现技术，它基于历史的学习结果对新增加 的数据进行再学习，使得学习具有一定的连续性。 运用增量学习的思想进行支持向量机增量学习，现有的简单支持向量机增量 学习算法大部分都没有充分考虑到新增样本对初始样本集中位于支持向量附近的 非支持向量的影响，致使一些有用的历史数据过早的被淘汰，从而严重影响分类 的精度。针对这一问题提出了一种新的s v m 增量学习算法一寻找最近点s v m 增量学习算法，该算法有效利用了支持向量附近的非支持向量，先找出原样本中 距离支持向量最近的非支持向量作为训练集的一部分，再结合s v m 寻优问题的条 件和样本之间的关系，对训练数据进行有效的遗忘淘汰。对标准数据集的试验结 果表明，该算法在新样本集加入后有效的压缩了整个样本集的大小，淘汰无用的 样本，减少了对存储空间的占用，在保证了训练速度的同时训练精度有了明显的 提高。 关键词：支持向量机增量学习算法分类广义k k t 条件 a b s t r a c t t h es u p p o r tv e c t o rm a c h i n e ( s v m ) w h i c hi sp r o p o s e db yv a p n i ka n do t h e r sh a s r e c e i v e dm a n ys c h o l a r s c l o s ea t t e n t i o ns i n c ei th a sb e e np r o g r e s s e di n t ot h em a c h i n e l e a m i n gd o m a i na f t e rt h ec a l c u l a t i o nt h e o r e t i c a ls t u d ys e s s i o ni n19 9 2 s u p p o r tv e c t o r m a c h i n ei san e wm a c h i n el e a r n i n gm e t h o db 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 ya n d s t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e ，s e t t i n go p t i m i z a t i o n ，k e r n e lf u n c t i o n ，t h eb e s t g e n e r a l i z a t i o na b i l i t ya n do t h e rc h a r a c t e r i s t i c s i no n e ，h a sav e r yg o o dl e a m i n g p e r f o r m a n c ea n dg e n e r a l i z a t i o nc a p a b i l i t i e s ，s u c c e s s f u l l ya n dw i d e l yu s e di nm a n y f i e l d s ，i th a sb e c a m et h es t a n d a r dt o o l si nt h em a c h i n el e a r n i n ga n dd a t am i n i n gf i e l d h o w e v e r , i np r a c t i c a lp r o b l e m s ，t h es a m p l ea c q u i s i t i o na n du n d e r s t a n d i n gi s a p r o c e s so fg r a d u a la c c u m u l a t i o n , t h e r e f o r e ，a d d i t i o no ft h et r a i n i n gs a m p l e sf o rt h e p r a c t i c a lp r o b l e mi s c o m m o na n dr e a s o n a b l e i n c r e m e n t a ll e a r n i n gt e c h n o l o g yi sa w i d e l yu s e di n t e l l i g e n td a t am i n i n ga n dk n o w l e d g ed i s c o v e r yt e c h n o l o g y , w h i c hi s b a s e do nt h eh i s t o r i c a ll e a r n i n gr e s u l t st os t u d yt h en e w l ya d d e dd a t a ，m a k i n gt h e l e a r n i n gh a sac e r t a i nd e g r e eo fc o n t i n u i t y m a t c ht h ei n c r e m e n t a ls v ml e a r n i n gw i t ht h et h i n k i n go fi n c r e m e n t a ll e a r n i n g ， m o s to ft h ee x i s t i n gs i m p l ei n c r e m e n t a ls v ml e a r n i n ga l g o r i t h m sd on o tf u l l yt a k ei n t o a c c o u n tt h ei m p a c to fa d d i t i o n a ls a m p l e st ot h en o n - s u p p o r tv e c t o r sn e a r b yt h es u p p o r t v e c t o r si n i n i t i a ls a m p l es e t r e s u l t e di ns o m eu s e f u lh i s t o r i c a ld a t at ob ee l i m i n a t e d e a r l y , a n da f f e c tt h ec l a s s i f i c a t i o na c c u r a c y p o i n tt ot h ed e f a u l t ，an o v e li n c r e m e n t a ls v ml e a r n i n ga l g o r i t h mi sp r e s e n t e d ， w h i c hi sc a l l e d f i n d i n gt h en e a r e s tp o i n t i n c r e m e n t a ls v ml e a r n i n ga l g o r i t h m ， i d e n t i f y i n gt h en o n s u p p o r tv e c t o r sw h i c h a r en e a r e s tt os u p p o r tv e c t o r sf r o mt h ei n i t i a l s a m p l es e ta sp a r to ft h ef i n a ls a m p l es e tf i r s t l y , c o m b i n e dw i t ht h er e l a t i o n s h i pb e t w e e n t h ek k tc o n d i t i o no fs v mo p t i m i z a t i o na n dt h es a m p l e s ，f o r g e t t i n ga n de l i m i n a t i n g t h et r a i n i n gd a t ae f f e c t i v e l y t h et e s tt os t a n d a r dd a t as e t ss h o w st h a tt h i sa l g o r i t h mc a n r e d u c et h es i z eo ft h ee n t i r es a m p l es e te f f e c t i v e l y , e l i m i n a t eu s e l e s ss a m p l e s ，r e d u c et h e o c c u p a t i o no fs t o r a g er o o m ，i tn o to n l ye n s u r et h et r a i n i n gs p e e db u ta l s oi m p r o v et h e t r a i n i n ga c c u r a c ys i g n i f i c a n t l y k e y w o r d s ：s u p p o r t v e c t o rm a c h i n ei n c r e m e n t a ll e a r n i n gc l a s s i f i c a t i o n g e n e r a l i z e dk k tc o n d i t i o n 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人 在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究 成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的 说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。( 保密的 论文在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：羔蓥 导师签名：压3 r 监萎 第一章绪论 第一章绪论 本章首先从论文题目的选题背景和研究意义出发，介绍支持向量机的研究现 状，最后给出论文的大致结构内容安排。 1 1 选题背景及研究意义 基于数据的机器学习是现代智能技术中的重要组成部分，机器学习是一门研 究机器获取新知识和新技能并识别现有知识的学问。机器学习的主要思想是从已 知数据( 样本) 出发寻找规律，然后利用这些规律对未来数据或者未知的数据进 行预测，在相关学科的研究与实际应用中起着主导作用。本课题来源于国家自然 科学基金( 项目编号：6 0 6 0 3 0 9 8 ) 。到目前为止，机器学习的实现方法可以分为以下 三种： 第一种是经典的( 参数) 统计估计方法( t h ec l a s s i c ( p a r a m e t e r s ) s t a t i s t i c a l e s t i m a t i o n ) 。统计学是包括模式识别、神经网络等在内的现有机器学习方法共同的 重要理论基础之一。经典的( 参数) 统计估计方法正是基于传统统计学发展起来 的机器学习方法，在这种方法中，参数的相关形式是已知的，训练样本用来估计 参数的值。尽管这种方法的形式很简单但却有很大的局限性：一方面，它需要花 费很大代价，因为它需要己知样本的分布形式；另一方面，传统统计学研究的是 样本数目趋于无穷大时的渐近理论，并且现有的学习方法也多是基于此假设，但 在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法在实际 应用中的表现却可能不尽人意。 第二种是经验非线性方法，这种方法的典型代表就是人工神经网络( a r t i f i c i a l n e u r a ln e t w o r k ，a n n ) 。这种方法利用已知样本建立非线性模型，克服了传统参 数估计方法的困难。但是这种方法也有一定的缺点：首先，这种方法缺乏一种统 一的数学理论基础，算法容易在局部极小值点处被“卡住”，大大影响算法的效果； 其次，网络的泛化能力不强，缺乏一种有理论依据的严格设计程序的思路，算法 结构的设计在很大程度上取决于设计者的经验和先验知识。这些网络在原有的框 架内之所以能够取得很多成功的应用，主要原因在于这些应用的设计者在设计过 程中很好的运用了自己的经验和先验知识。 第三种是统计学习理论( 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 ) 。与传统统计学相 比，统计学习理论是一种专门研究小样本情况下机器学习规律的理论，针对小样 本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了 2 新的支持向量机增量学习算法 对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。v v a p n i k 等人从二十世纪六、七十年代开始致力于此方面研究，到九十年代中期，随着其 理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性的进展， 统计学习理论开始受到越来越广泛的重视。统计学习理论能将很多现有方法纳入 其中，为解决有限样本学习问题提供一个统一的框架，能够帮助解决许多原来难 以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) ；同时，在这一 理论基础上发展起来的一种新的通用学习方法支持向量机( s u p p o r tv e c t o r m a c h i n e ，s v m ) ，已初步表现出很多优于已有方法的性能，成功并广泛地应用于 相关领域。一些学者认为，s l t 和s v m 正在成为继神经网络研究之后新的研究热 点，并将推动机器学习理论和技术的重大发展。 支持向量机与神经网络类似，都是学习型的机制，但与神经网络不同的是s v m 使用的是数学方法和优化技术。支持向量机( s v m ) 是数据挖掘中的一个新方法，能 非常成功地处理回归问题( 时间序列分析) 和模式识别( 分类问题、判别分析) 等诸多 问题，并可推广于预测和综合评价等领域，因此可应用于理科、工科和管理等多 种学科。目前国际上支持向量机在理论研究和实际应用两方面都正处于飞速发展 阶段，它广泛地应用于统计分类以及回归分析中。目前，s v m 算法在模式识别、 回归估计、概率密度函数估计等方面都有应用，例如在模式识别方面，对于手写 数字识别、语音识别、人脸图像识别、文章分类等问题，s v m 算法在精度上已经 超过传统的学习算法或与之不相上下。 1 2 研究现状 由v a p n i k 及其合作者所提出的支持向量机自1 9 9 2 年在计算学习理论会议上进 入机器学习领域之后，便受到了不少学者的密切关注。支持向量机是建立在统计 学习理论和结构风险最小化原则基础之上的一种全新的机器学习方法，有着很好 的学习性能和泛化能力，广泛并成功的应用于许多领域，现已成为机器学习和数 据挖掘领域的标准工具。但是支持向量机的应用也有一定的限制条件，随着样本 数量的增加以及新增样本的出现，现有的支持向量机算法会出现空间和时间复杂 度增加等问题，从而无法进行增量学习。基于这种情况，支持向量机增量学习算 法的提出具有重要意义。 现有的增量学习方法【2 3 】大多采用决策树算法和神经网络算法实现，一般有以 下两方面的缺点：一是缺乏对整个样本集期望风险的控制，算法对训练数据易于 产生过量匹配；二是由于缺乏对以往训练数据有选择的淘汰机制，在很大程度上 影响了分类精度。基于结构风险最小化理论( s r m ) 理论的s v m 学习算法【4 5 】是少数 可以成功解决第一个问题的学习算法。n a s y e d 与n l i b 6 , 7 】提出了一种s v m 增量 第一章绪论 3 训练算法。该算法直接通过支持向量实现增量学习，即每次只选一小批常规二次 规划算法能处理的训练样本，然后保留其中的支持向量，完全淘汰抛弃非支持向 量，和新增加的样本混合进行训练，直到处理完全部训练样本集。这种方法简洁 高速，但其缺点在于过于依赖历史训练集中的支持向量，这将导致一些有用的历 史信息的过早损耗，直接影响后续的学习的训练精度，实现的只是近似的增量学 习。e m i t r a 和c a m u r t h y 等人【8 】利用统计力学上的a d m o m 方法训练支持向量机 种的系数口，将系数口的求解看成系统由不稳定态到稳定态变化的过程。与s v m 算法对比实验表明，此方法可以在很大程度上提高运算速度。由a d a t o m 算法改进 得出的k e r n e l a d a t r o n 算法，通过在线学习构建了大边际超平面，该算法实现简单， 但只是对于可分数据集有效。c d o m e n t c o m 和d g u n o p u l o s 9 】提出了增量式求解全 局优化问题精确解的方法，该方法对于增加一个样本或者减少一个样本对拉格朗 日系数和支持向量的影响进行分析，并从理论角度证明算法是有效的，从全局优 化的角度对算法进行了改进。 1 3 1 本文的主要工作 1 3 本文主要工作及内容安排 在支持向量机的的分类问题中，以往的支持向量机增量学习算法在对初始样 本按照一定的规则进行选择淘汰的时候，对支持向量附近的非支持向量的处理过 于粗糙。对于有新增样本加入的数据集来说，由于新增样本的加入而改变了原分 类机对数据的初始规划，其中位于分类间隔上的边界向量在很大程度上决定了新 的支持向量分类机，也就是说，原样本集中位于支持向量附近的非支持向量很有 可能成为有新样本加入之后的新样本集中的支持向量。 本文充分考虑到新增样本对初始样本集中位于支持向量附近的非支持向量的 影响，基于分类样本集与k k t 条件的关系提出了一种新的s v m 增量学习算法。 该算法先找出原样本中距离支持向量最近的非支持向量作为训练集的一部分，再 结合s v m 寻优问题的k k t 条件和样本之间的关系，以达到对训练数据进行有效 的遗忘淘汰的目的。对标准数据集的试验结果表明，该算法在新样本集加入后有 效的压缩了整个样本集的大小，淘汰无用的样本，在保证了训练速度的同时又提 高训练精度。 1 3 2 本文的内容安排 本文的主要内容分为五章，各章的内容简单概括如下： 4 新的支持向量机增量学习算法 第一章为绪论部分，先是介绍了论文的选题来源及研究背景，阐述了所选课 题的意义所在，然后简单介绍了支持向量机增量学习的研究现状，最后总结了本 文所要做的主要工作。 第二章给出了支持向量机增量学习的理论准备，先简单介绍了增量学习的主 要思想和其本身所具有的优势，再给出了支持向量机的基本原理及优点，最后给 出最优化问题的一个关键理论豚丁条件。 第三章支持向量机的相关算法概述，首先根据数据本身的分布特点，给出了 对于线性可分、线性不可分和非线性可分这三种情况下的支持向量机标准算法； 随后又给出了对于海量数据的s v m 算法，如选块算法、分解算法和序列最小最优 化算法。 第四章介绍了支持向量机增量学习算法，注意到简单的支持向量机增量学习 算法中存在的弊端，并根据原训练样本集中支持向量与非支持向量的相对几何分 布特征，提出了一种新的支持向量机增量学习算法寻找最近点支持向量机增 量学习算法。 第五章利用u c i 数据库的标准数据进行实验，将文中所提出的新s v m 增量学 习算法分别与标准s v m 算法( 以s m o 算法为例) 和一般的增量学习算法作一个 比较，通过表格和图像给出试验结果并对结果进行分析和比较，总结出新算法在 分类精度方面的优势。 最后是对本文的总结和对支持向量机增量学习算法前景的展望。 第二章支持向量机增鼍学习的基本理论 第二章支持向量机增量学习的基本理论 基于样本的机器学习问题是现代人工智能学习领域的一个重要分支，它模拟 了人类从实例中的学习归纳能力，通过对现有的观测数据集( 也就是所谓的样本 集) 进行探索研究，获得目前尚不能通过原理分析得到的规律，并利用这些规律 去分析后续的未知数据，对无法直接观测的新现象进行预测和判断。9 0 年代初期， 有限样本的机器学习理论逐渐成熟起来，形成了一个较为完善的理论体系统 计学习理论( s t a t i s t i cl e a r n i n gt h e o r y ，简称s l t ) t l o l 。支持向量机( s u p p o r tv e c t o r m a c h i n e ，s v m ) 是建立在统计学理论最新进展基础上的新一代学习系统。它以正 则化技术的研究成果为基础，在若干实际应用( 如文本编目、手写字符识别、图 像分类和生物进化链分析等) 中表现出最佳的学习性能，并且在机器学习与数据 挖掘中已被确立为一种标准工具。在数学方法和应用技术两个方面都可能成为一 座真正的科学金矿。目前，s l t 与在此基础上发展起来的s v m 机器学习方法成为 机器学习领域新的研究热点。接下来给出s l t 以及s v m 的相关基本理论。 2 1 统计学习理论 统计学习理论的基本内容诞生于2 0 世纪6 0 - - 7 0 年代，到9 0 年代中期发展得 比较成熟并受到世界机器学习界的广泛重视，是研究利用经验数据进行机器学习 的一种一般理论，属于计算机科学、模式识别和应用统计学相互交叉与结合的范 畴。统计学习理论是针对小样本情况研究统计学习规律的理论，是传统统计学的 重要发展和补充，为研究有限样本情况下机器学习的理论和方法提供了理论框架。 其核心思想是通过控制学习机器的容量来实现很多理论和实践上的优势【1 2 】。在这 一理论中发展出来的支持向量机方法是一种新的通用学习机器，较以往方法表现 出很多理论和实践上的优势。 v c 维是s l t 中的一个重要概念，被认为是数学和计算机科学中非常重要的定 量化概念，它可用来刻画分类系统的性能。我们知道在学习算法中需要选择适当 的假设集f 。实际上，这里的关键因素是假设集f 的大小，或f 的丰富程度，或 者说，的“表达能力 。由v v a p n i k 和a c h e r v o n e n k i s 1 3 。5 】提出来的v c 维，是对 这种“表达能力 的一种描述。v c 维反映了函数集的学习能力，v c 维越大则学 习机器越复杂( 容量越大) ，所以v c 维又是学习机器复杂程度的一种衡量。v c 维的概念是为了研究学习过程一致收敛的速度和推广性，是由统计学习理论定义 的有关函数集学习性能的一个重要指标。 6 新的支持向量机增量学习算法 我们知道当假设集，的v c 维有限时，经验风险最小化( e r m ) 1 6 j 归纳原则 是一致的，显然这是当样本数，趋于无穷大时的性质。然而，我们通常考虑的是样 本点个数有限的情况。然而在样本点个数有限时，仅仅用经验风险来近似期望风 险是行不通的。结构风险是期望风险的一个上界，这个上界是经验风险和置信区 间的和。我们知道经验风险依赖于厂的选择，而置信区间则是，的v c 维的增函 数。粗略地说，当集合f 比较大时，可以选到适当的厂，使得。i f 】比较小，而 此时由于f 的v c 维比较大，也会使置信区间比较大。反之，当缩小集合f 时， 的v c 维会降低，置信区间会变小，而疋。 门可能增大。两者此消彼长，有互相 矛盾的倾向，为了选出兼顾二者的假设，引进了结构风险最小化原则。 实现结构风险最小化原则证据要有两种思路：第一种思路是从每一个子集入 手，也就是说在每个子集中求最小经验风险，然后选择使得经验风险和置信区间 之和最小的子集。很显然，这种方法比较费时，当子集数目很大甚至是无穷的时 候这种方法不可行。第二种思路是设计函数集的某种结构使每个子集中都能取得 最小的经验风险( 如使训练误差为0 ) ，然后只需选择选择适当的子集使置信区间最 小，则这个子集中使经验风险最小的函数即为最优函数。支持向量机方法实际上 就是这种思想的具体体现。 2 2 支持向量机( s v m ) 的相关理论 2 2 1 支持向量机( s v m ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是由v a p n i k 领导的a t & t b e l l 实验 室研究小组在1 9 6 3 年提出的一种新的非常有潜力的分类技术，s v m 是一种基于统 计学习理论的模式识别方法，主要应用于模式识别领域。由于当时这些研究尚不 十分完善，在解决模式识别问题中往往趋于保守，且数学上比较艰涩，这些研究 一直没有得到充分的重视。直到9 0 年代，统计学习理论( s t a t i s t i c a ll e a r n i n g t h e o r y ， s l t ) 的实现和由于神经网络等较新兴的机器学习方法的研究遇到一些重要的困 难，比如如何确定网络结构的问题、过学习与欠学习问题、局部极小点问题等， 才使得s v m 迅速发展和完善，在解决小样本、非线性及高维模式识别问题中表现 出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。从此迅 速的发展起来，现在已经在许多领域( 生物信息学，文本和手写识别等领域) 都 取得了成功的应用。 支持向量机是由一种以统计学习理论和w o l f 对偶规划理论为背景，借助最优 化方法来解决机器学习问题，充分体现了统计学习理论中的结构风险最小化原则， 集优化、核、最佳推广能力等特点于一身的新的分类和函数估计方法。它是建立 第二章支持向量机增量学习的基本理论 7 在统计学习理论的v c 维理论和结构风险最小原理基础上的，根据有限的样本信息 在对特定训练样本的学习精度和学习能力之间寻求最佳折衷，以期获得最好的泛 化能力和推广能力。与传统学习方法相比，s v m 具有较好的学习性能和泛化能力， 能够较好地解决小样本、高维数、非线性、局部极小等问题，现已成为机器学习 和数据挖掘领域的标准工具。支持向量机主要有以下优点【1 7 , 1 8 】： ( 1 ) 组成网络的结构相对简单，是专门针对有限样本情况的，其目标是得到现有 信息下的最优解，而不仅仅是样本数趋于无穷大时的最优值； ( 2 ) 算法最终将转化成为一个约束条件下的凸二次型寻优问题，从理论上说，得 到的将是全局最优点，解决了在神经网络方法中无法避免的局部极小化问题； ( 3 ) 算法只需要更换核函数就可以得到各种不同的分类曲面，可以适应不同的数 据类型，从而保证了算法具有优良的分类性能和较好的泛化能力； ( 4 ) 算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e ) ，在高 维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证 机器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维 数无关，只取决于支持向量的个数。 支持向量机的理论最初来自于对数据二分类问题的处理，在线性可分问题中， s v m 考虑寻找一个满足分类要求的分类超平面，并使训练集中的点距离该分类超 平面尽可能地远，即寻找一个分割平面，使其两侧的空白区域尽可能的大，空白 区域越大表示其泛化能力越强。对于线性不可分的情况，可以选择一个映射把低 维输入空间中线性不可分的样本映射到高维属性空间( 一般来说，它是一个h i l b e r t 空间) 使其线性可分，从而使得在高维属性空间采用线性算法对样本的非线性特 性进行分析成为可能。 我们通常希望分类的过程是一个机器学习的过程。这些数据点是栉维实空间中 的点。我们希望能够把这些点通过一个n 一1 维的超平面分开。通常这个被称为线 性分类器。有很多分类器都符合这个要求。但是我们还希望找到分类最佳的平面， 即使得属于两个不同类的数据点间隔最大的那个面，该面亦称为最大间隔超平面。 如果我们能够找到这个面，那么这个分类器就称为最大间隔分类器。 s v m 的关键在于核函数。低维空间向量集通常难于划分，解决的方法是将它 们映射到高维空间。但这个办法带来的困难就是计算复杂度的增加，而核函数正 好巧妙地解决了这个问题。也就是说，只要选用适当的核函数，就可以得到高维 空间的分类函数。在s v m 理论中，采用不同的核函数将导致不同的s v m 算法。 在s v m 方法中，只要定义不同的内积函数，就可以实现多项式逼近、贝叶斯分类 器、径向基函数( r a d i a lb a s i cf u n c t i o n 或r b f ) 方法、多层感知器网络等许多现有 学习算法。 新的支持向量机增量学习算法 2 2 2 支持向量( s v ) 支持向量机的泛化性能并不依赖于全部训练数据，而仅依赖于最优化问题的 最优解的非零分量所对应的训练点，即支持向量( s u p p o r tv e c t o r ，s v ) ，而与非支 持向量无关。所谓支持向量就是指训练集中某些训练点的输入五。事实上，最优 化问题 1， m 。i n吉咒y ，q 吩( 而_ ) 一q ， ( 2 - z o ) 1 = ij - , i j - 上 j j y , a t = 0 ( 2 - 1 1 ) i - i q 0 ，f = l ，( 2 1 2 ) 的解口的每一个分量口? 都与一个训练点相对应，而由一系列的算法所构造的分类 超平面，仅仅依赖与那些相应于彳不为零的训练点( 五，乃) ，而于相应于西为零的 那些训练点无关。所以我们特别关心相应于西不为零的训练点( 鼍，咒) ，并称这些 训练点的输入五为支持向量。 在最优超平面的求解过程中，v a p n i k 证明，最优分类超平面的法向量可以表 示为支持向量的线性组合，h p ： 萨c r t y i x f ，0 c ( 2 - 1 3 ) 其中1 ，是支持向量集。显然，只有支持向量对最终求得的分类超平面的法方 向缈有影响，而与非支持向量无关。也就是说支持向量集可以充分描述整个样本 集的特征，它具有和样本空间等价的分类特性。通常情况下，当训练集中的样本 点较多时，支持向量所占的比例并不大，大部分都是非支持向量，即优化对偶问 题的解口+ 的大部分分量是零，相应的这些非支持向量对于决策函数没有贡献。这 一事实体现了问题的稀疏性，因此可以通过对支持向量集的训练来取代对原训练 样本集进行分类学习，在不影响分类精度的同时可以极大地减少训练时间，提高 训练速度。 以下给出关于支持向量的性质的一个定理： 定理2 1 支持向量具有以下性质： ( i ) 界内的支持向量一定位于间隔边界上的正确划分区； ( i i ) 支持向量不会出现在间隔以外的正确划分区； ( i i i ) 非支持向量一定位于带有间隔的正确划分区。 接下来给出定理2 1 的推论： 推论2 2 ( i ) 不属于带有间隔的正确划分区的输入必定是支持向量； 第二章支持向量机增量学习的基本理论 9 题： ( i i ) 属于间隔以外的正确划分区的输入必定不是支持向量。 此定理及推论证明见参考文献【1 6 】：1 8 5 。 2 3 。1k 研条侮 2 3 最优化问题的胱r 条件 对于分类问题，支持向量机把分类边界最大最终归结为如下凸半正定规划问 m a xw ( a ) = a , 一藐o 【p j y i y j k b l ，x 3 i = 1 ，。，= i ， 趴t f f i y t = 0 t = 1 【0 ，c 】，i = 1 ， 决策函数为： ， y = s 咖 q 咒k ( 薯，工) + 6 ) f = i ( 2 1 4 ) ( 2 1 5 ) 当且仅当每一个z 都满足如t k k t 条件，口= q ，a 2 ，q 】才是上述规划的最 优解： i q = 0 j y f f ( x ，) l 0 呸 c j y t f ( x f ) = l( 2 - 1 6 ) 【哆= c y f f ( x f ) 1 f = o j f ( x t ) 1 彭( 玉) - - 1 即： 0 q c j f ( x t ) = l 蜀矿( 而) = - 1 ( 2 1 7 ) i q = c j - 1 厂( 五) s l 周伟达等人在文献【1 9 】中证明了下面的这个定理 定理2 3 厂( 石) 为s v m 分类决策函数， 五，咒 为新增样本。满足尼汀条件的 新增样本将不会改变支持向量集：而违背k k t 条件的新增样本将使得支持向量集 发生变化。 假设第n 步增量学习后的决策函数为厂( 功，( 玉，儿) 为新增样本，违背k k t 条 l o 新的支持向量机增量学习算法 件可以分为如下3 种类型： ( 1 ) ( 玉，乃) 位于分类间隔中，与本类样本在分类边界同侧，可以被原分类 器正确分类，满足o 咒厂( 薯) 0 ，构造