四. GSA算法Spark上的并行化實(shí)現(xiàn)
GSA算法是基本的優(yōu)化方法，在Spark上還需要考慮算法并行化的問題。機(jī)器學(xué)習(xí)算法的并行化有兩種方式，一種是數(shù)據(jù)并行，另一種是模型并行。但是Spark只能支持?jǐn)?shù)據(jù)并行，因?yàn)槟Ｐ筒⑿袝a(chǎn)生大量細(xì)粒度的節(jié)點(diǎn)間通信開銷，這是Spark采用的BSP同步模式無法高效處理的。
數(shù)據(jù)并行模式下進(jìn)行機(jī)器學(xué)習(xí)算法的并行化又有三種方法，分別是梯度平均，模型平均，以及結(jié)果平均。梯度平均是在各個數(shù)據(jù)分片上計算當(dāng)前的梯度更新量然后匯總平均各分片上的梯度更新量總體更新模型。模型平均是各分片訓(xùn)練自己的模型，然后再將模型匯總平均獲得一個總體的模型。而結(jié)果平均實(shí)際上就是Ensemble Learning， 在大規(guī)模問題上因?yàn)槟Ｐ鸵?guī)模的問題，并不是一個好的選擇。
實(shí)際上是目前采用得最多的是梯度平均，當(dāng)前Parameter Server各種實(shí)現(xiàn)上主要還是用來支持這種方式，Spark MLLib的算法實(shí)現(xiàn)也是采用的該方式。但是在Spark上采用梯度平均在效率上也有比較大的瓶頸，因該方法計算當(dāng)前的梯度更新量是要依賴于當(dāng)前的最新模型的，這就帶來了在各數(shù)據(jù)分片之間頻繁的模型同步開銷，這對Map Reuce計算模式的壓力是較大的。
模型平均一直被認(rèn)為其收斂性在理論上是沒有保證的，但是最近Rosenblatt[8]等人證明了模型平均的收斂性。而我們在大量的測試中，也發(fā)現(xiàn)模型平均通常能取得非常好的模型精度?？紤]到模型平均的計算模式更適合Map Reduce計算模型，我們在Fregata中對于GSA算法的并行方法采用的就是模型平均方法。模型平均的并行方法中，每個數(shù)據(jù)分片在Map階段訓(xùn)練自己的模型，最后通過Reduce操作對各個分片上的模型進(jìn)行平均，掃描一次數(shù)據(jù)僅需要做一次模型同步。而且在大量的實(shí)驗(yàn)中，該方法在掃描一次數(shù)據(jù)后，模型的精度就可達(dá)到很高的水平，基本接近于更多次迭代后的最好結(jié)果。
五. Fregata與MLLib對比
Fregata是基于Spark的機(jī)器學(xué)習(xí)算法庫，因此與Spark內(nèi)置算法庫MLLib具有很高的可比性。我們這里簡要介紹了三個數(shù)據(jù)集，兩種算法（Logistic Regression和Softmax）上的精度和訓(xùn)練時間對比。精度指標(biāo)我們采用的是測試集的AUC。對于精度和訓(xùn)練時間，算法每掃描完一次數(shù)據(jù)記錄一次。
Fregata的算法不需要調(diào)參，因此我們都只做了一次實(shí)驗(yàn)。而對于MLLib上的算法，我們在各種參數(shù)組合（包括優(yōu)化方法的選擇）中進(jìn)行了網(wǎng)格搜索，選取了測試集AUC能達(dá)到最高的那組參數(shù)作為對比結(jié)果。
Lookalike是一個基于Fregata平臺運(yùn)用比較成熟的服務(wù)，其目標(biāo)在于根據(jù)種子人群進(jìn)行人群放大以尋找潛在客戶。我們將Lookalike作為二分類問題來處理，因此可以采用Logistic Regression算法來處理。在訓(xùn)練模型時以種子人群為正樣本，其他為負(fù)樣本，通常種子人群的數(shù)量不會很多，因此Lookalike通常是正樣本比例非常少的class imblance問題。 在一個大規(guī)模數(shù)據(jù)集(4億樣本，2千萬個特征)上的Lookalike問題的模型訓(xùn)練中，我們對比了Fregata LR和MLLib LR的性能。
從圖4中可以看到Fregata的LR算法掃描一次數(shù)據(jù)即收斂達(dá)到AUC（測試集上）的最高值0.93。在這個數(shù)據(jù)樣本中 而MLLib的LR算法，即使我們通過調(diào)參選取了最好的AUC結(jié)果，其AUC也僅為0.55左右。模型預(yù)測精度差別非常大。另外，MLLib的訓(xùn)練時間（達(dá)到最高精度的時間）也是Fregata大的6倍以上。
在公開數(shù)據(jù)集eplison[9]上（40萬訓(xùn)練集，2000特征）, Fregata LR無論從收斂速度還是模型效果與MLLib LR相比也有較大的優(yōu)勢。從圖5中可以看到，在這個數(shù)據(jù)集上Fregata LR在迭代一次以后就在測試集上非常接近最好的結(jié)果了，而MLLib LR需要5次迭代而且最高的精度比Fregata LR相差很大，而訓(xùn)練時間MLLib LR也是Fregata LR的5倍以上。
另外圖6展示了Fregata LR與MLLib LR在6個不同問題上的測試集AUC曲線，可以看到Fregata LR算法在不同問題上收斂速度和穩(wěn)定性相較于MLLib LR都是有較大的優(yōu)勢。Fregata LR在第一次迭代后，AUC就已經(jīng)基本收斂，即使與最高值還有一些差距，但是也是非常接近了。
我們也在公開數(shù)據(jù)集MNIST上測試了Softmax算法。 從圖7中可以看到， Fregata Softmax也是一次掃描數(shù)據(jù)后在測試集上的AUC就非常接近最好的結(jié)果， 而MLLib Softmax需要掃描數(shù)據(jù)多達(dá)40多次以后才接近Fregata Softmax一次掃描數(shù)據(jù)的結(jié)果。對比兩個算法在達(dá)到各自最優(yōu)結(jié)果所花的時間，MLLib Softmax是Fregata Softmax的50倍以上。