王建飛，亢良伊，劉 杰，葉 丹

1.中國科學院 軟件研究所 軟件工程技術研發(fā)中心，北京 100190

2.中國科學院大學，北京 100190

1 介紹

在機器學習領域，機器學習問題通常轉換成一個目標函數(shù)，然后利用優(yōu)化算法求解目標函數(shù)中的參數(shù)，因此優(yōu)化算法在機器學習中具有非常重要的地位。

給定n個訓練樣本，xi表示輸入向量，yi為輸出，(x1,y1),(x2,y2),…,(xn,yn),xi∈Rd,yi∈R ，求解一個目標函數(shù)確保每個樣本對應輸出與已知輸出誤差最小。利用φ表示目標函數(shù)，目標函數(shù)表示為：

通常利用標準的梯度下降（gradient descent，GD）進行求解，更新公式如式（2）所示：

然而，每一步模型更新，需要計算所有樣本點的梯度，代價較大。一個更加高效的算法是隨機梯度下降（stochastic gradient descent，SGD）[1]，每次隨機從數(shù)據集中選擇一個樣本點it進行梯度更新，即式（3）：

隨后，針對類似的大規(guī)模分布式機器學習問題，SGD出現(xiàn)了改進的Mini-Batch[2]版本。隨機選取m個樣本進行并行或者分布式計算，(x1,y1),(x2,y2),…,(xm,ym),xi∈Rd,yi∈R ，其中 m 代表批（batch）的大小，然后使用式（4）更新模型：

理論分析和實踐經驗表明，SGD是大規(guī)模機器學習問題比較好的求解方法，具有廣泛應用。然而SGD在穩(wěn)定性方面還有所欠缺，容易受噪聲梯度的影響，在固定學習率的情況下，很難達到某一最優(yōu)解，在學習率逐漸減小的情況下，只能達到次線性的收斂速率。

針對SGD受噪聲干擾的問題，文獻[3]提出了隨機方差消減梯度算法（stochastic variance reduction gradient，SVRG），核心思想是利用全局的梯度信息對每次用于模型更新的梯度進行修正。理論分析可以證明SVRG具有線性收斂速率。因為SVRG是單機串行算法，難以應用到大數(shù)據環(huán)境。已有的分布式SVRG算法（distributed SVRG，DSVRG）[4]采用循環(huán)節(jié)點更新策略，并不是完全的并行化，SCOPE（scalable composite optimization for learning）[5]理論證明了線性收斂性，但是存在較難調優(yōu)的參數(shù)。因此，本文對原始SVRG的模型更新進行了改進，提出一種新的算法topkSVRG（top-k model average based SVRG）。其改進在于：主節(jié)點維護一個全局模型，從節(jié)點基于本地數(shù)據進行局部模型更新，每輪迭代時，選擇與當前全局模型距離最小的k個局部模型進行平均來更新全局模型，參數(shù)k調大可以提高收斂速度，調小k可以保證收斂。topkSVRG的動機也是通過選擇與全局模型最近的局部模型，來減少噪音的影響。本文理論分析了算法的線性收斂性，基于Spark進行算法實現(xiàn)，通過與Mini-Batch SGD、CoCoA、Splash及相關算法的實驗比較，topkSVRG可以在高精度要求下更快地收斂。topkSVRG魯棒性比較好，在稀疏數(shù)據集、稠密數(shù)據集上都可以取得不錯的加速效果。

本文主要貢獻有如下兩點：

（1）提出了一種新的分布式SVRG實現(xiàn)算法，通過k個最近似局部模型來更新全局模型，從而加快收斂速度，并進行了基本的理論分析。

（2）基于Spark平臺進行了算法的分布式實現(xiàn)，與Mini-Batch SGD、CoCoA、Splash，以及Mini-Batch SGD結合Adadelta、Adagrad、Adam和Momentum等算法進行了評測對比，證明了topkSVRG在高精度要求下收斂速度較快，這與原始SVRG的實驗效果一致。

本文組織結構如下：第2章介紹了主流的分布式梯度下降算法；第3章提出了topkSVRG算法，并且理論分析了該算法的線性收斂性；第4章給出了實驗評測方案和結果；第5章進行了總結和展望。

2 相關工作

梯度下降法是應用最廣泛的優(yōu)化方法，有大量相關工作，本文主要介紹三類：（1）以Mini-Batch SGD為基礎的相關優(yōu)化；（2）分布式SVRG的相關工作；（3）其他分布式SGD的重要工作。本文面向凸優(yōu)化問題，因此不介紹深度學習相關優(yōu)化算法。

分布式環(huán)境下目前主流的方法都是基于Mini-Batch的思想，Spark目前實現(xiàn)了Mini-Batch SGD算法，用于支持MLLib[2]大量模型求解，但是該算法存在收斂速度慢，穩(wěn)定性欠缺，難以確定學習率等問題[6]。于是出現(xiàn)了自適應學習率的Momentum[7]、Adagrad[8]、Adadelta[9]、Adam[10]等優(yōu)化方法，這些方法不改變Mini-Batch SGD的執(zhí)行邏輯，比較容易進行分布式實現(xiàn)。

隨機方差削減梯度（SVRG）[3]是噪聲梯度去除方法中的典型方法。這個方法的整體思路是：為了提高梯度計算的準確性，利用全局的梯度信息對每次用于模型更新的梯度進行修正。理論分析和實踐經驗表明，串行SVRG可以取得目前幾乎最好的單機收斂速度。隨后，諸多學者研究分布式模式下的SVRG方法。Jason等人提出了DSVRG[4]，證明了在數(shù)據隨機劃分的條件下，相比其他一階優(yōu)化方法，可以取得最優(yōu)的運行時間、最少的通信次數(shù)等。但是DSVRG存在如下問題：該算法是單機多線程模式，每個線程代表一個計算節(jié)點，通過節(jié)點之間相互傳遞消息，實現(xiàn)參數(shù)的更新。本質上來講，這種循環(huán)更新模式是串行的，當一個機器更新模型的時候，其他機器會存在等待的情況，不是真正意義上的分布式并行。針對該問題，Zhao等人提出了SCOPE[5]，其是對SVRG的分布式實現(xiàn)，理論證明了該方法具有線性的收斂速度，并且通過實驗表明，在很多數(shù)據集上SCOPE可以取得明顯優(yōu)于其他分布式SGD的收斂速率。但是在SCOPE中，收斂保證因子C難以確定（C的取值范圍太大），如果設置太小，會降低收斂速率，如果設置太大，可能導致不收斂。

Jaggi等人提出了CoCoA[11]，CoCoA是一種分布式坐標下降方法，該方法在梯度計算過程中會對模型進行本地更新，從而使得最后每個計算節(jié)點計算出的模型更加準確，然后進行全局的聚合操作，有效地減少了全局的通信次數(shù)。Zhang等人提出了Splash[12]。Splash的核心思想是：首先將集群中的計算單元分成K組，然后每個計算處理單元使用本地數(shù)據計算本地模型，K個組分別合并組內的模型，通過交叉驗證法選擇K組內最好的模型，從而獲得更為精準的計算結果。

3 topkSVRG算法

本章首先簡單介紹SVRG原始算法，然后介紹本文提出的topkSVRG算法。

3.1 串行SVRG

為了降低梯度噪聲，SVRG通過全局的梯度進行修正。SVRG中，每個計算節(jié)點使用式（5）、（6）進行更新：

其中，w∈Rd表示模型參數(shù)；η表示更新步長；?Rn(wt)是使用上一輪的模型wt計算出的平均梯度；?fij(wt)表示函數(shù) f在樣本點ij的梯度；?fij(wt)-?Rn(wt)是梯度的偏差是經過修正的梯度，是無偏的，使用更新模型算法偽代碼如算法1所示。

算法1SVRG(T,m,η)

從wt到wt+1需要2m+n次梯度計算，其中步驟3執(zhí)行n次，步驟7執(zhí)行2m次。因此，每輪迭代需要2m+n次梯度計算，SVRG的單次迭代代價比SGD（m次梯度計算）要大。實踐經驗表明：在大多數(shù)應用上，SVRG比SGD收斂速度更快，其具有線性收斂率[3]，尤其是需要大量數(shù)據集遍歷（epochs）的時候。此外，算法1步驟1對w1進行初始化，對于凸優(yōu)化問題，可以通過運行1輪SGD確定；對于非凸優(yōu)化問題，可以運行大約10輪SGD確定。

3.2 分布式SVRG

分布式實現(xiàn)SVRG的主要目的是每輪迭代，由多個節(jié)點通過Mini-Batch的方式來計算梯度，更新局部模型。主要難點在于主節(jié)點每輪更新模型的時候如何在有效利用每個計算節(jié)點計算結果的同時，又能保證算法的收斂性。如果直接對從節(jié)點模型進行平均可能導致不收斂；SCOPE[5]通過增加一個收斂保證因子來確定收斂性，但是參數(shù)較難確定。本文提出一種直觀的方法，主節(jié)點維護一個全局模型，從節(jié)點基于本地數(shù)據進行局部模型更新，每輪迭代時，選擇與當前全局模型距離最小的k個局部模型進行平均來更新全局模型，參數(shù)k調大可以提高收斂速度，調小k可以保證收斂。該算法的動機也是通過選擇與全局模型最近的局部模型，來減少噪音的影響。因此算法命名為topkSVRG。topkSVRG架構如圖1。

算法偽代碼如算法2所示。topkSVRG主要包括4階段：

（1）計算平均梯度，采用Spark實現(xiàn)分布式計算，如步驟3所示；

（2）多個計算節(jié)點并行地按照串行SVRG的模型更新策略更新模型，如步驟4～步驟11所示；

Fig.1 Framework of topkSVRG圖1 topkSVRG架構圖

（4）平均這k個模型,從而獲得最終的模型wt+1，如步驟16所示。

算法2分布式SVRG(T,K,k,h,r,η)

3.3 算法實現(xiàn)

本文提出的topkSVRG基于整體同步并行計算模型（bulk synchronization parallel computing model，BSP）[13]，適合目前主流的Spark平臺。通過Spark RDD[14]（resilient distributed datasets）操作，可以方便高效地實現(xiàn)上面的每一個過程，具體說明如下：

（1）通過Spark RDD的map、aggregate操作實現(xiàn)平均梯度的計算。

（2）通過Spark RDD的mapPartition操作實現(xiàn)各個計算節(jié)點的并行計算。

（3）主節(jié)點通過Spark RDD的takeOrdered操作獲取k個與上一輪模型最接近的模型。

（4）主節(jié)點通過Spark RDD的average操作對k個模型進行平均。

具體實現(xiàn)參見實驗部分所示地址http://github.com/codlife/Ssgd。

3.4 算法收斂性分析

本文提出一種“top k最鄰近模型平均策略”，即主節(jié)點聚合每個計算節(jié)點模型的時候，選取k個與當前模型最接近的模型，對這k個模型進行平均。該策略是算法收斂性證明的關鍵。算法收斂性分析如下：單機串行SVRG每一輪迭代有式（7）成立。其中L為常數(shù),w*是模型的最優(yōu)解，因此串行SVRG具有線性收斂速度[6]。

本文提出的topkSVRG中每個計算節(jié)點同樣有式（8）成立。其中 p表示第p個計算節(jié)點，K表示節(jié)點個數(shù)。

假設各個wpt都比較接近，通過平行四邊形法則可以證明，對于任意兩個 wpt、wit、wjt有式（9）、（10）成立：

由式（8）可以得到式（11）成立：

由式（9）、（10）、（11）可以得到式（12）成立：

式（12）表明：當每個計算節(jié)點的計算結果wpt比較接近的時候，直接對模型進行平均可以獲得和單機串行SVRG相同的線性收斂速率。

關于參數(shù)k，在初始數(shù)據隨機劃分的情況下，將k設置為計算節(jié)點的個數(shù)能夠取得較快的收斂速度；通過縮小k，可以保證收斂。通常建議將k設置為Round（0.9×K）、Round（0.8×K）、Round（0.6×K）、Round（0.5×K）（Round為下取整操作）等幾個常見的值。

4 實驗評測

針對求解L2正則化的邏輯回歸（logistic regression，LR）[15]的場景，對本文提出的方法和一些實驗基準（Baseline）進行評測。目標函數(shù)如下所示：

Table 1 Dataset表1 數(shù)據集

其中，學習率η設置為（t是迭代輪數(shù)）；采樣因子r設置為0.1；計算節(jié)點內循環(huán)次數(shù)h設置為1 000。

對于參數(shù)設置：本文的實驗超參數(shù)λ設置為10-4；參數(shù)k，實驗1、實驗3數(shù)據集都是稀疏數(shù)據集，k設置為Round（0.8×K），實驗2數(shù)據集是稠密數(shù)據集，k設置為Round（0.9×K），實驗4測試數(shù)據集較多，k設置為Round（0.8×K），以獲得一個比較穩(wěn)定的收斂過程。

4.1 數(shù)據集

本文使用多個數(shù)據集進行測評，從LibSVM網站獲取，選取具有代表性的數(shù)據集，實驗數(shù)據集如表1所示。

4.2 實驗環(huán)境和實驗基準

使用具有10個節(jié)點的Spark集群，Spark采用2.0版本。集群配置如表2所示。

Table 2 Machine configuration表2 機器配置

實現(xiàn)了本文提出的topkSVRG和工業(yè)界廣泛使用的Mini-Batch SGD、Mini-Batch SGD with Adadelta、Adagrad、Adam、Momentum。同時將上述算法和CoCoA、Splash等算法進行對比。

4.3 實驗結果

實驗結果如圖2～圖4所示，圖中的縱軸為對模型精度取對數(shù)lg。

實驗1基于Rcv1數(shù)據集（高維，稀疏，N>>d），實驗結果如圖2。通過該實驗可以發(fā)現(xiàn)，在高維稀疏樣本數(shù)遠遠大于特征維數(shù)的數(shù)據集上有以下特點：

Fig.2 Experiment on Rcv1 dataset圖2 數(shù)據集Rcv1上的實驗

（1）topkSVRG收斂速率相比其他分布式SGD加速明顯，并且可以達到較高的收斂精度。這是由于在稀疏數(shù)據集上，其他分布式SGD更易受梯度噪聲的影響。

（2）Spark Mini-Batch SGD穩(wěn)定性欠缺。

實驗2基于Susy數(shù)據集（低維，稠密，N>>d），實驗結果如圖3。通過該實驗可以發(fā)現(xiàn)，在低維稠密樣本數(shù)遠遠多于特征維數(shù)的數(shù)據集上有以下特點：

Fig.3 Experiment on Susy dataset圖3 數(shù)據集Susy上的實驗

Table 3 AUC on many datasets within 100 iterations表3 在大量數(shù)據集上100輪迭代時的AUC

（1）topkSVRG收斂速率略優(yōu)于Spark Mini-Batch SGD，加速相對較差。

（2）Spark Mini-Batch SGD穩(wěn)定性欠缺，并且收斂速度較慢。

（3）CoCoA、Splash等算法很難達到較高的精度。

實驗3基于Real-sim數(shù)據集（低維，稀疏，N>d），實驗結果如圖4。通過該實驗可以發(fā)現(xiàn)，在低維稀疏樣本數(shù)多于特征維數(shù)的數(shù)據集上有以下特點：

（1）topkSVRG收斂速率相比Spark Mini-Batch SGD加速明顯，尤其是在高精度范圍內。

（2）Spark Mini-Batch SGD穩(wěn)定性欠缺，收斂速度較慢。

（3）CoCoA、Splash等算法很難達到較高精度。

Fig.4 Experiment on Real-sim dataset圖4 數(shù)據集Real-sim上的實驗

實驗4將本文提出的topkSVRG和Spark Mini-Batch SGD with Adadelta/Adagrad/Adam/Momentum等在不同數(shù)據集上迭代100輪時的AUC值進行對比，結果如表3所示。可以發(fā)現(xiàn)，在各種類型數(shù)據集上，相同迭代次數(shù)，topkSVRG性能最穩(wěn)定。

4.4 實驗總結

通過實驗1～實驗3可以發(fā)現(xiàn)分布式SVRG相比Spark Mini-Batch SGD結合Adadelta、Adagrad、Adam和Momentum等算法，以及CoCoA、Splash等算法在較高收斂精度要求下，收斂加速效果明顯。通過實驗4可以發(fā)現(xiàn)topkSVRG是一個相對穩(wěn)定的算法，模型準確率相對較高。

5 結束語

采用top-k局部模型平均來更新全局模型的思想，本文設計實現(xiàn)了分布式SVRG算法topkSVRG，用于求解大規(guī)模分布式機器學習最優(yōu)化問題；基于Spark平臺進行實現(xiàn)，并理論分析了topkSVRG的線性收斂性；實驗表明topkSVRG優(yōu)于目前Spark支持的Mini-Batch SGD算法，尤其是在高精度范圍內可以取得明顯的加速效果。此外，topkSVRG魯棒性比較好,在稀疏數(shù)據集、稠密數(shù)據集上都可以取得不錯的加速效果。

對于訓練樣本小于特征維數(shù)的情況(N≤d)，topkSVRG還存在一些不足，相比Spark Mini-Batch沒有太大優(yōu)勢。下一步針對樣本數(shù)少于特征維數(shù)的情況進行算法優(yōu)化，并進一步完善理論證明。此外，將topkSVRG應用于深度學習場景并進行優(yōu)化。