数字技术与应用
常用支持向量机算法分析
姚兆
陈喜龙
（装甲兵技术学院
黄丹丹
吉林长春
130117)
·学术论坛·
【摘要]支持向量机是在统计学习理论的VC维理论和结构风险最小化原则的基础上提出的一种新的模式识别技术，本文对于当前常用支持向量机的几种算法进行了总结和分析，对于今后提出更精确的方法做了充分的准备。
[关键词]支持向量机[中图分类号]TP391
早
机器学习
模式识别
[文献标识码]A
[文豪编号]1007-9416（2010）060150-01
一个确定换出样本的间题（固为换出的样
支持向量机（Support VectorMachines 葡称SVM）追求的是在有限样本情况下的最优解而不仪仅是样本数趋于无穷时的最优解，它具有很好的推广性能，对未知样本的预测有较高的准确率，因此得到广泛应用，目前SVM已成为国际上机器学习领域的研究热点：
1分块算法
“块算法”基于的是这样的事实，去掉Lagrange乘子等于零的训练样本不会影响原间题的解，对于给定的训练样本集，如果其中的支持向量是已知的，寻优算法就可以排除非支持向量，只需要对支持向量计算权值（即Lagrange乘子）即可。实际上支持向量是未知的，因此“块算法”的目标就是通过某种选代方式逐步排除非支持向量。具体的作法是，选择一部分样本构成工作样本集进行训练，别除其中的非支持向量。并用训练结果对别余样本进行检验，将不符合训练结果（一般是指违反 KKT条件）的样本（或其中的一部分）与本次结果的支持向量合并成为一个新的工作样本集，然后重新训练。如此重复下去直到获得最优结果，其收敏性在文献中得到了证明，同时在文献中也对分解算法的收性进行了研究。这种方法当支持向量的数目远远小于训练样本数目时，“块算法”显然能够大大提高运算速度。
2子集选择算法
把间题分解成为固定样本数的子间题：工作样本集的大小固定在算法速度可以容忍的限度内，选代过程中只是将剩余样本中部分情况最糖的样本与工作样本集中的样本进行等量交换，即使支持向量的个数超过工作样本集的大小，也不改变工作集的规模，而只对支持向量中的一部分进行优化，
这个思想最早由Osuna等人提出来的。在Osuna算法中，首先建立一个工作集，保持其大小不变，在解决每个二次规划子间题时，先从工作集中移走一个样本，并加入一个不满足KKT条件的样本，再进行优化。周定工作样本集的方法和块算法的主要区别在于：块算法的目标中仅包含当前· 工作样本集中的样本，面固定工作样本集方法虽然优化变量仅包含工作样本，其目标函数却包含整个训练样本集，即工作样本集之外的样本的Lagrange乘子围定为前一次送代的结果，面不是像块算法那样设为0。而且固定工作样本集方法还涉及到
150
数字技术与应用万方数据
本可能是支持向量)。这样，这一类算法的关键就在于找到一种合适的选代策略使得算法最终能收数并且较快地收做到最优结来
3序列最小优化算法
Platt在中提出 SMO(Sequential Mini malOptimization或SMO）算法，将工作样本集的规模减到最小（两个样本）。之所以需要两个样本是因为等式线性约束的存在使得同时至少有两个Lagrange栗子发生变化。由于只有两个变量，面且应用等式约束可以将其中一个用另一个表示出来，所以选代过程中每一步的子间题的最优解可以直接用解析的方法求出来。这样，算法避开了复杂的数值求解优化问题的过程，此外，Platt还设计了一个两层嵌套循环分别选择进入工作样本集的样本，这种启发式策略大大加快了算法的收敛速度。
对Platt的SMO算法，Keerthi等通过对SVM算法的分析在文款中提出了重大改进，即在判别最优条件时用两个阔值代替一个阔值，从而使算法更合理，更快。其收敛证明在文献中。并通过实际数据的对
证明确实比传统SMO快。同时也指出比，
SMO算法应用于回归等类似的间题。 Ronan将考虑了上述改进的SMO算法应用于分类和回归间题，实现了比SVMlight更强的软件包。Pavlov提出了速度快于SMO 方法的Boost-SMO方法。为了弥补SMO在求解线性支持向量机当中的不足，Kai-MinChung提出了线性支持向量机的分解算法。
4增量式算法
文献提出一种增量式学习方法，其将增量集合作为测试集合，将所有造反KKT 条件的样本与原先的支持向量集合作为新的训练集合，面将所有正确分类的样本抛弃，然面对于新的分类器的偿转和移动，这些样本也有可能成为违反KKT条件的样本，所以如果将这些样本抛弃，有可能会丢失有用信息，影响分类器的精度。
文献"提出一种在线训练支持向量机的方法，其从实验结果证明了其学习速度快于SMO方法，但其是从两个样本开始，新的样本是一个一个地增加的，每检测到一个造反KKT条件的样本，部要进行一系列的循环训练，直到全部被正确分类为止，
这样当支持向量的数量较少时，求解二次规划的规模较小，速度可以较快，但当支持向量数盘较多时，每新增一个违反
KKT条件的样本都求解一次大规模二次规划间题，支持向量机的训练速度会大大降低，这时其在线学习的时间会明显增加，其效率明显降低，
5SVM多类分类方法方面的研究
支持向量机最初是为两类分类间题面设计的，如何有效地将其应用到多类分类间题，是当前支持向量机研究的一个重要方面。目前，构造SVM多值分类器的方法主要有两类，一类是同时考虑多类的分类方法：V.Vapniki2，Weston在1999所提出的多值分类算法，与前面方法对等的还有文歇中所提出的方法，Crammer
and
Singer在2000年提出的多类分类算法，
另一类算法的基本思想是通过组合多个二值子分类器实现对多类分类器的构造，
1~ar（1against=rest）方法，对于N 类间题，构适N个分类器，第i个SVM用第1类中的调练样本作为正的训练样本，而将其它的样本作为负的训练样本，最后的输出是两类分类器输出录大的那一类，其缺点是它的泛化误差无界。
1-a-1（1-against-1）方法，该算法在N类训练样本中构造所有可能的两类分类器，每类仪仅在N类中的2类训练样本上调练，结果共构造K=N(N-1)/2个分类器，
Platt等提出了一个新的学习架构：决策导向的循环图（DecisionDirectedAcy clicGraph，DDAG)，将多个两类分类器组合成多类分类器。对于N类间题，DDAG 含有N（N-1）/2个分类器，每个分类器对应两类，其优点是泛化误差只取决于类数N，和节点上的类间间隙（Margin)，面与输人空间的维数无关，根据DDAG提出算法DAGSVM，DDAG的每个节点和一个 1-a-1分类器相关，其速度显著比标准算法（1-a-r）或最大值算法（MaxWins）
快。
【参考文献]
[1] Lau K W,Wu Q H.Online Train-
ing of Support Vector Classifier[JJ.Pat tern Recognition,2003,36:1913~1920.
[2] Vapnik V.Statistical Learning Theory [M].New York; Wiley,1998.
[3] Weston J and Watkins C.Multiclass
machines[M]. Proc.
supportvector
ESANN99,Brussels, Belgium,1999.