（计算机应用技术专业论文）支持向量机分类器及其贝叶斯框架研究.pdf

支持向量机分类器及其贝叶斯框架研究 摘要 基于统计学习理论的支持向量机是当前机器学习领域的一个研究热点。它 具有良好的泛化性能、可解决非线性问题、具有稀疏性和全局最优解等优点， 但在标准分类模型和参数选择方面仍值得研究，本文的主要工作如下： ( 1 ) 从支持向量的角度，提出一个基于同心超球面分割的支持向量预抽取 方法。利用预抽取的支持向量代替整个数据集进行训练，可以有效的降低计算 量。 ( 2 ) 损失函数是支持向量机风险泛函的关键部分，选择不同的损失函数可 以构造不同类型的支持向量机。本文对三角函数进行了改进，并推导出相应的 支持向量机分类的原始问题和对偶问题。 ( 3 ) 集成学习是当前机器学习的一个研究热点，它可以提高分类算法的泛 化性能。本文利用b o o s t i n g 对支持向量机进行集成学习，并给出了一种基于 b o o s t i n g 的支持向量机组合分类器。 ( 4 ) 对支持向量机分类的贝叶斯框架进行了系统的理论阐述。由于再生核 希尔伯特空间与随机过程之间存在对偶性，因此可以通过高斯过程为支持向量 机建立一个贝叶斯框架，从而利用贝叶斯方法来实现最优参数的选择。 关键词：支持向量机；分类；超球面分割；损失函数；集成学习；贝叶斯方法 r e s e a r c ho ns u p p o r tv e c t o rm a c h i n ec l a s s i f i e ra n di t s b a y e s i a nf r a m e w o r k a b s t r a c t c u r r e n t l y ，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 hb a s e d o ns t a t i s t i c a l l e a r n i n gt h e o r y i sar e s e a r c h h o t s p o t i t h a s m a n ym e r i t s ，s u c h a sg o o d g e n e r a l i z a t i o np e r f o r m a n c e ，r e s o l v i n gn o n - l i n e a rp r o b l e m ，s p a r s ep r e s e n t a t i o na n d g l o b a lo p t i m a l s o l u t i o ne t c b u t s t a n d a r dc l a s s i f i c a t i o nm o d e la n dp a r a m e t e r s s e l e c t i o ns h o u l db er e s e a r c h e ds t i l l ，a n dt h em a i nw o r ki nt h i st h e s i si sa sf o l l o w ： ( 1 ) f r o ms u p p o r tv e c t o r sv i e w ，t h em e t h o do fp r e e x t r a c t i n gs u p p o r tv e c t o r s b a s e do nc o n c e n t r i ch y p e r s p h e r e sd i v i s i o ni s p r o p o s e d t h ee x t r a c t e ds u p p o r t v e c t o r sc a nb et r a i n e di n s t e a do ft o t a ld a t as e t ，s oc o m p u t a t i o n a lc o s tw i l lb e r e d u c e d ( 2 ) t h el o s sf u n c t i o ni sv e r yi m p o r t a n tt or i s kf u n c t i o n a lo ft h es v m v a r i o u s s v m sc a nb ec o n s t r u c t e dw i t hd i f f e r e n tl o s sf u n c t i o n s i nt h i st h e s i s ，s o m e i m p r o v e m e n t sa r eg i v e nf o rt r i g o n o m e t r i cf u n c t i o n ，a n dt h ep r i m a la n dd u a l p r o b l e mo fc o r r e s p o n d i n gs v m a r ed e d u c e d ( 3 ) e n s e m b l el e a r n i n gi sar e s e a r c hh o t s p o ti nm a c h i n el e a r n i n g ，w h i c hc a n i m p r o v eg e n e r a l i z a t i o np e r f o r m a n c eo fc l a s s i f i c a t i o na l g o r i t h m i n t h i st h e s i s ， b o o s t i n gi s i n t r o d u c e dt ot h es v m ，a n ds u p p o r tv e c t o rm a c h i n e sc o m b i n a t i o n c l a s s i f i e ri sp r o p o s e d ( 4 ) b a y e s i a nf r a m e w o r kf o rs u p p o r tv e c t o rm a c h i n ei n c l a s s i f i c a t i o ni s t h e o r e t i c a l l yd e s c r i b e d d u et o t h ed u a l i t yb e t w e e nr e p r o d u c i n gk e r n e lh i l b e r t s p a c ea n ds t o c h a s t i cp r o c e s s e s ，b a y e s i a nf r a m e w o r kc a nb ed e s i g n e df o rs u p p o r t v e c t o rm a c h i n e sw i t hg a u s s i a np r o c e s s t h e r e f o r e ，o p t i m a lp a r a m e t e r so ft h es v m c a nb es e l e c t e db yb a y e s i a nm e t h o d 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 ；c l a s s i f i c a t i o n ；h y p e r s p h e r e sd i v i s i o n ；l o s s f u n c t i o n ；e n s e m b l el e a r n i n g ；b a y e s i a na p p r o a c h 符号说明 原始样本空间中的向量 目标值( 或类别值) 一个样本( 模式) 数据集的规模( 样本的个数) d 维原始样本空间 数据的联合概率分布 非线性映射 高维特征空间中的向量 模型的超参数 参数空间 隐函数 损失函数 超平面的法向量 v c 维 经验风险 期望风险( 真实风险) 置信范围 核函数 折中的惩罚因子 松弛变量 一组拉格朗日乘子的向量 拉格朗日乘子 超球面间隔 两个变量的协方差 单位矩阵 f i x 。) ) 静态高斯过程 ，的先验分布 ，的似然 ，的后验分布 瑚 ， 肛 ， ” 回巾 町 j 。 咄 力 x ，以矿口w向蛐ec鲁口 嘶娜，一朋一 d z ( c ) 三 l i n e a r p o l y r b f 损失变量( 噪音变量) 规范化因子 似然 线性核函数 多项式核函数 径向基核函数 图1 1 图1 2 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图3 1 图4 1 表2 1 表3 1 表4 1 s r m 示意图 分类器训练模型 图表清单 不同的分类超平面 最优分类超平面及其间隔 数据非线性可分的情况 数据在高维特征空间中的线性可分 d d a g s v m s 分类 c h u n k i n g 算法前三步迭代训练示意图 分解算法前三步迭代训练示意图 s m o 算法前三步迭代训练示意图 同心超球面分割 常见的损失函数 不同的划分超平面及其间隔 h d s v c 与标准s v c 的比较 l t s v c 与t s v c 、s v c 分类性能的比较 b o o s t i n g m u l t i s v c 与标准s v c 分类性能的比较 j 一 “ h m 掩 他 掩 加 驺 毖 勰 ” 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得金胆王些太堂 或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名 蜘憾。 签字日期：7 吨6 年妇7 日 学位论文版权使用授权书 本学位论文作者完全了解金壁王些盍堂有关保留、使用学位论文的规定有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金胆兰些盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 弘似 签字日期：y e 年f 月呵日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 髟 签字日期：衫年，月夕日 电话 邮编 致谢 论文是在导师王浩教授的悉心指导下完成的。感谢王老师近三年来给我提 供了良好的、宽松的学习环境! 王老师治学严谨、学识渊博、宽以待人，深深 的影响了我的学习以及将来的工作! 感谢胡学钢教授，胡老师高层建瓴、循循善诱，为我们的学习和工作树立 了榜样! 感谢徐静老师，她对我的研究生学习给予了大量的关心和帮助! 感谢张润梅老师、姚宏亮博士和所有实验室的成员! 感谢高建清、李元元、宋蓓蓓、张忆同学，我们共同探讨问题，度过了难 忘的三年研究生时光! 最后，由衷的感谢我的父亲、母亲和兄嫂，他们无私的爱护和坚持不懈的 鼓励，使我能够鼓足勇气充满信心，在学习的道路上越走越长! 琚旭 2 0 0 6 年4 月 第一章绪论 传统机器学习方法的理论基础之一是经典统计学，经典统计学研究的是样 本数目趋于无穷大时的渐近理论，现有的学习方法也多是基于此假设。但在实 际问题中，样本数目往往是有限的，因此一些理论上很优秀的学习方法在实际 应用中表现却不尽如人意j 。 机器学习f m a c h i n el e a r n i n g ) 就是通过数据集学习出一个学习机器，训练的 根据是期望风险最小化。由于数据集的先验概率未知，因此期望风险无法直接 求解。传统的机器学习方法利用经验风险最小化代替期望风险最小化，但这缺 乏理论保证。按照大数定律：当样本数目趋于无穷大时，经验风险r 。( w ) 才在 概率上逼近于期望风险r ( w ) ，而且无法保证凡。最小时的变量w 1 + 与r 最小时 的变量w 2 。是同一个值，更不能保证r 。m p ( w l + ) 逼近于r ( w 2 4 ) 。因此按照经验风 险最小化训练出的机器并非最优的，其中过学习( o v e r f i t t i n g ) 就是一个典型 的问题。 统计学习理论( 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 ) 口j 是v a p n i k 等人于2 0 世纪 6 0 年代末创立的一种专门研究小样本情况下机器学习规律的理论，并于9 0 年 代得到完善。统计学习理论指出，实际风险的上界是一个由经验风险和置信范 围组成的结构风险。经验风险和置信范围是不可调和的：经验风险越小，置信 范围越大：经验风险越大，置信区间越小。因此要使得学习机器具有较好的推 广性，就要在经验风险和置信范围中寻找一个折中( t r a d e o f f ) ，使得结构风险最 小，而不仅仅是经验风险最小。 支持向量机 2 】f 3 】【4 【4 7 【4 8 】( 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 1 。 1 1 机器学习 机器学习【5 h 6 m 是人工智能的一个核心研究领域，其目的是根据给定的有限 训练样本估计出输入和输出之间的依赖关系，使得训练出的学习机器能够准确 的对未知样本进行预测。给定一个数据集： d = ( x l ，y 】) ，( x 。，y 。) ，x ，r “，i = l ，f ，y ， 1 ，k ( 1 1 ) x ，在x 中是独立同分布的，y ，在y 中也是独立同分布的。变量y 与x 存在未知的 依赖关系，即遵循着某一未知的联合概率分布p ( x ，y ) 。学习的问题就是从给定 的学习函数集 厂( x ，口) ；曰 中选择一个最优的函数厂，其中口是超参数， 是 参数空间。 定义一个损失函数m ，f ( x ，口) ) 来度量y 与f ( x ，目) 之间的差异，它的数学期 望为： 尺( 口) = n ( y ，( x ，目) x 护( x ，y ) ( 1 2 ) 这就是期望风险( e x p e c t e dr i s k ) ，或称风险泛函( r i s kr e g u l a r i z e df u n c t i o n a l ) 【2 1 ， 通过最小风险泛函r ( o ) 获得最优的学习机器，。 1 1 1 经验风险最小化 要使得期望风险最小，必须知道样本的联合概率分布e ( x ，y ) ，但是在实际 的机器学习中，p ( x ，y ) 是未知的，因此无法直接计算期望风险r ( o ) 。传统的机 器学习方法则用经验风险代替期望风险，经验风险定义如下： r 。，( 目) = 亡( y ，厂( x ，目) ) ( 1 3 ) 。 h 百 通过最小经验风险获得最优的学习机器，这称为经验风险最小化原则 ( e x p e r i e n c er i s km i n i m i z a t i o n ，e r m ) 。 1 1 2 三类基本的机器学习问题 ( 1 ) 模式分类。学习机器的输出y 是类别标号，离散且有限。 题的方便，只考虑两类情况即y = o ，1 ) ，考虑如下的损失函数： 船以啪胪 o ：三篙 为了描述问 ( 1 4 ) 模式分类的问题就是：在训练样本已知但联合概率分布p ( x ，y ) 未知的情况下， 通过最小期望风险求得最优的分类函数厂o ( 2 ) 函数逼近。学习机器的输出y 是实数值，损失函数可以定义如下： e ( y ，f ( x ，曰) ) = ( y f ( x ，护) ) 2( 1 5 ) 函数逼近的问题就是：在训练样本已知但联合概率分布p ( x ，y ) 未知的情况下， 通过最小期望风险求得最优的函数厂d ( 3 ) 密度估计。从函数集 p ( x ，口) ；0 o 中估计密度函数，损失函数可以定 义如下： g ( p ( x ，口) ) = 一l o g p ( x ，臼)( 1 6 ) 密度估计的问题就是：在训练样本已知但先验概率尸( x ) 未知的情况下，通过期 望风险最小化求得最优的密度函数p 。 2 1 1 3 复杂性与推广能力 推广能力( g e n e r a l i z a t i o na b i l i t y ) 就是学习机器对未来输出进行正确预测的 能力，或称泛化能力。在传统的机器学习方法中，比如早期的神经网络，人们 总是把注意力集中在如何使经验风险更小。但很快发现，尽可能的使得训练误 差最小并非总是能够达到好的预测效果，即推广能力比较差。在某些情况之下， 训练误差很小反而导致推广能力的下降，这就是所谓的“过学习”。 之所以会出现过学习的现象，原因在于人们为了追求最小的经验风险，总 是试图用复杂的机器去拟合有限的样本，但得到的学习机器却丧失了推广能力。 i ) l l 练的结果从表面上看错误率很小，但实际上却无法保证学习机器对未来样本 的有效预测。 综上所述，得出两个重要的结论： 经验风险最小并不一定意味着期望风险最小。 学习机器的复杂性不但要与所研究的系统有关，而且要与有限的训练样本 相适应。 o c c a m 剃刀原理【9 】为模型选择提供了一般化的哲学原则，即除非必要，实 体( 或解释) 不应该随便增加。因此，我们需要一种能够指导我们在有限样本 情况下建立有效的学习和推广方法的理论，通过控制学习机器的复杂性来获得 良好的推广能力。 1 2 统计学习理论 统计学习理论被认为针对小样本估计和预测学习的最佳理论”。它从理论 上系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望 风险的关系以及如何利用这些理论找到新的学习原则和方法等。其核心思想是： 通过控制学习机器的容量( c a p a c i t y ) 实现对其推广能力的控制。下面就重点 介绍统计学习理论中的v c 维、推广能力的界和结构风险最小化。 1 2 1v c 维【2 】【8 学习系统的容量对其推广能力有重要影响。低容量学习系统只需要较小的 训练集，高容量学习系统则需要较大的训练集，但其所获的解将优于前者。对 给定训练集来说，高容量学习系统的训练集误差和测试集误差之间的差别将大 于低容量学习系统。v a p n i k 指出，学习系统的容量可由v c 维f 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 c 维的直观定义：对于一个 指示函数集，如果存在h 个样本能够被函数集中的函数按所有可能的2 “种形式 分开，则称函数集能够把h 个样本打散( s h a t t e r i n g ) ，那么函数集的v c 维就是它 能打散的最大样本数目h 。若对任意数目的样本，都存在一个函数能将它们打 散，则函数集的v c 维是无穷大。 对于模式识别问题来说，学习系统可以由二值函数集( ，0 ，印，0e ) 来描 述，其中参数0 可以唯一确定函数，( ) ， 为0 所有可能的取值集合。因此，钡z ， 易，口 的v c 维也表征了该学习系统的容量或复杂度，即学习系统的学习能 力，v c 维越大则学习系统越复杂( 容量越大) v c 维是统计学习理论中一个核心的概念。遗憾的是，目前尚没有通用的 关于任意函数集v c 维计算的理论，只知道一些特殊函数集的v c 维，比如n 维 实空间中线性函数的v c 维是7 + 1 ，而f ( x ，口) = s i n ( a x ) 的v c 维为无穷大。对于 一些比较复杂的学习机器，其v c 维除了与函数集有关外，还受到学习算法等 影响。如何计算v c 维是当前统计学习理论中有待研究的一个问题。 1 2 2 推广能力的界 经验风险和实际风险之间存在的关系称为推广能力的界，它是分析学习机 器性能和发展新算法的主要理论基础。v a p n i k 证明【2 1 ，对于指示函数集中的所 有函数，实际风险r ( o ) 满足一个上界，即任取玎满足0 r | j 层交叉验证方法f t c r o s sv a l i d a t i o n ) 将数据集分为七个没有交叉的子集，每个子集有k n 个数据，其中玎是数 据的总数。分类器要训练k 次，每次在一个子集上进行测试，在剩下的七1 个 子集上进行训练。评估出的推广错误率是个错误率的平均。当k = - n 时，称为 “留一法”。交叉验证法可以被重复多次，对于一个f 次的| j 层交叉验证法，时 个分类器将被构造并被评估，这意味着交叉验证的时间是分类器构造时间的打 倍。增加重复的次数意味着训练时间的增长和错误率评估的改善。我们可以对 l j 值进行调挺，一般将设为3 或5 ，这样可以缩短训练时间。值得注意的是，“验 证”是一种启发式的方法，因而未必对所有情况都能提高其性能。虽然如此， 该方法简单易用，在许多实际问题中能有效的提高分类性能。 ( 2 ) 模型的简洁性和可理解性 分类器模型越简洁越容易理解就越受到欢迎。 ( 3 ) 计算复杂度 在硬件条件限制下，时间复杂度和空间复杂度是一个重要的评估标准，比 如对内存的需求，或者算法的收敛性等。 ( 4 ) 鲁棒性 它反映了数据集在出现噪音数据或属性值空缺等情况下，分类器是否仍具 有正确的分类能力。 ( 5 ) 可伸缩性 大部分算法在训练时需要驻留在内存中，这将依赖于数据集的规模。在数 值实验中采用的数据集规模一般不大，但在实际应用中算法面临的是大规模数 据集特别是海量数据，这就意味着一个好的分类算法在硬件条件限制下具有很 好的伸缩性。 1 4 论文的结构 论文分为六章，各章内容安排如下： 第一章绪论 介绍支持向量机的背景。分析了统计学习理论产生的原因，介绍了统计学 习理论的核心概念，然后讨论了支持向量机分类的研究重点，最后给出论文的 结构安排。 第二章支持向量机分类的算法 针对支持向量机分类的算法进行了研究。系统分析了标准s v m 算法，简 要介绍了多分类问题和分解方法。最后提出了基于同心超球面分割的支持向量 预抽取方法，可以利用预抽取的支持向量代替整个数据集进行训练，并在标准 数据集上对该方法进行验证。 第三章损失函数 针对支持向量机的损失函数进行了研究。首先对常见的损失函数进行了分 析，然后对三角损失函数进行了改进，并给出相应支持向量机分类的原始和对 偶问题。最后在标准数据集上，对改进的三角函数支持向量机分类器的泛化性 能进行了实验。 第四章集成学习 针对支持向量机分类器的集成学习进行了研究。详细介绍了b o o s t i n g 和 b a g g i n g 方法，据此提出了一种基于b o o s t i n g 的支持向量机组合分类器。最后 在标准数据集上，对支持向量机组合分类器的泛化性能进行了实验。 第五章贝叶斯框架 针对支持向量机分类的贝叶斯框架进行了研究。探讨了高斯过程、贝叶斯 理论和支持向量机分类之间存在的联系。 第六章结束语 对论文进行了总结，并对今后的工作进行了展望。 本文受安徽省自然科学基金：基于贝叶斯网络技术的智能a g e n t 自组织和 学习的研究f 0 3 0 4 2 3 0 5 ) 资助。 第二章支持向量机分类的算法 s v m l 3 】【4 】1 首先是从两类分类问题提出的，其目标是求一个最优的超平面， 不仅使得两类分开( 保证经验风险尽可能的小) ，而且使得两类的分开间隔最大 ( 保证置信范围最小) ，以此遵循结构风险最小化原则，从而实现真实风险最小。 根据以上讨论，s v m 最终将分类问题转化为一个带约束条件的二次规划 ( q u a d r a t i cp r o g r a m m i n g ，q p ) ，这就是标准分类模型。标准分类模型简洁易用， 其计算速度主要取决于训练集的规模，与特征空间的维数无关。当数据集规模 不大的时候，标准分类算法可以胜任。但实际应用所面临的都是大数据集，训 练速度慢成为s v m 在应用上的一个瓶颈，为了解决这个问题，分解方法被提 出来。 目前s v m 的算法主要分为几何方法和代数方法两大类【12 1 ，另外还有一些 预处理方法。代数方法有标准s v m 算法，c h u n k i n g 算法、分解算法( o s u n a ) 和 s m 0 算法等分解方法，连续超松弛( s u c c e s s i v eo v e r r e l a x a t i o n ，s o r ) ，最小 二乘支持向量机( l s s v m ) ，v s v m 等。几何方法有最近点算法( s s k e e r t h i ) 和卫向量法( g u a r d v e c t o r ) 等。 s v m 的算法都是建立在标准算法的基础之上，其中标准算法和分解方法是 目前主流的训练方法。标准算法专门仅仅针对二分类问题，而多分类f 3 l 问题则 通过构造多个二分类s v m 来解决。 2 1 标准支持向量机分类模型 在原始数据空间中，如果存在一个线性函数无错误的把数据集分开，那么 称该数据完全线性可分；如果存在一个线性函数可以以低错误率把数据集分开， 则称该数据集是近似线性可分；如果仅存在非线性函数把数据集分开，则称该 数据集非线性可分。下面将详细分析支持向量机的分类模型。 2 1 1 数据完全线性可分 2 1 1 1 最大间隔思想 给定训练集d = ( x l ，y ) ，( x 。，y 。) ) ，x ，r 4 ，y ， l ，一1 ) ，i = 1 ，2 ， 。如 图2 1 所示，训练数据可以被不止一个超平面分开，可以达到训练误差为零，即 经验风险最小，但这些分类超平面中肯定存在一个最优的。 如图2 2 所示，选定其中一个超平面日：，然后两边平移，可以得到两个极 端的超平面h 。和皿。日，和乩会形成一个间隔( m a r g i n ) ，该间隔就称为超平面 h ：的分类间隔，h ，和h ，分别是间隔的边界( b o u n d ) 。通过归一化处理得到日- 、 h ：和日，的方程： 日l ：( w x ，) + 6 = 1 ，h 2 ：( w x ，) + 6 = 0 ，h 3 ：( w x ，) + 6 = 一1 图2 1 不同的分类超平面图2 2 最优分类超平面及其间隔 为了描述超平面的分类性质，使用下面的形式： ( w x ，) + b 1 ，若y = 1( 2 1 ) ( w x 。) + b 一1 ，若y = 一1( 2 2 ) 根据式( 2 1 ) 和( 2 2 ) ，可以得到如下的一种紧凑的形式： y ，“w x ，) + 6 ) 1 ，i = 1 ，2 ，n( 2 3 ) 此时分类间隔大小为力知旷 所谓最优的分类超平面就是分类面不但将两类样本正确分开( 训练误差为 零) ，而且使分类间隔最大。在数据可分基础之上，寻优问题转化为使间隔最大 即等价于i l w 最小。 统计学习理论指出 2 1 ：在d 维空间中，假设样本分布在一个半径为r 的超 球范围内，那么满足1 1 w l l a 的正则超平面构成的指示函数集 f ( w ，x ，b ) = s i g n w x + b 的v c 维满足下面的界： h r a i n ( j r2 a 2 】，d ) + 1 ( 2 4 ) 由式( 2 4 ) 可以看出，使恻1 2 最小就是使v c 维的上界最小，从而实现s r m 原则 中对函数复杂性的选择。这样，s v m 首先保证了一个小的经验风险，并通过选 择间隔最大的超平面的方式控制了函数集的v c 维，这正是s r m 原则所要求 的，使分类间隔最大实际上就是对推广能力的控制。 2 1 1 2 原始问题和对偶问题 综上，s v m 分类的原始最优化问题如下 式( 2 5 ) 是一个凸二次规划( c o n v e xq u a d r a t i cp r o g r a m m i n g ) ，因此存在全局最优 解。7 1 入拉格朗日乘子d 0 ，i = 1 ，2 ，z ，构造l a g r a n g e 函数1 3 1 ： w 0 2 - e ”叩。( w 一+ 6 ) + 宝口， ( 2 6 ) 以6 ) = w 旷口。y 。( w x ，+ 6 ) + 口， ( 2 6 ) 求( 2 6 ) 对w 和b 的极小得到如下的极值条件，也称k k t 条件( 见附录a ) ： 丝8 b = 扣，= 。 ( 2 7 ) 罢= w - - 主y 肫：o ( 2 8 ) 撕 。i = 1 一 。 其中( 2 8 ) 中罢：( 兰，兰，兰) ，w ：y 舳。oo w w , o w 。o w 。 ，一1 把( 2 7 ) 和( 2 8 ) 代入( 2 6 ) 中，可以得到原始问题( 2 5 ) 的对偶问题1 3 】： 月1n m 0 2 c 口，一去口，口y ，yj x 。x j y ，= 0 ( 2 9 ) 口，0 ，i = 1 ，n a ( 2 9 ) 也是一个凸二次规划【13 1 ，口，是与每个样本对应的l a g r a n g e 乘子。 假设最优解口= 。，口：，口。) ，则最优的分类函数为： ，月、 d ( x ) = s g n i q y ，( x ，x ) + 6 ( 2 1 0 ) 、i = 1 其中b = y ，一y 。q ( x 。- x i ) a f = 1 在通常情况下，大部分l a g r a n g e 乘予为零，只有相对较少的不为零，不为 零的乘予所对应的样本点称为支持向量( s u p p o r tv e c t o r ，s v ) ，如图2 2 中的 方框所示的样本点。由式( 2 1o ) 可以看出，分类函数仅仅由数量较少的支持向量 决定，这称为问题的稀疏性【2 3 】( s p a r s e n e s s ) 。 通过式( 2 5 ) 构造出的超平面被称为硬间隔( h a r dm a r g i n ) 超平面。 2 1 2 数据近似线性可分 c o r t e s 和v a p n i k 在1 9 9 5 年引入了软间隔最优超平面的概念，通过一个松 52 胛2 = 0 一 一6+x ，一2 n 砌 姐 弛变量鼻0 ，将约束条件( 2 3 ) 放松为 y ，( w x ，+ b ) 一1 + 毒0 ，i = 1 ，2 ，一，z ( 2 1 1 ) 显然当毒充分大时，样本点( x ，y i ) 总是可以满足上述约束条件。但应该设法避 免毒取太大的值，为此可以在目标函数里对它们进行惩罚，比如在目标函数中 加入专。因此原始问题( 2 5 ) e 以修改如下： 埘椭抑卜c 喜鲁)眨 s t y ，( w x 。+ b ) 1 一专，i = 1 ，2 ，一，竹 其中c 0 是一个惩罚参数，c 越大，对应的惩罚越大，它实现在错分样本比例 与算法复杂度之间的折中。( 2 1 2 ) 通过遵循s r m 原则构造出一个软间隔( s o f t m a r g i n ) 的分类超平面，显然硬间隔是软间隔的一个特殊情况。 原始问题( 2 1 2 ) 对应的对偶问题为： m a x q 一去吒叩， 一， 妣 q y 。= 0 ( 2 1 3 ) 0 口c ，i = 1 ，一，n 通过求解( 2 1 3 ) ，得到最优解口= ( 口1 ，口2 ，口。) ，其中口，= 0 对应于正确分类的样 本，口，= c 对应于错分的样本，0 a ， c 对应于支持向量。因此，所有的训练 样本均满足如下不等式： 口，= 0 营y ，f ( x ，) 1 ，毒= 0 0 口， c y i f ( x ，) = i ，专= 0 口，= c 甘y ，f ( x ，) 兰1 ，鲁0 最优的分类函数为： d ( x ) = j g n i 嘁y ( x ；x ) + 6 ，n、 ，= l 式( 2 1 7 ) q h 仅仅涉及到样本的内积x ，x ，即x 。不会单独出现。 2 1 3 数据非线性可分 2 1 3 1 非线性问题的变换 ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) ( 2 1 7 ) 绝大部分的现实问题都是非线性的，然而没有直接求解非线性问题的方法 一般的做法是把非线性问题变换为线性问题。图2 3 所示的是一个非线性分类 问题，存在某种映射可以把原始样本从低维样本空间映射到高维特征空间，如 图2 4 所示，在高维特征空间中样本变得线性可分( 或近似线性可分) 。因此， 可以通过映射把非线性问题变换成线性问题。 图2 3数据非线性可分的情况 图2 4 数据在高维特征空间中的线性可分 假设非线性问题的原始样本集为 ( x 。，y ，) ，( x ：，y ：) ，( x 。，y 。) ，经过g - n n 妒转换到另一空间得 ( 庐( x ，) ，y ，) ，( 庐( x ：) ，y ：) ，( 庐( x 。) ，y 。) ，变得线性可分。前面 的算法可以适用，根据前面，很显然线性问题已有相应的分类函数，因 此在此空间中分类函数为： 厂、 d ( x ) = s 咖i y ，呸( x 。) - 庐( x ) ) + 6 】 ( 2 18 ) i = l 式( 2 18 ) 中仅仅涉及到样本在高维空间中的内积妒( x 。) 庐( x ) ，即( x ，) 不会单独出 现。 2 1 3 2 核函数 根据泛函的相关理论和h i l b e r t s c h m i d t 原理，如果某个函数k ( x ，x ) 满足 m e r c e r 条件，那么它就对应于某一变换空间中的内积，即k ( x ，x ，) = 矿( x ，) ( x ，) ， 该函数称为核函数【3 】【1 钔。对于内积而言，庐只是一种形式，而k ( x 。，x ，) 是显式 的。值得一提的是，计算过程根本不涉及到高维空间的维数，所以不会出现维 数灾难的问题。 常见的核函数有： 多项式核函数k ( x ，x ，) = ( x 。x + 1 ) 9 ，其中参数g 是自然数。 径向基核函数( r b f ) 置( x ，x ，) ：e x p j 一坚二业 ，其中参数盯控制核的宽度。 【 仃 j s 型核函数k ( x ，x ，) = 留p ( x x ，) + c ) ，其中v ，c 分别控制核函数的斜率和偏移 量。 此外，还有诸如b 样条核函数、傅立叶核函数、a m a r i & w u 的动态核函数 以及一些组合的核函数等等。所有这些核函数的一个共同特点就是只会涉及到 向量的内积运算。 支持向量机通过引入核函数k ( x ，x ，) 可以巧妙的解决非线性分类问题，但 计算复杂度却没有增加，分类函数( 2 1 8 ) 变为： r l、 ，( x ) = s g n f y f 口。正( x ，x ) + b ( 2 1 9 ) j = l 由f 2 1 9 ) 可以看出，选择不同的核函数可以得到不同的支持向量机。概括的 说，对于任何一个可分的数据集，支持向量机可以通过核函数将输入空间映射 到一个高维特征空间( 也称核空间) ，然后在高维空间中求最优分类超平面。 2 1 4 支持向量机分类的标准算法 设训练集d = ( x 】，y 1 ) ，( x 。，y 。) ，x ，r 4 ，y ， 1 ，一1 ) ，i = 1 ，2 ，n ； 选取适当的核函数k ( x ，x ) 和正参数c ，构造并求解最优化问题： m i n y ，y ，q 世( x i x ，) 一a ， 。i = 1j = l j = 】 n y ，= 0 ( 2 2 0 ) 0 口c ，i = 1 ，2 ，” 得到最优解口= ( ，口2 ，口。) ； 选取口的一个正分量0 口。 c ，并据此计算闽值b = y ，一y ，q k ( x ，一，) ： 构造分类器矾x ) = j 劬l 蕃h 世( x ，x ，) + 6 j 2 2 多分类支持向量机 标准的支持向量机分类算法是针对两类问题而设计的，为使支持向量机方 法应用更为广泛，解决实际应用中的g - + o o 多类模式识别问题，人们在两类算法 的基础上，对多类算法进行了深入的研究。目前多分类s v m s 3 1 主要有一对一 s v m s 、一对多s v m s 、有向无环图s v m s 、层次s v m s 和纠错编码s v m s 等。 下面主要介绍一对多s v m s 、一对一s v m s 和有向无环图s v m s 。 2 2 1 一对多s v m s 针对类问题，选取第i 类样本作为正类，剩下n - 1 类样本作为负类，然 后调用某一训练算法构造出二类分类器s v m ( f = 1 ，n ) ，一共构造出n 个 s v m 分类器。如果样本x 是第，类，则s v m ( 。( x ) 输出为1 ，否则输出为一1 。给定 一个未知的输入x ，其类别就是s v m ( ”，s v m ( ”，s v m ( ”中输出为1 的上 标。 2 2 2 一对一s v m s 针对类问题，从训练集中选取第f 类和第，类的样本，可以构造出分类器 s v m ( u ) ( i ，i ，= 1 ，) ，结果共构造n ( n 一1 ) 2 个分类器。给定一个未知的 输入x ，当预测它的类别时，我们将考虑所有分类器的意见：一个分类器判定x 属于第i 类意味着第i 类获得一票，得票最多的类别就是x 的最终预测结果。 2 2 3 有向无环图s v m s 有向无环图多类s v m s 分类法( d i r e c t e da c y c l i cg r a p hs v m s ，d a g - s v m s ) 在训练阶段和“一对一”投票一样，也要构造出每两类间的分类面，即有k ( k - 1 ) 2 个分类器。但是在分类阶段，该方法将所用分类器构造成一种两向有向无环图， 如图2 5 所示：包括k ( k 一1 ) 2 个节点和k 个“叶”。其中每个节点为一个分类器， 并与下一层的两个节点( 或者叶) 相连。当对一个未知样本进行分类时，首先从 顶部的根节点开始，根据根节点的分类结果用下一层中的左节点或者右节点继 续分类，直到达到底层某个叶为止，该叶所表示的类别即未知样本的类别。 2 3 分解方法 图2 5d d a g s v i v i s 分类 支持向量机的标准算法在训练时把所有的样本作为一个整体训练，假设有 挥个样本，在内存中需要保存一个n 2 的核矩阵，在一般的数值实验中，当 4 0 0 0 时，标准算法可以胜任。当面对大规模数据集时，标准算法需要进行到大量的 矩阵运算，由于硬件的限制而大大降低了算法的性能，这也就形成了支持向量 机在实际应用中的一个瓶颈。 为了克服大规模数据集训练的难题，分解算法f 3 】 1 5 f 1 6 】 17 1 被提出来了，分解 方法把大数据集分解成若干个小的数据集，即将大规模的原始问题分解为小规 模的子问题，按照某种迭代策略，反复求解子问题，构造原始问题的近似解， 1 6 并使该近似解逐渐收敛到原始问题的最优解。分类器训练的时间是若干个子问 题的时间叠加。根据分解策略、子问题的大小以及子问题的求解策略，可以有 不同的训练算法，如选块算法( v a p n i k ) 、分解算法【l 副( o s u n a ) 和s m o “( p l a t t ) 算法等。 显然分解算法可以从根本上解决s v m 面对大数据集训练时速度缓慢，甚 至无法训练的问题，但是子问题的规模与算法的迭代次数是一对矛盾。因为分 解方法实际上把求解子问题的耗费转移到迭代上，然后在迭代上进行快速的训 练，如果分解的子集越小，子集的数目就越多，那么迭代的时间越长。 标准算法训练的时间按照样本数目的增加呈几何级数增长，而分解方法的 时间是若干子问题的线性叠加，从而训练大数据集的时间大大减少。大量的实 验表明，当数据规模不大时，无法比较标准算法与分解算法的优劣，但是随着 规模的增大，分解算法明显体现出了优越性。 2 3 1 选块算法( c h u n k i n g ) 在标准支持向量机中，最优解仅仅依赖于支持向量，如果我们知道支持向 量的信息，就可以率先训练支持向量对应的样本。如果不知道哪些是支持向量， 一般来说就要采用启发式算法来寻找，最简单的启发式方法是选块算法。我们 称训练集中的任意一个子集为块( 工作集) ，选块的过程大致如下： ( 1 ) 首先随机选择一个工作集，进行支持向量机的训练，得到支持向量和相应 的分类函数； ( 2 ) 然后用下列方式调整下一次的工作集：保留该块中非零支持向量对应的 样本，舍弃块中其它的样本；利用分类函数来检验训练集中除去该块后的所 有训练点，把m 个违反k k t 条件最严重的点( m 事先给定) 加到新工作集中， 然后再训练新的工作集。重复以上过程，直到满足某一个停机标准为止。 一般来说，工作集是增加的。这种算法的优点是当支持向量机的数目远小 于训练样本的数目时，能够大大提高训练速度。相反，当支持向量的数目较多 时，随着迭代的次数的增加，所选的块越来越大，训练速度就相对缓慢。 选块算法并非最优，原因有两点：该算法需要一种好的选择工作集的策 略，支持向量的数目未知。尽管如此，由于它是第一个具有分解思想的训练 算法，因此它具有开创性，为后来的研究工作奠定了基础