本站原创
摘 要： 序贯最小优化算法（O）是支持向量机（SVM）训练算法中一种十分有效的改进方法，但针对大规模样本数据时，O训练速度仍比较慢。为了提高训练速度，在基本保持训练精度的前提下，提出了一种改进优化策略：即跳过部分与精度无关的向量集、提前结束循环、松弛KKT条件以便收缩工作集。经过几个著名的数据集的试验结果表明，此策略可以大幅缩短O的训练时间，并且精度没有明显变化。
关键词： 支持向量机； 序贯最小优化算法； 去除无关向量； 收缩工作集
1004?373X（2013）08?0017?03
0 引 言
支持向量机（Support Vector Machine，SVM）是1995年由 Cortes和Vapnik首先提出的一种新的分类回归方法。它是建立在统计
给定输入空间的l个训练样本[（xi，yi），i=1，2，…，][l，xi∈Rd，yi∈{-1，1}]， SVM的实质是寻找最优分类超平面。将寻找的过程转化为求解一个二次规划问题，式子最终变为：
[min： f（α）=12αTQα-eTαs.t yTαi=0， 0≤αi≤C， i=1，2，…，l]
式中：[e]为全1向量；C为一个重要的参数，从本质上说是平衡经验风险和置信风险的，C越大置信风险越大，经验风险越小，并且所有的[α]都限制在边长为C的正方形范围内；[Q]为l×l的Hessian半正定矩阵，[Qij=][yiyjK（xi，xj）]，而[K（xi，xj）]为核函数。经典的二次规划算法无法处理数据集过大的问题。因此，[Q]阵的存储和计算成为训练SVM急需解决的问题。
早期研究中，Vapnik提出了Chunking算法；Osuna等人提出了工作集固定的分解算法；Joachim将Zoutendijk的可行方向法、Shrinking法、Kernel Cache技术相结合实现了SVMLight软件；Platt的O算法[3]将工作集固定为最小规模，从而可以获得解析解；Keerthi提出了O的改进算法GO；孙剑等人运用缓存机制，减少对BSV核函数的计算来缩减训练时间[4]；李建民等人提出了考虑目标函数下降量和计算代价，提高缓存效率的收益代价平衡的工作集选择算法[5]；张浩然等人提出的策略使得所选取的优化变量能够使目标函数的下降最多， 优化步长更大[6]。近些年来，改进和优化主要涉及到让更多的样本同时得到优化[7]、增加步长加速收敛速度[8]、综合考虑迭代次数和缓存效率[9]、考虑非正定核的运用[10]、运用聚类的方法等的方面，并且都取得了一些成效。
本文在分析O算法的基础上，针对分类向量集过于庞大、算法后期工作集的选取策略、停机条件的设置等方面的问题进行了适当的改进。通过对著名数据集的对比实验，发现此项改进在缩短测试时间的基础上，算法的精度没有很大的变化，仍能达到满意的效果。
具体做法是首先遍历非边界样本选择一个违反KKT条件的样本[α1]，寻找非边界样本[α2]，如果没有非边界样本可以调整，就遍历所有样本；其次是寻找违反KKT条件的边界样本[α1]，寻找非边界样本[α2]，如果没有可以优化的样本就遍历所有样本。寻找的依据是使[E1-E2η]（[Ei]为第i个样本的输出错误）取得最大值。
O算法在选择两个乘子配对优化时，耗时主要是花费在优化选择和迭代次数上。O 除了在处理线性SVM和具有稀疏二进制的数据时训练速度较快之外，对一般数据是非常慢的。
（1）目标函数[W（α）]的增长率，即[W（αt+1）-W（α）W（α）]小于某个容忍值就可以停止，这个条件是最简单的；
（2）原问题的KKT条件，对于凸优化来说它是收敛的充要条件，由于KKT条件本身是比较苛刻的，所以也可以设定一个容忍值，即所有样本在容忍值范围内满足KKT条件则认为训练可以停止；
（3）可行间隙，即原目标函数值[O（w，b）]和对偶目标函数值[W（α）]的间隙，凸二次优化问题的间隙是零。当[O（w，b）-W（α）O（w，b）]小于某个容忍值就可以停止。
恰当的停止条件可以使得算法提早结束训练，从而节省训练的时间。其实，从本质上来说可以推广到寻找经验风险和置信风险之间的平衡。
另一方面，对于算法所依赖的物理条件而言，优化可以从以下方面：
（1）缓存的恰当运用，能用缓存的地方尽量用缓存，这样可以减少重复计算的次数，提高运行效率，但会增加算法的空间复杂度。
（2）关注可以并行计算的地方，将其分成若干部分并行计算，从部分最优寻找到全局最优。
关键词： 支持向量机； 序贯最小优化算法； 去除无关向量； 收缩工作集
1004?373X（2013）08?0017?03
0 引 言
支持向量机（Support Vector Machine，SVM）是1995年由 Cortes和Vapnik首先提出的一种新的分类回归方法。它是建立在统计
源于：论文格式字体www.udooo.com
机器学习的VC维理论和结构风险最小化的理论基础之上。在模式识别、数据挖掘、分类、回归等问题领域都表现出许多特有的优势，因而获得了良好的应用。给定输入空间的l个训练样本[（xi，yi），i=1，2，…，][l，xi∈Rd，yi∈{-1，1}]， SVM的实质是寻找最优分类超平面。将寻找的过程转化为求解一个二次规划问题，式子最终变为：
[min： f（α）=12αTQα-eTαs.t yTαi=0， 0≤αi≤C， i=1，2，…，l]
式中：[e]为全1向量；C为一个重要的参数，从本质上说是平衡经验风险和置信风险的，C越大置信风险越大，经验风险越小，并且所有的[α]都限制在边长为C的正方形范围内；[Q]为l×l的Hessian半正定矩阵，[Qij=][yiyjK（xi，xj）]，而[K（xi，xj）]为核函数。经典的二次规划算法无法处理数据集过大的问题。因此，[Q]阵的存储和计算成为训练SVM急需解决的问题。
早期研究中，Vapnik提出了Chunking算法；Osuna等人提出了工作集固定的分解算法；Joachim将Zoutendijk的可行方向法、Shrinking法、Kernel Cache技术相结合实现了SVMLight软件；Platt的O算法[3]将工作集固定为最小规模，从而可以获得解析解；Keerthi提出了O的改进算法GO；孙剑等人运用缓存机制，减少对BSV核函数的计算来缩减训练时间[4]；李建民等人提出了考虑目标函数下降量和计算代价，提高缓存效率的收益代价平衡的工作集选择算法[5]；张浩然等人提出的策略使得所选取的优化变量能够使目标函数的下降最多， 优化步长更大[6]。近些年来，改进和优化主要涉及到让更多的样本同时得到优化[7]、增加步长加速收敛速度[8]、综合考虑迭代次数和缓存效率[9]、考虑非正定核的运用[10]、运用聚类的方法等的方面，并且都取得了一些成效。
本文在分析O算法的基础上，针对分类向量集过于庞大、算法后期工作集的选取策略、停机条件的设置等方面的问题进行了适当的改进。通过对著名数据集的对比实验，发现此项改进在缩短测试时间的基础上，算法的精度没有很大的变化，仍能达到满意的效果。
1 标准O算法
O是将大的QP问题分解成最小规模的QP问题，算法在固定其他参数的条件下，每次仅选择两个Lagrange乘子[α1，α2]进行更新，由于Lagrange乘子的线性约束条件，所以可以解析出这两个乘子所满足条件的最优值，不断的优化所有的乘子，最终能够解决这个二次规划问题。具体做法是首先遍历非边界样本选择一个违反KKT条件的样本[α1]，寻找非边界样本[α2]，如果没有非边界样本可以调整，就遍历所有样本；其次是寻找违反KKT条件的边界样本[α1]，寻找非边界样本[α2]，如果没有可以优化的样本就遍历所有样本。寻找的依据是使[E1-E2η]（[Ei]为第i个样本的输出错误）取得最大值。
O算法在选择两个乘子配对优化时，耗时主要是花费在优化选择和迭代次数上。O 除了在处理线性SVM和具有稀疏二进制的数据时训练速度较快之外，对一般数据是非常慢的。
2 改进O的策略
一方面，对于凸优化问题，在实现时需要适当的停止条件来结束优化过程，停止条件可以是：（1）目标函数[W（α）]的增长率，即[W（αt+1）-W（α）W（α）]小于某个容忍值就可以停止，这个条件是最简单的；
（2）原问题的KKT条件，对于凸优化来说它是收敛的充要条件，由于KKT条件本身是比较苛刻的，所以也可以设定一个容忍值，即所有样本在容忍值范围内满足KKT条件则认为训练可以停止；
（3）可行间隙，即原目标函数值[O（w，b）]和对偶目标函数值[W（α）]的间隙，凸二次优化问题的间隙是零。当[O（w，b）-W（α）O（w，b）]小于某个容忍值就可以停止。
恰当的停止条件可以使得算法提早结束训练，从而节省训练的时间。其实，从本质上来说可以推广到寻找经验风险和置信风险之间的平衡。
另一方面，对于算法所依赖的物理条件而言，优化可以从以下方面：
（1）缓存的恰当运用，能用缓存的地方尽量用缓存，这样可以减少重复计算的次数，提高运行效率，但会增加算法的空间复杂度。
（2）关注可以并行计算的地方，将其分成若干部分并行计算，从部分最优寻找到全局最优。
2.1 跳过部分非支持向量
在优化过程中，考虑到只有部分样本会成为支持向量，可以将明显不是支持向量的样本跳过来删减大规模训练集，从而减少样本训练的时间，提高训练效率。但修剪的精度不容易掌握，对于边界支持向量较多时，可能修剪的过于粗糙，对于较少时，可能误删了部分支持向量。因此可以计算样本x到分类超平面H的距离d，若[d≤ξ]，则保留此样本，否则就跳过。[ξ]是一个可以调节的量，用它来控制删减的力度。具体到算法中：源于：论文格式字体www.udooo.com