1、I综述机器学习与支持向量机摘要机器学习是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能，它是人工智能的核心，是使计算机具有智能的根本途径。基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测，包括模式识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。支持向量机是从统计学发展而来的一种新型的机器学习方法，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势，但是，支持向量机方法中也存在着一些亟待解决的问题，主要包括：如何用支持向量机更有效
2、的解决多类分类问题，如何解决支持向量机二次规划过程中存在的瓶颈问题、如何确定核函数以及最优的核参数以保证算法的有效性等。本文详细介绍机器学习的基本结构、发展过程及各种分类，系统的阐述了统计学习理论、支持向量机理论以及支持向量机的主要研究热点，包括求解支持向量机问题、多类分类问题、参数优化问题、核函数的选择问题等，并在此基础上介绍支持向量机在人脸识别中的应用，并通过仿真实验证明了算法的有效性。关键词：机器学习；统计学习理论；SVM； VC维；人脸识别IIThe Summarization of Machine Learning and Support Vector MachineABSTRACT
3、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 int
4、elligence.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
5、 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, nonlineari
6、ty 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 paramete
7、rs 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-cla
8、ssification, 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目 录摘要 .
9、IABSTRACT .II1.绪论 .11.1 研究背景及意义 .11.1.1 机器学习概念的出现 .11.1.2 支持向量机的研究背景 .11.2 本文主要内容 .32.机器学习的结构及分类 .42.1 机器学习定义及发展 .42.2 机器学习系统的基本结构 .52.3 机器学习的分类 .62.4 目前研究领域 .93.支持向量机的原理 .103.1 统计学习理论 .103.1.1 机器学习问题 .103.1.2 统计学理论的发展与支持向量机 .113.1.3VC维理论 .123.1.4 推广性的界 .123.1.5 结构风险最小化原则 .133.2 支持向量机理论 .143.2.1 最优分
10、类面 .163.2.2 标准支持向量机 .184.支持向量机的主要研究热点 .204.1 支持向量机多类分类方法 .204.2 求解支持向量机的二次规划问题 .234.3 核函数选择及其参数优化 .255.支持向量机的算法仿真 .275.1 人脸识别的理论基础 .275.2 基于 PCA 方法和 SVM 原理的人脸识别仿真 .286.参考文献 .3311.绪论1.1 研究背景及意义1.1.1 机器学习概念的出现学习是人类具有的一种重要智能行为，但究竟什么是学习，长期以来却众说纷纭。社会学家、逻辑学家和心理学家都各有其不同的看法。按照人工智能大师西蒙的观点，学习就是系统在不断重复的工作中对本身能
11、力的增强或者改进，使得系统在下一次执行同样任务或相同类似的任务时，会比现在做得更好或效率更高。西蒙对学习给出的定义本身，就说明了学习的重要作用。在人类社会中，不管一个人有多深的学问，多大的本领，如果他不善于学习，我们都不必过于看重他。因为他的能力总是停留在一个固定的水平上，不会创造出新奇的东西。但一个人若具有很强的学习能力，则不可等闲视之了。机器具备了学习能力，其情形完全与人类似。什么是机器学习？迄今尚没有统一的定义，由其名字可理解为机器学习是研究如何使用机器来模拟人类学习活动的一门学科。稍微严格的提法是机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。这里所说的“机器” ，指的
12、就是计算机，现在是电子计算机，以后还可能是种子计算机、光子计算机或神经计算机等等。机器能否像人类一样能具有学习能力呢？1959 年美国的塞缪尔(Samuel)设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对弈中改善自己的棋艺。4 年后，这个程序战胜了设计者本人。又过了 3 年，这个程序战胜了美国一个保持 8 年之久的常胜不败的冠军。这个程序向人们展示了机器学习的能力，提出了许多令人深思的社会问题与哲学问题。机器的能力是否能超过人的，很多持否定意见的人的一个主要论据是：机器是人造的，其性能和动作完全是由设计者规定的，因此无论如何其能力也不会超过设计者本人。这种意见对不具备学习能力的机器
13、来说的确是对的，可是对具备学习能力的机器就值得考虑了，因为这种机器的能力在应用中不断地提高，过一段时间之后，设计者本人也不知它的能力到了何种水平。1.1.2 支持向量机的研究背景支持向量机(Support Vector Machine，SVM) 方法是在统计学习理论(Statistical Learning Theory,SLT)基础上发展而来的一种机器学习方法， SVM 在使用结构风险最小化原则替代经验风险最小化原则的基础上，又结合了统计学习、机器学习和神经网络等方面的技术，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势。它一方面可以克服神经网络等方法所固2有的过学习和欠学
14、习问题，另一方面又有很强的非线性分类能力，通过引入核函数，将输入空间的样本映射到高维特征空间，输入空间的线性不可分问题就转化为特征空间的线性可分问题。支持向量机被看作是对传统分类器的一个好的发展，并被证明可在保证最小化结构风险的同时，有效地提高算法的推广能力。随着计算机技术的蓬勃发展以及人们在各个领域对模式识别技术的需求与应用，计算机模式识别技术也有了很大的发展。模式识别就是设计一个能够对未知数据进行自动分类的方法，常用模式识别方法有统计识别方法、句法结构识别方法、模糊理论识别方法、神经网络识别方法、模板匹配识别方法和支持向量机的识别方法等。其中，基于支持向量机的模式识别方法是目前最为有效的模
15、式识别方法之一。VVapnik 等人早在 20 世纪 60 年代就开始研究小样本情况下的机器学习问题，当时这方面的研究尚不十分完善，且数学上比较艰涩，大多数人难以理解和接受，直到 90 年代以前还没能够提出将其理论付诸实现的方法，加之当时正处在其他学习方法飞速发展的时期，因此这方面的研究一直没有得到足够的重视。直到 90 年代中期，小样本情况下的机器学习理论研究逐渐成熟起来，形成了较完善的理论体系统计学习理论(Statistical Learning Theory,SLT)2，而同时，神经网络等新兴的机器学习方法的研究则遇到了许多困难，在这种情况下，试图从更本质上研究机器学习问题的统计学习理论
16、逐步得到重视。统计学习理论是建立在坚实的理论基础之上的，为解决小样本学习问题提供了统一的框架。统计学习理论的核心是 VC 维理论与结构风险最小化理论，它用 VC 维来描述学习机器的复杂度，并以此为出发点导出了学习机器推广能力的界的理论。该理论致力于寻找在小样本情况下学习问题的最优解，而不需要利用样本数趋于无穷大的渐进性条件，这使得统计学习理论在小样本情况下同样能得到具有推广价值的知识。1992 年至 1995 年，在统计学习理论的基础上发展出了一种新型的学习机器支持向量机(Support Vector Machine 简称 SVM)。支持向量机是建立在统计学习理论的 VC 维理论和结构风险最小
17、原理基础上的，根据有限的样本信息在模犁的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力。支持向量机被看作是对传统分类器的一个好的发展，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势。SVM 方法是由 Vapnik 及其合作者 Boser、Guyon、Cortes 及 Scholkopf 在AT&T Bell 实验室共同创造与发展起来的一种新方法 3。近年来，许多关于SVM 方法的研究，包括算法本身的改进和算法的实际应用，都陆续被提了出来，如 Scholkoph 等人提出了 v.SVM 方法、Suykens 等人提出了最小二乘支持向量3机(LSSVM)、Zhang 提
18、出的类中心支持向量机(CSVM)方法、Lin 等提出了模糊支持向量机方法(Fuzzy SVM)等4。其中，在理论上主要以 Vapnik 及其研究小组做了大量开创性及奠基性的工作。随着支持向量机的不断发展，人们对支持向量机的研究也越来越细化，其主要研究方向大致可分为：求解支持向量机问题，支持向量机多类分类问题，参数的选择和优化问题等。求解一个 SVM 问题最终都转化为解一个具有线性约束的凸规划问题或其对偶问题的二次规划问题(Quadratic Programming，QP)。传统的方法是利用标准二次型优化技术解决对偶问题，这就导致算法的训练速度很慢，一方面是由于 SVM 需要计算和存储核函数矩阵
19、，当样本规模较大时必然导致内存需求增加；另一方面，SVM 在二次寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法占用了大部分的算法时间，这就使得存储空间和和计算时间成了求解二次规划问题的瓶颈。常用的解决方法是将一个大的二次规划问题转化为若干个小的二次规划问题以提高分类效率，如块算法、分解算法、SMO 算法、增式算法等等。支持向量机分类理论是针对两类分类问题提出的，然而，现实世界的分类问题，如船舰识别、字体识别、人脸识别等，都属于多类分类的范畴。如何将二类分类方法扩展到多类分类情况是支持向量机方法研究的重要内容之一。目前，用 SVM 解决多类分类问题方法主要是通过构造或组合多个两类分类器来实
20、现多类问题的分类。子分类器的构造和组合将两类分类扩展到多类问题，将多类分类问题逐步转化为两类分类问题。常用的算法有“one-against-one ”方法、 “one-against-rest”方法、 “基于决策树的方法 ”等。支持向量机多类分类方法的引入拓展了支持向量机的应用范围，也加快了支持向量机方法的改进和创新，同时，支持向量机的核函数的选择以及核参数的选择也是一个重要的研究方向。1.2 本文主要内容本文旨在综述机器学习及支持向量机的基本原理及研究方向。第一章为绪论，介绍了机器学习概念的出现与支持向量机的背景知识；第二章介绍了机器学习的发展过程、基本结构、分类及应用领域；第三章详细介绍了
21、支持向量机的原理，包括统计学习理论和支持向量机理论；第四章介绍了支持向量机的主要研究热点，包括求解支持向量机问题、多类分类问题、参数优化问题、核函数的选择问题等，并列出支持向量机的主要优点；第五章给出支持向量机算法的一个仿真实验。42.机器学习的结构及分类2.1 机器学习定义及发展机器学习(Machine Learning)是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域，它主要使用归纳、综合而不是演绎。学习能力是智能行为的一个非常重要的特征，但至今对学习
22、的机理尚不清楚。人们曾对机器学习给出各种定义。H.A.Simon 认为，学习是系统所作的适应性变化，使得系统在下一次完成同样或类似的任务时更为有效。R.s.Michalski认为，学习是构造或修改对于所经历事物的表示。从事专家系统研制的人们则认为学习是知识的获取。这些观点各有侧重，第一种观点强调学习的外部行为效果，第二种则强调学习的内部过程，而第三种主要是从知识工程的实用性角度出发的。机器学习在人工智能的研究中具有十分重要的地位。一个不具有学习能力的智能系统难以称得上是一个真正的智能系统，但是以往的智能系统都普遍缺少学习的能力。例如，它们遇到错误时不能自我校正；不会通过经验改善自身的性能；不会
23、自动获取和发现所需要的知识。它们的推理仅限于演绎而缺少归纳，因此至多只能够证明已存在事实、定理，而不能发现新的定理、定律和规则等。随着人工智能的深入发展，这些局限性表现得愈加突出。正是在这种情形下，机器学习逐渐成为人工智能研究的核心之一。它的应用已遍及人工智能的各个分支，如专家系统、自动推理、自然语言理解、模式识别、计算机视觉、智能机器人等领域。其中尤其典型的是专家系统中的知识获取瓶颈问题，人们一直在努力试图采用机器学习的方法加以克服。机器学习的研究是根据生理学、认知科学等对人类学习机理的了解，建立人类学习过程的计算模型或认识模型，发展各种学习理论和学习方法，研究通用的学习算法并进行理论上的分
24、析，建立面向任务的具有特定应用的学习系统。这些研究目标相互影响相互促进。自从 1980 年在卡内基-梅隆大学召开第一届机器学术研讨会以来，机器学习的研究工作发展很快，已成为中心课题之一。 机器学习是人工智能研究较为年轻的分支，它的发展过程大体上可分为 4个时期：第一阶段是在 50 年代中叶到 60 年代中叶，属于热烈时期；第二阶段是在 60 年代中叶至 70 年代中叶，被称为机器学习的冷静时期；5第三阶段是从 70 年代中叶至 80 年代中叶，称为复兴时期；机器学习的最新阶段始于 1986 年。机器学习进入新阶段的重要表现在下列诸方面：(1) 机器学习已成为新的边缘学科并在高校形成一门课程。它
25、综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机器学习理论基础。(2) 结合各种学习方法，取长补短的多种形式的集成学习系统研究正在兴起。特别是连接学习符号学习的耦合可以更好地解决连续性信号处理中知识与技能的获取与求精问题而受到重视。(3) 机器学习与人工智能各种基础问题的统一性观点正在形成。例如学习与问题求解结合进行、知识表达便于学习的观点产生了通用智能系统 SOAR 的组块学习。类比学习与问题求解结合的基于案例方法已成为经验学习的重要方向。(4) 各种学习方法的应用范围不断扩大，一部分已形成商品。归纳学习的知识获取工具已在诊断分类型专家系统中广泛使用。连接学习在声图文识别
26、中占优势。分析学习已用于设计综合型专家系统。遗传算法与强化学习在工程控制中有较好的应用前景。与符号系统耦合的神经网络连接学习将在企业的智能管理与智能机器人运动规划中发挥作用。(5) 与机器学习有关的学术活动空前活跃。国际上除每年一次的机器学习研讨会外，还有计算机学习理论会议以及遗传算法会议。2.2 机器学习系统的基本结构机器学习系统的基本结构如图 2.1 所示，环境向系统的学习部分提供某些信息，学习部分利用这些信息修改知识库，以增进系统执行部分完成任务的效能，执行部分根据知识库完成任务，同时把获得的信息反馈给学习部分。在具体的应用中，环境，知识库和执行部分决定了具体的工作内容，学习部分所需要解
27、决的问题完全由上述 3 部分确定。下面我们分别叙述这 3 部分对设计学习系统的影响。环境 学习 知识库 执行图 2.1 学习系统的基本结构影响学习系统设计的最重要的因素是环境向系统提供的信息。或者更具体地说是信息的质量。知识库里存放的是指导执行部分动作的一般原则，但环境6向学习系统提供的信息却是各种各样的。如果信息的质量比较高，与一般原则的差别比较小，则学习部分比较容易处理。如果向学习系统提供的是杂乱无章的指导执行具体动作的具体信息，则学习系统需要在获得足够数据之后，删除不必要的细节，进行总结推广，形成指导动作的一般原则，放入知识库，这样学习部分的任务就比较繁重，设计起来也较为困难。因为学习系
28、统获得的信息往往是不完全的，所以学习系统所进行的推理并不完全是可靠的，它总结出来的规则可能正确，也可能不正确。这要通过执行效果加以检验。正确的规则能使系统的效能提高，应予保留；不正确的规则应予修改或从数据库中删除。知识库是影响学习系统设计的第二个因素。知识的表示有多种形式，比如特征向量、一阶逻辑语句、产生式规则、语义网络和框架等等。这些表示方式各有其特点，在选择表示方式时要兼顾以下 4 个方面：(1)表达能力强。(2) 易于推理。 (3)容易修改知识库。(4) 知识表示易于扩展。对于知识库最后需要说明的一个问题是学习系统不能在全然没有任何知识的情况下凭空获取知识，每一个学习系统都要求具有某些知
29、识理解环境提供的信息，分析比较，做出假设，检验并修改这些假设。因此，更确切地说，学习系统是对现有知识的扩展和改进。执行部分是整个学习系统的核心，因为执行部分的动作就是学习部分力求改进的动作。同执行部分有关的问题有 3 个：复杂性、反馈和透明性。2.3 机器学习的分类1.基于所获取知识的表示形式分类学习系统获取的知识可能有：行为规则、物理对象的描述、问题求解策略、各种分类及其它用于任务实现的知识类型。对于学习中获取的知识，主要有以下一些表示形式：1）代数表达式参数：学习的目标是调节一个固定函数形式的代数表达式参数或系数来达到一个理想的性能。2）决策树：用决策树来划分物体的类属，树中每一内部节点对
30、应一个物体属性，而每一边对应于这些属性的可选值，树的叶节点则对应于物体的每个基本分类。3）形式文法：在识别一个特定语言的学习中，通过对该语言的一系列表达式进行归纳，形成该语言的形式文法。4）产生式规则：产生式规则表示为条件动作对，已被极为广泛地使用。学习系统中的学习行为主要是：生成、泛化、特化或合成产生式规则。75）形式逻辑表达式：形式逻辑表达式的基本成分是命题、谓词、变量、约束变量范围的语句及嵌入的逻辑表达式。6）图和网络：有的系统采用图匹配和图转换方案来有效地比较和索引知识。7）框架和模式（schema ）：每个框架包含一组槽，用于描述事物（概念和个体）的各个方面。8）计算机程序和其它的过
31、程编码：获取这种形式的知识，目的在于取得一种能实现特定过程的能力，而不是为了推断该过程的内部结构。9）神经网络：这主要用在联接学习中，学习所获取的知识，最后归纳为一个神经网络。10）多种表示形式的组合：有时一个学习系统中获取的知识需要综合应用上述几种知识表示形式。根据表示的精细程度，可将知识表示形式分为两大类：泛化程度高的粗粒度符号表示、泛化程度低的精粒度亚符号(sub-symbolic)表示。像决策树、形式文法、产生式规则、形式逻辑表达式、框架和模式等属于符号表示类；而代数表达式参数、图和网络、神经网络等则属亚符号表示类。2.按应用领域分类最主要的应用领域有：专家系统、认知模拟、规划和问题求
32、解、数据挖掘、网络信息服务、图象识别、故障诊断、自然语言理解、机器人和博弈等领域。从机器学习的执行部分所反映的任务类型上看，目前大部分的应用研究领域基本上集中于以下两个范畴：分类和问题求解。（1）分类任务要求系统依据已知的分类知识对输入的未知模式（该模式的描述）作分析，以确定输入模式的类属，相应的学习目标就是学习用于分类的准则（如分类规则）。（2）问题求解任务要求对于给定的目标状态，寻找一个将当前状态转换为目标状态的动作序列；机器学习在这一领域的研究工作大部分集中于通过学习来获取能提高问题求解效率的知识（如搜索控制知识，启发式知识等）。3.综 合 分 类综合考虑各种学习方法出现的历史渊源、知识表示、推理策略、结果评估的相似性、研究人员交流的相对集中性以及应用领域等诸因素，将机器学习方法区分为以下六类：1）经验性归纳学习(empirical inductive learning)经验性归纳学习采用一些数据密集的经验方法（如版本空间法、ID3 法，定律发现方法）对例子进行归纳学习，其例子和学习结果一般都采用属性、谓
