【毕业学位论文】（Word原稿）基于支撑矢量机的模式识别算法的研究-应用数学

摘 要 - I - 摘 要 支 撑 矢量机 (基于统计学习理论的一种模式识别 方法 。使用结构风险最小化原则替代经验风险最小化原则， 避免了一些长期困扰其他模式识别方法的问题， 使它 对于 小样本学习 有着较好的处理能力 。 利用 核函数，把非线性空间的问题转换到线性空间 上来解决 ，降低了算法的复杂度。 由于具有得天独厚的优点（ 完备的理论基础和较好的学习性能 ） ，使它成为 当前模式识别领域研究的 热点。 首先对 理论 基础 统计学习理论和相关概念进行了 介绍。然后对 二类现算法进行 深入研究 ，并对他 们的性能进行分析，对其优缺点进行了总结。下来对多类分类及实现算法进行了研究与分析，并对他们的算法特点进行对比。 针对大规模训练集，提出了一种增量学习方法。这种算法通过分析 布的特点，采用小规模的矩阵运算来代替大规模的矩阵运算。实验结果表明，该算法有效的提高了训练速度。 关键词 支 撑 矢量机 统计学习理论 模式识别 西安科技大学硕士学位论文 - is a on a a A be to a of as is a in at VM a of be in . of be in of be in a be in . to 目录 摘要 . I . 1 章 绪论 . 1 究背景 . 1 理论基础 . 2 计学习理论 . 2 示函数集的 . 4 构风险最小化原则 . 5 基本原 理 . 6 阶段 主要研究方向 . 9 要工作和全文结构 . 9 第 2 章 支撑矢量机实现算法的研究 . 11 解算法 . 11 算法 . 12 定工作样本集 . 12 . 15 列算法 . 16 球面分类算法 . 17 法描述 . 17 球面分类的优化算法 . 19 章小结 . 22 第 3 章 支撑矢量机多类分类实现算法 . 24 一对多”方法 . 24 一对一”方法 . 25 次性求解方法 . 26 策有向无环图 . 27 于二叉树的多类支撑矢量机分类方法 . 29 级支撑矢量机方法 . 30 球面 类分类器 . 31 章小结 . 32 西安科技大学硕士学位论文 - - 4 章 支撑矢量机学习步骤的改进 增量学习算法 . 33 量学习算法的意 义 . 33 撑矢量的分布特点 . 33 量训练算法 . 35 法的实现步骤与流程 . 36 验及结果分析 . 37 第 5 章 结论与展望 . 39 参考文献 . 40 附录 学习问题研究的发展与现状 . 43 攻读学位期间发表的学术论文 . 47 致谢 . 48 索引 . 49 个人简历 . 50 目录 - 1 - 第 1章 绪论 究背景 支撑矢量机是一种用于模式识别的方法。模式识别的作用就在于让计算机面对某一事物时将其正确的归入某一类别，它诞生于 20 世纪 20 年代，随着 40 年代计算机的出现， 50 年代人工智能的兴起，模式识别在 60 年代初迅速发展成一门学科。几十年来，模式识别研究取得了大量的成果，在很多方面取得了成功的应用，推动了人工智能的发展。经典的模式识别方法有统计模式识别和结构（句法）模式识别。统计模式识别可看成是基于数据的机器学习的特例。基于数据的机器学习是现代智能技术中十分重要的一个方面，主要研究如何从一些观测数据出发得出尚不能通过原理分析得到的规律，利用这些规律去分析客观对象，对未来数据或无法观测数据进行预测。当把要研究的规律抽象成分类关系时， 这种机器学习问题就是模式识别问题。随着人工智能的发展，模糊模式识别，神经网络模式识别也取得了大量的成果。特别是在神经网络模式识别领域，集中了大量的研究人员，成果层出不穷。神经网络模式识别方法的一个重要特点就是它能够 有效的解决很多非线性问题。但另一方面，神经网络中很多重要的问题 没 有从理论 上得到解决，实际应用中仍有许多因素需要凭经验确定，像网络节点数及网络层数的选择，初始权值和学习步长的确定等；局部极小点问题，过学习与欠学习等都是很多神经网络方法中普遍存在的问题。这些问题几乎使以神经网络为代表的经典机器学习方法 的研究停滞不前。 人的智慧中一个很重要的方面是从实例学习的能力，通过对已知事实的分析总结出规律，预测不能直接观测的事实。在这种学习中，重要的是要能够举一反三，即利用学习得到的规律，不但可以较好地解释已知的实例，而且能够对未来的现象或无法观测的现象做出正确的预测和判断。我们把这种能力叫做推广能力 。 在人们对机器智能的研究中，希望能够用机器（计算机）来模拟这种学习能力，这就是我们所说的基于数据的机器学习问题，或者简单地称作机器学习问题。我们的目的是，设计某种（某些）方法，使之能够通过对已知数西安科技大学硕士学位论文 - 2 - 据的学习，找到数据内 在的相互依赖关系，从而对未知数据进行预测或对其性质进行判断。同样，在这里，我们最关心的仍是推广能力问题。 统计学在解决机器学习问题中起着基础性的作用。但是，传统的统计学所研究的主要是渐近理论，即当样本趋向于无穷多时的统计性质。在现实的问题中，我们所面对的样本数目通常是有限的，有时还十分有限。虽然人们实际上一直知道这一点，但传统上仍以样本数目无穷多为假设来推导各种算法，希望这样得到的算法在样本较少时也能有较好的（至少是可接受的）表现。然而，相反的情况是很容易出现的。其中，近年来经常可以听到人们谈论的所谓神经网 络过学习问题就是一个典型的代表：当样本数有限时，本来很不错的一个学习机器却可能表现出很差的推广能力。 人们对于解决此类问题的努力实际上一直在进行。但是，其中多数工作集中在对已有（基于传统统计学原则的）方法的改进和修正，或者利用启发式方法设计某些巧妙的算法。 在人类迈进一个新世纪的时候，人们开始逐渐频繁地接触到一个词，就是“统计学习理论 1”。这实际上是早在 20 世纪 70 年代就已经建立了其基本体系的一门理论，它系统地研究了机器学习的问题，尤其是有限样本情况下的统计学习问题。在 90 年代，这一理论框架下产生出了“ 支撑矢量机(234”这一新的通用机器学习方法。或许是由于统计学习理论为人们系统研究有限样本情况下机器学习问题提供了有力的理论基础，或许更是因为在这一基础上的支撑矢量机方法所表现出的令人向往的优良特性，人们开始迅速重视起这一早在 30 年前就该重视的学术方向。 现在，越来越多的学者认为，关于统计学习理论和支撑矢量机的研究，将很快出现像在 80 年代后期人工神经网络研究那样的飞速发展阶段。然而，所不同的是，统计学习理论有完备的理论基础和严格的理论体系（相比之下神经网络有更多的启发式成分），而且其出发 点是更符合实际情况的有限样本假设，因此，我们期望，统计学习理论的这个研究热潮将持续更长久，而且将在人们关于机器智能的研究中做出影响更深远的贡献。 理论基础 计学习理论 机器学习问题可以形式化地表示为：己知变量 y 与输入 x 之间存在一定第 1 章 绪论 - 3 - 的未知依赖关系，即 存 在一个未知的联合概率 ( , )F x y ( x 和 y 之间的确定性关系可看作是一个特例 )，机器学习就是根据 n 个独立同分布观测样本1 1 2 2( , ) , ( , ) , , ( , )y x y x y， 在 一 组 函 数 ( , )f x w 中 ， 求 一 个 最 优 函 数0( , )f x w，使预测期望风险 ( ) ( , ( , ) ) ( , )R w L y f x w d F x y (1最小。其中， ( , )f x w 称作预测函数集， w 为函数的广义参数，故 ( , )f x w 可表示任何函数集， ( , ( , )L y f x w 为由于用 ( , )f x w 对 y 进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数。预测函数通常称作学习函数，学习模型或学习机器。显然，要使式 (1义的期望风险最小，必须 依赖关于联合概率 ( , )F x y 的信息。由概率论可知，必须要求己知类先验概率和类条件概率密度才能求得联合概率。但是，在实际的机器学习问题中，我们只能利用已知样本的信息，因此期望风 险无法直接计算和最小化。根据概率论中大数定律 的思想，我们用算术平均代替式 (1的数学期望，定义 11( ) ( , ( , ) )ne m p i w L y f x (1来逼近式 (1义的期望风险。由于式 (1用已知的训练样本定义的，因此称作经验风 险。 用经验风险代替期望风险，就是经验风险最小化原则。以神经网络为代表的传统机器学习方法，都采用经验风险最小化原则训练分类器。 仔细研究经验风险最小化原则和机器学习问题中的期望风险最小化要求，可以发现，从期望风险最小化到经验风险最小化并没有可靠的理论依据，只是直观上合理的想当然的做法。 首先，式 (1式 (1是 w 的函数，概率论中的大数定律 只说明（在一定条件下）当样本量趋于无穷时，式 (1在概率意义上趋近于式 (1，并没有保证使式 (1小的 w 与使式 (1小的 w 是同一个点，也不能保证 ()其次，即使我们有办法使这些条件在样本数无穷大时 得到保证，我们也无法认定在这些前提下得到的经验风险最小化方法在样本数有限时仍能得到好的结果。 西安科技大学硕士学位论文 - 4 - 尽管有这些未知的问题，经验风险最小化作为解决模式识别等机器学习问题的基本思想仍统治了这一 领域几乎所有的研究，人们多年来一直将大部分注意力集中到如何更好地求取最小经验风险上。 传统统计学应用在机器学习问题中的这些不足做了系统的研究，从而提出了专门针对解决小样本学习问题的统计学习理论，该理论系统地给出了经验风险最小化原则下统计学习一致性的条件以及在这些条件下关于统计学习方法推广性的界的结论，并在这些界的基础上建立了全新的小样本归纳推理原则，以及实现这些原则的算法。 示函数集的 函数集的 是统计学习理论中的一个核心概念，由 出，并取两人名 首字母而得名。 反映了函数集的容量。在模式识别问题中，我们研究指示函数集的 。一个指示函数集的，是能够被集合中的函数以所有可能的 2n 种方式分成两类的矢量的最大数目（也就是能够被这个函数集打散的矢量的最大数目）。如果对任意的n ，总存在一个 n 个矢量的集合可以被函数集打散，那么函数集的 就是无穷大。统计学习理论指出，是函数集的 （而不是其自 由参数个数）影响了学习机的推广性能。这样，我们可以通过控制函数集的 来控制学习机的推广性能，而不必考虑所谓的“维数灾难”问题。 0 11z 3 V C 维 示 例 平 面 中 直 线 的 V C 维 等 于 3 因 为 它 们 能 打 散 3 个 向 量 而 不 能 打 散 4 个 例 如 向 量不 能 被 直 线 与 向 量 分 开24,3, 章 绪论 - 5 - 构风险最小化原则 在解模式识别问题的过程中，由于实现由贝叶斯决策理论导出的期望风险最小化原则必须依赖类先验概率和类条件概率密度，故期望风险无法直接计算并最小化。在实际应用中，我们只能用经验风险逼近期望风险，并希望通过最小化经验风险来实现期望风险最小 5。经验风险最小化 (则一直是解统计模式识别等统计机器学习问 题的基本思想 们主要解决如何更好地求取最小经验风险。但实践证明，一味追求训练误差最小（对应经验风险最小）并不能得到最好泛化能力，有些情况下，训练误差太小反而会导致泛化能力下降，这在神经网络中表现得尤为突出（过学习问题）。导致出现该问题的一个根本原因就是传统统计学是一种渐进理论，它的许多结论都是在样本数目趋向于无穷大的条件下得出的，而在小样本条件下，以传统渐进统计学为理论基础的经验风险最小化原则并不能很好的实现由贝叶斯决策理论导出的期望风险最小化原则。统计学习理论指出，在小样本条件下，只有 同时控制经验风险和学习机的容量（用 衡量），才能获得具有良好推广能力的学习机 ( ) ( )e m pR w R w (1其中 ( l n ( 2 / ) 1 ) l n ( / 4 )h n 称 作 置 信 范 围 ( ()示实际风险， ()h 表示 ， 1 为置信水平。但该界不具备构造性，即我们无法直接由该界构造出能实现其理论思想的有效学习算法。因此我们必须找出某个能同时实现该理论思想并具备构造性的理论。结构风险最小化原则就是满足这样要求的一个理论。 结构风险最小化 (67原则很好地实现了同时控制经验风 险和学习机容量的思想，其原理如图 2 所示。 分类器构成的函数集合划分成若干按置信范围（也即按 ）升序排列的子集，然后再在每一个子集中寻找最小经验风险，从而分两步实现式 (1思想。 西安科技大学硕士学位论文 - 6 - 真 实 风 险 的 界置 信 范 围风 险函 数 集 结 构. . . . 经 验 风 险欠 学 习 过 学 习基本原 理 则具备算法构造性， 较好的实现了 则。在众多分类器当中，线性分类器具有最简单的结构，人们便考虑用类似线性判别函数的方法来实现 则， 是从模式类线性可分情况下的最优分类面 (出的，它的基本思想是：若在原始特征空间中实现的分类器结构十分复杂，则通过定义适当的核函数诱导出某个非线性变换，用此变换将原始特征空间映射到一个高维空间，然后在这个新的特征空间中求得最优线性分类面，以降低分类器的复杂度。由 论 8910可知，当选定的核函数满足一定条件时，由该核函数导出的高维特征空间中两特征矢量间的点积可由核函数在低维特征空间中对应两特征矢量上定义的计算而得到。这样，我们便可在低维特征空间中处理对应高维特 征空间中的数据。由于求解 涉及到矢量间的点积运算，故我们可不必担心由于引入核函数而引起计算上的维数灾难，而可第 1 章 绪论 - 7 - 将注意力集中到如何选取恰当的核函数上，以改善特征矢量在高维特征空间中的分布，从而使分类器结构更简单。这样，求解 过程即为在高维特征空间中求解模式类样本数据之间最优分类面的过程，此处的最优分类面是在控制样本错分率的前提下使两类样本数据间的分类间隔（高维特征空间中）最大的分类面。统计学习理论指出， 间隔分类超平面集合的 上界 h 可由式 (1出： 22m i n , 1(1其中， R 为 包 含 训 练 数 据 的 球 体 的 半 径 ， 1w，1y a，, 0 , 1 , 2 , ,a i l 。 n 为特征空间的维数。我 们考虑 两 类分类问题， , 中i 个样本矢量， 1,1，代表样本线性不可分时，广义最优分类面可通过解决下列条件约束优化问题而得到： 21() 2. ( ) 1 0 1 , 2 , ,t y w x b i l (1使分类间隔最大相当于使 2w 最小，训练错误率为 0 意味着对所有的样本 ( , ) ( ) 1 0w x b (1这时，求最优分类问题表示为求解下列 题： 21m i n ( )2 ( ) 1 0 1 , 2 , ,w x b i l (1在线形不可分 的 情 况下引入松弛变量，则转化为下面的 题： 西安科技大学硕士学位论文 - 8 - 211m i n ( , ) ( )2. ( ) 1 0 1 , 2 , ,w Cs t y w x b i l (1其中， 0 为松弛因子。 利用 法将上述问题转化为其对偶问题，若选定某一个核函数，当 1 时，就得到 时，等价于解决下列 化问题 10： m i n ,0 1 , ,0 a e i , .(1其中，12( , ) , ( ) Ti j i j nQ y y K x x a a a a ，12( ) , 1 , 1 y y y y ，12()c c c ，且12 nc c c . ( , )x C 为控制错分样本与模型复杂度之间折衷度的常量。我们称 (1 P 问题。解 P 问题后即可得到 1( ) s g n ( ( , ) )m i i x a y K x x b (1可以证明， (1化问题的最优解对应于一个 间隔分类超平面集合中处于几何中心位置的元素（在高维空间中，从几何上来讲，该优化问题的最优解所对应的学习机即为 某一个超球的中心位置所对应的矢量）。由式 (1知，在选定核函数，训练集确定的情况下，只需最小化 w 便可控制h ，从而可以控制分类器所在的分类超平面集合的置信范围。然后再在该集合中寻找使经验风险最小的分类器（该分类器即对应于分类器集合的几何中心），继而实现 则。 总结起来， 要体现了以下思想： 1) 分类器容量控制的思想。也即控制分类器集合函数的 。该思想直接来源于统计学习理论， 过 同时控制经验风险和学习机的容量来提高推广能力。 第 1 章 绪论 - 9 - 2) 通过引入核的思想来控制分类器容量。若在原始特征空间中实现的分类器结构十分复杂（对应分类器函数集的 比较高），则通过定义适当的核函数诱导出某个非线性变换，用此变换将原始特征空间映射到一个高维空间，然后在这个新的特征空间中求得最优线性分类面，以降低分类器的复杂度（即降低分类器函数集的 ）。 3) 通过求解 实现容量控制的思想与核的思想。 阶段 主要研究方向 1) 出之后，从理论的角度研究 推广性能一直是 域的研究重点， 并取得了丰硕的成果，这些成果为提高 推广性能提供了理论保证。 2)从 现算法的角度看，求解 以转化成一个二次规划 (题，目前，针对 研究已相当深入，这些研究成果从算法实现上保证了 实用性。但实际上，通过求解 实现容量控制与核的思想，在实践中还存在众多问题。其中一个主要问题就是参数选择与优化问题，包括核函数的选择与参数优化及控制经验风险与分类器函数集 的参数 函数选择及参数优化是当今 域的研究热点。 3) 一种 两类分类器，而在实际应用中要 解决多类分类问题。用造多类分类器是 域的又一研究重点。用 造多类分类器有众多的理论与算法问题 需 要解决。一方面，衡最 广性能的现论成果不能直接应用于由 造的多类分类器之中，因此，有必要从理论上研究由 造的多类分类器的推广能力，为构造多类分类器提供理论指导。另一方面，虽然现阶段 实现算法已非常高效，但由于多类分类问题往往较复杂，要处理的数据也比较庞大，因此，多类分类器的高效构造算法的研究就显得非常重要。 4) 应 用研究。应用研究领域包括图像识别（指纹、卫星图像等）与声音、压力等感知信号的识别。日前，上述几方面问题正得到广泛研究。 要工作和全文结构 本文主要 针 对支 撑矢 量机这种 比较新的 机器学习 方 法进行分析研究 ，重西安科技大学硕士学位论文 - 10 - 点在其实现算法上 。支 撑矢 量机 原 本是针对 二 类分类问题而提出的， 通常的办法是将其转化为二次规划问题加以解决，如何利用支撑矢量机的特点进行算法的优化和如何将其由二类分类器 推广到 解决现实中常见的多类分类问题的 多类 分类器 是目前的研究重点。本文针对这些方面进行研究并探索其在 织物图像识别 问题中的应用。 论文的结构安 排如下 : 第一章绪论，简要介绍了 支撑矢量机 的理论基础 统计学习理论的若干原理，并对支 撑矢量 机算法的 发展 现状及主要研究内容作了简单概括。 第二章基于 支撑矢量机实现算法的研究 ，分析现有的典型二 类 支 撑矢 量机分类算法。 第三章支 撑矢 量机多类分类算法的研究，总结 目 前基于支 撑矢 量机的多类别分类方法，包括“一对多”方法、“一对一”方法、一次性求解方法、决策有向无环图方法 等。 第四章针对支撑矢量机学习步骤，提出了一种改进算法 增量学习算法。 全文对现有支撑矢量机的实现算法进行了分析，指出其优缺点并提出改进算法，并结合织 物图像的识别，进行了试验对比，这样对这些算法的性能有了更加直观的对比。 第 2 章 支撑矢量机实现算法的研究 - 11 - 第 2章 支撑矢量机实现算法的研究 前面提到，本质上是通过求解下面的二次规划问题来实现 法： m i n ,0 1 , ,0 a e i , .(2对上面的优化问题，可用传统的标准二次型优化技术来解决，例如牛顿法 (、拟牛顿法 (、共扼梯度法 ( 、原 等，现在也有现成的软件包，如 但这些方法 存在一些问题，一是 运算速度比较慢， 二是有 稳定性问题。产生这 些 问题 的主要原因是：首先， 法需要计算和存储核函数矩阵，当样本点数目较大时，需很大的内存；其次，二次型寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法是占用算法时间的主要部分 11。 由于支撑矢量机转化为二次规划问题中具有线性约束，其矩阵 Q 为正半定 ，其具有一些良好的数学特性： 1)最优化问题的凸性（目标函数为 凸函数），具有全局最优解； 2)满足 件的解必为全局最优解； 3)身 具有：支撑矢量数目远小于训练样本数目，并且有些支撑矢量为取上界值的支撑矢量 (反映在二次规划问题中即为其全局最优解具有稀疏性。利用这些特性，可以使用优化技术来加快计算速度和降低存储占用 。 解算法 人提出了分解算法 (1213。其基本思想就是循环迭代：将原 题分解成为一系列小的 问题，按照某种迭代策略，通过反复求解子问题， 最终使结果收敛到原问题的最优解。根据子问题的划分和迭 代策略的不同 , 又可以大致分为 2 类。 西安科技大学硕士学位论文 - 12 - 算法 块算法 (于这样一个事实，即去掉 子等于零的训练样本不会影响原问题的解。对于给定的训练样本集，如果其中的支撑矢量是已知的。寻优算法就可以排除非支撑矢量，只需针对支撑矢量计算权值（ 子）即可。实际上，支撑矢量是未知的，因此块算法的目标就是通过某种迭代方式逐步排除非支撑矢量。具体的做法是：选择一部分样本构成工作样本集进行训练，剔除其中的非支撑矢量，并用训练结果对剩余样本进行检验，将不符合训练结果（ 一般指违反 件）的样本（或其中的一部分）与本次结果的支撑矢量合并为一个新的工作样本集，然后重新训练。如此重复直到获得最优结果为止。当支撑矢量的数目远远小于训练样本数目时，块算法显然能够大大提高运算速度。然而，如果分类不可分的，或者是回归 情况，这时支撑矢量的数目本身就比较多，随着算法迭代次数的增多，工作样本集也会越来越大，算法依旧会变得十分复杂。 定工作样本集 针对块算法的缺点，提出把问题分解成为固定样本数子问题的方法：工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程中只是将剩 余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换，即使支撑矢量的个数超过工作样本集的大小，也不改变工作样本集的规模，而只对支撑矢量中的一部分进行优化。 算法描述 ： 样本分成两部分，一部份是工作集 B ，一部份是保留集 N ： (1)给定工作集中元素个数 B q l（ q 为偶数）及精度要求 ，取初始点 1 ，令 k =1. (2) 如果 问 题 的 最 优 解 ， 则 停 止 。 否 则 ， 重 新 寻 找 工 作 集 1, ,， ，定义 1, , /N l B ，定义 矢量 子矢第 2 章 支撑矢量机实现算法的研究 - 13 - 量，它们分别对应 B 和 N . (3)求解关于 1m i n 20 , 1 , , B B B N N BB N B N a e Q a i qy a y ,.(2(4)设 1 (2)式的最优解并且 1，设 1并转过程 (2). 算法特点 ： 固定工作样本集的方法和块算法的主要区别在于：块算法的目标函数中仅包含当前工作样本集中的样本，而固定工作样本集方法虽然其优化变量仅包含工作样本，但其目标函数却包含整个训练样本集，即工作样本集之外的样本的 子固定为前一次迭代的结果，而不像块算法中那样设为0. 而且固定工作样本集方法还涉及到一个确定换出样本的问题（因为换出的样本可能是支撑矢量 )。 工作集的选取问题 ： 此算法的一个重要议题是每次迭代时工作集 B 的选取。 他的算法中采用了 法，就是找一个恰有 B 个分量，且使 (2标函数下降速度最快的方向 d ，然后用 d 的这些非零分量的下标组成工作集 B . 确切地说 ,考虑如下的优化问题 : m i n ( )0 , 1 1 , 1 , ,0 , ( ) 0 ; 0 , ( )0i i a dy d d i l ad i f a d i f a C bd d q c . ( )( ). ( )(21() 2 a a Q a e a， 第 k 次迭代时 a 的值。 ()为第 k 次迭代时()的梯 度。工作集的选取算法如下： 西安科技大学硕士学位论文 - 14 - (1)降序排列 ()f a. (2)设，从序列的顶部依次往后选取 /2q 个元素，要求入选的元素满足 0或者 (b ) . 设从序列的底部依次往前选取 /2q 个元素，要求入选的元素满足 0或者 (b ) . 不满足以上条件的元素对应 的. 收敛性分析 ： 这个算法收敛性的证明引起了很多学者的兴趣，他们做了很多有益的工作。 但到目前为止，这个算法的收敛性还没有被完全证明。 总体证明思路： (1) 通过上面工作集选取算法所获得的 d 是 (2的最 优解； (2) 根据 法的属性可知： a 是 (2的最优解的充要条件是 a 也是 (2式的最优解，并且 (2在 a 处的值为零（后续所有证明步骤都围绕这个目标进行）； (3) 1()是关于 21 的减函数； (4)1,l i m ,kk k K a a k K ； (5) 如果12()f a降序序列里从 选取的第一个元素，则这个证明目前存在的缺陷是在第 (3)步的证明过程中应用到了一个假设 : 矩阵 Q 满足1 1 2 2( ) ( )i i i iy f a y f a ； (6) ( ) 0Tf a d. 这个证明目前存在的缺陷是在第 (3)步的证明过程中应用到了一个假设：矩阵 Q 满足 m i n ( m i n ( ( ) ) ) 0 , m i n ( ( . ) )I e i g Q e i g是 矩 阵 的 最 小 特 征 值 ， I 是第 2 章 支撑矢量机实现算法的研究 - 15 - 1, , l 的任意子集，并且 (这个假设目前还没有被去掉 ) . 有关算法收敛性的证明揭示了训练过程中 a 的变化轨迹及算法收敛时各元素在