机器学习论文

现代机器学习理论

题 目：学 院：专 业：学 号：学生姓名：论文

综述机器学习与支持向量机 电子工程学院

综述机器学习与支持向量机

摘要

机器学习是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能，它是人工智能的核心，是使计算机具有智能的根本途径。

基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测，包括模式识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。

支持向量机是从统计学发展而来的一种新型的机器学习方法，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势，但是，支持向量机方法中也存在着一些亟待解决的问题，主要包括：如何用支持向量机更有效的解决多类分类问题，如何解决支持向量机二次规划过程中存在的瓶颈问题、如何确定核函数以及最优的核参数以保证算法的有效性等。

本文详细介绍机器学习的基本结构、发展过程及各种分类，系统的阐述了统计学习理论、支持向量机理论以及支持向量机的主要研究热点，包括求解支持向量机问题、多类分类问题、参数优化问题、核函数的选择问题等，并在此基础上介绍支持向量机在人脸识别中的应用，并通过仿真实验证明了算法的有效性。

关键词：机器学习；统计学习理论；SVM；VC维；人脸识别

I

The Summarization of Machine Learning

and Support Vector Machine

ABSTRACT

Machine learning is to study how a computer simulates or realizes human behaviors to acquire new information and skills, then rebuilds its knowledge structure to improve itself capability constantly. It is the core of Artificial Intelligence，and is the underlying way in which a computer develops intelligence.

Machine learning based on data is one of the most important aspects of modern intelligence technology. It is to investigate how to find a rule starting from data observation, and use the rule to predict future data and unavailable data. Statistics is one of the most common important theory elements of the existing methods of machine learning, including Pattern Recognition and Neural Networks.

SVM(Support Vector Machine) is a novel method of machine learning evoling from Statistics. SVM presents many own advantages in solving machine learning problems such as small samples, nonlinearity and high dimension. However, SVM methods exist some problems need to be resolved, mainly including how to deal with multi-classification effectively, how to solve the bottle-neck problem appearing in quadratic programming process, and how to decide kernel function and optimistical kernel parameters to guarantee effectivity of the algorithm.

This paper has introduced in detail the structure, evolvement history, and kinds of classification of machine learning, and demonstrated systemly SLT(Statistical Learning Theory), SVM and research hotspots of SVM, including seeking SVM problems, multi-classification, parameters optimization, kernel function selection and so on. The application on human face recognition has been introduced based on above theory, and the simulation experiment has validated the algorithm.

Keywords: Machine learning, SLT, SVM, VC dimension, Human face recognition

II

目 录

摘要................................................................................................................................ I ABSTRACT .................................................................................................................. II 1.绪论............................................................................................................................. 1 1.1研究背景及意义.................................................................................................. 1 1.1.1 机器学习概念的出现.................................................................................. 1 1.1.2支持向量机的研究背景............................................................................... 1 1.2本文主要内容...................................................................................................... 3 2.机器学习的结构及分类............................................................................................. 4 2.1机器学习定义及发展.......................................................................................... 4 2.2机器学习系统的基本结构.................................................................................. 5 2.3机器学习的分类.................................................................................................. 6 2.4目前研究领域...................................................................................................... 9 3.支持向量机的原理................................................................................................... 10 3.1统计学习理论.................................................................................................... 10 3.1.1机器学习问题............................................................................................. 10 3.1.2统计学理论的发展与支持向量机............................................................. 11 3.1.3VC维理论 ................................................................................................... 12 3.1.4推广性的界................................................................................................. 12 3.1.5结构风险最小化原则................................................................................. 13 3.2支持向量机理论................................................................................................ 14 3.2.1最优分类面................................................................................................. 16 3.2.2标准支持向量机......................................................................................... 18 4.支持向量机的主要研究热点................................................................................... 20 4.1支持向量机多类分类方法................................................................................ 20 4.2求解支持向量机的二次规划问题.................................................................... 23 4.3核函数选择及其参数优化................................................................................ 25 5.支持向量机的算法仿真........................................................................................... 27 5.1人脸识别的理论基础........................................................................................ 27 5.2基于PCA方法和SVM原理的人脸识别仿真 ............................................... 28 6.参考文献................................................................................................................... 33

1.绪论

1.1研究背景及意义

1.1.1 机器学习概念的出现

学习是人类具有的一种重要智能行为，但究竟什么是学习，长期以来却众说纷纭。社会学家、逻辑学家和心理学家都各有其不同的看法。按照人工智能大师西蒙的观点，学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或相同类似的任务时，会比现在做得更好或效率更高。西蒙对学习给出的定义本身，就说明了学习的重要作用。在人类社会中，不管一个人有多深的学问，多大的本领，如果他不善于学习，我们都不必过于看重他。因为他的能力总是停留在一个固定的水平上，不会创造出新奇的东西。但一个人若具有很强的学习能力，则不可等闲视之了。机器具备了学习能力，其情形完全与人类似。

什么是机器学习？迄今尚没有统一的定义，由其名字可理解为机器学习是研究如何使用机器来模拟人类学习活动的一门学科。稍微严格的提法是机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。这里所说的“机器”，指的就是计算机，现在是电子计算机，以后还可能是种子计算机、光子计算机或神经计算机等等。

机器能否像人类一样能具有学习能力呢？1959年美国的塞缪尔(Samuel)设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对弈中改善自己的棋艺。4年后，这个程序战胜了设计者本人。又过了3年，这个程序战胜了美国一个保持8年之久的常胜不败的冠军。这个程序向人们展示了机器学习的能力，提出了许多令人深思的社会问题与哲学问题。

机器的能力是否能超过人的，很多持否定意见的人的一个主要论据是：机器是人造的，其性能和动作完全是由设计者规定的，因此无论如何其能力也不会超过设计者本人。这种意见对不具备学习能力的机器来说的确是对的，可是对具备学习能力的机器就值得考虑了，因为这种机器的能力在应用中不断地提高，过一段时间之后，设计者本人也不知它的能力到了何种水平。

1.1.2支持向量机的研究背景

支持向量机(Support Vector Machine，SVM)方法是在统计学习理论(Statistical Learning Theory,SLT)基础上发展而来的一种机器学习方法，SVM在使用结构风险最小化原则替代经验风险最小化原则的基础上，又结合了统计学习、机器学习和神经网络等方面的技术，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势。它一方面可以克服神经网络等方法所固有的过学习和欠学

1

习问题，另一方面又有很强的非线性分类能力，通过引入核函数，将输入空间的样本映射到高维特征空间，输入空间的线性不可分问题就转化为特征空间的线性可分问题。支持向量机被看作是对传统分类器的一个好的发展，并被证明可在保证最小化结构风险的同时，有效地提高算法的推广能力。随着计算机技术的蓬勃发展以及人们在各个领域对模式识别技术的需求与应用，计算机模式识别技术也有了很大的发展。模式识别就是设计一个能够对未知数据进行自动分类的方法，常用模式识别方法有统计识别方法、句法结构识别方法、模糊理论识别方法、神经网络识别方法、模板匹配识别方法和支持向量机的识别方法等。其中，基于支持向量机的模式识别方法是目前最为有效的模式识别方法之一。

V．Vapnik等人早在20世纪60年代就开始研究小样本情况下的机器学习问题，当时这方面的研究尚不十分完善，且数学上比较艰涩，大多数人难以理解和接受，直到90年代以前还没能够提出将其理论付诸实现的方法，加之当时正处在其他学习方法飞速发展的时期，因此这方面的研究一直没有得到足够的重视。直到90年代中期，小样本情况下的机器学习理论研究逐渐成熟起来，形成了较完善的理论体系——统计学习理论(Statistical Learning Theory,SLT)[2]，而同时，神经网络等新兴的机器学习方法的研究则遇到了许多困难，在这种情况下，试图从更本质上研究机器学习问题的统计学习理论逐步得到重视。

统计学习理论是建立在坚实的理论基础之上的，为解决小样本学习问题提供了统一的框架。统计学习理论的核心是VC维理论与结构风险最小化理论，它用VC维来描述学习机器的复杂度，并以此为出发点导出了学习机器推广能力的界的理论。该理论致力于寻找在小样本情况下学习问题的最优解，而不需要利用样本数趋于无穷大的渐进性条件，这使得统计学习理论在小样本情况下同样能得到具有推广价值的知识。

1992年至1995年，在统计学习理论的基础上发展出了一种新型的学习机器——支持向量机(Support Vector Machine简称SVM)。支持向量机是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模犁的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力。支持向量机被看作是对传统分类器的一个好的发展，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势。

SVM方法是由Vapnik及其合作者Boser、Guyon、Cortes及Scholkopf在AT&T Bell实验室共同创造与发展起来的一种新方法[3]。近年来，许多关于SVM方法的研究，包括算法本身的改进和算法的实际应用，都陆续被提了出来，如Scholkoph等人提出了v.SVM方法、Suykens等人提出了最小二乘支持向量机(LS．SVM)、Zhang提出的类中心支持向量机(CSVM)方法、Lin等提出了模糊支

2

持向量机方法(Fuzzy．SVM)等[4]。其中，在理论上主要以Vapnik及其研究小组做了大量开创性及奠基性的工作。

随着支持向量机的不断发展，人们对支持向量机的研究也越来越细化，其主要研究方向大致可分为：求解支持向量机问题，支持向量机多类分类问题，参数的选择和优化问题等。

求解一个SVM问题最终都转化为解一个具有线性约束的凸规划问题或其对偶问题的二次规划问题(Quadratic Programming，QP)。传统的方法是利用标准二次型优化技术解决对偶问题，这就导致算法的训练速度很慢，一方面是由于SVM需要计算和存储核函数矩阵，当样本规模较大时必然导致内存需求增加；另一方面，SVM在二次寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法占用了大部分的算法时间，这就使得存储空间和和计算时间成了求解二次规划问题的瓶颈。常用的解决方法是将一个大的二次规划问题转化为若干个小的二次规划问题以提高分类效率，如块算法、分解算法、SMO算法、增式算法等等。

支持向量机分类理论是针对两类分类问题提出的，然而，现实世界的分类问题，如船舰识别、字体识别、人脸识别等，都属于多类分类的范畴。如何将二类分类方法扩展到多类分类情况是支持向量机方法研究的重要内容之一。目前，用SVM解决多类分类问题方法主要是通过构造或组合多个两类分类器来实现多类问题的分类。子分类器的构造和组合将两类分类扩展到多类问题，将多类分类问题逐步转化为两类分类问题。常用的算法有“one---against---one”方法、“one--against--rest”方法、“基于决策树的方法”等。支持向量机多类分类方法的引入拓展了支持向量机的应用范围，也加快了支持向量机方法的改进和创新，同时，支持向量机的核函数的选择以及核参数的选择也是一个重要的研究方向。

1.2本文主要内容

本文旨在综述机器学习及支持向量机的基本原理及研究方向。第一章为绪论，介绍了机器学习概念的出现与支持向量机的背景知识；第二章介绍了机器学习的发展过程、基本结构、分类及应用领域；第三章详细介绍了支持向量机的原理，包括统计学习理论和支持向量机理论；第四章介绍了支持向量机的主要研究热点，包括求解支持向量机问题、多类分类问题、参数优化问题、核函数的选择问题等，并列出支持向量机的主要优点；第五章给出支持向量机算法的一个仿真实验。

3

2.机器学习的结构及分类

2.1机器学习定义及发展

机器学习(Machine Learning)是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域，它主要使用归纳、综合而不是演绎。

学习能力是智能行为的一个非常重要的特征，但至今对学习的机理尚不清楚。人们曾对机器学习给出各种定义。H.A.Simon认为，学习是系统所作的适应性变化，使得系统在下一次完成同样或类似的任务时更为有效。R.s.Michalski认为，学习是构造或修改对于所经历事物的表示。从事专家系统研制的人们则认为学习是知识的获取。这些观点各有侧重，第一种观点强调学习的外部行为效果，第二种则强调学习的内部过程，而第三种主要是从知识工程的实用性角度出发的。

机器学习在人工智能的研究中具有十分重要的地位。一个不具有学习能力的智能系统难以称得上是一个真正的智能系统，但是以往的智能系统都普遍缺少学习的能力。例如，它们遇到错误时不能自我校正；不会通过经验改善自身的性能；不会自动获取和发现所需要的知识。它们的推理仅限于演绎而缺少归纳，因此至多只能够证明已存在事实、定理，而不能发现新的定理、定律和规则等。随着人工智能的深入发展，这些局限性表现得愈加突出。正是在这种情形下，机器学习逐渐成为人工智能研究的核心之一。它的应用已遍及人工智能的各个分支，如专家系统、自动推理、自然语言理解、模式识别、计算机视觉、智能机器人等领域。其中尤其典型的是专家系统中的知识获取瓶颈问题，人们一直在努力试图采用机器学习的方法加以克服。

机器学习的研究是根据生理学、认知科学等对人类学习机理的了解，建立人类学习过程的计算模型或认识模型，发展各种学习理论和学习方法，研究通用的学习算法并进行理论上的分析，建立面向任务的具有特定应用的学习系统。这些研究目标相互影响相互促进。

自从1980年在卡内基--梅隆大学召开第一届机器学术研讨会以来，机器学习的研究工作发展很快，已成为中心课题之一。

机器学习是人工智能研究较为年轻的分支，它的发展过程大体上可分为4个时期：

第一阶段是在50年代中叶到60年代中叶，属于热烈时期；

第二阶段是在60年代中叶至70年代中叶，被称为机器学习的冷静时期；

4

第三阶段是从70年代中叶至80年代中叶，称为复兴时期； 机器学习的最新阶段始于1986年。

机器学习进入新阶段的重要表现在下列诸方面：

(1) 机器学习已成为新的边缘学科并在高校形成一门课程。它综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机器学习理论基础。

(2) 结合各种学习方法，取长补短的多种形式的集成学习系统研究正在兴起。特别是连接学习符号学习的耦合可以更好地解决连续性信号处理中知识与技能的获取与求精问题而受到重视。

(3) 机器学习与人工智能各种基础问题的统一性观点正在形成。例如学习与问题求解结合进行、知识表达便于学习的观点产生了通用智能系统SOAR的组块学习。类比学习与问题求解结合的基于案例方法已成为经验学习的重要方向。

(4) 各种学习方法的应用范围不断扩大，一部分已形成商品。归纳学习的知识获取工具已在诊断分类型专家系统中广泛使用。连接学习在声图文识别中占优势。分析学习已用于设计综合型专家系统。遗传算法与强化学习在工程控制中有较好的应用前景。与符号系统耦合的神经网络连接学习将在企业的智能管理与智能机器人运动规划中发挥作用。

(5) 与机器学习有关的学术活动空前活跃。国际上除每年一次的机器学习研讨会外，还有计算机学习理论会议以及遗传算法会议。

2.2机器学习系统的基本结构

机器学习系统的基本结构如图2.1所示，环境向系统的学习部分提供某些信息，学习部分利用这些信息修改知识库，以增进系统执行部分完成任务的效能，执行部分根据知识库完成任务，同时把获得的信息反馈给学习部分。在具体的应用中，环境，知识库和执行部分决定了具体的工作内容，学习部分所需要解决的问题完全由上述3部分确定。下面我们分别叙述这3部分对设计学习系统的影响。

环境 学习 知识库

图 2.1 学习系统的基本结构

执行 影响学习系统设计的最重要的因素是环境向系统提供的信息。或者更具体地说是信息的质量。知识库里存放的是指导执行部分动作的一般原则，但环境向学习系统提供的信息却是各种各样的。如果信息的质量比较高，与一般原则的差别比较小，则学习部分比较容易处理。如果向学习系统提供的是杂乱无章的指导执行具体动作的具体信息，则学习系统需要在获得足够数据之后，删除不必要的细

5

节，进行总结推广，形成指导动作的一般原则，放入知识库，这样学习部分的任务就比较繁重，设计起来也较为困难。

因为学习系统获得的信息往往是不完全的，所以学习系统所进行的推理并不完全是可靠的，它总结出来的规则可能正确，也可能不正确。这要通过执行效果加以检验。正确的规则能使系统的效能提高，应予保留；不正确的规则应予修改或从数据库中删除。

知识库是影响学习系统设计的第二个因素。知识的表示有多种形式，比如特征向量、一阶逻辑语句、产生式规则、语义网络和框架等等。这些表示方式各有其特点，在选择表示方式时要兼顾以下4个方面：

(1)表达能力强。(2)易于推理。(3)容易修改知识库。(4)知识表示易于扩展。 对于知识库最后需要说明的一个问题是学习系统不能在全然没有任何知识的情况下凭空获取知识，每一个学习系统都要求具有某些知识理解环境提供的信息，分析比较，做出假设，检验并修改这些假设。因此，更确切地说，学习系统是对现有知识的扩展和改进。

执行部分是整个学习系统的核心，因为执行部分的动作就是学习部分力求改进的动作。同执行部分有关的问题有3个：复杂性、反馈和透明性。

2.3机器学习的分类

1.基于所获取知识的表示形式分类

学习系统获取的知识可能有：行为规则、物理对象的描述、问题求解策略、各种分类及其它用于任务实现的知识类型。对于学习中获取的知识，主要有以下一些表示形式：

1）代数表达式参数：学习的目标是调节一个固定函数形式的代数表达式参数或系数来达到一个理想的性能。

2）决策树：用决策树来划分物体的类属，树中每一内部节点对应一个物体属性，而每一边对应于这些属性的可选值，树的叶节点则对应于物体的每个基本分类。

3）形式文法：在识别一个特定语言的学习中，通过对该语言的一系列表达式进行归纳，形成该语言的形式文法。

4）产生式规则：产生式规则表示为条件—动作对，已被极为广泛地使用。学习系统中的学习行为主要是：生成、泛化、特化或合成产生式规则。

5）形式逻辑表达式：形式逻辑表达式的基本成分是命题、谓词、变量、约束变量范围的语句及嵌入的逻辑表达式。

6）图和网络：有的系统采用图匹配和图转换方案来有效地比较和索引知识。 7）框架和模式（schema）：每个框架包含一组槽，用于描述事物（概念和

6

个体）的各个方面。

8）计算机程序和其它的过程编码：获取这种形式的知识，目的在于取得一种能实现特定过程的能力，而不是为了推断该过程的内部结构。

9）神经网络：这主要用在联接学习中，学习所获取的知识，最后归纳为一个神经网络。

10）多种表示形式的组合：有时一个学习系统中获取的知识需要综合应用上述几种知识表示形式。

根据表示的精细程度，可将知识表示形式分为两大类：泛化程度高的粗粒度符号表示、泛化程度低的精粒度亚符号(sub-symbolic)表示。像决策树、形式文法、产生式规则、形式逻辑表达式、框架和模式等属于符号表示类；而代数表达式参数、图和网络、神经网络等则属亚符号表示类。

2.按应用领域分类

最主要的应用领域有：专家系统、认知模拟、规划和问题求解、数据挖掘、网络信息服务、图象识别、故障诊断、自然语言理解、机器人和博弈等领域。从机器学习的执行部分所反映的任务类型上看，目前大部分的应用研究领域基本上集中于以下两个范畴：分类和问题求解。

（1）分类任务要求系统依据已知的分类知识对输入的未知模式（该模式的描述）作分析，以确定输入模式的类属，相应的学习目标就是学习用于分类的准则（如分类规则）。

（2）问题求解任务要求对于给定的目标状态，寻找一个将当前状态转换为目标状态的动作序列；机器学习在这一领域的研究工作大部分集中于通过学习来获取能提高问题求解效率的知识（如搜索控制知识，启发式知识等）。

3.综合分类

综合考虑各种学习方法出现的历史渊源、知识表示、推理策略、结果评估的相似性、研究人员交流的相对集中性以及应用领域等诸因素，将机器学习方法区分为以下六类：

1）经验性归纳学习(empirical inductive learning)

经验性归纳学习采用一些数据密集的经验方法（如版本空间法、ID3法，定律发现方法）对例子进行归纳学习，其例子和学习结果一般都采用属性、谓词、关系等符号表示。它相当于基于学习策略分类中的归纳学习，但扣除联接学习、遗传算法、加强学习的部分。

2）分析学习（analytic learning）

分析学习方法是从一个或少数几个实例出发，运用领域知识进行分析。其主要特征为：

7

 推理策略主要是演绎，而非归纳；

 使用过去的问题求解经验（实例）指导新的问题求解，或产生能更有效地运用领域知识的搜索控制规则。

分析学习的目标是改善系统的性能，而不是新的概念描述。分析学习包括应用解释学习、演绎学习、多级结构组块以及宏操作学习等技术。

3）类比学习

它相当于基于学习策略分类中的类比学习。目前，在这一类型的学习中比较引人注目的研究是通过与过去经历的具体事例作类比来学习，称为基于范例的学习(case_based learning)，或简称范例学习。

4）遗传算法（genetic algorithm）

遗传算法模拟生物繁殖的突变、交换和达尔文的自然选择（在每一生态环境中适者生存）。它把问题可能的解编码为一个向量，称为个体，向量的每一个元素称为基因，并利用目标函数（相应于自然选择标准）对群体（个体的集合）中的每一个个体进行评价，根据评价值（适应度）对个体进行选择、交换、变异等遗传操作，从而得到新的群体。遗传算法适用于非常复杂和困难的环境，比如，带有大量噪声和无关数据、事物不断更新、问题目标不能明显和精确地定义，以及通过很长的执行过程才能确定当前行为的价值等。同神经网络一样，遗传算法的研究已经发展为人工智能的一个分支，其代表人物为霍勒德。

5）联接学习

典型的联接模型实现为人工神经网络，其由称为神经元的一些简单计算单元以及单元间的加权联接组成。

6）加强学习（reinforcement learning）

加强学习的特点是通过与环境的试探性（trial and error）交互来确定和优化动作的选择，以实现所谓的序列决策任务。在这种任务中，学习机制通过选择并执行动作，导致系统状态的变化，并有可能得到某种强化信号（立即回报），从而实现与环境的交互，强化信号就是对系统行为的一种标量化的奖惩。系统学习的目标是寻找一个合适的动作选择策略，即在任一给定的状态下选择哪种动作的方法，使产生的动作序列可获得某种最优的结果（如累计立即回报最大）。

在综合分类中,经验归纳学习、遗传算法、联接学习和加强学习均属于归纳学习，其中经验归纳学习采用符号表示方式，而遗传算法、联接学习和加强学习则采用亚符号表示方式；分析学习属于演绎学习。

实际上，类比策略可看成是归纳和演绎策略的综合。因而最基本的学习策略只有归纳和演绎。

从学习内容的角度看，采用归纳策略的学习由于是对输入进行归纳，所学习

8

的知识显然超过原有系统知识库所能蕴涵的范围，所学结果改变了系统的知识演绎闭包，因而这种类型的学习又可称为知识级学习；而采用演绎策略的学习尽管所学的知识能提高系统的效率，但仍能被原有系统的知识库所蕴涵，即所学的知识未能改变系统的演绎闭包，因而这种类型的学习又被称为符号级学习。

2.4目前研究领域

目前，机器学习领域的研究工作主要围绕以下三个方面进行：

1）面向任务的研究。研究和分析改进一组预定任务的执行性能的学习系统。 2）认知模型。研究人类学习过程并进行计算机模拟。

3）理论分析。从理论上探索各种可能的学习方法和于应用领域的算法，机器学习是继专家系统之后人工智能应用的又一重要研究领域，也是人工智能和神经计算的核心研究课题之一。现有的计算机系统和人工智能系统没有什么学习能力，至多也只有非常有限的学习能力，因而不能满足科技和生产提出的新要求。对机器学习的讨论和机器学习研究的进展，必将促使人工智能和整个科学技术的进一步发展。

9

3.支持向量机的原理

支持向量机(Support Vector Machine，SVM)是由Vapnik及其合作者共同创造与发展起来的一种新的机器学习方法，其核心内容在1992年至1995年间提出的。目前，支持向量机已经成为机器学习领域的标准工具之一并仍在不断的发展之中。支持向量机集成了机器学习领域的若干标准，如最人间隔超平面，Mercer核，凸二次规划，松弛变量等技术等。支持向量机在语音识别、字符识别等领域均获得了目前为止最好的性能。在美国的科学杂志上，支持向量机被认为“是机器学习领域中的一个令人瞩目的发展方向”[10]。

3.1统计学习理论

统计学习理论建立在一套较为坚实的理论基础之上，为解决有限样本的学习问题提供了一个统一的框架。它能将许多现有的方法纳入其中，有望帮助解决许多原来难以解决的问题，比如神经网络的结构选择问题、局部最小点问题等。

3.1.1机器学习问题

机器学习问题[1]可以看作是通过某种训练方法，对某一系统的输入与输出之间的依赖关系进行估计，并且期望这一估计可以对任意给定输入尽量准确地进行输出预测。一般地，机器学习问题可以表示为：假设变量y与x之间存在一定的未知依赖关系，即遵循某一未知的联合概率Fx,y(x和y之间的确定性关系可以看作是其特例)，机器学习问题就是根据n个同分布观测样本在一组函数fx,中求一个最优的函数fx,a对x1,y1,x2,y2,...,xn,yn，

依赖关系进行估计，使得期望风险最小。

Ry,fx,dFx,y 3-(1)

L其中fx,称作预测函数集，为函数的广义参数，fx,可以表示任何函数集；Ly,fx,为由于用fx,对y进行预测而造成的损失，不同类型的学习问题有不同形式的损失函数。

在上面问题的表述中，学习的目标在于使期望风险最小化，但是，由于可以利用的信息只有样本最初的观测样本x1,y1,x2,y2,...,xn,yn，因此，期望风险3-(1)是无法计算的。传统的学习方法是采用了所谓经验风险最小化(ERM)准则[11]，即用样本定义经验风险

1nRempLyi,fxi, 3-(2)

ni1来逼近3-(1)定义的期望风险，用对参数求经验风险Remp的最小值代替求期望风险R的最小化，这就是所谓的经验风险最小化原则。

10

事实上，用经验风险最小化准则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理的想当然做法，但这种思想却在多年的机器学习方法研究中占据了主要地位。而实际上，即使可以假定当n趋向于无穷大时，公式3-(2)趋近于公式3-(1)，但在很多实际的问题中，样本数目也离无穷大相去甚远，那么在有限样本情况下，采用最小化经验风险准则，得到的结果能使真实风险也较小吗？要得到这个答案，需要了解统计学习理论对采用经验风险最小化准则解决期望风险最小化问题的前提，如果这些前提不成立时，需要找到更合理的准则。

在早期的机器学习理论的研究中，人们总是把注意力集中在如何使Remp更小，但很快便发现，一味追求训练误差小并不是总能达到好的预测效果。在某些情况下，当训练误差过小反而会导致推广能力的下降，这就是几乎所有神经网络研究者都曾得到的过学习(Overfitting)问题，即训练误差过小反而导致推广能力下降、真实风险的增加。从理论上看，模式识别中也存在同样的问题，但因为通常使用的分类器模型(比如线性分类器)都是相对比较简单的，因此过学习问题并不像神经网络中那样突出。支持向量机是在统计学习理论的基础上发展起来的，它能够有效地解决小样本问题，同时避免过学习问题的产生，它的出现推动了机器学习理论和技术的发展。

3.1.2统计学理论的发展与支持向量机

统计学习理论(Statistical Learning Theory，SLT)是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。V. Vapnik等人从六、七十年始致力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性的进展，统计学习理论开始受到越来越广泛地重视。同时，在这一理论基础上发展了一种新的通用学习方法---支持向量机。目前，支持向量机已初步表现出很多优于各种传统方法的性能。

概括说来，统计学习理论就是研究小样本统计估计和预测的理论，主要内容包括以下四个方面：

(1)经验风险最小化准则下统计学习一致性的条件； (2)在这些条件下关于统计学习方法推广性的界的结论； (3)在这些界的基础上建立的小样本归纳推理准则； (4)实现新的准则的实际方法(算法)。

其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是VC维。统计学习理论被认为是只前针对小样本统计估计和预测学习的最佳理论，它从理论上较系统地研究了经验风险最小化原则成立的条件，有限样本下经验风险与期

11

望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。

3.1.3VC维理论

模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2h种形式分开，则称函数集能够把h个样本打散；函数集的VC维就是它能打散的最大样本数目h。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大。

VC维反映了函数集的学习能力，VC维越大则学习机器越复杂(容量越大)。遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只确定了一些特殊的函数集的VC维。比如在n维实数空间中线性分类器和线性实函数的VC维是n1，对于一些比较复杂的学习机器(如神经网络)，其VC维除了与函数集(神经网结构)有关外，还受学习算法等的影响，其确定更加困难。但是，在实际应用统计学习理论时，可以通过变通的办法巧妙地避开直接求VC维的问题。

3.1.4推广性的界

统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之 间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有 函数(包括使经验风险最小的函数)，经验风险Remp和实际风险R之间以概率1满足如下关系：

hln2nh1ln4RRemp 3-(3)

n其中h是函数集的VC维，n是样本数。

这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险(训练误差)，另一部分称作置信范围，它和学习机器的VC维及训练样本数有关，可以简单地表示为：

RRemphn 3-(4)

它表明，在有限训练样本下，学习机器的VC维越高(复杂性越高)则置信范围越大，导致真实风险与经验风险之间可能的差别越大，这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性，这一理论可以由图3.1说明。

12

图3.1 置信范围、经验风险与实际风险之间的关系

由图3.1可以看出，当样本数目n固定，算法的VC维增大时，它对给定训练样本集合有更强的分类或拟合能力，导致了更小的经验风险Remp，甚至使它为零。但是，VC维增大时，hn也随之增大，即放大了置信范围，从而减小了算法具有小的实际风险R的可能性。反之，若VC维缩小，那么它对给定的训练样本集合的分类或拟合能力减弱，导致了大的经验风险，此时，虽然置信区间hn缩小了，但仍不能保证获得小的实际风险。可以看出n固定时Remp与hn是一对矛盾体，它们不可能同时都减小，但确实存在某个h值使实际风险上界达到最小值。

3.1.5结构风险最小化原则

经验风险最小化原则是目前绝大多数模式识别方法的基础，其定义为训练集上的平均错误率，用于对整个样本集的期望风险进行估计，它建立在样本数目足够多的前提下，致使各种方法只有在样本数趋向无穷大时，其性能才有理论上的保证。而在现实世界的应用中，这一前提并不总能被满足，这时大多数此类方法都难以取得理想的结果。

由3.1.4节中的推广性的界可以看出，影响期望风险上界的因子有两个方面：首先是训练集的规模n，其次是VC维h。可见，在保证分类精度(经验风险)的同时，降低学习机器的VC维，可以使学习机器在整个样本集上的期望风险得到控制，这就是结构风险最小化(Structure Risk Minimization，简称SRM)的由来。

由VC维的讨论可以看到，经验风险和期望风险依赖于学习机器函数族的选

13

择。把函数集sfx,,分解为一个函数子集序列

s1s2...sk... 3-(5)

使各个子集能够按照置信范围的大小排序，即

h1h2...hk 3-(6)

所谓结构风险最小化，便是构造一组嵌套的函数子集，使得其VC维由内向外依次递增，然后在其上寻找经验风险和置信范围之和最小的子集，从而使得实际风险的上界最小化，如图3.2所示

图3.2 结构风险最小化示意图

基于结构风险最小化准则的统计学习理论是一种专门研究小样本的统计理论，它为研究有限样本情况下的统计模式识别，并为更广泛的机器学习问题建立了一个较好的理论框架，同时也发展出了一种新的模式识别方法——支持向量机，从而能够较好地解决小样本的学习问题。

3.2支持向量机理论

SVM方法是由Vapnik及其合作者Boser、Guyon、Cortes及Scholkopf在AT&TBell实验室共同创造与发展起来的一种新的学习方法。近年来，许多关于SVM方法的研究，包括算法本身的改进和算法的实际应用，都陆续被提了出来，其中在理论上主要以Vapnik及其研究小组做了大量开创性及奠基性的工作。目

14

前SVM正处于不断发展阶段，现在已经成为机器学习领域的标准工具之一。

支持向量机是个三层网络结构，是一个多输入、单输出的学习机器，其体系结构如图3.3所示

图3.3 支持向量机的体系结构

其中，位于体系结构最底层的x1,x2,x3,...,xn是输入样本，Kxi,xi1,2,...,n是样本x与支持向量在特定空间的内积，ii1,2,...,n是拉格朗日乘子，fx是决策函数的输出。图3.3清晰的表示出支持向量机的逻辑概念框架，首先确定训练样本作为支持向量机的输入，然后选择适当的核函数，将样本从输入空间映射到高维的特征空间，根据优化问题求解出来的支持向量最终得到相应的决策函数。它与传统的神经网络的最大区别在于：神经网络结构的确定大多是凭经验选取的，有一定的盲目性，无法确定泛化的置信空间界限，所以无法保证网络的推广能力，容易出现过学习的现象。而支持向量机网络通过结构化风险最小化归纳原理控制学习单元的VC维的上界，了学习单元的能力，在一定程度上避免了过学习现象。

支持向量机是建立在统计学习理论的VC维理论和结构风险最小化原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期

15

获得最好的推广能力。支持向量机被看作是对传统分类器的一个好的发展，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势。概括的说，支持向量机是以寻找最优分类面为目标、以二次规划为手段、以非线性映射为理论基础的统计学习方法。下面将分别从这几个方面对支持向量机理论进行系统的阐述。

3.2.1最优分类面

支持向量机是从线性可分情况下的最优分类面发展而来的，其基本思想可用图3.4表示，对应于一维空间中的点，二维空间中的直线，三维空间中的平面，以及高维空问中的超平面。图中圆形和三角形的标志分别代表两类样本，中间的实线为两类样本之间的分类超平面，两条虚线分别表示过各类中距离分类面最近的样本且平行于分类面的超平面，它们之间的距离叫做分类间隔(margin)。

图3.4 最优分类面示意图

最优分类面在把两类正确分开的同时保证分类间隔最大，根据结构风险最小化原则，前者是保证经验风险最小，而后者使分类问隔最大，导致VC维最小，实际上就是使推广性的界中的置信范围最小，从而达到使真实风险最小。后者保证VC维最小，从而达到使真实风险最小。

假定给出一个样本集xi,yi,i1,...n,xRd,y1,1满足

tyixib10,i1,...,n 3-(7)

其中txib0是分类面方程，此时分类间隔为22，最终目标是求一个

2分类面，使得能够将两类样本正确分类的同时保证分类间隔最大，这里是使最小。如图3.4所示，中间的实线为最优分类面，两侧虚线上的样本即为支持向

16

量。因而，在线性可分的情况下，得到的SVM的目标函数是：

12 3-(8)

2ts..t yixib10,i1,...,n 3-(9)

为求得公式3-(8)的最小值，定义如下Lagrange函数：

n12tL,b,iyixb1 3-(10) 2i1其中i0为各样本对应的Lagrange乘子。为了求解表达式3-(10)的最小值，可以令该泛函对、b求偏导，并令其等于零，我们得到表达式3-(10)的相应的对偶函数：

1nQiijyiyjxi,xj 3-(11)

2i,j1i1ns..t

yii1ni0 i0 i1,...,n 3-(12)

在表达式3-(12)的约束下，求得表达式3-(11)的唯一解i，其中，不为零Lagrange乘子i所对应的样本就是支持向量。

若i*为最优解，相应的求出最优分类面权系数向量*和分类器的阈值b* ：

*b*xisv*iiiyx 3-(13)

1**x1*x*1 3-(14) 2其中x*1、x*1分别表示两类中任意一个支持向量。

由上面推导得出的参数、b可以得到分类器的决策函数：

fxsgn,xbsgniyixi,xb 3-(15)

xisv上述方法可以确保在线性可分的情况下将全部样本正确分类，如果对于线性不可分或者事先不知道是否线性可分的情况，可以通过引入非负松弛变量

i,i1,2,...,n来允许错分样本的存在。相应地，表达式3-(7)、3-(8)、3-(9)分别变为：

tyixib1i0,i1,...,n 3-(16)

1n2Ci 3-(17)

2i1ts..t yixib1i0,i1,...,n 3-(18)

其中，C0是一个自定义的惩罚因子，它表示对错分样本惩罚的程度，用来控

17

制样本偏差与机器推广能力之间的折衷。C越大，对错分样本的惩罚就越大，对错分样本的约束程度就越大。

容许错分的分类面又称为软问隔分类面[12]，求解表达式3-(17)的优化问题和求解表达式3-(8)的优化问题类似，都是通过引入相应的拉格朗日函数及其对偶问题并对其求解，最终得到最优分类判别函数。

3.2.2标准支持向量机

支持向量机是从线性可分情况下的最优分类面发展而来的，前面介绍的是在线性分类情况下如何求解最优分类超平面。而在实际问题中，分类问题是常常是非线性问题，理想的最优分类面应该是非线性的。支持向量机解决非线性问题的思想是：首先选择适当的核函数[13]，将低维空间的训练样本通过非线性映射映射到高维特征空间中，然后用前面介绍的方法在高维空间中求解最优分类超平面，高维空问中得到的线性分类面就对应着低维空间的非线性分类面。如图3.5所示，支持向量机处理非线性分类问题时，只是比线性分类问题多了个非线性映射过程，设定该非线性映射为：

xx 3-(19)

则表达式3-(11)的优化问题最转化为：

1nQaiijyiyjxixj 3-(20)

2i,j1i1n图3.5 输入空间和特征空间所对应的分类面示意图

非线性映射的引入很好的解决了非线性分类问题，同时也增加了优化求解的困难，使3-(20)的计算非常不容易实现，但是注意到，上面的对偶问题中只涉及到高维空间中的内积运算，即xixj，而没有单独的映射xi。因此，可以考虑是否可以找到输入空间的一个函数K来替代特征空间的内积运算，即

18

Kxi,xjxixj 3-(21)

这样就省去了高维空间中复杂的内积计算，我们甚至不需要知道映射变换•,的具体表示形式。根据泛函的有关理论，只要Kxi,xj满足下列定理的Mercer条件，它就对应某一变换空间的内积。

定理3.1(Mercer条件)对于任意的对称函数kx,x，它是某个特征空间中的内积运算的充分必要条件是，对于任意的x0且2xdx有

kx,xxxdxdx0 3-(22)

这样，在高维空间中求解最优分类面时，可以通过采用适当的核函数

kxi,xj将高维空将的内积运算转化为低维空间的函数运算，就可以在不影响计算复杂度的情况下实现非线性分类问题。表达式3-(20)也相应的转化为：

1nQaiijyiyjkxi,xj 3-(23)

2i,j1i1n相应的最优分类面的决策函数也转化为：

fxsgn,xbsgniyikxi,xb 3-(24)

xisv我们称3-(21)的kxi,xj为核函数，核函数的引入，很好的解决了高维问题，将高维空间的内积运算转化为低维空间的函数运算，常用的核函数有多项式核函数、径向基核函数和Sigmoid核函数等。

(1)多项式核函数 kx,xjx,xj1 3-(25)

qxxj(2)径向基核函数 kx,xjexp22 3-(26) (3)Sigmoid核函数 kx,xjtanhvx,xjc 3-(27)

19

4.支持向量机的主要研究热点

支持向量机是从统计学发展而来的一种新型的机器学习方法，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势，但是，支持向量机方法中也存在着一些亟待解决的问题，主要包括：如何用支持向量机更有效的解决多类分类问题，如何解决支持向量机二次规划过程中存在的瓶颈问题、如何确定核函数以及最优的核参数以保证算法的有效性等。

4.1支持向量机多类分类方法

支持向量机最初是为两类分类而设计的，不能直接用于解决多分类问题，而在实际应用中遇到的多为多分类问题。为了扩展SVM的应用范围以适应实际需求，支持向量机的多类分类方法的研究也就成为支持向量机研究的一个热点[14]。常用的方法有“one--against--one”方法、“one--against--rest”方法、有向无环图SVMS、基于决策树的方法等。目前一些SVM的多类分类算法已经得到推广应用，如文本(超文本)分类、图像分类、生物序列分析和手写字符识别等[15]。 1.“one--against--rest”方法

“one--against--rest”方法是支持向量机多类分类方法最早使用的算法。用支持向量机解决多类分类问题[16]，通常的方法是构造一系列两类分类器，将这些子分类器按照不同的方式组合就可以解决多类分类问题。“one—against--rest”方法是对于k类问题构造k个支持向量机子分类器，每个子类都与其余类构造一个子分类器，在构造第i个支持向量机子分类器时，将属于第i类的样本数据标记为正类，不属于i类别的样本数据标记为负类。解决下面的最优化问题：

1mini2iT2lCij 4-(1)

j1xbji1ij, if yji,

1ij, if yji, 4-(2)

s..t iTxbjiij0,j1,...,l

求解4-(1)最优化问题后，就可以得到k个决策函数：

1xb1,...,kxbk 4-(3)

TT测试时，对测试数据分别计算各个子分类器的决策函数值，并选取函数值最大的所对应的类别为测试数据的类别。对于待测样本x，将其输入这k个决策函数中，得到k个值，取得最大值的函数对应的类别即为该样本所属类别，那么用

Cx表示样本x所属的类别：

20

Cxargmaxi1,...,kiTxb 4-(4)

i“one--against--rest”方法的一个明显优点是，只需要训练k个两类分类支持向量机，故其所得到的分类函数的个数k较小，分类速度也相对较快。该方法的缺点是，每个分类器的训练都要将全部的样本作为训练样本，使训练速度随着训练样本数量的增加急剧减慢，训练时间较长。 2.“one--against--one”方法

“one--against--one”方法[16]也是要构造一系列两类分类器，与“one--against--rest”方法不同的是，“one--against--one”方法是对于任意的两个类都构造一个两类分类器，这样k类样本生kk12个SVM子分类器。在构造类别i和类别j的SVM子分类器时，在样本数据集中仅选取属于类别i和类别j，的样本数据作为训练样本数据，并将属于类别i的数据标记为正，将属于类别j的数据标记为负。“one--against—one”方法需要解决如下的最优化问题：

1minij2ijT2Cnij 4-(5)

nxbnTijij1n, if yni,

s..t ijxnbij1nij if ynj, 4-(6)

nij0

其中，nij0对于类别i和类别j的n个样本成立，由于fijxfjix，因此存在kk12个不同的SVM子分类器，这种方法符合SVM的特点，可以直接计算两类之间的分类平面。

“one--against--one\"方法中，用于测试的常用方法是“投票机制\"，即多数获胜，每个分类器为它的首选类投出一票，最终结果就是拥有票数最多的类别，也就是样本x属于类i，当且仅当

Cxargmaxikj1,jisignfijx 4-(7)

其中Cx表示样本x属于类i时拥有的票数，signfij是符号函数，即当fij值为正数时，函数值为1，否则为0。当多于一个类别具有相同数目的最多票数时，也就是产生不可分区域，那么不可分区域中的样本点就根据决策函数实际值的大小分到与之距离最近的类中：

Vxargmaxikj1,jifijx 4-(8)

21

其中，Vx表示样本x属于类i时决策函数的实际输出值。

“one--against--one”方法的缺点是当类别k过大时，相对于“one--against--rest”方法，子分类器数目明显增加，训练时间更长；在测试时要对任意两类进行比较，训练速度会随着类别的增加成指数倍降低。 3．有向无环图SVMS

有向无环SVMS[17]是针对“one--against--one”方法存在错分、拒分现象提出的。在训练阶段，该方法与“one--against--one”相同，对于k类样本，同样也需要构造kk12个子分类器，但在测试过程中，该方法将所有子分类器构造成一个有向无环图，包括kk12个内部节点和k个叶子节点，每个内部节点是一个子分类器。当对未知样本测试时，从根节点开始分类，只需k1步即可完成分类，与“one--against--one”方法相比，训练阶段两者是相同的，在测试过程中减少了重复操作，大大提高了分类速度。但是，对于类别较多的训练样本，有向无环SVMS需要训练大量的子分类器，同时，每个子分类器的构造都需要两个类别的所有样本都参加训练，时间复杂度高。 4. 二叉树SVM

二叉树分类法首先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环下去，直到所有的类别都被正确划分出来为止，这样就得到一个倒立的二叉分类树。该方法将原有的多类问题同样分解成了一系列的两类分类问题，其中两个子类间的分类函数采用支持向量机。对于两个子类的分割一般采用聚类分析等方法；二叉树有：“正态树”(图4-1)和“偏态树”(图4-2)两种[18]。

影响二叉树分类方法分类效率和推广能力的因素很多，不同的二叉树构造方法、不同的分割顺序都将影响到分类器的分类性能。越是在上层节点的子分类器，其分类性能对于整个分类模型的推广性影响越大，因此，在生成二叉树是应该让最容易分割出来的类最早分割出来，即在决策树的上层节点处分割(一般根据初始样本的集合分布确定分割顺)，同时，样本在输入空间的物理联系在特征空间中也同样存在，因而只需在输入空间中考虑样本的几何分布。

“正态树”首先将所有类别的样本分为两个次级子类，然后再对每个次级子类做同样的工作，直到所有的节点都只包含一个类别为止；“偏态树”每次将一个类别与其他所有类别分开，直到所有的类别都被正确的分开为止。有些算法对二叉树方法做了改进，如在训练阶段采用聚类方法、用奇偶分组方法、折半方法等对样本进行初始化分。

22

图4.1 正态树

图4.2 偏态树

以上简要介绍了几种常用的支持向量机多类分类方法，其中比较常用的是“one--against--one”方法，但是各种方法都存在着其优势和不足，因而，支持向量机的多类分类方法仍在不断的研究探讨之中。

4.2求解支持向量机的二次规划问题

支持向量机把分类问题归结为一个带有线性约束的凸二次规划问题，因此，求解SVM的问题就等价于求解一个凸二次规划问题。针对大规模样本集的训练问题，其二次规划问题求解的时间复杂度和空间复杂度也很高，这就使得计算时间和存储空间成了求解支持向量机的瓶颈，如何有效的求解一个大的二次规划问题也就成了支持向量机领域的一个研究热点。

针对如有效的求解支持向量机问题，目前主要有以下四种解决方法：选块算法，分解算法，SMO算法以及增式算法[19] [20] [21]。 1. 选块算法

选块算法又名“chunking”算法，是由Boser等人首先提出来的，是最简单

23

的一种启发式算法。通常称训练集T中的任意一个子集为“块”，有时也称“块”为工作集。选块算法的基本思想是，去掉Lagrange乘子i0的训练样本，而对支持向量计算相应的Lagrange乘子i，选块算法需要通过某种迭代算法逐步排除非支持向量，选出支持向量对应的“块”。每次求解一个子二次规划问题，得到若干支持向量，用这些支持向量和一些不满足优化条件的样本，构成新的子二次规划问题，而初始子问题由任意若干个样本构成，重复上述过程，直到所有样本满足优化条件。实际求解的二次规划问题中的赫赛矩阵的规模由ll下降为

NsvNsv (Nsv为支持向量的数目)。这种方法在训练集的支持向量数目较少的时

候比较有效，能够大大提高运算速度，但是，如果支持向量个数本身就比较多，随着算法迭代次数的增多，所选的块也会越来越大，计算复杂度增加，不能体现出选块算法的优越性。 2. 分解算法

Osuna等人首次提出了分解算法的基本框架，将大规模的二次规划问题转化成一系列小规模的二次规划问题。将样本集A分成两个集合，工作集B和非工作集N，其大小B和N都是固定的，他们对应的下标集合分别标记为B和N，则有：

B,yyB,HHBByNNHNBHBN 4-(9) HNN算法迭代过程中，首先要确定B，然后求解关于B的二次规划问题，而保持N中样本系数不变，即，迭代过程中要调整的是B，而N是固定不变的。分解法的关键问题是每次迭代过程中，如何选择工作集B以及算法的收敛性。Osuna等人根据KKT条件选择工作集，而Joachims、Laskov、Hsu等人采用可行方向法选择工作集，这些分解方法的收敛性已得到了证明。和块算法不同的是分解算法每次只更新若干个Lagrange乘子，而其他乘子保持不变，每一次新的训练样本加入到工作集中，就必须舍去另外一个训练样本。迭代过程只是将工作集之外的训练样本一部分“情况最糟的样本”和工组集中一部分样本进行等量交换，这样，即使支持向量个数超过工作集的大小，也不会改变工作集的规模。 3. 序列最小优化算法(Sequential Minimal Optimization，SMO)

Platt提出的顺序优化算法(SMO)是将工作集B样本数目q限定为2，即

B2，这样在每次迭代过程中只调整对应于两个训练样本xi,yi和xj,yj的

i和j，它只求解一个具有变量的最优化问题。进行小规模二次规划求解时，可用解析法直接计算，而不需要采用数值优化算法。Keerthi等人证明了SMO算法的收敛性，并对SMO分解算法提出了重大的改进，即在判别最优条件时用两个阈值代替一个阈值，从而使算法更加合理，速度更快。

24

4. 增式算法

增式算法可以看作是由分解算法发展而来的，增式算法先将整个训练样本按照一定的规则划分，选择其中的一部分先行训练，得到一部分符合优化条件的样本，再与新增加的一部分样本一同作为新的训练样本集合，如此反复，直到所有的训练样本子集都参加训练，所得到的支持向量机也就是最有效的。传统的增式算法只保留每次训练得到的支持向量，然后，将保留下来的样本同新增的样本一同做为下次训练的样本集，如此反复，直到所有的样本子集都参加训练为止，最终得到的分类器即为所求。同时，前面所讨论的支持向量机，都需要采用二次规划或线性方程组求解最优化的问题，而Roobaert提出的直接支持向量机(Direct--SVM)，采用了启发式搜索方法在所有训练样本集中直接搜索支持向量，从而避免了采用二次规划进行最优求解，使用的启发性规则主要包括：①距离最近的2个不同类别的数据点有可能是支持向量；②最大偏离最优超平面的数据点，也就是误分类最严重的数据点有可能是支持向量。根据这两条启发式规则搜索支持向量及最优超平面，该方法具有直观、求解速度快等优点。

以上总结了几种常用的求解二次规划问题的方法，SMO算法是分解算法的特例，最为关键的是工作集的选择策略和优化停止准则。二次规划问题的有效解决直接关系到支持向量机分类效率的优化问题，也是近年来支持向量机领域研究的一个热点。

4.3核函数选择及其参数优化

对于支持向量机的设计，核函数非常重要，因为特征空间的结构由核函数决定，它设计的好坏直接影响到分类效果。尽管只要满足定理3.1 Merce条件的函数在理论上都可选为核函数，但不同的核函数，其分类器的性能完全不同。因此，针对某一特定问题，选择什么样的核函数是至关重要的。同时，支持向量机方法中二次规划参数如C参数、M参数(M--SVM)、r参数(LS--SVM)对分类器的推广能力也有影响[22]。核函数类别的选择、核函数参数的选择及二次规划参数的选择统称为模型选择。尽管模型选择方面的研究成果不多，但作为支持向量机方法中的重要研究内容之一已日益受到研究者的重视。

构造一个支持向量机，首先要选择用于训练和测试的样本集合、核函数以及相应的核参数，如果是多类分类还要选择相应的多类分类方法，其中，参数的选择也是十分重要的，参数选择的好坏直接影响到分类器的分类效率。比较常用的核函数是RBF核函数，选择RBF核函数的原因主要有：(1)RBF核把样本非线性映射到更高维的空间上，因而可以处理类标签和属性之间的非线性关系；(2)超参数的个数影响模型选择的复杂性，多项式核的超参数比核的要多，选择起来比较复杂；(3)RBF核的计算难度比较小。如果多项式的次数比较高的话，在运算

25

时可能会出现溢出的现象。

选择了核函数，下一步就要确定相应的参数，以RBF核函数为例，我们要确定的参数有两个：惩罚因子C和核参数。确定参数的方法主要有两种：双线性搜索法和网格搜索法[23]。

1.双线性搜索法：双线性搜索将参数空间分为欠训练区、过训练区和好区，我们以log、logC为坐标轴，通过大量的实验证明，学习精度最高，也就是分类效果最好的参数组合C,将集中出现在“好区”中的直线loglogClogC附近，其中C为使线性SVM学习精度最高的惩罚因子。

进行线性搜索的步骤是：首先，训练线性SVM确定最佳参数C，使以之为参数的线性SVM的学习精度最高，记作C；然后对RBF核的SVM，固定C，对于满足loglogClogC的C,训练SVM，对其精度进行估算，精度最高的一组参数组合即为最优参数。

2. 网格搜索法：基于网格搜索的参数确定方法涉及到支持向量机的训练、预测和预测准确率的比较。基于网格搜索的参数确定方法实现如下：首先将C、

分别取M和N个值，再对C、的范围做一界定，如210~215，搜索步长

为-1，C210~215，搜索步长为l；这样在C、坐标系上构成一个二维网格，对于网格上每一个C,的组合，分别训练不同的SVM，再计算其准确率，把每个C,对应的准确率用等高线绘出，据此得到最优的C,组合。

以上的两种参数选择方法是最基本的两种参数选择方法，有些算法对其进行了改进，也有的方法将两种方法进行结合，提出了双线性网格搜索方法等。

支持向量机方法主要优点包括：第一，支持向量机是专门针对小样本情况的，其求解目标是得到现有有限样本的最优解而不仅仅是样本趋向于无穷大时的最优解；第二，支持向量机算法实质是一个凸二次规划问题，从理论上说，凸二次规划得到的是全局最优解，解决了在神经网络方法中无法避免的局部最优解问题；第三，支持向量机通过核函数将输入空间的样本通过非线性映射转换到高维的Hilbert特征空间中，通过在高维空间中构造线性判别函数来实现输入空间的非线性分类问题，它巧妙地解决了维数灾难的问题；支持向量机的特有优势使得支持向量机解决了以往的机器学习方法存在的一些问题，如模型选择问题、过学习问题、非线性问题和维数灾难问题等。

26

5.支持向量机的算法仿真

支持向量机是以结构风险最小化理论和VC维理论为理论基础，以求解二次规划问题为主要手段，以在高维空间中求解最优分类超平面为主要目标，以求解支持向量为结果的一种新的机器学习方法。目前，支持向量机在模式识别、图形分割等领域已经进入了实用阶段。一些学者认为，统计学习理论和支持向量机理论正在成为继神经网络研究之后新的研究热点，并将推动机器学习理论和技术的进一步发展。

人脸识别是生物特征识别的一个重要方面，在安全验证系统、医学、档案管理系统、人机交互系统、视频会议以及图像检索等领域具有很大的应用前景，比起指纹识别、视网膜识别、虹膜识别等技术来说，人脸识别相对更加直接，友好，使用者更容易接受[24]。事实上，不管是对人也好，还是对于计算机也好，要实现对人的检测识别，最优先考虑、最直接、也最有意义的特征就是人脸了，而且如果做更深入的分析，还可以从人脸获取更多的信息，如表情，姿态，年龄等。本章将支持向量机多类分类算法应用于人脸识别中，并通过仿真实验证明算法的有效性。

5.1人脸识别的理论基础

一个基本的人脸检测识别系统应该包括以下几个方面：人脸检测，人脸表示和人脸鉴别，其中后两步也就是通常所说的人脸识别。人脸识别的主要步骤大致分为图像获取、特征提取和人脸识别几个部分，具体流程如图5.1所示：

图像获取 特征提取 预处理 人脸检测 人脸识别 分类器设计

图5.1 人脸识别系统示意图

图像获取是人脸识别的第一步，它是指从不同条件下获取的图像中，根据一定的规则和先验知识，利用选择的特征进行检测。先确定有无人脸，若检测到有人脸存在，则对人脸进行定位并获取其尺度姿态等信息，将图像分割成人脸区域和非人脸区域，这一步预处理的工作直接影响着后面的特征提取和识别工作，所以是极其重要的。

特征提取是指采取某种表示方式表征检测出的人脸和数据库中的人脸，也可以把它看作一个人脸表示的过程。这些特征可以是较直观的人脸器官的几何特

27

征，如眼，耳，口，鼻的位置，形状，距离等，也可以是比较抽象的代数特征，如K-L变换所得的主成分特征，奇异值分解得到的奇异值特征等，还可以是模板特征，颜色特征，纹理特征等[25]。

人脸识别这一步的主要工作是把待识别人脸数据和数据库中的已知人脸数据进行匹配，以得到相关信息，实际上可以把人脸识别看作是一个分类过程，关键在于选择适当的分类器和分类策略，对表示人脸的特征进行分类。根据对人脸的不同的特征表示，分类器选择也不同，可以是传统的最小距离法、最近邻法等，也可以是较新的神经网络、支持向量机等，而且利用多特征和多分类器组合来改善识别效果也是近年来的一个研究方向。

近些年来，人脸识别研究和应用已相对比较成熟，提出了不少新的算法，目前主要有基于几何特征的方法、基于代数特征的方法、基于弹性模型的方法、基于神经网络方法和基于支持向量机的方法等，通常的实验结果表明支持向量机有较好的识别效率。

5.2基于PCA方法和SVM原理的人脸识别仿真

基于PCA（Principal Components Analysis，主成分分析方法）和SVM方法的人脸识别算法首先将实验图像进行预处理[26]，然后用PCA方法进行特征提取，最后，将得到的图像特征作为支持向量机的输入训练并测试分类器。选用第四章中介绍的决策树方法来构造分类器，对输入的图像进行训练和识别，具体实现步骤如下：

(1)图像获取。选取数据库中的200幅图像(前一百幅为人脸图像，后一百幅为非人脸图像)作为实验样本；

(2)预处理。由于本实验中选取的图像为小图像，故无需进行预处理； (3)特征提取，计算预处理之后每幅图像的PCA特征。首先计算每幅人脸图像的协方差矩阵，然后计算每个协方差矩阵的特征值和特征向量，将特征向量矩阵的列向量按特征值降序排列，选取最大特征值对应的特征向量作为投影轴，求图像在该轴上的投影，作为训练和测试的样本输入值；

(4)训练分类器。将计算得到的图像特征作为支持向量机的输入，结合第四章提出的SVM两类分类算法训练初始支持向量机SVM；

(5)测试训练得到的支持向量机，通过这种传统的支持向量机两类分类算法，得到的实验结果表明，本算法具有一定的有效性。

仿真实验的主要程序及结果如下： （1）PCA方法对图像进行特征提取的程序为： function w=pca (data,subDim) imSpace=data; 28

psi = mean(double(imSpace'))'; sizedata=size(data); zeroMeanSpace = zeros(sizedata); for i = 1 : sizedata(2) zeroMeanSpace(:, i) = double(imSpace(:, i)) - psi; end L = zeroMeanSpace' * zeroMeanSpace; [eigVecs, eigVals] = eig(L); diagonal = diag(eigVals); [diagonal, index] = sort(diagonal); index = flipud(index); pcaEigVals = zeros(size(eigVals)); for i = 1 : size(eigVals, 1) pcaEigVals(i, i) = eigVals(index(i), index(i)); pcaEigVecs(:, i) = eigVecs(:, index(i)); end pcaEigVals = diag(pcaEigVals); pcaEigVals = pcaEigVals / (sizedata(2)-1); pcaEigVals = pcaEigVals(1 : subDim); pcaEigVecs = zeroMeanSpace * pcaEigVecs; for i = 1 : sizedata(2) pcaEigVecs(:, i) = pcaEigVecs(:, i) / norm(pcaEigVecs(:, i)); end w = pcaEigVecs(:, 1:subDim); （2）训练并测试SVM线性分类器的程序为： clear all; numtouyingfangxiang=50; for j=1:1000 im=imread(['D:\\svm_Alg\\pcasvm\\pcasvm\rain1\\g (' int2str(j-1) ').jpg']); sizeim=size(im); im=im'; for m=1:sizeim(1)*sizeim(2) b(m,j)=double(im(m)); end 29

im=im'; if(j<=500) lab(j,1)=1; else lab(j,1)=-1; end end w=pca(b,numtouyingfangxiang); %PCA特征提取 a=w'*b; sPARAMS.KERNEL=0; %选用LinearSVC核函数 sPARAMS.C=1; sPARAMS.GAMMA=1; Model = CLSosusvm(a,lab,sPARAMS); for j=2900:3100 im=imread(['D:\\svm_Alg\\database\\database\\g (' int2str(j-1) ').jpg']); sizeim=size(im); im=im'; for m=1:sizeim(1)*sizeim(2) c(m,1)=double(im(m)); end im=im'; d=w'*c; [ry,rw] = CLSosusvmC(d,Model); j jilv(j,1)=ry; %分类结果 end qian1001=length(find(jilv(2900:3000)==1)); %前一百个数据中为1的个数 hou1001=length(find(jilv(3001:3100)==1)); %后一百个数据中为1的个数 errorrate=(100-qian1001+hou1001)/200; disp('分类错误率为：') fprintf('%f\\n',errorrate) （3）核函数列表程序为： function Model = CLSosusvm(Xtrain,Ytrain,sPARAMS); Ytrain = Ytrain'; 30

if nargin<3 SETPARAMS = 1; elseif isempty(sPARAMS) SETPARAMS = 1; else SETPARAMS = 0; end if SETPARAMS sPARAMS.KERNEL = 0; sPARAMS.C = 1; end switch sPARAMS.KERNEL, case 0, [AlphaY, SVs, Bias, Parameters, nSV, nLabel] = ... LinearSVC(Xtrain, Ytrain, sPARAMS.C); case 1, [AlphaY, SVs, Bias, Parameters, nSV, nLabel] = ... PolySVC(Xtrain, Ytrain, sPARAMS.DEGREE, sPARAMS.C, 1,0); case 2, [AlphaY, SVs, Bias, Parameters, nSV, nLabel] = ... PolySVC(Xtrain,Ytrain,sPARAMS.DEGREE,sPARAMS.C,1,sPARAMS.COEF); case 3, [AlphaY, SVs, Bias, Parameters, nSV, nLabel] = ... end Model.AlphaY = AlphaY; Model.SVs = SVs; Model.Bias = Bias; Model.Parameters = Parameters; Model.nSV = nSV; Model.nLabel = nLabel; Model.sPARAMS = sPARAMS;

31

RbfSVC(Xtrain, Ytrain, sPARAMS.GAMMA, sPARAMS.C);

（4）SVM线性分类器的仿真结果如图5.2所示：

图5.2 基于SVM分类结果

（5）以下为使用SVM线性分类器的分类错误率: >> qian1001=length(find(jilv(2900:3000)==1)); hou1001=length(find(jilv(3001:3100)==1)); errorrate=(100-qian1001+hou1001)/200; disp('分类错误率为：') fprintf('%f\\n',errorrate) 分类错误率为： 0.110000 32

6.参考文献

[1]邓乃扬，田英杰．数据挖掘中的新方法一一支持向量机[M]．科学出版社，2004 [2]张翔．支持向量机及其在医学图象分割中的应用ED]．华中科技大学，2004 [3] Vapnik V．The Nature of Statistical Learning Theory(2nd edition．)[J]．New York， Springer，2000

[4]昕炜．支持向量机算法的研究及应用[D]．浙江大学，2003

[5] Pabitra Mitra，B．Uma Shankar，Sankar K．Pal． Segmentation of multispectral remote sensing images using active support vector machines[J]．Pattern Recognition Letters．2004，25(9)：1067—1074

[6] Xue-Cheng Xi，Aun—Neow Poo and Si都r—Kiang Chou．Support vector regression model predictive control on a HVAC plant[J]．Control Engineering Practice，2007，8(15)：7-908

[7] Qi Miao．Shi—Fu Wang．Nonl inear Model Predictive Control Based on Support Vector Regression[J]．Proceedings of International Conference on Machine Learning and Cybernetics，2002，(3)：1657—1661

[8] B.J.de Krnif，T.J.A.deVries．On Using a Support Vector Machine in Learning Feed—Forward Contr01.In Proceediings of Int. Conf.on Advanced Intelligent Mechatronics[J]，Como，Italy，July 2001：272-277

[9] J.A.K.Suykens．Nonlinear Modeling and Support Vector Machines[J]．Proceedings of the 18th IEEE Instrumentation and Measurement Technology Conference, 2001,(1):287—294

[10]王莉，林锦国．支持向量机的发展与应用[J]．石油化工自动化，2006，(3)：34-38

[11]V.N Vacpnik. Principles of risk minimization for learning theory[J].Neural Information Processing Systems，V01．4，morgan Kanfmann，San MateolCA，1992，(4):831—838

[12]C.Cortes,V.Vapnik. The Soft Margin C1assifier[J]. Technical memorandu 11359-931 209—18TM，AT&T Bell Labs，1993

[13] V.Vapnik，S.Golowich，A.Smola.Support Vector Method for Function Approximation，Regression Estimation，and Signal Processing[J]. Advances inNeural Information ProcessingSystems 9，Cambridge，MIT Press，1997：281—287

[14]郑勇涛,刘玉树.支持向量机解决多分类问题研究[J]. 计算机工程与应用，2005，41(23)：187-190

33

[15] Yiguang Liu，Zhisheng YoU，Liping Cao．A novel and quick SYM-based multi—class classifier[J]．Pattern Recognition. 2006,39(11)：2258—22

[16] Pawan Lingras。Cory Butz．Rough set based 1--v--1 approaches to support vector machine multi—classification[J]．information sciences．2007，177(8)：3782—3798 [17]唐发明，王仲东，陈绵云．支持向量机多类分类算法研究[J]．控制与决策，2005，20(7)：746—749

[18]黄勇，郑春颖，宋忠虎．多类支持向量机算法综述[J]．计算机技术与自动化2005，24(4)：61-

[19] Qing 1 i，Licheng jiao，Yingjuan Hao．Adaptive simplification of soluting for support vector machine[J]．Pattern Recognition．2007，40(3)：972—980

[20] Hong Qiao，Yan-Guo Wang，Bo Zhang．A simple decomposition algorithm for Support

vector

machines

with

polynomialtime

convergence[J]

Pattern

Recognition 2007，40(9)：2534—29．

[21] E1 isa Ricci，Luca Rugini，Renzo Perfetti．SVM-based CDMA receiver with incremental active learning．Neurocomputing，2006，69(13—15)：1691—1696 [22] Mathias M．Adankon，Mohamed Cheriet．Optimizing resources in model selection for support vector machine[J]．Pattern Recognition，2007，40(3)：953—963

[23] Carl Golda，Alex Holuba，Peter Sollich．Bayesian approach to feature selection and parameter tuning for support vector machine classifiers[J]. Neural Networks．2005．18(5-6)：693-701

[24] Francesco Camastra.A SvM—based cursive character recognizer[J]，Pattern Recognition. 2007,40(12)：3721—3727

[25] Cheng-Lung Huang，Hung—Chang Liao，Mu—Chen Chen．Prediction model bui lding and feature selection with support vector machines in breast cancer diagnosis[J]. Expert Systems Appl ication,2008,34(1)：578—587

[26] Guo G．，Li S．Z．，Chan K．L．Support vector machines for face recognition[J]． International Journal of Computer Vision, 2001,19(25)：631—638

34