一种多重支持向量机在线学习算法的研究

摘要：增量式支持向量机学习算法是一种重要的在线学习方法。传统的单增量支持向量机学习算法使用一个数据样本更新支持向量机模型。在增加或删除的数据样本点较多时，这种模型更新模式耗时巨大，具体原因是每个被插入或删除的样本都要进行一次模型参数更新的判断。该文提出一种基于参数规划的多重增量式的支持向量机优化训练算法，使用该训练算法，多重的支持向量机的训练时间大为减少。在合成数据集及真实测试数据集上的实验结果显示，该文提出的方法可以大大降低多重支持向量机训练算法的计算复杂度并提高分类器的精度。

关键词：支持向量机；增量式算法；核函数；支持向量

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）01-0115-05

支持向量机（support vector machine，SVM）是一种基于统计学习理论[1]的机器学习方法。SVM利用核函数代将数据映射到高维空间的特征空间，使得原本在低维空间中不可分类的数据变得可以分类。由于SVM最终决策函数只由少数的支持向量确定，因此计算的复杂性取决于支持向量的数目，而不是样本空间的维数， 这在某种意义上避免了“维数灾难”，并使得模型具有鲁棒性。

虽然SVM是一种基于小样本的学习方法，但在很多实际应用中，很难在学习过程的初期就获得一个较为完备的训练数据集，而且随着时间的推移，数据集的特性也会发生一定的变化，因此很必要对学习机进行增量学习，即随着样本数据的不断进入学习机，调整学习机的模型参数，提高学习机的精度就显得尤为重要。

增量式SVM学习，即在获取新的样本后，对整个模型进行重新的学习，调整学习机的相关参数，删除无用的历史样本数据，增加新的样本数据，提高训练模型的适应性和精度[2]。文献[3]用支持向量和新样本构成新增量训练集，只需学习一次就可完成模型参数调整。但该方法在增量训练中抛弃了所有的非支持向量样本，且他们的样本处理是单一调整的模式。在文献[4][5]中，增量学习算法考虑了KKT 条件与样本的分布，样本可以批量的进行加载，但该方法训练时间有待进一步的提高。文献[6]中通过选取训练样本的包向量进行增量训练，这种方法可以减少训练数据的多次扫描，提高训练速度，但还需要解决丢失有用信息的导致的历史数据再训练的问题问题。

本文研究多重增量支持向量机的训练算法。该问题可以描述为：当多个样本点（相对于基于单样本的增量SVM训练而言）被加入或移除SVM训练机时，如何更为有效地调整训练模型的参数。为此，我们借鉴了参数规划问题中的一些方法[3，6]，提出基于参数规划的多重支持向量机更新算法。基于参数规划的训练算法的计算代价为求解在每个断点处的一个线性系统的代价，该代价只与解空间中解路径上的断点数目有关，因此计算复杂度大为降低。

论文组织如下，第一部分介绍SVM及KKT条件。第二部分中，首先简单介绍基于单个数据的SVM训练模型更新算法，然后介绍本文的多重更新算法。第三部分中，我们使用最为流行的基于单个数据更新的增量SVM训练算法算法包Libsvm[7]（基于SMO算法）作为对比算法，在多个数据集上进行了性能对比。第四部分是论文的总结。

1 支持向量机及KKT条件

假设给定一个训练集[S={（xi，yi）}]，i=1，2，...，n，[xi∈X?Rd]是d维空间上的样本点，[yi∈{-1，1}]是样本的类标签空间。支持向量机在样本集[S={（xi，yi）}]上学习如下的一个分类函数：

[f（x）=ωTΦ（x）+b] （1）

其中，[Φ（x）]表示一個特征空间的映射。该模型中的参数[ω]和b可以通过求解式（2）的优化问题得到：

[min 12||ω||2+Ci=1nξi]

[s.t. yif（xi）≥1-ξi]，[ξi≥0，i=1，...，n] （2）

2） 式中，[C]是正则化参数。在（2）式中引入拉格朗日乘子[αi≥0]，最优分辨函数[f：Χ→R]可以描述为[f（xi）=i=1nαiyiK（x，xi）+b]，其中[K（xi，xj）]=[Φ（xi）TΦ（xj）]是一个核函数。根据Karush-Kuhn-Tucker最优条件（KKT），可以得到如下的关系等式：

[yif（xi）≥1 ? αi=0，] （3a）

[yif（xi）=1 ? αi∈[0，C]，] （3b）

[yif（xi）<1 ? αi=C，] （3b）

[i=1n yiαi=0.] （3d）

利用（3a）-（3c），我们定义如下的索引集合：

[Ο={i|yif（xi）>1， αi=0}，] （4a）

[M={i|yif（xi）=1， 0≤αi≤C}，] （4b）

[I={i|yif（xi）<1， αi=C}.] （4c）

在后面的描述中，我们用[vI∈Rn]表示一个以索引集合[I]为下标的子向量。类似的，用[MM，O∈Rn×n]表示一个一M和O为索引的子矩阵。下面我们介绍增量/减量SVM学习算法。

2 增量/减量SVM学习算法

2.1 基于单样本的增量/减量SVM学习算法

在本节，我们简要的介绍一下基于单样本的增量/减量支持向量机算法。使用（4b）和（4c）中得到的数据（支持向量），我们可以将[yif（xi）]扩展为：

[yif（xi）]=[j∈MQijαj+j∈IQijαj+yib] （5）

其中，[Qij=yiyjK（xi，xj）]。当一个新的样本数据[（xc，yc）]添加到训练集中时，我们将它对应的[αC]增加为0，同时保持其他参数的最优条件为满足状态。假设每个变量带来的增量用符号[Δ]表示，为满足（3b）和（3d）的条件，我们需要求解如下的公式：

[QicΔαc+j∈MQijαj+yiΔb=0， i∈M，] [ycΔαc+j∈Myjαj=0.] （6）

关于这个线性系统求解[Δαi]，[i∈M]和b，我们可以得到模型参数更新的方向。在没有元素穿过集合[M]，[I]和[O]的约束下，我们最大化增量[Δαi]。在更新了索引集合[M]，[I]和[O]后，我们重复这个过程，直到这个新的数据点满足最优条件。减量式SVM训练算法的过程类似，只是目标参数趋近于0。

2.2 多重样本的增量/减量SVM学习算法

在线SVM的训练过程中，假设我们同时增加了m个新的样本点，并从原数据集合中移除了[l]个样本的。我们将新增加的样本点和移除的样本点分别记为：[A={n+1，n+2，...，n+m}]和[R?{1，...，n}]，其中，[R]=[l]。我们将[R]中的元素从索引集合[M]，[I]和[O]中移除（例如，[M←M＼R]，[I←I＼R]，[O←O＼R]）。定义两个向量[y=[y1，...，yn+m]T]，[α=[α1，...，αn+m]T]和矩阵[Q∈R（n+m）×（n+m）]。当m=1，[l]=0或者m=0，[l]=1时，此方法等价于上部分介绍的单数据的更新方法。首先，我们设置[αi]=0，[?i∈A]。如果[yif（xi）>1]，[i∈A]，我们可以将这些数据追加到索引集合[O]中，然后将它们从集合[A]中移除，因为这些数据点已经满足了最优条件（3a）。类似地，可以将数据集[{i|yif（xi）=1，i∈A}]添加到集合M，并将它们从A中移除。此外，还可以移除[{i|αi=0，i∈R}] 的那些点，因为这些点对模型的参数没有影响。与单样本的训练算法不同的是，我们需要判定[ΔαA]和[ΔαR]的方向，这两个方向对计算代价有着关键的影响。对于[ΔαR]，跟踪它趋于0 的最短的路径，例如：

[ΔαR]=[-ηαR] （7）

[η]是一个步长参数。对于[ΔαA]，由于我们在先前不能确定[αA]的值，为了判定它的方向，我们可以使用一些优化技术（例如牛顿方法），但是类似的优化方法增加了额外的计算负担。该文用：

[ΔαA]=[η（C1-αA）] （8）

来表示其方向。当[αi]=[C]，[?i∈A]时，这就是一个最优的下降方向。

当调整参数[αi]，[?i∈A?R]时，需要保持其他参数的最优条件。对于[yif（xi）=1]，[?i∈M]以及（3d）中的约束条件，需要判断如下等式：

[j∈AQijΔαj+j∈RQijΔαj+j∈MQijΔαj+yiΔb=0] [?i∈M] （9）

[j∈AyjΔαj+j∈RyjΔαj+j∈MyjΔαj=0] （10）

使用矩阵表示公式（9）和（10），得到如下的公式：

[MΔbΔαM+yTAyTRQM，AQM，RΔαAΔαR=0] （11）

其中，[M=0yTMyMQM]。

根据（4a）-（4c）索引集合的定义，训练算法也要满足下面这些不等式：

[ 0≤αi+Δαi≤C， i∈M，] （12a）

[yi{f（xi）+Δf（xi）}>1， i∈O，] （12b）

[yi{f（xi）+Δf（xi）}<1， i∈I.] （12c）

当将样本编号为[{i|f（xi）≥1}]的样本从集合[A]中移除后，我们得到如下的公式：

[yi{f（xi）+Δf（xi）}<1， i∈A.] （13）

在將[αi]，[ i∈A]从[C]调整的过程中，如果某个[ i]在不等式（13）上变为等号，则将[ i]对应的数据点追加到集合[M]，并将该数据的从集合[A]中移除。此外，如果式（13）保持为真直到[αi=C]，则将该下标对应的数据点从集合[I]中移除。在文献[8]中，满足公式（12）和（13）的区域叫做关键区域（critical region，CR）。

通过控制不等式（12）和（13），该文的算法来更新线性系统（11）的方向。将（7）和（8）代入线性系统（11），得到如下的更新方向：

[ΔbΔαM=η?] （14）

[?=-M-1ΔbΔαM+yTAyTRQM，AQM，R-C1-ΔαAΔαR.] （15）

为得到更新的步长参数[η]，需要验证不等式（12）和（13）。使用向量标记机点积表示法，得到如下的等式：

[yi?Δf=ηψ] （16）

[ψ=y Q：，M?+Q：，A（C1-αA）-Q：，RαR] （17）

此次，“：”表示Q的下标为{1，...， n+m}的元素。由于式（15）与（17）都是关于[η]的线性函数，我们可以计算出每个[i]最大的步长[η]。步长的总个数为[M][×]2+[O]+[I]+[A]。将这个集合记为[H]。则步长可以定义为如下的公式：

[η=min（{η|η∈H，η≥0}?{1}）] （18）

如果[η]变为1，算法终止。因为所有[A]中新的数据及集合[M]，[O]和[I]中的点都满足了最优条件，且[αR]为0。当需要决定[η]的取值时，可以使用公式（14）和（15）更新[αM]和[b]的值，用公式（7）和（8）更新[αA]和[αR]的值。在基于路径的相关文献中，使得线性系统（14）和（15）改变的点叫做断点（breakpoints）。

2.3 断点的数目

增量/减量支持向量机的计算复杂度主要来自于在每个断点求解线性系统（14）的计算代价。因此断点的数目是衡量计算复杂度的重要因素。为描述问题方便，假设有如下条件成立：

1） 断点的数目和路径的总长度成正比。

2） 利用本文中的方法得当的路径是最短路径。

第一点假设意味着断点一致分布在路径上。第二个假设对于移除数据点的参数[αR]为真，因为我们在训练过程中将[αR]调整至0。另一方面，对于一些[αR]，第二个假设不一定要成立，因为我们无法预先确定[αA]最优的取值。图1是一个路径长度和断点的示意图。

（a）增加两个数据点时路径和断点 （b）删除和增加一个数据点

图1 路径长度和断点个数的示意图

3 实验分析

3.1 人工数据集上的性能测试

为了对比本文提出的增量SVM训练算法的性能，我们将本文提出的算法（MI-SVM），基于单个数据点的SVM增量算法（SI-SVM）和最为流行的增量支持向量机训练算法LIBSVM（基于SMO的实现）进行了对比。

在LIBSVM中，我们设定算法停机参数值[ε=10-3]。我们参照问下[8][9]中的方法使用[α]种子的方法来对LIBSVM进行在线学习。实验中使用的核函数是径向基函数核—RBF核，[K（xi，xj）]=[exp（-γxi-xj2）]。

第一个实验是在人工数据集上进行的测试。该人工数据集定义为[（x，y）][∈][?2×{+1，-1}]，数据满足正态分布。实验中，先生成100000个数据点。我们对比了如下场景：（a）分别增加[m][∈][{1，...，50}]个数据点；（b）分别移除[l][∈][{1，...，50}]个数据点；（c）分别同时增加[m][∈][{1，...，25}]和[l][∈][{1，...，25}]。实验结果如图2所示。从图2可以看到，随着增量或减量样本的数目的增多，MI-SVM明显地比SI-SVM快。而SMO算法的变化相对平稳，其变化不是很明显，因为增加和移除的数据比原数据集要小得多。

（a） 增加m个样本点的训练时间 （b） 移除[l]个样本点的训练时间

（c） 同时增加m个数据，移除[l]个样本的训练时间

图2 增加，移除，同时增加和移除训练样本点的性能对比

3.2 真实数据集上的性能测试

为了在真实的数据集上测试本文提出的方法的有效性，我们在UCI的数据集上进行了测试[10]。在训练之前，对数据进行了预处理。实验结果进行了10-交叉验证（对每个测试数据集，分类器都增量式地在另外9份数据集上测试了分类器的性能）。对这组实验中的每个个数据集，核函数也是通过在整个数据集上进行10-折交叉验证得到。下表是本次实验的数据集合核函数的描述，其中C=1，在LIBSVM中，算法停机参数值[ε=10-3]。

表1 数据集及核函数参数

[Data set＼&Attri＼&Sample＼&Kernel＼&diabetes＼&8＼&768＼&RBF，[γ]=0.01＼&German＼&24＼&1000＼&RBF， [γ]=0.0005＼&australian＼&38＼&690＼&RBF， [γ]=0.0005＼&Heart＼&20＼&270＼&RBF， [γ]=0.0005＼&Ionosphere＼&34＼&351＼&RBF， [γ]=0.01＼&]

三种分类方法的精度如表2所示。

表2 三种算法的精度对比（%）

[Data set＼&SMO＼&SI-SVM＼&MI-SVM＼&diabetes＼&70.93＼&70.8＼&70.43＼&German＼&74.90＼&75.8＼&76.7＼&australian＼&85.21＼&85.5＼&85.5＼&Heart＼&77.3＼&75.93＼&79.62＼&Ionosphere＼&94.2＼&94.2＼&94.89＼&]

可以看出，MI-SVM在大多数数据集上显示出了较好的精度，加之第一实验训练速度的提升，MI-SVM算法可以更为有效地解决增量SVM的学习问题。

4 结束语

本文提出了多重增量/减量的支持向量机学习算法。与基于单样本的增量训练算法不同的是，该文提出的方法可以有效地同时在多个增加的样本上进行增量的训练和学习。该文的算法是基于参数规划的思想，通过求解一个线性系统来优化训练算法的路径选择。在人工数据集及真实数据集上的测试表明，该文提出的方法在训练时间和测试精度上都有较好的提高。该文的进一步工作是在更大的数据集上测试增量式SVM的模型优化模型。

参考文献：

[1] Vapnik V.The nature of statistical learning theory[M].New York：Springer Press，1995.

[2] Pavel Laskov，Christian Gehl，Stefan Krüger， and Klaus-Robert Müller.Incremental Support Vector Learning：Analysis，Implementation and Applications.J.Mach.Learn. Res.7，2006， 1909-1936.

[3] Trevor Hastie，Saharon Rosset， Robert Tibshirani， and Ji Zhu.2004.The Entire Regularization Path for the Support Vector Machine. J. Mach. Learn. Res. 5 （December 2004，1391-1415.

[4] Diehl，C.P.；Cauwenberghs，G.，"SVM incremental learning， adaptation and optimization，" Neural Networks，Proceedings of the International Joint Conference on，vol.4，no，2003，2685，2690 vol.4，20-24.

[5] Lacey Gunter and Ji Zhu.Efficient Computation and Model Selection for the Support Vector Regression.Neural Comput，2007，19（6）：1633-1655.

[6] Gang Wang， Dit-Yan Yeung， Frederick H. Lochovsky： A New Solution Path Algorithm in Support Vector Regression. IEEE Transactions on Neural Networks 2008，19（10）：1753-1767.

[7] C.-C. Chang and C.-J. Lin， “LIBSVM： a library for support vector machines，” 2001. Software available at http：//www.csie.ntu.edu.tw/～cjlin/libsvm.

[8]D.DeCosteandK.Wagstaff. “Alpha seedingfor supportvector machines，”in Proceedings of the Inter-national Conference on Knowledge Discovery and Data Mining，2000：345-359.

[9] M.M.Lee， S.S.Keerthi， C.J.Ong，and D. DeCoste， “An efficient method for computing leave-one-out error in support vector machines，” IEEE transaction on neural networks， vol. 15， no. 3，2004：750-757.

[10] P.M. Murphy and D. W. Aha. Uci repository of machine learning databases，1994.

[11] 龍军，殷建平，祝恩，等.选取最大可能预测错误样例的主动学习算法[J].计算机研究与发展，2008，45（3）：472-478.