非均衡加权随机梯度下降SVM在线算法*

鲁淑霞，周 谧，金 钊

河北大学 数学与信息科学学院 河北省机器学习与计算智能重点实验室，河北 保定 071002

非均衡加权随机梯度下降SVM在线算法*

鲁淑霞+，周 谧，金 钊

河北大学 数学与信息科学学院 河北省机器学习与计算智能重点实验室，河北 保定 071002

Abstract:Stochastic gradient descent(SGD)has been applied to large scale support vector machine(SVM)training.Stochastic gradient descent takes a random way to select points during training process,this leads to a result that the probability of choosing majority class is far greater than that of choosing minority class for imbalanced classification problem.In order to deal with large scale imbalanced data classification problems,this paper proposes a method named weighted stochastic gradient descent algorithm for SVM.After the samples in the majority class are assigned a smaller weight while the samples in the minority class are assigned a larger weight,the weighted stochastic gradient descent algorithm will be used to solving the primal problem of SVM,which helps to reduce the hyperplane offset to the minority class,thus solves the large scale imbalanced data classification problems.

Key words:stochastic gradient descent(SGD);weight;imbalanced data;large scale learning;support vector machine(SVM)

随机梯度下降（stochastic gradient descent，SGD）方法已被应用于大规模支持向量机（support vector machine，SVM）训练，其在训练时采取随机选点的方式，对于非均衡分类问题，导致多数类点被抽取到的概率要远远大于少数类点，造成了计算上的不平衡。为了处理大规模非均衡数据分类问题，提出了加权随机梯度下降的SVM在线算法，对于多数类中的样例被赋予较小的权值，而少数类中的样例被赋予较大的权值，然后利用加权随机梯度下降算法对SVM原问题进行求解，减少了超平面向少数类的偏移，较好地解决了大规模学习中非均衡数据的分类问题。

随机梯度下降（SGD）；权；非均衡数据；大规模学习；支持向量机（SVM）

1 引言

近些年，相继有人提出了基于随机梯度下降（stochastic gradient descent，SGD）的支持向量机（support vector machine，SVM）算法。Bottou[1]和Zhang[2]提出了一种在线训练SVM的方法，这一方法基于SGD，并且能够对大规模数据进行分类，同时有着很快的收敛性以及很小的物理存储空间需求；Shalev-Shwartz等人[3]提出了著名的Pegasos算法，这一算法运用了随机梯度下降方法，其原理决定了它在训练时必须在每一次迭代中对整个训练集进行检索，因此注定这一算法只局限于非在线情况；Bordes[4-5]和Byrd[6]等人则尝试应用拟牛顿法对传统的SGD进行改进，从而使收敛率得到提升；Polyak和Juditsky[7]提出了一种平均随机梯度下降（averaged stochastic gradient descent，ASGD）方法，这一方法能够得出精准的渐近线；Sopyla等人[8]提出了一种带有BB更新步骤的SGD方法，通过采用不同的步长计算方式从而提高精度。虽然核化能够继续解决复杂的非线性问题，但同时它也面临着繁重的计算负担。主要原因是支持向量的数量会随着训练样例数量的增长而增长。除了超出物理存储容量的危险以外，这也意味着随着数据规模的变大，模型更新和预测时间都会发生线性增长。这种核在线算法的特性人们称之为“核化的诅咒”。Wang等人[9]提出了一种打破“核诅咒”的编入预算的SGD算法，通过控制训练中产生的支持向量数量来控制计算规模，不过随之牺牲的是支持向量的数量和精度，这一算法是一种在线算法。

近期提出了适合不同问题的各种SGD算法[10-15]，如文献[10]针对大规模支持向量机的两阶段随机梯度方法，文献[11]基于随机梯度和极速学习机的稳定在线算法，文献[12-13]随机对偶坐标上升方法以及对应的加速近似方法，文献[14]基于采样技术的随机梯度下降扩展性算法，文献[15]随机强凸优化问题的优化算法。

上述算法无论是线性亦或是非线性，它们都只适用于均衡数据集，当面对非均衡数据集时却显得束手无策。

随机梯度下降方法对于样例点的选取是随机的，对于非均衡数据，从概率意义上讲，在一定次数的迭代训练下，多数类中的样例被选到的次数要远远大于少数类中的样例，这就导致多数类的点对于分划超平面的训练所起到的作用要远大于少数类的点，因此训练结束往往只能保证多数类点被正确划分。从多次实验的测试结果来看，最终则体现为测试集中几乎所有的多数类点被正确划分，少数类点由于“被考虑”得少，因而大部分被分错。虽然数值上测试精度会很高，但对于实际没有太大意义，因为整体的几何均值精度很低。这一结果实际上是由于每一次迭代训练过程中在计算上的不平等造成的，即多数类“被考虑”得多，少数类“被考虑”得少。

为了解决大规模非均衡数据分类问题，本文提出了一种SVM的加权随机梯度下降算法，在SVM优化问题的损失函数前加一个权值系数来控制超平面的偏移。依据每类数据中样例个数的多少对数据进行加权，多数类中的样例被赋予较小的权值，而少数类中的样例被赋予较大的权值，然后利用加权随机梯度下降算法对SVM原问题进行求解，减少了超平面向少数类的偏移，较好地解决了大规模学习中非均衡数据的分类问题。

本文研究加权随机梯度下降算法对大规模非均衡数据进行分类的方法。第2章简述随机梯度下降方法；第3章介绍基于随机梯度下降的在线算法，即线性SGD（linear stochastic gradient descent，LSGD）以及带核的 SGD（kernelized stochastic gradient descent，KSGD）；第4章提出加权的SGD算法，即加权线性SGD（weighted linear stochastic gradient descent，WLSGD）和加权带核的SGD（weighted kernelized stochastic gradient descent，WKSGD）；第5章给出实验结果，并对实验结果进行分析；第6章总结全文。

2 随机梯度下降算法

2.1 SVM优化问题

在两类分类问题中，分类的质量是通过损失函数来度量的，分类问题的主要目的是找到能够使期望风险最小的估计。这里对（1）形式下的经验风险进行最小化用以代替期望风险。给定训练集T={(x1,y1),(x2,y2),…,(xN,yN)} ∈(Rd×Y)N,其中xi∈Rd,yi∈{1,-1},i=1,2,…,N。优化问题为：

使得原问题达到最小值的解w*就是分划超平面w*x+b=0中的w*。本文采用无偏估计，即偏置项b=0,λ＞0是正则化参数，这一参数控制着正则化项的强度，并对最终SGD的收敛性和精确性有着重要的影响。这里的损失函数取铰链损失：

2.2 梯度下降

设t为迭代次数，为步长（又称学习率）。梯度下降算法的核心迭代公式为：

从式（3）中可以看出，对于每一次迭代，所有的梯度值∇p(w)都需要计算，也就是说需要对全部的训练集进行存储，这对于大规模环境来讲在计算上的强度是非常大的。

2.3 随机梯度下降

随机梯度下降算法允许对原问题进行约简：进而对向量w的更新步骤也同样进行约简。随机梯度下降算法的核心迭代公式为：

从式（5）中可以看出，随机梯度下降算法的每一次迭代只需从训练集中随机选取一个样例点(xt,yt)即可。

停机准则：对于线性可分问题，每一次迭代更新两个量，一是迭代次数t是否达到上限tupperlimit以及更新后的wt+1值与更新前的wt值之差取范数||wt+1-wt||是否小于一个精度ε，只要两个条件之一满足，则立即停机（对于非线性可分问题，只要迭代次数t达到上限tupperlimit便立即停机），此时的w就是所要求解的w*,则决策函数可表示为：

3 基于随机梯度下降的在线算法

3.1 线性SGD

由式（5）得：

按照式（7）核心更新步骤，LSGD算法表述如下。

算法1 LSGD

3.2 带核的SGD

当考虑非线性可分问题时，用某种映射φ:X=φ(x)将原空间的点映射到特征空间，使其呈线性分布，进而就可以用SGD的思想求解特征空间中的w*。由式（7）可以看到，每一步迭代都含有φ(xt)，而φ未知，因此每一步的w不可算，从而不能选用||wt+1-wt||＜ε作为停机准则。这里选用迭代次数t达到上限，即停机，那么第t次迭代所对应的w就是特征空间中的解w*。于是要寻求一种规律，将任意次迭代对应的w，即wt表达出来。由式（7）便有：

这里取w的初始值w1=0,为步长，则，因而有上述推导过程。

这里∑中的Xj为支持向量，把满足＜1的点称作支持向量。因此KSGD算法相当于在t次迭代中收集支持向量，即在每一次迭代中计算式（8）的值并与1比较（当迭代次数达到上限时，wt+1与wt已经很接近了，因此任意次迭代下有

从而判断该次随机得到的点是否是支持向量。引入Gauss径向基函数：K(x,x′)=exp(-||x-x′||2/σ2)，从而使得每一步的(xt)yt变得可算。

式（8）作为核心更新步骤，KSGD算法表述如下。

算法2 KSGD

支持向量集齐后便可得到最终的决策函数：

4 加权随机梯度下降SVM在线算法

4.1 加权线性SGD

为了解决大规模非均衡数据分类问题，本文提出了一种SVM的加权随机梯度下降算法，在SVM优化问题的损失函数前加一个权值系数来控制超平面的偏移。优化问题为：

其中，ρt是权值系数，故由式（5）得：

式（11）作为核心更新步骤，WLSGD算法如下。

算法3 WLSGD

4.2 加权带核的SGD

根据式（11）及KSGD中关于wt+1的推导过程，很容易得出WKSGD中任意次迭代的wt的表达式，其中ρj是与支持向量xj相对应的权值，则WKSGD的核心更新步骤为：

式（12）作为核心更新步骤，WKSGD算法如下。

算法4 WKSGD

可以看出，WKSGD的核心更新步骤与KSGD的十分相近，仅是多了一个权值项系数，通过核函数的引入，在每一步迭代过程中(xt)yt也同样是可算的。

注意：WKSGD不同于KSGD的地方是，WKSGD除了需要建立一个储存支持向量的集合外，还需要建立一个与支持向量一一对应的储存权值的集合，即每次判断随机得到的点是否是支持向量，如果是，则把该点装入SV集合，同时计算该支持向量对应的权值，并将其权值存入权值集合。

5 实验

5.1 数据集

实验部分选取6个数据集来对4种算法进行测试，分别为 Mnist、Ijcnn、Shuttle、Letter、Usps、Adult。6个数据集各有特点，其中Mnist、Shuttle、Letter、Usps为多类数据集，通过预处理将其中一种取值的标签归为正类，其余取值的标签归为负类，即把多类的数据人为地分成两类，从而构成不均衡数据集。Ijcnn和Adult本身带有不均衡性，其中Adult数据集通过人为随机删除正类样本点来获得不均衡性，少数类与多数类的比值接近1∶100。表1给出了这6个数据集的详细信息，在测试集中还给出了正类、负类点的个数，以便更直观地体现数据的不均衡性。

Table 1 Introduction to data set表1 数据集介绍

5.2 算法

本文对4种算法LSGD、WLSGD、KSGD、WKSGD在每一个数据集上进行比较，由于存在随机性，同一算法采用固定参数值对同一数据集进行30次实验，记录它们的训练时间、测试时间和几何均值精度。这里由于多类点数量上的比重大，各算法的测试精度大都很高，因此测试精度意义不大，本文不做记录。参考文献[3,8-9]中关于随机梯度下降算法的相关实验中所采用的参数来对本文实验的参数进行设置，由于WKSGD在损失函数前加了一个权值系数，这在计算上影响了支持向量的判定，实验表明，如果其与KSGD采用相同的步长，则1 000次迭代中产生的支持向量个数往往为1 000个，与实际应该有的200个左右这一水平相差巨大，出现异常。因此在实验前通过调整步长的值，使实验结果达到预期精度，从而参数设置中WKSGD的步长不同于KSGD，其依据不同数据集采用不同的步长值。η0=1,预定的迭代个数T=106，高斯核宽度σ=1.5,正则化参数以及允许误差参数由表2给出。

Table 2 Parameter setting表2 参数设置

5.3 实验环境

算法用C#语言编写，实验程序运行环境为Microsoft Visual Studio 2010，计算机配置为第四代智能英特尔®酷睿TMi5-4 210U双核处理器（1.7 GHz，睿频可达2.7 GHz），4 GB DDR3低电压内存。

5.4 实验结果

表3给出了6个数据集上的实验结果，记录的是训练时间、测试时间和几何均值精度。其中各项数据均为30次实验的平均水平。几何均值精度（G-mean）：

其中，TP是正类正确分类的个数；FN是预测为负类但是真实为正类的个数；TN是负类正确分类的个数；FP是预测为正类但是真实为负类的个数。

Table 3 Experimental result表3 实验结果

对于Mnist和Usps数据集，4种算法的表现都非常好，它们的平均几何均值精度都较高，不加权的算法几何均值精度也不差，其中带核的算法精度普遍高于线性算法，这是由于样本点的分布不完全按照线性分布。而各算法表现出来的精度都较高的原因不在于算法，而在于数据集本身。两个数据集虽为非均衡，但其两类点从分布上讲“分得比较开”，这使得一般算法也能对其起到较好的分类效果。这两个数据集上的实验表明，加权算法不但在精度上没有损失反而有所提高，同时还继承了原算法本身的高稳定性。

对于Ijcnn和Letter数据集，从实验结果来看，两种不加权的算法表现就没那么乐观。在Ijcnn上的实验，LSGD的几何均值精度只维持在50%左右；KSGD则极其不稳定，最低达26.99%，最高达63.19%，情况很差；相比之下，两种加权算法则表现出较高的精度及较强的稳定性，WLSGD的精度稳定在77%左右，而WKSGD的精度则稳定在72%上下。在Letter上的实验，LSGD的几何均值精度只维持在18%～30%区间；KSGD极其不稳定，最低达46.60%，最高达89.88%；WLSGD的精度稳定在67%左右，而WKSGD的精度则稳定在86%上下。在这两个数据集上的实验体现了加权算法对于非均衡数据处理的能力以及稳定性方面的优势。

Shuttle和Adult数据集上的对比结果则显得更加明显。在Shuttle上的实验，LSGD表现最差，全部实验几何均值精度均为0，正类点没有一个分对的；KSGD最高达67.74%，最低达4.31%，可变系数太大，不具有实用性；而WLSGD的几何均值精度也只有40%左右，这是由于数据点呈非线性分布，这样线性算法就显得很不适应，因此精度表现较差；表现最为突出的是WKSGD，精度稳定在88%上下，最低为82.39%，最高可达94.54%，具有很高的精度水平和稳定性。Adult是6个数据集中最不均衡的，通过人为随机删除少数类样本点来构造非均衡，使得正类与负类的比值接近1∶100。在这样一种数据集上，LSGD表现同样最差，全部实验几何均值精度均为0，正类点没有一个分对；KSGD的精度时而为0，时而为9%，时而为24%，精度极低且不稳定；WLSGD的精度稳定在76%左右；WKSGD的精度则稳定在73%左右。在这两个数据集上的实验，加权算法与不加权算法所体现出来的巨大差距充分证明了加权算法在处理非均衡数据上具备高精度以及高稳定性的优势。

以上分析表明，WKSGD算法在处理线性、非线性、均衡、非均衡数据时，都具有良好的性能，不但具有非常广的适用性，同时具备较好的稳定性以及良好的精度。

在每个数据集上每种算法进行了30次测试，取其中5次测试的实验结果，图1～图6直观地反映了6个数据集上4种算法精度的比较。

Fig.1 Accuracy on Mnist图1 Mnist上的精度

Fig.2 Accuracy on Ijcnn图2 Ijcnn上的精度

Fig.3 Accuracy on Shuttle图3 Shuttle上的精度

Fig.4 Accuracy on Letter图4 Letter上的精度

Fig.5 Accuracy on Usps图5 Usps上的精度

Fig.6 Accuracy onAdult图6 Adult上的精度

5.5 WKSGD算法中λ、支持向量个数、精度之间的关系

此外，在对WKSGD算法的测试过程中，由于实验初期无法确定合适的参数取值，因而初期的精度都很低，通过不断尝试调整各参数的值，在固定迭代次数下，正则化参数λ控制着支持向量的个数，进而影响算法最终的几何均值精度。λ的值取得越小，支持向量的个数就越少，最终趋于一个固定的范围，而精度随着这一过程会不断提高。当然，在参数值确定的情况下，迭代次数越多，产生的支持向量个数就越多。

以Shuttle数据集的实验为例，表4给出了不同参数λ对应的支持向量个数和精度。

为表现得更直观，图7给出1/λ与支持向量个数的关系曲线。

从图7中可以看出，随着λ的减小，支持向量的数量也不断减少，最终趋于稳定。而λ与精度的关系有待进一步研究。

6 结束语

本文首先给出了一种收集支持向量的带核SGD方法（KSGD），这种形式决定了它是一种快速高效的在线算法，其有别于传统的Pegasos算法以及其他基于SGD带核的方法，是一种基于SGD运用核函数以及支持向量形式的方法。为了处理大规模非均衡数据分类问题，提出了两种加权随机梯度下降的SVM在线算法（WLSGD和WKSGD），利用加权随机梯度下降算法对SVM原问题进行求解，减少了超平面向少数类的偏移。实验结果验证了加权随机梯度下降算法能够有效地解决大规模学习中非均衡数据的分类问题。

Table 4 Relationship betweenλ,number of support vectors and accuracy表4λ、支持向量个数、精度之间的关系

Fig.7 Relationship between1/λand number of support vectors图7 1/λ与支持向量个数关系图

对于KSGD和WKSGD，不同的正则化系数λ影响着固定迭代次数下支持向量的个数，从而直接影响到算法的精度。而迭代次数的设置，由于算法存在随机性，适当地增加迭代次数也会在一定程度上影响精度。这些可变因素都对算法最终的表现起着不容忽视的作用，因此接下来的工作需要进一步研究参数值与算法精度的关系，找到能够快速匹配任意数据集的参数方法。

[1]Bottou L.Large-scale machine learning with stochastic gradient descent[C]//Proceedings of the 19th International Conference on Computational Statistics,Paris,Aug 22-27,2010.Berlin,Heidelberg:Springer,2010:177-187.

[2]Zhang Tong.Solving large scale linear prediction problems using stochastic gradient descent algorithms[C]//Proceedings of the 21st International Conference on Machine Learning,Banff,Canada,Jul 4-8,2004.New York:ACM,2004:919-926.

[3]Shalev-Shwartz S,Singer Y,Srebro N,et al.Pegasos:primal estimated sub-gradient solver for SVM[J].Mathematical Programming,2011,127(1):3-30.

[4]Bordes A,Bottou L,Gallinari P.SGD-QN:careful Quasi-Newton stochastic gradient descent[J].Journal of Machine Learning Research,2009,10(3):1737-1754.

[5]Bordes A,Bottou L,Gallinari P,et al.Erratum:SGDQN is less careful than expected[J].Journal of Machine Learning Research,2010,11(11):2229-2240.

[6]Byrd R H,Hansen S L,Nocedal J,et al.A stochastic Quasi-Newton method for large-scale optimization[J].SIAM Journal on Optimization,2016,26(2):1008-1031.

[7]Polyak B T,JuditskyAB.Acceleration of stochastic approximation by averaging[J].SIAM Journal on Control&Optimization,1992,30(4):838-855.

[8]Sopyła K,Drozda P.Stochastic gradient descent with Barzilai-Borwein update step for SVM[J].Information Sciences,2015,316(C):218-233.

[9]Wang Zhuang,Crammer K,Vucetic S.Breaking the curse of kernelization:budgeted stochastic gradient descent for largescale SVM training[J].Journal of Machine Learning Research,2012,13(1):3103-3131.

[10]Couellan N,Wang Wenjuan.Bi-level stochastic gradient for large scale support vector machine[J].Neurocomputing,2015,153:300-308.

[11]Janakiraman V M,Nguyen X L,Assanis D,et al.Stochastic gradient based extreme learning machines for stable onlinelearning of advanced combustion engines[J].Neurocomputing,2016,177(C):304-316.

[12]Shalev-Shwartz S,Zhang Tong.Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization[J].Mathematical Programming,2016,155(1):105-145.

[13]Shalev-Shwartz S,Zhang Tong.Stochastic dual coordinate ascent methods for regularized loss minimization[J].Journal of Machine Learning Research,2013,14(1):567-599.

[14]Clémençon S,Bellet A,Jelassi O,et al.Scalability of stochastic gradient descent based on smart sampling techniques[J].Procedia Computer Science,2015,53(1):308-315.

[15]Hazan E,Kale S.Beyond the regret minimiztion barrier:optimal algorithms for stochastic strongly convex optimization[J].Journal of Machine Learning Research,2014,15(1):2489-2512.

[16]Li Kuan,Kong Xiangfei,Lu Zhi,et al.Boosting weighted ELM for imbalanced learning[J].Neurocomputing,2014,128(5):15-21.

Imbalanced Weighted Stochastic Gradient Descent OnlineAlgorithm for SVM*

LU Shuxia+,ZHOU Mi,JIN Zhao
Hebei Province Key Laboratory of Machine Learning and Computational Intelligence,College of Mathematics and Information Science,Hebei University,Baoding,Hebei 071002,China

A

TP181

+Corresponding author:E-mail:cmclusx@126.com

LU Shuxia,ZHOU Mi,JIN Zhao.Imbalanced weighted stochastic gradient descent online algorithm for SVM.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1662-1671.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1662-10

10.3778/j.issn.1673-9418.1609009

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The Natural Science Foundation of Hebei Province under Grant No.F2015201185(河北省自然科学基金).

Received 2016-09,Accepted 2016-12.

CNKI网络优先出版:2016-12-23,http://www.cnki.net/kcms/detail/11.5602.TP.20161223.1702.002.html

LU Shuxia was born in 1966.She received the Ph.D.degree in 2007.Now she is a professor and M.S.supervisor at College of Mathematics and Information Science,Hebei University,and the member of CCF.Her research interests include machine learning,computational intelligence and support vector machine.

鲁淑霞（1966—），博士，河北大学数学与信息科学学院教授、硕士生导师，CCF会员，主要研究领域为机器学习，计算智能，支持向量机。

ZHOU Mi was born in 1991.He is an M.S.candidate at Hebei University.His research interests include support vector machine and machine learning.

周谧（1991—），河北大学硕士研究生，主要研究领域为支持向量机，机器学习。

JIN Zhao was born in 1991.He is an M.S.candidate at Hebei University.His research interests include support vector machine and machine learning.

金钊（1991—），河北大学硕士研究生，主要研究领域为支持向量机，机器学习。