上届论文——基于支撑矢量机的模式识别算法的研究.doc

摘要摘要支撑矢量机(SVM，Support Vector Machine)是基于统计学习理论的一种模式识别方法。使用结构风险最小化原则替代经验风险最小化原则，避免了一些长期困扰其他模式识别方法的问题，使它对于小样本学习有着较好的处理能力。利用核函数，把非线性空间的问题转换到线性空间上来解决，降低了算法的复杂度。由于具有得天独厚的优点（完备的理论基础和较好的学习性能），使它成为当前模式识别领域研究的热点。首先对SVM的理论基础统计学习理论和相关概念进行了介绍。然后对二类SVM实现算法进行深入研究，并对他们的性能进行分析，对其优缺点进行了总结。下来对多类分类及实现算法进行了研究与分析，并对他们的算法特点进行对比。针对大规模训练集，提出了一种增量学习方法。这种算法通过分析SV分布的特点，采用小规模的矩阵运算来代替大规模的矩阵运算。实验结果表明，该算法有效的提高了训练速度。关键词支撑矢量机 统计学习理论 模式识别AbstractSubject : Pattern Recognition Algorithm Based on Support Vector MachineSpecialty : Applied MathematicsName : Instructor : ABSTRACTSupport vector machine is a pattern recognition algorithm based on statistical learning theory. Being substituted structural risk minimization for empirical risk minimization, support vector machine solves some problems puzzling pattern recognition field within a long period. Support vector machine has a good ability processing less simples. A nonlinear problem can be transformed to a linear problem with using kernel functions. The transformation reduces complexity of the algorithm. With some highlights such as perfect theories, support vector machine is a hot point in pattern recognition field nowdays.Theoretical basis for SVM-related statistical learning theory and concepts are introduced at the beginning. Some analysis of 2-category SVM algorithms performance and a summary of their advantages and disadvantages be done in chapter 2. Realization of multi-category classification algorithms be researched and analyzed in the next chapter. Some comparisons of their features algorithm be done in same chapter.For massive training sets, a incremental learning methods be proposed in chapter 4. Such algorithms through analysis Support Vectors distribution characteristics, use small-scale matrix operations to replace large-scale matrix operations. Experimental results show that the algorithm effectively improve training speed.Keywords : Suport Vector Machine; Statistical Learning Theory; Pattern RecognitionThesis : Applied Reserch不要删除行尾的分节符，此行不会被打印- I -目录目录摘要IAbstractII第1章 绪论11.1 研究背景11.2 SVM的理论基础21.2.1 统计学习理论21.2.2 指示函数集的VC维41.2.3 结构风险最小化原则51.3 SVM的基本原理61.4 现阶段SVM的主要研究方向91.5 主要工作和全文结构9第2章 支撑矢量机实现算法的研究112.1 分解算法112.1.1 块算法122.1.2 固定工作样本集122.1.3 SMO152.2 序列算法162.3 超球面分类算法172.3.1 算法描述172.3.2 超球面分类的优化算法192.4 本章小结22第3章 支撑矢量机多类分类实现算法243.1 “一对多”方法243.2 “一对一”方法253.3 一次性求解方法263.4 决策有向无环图273.5 基于二叉树的多类支撑矢量机分类方法293.6 多级支撑矢量机方法303.7 超球面SVM多类分类器313.8 本章小结32第4章 支撑矢量机学习步骤的改进增量学习算法334.1 增量学习算法的意义334.2 支撑矢量的分布特点334.3 SVM增量训练算法354.4 算法的实现步骤与流程364.5 实验及结果分析37第5章 结论与展望39参考文献40附录 学习问题研究的发展与现状43攻读学位期间发表的学术论文47致谢48索引49个人简历50千万不要删除行尾的分节符，此行不会被打印。在目录上点右键“更新域”，然后“更新整个目录”。打印前，不要忘记把上面“Abstract”这一行后加一空行- III -第5章 结论与展望第1章 绪论1.1 研究背景支撑矢量机是一种用于模式识别的方法。模式识别的作用就在于让计算机面对某一事物时将其正确的归入某一类别，它诞生于20世纪20年代，随着40年代计算机的出现，50年代人工智能的兴起，模式识别在60年代初迅速发展成一门学科。几十年来，模式识别研究取得了大量的成果，在很多方面取得了成功的应用，推动了人工智能的发展。经典的模式识别方法有统计模式识别和结构（句法）模式识别。统计模式识别可看成是基于数据的机器学习的特例。基于数据的机器学习是现代智能技术中十分重要的一个方面，主要研究如何从一些观测数据出发得出尚不能通过原理分析得到的规律，利用这些规律去分析客观对象，对未来数据或无法观测数据进行预测。当把要研究的规律抽象成分类关系时，这种机器学习问题就是模式识别问题。随着人工智能的发展，模糊模式识别，神经网络模式识别也取得了大量的成果。特别是在神经网络模式识别领域，集中了大量的研究人员，成果层出不穷。神经网络模式识别方法的一个重要特点就是它能够有效的解决很多非线性问题。但另一方面，神经网络中很多重要的问题没有从理论上得到解决，实际应用中仍有许多因素需要凭经验确定，像网络节点数及网络层数的选择，初始权值和学习步长的确定等；局部极小点问题，过学习与欠学习等都是很多神经网络方法中普遍存在的问题。这些问题几乎使以神经网络为代表的经典机器学习方法的研究停滞不前。人的智慧中一个很重要的方面是从实例学习的能力，通过对已知事实的分析总结出规律，预测不能直接观测的事实。在这种学习中，重要的是要能够举一反三，即利用学习得到的规律，不但可以较好地解释已知的实例，而且能够对未来的现象或无法观测的现象做出正确的预测和判断。我们把这种能力叫做推广能力。在人们对机器智能的研究中，希望能够用机器（计算机）来模拟这种学习能力，这就是我们所说的基于数据的机器学习问题，或者简单地称作机器学习问题。我们的目的是，设计某种（某些）方法，使之能够通过对已知数据的学习，找到数据内在的相互依赖关系，从而对未知数据进行预测或对其性质进行判断。同样，在这里，我们最关心的仍是推广能力问题。统计学在解决机器学习问题中起着基础性的作用。但是，传统的统计学所研究的主要是渐近理论，即当样本趋向于无穷多时的统计性质。在现实的问题中，我们所面对的样本数目通常是有限的，有时还十分有限。虽然人们实际上一直知道这一点，但传统上仍以样本数目无穷多为假设来推导各种算法，希望这样得到的算法在样本较少时也能有较好的（至少是可接受的）表现。然而，相反的情况是很容易出现的。其中，近年来经常可以听到人们谈论的所谓神经网络过学习问题就是一个典型的代表：当样本数有限时，本来很不错的一个学习机器却可能表现出很差的推广能力。人们对于解决此类问题的努力实际上一直在进行。但是，其中多数工作集中在对已有（基于传统统计学原则的）方法的改进和修正，或者利用启发式方法设计某些巧妙的算法。在人类迈进一个新世纪的时候，人们开始逐渐频繁地接触到一个词，就是“统计学习理论1”。这实际上是早在20世纪70年代就已经建立了其基本体系的一门理论，它系统地研究了机器学习的问题，尤其是有限样本情况下的统计学习问题。在90年代，这一理论框架下产生出了“支撑矢量机(SVM)234”这一新的通用机器学习方法。或许是由于统计学习理论为人们系统研究有限样本情况下机器学习问题提供了有力的理论基础，或许更是因为在这一基础上的支撑矢量机方法所表现出的令人向往的优良特性，人们开始迅速重视起这一早在30年前就该重视的学术方向。现在，越来越多的学者认为，关于统计学习理论和支撑矢量机的研究，将很快出现像在80年代后期人工神经网络研究那样的飞速发展阶段。然而，所不同的是，统计学习理论有完备的理论基础和严格的理论体系（相比之下神经网络有更多的启发式成分），而且其出发点是更符合实际情况的有限样本假设，因此，我们期望，统计学习理论的这个研究热潮将持续更长久，而且将在人们关于机器智能的研究中做出影响更深远的贡献。1.2 SVM的理论基础1.2.1 统计学习理论机器学习问题可以形式化地表示为：己知变量与输入之间存在一定的未知依赖关系，即存在一个未知的联合概率( 和之间的确定性关系可看作是一个特例)，机器学习就是根据个独立同分布观测样本，在一组函数中，求一个最优函数，使预测期望风险 (1-1)最小。其中，称作预测函数集，为函数的广义参数，故可表示任何函数集，为由于用对进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数。预测函数通常称作学习函数，学习模型或学习机器。显然，要使式(1-1)定义的期望风险最小，必须依赖关于联合概率的信息。由概率论可知，必须要求己知类先验概率和类条件概率密度才能求得联合概率。但是，在实际的机器学习问题中，我们只能利用已知样本的信息，因此期望风险无法直接计算和最小化。根据概率论中大数定律的思想，我们用算术平均代替式(1-1)中的数学期望，定义 (1-2)来逼近式(1-1)定义的期望风险。由于式(1-2)是用已知的训练样本定义的，因此称作经验风险。用经验风险代替期望风险，就是经验风险最小化原则。以神经网络为代表的传统机器学习方法，都采用经验风险最小化原则训练分类器。仔细研究经验风险最小化原则和机器学习问题中的期望风险最小化要求，可以发现，从期望风险最小化到经验风险最小化并没有可靠的理论依据，只是直观上合理的想当然的做法。首先，式(1-1)和式(1-2)都是的函数，概率论中的大数定律只说明（在一定条件下）当样本量趋于无穷时，式(1-2)将在概率意义上趋近于式(1-1) ，并没有保证使式(1-2)最小的与使式(1-1)最小的是同一个点，也不能保证能够趋近于。其次，即使我们有办法使这些条件在样本数无穷大时得到保证，我们也无法认定在这些前提下得到的经验风险最小化方法在样本数有限时仍能得到好的结果。尽管有这些未知的问题，经验风险最小化作为解决模式识别等机器学习问题的基本思想仍统治了这一领域几乎所有的研究，人们多年来一直将大部分注意力集中到如何更好地求取最小经验风险上。Vapnik对传统统计学应用在机器学习问题中的这些不足做了系统的研究，从而提出了专门针对解决小样本学习问题的统计学习理论，该理论系统地给出了经验风险最小化原则下统计学习一致性的条件以及在这些条件下关于统计学习方法推广性的界的结论，并在这些界的基础上建立了全新的小样本归纳推理原则，以及实现这些原则的算法。1.2.2 指示函数集的VC维函数集的VC维是统计学习理论中的一个核心概念，由Vapnik和Chervonenkis提出，并取两人名首字母而得名。VC维反映了函数集的容量。在模式识别问题中，我们研究指示函数集的VC维。一个指示函数集的VC维，是能够被集合中的函数以所有可能的种方式分成两类的矢量的最大数目（也就是能够被这个函数集打散的矢量的最大数目）。如果对任意的，总存在一个个矢量的集合可以被函数集打散，那么函数集的VC维就是无穷大。统计学习理论指出，是函数集的VC维（而不是其自由参数个数）影响了学习机的推广性能。这样，我们可以通过控制函数集的VC维来控制学习机的推广性能，而不必考虑所谓的“维数灾难”问题。1.2.3 结构风险最小化原则在解模式识别问题的过程中，由于实现由贝叶斯决策理论导出的期望风险最小化原则必须依赖类先验概率和类条件概率密度，故期望风险无法直接计算并最小化。在实际应用中，我们只能用经验风险逼近期望风险，并希望通过最小化经验风险来实现期望风险最小5。经验风险最小化(ERM)原则一直是解统计模式识别等统计机器学习问题的基本思想.在此思想的指导下，人们主要解决如何更好地求取最小经验风险。但实践证明，一味追求训练误差最小（对应经验风险最小）并不能得到最好泛化能力，有些情况下，训练误差太小反而会导致泛化能力下降，这在神经网络中表现得尤为突出（过学习问题）。导致出现该问题的一个根本原因就是传统统计学是一种渐进理论，它的许多结论都是在样本数目趋向于无穷大的条件下得出的，而在小样本条件下，以传统渐进统计学为理论基础的经验风险最小化原则并不能很好的实现由贝叶斯决策理论导出的期望风险最小化原则。统计学习理论指出，在小样本条件下，只有同时控制经验风险和学习机的容量（用VC维衡量），才能获得具有良好推广能力的学习机.该思想在数学上可由下式表示的衡量分类器推广能力的界来表达： (1-3)其中称作置信范围(Confidence Interval)，表示实际风险，表示经验风险，表示VC维，为训练集样本数，为置信水平。但该界不具备构造性，即我们无法直接由该界构造出能实现其理论思想的有效学习算法。因此我们必须找出某个能同时实现该理论思想并具备构造性的理论。结构风险最小化原则就是满足这样要求的一个理论。结构风险最小化(Structural Risk Minimization, SRM)67原则很好地实现了同时控制经验风险和学习机容量的思想，其原理如图2所示。SRM将分类器构成的函数集合划分成若干按置信范围（也即按VC维）升序排列的子集，然后再在每一个子集中寻找最小经验风险，从而分两步实现式(1-3)的思想。1.3 SVM的基本原理 SRM原则具备算法构造性，SVM就较好的实现了SRM原则。在众多分类器当中，线性分类器具有最简单的结构，人们便考虑用类似线性判别函数的方法来实现SRM原则，SVM便是从模式类线性可分情况下的最优分类面(Optimal Hyperplane)提出的，它的基本思想是：若在原始特征空间中实现的分类器结构十分复杂，则通过定义适当的核函数诱导出某个非线性变换，用此变换将原始特征空间映射到一个高维空间，然后在这个新的特征空间中求得最优线性分类面，以降低分类器的复杂度。由RKHS(Reproducing Kernel Hilbert Spaces)理论8910可知，当选定的核函数满足一定条件时，由该核函数导出的高维特征空间中两特征矢量间的点积可由核函数在低维特征空间中对应两特征矢量上定义的计算而得到。这样，我们便可在低维特征空间中处理对应高维特征空间中的数据。由于求解 SVM只涉及到矢量间的点积运算，故我们可不必担心由于引入核函数而引起计算上的维数灾难，而可将注意力集中到如何选取恰当的核函数上，以改善特征矢量在高维特征空间中的分布，从而使分类器结构更简单。这样，求解SVM的过程即为在高维特征空间中求解模式类样本数据之间最优分类面的过程，此处的最优分类面是在控制样本错分率的前提下使两类样本数据间的分类间隔（高维特征空间中）最大的分类面。统计学习理论指出，间隔分类超平面集合的VC维上界可由式(1-4)给出： (1-4)其中，为包含训练数据的球体的半径，。为特征空间的维数。我们考虑两类分类问题，为给定训练样本，其中为第个样本矢量，代表的类别。当样本线性不可分时，广义最优分类面可通过解决下列条件约束优化问题而得到： (1-5)使分类间隔最大相当于使最小，训练错误率为0意味着对所有的样本有 (1-6)这时，求最优分类问题表示为求解下列QP (Quadratic Programming)问题： (1-7)在线形不可分的情况下引入松弛变量，则转化为下面的QP问题： (1-8)其中，为松弛因子。利用lagrange方法将上述问题转化为其对偶问题，若选定某一个核函数，当时，就得到Ll-SoftMargin SVM，这时，等价于解决下列QP (Quadratic Programming)优化问题10： (1-9)其中，且.为我们选定的核函数，为样本矢量，为样本类别，为控制错分样本与模型复杂度之间折衷度的常量。我们称(1-9)为Ll-SVM QP问题。解Ll-SVM QP问题后即可得到SVM： (1-10)可以证明，(1-9)优化问题的最优解对应于一个间隔分类超平面集合中处于几何中心位置的元素（在高维空间中，从几何上来讲，该优化问题的最优解所对应的学习机即为某一个超球的中心位置所对应的矢量）。由式(1-4)可知，在选定核函数，训练集确定的情况下，只需最小化便可控制，从而可以控制分类器所在的分类超平面集合的置信范围。然后再在该集合中寻找使经验风险最小的分类器（该分类器即对应于分类器集合的几何中心），继而实现SRM原则。总结起来，SVM主要体现了以下思想：1) 分类器容量控制的思想。也即控制分类器集合函数的VC维。该思想直接来源于统计学习理论，SVM通过同时控制经验风险和学习机的容量来提高推广能力。2) 通过引入核的思想来控制分类器容量。若在原始特征空间中实现的分类器结构十分复杂（对应分类器函数集的VC维比较高），则通过定义适当的核函数诱导出某个非线性变换，用此变换将原始特征空间映射到一个高维空间，然后在这个新的特征空间中求得最优线性分类面，以降低分类器的复杂度（即降低分类器函数集的VC维）。3) 通过求解QP来实现容量控制的思想与核的思想。1.4 现阶段SVM的主要研究方向1) SVM提出之后，从理论的角度研究SVM的推广性能一直是SVM领域的研究重点，并取得了丰硕的成果，这些成果为提高SVM的推广性能提供了理论保证。2)从SVM实现算法的角度看，求解SVM可以转化成一个二次规划(QP)问题，目前，针对QP的研究已相当深入，这些研究成果从算法实现上保证了SVM的实用性。但实际上，通过求解QP来实现容量控制与核的思想，在实践中还存在众多问题。其中一个主要问题就是参数选择与优化问题，包括核函数的选择与参数优化及控制经验风险与分类器函数集VC维的参数的优化等。核函数选择及参数优化是当今SVM领域的研究热点。3) SVM是一种两类分类器，而在实际应用中要解决多类分类问题。用SVM构造多类分类器是SVM领域的又一研究重点。用SVM构造多类分类器有众多的理论与算法问题需要解决。一方面，衡最SVM推广性能的现论成果不能直接应用于由SVM构造的多类分类器之中，因此，有必要从理论上研究由SVM构造的多类分类器的推广能力，为构造多类分类器提供理论指导。另一方面，虽然现阶段SVM的实现算法已非常高效，但由于多类分类问题往往较复杂，要处理的数据也比较庞大，因此，多类分类器的高效构造算法的研究就显得非常重要。4) SVM的应用研究。应用研究领域包括图像识别（指纹、卫星图像等）与声音、压力等感知信号的识别。日前，上述几方面问题正得到广泛研究。1.5 主要工作和全文结构本文主要针对支撑矢量机这种比较新的机器学习方法进行分析研究，重点在其实现算法上。支撑矢量机原本是针对二类分类问题而提出的，通常的办法是将其转化为二次规划问题加以解决，如何利用支撑矢量机的特点进行算法的优化和如何将其由二类分类器推广到解决现实中常见的多类分类问题的多类分类器是目前的研究重点。本文针对这些方面进行研究并探索其在织物图像识别问题中的应用。 论文的结构安排如下:第一章绪论，简要介绍了支撑矢量机的理论基础统计学习理论的若干原理，并对支撑矢量机算法的发展现状及主要研究内容作了简单概括。第二章基于支撑矢量机实现算法的研究，分析现有的典型二类支撑矢量机分类算法。第三章支撑矢量机多类分类算法的研究，总结目前基于支撑矢量机的多类别分类方法，包括“一对多”方法、“一对一”方法、一次性求解方法、决策有向无环图方法等。第四章针对支撑矢量机学习步骤，提出了一种改进算法增量学习算法。全文对现有支撑矢量机的实现算法进行了分析，指出其优缺点并提出改进算法，并结合织物图像的识别，进行了试验对比，这样对这些算法的性能有了更加直观的对比。在本课题中将采用一种新的方法对矿井瓦斯监测数据及瓦斯流的分布情况进行分析即蒙特卡洛统计模拟分析法。所谓蒙特卡洛法就是利用对所要求解的变量的统计数字特征来进行问题求解的。这种方法所使用的概率分布的原始分布来自于对变量的客观观测值系列，所以它能准确的反映变量的概率特征，而不加入任何的主观判断因素。双击上一行的“1”“2”试试，J(本行不会被打印，请自行删除)第2章 支撑矢量机实现算法的研究前面提到，本质上是通过求解下面的二次规划问题来实现SVM算法： (2-1)对上面的优化问题，可用传统的标准二次型优化技术来解决，例如牛顿法(Newton) 、拟牛顿法(Quasi-Newton) 、共扼梯度法(Conjugate Gradient ) 、原-对偶内点法(Primal-dual Interior Point Methods) 等，现在也有现成的软件包，如Lindo. 但这些方法存在一些问题，一是运算速度比较慢，二是有稳定性问题。产生这些问题的主要原因是：首先，QP 方法需要计算和存储核函数矩阵，当样本点数目较大时，需很大的内存；其次，SVM 在二次型寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法是占用算法时间的主要部分11。 由于支撑矢量机转化为二次规划问题中具有线性约束，其矩阵为正半定Hessian阵，其具有一些良好的数学特性：1)最优化问题的凸性（目标函数为凸函数），具有全局最优解；2)满足KKT(Karash-Kuhn-Tucker)条件的解必为全局最优解；3)SVM本身具有：支撑矢量数目远小于训练样本数目，并且有些支撑矢量为取上界值的支撑矢量(Bounded Support Vectors)，反映在二次规划问题中即为其全局最优解具有稀疏性。利用这些特性，可以使用优化技术来加快计算速度和降低存储占用。2.1 分解算法Qsuna、 Joachims、Platt等人提出了分解算法(decomposition) 1213。其基本思想就是循环迭代：将原QP问题分解成为一系列小的QP子问题，按照某种迭代策略，通过反复求解子问题，最终使结果收敛到原问题的最优解。根据子问题的划分和迭代策略的不同, 又可以大致分为2类。2.1.1 块算法块算法(Chunking Algorithm)基于这样一个事实，即去掉Lagrange乘子等于零的训练样本不会影响原问题的解。对于给定的训练样本集，如果其中的支撑矢量是已知的。寻优算法就可以排除非支撑矢量，只需针对支撑矢量计算权值（Lagrange乘子）即可。实际上，支撑矢量是未知的，因此块算法的目标就是通过某种迭代方式逐步排除非支撑矢量。具体的做法是：选择一部分样本构成工作样本集进行训练，剔除其中的非支撑矢量，并用训练结果对剩余样本进行检验，将不符合训练结果（一般指违反KKT条件）的样本（或其中的一部分）与本次结果的支撑矢量合并为一个新的工作样本集，然后重新训练。如此重复直到获得最优结果为止。当支撑矢量的数目远远小于训练样本数目时，块算法显然能够大大提高运算速度。然而，如果分类SVM是不可分的，或者是回归SVM的情况，这时支撑矢量的数目本身就比较多，随着算法迭代次数的增多，工作样本集也会越来越大，算法依旧会变得十分复杂。2.1.2 固定工作样本集针对块算法的缺点，提出把问题分解成为固定样本数子问题的方法：工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程中只是将剩余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换，即使支撑矢量的个数超过工作样本集的大小，也不改变工作样本集的规模，而只对支撑矢量中的一部分进行优化。算法描述：样本分成两部分，一部份是工作集，一部份是保留集：(1)给定工作集中元素个数（为偶数）及精度要求，取初始点，令=1.(2)如果是问题的最优解，则停止。否则，重新寻找工作集，定义，定义、为矢量的子矢量，它们分别对应和.(3)求解关于的二次规划： (2-2)(4)设为(2)式的最优解并且，设并转过程(2).算法特点：固定工作样本集的方法和块算法的主要区别在于：块算法的目标函数中仅包含当前工作样本集中的样本，而固定工作样本集方法虽然其优化变量仅包含工作样本，但其目标函数却包含整个训练样本集，即工作样本集之外的样本的Lagrange乘子固定为前一次迭代的结果，而不像块算法中那样设为0. 而且固定工作样本集方法还涉及到一个确定换出样本的问题（因为换出的样本可能是支撑矢量)。工作集的选取问题：此算法的一个重要议题是每次迭代时工作集的选取。Joachims在他的算法中采用了Zoutendijk方法，就是找一个恰有个分量，且使(2-2)目标函数下降速度最快的方向，然后用的这些非零分量的下标组成工作集. 确切地说,考虑如下的优化问题: (2-3)，为第次迭代时的值。为第次迭代时的梯度。工作集的选取算法如下：(1)降序排列 .(2)设，从序列的顶部依次往后选取个元素，要求入选的元素满足或者() . 设，从序列的底部依次往前选取个元素，要求入选的元素满足或者() . 不满足以上条件的元素对应的设为0.收敛性分析：这个算法收敛性的证明引起了很多学者的兴趣，他们做了很多有益的工作。 但到目前为止，这个算法的收敛性还没有被完全证明。总体证明思路：(1) 通过上面工作集选取算法所获得的是(2-3)式的最优解；(2) 根据Zoutendijk方法的属性可知：是(2-1)式的最优解的充要条件是也是(2-3) 式的最优解，并且(2-3)式在处的值为零（后续所有证明步骤都围绕这个目标进行）；(3) 是关于的减函数；(4)；(5) 如果是降序序列里从top (bottom)部选取的第一个元素，则这个证明目前存在的缺陷是在第(3)步的证明过程中应用到了一个假设: 矩阵Q 满足；(6).这个证明目前存在的缺陷是在第(3)步的证明过程中应用到了一个假设：矩阵满足是矩阵的最小特征值，是的任意子集，并且(这个假设目前还没有被去掉) .有关算法收敛性的证明揭示了训练过程中的变化轨迹及算法收敛时各元素在序列的位置及其变化情况。这些信息对算法的改进，如工作集的选取与缩减，停机条件的设定具有重要的指导意义。2.1.3 SMOPlatt在1998年提出SMO(Sequential Minimal Optimization，连续最小优化)算法12，它是一种特殊的分解算法。其特点是将工作集中元素个数固定为2，由于(2-1)具有线性约束和不等式约束，故2是使优化可行的最小变量数。每次迭代只优化两个参数，这样就使得对这两个变量优化过程中不需要引入QP问题优化器进行数字求解，只用分析的方法即可得到两个变量的最优解。由于逻辑分析器远比优化器进行复杂的数学运算快很多，所以使用这种方法可以显著提高效能。)两变量QP问题的分析求解设，为待优化变量，令，则的约束如下： (2-4)正常情况下，目标函数正定，沿线性约束方向具有最小值，如下计算： (2-5)其中，为SVM上一步输出的误差。将经区间限定后，得到最优解. 则，然后用KKT条件对解进行评价。)待优化变量选择策略SMO采用启发式方法确定每一步要优化的变量，以提高收敛速度。针对,有两个独立的选择策略，选择其中一个变量（如）的过程构成外层循环，如果外层循环找到一个违反KKT条件的变量，则将该变量确定为优化目标。外层循环单程遍历所有变量，并与多重遍历非界值支撑矢量对应的变量集交替进行。算法将非界值支撑矢量集对应的变量集优化完成后再单程遍历所有变量，这样，算法把训练时间主要集中在违反KKT条件概率较大的变量身上。随着算法的进行，界值支撑矢量对应的变量趋向于保持边界值不动，而其他支撑矢量对应的变量则得到更多的动态优化。一个变量选好后，算法通过选取使最大的变量作为另外一个待优化的变量。)优缺点分析该算法可以说是分解算法的一个极端特例，其优点是针对2个样本的二次规划问题可以有解析解的形式。因为只有2个变量，应用等式约束可以将其中一个用另一个表示出来，所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出。这样，算法避开了复杂的数值求解优化问题的过程；其工作集的选择也别具特色，不是传统的最陡下降法，而是启发式。Platt设计了一个两层嵌套循环分别选择进入工作样本集的样本，在外环中寻找违背KKT最优条件的样本，然后在内环中再选择另一个样本，完成一次优化。再循环，进行下一次优化，直到全部样本都满足最优条件为止。这种启发式策略大大加快了算法的收敛速度。SMO算法主要耗时在最优条件的判断上，所以应寻找最合理即计算代价最低的最优条件判别式，同时对常用的参数进行缓存。子问题的规模和迭代的次数是一对矛盾，SMO将工作样本集的规模减少到2，一个直接的结果就是迭代次数的增加。所以SMO实际上是将求解子问题的耗费转嫁到迭代上，然后再在迭代上寻求快速算法。2.2 序列算法解决算法速度问题的另一个途径是采用序列优化的思想。这种方法主要目的是研究当出现新的单个样本时，它与原有样本集或其子集，或与原有样本集训练结果之间有何种关系。例如，它的加入对原有样本集的支撑矢量集有什么样的影响，怎样迅速地确定它对新的决策函数的贡献等等。如果能够简单、有效地确定单个样本加入工作样本集后对训练结果的影响，那么，当出现新的样本时，可以利用原来的训练结果而不必重新开始；也可以让训练样本逐个进入工作样本集以简化寻优过程，提高算法速度。这实际上是将工作样本集中的样本数减少到1个。 这种算法也可以用于SVM的在线学习方法，SOR14（Successive Overrelaxation，连续过松弛）方法就是这样一种思路，通过在原目标函数中加一项，从而对偶问题多了1项，而约束条件少了1项等式约束，变为边界约束条件下二次规划问题，适合迭代求解。同时，应用矩阵分解技术，每次只需更新Lagrange乘子的1个分量，而不需将所有样本载入内存，提高了收敛速度。Gert提出了一种增量减量式序列学习方法，即增加1个训练样本或减少1个样本对Lagrange 系数和支撑矢量机的影响。实验表明，算法是有效的，特别是减少1个样本时，对模型选择算法LOO(Leave One Out) 的形象解释。Mario Martin提出了回归SVM的在线序列学习方法，其思路和Gert是相同的。Liva Ralaivola提出了一种增量式序列学习方法，它的特点是基于RBF核的局部特性只更新对学习机输出影响最大的Lagrange系数，其余的Lagrange系数不变，这样就可以减少计算复杂性。2.3 超球面分类算法在现实中，有很多问题涉及到划分正常和非正常两类样本的问题。在很多领域(例如医学诊断、故障检测等)有较大的应用潜力。一个可行的办法是对当前已知的数据分布建立模型，得出支撑点；这样，可以建立一个判断函数，对于新的样本点，如果函数计算结果为正，则是正常样本，否则，是奇异点。超球面分类器就是基于上述思想产生的，目的就是找到一个超球面，包含尽量多的正常点，而其半径尽量小。落在这个超球面以外的都是非正常的点。2.3.1 算法描述包含所有样本的最小球作为决策边界，称为支撑矢量数据域描述15(SVDD, Support Vector Domain Description).要求包含所有样本的最小球，需要确定球心和半径,使得所有样本位于球内且半径最小，也就是需要解决下面的问题16： (2-6)转化为其对偶问题： (2-7)要测试一个新的样本是否位于球内，需要计算其到球心的距离，当此距离小于半径时，该样本被接受，即新样本需满足： (2-8)其中球心，半径可通过任一支撑矢量所对应的lagrange乘子求得： (2-9)通常即使将最外层数据忽略，数据也不是成球形分布的。为了使对数据的描述更为灵活，同样引入核函数，将样本映射到某特征空间，此时只需要用核函数代替式(2-7), (2-8)中的矢量点积： (2-10) (2-11)不同的核函数将导致不同的特征空间，也将因此形成原样本输入空间中不同形式的数据描述。在实际的应用中，超球面分类算法表现出了较好的特性，尤其是在异点检测中，这是因为：超平面把空间一分为二，两边的地位是相等的，对于第三类样本无法做出正确的处理；而超球面把空间分成地位不相等的两部分，对第三类样本来说，处在超求内部和外部是不一样的。通过控制超球的大小和范围，使超球的含义不仅仅是分开两类，而且还要把球里面的样本尽量包“牢”和包“纯”，拒绝其他类样本的进入。2.3.2 超球面分类的优化算法目前的超球面算法是有损失的，训练好的SVM间隙宽度在所有的情况下都为零，而SVM的基本思想就是要最大化间隙宽度，这就说明其推广能力一般。基于上述事实，需要在目标函数中补充使分类间隔尽量大这个条件，引入参数,对算法进行改进17： (2-12)其对偶问题为： (2-13)对于非线性问题，引入核函数，有： (2-14)类似于最优超平面，如果训练样本集被超球面正确的分开，并且距超球面最近的样本数据与超球面之间的距离最大，则该超球面为最优超球面(图3)，根据统计学习理论可知，其推广能力最优。图中小圆圈表示1类，小方块表示2类，黑色实心表示支撑矢量。类别1区域为： (2-15)类别2区域为： (2-16)最优超球面为： (2-17)其中，表示半径，为一个很小的正数，表示间隙宽度将(2-15)和(2-16)展开，得： (2-18) (2-19)当时，改进算法初始问题的约束条件(2-12)变为： (2-20) (2-21)令，又因为趋近于零，则式(2-18)和(2-20)，(2-19)和(2-21)是相等的。当时，此时间隙宽度为零，就是原先未改进的算法，推广能力差。当时，根据Kuhn-Tucher定理，对偶变量与约束的乘积在鞍点处为零，即. 因为，所以此时，可得： (2-22)然后根据式(2-14)的约束条件可得： (2-23) (2-24)由于边界支撑矢量具有性质，对于个边界支撑矢量之和总是小于，即： (2-25)式中，表示支撑矢量的数目，根据式(2-24)和(2-25)可得： (2-26)由式(2-26)可知，既是边界支撑矢量与样本数之比的上界，同时又是支撑矢量数与样本数之比的下界，因此通过可以有效地控制支撑矢量的数目。根据式(2-23), (2-24)和(2-26)可得： (2-27) (2-28)其中，表示边界支撑矢量属于正类的数目，表示支撑矢量属于正类的数目，表示边界支撑矢量属于负类的数目，表示支撑矢属于负类的数目。根据式(2-27)和(2-28)可知，又因，为了使正类别错分的训练样本点尽可能的少，即使NBSv+尽可能的小，就需要调节，使之尽可能的小。这个改进算法引入了参数，并且训练好的SVM在大多数情况下能够保证，也就是间隙宽度在大多数情况下是不为零的，因此具有较好的推广能力。克服了之前的超平面算法的推广能力差的缺点。2.4 本章小结本章针对几种常见的支撑矢量机两类分类器进行了分析与研究，对其性能以、优缺点以及适用范围做了探讨。总体来说，两类支撑矢量机分类器发展的比较成熟，已经广泛地应用到工程、科研等领域，尤其是对解决一些小样本下的模式识别问题发挥了非常好的作用。但需要指出的是，现实中的实际情况，更多的是多类识别问题，如何将两类支撑矢量机应用到多类模式识别，是个急需解决的问题。第3章 支撑矢量机多类分类实现算法现实中更多的是多类分类的问题，而支撑矢量机最初是作为两类分类器提出的，如何将其扩展到多类分类器，从它诞生之时就成为一个研究的热点。3.1 “一对多”方法支撑矢量机多类分类方法最早使用的算法就是“一对多”(One-against-the-rest Method)方法18。要得到多类分类机，通常的方法是构造一系列两类分类机，其中的每一个分类机都把其中的一类同余下的各类分划开。然后据此推断某个输入的归属。“一对多”方法是对于类问题构造个支撑矢量机子分类器。在构造第个支撑矢量机子分类器时，将属于第类别的样本数据标记为正类，不属于类别的样本数据标记为负类。测试时，对测试数据分别计算各个子分类器的决策函数值，并选取函数值最大所对应的类别为测试数据的类别。第个支撑矢量机需要解决下面的最优化问题： (3-1)解决(3-1)的最优化问题后，就可以得到个决策函数： (3-2)对于待测样本，将其输入这个决策函数中，得到个值，取得最大值的函数对应的类别即为该样本所属类别。通过以上叙述的“一对多”方法的算法过程，可以看到这种方法的一个明显优点是，只需要训练个两类分类支撑矢量机，故其所得到的分类函数的个数()较少，其分类速度相对较快。这种方法的缺点是，每个分类器的训练都是将全部的样本作为训练样本，这样需要求解个有个变量的二次规划问题，因为每个支撑矢量机的训练速度随着训练样本的数量的增加急剧减慢，因此，这种方法训练时间较长。另一个缺点是，一类对余类的这些两类问题是很不对称的。比如在1到10的数字识别中，要建立把“3”这个数字（正类）同其他数字（负类）划分开的决策函数，此时的训练集中负类点就比正类点多得多。处理这种不对称，可以通过对不同类别用不同的惩罚因子来解决。3.2 “一对一”方法 “一对一”方法(One-against-one Method)方法19基于两类问题的分类方法，不过这里的两类问题是从原来的多类问题中抽取的。具体做法是：分别选取2个不同类别构成一个SVM子分类器，这样共有个SVM子分类器。在构造类别和类别的SVM子分类器时，在样本数据集选取属于类别、类别的样本数据作为训练样本数据，并将属于类别的数据标记为正，将属于类别的数据标记为负。“一对一”方法需要解决如下的最优化问题： (3-3)解决这一最优化问题后，也即用训练样本进行训练后就可以得到个SVM子分类器。 测试时，将测试数据对个SVM子分类器分别进行测试，并累计各类别的得分，选择得分最高者所对应的类别为测试数据的类别。 在这种方法中，需要许多两类问题的分类机。实际上对类问题，就有个两类分类机。例如，需要得到190个分类机。尽管如此，“一对一”方法的每个分类问题的规模比较小，要学习的问题也比较简单。但是如果太大，就会非常大，这