分散式機器學習系統筆記(一)——模型並行,資料並行,引數平均,ASGD

歡迎轉載,轉載請註明:本文出自Bin的專欄blog.csdn.net/xbinworld。
技術交流QQ群:433250724,歡迎對演算法、技術、應用感興趣的同學加入。
文章索引::”機器學習方法“,”深度學習方法”,“三十分鐘理解”原創系列


2017年3 月,谷歌大腦負責人 Jeff Dean 在 UCSB 做了一場題為《通過大規模深度學習構建智慧系統》的演講[9]。Jeff Dean 在演講中提到,當前的做法是:

解決方案 = 機器學習(演算法) 資料 計算力

未來有沒有可能變為:

解決方案 = 資料 100 倍的計算力?

由此可見,谷歌似乎認為,機器學習演算法能被超強的計算力取代[9]。
這裡寫圖片描述

[11]研究工作表明,任務表現與訓練資料數量級呈線性增長關係。或許最令人震驚的發現是視覺任務的表現和用於表徵學習的訓練資料量級(對數尺度)之間的關係竟然是線性的!即使擁有 300M 的大規模訓練影象,我們也並未觀察到訓練資料對所研究任務產生任何平頂效應(plateauing effect)。

這裡寫圖片描述

上圖說明預訓練模型在 JFT-300M 不同子資料集中的目標檢測效能。其中 x 軸代表資料集的大小,y 軸代表在 [email protected][.5,.95] 中 COCO-minival 子資料集上的檢測效能。

要完成超大規模資料的訓練,以及訓練超大規模的神經網路,靠單GPU是行不通的(至少目前來看),必須要有分散式機器學習系統的支撐,本文以及接下來幾篇部落格,會記錄一下前面幾年比較經典的分散式機器學習系統的學習筆記,文中資料都參考了public的paper或者網上資料,我會自己整理一下,並標明出處。作為第一篇,先總體地介紹一個全貌的基本概念。

並行模型

  • 模型並行( model parallelism ):分散式系統中的不同機器(GPU/CPU等)負責網路模型的不同部分 —— 例如,神經網路模型的不同網路層被分配到不同的機器,或者同一層內部的不同引數被分配到不同機器;[14]
  • 資料並行( data parallelism ):不同的機器有同一個模型的多個副本,每個機器分配到不同的資料,然後將所有機器的計算結果按照某種方式合併。

這裡寫圖片描述

  • 當然,還有一類是混合並行(Hybrid parallelism),在一個叢集中,既有模型並行,又有資料並行,例如,可以在同一臺機器上採用模型並行化(在GPU之間切分模型),在機器之間採用資料並行化。

這裡寫圖片描述

資料並行

資料並行化式的分散式訓練在每個工作節點上都儲存一個模型的備份,在各臺機器上處理資料集的不同部分。資料並行化式訓練方法需要組合各個工作節點的結果,並且在節點之間同步模型引數。文獻中討論了各種方法,各種方法之間的主要區別在於:

  1. 引數平均法 vs. 更新式方法
  2. 同步方法 vs. 非同步方法
  3. 中心化同步 vs. 分散式同步

引數平均 model averaging

引數平均是最簡單的一種資料並行化。若採用引數平均法,訓練的過程如下所示:

  1. 基於模型的配置隨機初始化網路模型引數
  2. 將當前這組引數分發到各個工作節點
  3. 在每個工作節點,用資料集的一部分資料進行訓練
  4. 將各個工作節點的引數的均值作為全域性引數值
  5. 若還有訓練資料沒有參與訓練,則繼續從第二步開始

上述第二步到第四步的過程如下圖所示。在圖中,W表示神經網路模型的引數(權重值和偏置值)。下標表示引數的更新版本,需要在各個工作節點加以區分。

這裡寫圖片描述

很容易證明引數平均法的結果在數學意義上等同於用單個機器進行訓練;每個工作節點處理的資料量是相等的。(實際上如果採用momentum等技術,並不是嚴格相等的)

假設該叢集有n個工作節點,每個節點處理m個樣本,則總共是對nxm個樣本求均值。如果我們在單臺機器上處理所有nxm個樣本,學習率設定為α,權重更新的方程為:
這裡寫圖片描述
現在,假設我們把樣本分配到n個工作節點,每個節點在m個樣本上進行學習(節點1處理樣本1,……,m,節點2處理樣本m 1,……,2m,以此類推),則得到:
這裡寫圖片描述

引數平均法聽上去非常簡單,但事實上並沒有我們看上去這麼容易。

首先,我們應該如何求平均值?最簡單的辦法就是簡單地將每輪迭代之後的引數進行平均。一旦這樣實現了,我們會發現此方法在計算之外的額外開銷非常巨大;網路通訊和同步的開銷也許就能抵消額外機器帶來的效率收益。因此,引數平均法通常有一個大於1的平均週期averaging period(就每個節點的minibatch而言)。如果求均值週期太長,那麼每個節點得到的區域性引數更多樣化,求均值之後的模型效果非常差。我們的想法是N個區域性最小值的均值並不保證就是區域性最小:

這裡寫圖片描述

什麼樣的平均的週期算是過高呢?這個問題還沒有結論性的回答,和其它超引數攪和在一起之後變得更為複雜,比如學習率、minibatch的大小,和工作節點的數量。有些初步的研究結論(比如[16])建議平均的週期為每10~20個minibatch計算一次(每個工作節點)能夠取得比較好的效果。隨著平均的週期延長,模型的準確率則隨之下降。

另一類額外的複雜度則是與優化演算法相關,比如adagrad,momentum和RMSProp。這些優化方法,在神經網路的訓練過程中能夠顯著提升收斂的特性。然而,這些updater都有中間狀態(通常每個模型引數有1或2個狀態值)—— 我們也需要對這些狀態值求均值嗎?對每個節點的中間狀態求均值可以加快收斂的速度,而犧牲的代價則是兩倍(或者多倍)增加網路的傳輸資料量。有些研究在引數伺服器的層面應用類似的“updater”機制,而不僅僅在每個工作節點([17])。

非同步隨機梯度下降 Asynchronous SGD

有另一種與引數平均概念類似的方法,我們稱之為‘基於更新’的資料並行化。兩者的主要區別在於相對於在工作節點與引數伺服器之間傳遞引數,我們在這裡只傳遞更新資訊(即梯度和衝量等等)。引數的更新形式變為了:
這裡寫圖片描述

這裡寫圖片描述

當引數時同步方式更新時,引數平均法等價於基於更新的資料並行化。這個等價關係對多個平均步驟以及其它updater都成立(不僅限於標準SGD)。

當我們鬆綁同步更新的條件之後,基於更新的資料並行化方法變得更有意思了。也就是說,一旦計算得到?Wi,j,就立即將其應用於引數向量(而不是等待N ≥ 1 輪迭代),我們因此得到了非同步隨機梯度下降演算法。非同步SGD有兩個主要優勢:

首先,我們能夠增加分散式系統的資料吞吐量:工作節點能把更多的時間用於資料計算,而不是等待引數平均步驟的完成
其次,相比於同步更新的方式(每隔N步),各個節點能夠更快地從其它節點獲取資訊(引數的更新量)。
但是,這些優勢也不是沒帶來開銷。隨著引入引數向量的非同步更新,我們帶來了一個新的問題,即梯度值過時問題。梯度值過時問題也很簡單:計算梯度(更新量)需要消耗時間。當某個節點算完了梯度值並且將其與全域性引數向量合併時,全域性引數可能已經被重新整理了多次。用圖片來解釋這個問題就是如下:

這裡寫圖片描述

非同步SGD的簡單實現可能會導致非常嚴重的梯度值過時。舉個例子,Gupta et al. 2015 [18]證明了梯度值的平均過時量等於執行單元的個數。假設有N個執行單元,也就是說梯度值被用於計算全域性引數向量時,平均會延遲N個計算步驟。這會在現實場景中帶來問題:嚴重的梯度值過時會明顯減慢網路模型的收斂速度,甚至完全停止了收斂。早期的非同步SGD實現(例如Google的DistBelief系統)並沒有考慮到這些問題,因此學習的效率遠不如它原本應有狀態。

非同步隨機梯度下降方法還有多種形式的變種,但採取了各種策略來減弱梯度過時所造成的影響,同時保持叢集的高可用率。解決梯度值過時的方法包括以下幾種:

  • 基於梯度值的過時量,對每次更新?Wi,j 分別縮放λ的值
  • 採用‘軟’的同步策略soft synchronization([19])
  • 使用同步策略來限制過時量。例如,[20]提到的系統在必要時會延遲速度較快的節點,以保證最大的過時量控制在某個閾值以下。事實上一般現在採用bounded delay策略更多,見[1],給定一個t引數,要求t輪之前舊的引數更新必須全完成才能開始當前輪次的引數更新。

所有這些方法相比簡單的非同步SGD演算法都本證明能提升收斂的效能。尤其是前兩條方法效果更為顯著。soft synchronization的方法很簡單:相對於立即更新全域性引數向量,引數伺服器等待收集n個節點產生的s次更新?Wj(1 ≤ s ≤ n)。引數隨之進行更新:

這裡寫圖片描述

這裡寫圖片描述表示縮放因子。

注意,我們設定s=1並且λ(·) = 常數,就得到了簡單版的非同步SGD演算法([2]);同樣的,若設定s = n,我們得到了類似(不完全相同)同步引數平均的演算法。


後面會介紹Google DistBelief 框架,並行隨機梯度下降演算法Downpour SGD

DistBelief

先來描述Google在2012年發表在NIPS上的一個工作[2],雖然不是分散式機器學習系統的第一篇,但我相信是在近幾年來影響最為深遠的一篇,之後包括微軟等公司紛紛研究自己的分散式系統Adam[12],Parameter Server[1][3][4],petuun[13],或多或少都受其影響。

(未完待續…)

參考資料

[1] Scaling Distributed Machine Learning with the Parameter Server
[2] Large Scale Distributed Deep Networks, DistBelief, 2012
[3] Parameter Server for Distributed Machine Learning
[4] 【深度學習&分散式】Parameter Server 詳解, http://blog.csdn.net/cyh_24/article/details/50545780
[5] 【深度學習系列4】深度學習及並行化實現概述, http://djt.qq.com/article/view/1245
[6] 最近比較火的parameter server是什麼?https://www.zhihu.com/question/26998075
[7] parameter_server架構, http://blog.csdn.net/stdcoutzyx/article/details/51241868
[8] DistBelief 框架下的並行隨機梯度下降法 – Downpour SGD, http://blog.csdn.net/itplus/article/details/31831661
[9] 谷歌要構建10 億 級別的超大資料集,這樣能取代機器學習演算法嗎?http://www.sohu.com/a/156598020_323203
[10] 學界 | 超越ImageNet:谷歌內建300M影象資料集揭露精度與資料的線性增長關係, http://www.sohu.com/a/156495509_465975
[11] 2017 – Revisiting Unreasonable Effectiveness of Data in Deep Learning Era
[12] Adam:大規模分散式機器學習框架, http://blog.csdn.net/stdcoutzyx/article/details/46676515
[13] 十分鐘瞭解分散式計算:Petuum, http://www.cnblogs.com/wei-li/p/Petuum.html
[14] 分散式深度學習(I):分散式訓練神經網路模型的概述,http://geek.csdn.net/news/detail/105793
[15] 談談你對”GPU/CPU叢集下做到Data/Model Parallelism的區別”的理解?https://www.zhihu.com/question/31999064?sort=created
[16] Hang Su and Haoyu Chen. Experiments on parallel training of deep neural network using model averaging. arXiv preprint arXiv:1507.01239, 2015.
[17] Kai Chen and Qiang Huo. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering.
[18] Suyog Gupta, Wei Zhang, and Josh Milthrope. Model accuracy and runtime tradeoff in distributed deep learning. arXiv preprint arXiv:1509.04210, 2015.
[19] Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-aware async-sgd for distributed deep learning. IJCAI, 2016.
[20] Qirong Ho, James Cipar, Henggang Cui, Seunghak Lee, Jin Kyu Kim, Phillip B. Gibbons, Garth A Gibson, Greg Ganger, and Eric P Xing. More effective distributed ml via a stale synchronous parallel parameter server
[21] HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent