（３ｂ）．设ｄ；：Ｙｉ，从序列的底部依次往前选取ｑ／２个元素，要求入选的元素满足０＜口。＜Ｃ或者（３ｂ）． 不满足以上条件的元素对应的ｄｉ设为０．
以上是Ｄｅｃｏｍｐｏｓｉｔｉｏｎ算法的介绍，而ＳＭＯ算法事实上是Ｄｅｃｏｍｐｏｓｉｔｉｏｎ算法的变种．它的特点是 Ｂ ｆ：２，即每次只选两个元素，则新的口ｒ、ａ笋”可解析求得，避免计算核矩阵Ｑ．
２００５年９月 第４卷第３期
渝西学院学报（自然科学版）。 Ｊｏｕｒｎａｌ ｏｆ Ｗｅｓｔｅｒｎ Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒｅ Ｓｃｉｅｎｃｅｓ Ｅｄｉｔｉｏｎ）
Ｓｅｐ．，２００５ Ｖ０１．４ Ｎｏ．３
ＳＶＭ算法分析与研究
王晓云
（涪陵师范学院 计算机科学系，重庆涪陵４０８００３）
２７丁１ ｃ口ｒ，ｃ ａ’，７，（一善一孑）（：＋）＋ｃ ｅｅｒ＋彳ｒ，￡ｅｒ一。７，（：＋）ｓｕⅥｅｃｔ ｔ。
ｙ７ｆ ａ。）＝ｏ，０≤Ｏｒ＂ｔ，口？≤ｃ，￡：”一，ｆ．
（６）
第二类包括口一ＳＶＣ、口一ＳＶＲ两种学习机，它们的统一表示方式为：
ｍｉｎ百１ ｔ７／＂∞＋ｐ７口，
０≤ａ。≤Ｃ，ｔ＝１，…，Ｚ．
上述事实迫使人们寻找提高算法运行速度及降低存储需求的新方法．目前最著名也最常被使用 的算法是分解算法（ｄｅｃｏｍｐｏｓｉｔｉｏｎ）和序列最小最优化方法（ＳＭＯ）．这两种算法都利用了支持向量机的 良好特性：解的稀疏性和最优化问题的凸性．
１分解算法简介 训练ＳＶＭ的本质是解决一个二次规划问题：
ｍｉｎ｛口７伽一ｅｒ口，
ｍｉｎ喜口７啦＋Ｐ７ａ，
０≤ａ。≤Ｃ，ｔ＝１，…，Ｚ．
（４）
），Ｔａ＝Ａ．
由于￡一ＳＶＲ的对偶问题为：
ｍｉ，专（ｄ～ａ‘）７Ｑ（口一ａ”）＋￡∑（口＋口＋）＋∑盈（ａ—ｎ＋）ｓｕｂｊｅｃｔ ｔｏ
∑（口。一＆？）＝ｏ，０≤ａｉ，ａ？≤Ｃ，ｉ＝１，…，ｚ．
（பைடு நூலகம்）
为了和（４）式相对应，ＬＩＢＳＶＭ将其改造为：
（５）如果ｉ：（ｉ：）是Ｙ。Ｖｆ（云）：降序序列里从ｔｏｐ（ｂｏｔｔｏｍ）部选取的第一个元素，则），‘Ｖ，（ａ）ｉ，＝ Ｙ。．Ｖ，（五）。
（６）ｖｆ（ａ）７１ｄ＝０． 这个证明目前存在的缺陷是在第（３）步的证明过程中应用到了一个假设：矩阵Ｑ满足 ｍｉｎ（ｍｉｎ（ｅｉｇ（ＱⅡ）））＞０，ｒａｉｎ（ｅｉｇ（．））是矩阵的最小特征值，，是｛１，…，ｆ｝的任意子集，并且ｌ，ｌ≤ｑ．
［参考文献］
［１］Ｋｅｅｒｔｈｉ Ｓ ａｎｄ Ｇｉｌｂｅｒｔ Ｅ Ｇ．Ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ８ ｇｅｎｅｒａｌｉｚｅｄ ＳＭＯ ａｌｇｏｒｉｔｈｍ ｆｏｒ ＳＶＭ ｃｌａｓｓｉｆｉｅｒ ｄｅｓｉｇｎ【Ｊ Ｊ，Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ，
２００２，４６：３５１—３６０．
［２］Ｋｅｅｎｈｉ Ｓ Ｓ，Ｓｈｅｖａｄｅ Ｓ Ｋ，Ｂｈａｔｔａｃｈａｒｙｙａ Ｃ ａｎｄ Ｍｕｒｔｈｙ Ｋ Ｒ Ｋ．Ｉｍｐｒｏｖｅｍｅｎｔｓ ｔｏ Ｐｌａｔｔ’ｓ ＳＭＯ ａｌｇｏｒｉｔｈｍ ｆｉ）ｒ ＳＶＭ ｃｌａｓｓｉｆｉｅｒ ｄｅｓｉｇｎ［Ｊ］．Ｎｅｕｒａｌ Ｃｏｍｐｕｔａｔｉｏｎ，２００１，１３：６３７—６４９．
３．１ 算法总体方案 ＬＩＢＳＶＭ库ｂ ３总体采用Ｄｅｃｏｍｐｏｓｉｔｉｏｎ算法．当算法２选取工作集Ｂ后，它采用ＳＭＯ方法解决关于 ｄ。的二次式． ３．２ 问题的统一表示 ＬＩＢＳＶＭ根据５种学习机相应的对偶问题及其约束条件的差异将其分为两大类，每一大类采用统 一的问题表示方式．第一类包括Ｃ—ＳＶＣ、Ｏｎｅ Ｃｌａｓｓ—ＳＶＣ和ｅ—ＳＶＲ．这３种学习机的对偶问题及其 约束条件统一表示为：
４展望 Ｄｅｃｏｍｐｏｓｉｔｉｏｎ和ＳＭＯ算法与Ｎｅｗｔｏｎ—ＰＣＧ等相比，在算法效率和所能处理的样本数量上有了很大 提高，但仍然不能处理大规模数据．目前，用ＳＶＭ进行大数据挖掘普遍采用的方法是先对数据进行聚 类，用聚类中心代表其它样本进行训练，获得先验知识；然后判断各样本点距离超平面的距离．距离 低于一定域值的样本点直接参与下一次训练，距离高于一定域值的样本点则由其所属类的质心代表 参与训练，迭代进行训练直至满足某一条件为止．但是，这种方法只适用于线性可分的样本，如果样 本通过核函数映射到高维空间的话，由于聚类这个函数不是同构的，这种办法就行不通了．这些问题 还有待于我们解决．
２ 算法收敛性分析 关于这两个算法收敛性的证明引起了很多学者的兴趣，他们做了很多有益的工作．但到目前为 止，这两个算法的收敛性还没有被完全证明． 总体证明思路：［１’３１ （１）通过算法２所获得的ｄ是（３）式的最优解． （２）根据Ｚｏｕｔｅｎｄｉｊｋ方法的属性可知：口是（１）式的最优解的充要条件是口也是（３）式的最优解，并 且（３）式在口处的值为零（后续所有证明步骤都围绕这个目标进行）． （３）．厂（ａ“１）是关于ｆｆ口“１一口。Ｉｆ ２的减函数． （４）ｌｉｍ ｄｋ＋ｌ：占，ｋ∈Ｋ．
［３］ｕｎ ｃ Ｊ．Ｏｎ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｔｈｅ ｄｅｃｏｍｐｏｓｉｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ｓｕｐｐｏｆｌ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ，１２（６）：１２８８—１２９８．
［４］Ｐｌａｔｔ Ｊ Ｃ．Ｆａｓｔ ｔｒａｉｎｉｎｇ ｏｆ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ ｕｓｉｎｇ ｓｅｑｕｅｎｔｉａｌ ｍｉｎｉｍａｌ ｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｎ Ｂ，Ｓｃｈ“ｏｌｋｏｐｆ，Ｃ．Ｊ．Ｃ．Ｂｕｒｇｅｓ， ａｎｄ Ａ．Ｊ．Ｓｍｏｌａ，ｅｄｉｔｏｒｓ，Ａｄｖａｎｃｅｓ ｉｎ Ｋｅｒｎｅｌ Ｍｅｔｈｏｄｓ—Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｌｅａｒｎｉｎｇ，Ｃａｍｂｒｉｄｇｅ，ＭＡ，１９９８．ＭＩＴ Ｐｒｅｓｓ．
支持向量机（Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅ）是在统计学习理论基础之上发展起来的一种全新的机器学习 算法。ＳＶＭ基于统计学习理论的结构风险最小化原则，它将最大化分类间隔的思想和基于核的方法结 合在一起，表现出很好的泛化能力．由于ＳＶＭ方法有统计学习理论作为其坚实的数学基础，并且可以 很好地克服“维数灾难”和“过拟合”等传统算法所不可规避的问题，所以受到了越来越多的研究人员 的关注．近年来，关于ＳＶＭ方法的研究，包括算法本身的改进和算法的实际应用，都被陆续提了出来． 但是，支持向量机训练的复杂度高度依赖于训练数据的大小．不仅训练时间与数据的平方成正比，而 且训练算法需要存储与训练集对应的核矩阵，当样本点数ｆ成千计时，所需内存相当大．
万方数据
则将其移出工作集，加快算法运行速度．这一思路来自于对算法收敛性的证明：当算法趋于收敛时，取 边界值的口ｉ保持不变，并且排列在Ｙ。ｖ．厂（口“）ｉ序列的正确位置．
３．５ Ｃａｃｈｅ方法 ＬＩＢＳＶＭ采用最近最常使用的方法来Ｃａｃｈｅ Ｑｉ的值．系统根据用户设定的域值在内存中建立一个 链表，每个最新算出的Ｑ。值插入链表的尾部．算法需要某个Ｑｉ值时就查询链表，如果链表不存在此 Ｑｉ，值就立刻计算并插入链表的尾部．如果此时所分配内存区域已满则删除链表头部的Ｑ“．采用此种
（３０）
ｄｉ≥０，ｉｆ（Ｏｌ‘）；＝０，ｄ。≤０，ｉｆ（ＯｔＫ）；＝Ｃ．
（３ｂ）
Ｉ｛ｄｉ ｄｉ≠０｝Ｉ≤ｑ．
（３ ｃ）
八口）＝喜，ＪＱａ—ｅｏ，ｎＫ为第Ｋ次迭代时口的值．ｖ“口‘）为第Ｋ次迭代时Ｖ厂（口）的梯度．工作集
的选取算法如下（算法２）： （１）降序排列Ｙｉ ｖｆ（ａ‘）ｉ． （２）设ｄｉ：一Ｙ。，从序列的顶部依次往后选取ｑ／２个元素，要求入选的元素满足０＜ａ。＜Ｃ或者
［５］Ｃｈｉｈ—Ｃｈｕｎｇ Ｃｈａｎｇ ａｎｄ Ｃｈｉｈ—Ｊｅｎ Ｌｉｎ，ＬＩＢＳＶＭ：ａ ｌｉｂｒａｒｙ ｆｏｒ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ［Ｊ］．２００１． ［６］ＶｌａｄｉｍｉｒＮ．Ｖａｐｎｉｋ统计学习理论的本质［Ｍ］．北京：清华大学出版社，２０００．
（这个假设目前还没有被去掉）． 有关算法收敛性的证明揭示了训练过程中ａ的变化轨迹及算法收敛时各元素在Ｙｉ ｖ厂（ａ２）ｉ序列
的位置及其变化情况．这些信息对算法的改进，如工作集的选取与缩减，停机条件的设定具有重要的 指导意义．
３ ＬＩＢＳＶＭ库分析
万方数据
ＬＩＢＳＶＭ是台湾大学ｃ．Ｊ Ｌｉｎ等人开发的一套支持向量机算法库．这个小组是算法收敛性证明的 主力军，他们利用收敛性证明的成果来改进算法，取得了非常好的结果．许多国际著名研究机构都采 用ＬＩＢＳＶＭ作为它们的训练算法．本节笔者对ＬＩＢＳＶＭ的核心学习引擎代码进行了分析，揭示了它的高 效所在．本分析是基于ＬＩＢＳＶＭ２．７１（ｒｅｌｅａｓｅｄ ｏｎ Ｎｏｖｅｍｂｅｒ ２０，２００４）．ＬＩＢＳＶＭ共实现５种类型的ＳＶＭ 机：Ｃ—ＳＶＣ，移一ＳＶＣ，Ｏｎｅ Ｃｌａｓｓ—ＳＶＣ，￡一ＳＶＲ，移一ＳＶＲ．
（１）给定工作集中元素个数ｌ Ｂ Ｉ：ｑ≤ｚ（ｇ为偶数）及精度要求ｅ，取初始点口１：ｆ％Ｉ，令ｋ： 、口Ⅳ， １．
（２）如果ａ‘是问题的最优解，则停止．否则，重新寻找工作集Ｂ Ｃ｛１，…，ｆ｝，Ｉ Ｂ Ｉ＝ｑ，定义Ｎ＝ ｛１，…，ｚ｝／Ｂ，定义口；、ａ：为向量口５的子向量，它们分别对应Ｂ和Ⅳ．
（３）求解关于ｄ。的二次式：
１ ３· ３．４
工作集缩减
ＬＩＢＳＶＭ采用算法２进行工作集选取时ｑ的取值足够大，即取到两个序列相遇或只隔一个元素为
止．当工作集选定以后，在此工作集内采用ＳＭＯ算法进行迭代解决关于ｄ。的二次式．ＬＩＢＳＶＭ设定一
个域值ｍｉｎ（ｆ，１ ０００）．当迭代次数到达此域值时，就对取边界值的口．进行判断．如果其满足ＫＫＴ条件，
方法避免了存储整个核矩阵给系统造成的负担． ３．６ 参数搜索网格 ＬＩＢＳＶＭ提供了寻找参数Ｃ和ｙ最佳值的方法（仅适用于径向基函数）．它定义Ｃ＝２１，２。２５，…，
２５．），：２一，２“７５，…，２～．用这些数值组成二维网格，每次采用一对网格顶点的值进行交叉测试直至 所有顶点都测试完毕．最后从中选出交叉测试准确率最高者所对应的（Ｃ，ｙ）值对．