基于选择性抽样的SVM增量学习算法的泛化性能研究

(1.湖北大学 计算机与信息工程学院，武汉 430062; 2.武汉晴川学院 计算机科学学院，武汉 430204)

0 引言

基于支持向量机(support vector machine,SVM)的分类算法[1]，不仅在解决非线性、小样本、高维模式识别和克服“维数灾难”等问题上中表现出了特有的优势，而且还具有坚实的统计学习理论基础[2-3]，简洁的数学模型以及良好的泛化性能。因此，SVM被广泛应用到时间序列预测[4]、回归分析[5]、人脸图像识别等各个领域。尽管SVM理论基础坚实，泛化性能良好，但经典SVM算法是批量式处理，即训练样本一次性被输入到计算机内存中，所以在处理大规模数据时会面临内存限制[6]以及学习效率低等问题。因此具有增量学习功能的数据分类技术应运而生，Syed等人[7]最早提出增量学习，其解决问题的核心在于每一次随机选取算法能够处理的数据量进行训练，留下支持向量，再加入新的训练样本继续训练，依此过程训练学习。近年来，孔锐等人[8]提出一种新的SVM增量学习算法，该算法首先选择可能成为支持向量的边界向量，以达到减少训练的样本数量。Li等人[9]提出基于超平面距离的支持向量机增量学习算法，采用Hyperplane-Distance方法提取样本，选取最有可能成为支持向量的样本构成边缘向量集以提高训练速度。

上述增量学习算法都是基于样本是独立同分布的假设，该假设无论在理论上，还是实际应用中都是非常强的，因现实机器学习[10]中不服从独立同分布的数据很是广泛,所以为非独立同分布的数据更适用于机器学习，减弱独立同分布的假设得到了相关学者的关注，Zou等人[11]证明了具有一致遍历马尔可夫链样本的ERM算法是一致的,且一致遍历马尔可夫链在SVM中也得到了应用，如Xu等人[12]证明了SVM泛化性能马氏抽样要优于随机抽样。针对样本是独立同分布的假设在实际应用中相对牵强，且独立随机抽样的时效普遍偏低，数据存在非全局性等缺点，提出一种新的SVM增量学习算法。该算法利用马氏抽样选取具有一致遍历马尔可夫链性质的训练样本集，研究增量学习的特性，并与基于随机抽样的SVM增量学习算法和文献[15]提出的增量学习算法做出比较。分别从分类错误率、支持向量个数和抽样与训练总时间三个方面对比增量学习算法性能，选用基准数据集作为样本数据，经实验表明，基于选择性抽样的SVM增量学习算法泛化性能更好。

1 相关知识

针对SVM增量学习所涉及到的概念以及一致遍历马尔可夫链等内容，本节将给予介绍以及给出相关的定义。

1.1 支持向量机

基于SVM的二分类器，是在给定的空间下，寻找能够分割两类样本且具有最大间隔的超平面。设带有类别标记的输入模式集X⊂Rn为二分类数据集，类别标签为Y={+1,-1}，输入集的每一个数据点，都有一个类别标签与之对应即X→Y，从中取大小为l的样本作为原始空间训练集:S={s1=(x1,y1),s2=(x2,y2),…,sl=(xl,yl)}，其中xi∈X,yi∈Y,i=1,2,…,l。SVM目标是求解可以分割两类样本点的超平面wx+b=0的最优解，将求解问题可以归纳为式(1)二次规划问题：

(1)

其中:C正则化参数，ε为松弛变量。

借助Lagrange乘子法，转化为对偶问题：

(2)

只需求解式(2)即可获取最优分类面，若原始空间中求取的分类面效果不佳，依据泛函理论知识。存在一种满足Mercer核条件的核函数：K(xi,xj)=<Φ(xi)·Φ(xj)>，可通过线性映射Φ:Rn→H，x→Φ(x)将输入空间映射到Hilber空间中，则相应的决策函数为：

其中非零的拉格朗日乘子(αi≠0)对应的样本点称作为支持向量。支持向量个数越少，则表明SVM的分类器越稀疏。

1.2 增量学习

传统的增量学习算法样本的选择是随机抽样，选取的样本之间不具备关联性。在第2节将介绍一种基于选择性抽样的SVM增量学习算法。

1.3 一致遍历马尔可夫链

实际应用中很多模型产生的样本在本质上是自然涌现的而非独立同分布，如市场预测，语音识别等，这些数据并不符合机器学习中数据独立同分布的假设。所以通过减弱样本是独立同分布的情形，利用一致遍历马尔可夫链模型进行算法泛化性能研究。如下给出一致遍历马尔可夫链的概念：

定义(Z,E)为一个可测空间，则一个随机变量序列{Zt}t≥1以及一系列转移概率测度Pn(S|zi),S∈E,zi∈Z共同构成一个马尔可夫链，假定：

Pn(S|zi):=P{Zn+i∈S|Zj,j

记Pn(S|zi)为n步转移概率：从初始状态为zi的时刻i开始，经过n步迭代后状态为zn+i属于集合S的概率。若转移概率不依赖于在时刻i之前的Zj状态集，称具有马尔可夫性质，即:Pn(S|zi):=P{Zn+i∈S|Zi=zi}，故马尔可夫链特性：若给定当前状态，则马尔可夫链的将来和过去状态都是独立的。

假设给定测度空间(Z,E)上的两个测度为μ1和μ2，将测度μ1和μ2的全变差定义为：

2 基于选择性抽样的增量学习算法

基于选择性抽样的SVM增量学习算法中利用马氏抽样选取增量样本集，马氏抽样通过定义每一次抽样的转移概率来选择样本数据，构建出具有马尔可夫性质的样本集。记DTR为训练集，DTE为测试集，T为增量学习次数，N为每次增量样本的大小，损失函数[13]定义为l(f,z)=(1-f(x)y)+。基于选择性抽样的SVM增量学习算法步骤如下:

算法1：SVM增量学习算法

输入：DTR，DTE，T，N，q。

4)令k=2。

5)令u=1。

8)若P=1,y*yu=-1或P<1,则依转移概率P接受样本z*；若P=1、y*yu=1则依转移概率P′=min{1,e-y*fk-1/e-yufk-1}接受样本z*；若有连续n个候选样本z*不能被接受，此时依转移概率P″=min{1,qP}接受样本z*，如果z*不能被接受，返回步骤7)，否则令u=u+1,zu=z*。

10)若k≤T，返回步骤5)，否则，获取抽样与训练总时间，支持向量数目，并使用分类模型fT计

算在测试集DTE中错分率。

输出：错分率、支持向量个数、抽样与训练总时间

评注1：算法1利用数据子集分类模型的均值来定义起始转移概率，可以避免因初始转移概率的定义而导致算法可能会具有的较大波动性。为快速生成马氏样本集，根据文献[12]的研究，在算法1中引进了两个参数n和q，其中n为候选样本连续被拒绝的次数，q为解决当损失函数l(f,z)值较小时，在以概率接收候选样本时需要花费大量的时间而引入的常数。

3 数值实验

本章将对实验选取的数据集，实验结果，实验分析做出阐述，为让实验更具有效性与说服力，在实验中，对于同一个数据集，均在数据子集划分、增量次数、每次增量数据量完全相同的情况下进行实验。

在实验结果比较中，记“iid”为基于随机抽样的SVM增量学习算法，“Markov”为基于选择性抽样的SVM增量学习算法。

3.1 实验参数及数据集

实验选取Matlab2016a作为编程软件,在CPU为Inter(R)Core(TM)i7-7500 @2.7 GHz，RAM为8 G的环境中编程(因计算机内存限制，其中数据集Skin在CPU为Intel(R)Xeon(R) E5-1603-v4@2.8 GHz，RAM为32 G的环境中实验)。处理高维数据时映射核函数选用高斯径向基函数[14]，算法通过10倍交叉验证从候选集[-0.01,-0.1,0,1,10,100, 1000,10000]中选取正则化参数C=1000。为更好证明算法的泛化能力，实验分别选取3维至300维的二分类数据集进行算法的泛化能力研究。实验所选取的9个数据集如表1所示。

表1 9个实验数据集

3.2 与随机抽样增量学习算法对比

为让实验更具说服力，实验中对于同一个数据集分别进行三次增量实验，即T值分别取10,20,30次，且每次增量样本会依据算法步骤1划分出的数据子集规模而定义较大的值，即N值。

实验结果如表2所示，其中表的第二列为“数字/数字”,如数据集Skin中的10/8000，表示数据集Skin增量10次(10个子集)，每次增量的样本数为8000；20/5000则表示数据集Skin增量20次(20个子集)，每次增量的样本数为5000；为充分的表明基于选择性抽样的SVM增量学习算法的泛化能力，实验分别从错误分类率，支持向量个数，抽样与训练总时间三个方面对比基于选择性抽样的SVM增量学习算法和基于随机抽样的SVM增量学习算法。

由表3的实验结果可以看出，基于选择性抽样的SVM的增量学习算法无论在T与N取何值时错误分类率均低于基于随机抽样的SVM增量学习算法，且能在保证错分率低的同时，能大幅度减少支持向量个数和抽样与训练总时间。因为基于选择性抽样的SVM的增量学习算法中增量样本非随机选取，而是通过计算样本之间的转移概率判断是否接

表2 数值实验结果

受样本，所以通过马氏抽样选取的样本之间具有关联性，可以很大程度的避开噪声等因素对数据的影响。

为更好地展示实验效果，图1给出了基于选择性抽样的SVM的增量学习算法和基于随机抽样的SVM增量学习算法的实验数据集部分错分率详细对比图、支持向量对比图、抽样与训练总时间对比图。

从图1的(a)与(d)中可以看出，基于选择性抽样的SVM增量学习算法，在增量样本相同的情况下，随着增量次数的增加，错分率总体呈下降趋势，且错分率逐渐趋于平稳，而基于随机抽样的SVM增量学习算法，波动较大。

从图1的(b)与(e)中可以看出，无论增量次数T和增量样本量N取何值，基于选择性抽样的SVM增量学习算法比基于随机抽样SVM增量学习算法的支持向量数目要少，即分类模型更稀疏。

从图1的(c)与(f)中可以看出无论增量次数T和增量样本量N取何值，基于选择性抽样的SVM增量学习算法学习效率有很大程度的提升。

图1 实验结果详细对比图

3.3 与文献[15]中算法对比

1)算法对比：自Syed等人[7]提出增量学习算法以来，以其优异的算法性能得到了许多学者的青睐，同时很多改进的增量学习算法也相继被提出，虽然在算法性能上有一定程度的优化，但基本都是建立在样本是独立同分布的假设情形，本质并没有改变。

Xu等人[15]提出的增量学习算法，其核心也是利用马氏抽样选取样本进行增量学习(X-ISVM)。基于选择性抽样的SVM增量学习算法(M-ISVM)与之最大的区别有以下几点：

(1)X-ISVM算法在训练集上没有进行子集划分，在整体训练集进行样本选取。M-ISVM算法则是在每一个数据子集上选取样本。

(2)X-ISVM算法马氏抽样的初始转移概率是依据第一次随机抽样的分类模型定义，M-ISVM算法是通过合成2→T的数据子集的分类模型来定义马氏抽样的初始转移概率。

(3)文献[15]实验中数据集都以T=10,N=500(T=20,N=300;T=20,N=400;T=30,N=200)为基准进行增量学习，增量样本数据量选取数据量较小，不具备说服力；M-ISVM算法则是根据数据子集规模的大小来定义N的值，且N值一般定义较大。

2)数值实验与结果：为更好地比较两种算法的泛化能力，在基准数据集下，对于每一个数据集分别进行T=10,N=500(T=10N依据划分的数据子集规模定义较大值)；T=20,N=300(T=20N依据数据子集规模定义较大值)的实验,对于每个数据集实验重复5次，然后根据每次实验增量最后的分类模型求取五次实验的平均错分率，平均支持向量和5次抽样与训练的总时间(s)。

表3 T次(T=10)增量学习后实验结果对比

表4 T次(T=10)增量学习后实验结果对比

表5 T次(T=20)增量学习后实验结果对比

表6 T次(T=20)增量学习后实验结果对比

表3为在T=10,N=500时X-ISVM算法和M-ISVM算法的平均错分率、方差、平均支持向量和5次抽样与训练的总时间的实验数据；表5为在T=10N依据数据子集规模取值时X-ISVM算法和M-ISVM算法的平均错分率、方差、平均支持向量和5次抽样与训练的总时间的实验数据。

表5为在T=20,N=300时X-ISVM算法和M-ISVM算法的平均错分率、方差、平均支持向量和5次抽样与训练的总时间的实验数据；表6为在T=20N依据数据子集规模取值时X-ISVM算法和M-ISVM算法的平均错分率、方差、平均支持向量和5次抽样与训练的总时间的实验数据。

表中的第一列为“数据集名-数字”，如“Skin-500”表示从Skin数据集中每次增量500个训练样本，即算法中N=500。

从表3～6中可以看出，M-ISVM算法，在增量次数相同的情况下，增量的样本量无论大小，平均错分率，平均支持向量，抽样与训练总时间表现都优于X-ISVM算法，且方差更低，说明算法稳定性好。因为M-ISVM算法在马氏抽样起始转移概率的定义上利用了2→T的数据子集的分类模型，而X-ISVM算法只利用了第一次随机抽样的分类模型，在每次增量的数据上，M-ISVM算法分别从每一次数据子集中选取，而X-ISVM则在整体训练集中选取，所以M-ISVM算法能更好地兼顾全局性，很大程度上避免实验结果的偶然性。实验结果表明，M-ISVM算法的泛化性能优于X-ISVM算法。

4 结束语

传统的增量学习都是建立在样本是独立同分的假设情形下，样本的选取都是基于独立随机抽样，这种假设并不能完全符合实际环境中样本的分布情况。基于选择性抽样的SVM增量学习算法，通过减弱样本是独立同分布的假设情形，利用马氏抽样方式选取具有一致遍历马尔可夫链性质的样本进行增量学习，文章中与基于随机抽样的SVM增量学习算法和文献[15]提出的算法做出比较。实验结果表明，基于选择性抽样的SVM增量学习算法在SVM分类问题上泛化性能更好。