魯淑霞，周 謐，金 釗

河北大學 數(shù)學與信息科學學院 河北省機器學習與計算智能重點實驗室，河北 保定 071002

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

魯淑霞+，周 謐，金 釗

河北大學 數(shù)學與信息科學學院 河北省機器學習與計算智能重點實驗室，河北 保定 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）方法已被應(yīng)用于大規(guī)模支持向量機（support vector machine，SVM）訓(xùn)練，其在訓(xùn)練時采取隨機選點的方式，對于非均衡分類問題，導(dǎo)致多數(shù)類點被抽取到的概率要遠遠大于少數(shù)類點，造成了計算上的不平衡。為了處理大規(guī)模非均衡數(shù)據(jù)分類問題，提出了加權(quán)隨機梯度下降的SVM在線算法，對于多數(shù)類中的樣例被賦予較小的權(quán)值，而少數(shù)類中的樣例被賦予較大的權(quán)值，然后利用加權(quán)隨機梯度下降算法對SVM原問題進行求解，減少了超平面向少數(shù)類的偏移，較好地解決了大規(guī)模學習中非均衡數(shù)據(jù)的分類問題。

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

1 引言

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

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

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

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

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

本文研究加權(quán)隨機梯度下降算法對大規(guī)模非均衡數(shù)據(jù)進行分類的方法。第2章簡述隨機梯度下降方法；第3章介紹基于隨機梯度下降的在線算法，即線性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章給出實驗結(jié)果，并對實驗結(jié)果進行分析；第6章總結(jié)全文。

2 隨機梯度下降算法

2.1 SVM優(yōu)化問題

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

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

2.2 梯度下降

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

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

2.3 隨機梯度下降

隨機梯度下降算法允許對原問題進行約簡：進而對向量w的更新步驟也同樣進行約簡。隨機梯度下降算法的核心迭代公式為：

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

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

3 基于隨機梯度下降的在線算法

3.1 線性SGD

由式（5）得：

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

算法1 LSGD

3.2 帶核的SGD

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

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

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

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

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

算法2 KSGD

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

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

4.1 加權(quán)線性SGD

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

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

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

算法3 WLSGD

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

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

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

算法4 WKSGD

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

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

5 實驗

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

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

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

5.2 算法

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

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

5.3 實驗環(huán)境

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

5.4 實驗結(jié)果

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

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

Table 3 Experimental result表3 實驗結(jié)果

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

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

對于KSGD和WKSGD，不同的正則化系數(shù)λ影響著固定迭代次數(shù)下支持向量的個數(shù)，從而直接影響到算法的精度。而迭代次數(shù)的設(shè)置，由于算法存在隨機性，適當?shù)卦黾拥螖?shù)也會在一定程度上影響精度。這些可變因素都對算法最終的表現(xià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(河北省自然科學基金).

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—），博士，河北大學數(shù)學與信息科學學院教授、碩士生導(dǎo)師，CCF會員，主要研究領(lǐng)域為機器學習，計算智能，支持向量機。

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—），河北大學碩士研究生，主要研究領(lǐng)域為支持向量機，機器學習。

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—），河北大學碩士研究生，主要研究領(lǐng)域為支持向量機，機器學習。