（应用数学专业论文）基于支持向量机机器学习模型构建及研究.pdf

巾山大学博士学能沦文 摘要 支持向量机理论是一种专门研究小样本情况下机器学习规律的基本理论和 数学构架。在结构风险最小化原则下，支持向量机有效地解决了有限样本下机器 学习的问题。 论文针对支持向量机研究的三个主要领域提出了新的理论和方法。主要包括 三个方面的内容： 首先，论文通过认真研究沃尔什函数的性质，发现了在较小置信范围条件下， 可以采用沃尔什函数来逼近机器学习的响应函数一指示函数，能够在结构风险最 小化原则下使风险泛函最小，从而保证小样本环境下机器学习的误差最小，并且 获得较好的学习推广能力。实现了沃尔什函数对实函数应用的扩展，并给出了所 作研究结论的应用实例。 其次，提出了变元可分离核函数的概念，证明了新定义的变元可分离核函数 满足m e r c e r 条件，从而实现在无穷维h i l b e r t 空间映射的可能性，并依此提出了 新的核函数选出方法。根据所提出的理论，对变元可分离应用于支持向量分类机 时的特征，从较新的角度进行了理论上的分析，并根据研究结果提出了实际应用 的算例。 最后，指出了现有支持向量机理论中样本数据“静态”不变的局限性，因为 实际问题中，并不存在绝对稳定的数据，更多的情况是被处理的数据时间变化的， 尤其是对实时系统更是如此。本文提出了离散时间系统的动态支持向量机的概 念，并且构造了相应的模型，给出了满足一定条件的证明结果。此外还根据模型 分析结果提出了相应的算法，并给出了基于这些算法的算例及其分析。 中1 1 1 大学博士学位论文 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 st h e o r y ( s v m ) p r o v i d e st h e o r e t i c a la n dm a t h e m a t i c a l f r a m ei ns t u d yo fm a c h i n el e a r n i n gr e g u l a r i t yu n d e rc o n d i t i o no fs m a l la m o u n t s a m p l e s b a s e do ns t m c t u m lr i s km i n i m i z a t i o n ( s r m ) p r i n c i p l e s v mc a nr e s o l v e m a c h i n el e a r n i n gp r o b l e m si nas t a t eo fl i m i t e ds a m p l e s i n t h i st h e s i s ，n e wt h e o r e m sa n dm e t h o d so ns u p p o r tv e c t o rm a c h i n e s ( s v m ) ， w h i c ha r ei n c l u d e di nt h r e ea r e a s ，a r ep r o p o s e d t h em a i nc o n t e n t sa r e ： f i r s t l y , b yd e e p l ya n a l y z i n gp r o p e r t yo fw a l s hf u n c t i o n ， i ti sf o u n dt h a tu n d e r s r mp r i n c i p l ea n ds m a l lc o n f i d e n c es c o p e ，w a l s hf u n c t i o ni su s e dt oa p p r o x i m a t e r e s p o n d i n gf u n c t i o no fl e a r n i n gm a c h i n e - - - - - d i r e c t i o nf u n c t i o n ，l e a d i n ge r r o ro ft h e l e a r n i n gm a c h i n et ob et h el e a s tw i t ht h es m a l ls a m p l ep r o b l e m s ，a n dt h eb e t t e r l e a r n i n gg e n e r a l i z a t i o na b i l i t yc a nb eo b t a i n e d s e c o n d l y , c o n c e p to fk e r n e lf u n c t i o nw i t hd i s s o c i a b l ev a r i a b l e si sa d v a n c e da n di t i sp r o v e dt h a tn e wd e f i n e dk e r n e lf u n c t i o nw i t hd i s s o c i a b l ev a r i a b l e sc a nb es u f f i c e d t om e r c e rc o n d i t i o nt or e a l i z ep o s s i b i l i t yo fh i l b e r ts p a c em a p p i n gi n i n f i n i t e d i m e n s i o n a ls p a c e i na c c o r d a n c ew i t ht h ep r o o f , s i f t i n gw a yo f n e wk e m e lf u n c t i o ni s p r o p o s e d n e wt h e o r yh a sa n a l y z e d b a s i cp r o p e r t yt h a tk e r n e l f u n c t i o nw i t h d i s s o c i a b l ev a r i a b l e si su s e dt os v mc l a s s i f i e rf r o mt h en e wa n g l e s ，a n df u r t h e r , c o n c r e t ea p p l i c a t i o na l g o r i t h ma n de x a m p l e sa r eg i v e n f i n a l l y , i ti si n d i c a t e dt h a t s t a t i cd a t a ”e x i s t e n c ei ns v mt h e o r yi sl i m i t e d ， b e c a u s et h e r ei sn oa b s o l u t es t a b l ed a t ai np r a c t i c a la p p l i c a t i o n i nm o r ec a s e s ，t h e h a n d l e dd a t ai sf r e q u e n t l yv a r i a b l ew i t ht i m e ，p a r t i c u l a r l yr e f e r r i n gt or e a lt i m es y s t e m i nt h i st h e s i s ，an e wc o n c e p t “d y n a m i cs u p p o r tv e c t o rm a c h i n e s ”b a s e do nd i s p e r s e d t i m es y s t e ma n dt h er e l a t i v em a t h e m a t i cm o d e la r ep r o p o s e d ，a n dt h ep r o v e d c o n c l u s i o nt os a t i s f yf i x e dc o n d i t i o ni sa l s og i v e n i i 中i i j 大学障上学位沦文 第一章综述 1 1 机器学习的发展 学习是人类具有的一种重要智能行为。按照著名的人工智能学者h s i m o n 1 的观点，学习就是系统在不断重复的工作中对本身能力的增强或改进，使得系统 在下一次执行同样或相类似的任务时，会比原来做得更好或效率更高。机器学习 研究的内容是如何使机器( 目前主要是计算机) 通过对象识别，利用现有知识来 获取新知识和新技能。 科学技术发展的最终目的在于扩充人类认识世界的能力，改善人类与自然的 共生共存的和谐性，并提高人类的生活质量，这些能力是综合的能力。其中。扩 展智力能力是最为引人入胜的，也是最为困难的问题。人们一赢努力尝试使机器 具有智能，期望机器不仅可以代替人类进行一般的体力劳动，而且可以帮助人们 从事一些智力工作。沿着这个方向，经过长期艰苦的努力，人工智能研究已经取 得了一些令人鼓舞的进展。 随着计算机技术的高速发展，学习行为的研究成为人工智能领域的重要内 容。因此，研究机器学习的意义就在于，构造一个能实现一个特定目标的系统， 这个系统不仅能够具有知识获取的能力，而且它必须在内部表现为新的知识结构 的建立和改进，外部表现为系统性能的改善，使系统反应更快、更精确、更健全。 机器的学习，由于模仿了人类的智能而具备了一定的智能化特点。一般认为 一个机器学习系统应有以下功能【2 】： 1 适当的学习环境； 2 具备一定的学习能力； 3 能用所学的知识解决问题； 4 能适度自我提高系统的性能。 我们以h s i m o n 的机器学习定义作为出发点，建立起下图所示的简单的学习 模型，然后通过对这个模型的讨论，总结出设计学习系统应当注意的一些原则。 巾山大学博士学位论文 个简单的机器学习模型如下 图1 1 当一个机器系统满足以上条件即具备了基于机器环境的、具备学习能力的最 基本的非人力智能系统构成的条件。图1 - 1 表示学习系统的基本结构。环境向系 统的学习部分提供某些信息，学习部分利用这些信息修改知识库，以增强系统执 行部分完成任务的效能。执行部分根据知识库完成任务，同时把获得的信息反馈 给学习部分。 人类的学习有如下几个基本特征； 1 学习是一个缓慢的过程； 2 学习不是一个简单的复制过程； 3 学习是一个逐渐积累的过程； 4 人类学习会遗忘。 与人类学习相比，除了第4 点，机器学习也具有基本相似的特征，而第4 点恰恰是机器学习的优越性所在，除非人为地将必要的信息删除。当然，一个良 好的机器学习系统要想满足前三个条件决非易事，因为机器学习系统应根据环境 在不断重复的工作中对本身能力有增强或改进。因此，研究机器学习的基本意义 在于：通过建立计算机学习模型，获得对学习方法的了解，使计算机具备学习的 能力阿。 因为机器学习是一项复杂的“智能”活动，相关的学习过程通过一定的算法 完成一定的推理，也确定了学习的策略和方法。按机器学习发展的过程来看，常 见的机器学习方法有1 2 m 3 哪：机械学习、示教学习、类比学习、事例学习、解 释学习等。但是从上世纪8 0 年代中期以来，人工神经瞬络( a n n ) 的研究已经成 为人工智能的热点，它的一个基本特点就是利用计算机对人脑神经元进行模拟。 2 中山大学博士学位论文 简言之就是抽象、简化和模拟大脑生物结构的计算模型，将大量功能简单而具有 自适应能力的信息处理单元一人工神经元按照大规模并行方式通过一定的拓扑 结构连接而成，形成复杂的人工构造的智能化的复杂网络结构。 神经嘲络中基本的人工神经元结构描述如下：设有集合= 缸 x 2 , 是神 经元的输入，既可以是外部的信息输入，也可以是对下一级神经元的输出；集合 w ，w 2 , ， 是输入到神经元的权值，表示神经元的连接强度，由学习过程的特 性决定。目是神经元的内部阈值，( ) 是神经元的激励函数( 或称传播函数) ，有 几种常见的激励函数。经过抽象和简化，单个神经元的结构图为： 图1 - 2 神经元通过对多个输入值与权值相乘及施加非线性变换得到输出，其信息处 理步骤为： a 1 对输入信息与对应的权值进行内积计算：即：“尸w i x i 一0 b ) 得到神经元输出粥= j ( u j ) c ) 对神经元输出判定，若y j 大于给定阈值，则神经元被激活。 以上结构和处理方法表明人工神经网络在某种程度上模拟了人脑的思维过 程，而构成各种a n n 的模型都包含神经网络拓扑结构、神经元特性结构和学习 算法三个要素。 1 2 支持向量机( s v m ) 理论及其发展 1 2 1 问题的提出 基于数据的机器学习是现代人工智能技术的一个重要方面，它的基本方法就 是从观测的样本出发，选定特征数据，从中找出规律，建立数学模型和函数依赖 规律，并能根据已知的数据对未知数据或无法观测的数据进行分类、识别和预测， 构造智能化的学习机器模型，文献【6 】、 3 1 、【3 3 、【3 6 、【3 7 、c 5 2 】、【5 4 、 5 5 、 【5 7 、 5 8 芹f 1 1 6 9 都有描述，但是目前最著名的方法有以下两种： 中山大学博士学位论文 第一种是人工神经网络( 甜n ) 。如前所述，它主要利用已知样本建立非线性 模型，克服了传统参数估计方法的困难。常见的神经网络结构有：多层感知器 ( m l p ) ，径哥基函数网( r b f ) 和h o p f i e l d 网等模型，它们已经成功地用于解决模 式识别、信号处理、智能控制等。 人工神经元网络是目前研究较多的交叉学科。由于通过选择适当的隐单元数 和网络层次，前馈网络能以任意精度逼近非线性函数，因此神经网络技术被广泛 应用到工业过程的建模与控制中，并取得了巨大成功。尽管如此，神经网络仍然 存在一些缺陷。 神经网络的一些缺陷如下： ( 1 ) 网络结构需要事先指定或应用启发式算法在训练过程中修正，这些启发 式算法难以保证网络结构的最优化。对于多层网络，系统的组合会非常复杂。 ( 2 ) 网络权系数的调整方法存在局限性，具体表现在训练可能过早结束而产 生权值衰退。 ( 3 ) 神经网络容易陷入局部最优，有些训练算法甚至无法得到最优解。 ( 4 ) 过分依赖学习样本，即模型性能的优劣过分依赖于模型训练过程中样本 数据的数量和质量。大多数情况下，样本数据是有限的。另外，许多实际问题中 的输入空间是高维的，样本数据仅是输入空间中的稀疏分布，即使能得到高质量 的训练数据，数据量也必然很大。大量的样本数据势必会大大增加算法的训练时 间： ( 5 ) 目前尚无一种理论能定量地分析神经网络的训练过程的收敛速度及收 敛速度的决定条件，并对其加以控制； ( 6 ) 神经网络方法的优化目标是基于经验的风险最小化( e r m ，e m p i r i c a l r i s k m i n i m i z a t i o n ) ，这只能保证学习样本点的估计( 分类) 误差最小。实际上， 该误差应对所有可能的点都达到最小，即泛化性能最好。神经嘲络方法回避了经 验风险能否收敛于实际风险以及收敛条件等重要问题。尽管存在上述问题，神经 网络在原有框架内仍然取得了很多成功应用，其原因就在于这些应用的设计者， 在设计神经网络过程中，有效； u 用了自己的经验和先验知识。因此，神经网络系 统的优劣是因人而异的。 第二种就是统计学习理论及支持向量机( s v m ) 。作为机器学习的新兴领域， 4 巾山大学博士学位论文 统计学习理论是由美国科学家v a p n i k 等人最早在六、七十年代开始建立的， 它是一种专门研究小样本情况下机器学习规律的理论。到了上世纪九十年代中 叶，随着该理论的日渐完善和神经网络等机器学习理论缺乏实质性的进展，统计 学习理论越来越受到人们的广泛重视。在这一理论基础上，v a p n i k 提出了支持向 量机理论( s v m ) ，这是一种基于小样本的统计学习理论，比传统的统计学习理论 和神经网络理论有更好的泛化推广能力，在国际上成为人工智能技术研究的又一 新的热点【4 【5 叭。支持向量机是近年来机器学习研究的一项重大成果。到目前为止， 能比较好地解决小样本条件下机器学习问题的理论就是统计学习理论，支持向量 机理论是它的发展和提高。 支持向量机具有严格的理论和数学基础，与基于神经 ) 9 络的学习方法相比， 支持向量机具有如下特点： ( 1 ) 基于结构风险最小化( s r m ，s t r u c t u r a lr i s km i n i m i z a t i o n ) 原则，保证 学习机器具有良好的泛化能力： ( 2 ) 巧妙地解决了算法复杂度与输入向量维数密切相关的问题； ( 3 ) 应用核技术，将输入空间中的非线性问题，通过非线性函数映射到高维 特征空间中，在高维空间中构造线性判别函数： ( 4 ) 与传统统计学不同，支持向量机专门针对小样本情况，它的最优解基于 已有样本信息，而不是样本数趋于无穷大时的最优解； ( 5 ) 算法最终转化为一个凸优化问题，保证了算法的全局最优性，解决了神 经网络无法避免的局部最小问题。 ( 6 ) 神经网络、遗传算法等传统方法的实现中带有的很大的经验成分，而支 持向量机具有更严格的理论和数学基础。 1 2 2 支持向量机基本问题 1 基于统计学习理论机器学习的基本概念【7 l 假设有有限数量观测样本，并有三个基本元素： ( 1 ) 产生器( g ) ：产生随机向量工掣，它们是从概率分布函数f ( x ) 中独立 抽取的。 ( 2 ) 口i 练器( s ) ：对每个输入向量互返回一个输出值y ，输出的依据是条 件分布函数f f y l x ) 。 中山大学博士学位论文 ( 3 ) 学习机器( l m ) ：能够实现一定的函数集f ( x ，口) ，o j ，其中 是参数 集合。用来描述机器学习的模型为； 图l 一3 ，a ) 从上图中可以看到，训练器s 针对输入集合铲 x ，x x i 有输出 y = y j , y 2 , y t ，形成训练集o ， y 夙仁a 如) o 如作为学习机器l m 的输入，学习 机器对任意输入x 有输出f c x ，口) 。学习的目标是输出f ( x ，0 7 ) 与训练器的响应y 之差尽可能地小，即学习机器相应对训练器响应有最好的逼近，使两者之间的差 异上p ，( x ，口) ) 最小，一般用它的数学期望值r ( 0 7 ) = f 0 展开成： k ( ) = g k z k ( 咖。( v ) ( 1 2 ) 女= i ( 即用k ( “v ) 描述一个特征空间中的一个内积) ，充分必要条件是，下列条件： ll k ( u , 力g ( “) g ( v ) d “d v o ( 1 - 3 ) 对于所有g 岛( c ) 成立( c 为的一个紧集) 。其中k ( u ，称为核函数，对应于 支持向量机模型，表达为瞰。曲。在满足优化条件时，对应于支持向量，表达为 k ( x a 柏的，也可称为内积的同旋。 ( 2 ) 若核函数存在，则可以构造在输入空间中的非线性决策函数： f ( x ) = s g n ( y i a l k ( x t ，x ) 一6 ) ，其中x i 为支持向量，它们等价于在高维特 芟仟同重 征空间( x ) ，缈。( x ) 中的线性决策函数，k ( x i , x ) 是核函数。 构造上式类型决策函数的学习机器称为支持向量机，其复杂程度取决于支 持向量的数目丽不是特征空间的维数。支持向量机s v m 可用如下图形表示： 对于分类的情况，要求得系数口，只要寻找泛函： 形 ) = q 一去q q * 乃彪( 玉，x j ) ( 1 - 4 ) i = 1 ，j = a ， 的最大值，约束条件为：y ，= o ， a i o , i = 1 , 2 ， x 1 z 2 注：输入向量f ( 石1 ，x n ) 图1 4 基于支持向量 柚一2 ”硝的 非线性变换 中山大学博士学位论文 1 2 3 支持向量机综述及进展 支持向量机理论从诞生至4 现在不足十年，由于其在许多方面表现的优良特性 而受到了广泛的重视，成为人工智能领域研究的热点。 支持向量机的核心内容最早由v l a d i m i rn ，v a p n i k 在1 9 9 2 到1 9 9 5 年问提出 的，也是统计学习理论中最重要、最实用的部分。由于现实社会中大量的非线性 问题的存在，使得一般的机器学习计算的复杂度过大。相对于其它的机器学习理 论，v a p n i k 的主要贡献在于【4 l 6 j 【7 l ： ( 1 ) 对于有限的训练样本，可将其映射成一个n 维乃至于无穷维的h i l b e r t 向量空间。对非线性问题可通过某种变换转化为某个高维空间中的线性问题，定 出最优分类面就能解决问题。 ( 2 ) 最优分类面只涉及训练样本之间的内积运算( z ，) ，见式( 1 - 4 ) ，并 不需要知道非线性变换以何种方式实现，只要找到一种核函数k ( t x i ) 满足 m e r c e r 条件，它就可以对应于高维的变换空间的内积。 从图1 - 4 的支持向量机结构可以看出，世( 薯x ，) 是构造s v m 的关键函数， 它是实现输入向量集合乒“1 j 2 ，一) 向高维特征空间映射，形成最优分类超平面 尤其是非线性条件下的决策函数的基础。从结构上看，它又非常类似于神经网络 结构。事实上，若引入核函数为k ( x ，x i ) = t a n ( x x i + c ) 就构成两层神经网络。 在结构风险最小化原则下，支持向量机有效地解决了有限样本下机器学习问 题，并且在一定程度上解决了神经网络所不能解决的问题，力图将基于非线性优 化的人工神经网络研究变换为线性优化问题。从数学上讲，线性优化对应的线性 可分问题又可转换为二次规划求解支持向量的问题。因此，s v m 对机器学习研 究者来说具有极大的吸引力，在近年来受到各国研究者和工程师的重视。从支持 向量机理论提出至目现在，其理论基础的重要性和应用方面的实用性已获得大家的 共同认船，在人工智能研究中已成为一个独有的领域，而且其理论还在不断地完 善和发展。支持向量机理论到现在为止虽然时间不长，但作为新一代学习机器， 它有许多引人注意的特点：它的理论基础扎实、严谨、清晰、明确；它的设计技 术既可行而又简单实用；它在函数表达能力、推广能力和学习效率上都优于传统 的人工神经阿络；它不仅可以处理数值信息，也可以处理符号信息；在实际应用 8 中山大学博上学位论文 中也解决了许多实际问题，并且效果良好。支持向最机作为一个快速发展的领域， 被学者们认为是机器学习研究的一个非常具有前途的发展方向，现在将对这方面 的问题作一个综述，并对一些基本进展作简要介绍。 1 支持向量机的理论研究进展1 4 4 i 虽然支持向量机发展时间很短，但是由于它的产生是基于统计学习理论的， 因此具有坚实的理论基础。近几年涌现出的大量理论研究成果，更为其应用研究 奠定了坚实基础。b a r a b i n o s 0 p a l l a v i c i n i 3 3 1 提出了多层支持向量感知机的概念， s h a w e - t a y l o r 和c r i s t i a n i n i 6 q 也给出了关于高维分布式支持向量机的概念；张文生 等人f 2 l 】提出了支持向量机中引入后验概率的理论和基于邻域原理求海量数据 的支持向量机的理论，陶卿等人 1 4 】解决了支持向黉机的几何解释问题，肖健华 等人提出了样本数目不对称时的s v m 模型，s u y k e n s 等j k l 3 6 提出了非线性支持 向量机模型，d r u c k e r t 3 5 1 等人提出了间隔分类支持向量机的概念。s u y k e n s 等j k l 6 5 】 成功地将支持向量机应用于主成分分析。随着支持向量机理论上深入研究，出现 了许多变种支持向量机，如s m o l a 等”5 6 】提出的用于分类和回归的v 支持向量机。 另外，一些学者还扩展了支持向量机概念，如m a n g a s a r i a n ( 1 9 9 7 ) 等人3 8 】的通 用支持向量机( g e n e m l i s e ds v i s ) 。 2 支持向量机( s v m ) 与神经网络的关系 支持向量机( s v m ) 与人工神经网络有一些共同点，比如：两者都是数据驱动 的学习机器，都是从经验数据集( 训练集) 中获得学习数据。在结构描述上两者 有相似之处，数学表达也类似。在功能上，都是构造逼近器去逼近定义的函数。 不同点是两者的目标函数出发点不一样。神经网络学习的目标函数是经验风险最 小化( e r m ) ，s v m 学习目标函数是结构风险最小化( s r m ) ：神经网络学习有过学 习现象，s v m 可以避免过学习；神经网络是启发式学习，s v m 有严格的理论基 础和数学基础。 张铃f 1 9 l 研究了基于核函数的s v m 与三层前向神经网络的关系，得出的结论 是：基于核函数的s v m 与三层前向神经网络等价，对任意样本集心均存在映 射e 在此映射下，( 目在高维空间中线性可分，并且是可构造性的。该文还给 出了求解核函数构造性多项式的算法。 巾山大学博士学位论文 3 关于s v l v l 算法的研究 关于s v m 算法的研究是支持向量机研究中最热门的，也是成果最多的，因 为无论理论多么完善，最终也还是要通过算法来实现。文献 5 】、 8 】、【l o 卜【1 1 、 1 3 、【1 7 、 i8 】、【2 5 2 7 1 、 3 0 、【4 5 1 、 4 7 1 5 1 1 、 5 4 、【6 1 、 6 4 分别探讨了 各种算法的特点。在这方面主要有两大类进展，一是提出各种新的s v m 算法， 二是各种算法的改进和优化。 支持向量机各种算法中最常见的是构造分类器，其基本原理是使用一个非线 性变换将一个线性不可分的空间映射到一个高维的线性可分的空间，从而建立一 个分类器。这种分类器只由大量样本中的极少量支持向量确定，并且具有最大的 边界宽度。支持向量机算法的最方便之处在于，可以不必计算复杂的非线性变换， 而只需计算非线性变换的点积，即求出核函数就能很方便地解决问题，从而大大 简化了计算，这是一个了不起的仓举。另外，通过把核函数引入到一些学习算法 可以方便地解决非线性算法的问题，我们将其与支持向量机一起称为基于核函数 的方法。 ( 1 ) 基于支持向量机算法概述 前述的文献中介绍了很多支持向量机算法有关的内容，现选择一些重点内容 予以概括。 a 1 分类阊趣 分类问题，实际上就是对两类或两类以上的样本，在一定条件下尽可能地以 小差错的结果分类。若对两类样本，设样本集为( x 。，y ，) ，( k ，y ，) r7 ，y 1 ，一l ， 应使两类样本到分类超平面w x + 扣0 的最小距离最大，即最大化分类间隔 ( m a r g i n ) ，也称分离裕度。可以证明分类间隔为击，使分类间隔( 分离裕度) l l i 最大，等价于l w | 2 最小。v a p n i k ”1 指出，i iwi i2 最小就相当于使v c 维上界 最小。故常见的分类学习问题最小化目标函数为： rr ( w ，善) = l ，w w + c 莓 ( 1 5 ) 二 洋1 。约束条件为” w x + b l - 芬三o ，i = 1 ，n ( 1 - 6 ) 其中，石为松弛项，因为在线性不可分的情况下，允许一定的错分。目标函 中山人学博士学位论文 数的第一项减d w c 维，第二项减小经验风险，可得到最小的期望风险。在线性 可分的情况下，经验风险为0 ，v c 维得到最小化。在线性不可分的情况下，折中 考虑了经验风险和v c 维的晟小化。 对于非线性分类，首先使用一个非线性映射函数西把数据从原空间足“映射到 一个高维特征空间口，再在高维特征空间q 建立优化超平面。高维特征空间q 的 维数可能是非常高的，可以高至无穷维。支持向量机算法巧妙地解决了这个问题。 在原空间的非线性问题如果在x r “空间，可以映射到更高的h i l b e r t 空间。若满 足优化条件，在非线性空间也只考虑在高维特征空间力的点积运算 m ( ) 中( x ，) = 眉，x j ) ，不必明确知道中( 葺) 是什么函数，决定最后问题解的是定 义的飘丑，x j ) ，称为核函数。已经证咀对称函数厨x i ，x i ) k 要满, 足_ m e r c e r 条件即 可实现向h i l b e r t 空间的映射，并使非线性问题得到解决。 b 1 回归问题1 6 1 1 2 5 j 若考虑样本( x i ，y 1 ) ，( ，妫) ，回归函数设为 ，( 砷= w 西0 ) 4 - b 优化问题最小化函数为 广r ( w ，毒f ) 2 吉w w + c 蕃( 毒+ 占) i 1 约束条件为：( 而) 一y ，等+ s ， i l y l f ( x ，) 缶+ 占，毒、等0 ( 1 - 7 ) 式( 1 7 ) 中第一项使函数更为平坦，从而提高泛化能力，第二项则为减小经验风 险，常数c 对两者做出折中。8 为一正常数，f ( ) 与的差别小于8 时不计入误 差，大于s 时误差计为i f ( x i ) 一肌| - s 。引入拉格朗日函数可以得到优化问题的对偶 形式，最大化函数为 群) 儿一( q - a ；) 6 ( 1 8 ) 这也是一个二次优化问题，求解这个问题得到回归函数 位 。目 xm 西 。q q o 心 咖 。蚪 r “ 一 。d 束 约 矿 其 中山大学博士学位论文 厂扛) = ( 啦一西) 世( z ，t ) + 6 ( 1 - 9 ) f = l c 1 基于核函数的算法删1 2 9 l | 砷i 将核函数的思想应用到其它线性学习机，可以得到非线性学习机的效果，称 为基于核函数的方法。 基于核的f i s h e r 判别分析 这是f h m i k a 等人 6 3 1 于1 9 9 9 年提出的方法。设两类摊样本分别为 x i = 爿，或；) ， x 2 = k ，_ 。2 ： ，”= ”1 + n 2 。f i s h e r 判别分析的原理是将摊x 空间的样本映射成一维空间点集，这个一维空间的方向就是相对于f i s h e r 准则。 基于核的感知机( p e r c e p t i o nb a s e d o nk e r n e l ) 这是j x u 等人于2 0 0 1 年提出的方法【6 4 1 。传统的单层神经网络( 即感知机) ， 在线性可分情况下是一个性能优良的分类器，其判别函数可定义为 ，；w x + b 根据支持向量机的理论，向量w 可表示为所有训练样本的线性组合 w = 口，一 若用核函数x ( x ，柚= 卿) d 代替点积0 x 1 ) ，可表示为 ，( x ) = 足( x ，) + 6 ( 1 1 0 ) t = l 上式即为基于核的感知机，在咖c 砷所处的特征空间f ，分类器是线性的，但在 原空问的分类器则成为非线性的。 非线性主成分分析( k e m e tp r i n c i p a lc o m p o n e n ta n a l y s i s ) 嘲 主成分分析p c a 用于以较少的维数描述数据，同时最大限度地保持数据的结 构。给定数据集合 x t ，x 2 ，, x n ，xe r ，目标是找到向量w 使投影量w x 具有最 大的偏差，相当于f i s h e r 判别函数问题，即： 峄( ) 2 ( 1 - 1 1 ) 为使| fw i 尽量小，优化阎题表示最小化目标函数为： 中山大学博士学位论文 r ( w ，。= i 1w w - - 誓主孝( 1 - 1 2 ) 条件为e f = w i x ，i = l ，月l 。引入拉格朗日函数求解后得到： 专盱善q - 一。0 ( 1 。1 3 ) 为得到最大的偏差，应选择最大特征值对应的特征向量，投影量为 z ( x ) = w 石= q ( 1 1 4 ) j = l 引入非线性变换，将投影放在高维特征空间进行，贝0 对偶问题变成 c a = , t a 式中，白= 西0 f ) 妣) = k ( x i ，x j ) ，投影量变成： z = w - 中o ) = c t i k ( x 。- x ) ( 1 - 1 5 ) ( 2 ) 训练算法的改进 由t s v m 对偶问题的求解过程相当于解一个线性约束的二项规划问题( q p ) 需要汁算和存储核函数矩阵，其大小与训练样本数的平方相关，因此，随着样本数 目的增多，所需要的内存也就增大。例如，当样本数目超过4 0 0 0 时，存储核函数 矩阵需要多达1 2 8 m 内存；其次，s v m 在二次型寻优过程中要进行大量的矩阵运 算，多数情况下，寻优算法是占用算法时间的主要部分。通常，训练算法改进的 思路是把要求解的问题分成许多子问题，然后通过反复求解子问题来求得最终的 解，方法有以下几种： 块处理算法m 1 ( c h u n k i n ga l g o r i t h m ) 它的思想是将样本集分成工作样本集和测试样本集，每次对工作样本集利用 二项规划求得最优解，剔除其中的非支持向量，并用训练结果对剩余样本进行检 验，将不符合训练结果的样本( 或其中的一部分) 与本次结果的支持向量合并，成 为一个新的工作样本集，然后重新训练。如此重复下去，直到获得最优结果。其依 据是去掉l a g r a n g e 乘子等于零的训练样本不会影响原问题的解。块算法的一个前 提是：支持向量的数目比较少。然而如果支持向量的数目本身就比较多，那么随着 训练迭代次数的增加，工作样本数也越来越大，就会导致算法无法实施。 中山大学博士学位论文 固定工作样本集算法 它使样本数目固定在足以包含所有的支持向量，且算法速度在计算机可以容 忍的限度内。迭代过程中只是将剩余样本中部分“隋况最糟的样本”与工作样本 集中的样本进行等量交换。即使支持向量的个数超过工作样本集的大小，也不改 变工作样本集的规模。文献 4 6 介绍了一种具体的算法，将样本集分为b 和n 两个 集合，集合b 作为予问题的工作样本集进行s v m 训练，集合n 中所有样本的 l a g r a n g e 乘予均最为零。显然，如果把集合b 巾对应l a g r a n g e 乘了为零的样本i ( 即 a f = 0 ，i b ) 与集合n 中的样爿可( 即嘶= o ，j n ) 交换，不会改变子问题与原问题 的可行性( 即仍旧满足约束条件) 。于是可以按照以下步骤迭代求解：选择集合 b ，构造子问题；求予问题最优解口f ，i b 及6 ，并置= 0 ，je n j 计算g ， ( x j ) y j ，je n ，找出其中g ( x j ) y j 1 的样本，( 其中g ( x f ) = y k ( x j ，) + 6 ) p = l 与b 中满足n 尸0 的样本f 交换，构成新的子问题。需要指出：如果集合b 不足以包括 所有的支持向量，该算法没有提出改变b 的大小的策略，就有可能得不到结果。 s m o 算法【4 7 】 s m o 是固定工作样本集算法的一个极端情况，其工作样本数目为2 。需要 两个样本，因为等式线性约束的存在使得同时至少有两个l a g r a n g e 乘子发生变 化。由于只有两个变最，而且应用等式约束可以将其中一个用另一个表示出来， 所以迭代过程中，每一步子问题的最优解都可以直接甩解析的方法求出来。这样， 算法就避开了复杂的数值求解优化问题的过程；此外，算法还设计了一个两层嵌 套循环，分别选择进入工作样本集的样本，这种启发式策略大大加快了算法的收 敛速度。标准样本集的实验结果证明，s m o 在速度方面表现出良好性能。 除了以上常见的几种算法，下面有关文献也对各自的算法作了总结： 许建华、张学工掣1 8 1 提出了一种基于核函数的非线性感知器算法，特点是 用简单的迭代过程和核函数实现了一种非线性分类器的设计，比线性感知器算法 有效地提高了分类精度。 张莉、周伟达等【8 1 提出了一种用于聚类分析的核聚类方法，通过利用m e r c e r 核将输入空间的样本映射到高维特征空间后，在特征空间中聚类，实现了样本在 特征空间的优化，较好地实现了对差另微弱的样本类之间的聚类，证实了核聚类 中i 大学博上学位论文 方法比经典聚类算法有更加可靠的性能。 涂承胜、刁力力等【1 0 l 系统地介绍了在s v m 组合方法中实现给定的模式识别 问题的s v m 解，以及a d a b o o s t 算法对风险泛函最小点进行“贪婪优化”的方 法，它能提高学习系统预测能力。 宋晓峰、陈德钊等。3 1 对近年来国际上开发的s v m 优化方法做了较详细、完 整的介绍。该文将主流的s v m 优化算法分为两条技术路线。一是基于o s u n a 的 分解策略，通过求解一系列小规模的子q p 问题来一步步实现对原有问题的解决。 二是0 l m a n g a s a r i a n 等人提出的算法，主要是对标准s v m 改造，将与样本有 关的矩阵求逆转换为与样本输入空间维数有关的矩阵求逆，降低了求解问题的复 杂性，算法简单，易于实施。 王国胜提出了最小近点算法( n e a r e s tp o i n ta g l o r i 吐1 m ) 理论的修正算法，它 把s v m 的优化问题等价于两个凸多面体之间的最近点问题，可以有更高的识别 率，并且在大的惩罚系数时成为良好的迭代算法。 田盛丰、黄厚宽 2 5 1 提出了一种回归型支持向量机的简化算法，避免了s v m 应用于函数估计时支持向量过多引起的计算复杂性，可以大幅度地减少支持向量 的数量，从而简化应用，提高学习效率。 卢增祥、李衍达【2 6 】提出了一种交互支持向量机学习算法，它将s v m 与主动 学习方法结合起来，可以根据学习的进程主动选择“有用”的样本进行进一步学 习，能有效地减少对样本的评价量，在文本信息的分类中得到了很好的应用。 刘江华、程君实等【2 7 1 较详细地对s v m 的训练算法做了综述，将算法分为三 大类：以s v m l i g h t 为代表的分解算法，序贯分类法和在线分类法。 分解算法的主要思想是将训练样本分为工作集b 和非工作集n 。b 中的样本 个数为q 个，q 远小于总样本个数。每次只针对工作集b 中的q 个样本训练而固 定n 中的训练样本。算法满足： ( 1 ) 应用有约束条件下二次规划极值点存在的最优条件l m 条件，推出问 题的约束条件和终止条件； ( 2 ) 工作集中训练样本的选择算法，应能保证分解算法能快速收敛。 序贯分类法的基本思想是考虑训练序贯加入，同时考虑其对支持向量有何影 响。 中山大学博士学位沦文 在线训练是指支持向量机的训练是在训练样本单个输入而且训练样本总个 数未知情况下的训练。 4 核函数构造、改进、参数调整及s v m 模型改进 核函数和s v m 模型改进是支持向量机研究的另一个重要方面，文献 9 、 1 8 、 1 9 、 2 9 、 5 0 、 5 6 、 5 7 、 6 0 “6 3 、 6 4 和 6 5 详细地分析了各自研 究的核函数方面的成果。 s v m 的核函数有多项式核函数、径向基函数等。尽管些实验结果表明核函 数的具体形式对分类效果的影响不大，但是核函数的形式以及其参数的确决定了 分类器的类型和复杂程度，它显然应该作为控制分类器性能的手段。 李辉、史忠植等1 9 提出了一种修正支持向量核函数的理论和方法，它利用置 换群的概念明确给出：在样本结合了不变性常识后对样本特征向量的修正公式， 并通过修正核函数，给出了将事物模式组成方面的不变性常识结合到分类器中的 一个通用方法，并给出了在文本领域中的应用。 杨强、吴中福等 i u 将支持向量机和邻域法思想结合起来，提出了基于支持向 量的分段线性学习算法，可以较好地限常0 期望风险，从而构造较好的学习系统。 张文生、王珏等f 1 2 1 重点研究了三个方面的内容：在给出样本点后验概率的 基础上将大规模优化问题分解成最大似然函数和最大分类边界两个小规模优化 的问题；给出了一种新的用后验概率修正最优分离超平面的方法，并分析了新 方法的合理性：用图象分类的三组实例说明本方法的有效性。 陶卿、王珏等 1 4 从闭凸集上投影和支持超平面的角度探讨支持向量的几何 意义和线性分类器设计的几何方法。对线性可分情形，支持向量由一类数据集合 闭凸包在另一类数据集合闭凸包上投影的非零系数向量组成，由s v m 方法决定 的分类超平面位于两投影点关于各自数据集合支持超平面的中间以确保泛化性 能最佳。 肖建华、吴金培1 5 1 根据s v m 的分类原理分析了样本数目差的影响，指出样 本数日相差较悬殊时，s v m 不能获得良好的分类能力。比如在故障诊断时，正 常状态样本数据量总是远大于故障状态样本数据量，当它们差别过大时会影响 s v m 的效果。该文通过对不同类的错分样本用不同惩罚的方法得到修正，效果 良好。 1 6 中ij i 大学博士学位论文 阎辉、张学工等 29 研究了支持向量机方法在一定假设条件下，核函数取为 样本协方差函数作为s v m 核函数的思想，并在此基础上分析了一般情况下在 s v m 中用协方差函数代替核函数的解的具体形式，也推导了克里格方法在 e f ( x ) = 0 条件下解的具体形式。 s e h o l k o p f b 和p l a t t jc 掣6 0 】贝0 较为系统地总结了基于核函数的学习方法。 5 s v m 的应用及简单概括