魯淑霞，周 謐，金 釗

河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室，河北 保定 071002

非均衡加權(quán)隨機(jī)梯度下降SVM在線算法*

魯淑霞+，周 謐，金 釗

河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室，河北 保定 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)

隨機(jī)梯度下降（stochastic gradient descent，SGD）方法已被應(yīng)用于大規(guī)模支持向量機(jī)（support vector machine，SVM）訓(xùn)練，其在訓(xùn)練時(shí)采取隨機(jī)選點(diǎn)的方式，對(duì)于非均衡分類問(wèn)題，導(dǎo)致多數(shù)類點(diǎn)被抽取到的概率要遠(yuǎn)遠(yuǎn)大于少數(shù)類點(diǎn)，造成了計(jì)算上的不平衡。為了處理大規(guī)模非均衡數(shù)據(jù)分類問(wèn)題，提出了加權(quán)隨機(jī)梯度下降的SVM在線算法，對(duì)于多數(shù)類中的樣例被賦予較小的權(quán)值，而少數(shù)類中的樣例被賦予較大的權(quán)值，然后利用加權(quán)隨機(jī)梯度下降算法對(duì)SVM原問(wèn)題進(jìn)行求解，減少了超平面向少數(shù)類的偏移，較好地解決了大規(guī)模學(xué)習(xí)中非均衡數(shù)據(jù)的分類問(wèn)題。

隨機(jī)梯度下降（SGD）；權(quán)；非均衡數(shù)據(jù)；大規(guī)模學(xué)習(xí)；支持向量機(jī)（SVM）

1 引言

近些年，相繼有人提出了基于隨機(jī)梯度下降（stochastic gradient descent，SGD）的支持向量機(jī)（support vector machine，SVM）算法。Bottou[1]和Zhang[2]提出了一種在線訓(xùn)練SVM的方法，這一方法基于SGD，并且能夠?qū)Υ笠?guī)模數(shù)據(jù)進(jìn)行分類，同時(shí)有著很快的收斂性以及很小的物理存儲(chǔ)空間需求；Shalev-Shwartz等人[3]提出了著名的Pegasos算法，這一算法運(yùn)用了隨機(jī)梯度下降方法，其原理決定了它在訓(xùn)練時(shí)必須在每一次迭代中對(duì)整個(gè)訓(xùn)練集進(jìn)行檢索，因此注定這一算法只局限于非在線情況；Bordes[4-5]和Byrd[6]等人則嘗試應(yīng)用擬牛頓法對(duì)傳統(tǒng)的SGD進(jìn)行改進(jìn)，從而使收斂率得到提升；Polyak和Juditsky[7]提出了一種平均隨機(jī)梯度下降（averaged stochastic gradient descent，ASGD）方法，這一方法能夠得出精準(zhǔn)的漸近線；Sopyla等人[8]提出了一種帶有BB更新步驟的SGD方法，通過(guò)采用不同的步長(zhǎng)計(jì)算方式從而提高精度。雖然核化能夠繼續(xù)解決復(fù)雜的非線性問(wèn)題，但同時(shí)它也面臨著繁重的計(jì)算負(fù)擔(dān)。主要原因是支持向量的數(shù)量會(huì)隨著訓(xùn)練樣例數(shù)量的增長(zhǎng)而增長(zhǎng)。除了超出物理存儲(chǔ)容量的危險(xiǎn)以外，這也意味著隨著數(shù)據(jù)規(guī)模的變大，模型更新和預(yù)測(cè)時(shí)間都會(huì)發(fā)生線性增長(zhǎng)。這種核在線算法的特性人們稱之為“核化的詛咒”。Wang等人[9]提出了一種打破“核詛咒”的編入預(yù)算的SGD算法，通過(guò)控制訓(xùn)練中產(chǎn)生的支持向量數(shù)量來(lái)控制計(jì)算規(guī)模，不過(guò)隨之犧牲的是支持向量的數(shù)量和精度，這一算法是一種在線算法。

近期提出了適合不同問(wèn)題的各種SGD算法[10-15]，如文獻(xiàn)[10]針對(duì)大規(guī)模支持向量機(jī)的兩階段隨機(jī)梯度方法，文獻(xiàn)[11]基于隨機(jī)梯度和極速學(xué)習(xí)機(jī)的穩(wěn)定在線算法，文獻(xiàn)[12-13]隨機(jī)對(duì)偶坐標(biāo)上升方法以及對(duì)應(yīng)的加速近似方法，文獻(xiàn)[14]基于采樣技術(shù)的隨機(jī)梯度下降擴(kuò)展性算法，文獻(xiàn)[15]隨機(jī)強(qiáng)凸優(yōu)化問(wèn)題的優(yōu)化算法。

上述算法無(wú)論是線性亦或是非線性，它們都只適用于均衡數(shù)據(jù)集，當(dāng)面對(duì)非均衡數(shù)據(jù)集時(shí)卻顯得束手無(wú)策。

隨機(jī)梯度下降方法對(duì)于樣例點(diǎn)的選取是隨機(jī)的，對(duì)于非均衡數(shù)據(jù)，從概率意義上講，在一定次數(shù)的迭代訓(xùn)練下，多數(shù)類中的樣例被選到的次數(shù)要遠(yuǎn)遠(yuǎn)大于少數(shù)類中的樣例，這就導(dǎo)致多數(shù)類的點(diǎn)對(duì)于分劃超平面的訓(xùn)練所起到的作用要遠(yuǎn)大于少數(shù)類的點(diǎn)，因此訓(xùn)練結(jié)束往往只能保證多數(shù)類點(diǎn)被正確劃分。從多次實(shí)驗(yàn)的測(cè)試結(jié)果來(lái)看，最終則體現(xiàn)為測(cè)試集中幾乎所有的多數(shù)類點(diǎn)被正確劃分，少數(shù)類點(diǎn)由于“被考慮”得少，因而大部分被分錯(cuò)。雖然數(shù)值上測(cè)試精度會(huì)很高，但對(duì)于實(shí)際沒(méi)有太大意義，因?yàn)檎w的幾何均值精度很低。這一結(jié)果實(shí)際上是由于每一次迭代訓(xùn)練過(guò)程中在計(jì)算上的不平等造成的，即多數(shù)類“被考慮”得多，少數(shù)類“被考慮”得少。

為了解決大規(guī)模非均衡數(shù)據(jù)分類問(wèn)題，本文提出了一種SVM的加權(quán)隨機(jī)梯度下降算法，在SVM優(yōu)化問(wèn)題的損失函數(shù)前加一個(gè)權(quán)值系數(shù)來(lái)控制超平面的偏移。依據(jù)每類數(shù)據(jù)中樣例個(gè)數(shù)的多少對(duì)數(shù)據(jù)進(jìn)行加權(quán)，多數(shù)類中的樣例被賦予較小的權(quán)值，而少數(shù)類中的樣例被賦予較大的權(quán)值，然后利用加權(quán)隨機(jī)梯度下降算法對(duì)SVM原問(wèn)題進(jìn)行求解，減少了超平面向少數(shù)類的偏移，較好地解決了大規(guī)模學(xué)習(xí)中非均衡數(shù)據(jù)的分類問(wèn)題。

本文研究加權(quán)隨機(jī)梯度下降算法對(duì)大規(guī)模非均衡數(shù)據(jù)進(jìn)行分類的方法。第2章簡(jiǎn)述隨機(jī)梯度下降方法；第3章介紹基于隨機(jī)梯度下降的在線算法，即線性SGD（linear stochastic gradient descent，LSGD）以及帶核的 SGD（kernelized stochastic gradient descent，KSGD）；第4章提出加權(quán)的SGD算法，即加權(quán)線性SGD（weighted linear stochastic gradient descent，WLSGD）和加權(quán)帶核的SGD（weighted kernelized stochastic gradient descent，WKSGD）；第5章給出實(shí)驗(yàn)結(jié)果，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析；第6章總結(jié)全文。

2 隨機(jī)梯度下降算法

2.1 SVM優(yōu)化問(wèn)題

在兩類分類問(wèn)題中，分類的質(zhì)量是通過(guò)損失函數(shù)來(lái)度量的，分類問(wèn)題的主要目的是找到能夠使期望風(fēng)險(xiǎn)最小的估計(jì)。這里對(duì)（1）形式下的經(jīng)驗(yàn)風(fēng)險(xiǎn)進(jìn)行最小化用以代替期望風(fēng)險(xiǎn)。給定訓(xùn)練集T={(x1,y1),(x2,y2),…,(xN,yN)} ∈(Rd×Y)N,其中xi∈Rd,yi∈{1,-1},i=1,2,…,N。優(yōu)化問(wèn)題為：

使得原問(wèn)題達(dá)到最小值的解w*就是分劃超平面w*x+b=0中的w*。本文采用無(wú)偏估計(jì)，即偏置項(xiàng)b=0,λ＞0是正則化參數(shù)，這一參數(shù)控制著正則化項(xiàng)的強(qiáng)度，并對(duì)最終SGD的收斂性和精確性有著重要的影響。這里的損失函數(shù)取鉸鏈損失：

2.2 梯度下降

設(shè)t為迭代次數(shù)，為步長(zhǎng)（又稱學(xué)習(xí)率）。梯度下降算法的核心迭代公式為：

從式（3）中可以看出，對(duì)于每一次迭代，所有的梯度值?p(w)都需要計(jì)算，也就是說(shuō)需要對(duì)全部的訓(xùn)練集進(jìn)行存儲(chǔ)，這對(duì)于大規(guī)模環(huán)境來(lái)講在計(jì)算上的強(qiáng)度是非常大的。

2.3 隨機(jī)梯度下降

隨機(jī)梯度下降算法允許對(duì)原問(wèn)題進(jìn)行約簡(jiǎn)：進(jìn)而對(duì)向量w的更新步驟也同樣進(jìn)行約簡(jiǎn)。隨機(jī)梯度下降算法的核心迭代公式為：

從式（5）中可以看出，隨機(jī)梯度下降算法的每一次迭代只需從訓(xùn)練集中隨機(jī)選取一個(gè)樣例點(diǎn)(xt,yt)即可。

停機(jī)準(zhǔn)則：對(duì)于線性可分問(wèn)題，每一次迭代更新兩個(gè)量，一是迭代次數(shù)t是否達(dá)到上限tupperlimit以及更新后的wt+1值與更新前的wt值之差取范數(shù)||wt+1-wt||是否小于一個(gè)精度ε，只要兩個(gè)條件之一滿足，則立即停機(jī)（對(duì)于非線性可分問(wèn)題，只要迭代次數(shù)t達(dá)到上限tupperlimit便立即停機(jī)），此時(shí)的w就是所要求解的w*,則決策函數(shù)可表示為：

3 基于隨機(jī)梯度下降的在線算法

3.1 線性SGD

由式（5）得：

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

算法1 LSGD

3.2 帶核的SGD

當(dāng)考慮非線性可分問(wèn)題時(shí)，用某種映射φ:X=φ(x)將原空間的點(diǎn)映射到特征空間，使其呈線性分布，進(jìn)而就可以用SGD的思想求解特征空間中的w*。由式（7）可以看到，每一步迭代都含有φ(xt)，而φ未知，因此每一步的w不可算，從而不能選用||wt+1-wt||＜ε作為停機(jī)準(zhǔn)則。這里選用迭代次數(shù)t達(dá)到上限，即停機(jī)，那么第t次迭代所對(duì)應(yīng)的w就是特征空間中的解w*。于是要尋求一種規(guī)律，將任意次迭代對(duì)應(yīng)的w，即wt表達(dá)出來(lái)。由式（7）便有：

這里取w的初始值w1=0,為步長(zhǎng)，則，因而有上述推導(dǎo)過(guò)程。

這里∑中的Xj為支持向量，把滿足＜1的點(diǎn)稱作支持向量。因此KSGD算法相當(dāng)于在t次迭代中收集支持向量，即在每一次迭代中計(jì)算式（8）的值并與1比較（當(dāng)?shù)螖?shù)達(dá)到上限時(shí)，wt+1與wt已經(jīng)很接近了，因此任意次迭代下有

從而判斷該次隨機(jī)得到的點(diǎn)是否是支持向量。引入Gauss徑向基函數(shù)：K(x,x′)=exp(-||x-x′||2/σ2)，從而使得每一步的(xt)yt變得可算。

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

算法2 KSGD

支持向量集齊后便可得到最終的決策函數(shù)：

4 加權(quán)隨機(jī)梯度下降SVM在線算法

4.1 加權(quán)線性SGD

為了解決大規(guī)模非均衡數(shù)據(jù)分類問(wèn)題，本文提出了一種SVM的加權(quán)隨機(jī)梯度下降算法，在SVM優(yōu)化問(wèn)題的損失函數(shù)前加一個(gè)權(quán)值系數(shù)來(lái)控制超平面的偏移。優(yōu)化問(wèn)題為：

其中，ρt是權(quán)值系數(shù)，故由式（5）得：

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

算法3 WLSGD

4.2 加權(quán)帶核的SGD

根據(jù)式（11）及KSGD中關(guān)于wt+1的推導(dǎo)過(guò)程，很容易得出WKSGD中任意次迭代的wt的表達(dá)式，其中ρj是與支持向量xj相對(duì)應(yīng)的權(quán)值，則WKSGD的核心更新步驟為：

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

算法4 WKSGD

可以看出，WKSGD的核心更新步驟與KSGD的十分相近，僅是多了一個(gè)權(quán)值項(xiàng)系數(shù)，通過(guò)核函數(shù)的引入，在每一步迭代過(guò)程中(xt)yt也同樣是可算的。

注意：WKSGD不同于KSGD的地方是，WKSGD除了需要建立一個(gè)儲(chǔ)存支持向量的集合外，還需要建立一個(gè)與支持向量一一對(duì)應(yīng)的儲(chǔ)存權(quán)值的集合，即每次判斷隨機(jī)得到的點(diǎn)是否是支持向量，如果是，則把該點(diǎn)裝入SV集合，同時(shí)計(jì)算該支持向量對(duì)應(yīng)的權(quán)值，并將其權(quán)值存入權(quán)值集合。

5 實(shí)驗(yàn)

5.1 數(shù)據(jù)集

實(shí)驗(yàn)部分選取6個(gè)數(shù)據(jù)集來(lái)對(duì)4種算法進(jìn)行測(cè)試，分別為 Mnist、Ijcnn、Shuttle、Letter、Usps、Adult。6個(gè)數(shù)據(jù)集各有特點(diǎn)，其中Mnist、Shuttle、Letter、Usps為多類數(shù)據(jù)集，通過(guò)預(yù)處理將其中一種取值的標(biāo)簽歸為正類，其余取值的標(biāo)簽歸為負(fù)類，即把多類的數(shù)據(jù)人為地分成兩類，從而構(gòu)成不均衡數(shù)據(jù)集。Ijcnn和Adult本身帶有不均衡性，其中Adult數(shù)據(jù)集通過(guò)人為隨機(jī)刪除正類樣本點(diǎn)來(lái)獲得不均衡性，少數(shù)類與多數(shù)類的比值接近1∶100。表1給出了這6個(gè)數(shù)據(jù)集的詳細(xì)信息，在測(cè)試集中還給出了正類、負(fù)類點(diǎn)的個(gè)數(shù)，以便更直觀地體現(xiàn)數(shù)據(jù)的不均衡性。

Table 1 Introduction to data set表1 數(shù)據(jù)集介紹

5.2 算法

本文對(duì)4種算法LSGD、WLSGD、KSGD、WKSGD在每一個(gè)數(shù)據(jù)集上進(jìn)行比較，由于存在隨機(jī)性，同一算法采用固定參數(shù)值對(duì)同一數(shù)據(jù)集進(jìn)行30次實(shí)驗(yàn)，記錄它們的訓(xùn)練時(shí)間、測(cè)試時(shí)間和幾何均值精度。這里由于多類點(diǎn)數(shù)量上的比重大，各算法的測(cè)試精度大都很高，因此測(cè)試精度意義不大，本文不做記錄。參考文獻(xiàn)[3,8-9]中關(guān)于隨機(jī)梯度下降算法的相關(guān)實(shí)驗(yàn)中所采用的參數(shù)來(lái)對(duì)本文實(shí)驗(yàn)的參數(shù)進(jìn)行設(shè)置，由于WKSGD在損失函數(shù)前加了一個(gè)權(quán)值系數(shù)，這在計(jì)算上影響了支持向量的判定，實(shí)驗(yàn)表明，如果其與KSGD采用相同的步長(zhǎng)，則1 000次迭代中產(chǎn)生的支持向量個(gè)數(shù)往往為1 000個(gè)，與實(shí)際應(yīng)該有的200個(gè)左右這一水平相差巨大，出現(xiàn)異常。因此在實(shí)驗(yàn)前通過(guò)調(diào)整步長(zhǎng)的值，使實(shí)驗(yàn)結(jié)果達(dá)到預(yù)期精度，從而參數(shù)設(shè)置中WKSGD的步長(zhǎng)不同于KSGD，其依據(jù)不同數(shù)據(jù)集采用不同的步長(zhǎng)值。η0=1,預(yù)定的迭代個(gè)數(shù)T=106，高斯核寬度σ=1.5,正則化參數(shù)以及允許誤差參數(shù)由表2給出。

Table 2 Parameter setting表2 參數(shù)設(shè)置

5.3 實(shí)驗(yàn)環(huán)境

算法用C#語(yǔ)言編寫(xiě)，實(shí)驗(yàn)程序運(yùn)行環(huán)境為Microsoft Visual Studio 2010，計(jì)算機(jī)配置為第四代智能英特爾?酷睿TMi5-4 210U雙核處理器（1.7 GHz，睿頻可達(dá)2.7 GHz），4 GB DDR3低電壓內(nèi)存。

5.4 實(shí)驗(yàn)結(jié)果

表3給出了6個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，記錄的是訓(xùn)練時(shí)間、測(cè)試時(shí)間和幾何均值精度。其中各項(xiàng)數(shù)據(jù)均為30次實(shí)驗(yàn)的平均水平。幾何均值精度（G-mean）：

其中，TP是正類正確分類的個(gè)數(shù)；FN是預(yù)測(cè)為負(fù)類但是真實(shí)為正類的個(gè)數(shù)；TN是負(fù)類正確分類的個(gè)數(shù)；FP是預(yù)測(cè)為正類但是真實(shí)為負(fù)類的個(gè)數(shù)。

Table 3 Experimental result表3 實(shí)驗(yàn)結(jié)果

對(duì)于Mnist和Usps數(shù)據(jù)集，4種算法的表現(xiàn)都非常好，它們的平均幾何均值精度都較高，不加權(quán)的算法幾何均值精度也不差，其中帶核的算法精度普遍高于線性算法，這是由于樣本點(diǎn)的分布不完全按照線性分布。而各算法表現(xiàn)出來(lái)的精度都較高的原因不在于算法，而在于數(shù)據(jù)集本身。兩個(gè)數(shù)據(jù)集雖為非均衡，但其兩類點(diǎn)從分布上講“分得比較開(kāi)”，這使得一般算法也能對(duì)其起到較好的分類效果。這兩個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)表明，加權(quán)算法不但在精度上沒(méi)有損失反而有所提高，同時(shí)還繼承了原算法本身的高穩(wěn)定性。

對(duì)于Ijcnn和Letter數(shù)據(jù)集，從實(shí)驗(yàn)結(jié)果來(lái)看，兩種不加權(quán)的算法表現(xiàn)就沒(méi)那么樂(lè)觀。在Ijcnn上的實(shí)驗(yàn)，LSGD的幾何均值精度只維持在50%左右；KSGD則極其不穩(wěn)定，最低達(dá)26.99%，最高達(dá)63.19%，情況很差；相比之下，兩種加權(quán)算法則表現(xiàn)出較高的精度及較強(qiáng)的穩(wěn)定性，WLSGD的精度穩(wěn)定在77%左右，而WKSGD的精度則穩(wěn)定在72%上下。在Letter上的實(shí)驗(yàn)，LSGD的幾何均值精度只維持在18%～30%區(qū)間；KSGD極其不穩(wěn)定，最低達(dá)46.60%，最高達(dá)89.88%；WLSGD的精度穩(wěn)定在67%左右，而WKSGD的精度則穩(wěn)定在86%上下。在這兩個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)體現(xiàn)了加權(quán)算法對(duì)于非均衡數(shù)據(jù)處理的能力以及穩(wěn)定性方面的優(yōu)勢(shì)。

Shuttle和Adult數(shù)據(jù)集上的對(duì)比結(jié)果則顯得更加明顯。在Shuttle上的實(shí)驗(yàn)，LSGD表現(xiàn)最差，全部實(shí)驗(yàn)幾何均值精度均為0，正類點(diǎn)沒(méi)有一個(gè)分對(duì)的；KSGD最高達(dá)67.74%，最低達(dá)4.31%，可變系數(shù)太大，不具有實(shí)用性；而WLSGD的幾何均值精度也只有40%左右，這是由于數(shù)據(jù)點(diǎn)呈非線性分布，這樣線性算法就顯得很不適應(yīng)，因此精度表現(xiàn)較差；表現(xiàn)最為突出的是WKSGD，精度穩(wěn)定在88%上下，最低為82.39%，最高可達(dá)94.54%，具有很高的精度水平和穩(wěn)定性。Adult是6個(gè)數(shù)據(jù)集中最不均衡的，通過(guò)人為隨機(jī)刪除少數(shù)類樣本點(diǎn)來(lái)構(gòu)造非均衡，使得正類與負(fù)類的比值接近1∶100。在這樣一種數(shù)據(jù)集上，LSGD表現(xiàn)同樣最差，全部實(shí)驗(yàn)幾何均值精度均為0，正類點(diǎn)沒(méi)有一個(gè)分對(duì)；KSGD的精度時(shí)而為0，時(shí)而為9%，時(shí)而為24%，精度極低且不穩(wěn)定；WLSGD的精度穩(wěn)定在76%左右；WKSGD的精度則穩(wěn)定在73%左右。在這兩個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)，加權(quán)算法與不加權(quán)算法所體現(xiàn)出來(lái)的巨大差距充分證明了加權(quán)算法在處理非均衡數(shù)據(jù)上具備高精度以及高穩(wěn)定性的優(yōu)勢(shì)。

以上分析表明，WKSGD算法在處理線性、非線性、均衡、非均衡數(shù)據(jù)時(shí)，都具有良好的性能，不但具有非常廣的適用性，同時(shí)具備較好的穩(wěn)定性以及良好的精度。

在每個(gè)數(shù)據(jù)集上每種算法進(jìn)行了30次測(cè)試，取其中5次測(cè)試的實(shí)驗(yàn)結(jié)果，圖1～圖6直觀地反映了6個(gè)數(shù)據(jù)集上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算法中λ、支持向量個(gè)數(shù)、精度之間的關(guān)系

此外，在對(duì)WKSGD算法的測(cè)試過(guò)程中，由于實(shí)驗(yàn)初期無(wú)法確定合適的參數(shù)取值，因而初期的精度都很低，通過(guò)不斷嘗試調(diào)整各參數(shù)的值，在固定迭代次數(shù)下，正則化參數(shù)λ控制著支持向量的個(gè)數(shù)，進(jìn)而影響算法最終的幾何均值精度。λ的值取得越小，支持向量的個(gè)數(shù)就越少，最終趨于一個(gè)固定的范圍，而精度隨著這一過(guò)程會(huì)不斷提高。當(dāng)然，在參數(shù)值確定的情況下，迭代次數(shù)越多，產(chǎn)生的支持向量個(gè)數(shù)就越多。

以Shuttle數(shù)據(jù)集的實(shí)驗(yàn)為例，表4給出了不同參數(shù)λ對(duì)應(yīng)的支持向量個(gè)數(shù)和精度。

為表現(xiàn)得更直觀，圖7給出1/λ與支持向量個(gè)數(shù)的關(guān)系曲線。

從圖7中可以看出，隨著λ的減小，支持向量的數(shù)量也不斷減少，最終趨于穩(wěn)定。而λ與精度的關(guān)系有待進(jìn)一步研究。

6 結(jié)束語(yǔ)

本文首先給出了一種收集支持向量的帶核SGD方法（KSGD），這種形式?jīng)Q定了它是一種快速高效的在線算法，其有別于傳統(tǒng)的Pegasos算法以及其他基于SGD帶核的方法，是一種基于SGD運(yùn)用核函數(shù)以及支持向量形式的方法。為了處理大規(guī)模非均衡數(shù)據(jù)分類問(wèn)題，提出了兩種加權(quán)隨機(jī)梯度下降的SVM在線算法（WLSGD和WKSGD），利用加權(quán)隨機(jī)梯度下降算法對(duì)SVM原問(wèn)題進(jìn)行求解，減少了超平面向少數(shù)類的偏移。實(shí)驗(yàn)結(jié)果驗(yàn)證了加權(quán)隨機(jī)梯度下降算法能夠有效地解決大規(guī)模學(xué)習(xí)中非均衡數(shù)據(jù)的分類問(wèn)題。

Table 4 Relationship betweenλ,number of support vectors and accuracy表4λ、支持向量個(gè)數(shù)、精度之間的關(guān)系

Fig.7 Relationship between1/λand number of support vectors圖7 1/λ與支持向量個(gè)數(shù)關(guān)系圖

對(duì)于KSGD和WKSGD，不同的正則化系數(shù)λ影響著固定迭代次數(shù)下支持向量的個(gè)數(shù)，從而直接影響到算法的精度。而迭代次數(shù)的設(shè)置，由于算法存在隨機(jī)性，適當(dāng)?shù)卦黾拥螖?shù)也會(huì)在一定程度上影響精度。這些可變因素都對(duì)算法最終的表現(xiàn)起著不容忽視的作用，因此接下來(lái)的工作需要進(jìn)一步研究參數(shù)值與算法精度的關(guān)系，找到能夠快速匹配任意數(shù)據(jù)集的參數(shù)方法。

[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(河北省自然科學(xué)基金).

Received 2016-09,Accepted 2016-12.

CNKI網(wǎng)絡(luò)優(yōu)先出版: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—），博士，河北大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院教授、碩士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，計(jì)算智能，支持向量機(jī)。

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—），河北大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)橹С窒蛄繖C(jī)，機(jī)器學(xué)習(xí)。

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—），河北大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)橹С窒蛄繖C(jī)，機(jī)器學(xué)習(xí)。