分布式機器學習的參數服務器

作者：不靠譜的貓 2018-11-07 09:23:21
服務器
分布式 許多機器學習問題依賴大量的數據進行訓練，然后進行推理。大型互聯網規(guī)模的公司用tb或pb的數據進行訓練，并從中創(chuàng)建模型。這些模型由權重組成，這些權重將優(yōu)化大多數情況下的推理誤差。權重/參數的數量以數十億至數萬億的順序排列。

創(chuàng)新互聯長期為上1000+客戶提供的網站建設服務，團隊從業(yè)經驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯網生態(tài)環(huán)境。為欽州企業(yè)提供專業(yè)的成都網站建設、成都做網站，欽州網站改版等技術服務。擁有十年豐富建站經驗和眾多成功案例,為您定制開發(fā)。

 介紹

許多機器學習問題依賴大量的數據進行訓練，然后進行推理。大型互聯網規(guī)模的公司用tb或pb的數據進行訓練，并從中創(chuàng)建模型。這些模型由權重組成，這些權重將優(yōu)化大多數情況下的推理誤差。權重/參數的數量以數十億至數萬億的順序排列。在這樣大的模型中，在一臺機器上學習和推理都是不可能的。有一個可以用于分布式學習和推理的框架是很有用的。由于參數需要在多個節(jié)點之間共享，然后使用這些節(jié)點執(zhí)行和完善它們的計算來更新它們，所以當涉及到共享時，這些大量數據可能成為瓶頸。共享在帶寬、順序機器學習(ML)算法的同步、機器的容錯性方面代價高昂，故障率高達10%。Parameter sever(https://www.cs.cmu.edu/~muli/file/parameter_server_osdi14.pdf)提出了一種新的框架來解決這些問題，并構建了分布式機器學習算法。

主要設計理念

Parameter Server提出了以下設計要求：

• 高效通信：一種異步任務模型和API，可以減少機器學習(ML)算法的整體網絡帶寬
• 靈活的一致性模型：寬松的一致性有助于降低同步成本。它還允許開發(fā)人員在算法收斂和系統(tǒng)性能之間進行選擇。
• 添加資源的彈性：允許添加更多容量而無需重新啟動整個計算。
• 高效的容錯：在高故障率和大量數據的情況下，如果機器故障不是災難性的，可以在一秒鐘左右的時間內快速恢復任務。
• 易用性：構造API以支持ML構造，例如稀疏向量，矩陣或張量。

分布式機器學習算法的示例

經典的監(jiān)督機器學習(ML)問題包括在給定標記數據的訓練集的情況下優(yōu)化成本函數。在許多樣本上改變和調整成本函數，以減少或最小化預測誤差。為了調整模型或減少誤差，計算偏導數/梯度。這些梯度有助于在正確的方向上移動權重，以最大限度地減少誤差。

對于“d”維特征向量，模型嘗試使用以下公式預測先前未見過的x的結果：for every i=1 to d, ∑xi * wi。為了確保模型相對較好地推廣(即，它僅在訓練數據上不能很好地執(zhí)行)，將正則化分量添加到預測函數。所以上面提到的函數變成Σxi* wi +?* Norm(w)。這里?用于懲罰在訓練數據上發(fā)現的權重。這削弱了學習的權重，因此避免了過度擬合，并有助于對以前看不見的數據進行泛化。本文更側重于該框架的系統(tǒng)方面。

讓我們看看分布式隨機梯度下降如何用于求解上述預測算法。下圖描繪了迭代算法并行化工作的高級過程：

分布式訓練算法

該系統(tǒng)由一些服務器節(jié)點和工作節(jié)點組成。每個worker加載一些數據子集，不同的workers加載不同的樣本。每個worker計算本地數據的梯度以優(yōu)化損失函數。然后，每個worker將這些部分梯度發(fā)送到服務器節(jié)點。服務器節(jié)點聚合從許多worker是、節(jié)點接收的那些梯度。完成服務器節(jié)點后，worker節(jié)點可以從服務器節(jié)點提取新的權重集，并再次執(zhí)行梯度計算。大多數時間花在計算g1，g2，...，gm梯度上。這些是使用轉置(X)* w計算的。如果w的數量級為數十億至數萬億，這種計算在任何單個節(jié)點上都是不可行的。但是，每個節(jié)點僅處理數據子集的良好副作用是，他們只需要相對應的權重,如數據。如果一個人試圖預測可能是用戶點擊一個廣告,然后“regularizers”等詞語不太有趣,大多數workers不會更新權重。正如你所看到的在上面的圖中,給定節(jié)點上,只有x的權重(w)的特征存在/相關的點積是必要發(fā)送給工人節(jié)點(參見x在每個工作節(jié)點和相應的列稀疏權向量w)。

在較高的層次上，算法在每個worker上看起來如下：

• 在每個worker上，計算數據子集的梯度??(偏導數)
• 將此部分梯度推送到服務器
• 在服務器準備就緒時從服務器中提取新的權重集

在每臺服務器上：

• 匯總所有'm'個worker的梯度，例如g =Σgi
• new_weights = old_weights - learning_rate *(g +?* Norm(old_weights))

架構

High level architecture

ParameterServer由服務器組組成，便于在系統(tǒng)中運行多種算法。服務器組中的每個服務器節(jié)點負責密鑰空間/數據的分區(qū)。服務器可以相互通信以遷移/復制數據，以實現可伸縮性和可用性。服務器管理器負責維護服務器組的一致視圖。它執(zhí)行活動檢查并為每個服務器節(jié)點分配密鑰空間的所有權。

通常為應用程序分配工作組。多個workers節(jié)點構成工作組，它們與服務器組通信以提取參數和推送梯度，如上一節(jié)所述。工作組不需要相互通信。調度程序查看工作組并為其分配任務。通常，相同的工作節(jié)點通過在同一數據集上運行迭代算法來利用本地存儲的數據。參數名稱空間可用于在多個工作組之間進一步并行化工作。此外，可以在多個組之間共享相同的參數命名空間：典型示例是支持實時推理的一個組，而其他工作組可以支持模型的開發(fā)和共享參數的更新。

讓我們看一下構建這種架構所需的一些原語

鍵值API

撰寫本文時，現有系統(tǒng)使用鍵值對來傳遞共享參數。一個例子是feature-id及其權重。傳統(tǒng)上，這是使用memcached或其他一些鍵值存儲實現的。重要的見解是值主要是一些線性代數基元，例如向量或矩陣，并且能夠優(yōu)化對這些構造的操作是有用的。典型的操作是點積，矩陣乘法，L-2范數等。因此，保持鍵值語義和賦值作為向量，矩陣對于優(yōu)化大多數常見的機器學習(ML)操作非常有用。

Range based push and pull

如前面算法中所述，從服務器節(jié)點和梯度中提取的權重被推送到服務器節(jié)點。支持基于Range的推送和拉取將優(yōu)化網絡帶寬使用。因此，系統(tǒng)支持w.push(R，destination)，w.pull(R，destination)來提取數據。在這兩種情況下，對應于Range R中的鍵的值被從目的節(jié)點推送和拉出。將R設置為單個鍵，提供簡單的鍵值讀寫語義。由于梯度g與w具有相同的密鑰，因此w.push(R，g，destination)可用于將局部梯度推送到目的地。

異步任務和依賴

任務可以看作是rpc。任何push或pull請求都可以是任務，也可以是正在執(zhí)行的遠程函數。任務通常是異步的，程序/應用程序可以在發(fā)出任務后繼續(xù)執(zhí)行。一旦接收到(鍵、值)對中的響應，就可以將任務標記為已完成。只有當給定任務所依賴的所有子任務返回時，才能將任務標記為已完成。任務依賴有助于實現應用程序的總體控制流。

靈活的一致性模型

從上面的模型中可以看出，任務是并行運行的，通常在遠程節(jié)點上運行。因此，在各種任務之間存在數據依賴關系的情況下，可能最終會拉出舊版本的數據。在機器學習中，有時用舊的或不太舊的權重，而不是最近的權重，并不是太有害。Parameterserver允許實現者選擇它們所追求的一致性模型。如下圖所示，支持三種類型的一致性模型。在順序一致性中，所有任務都是一個接一個地執(zhí)行。在最終的一致性中，所有的任務都是并行開始并最終聚合的。在有界延遲中，只要任何任務開始大于“t”次已經完成，任務就會啟動 - 下面的圖c顯示有界延遲為1。

一致性模型

實施細節(jié)

向量時鐘： 對于容錯和恢復，系統(tǒng)中需要一些時間戳。Parameterserver使用向量時鐘來建立系統(tǒng)中的某些事件順序?；诠?jié)點數(m)和參數數量(p)即O(m * p)，向量時鐘可能很昂貴?？紤]到系統(tǒng)中的大量參數，這可能非常大。由于大多數操作可以使用ranges完成，因此可以為每個range分配一個向量時鐘，而不是每個range獲得一個。如果系統(tǒng)中存在唯一的range，則通過該機制可以進一步降低復雜性，即O(m * r)。系統(tǒng)最初僅以m個時鐘開始，因此屬于該節(jié)點的整個密鑰空間具有一個向量時鐘。這可能會減慢恢復過程。因此，當在系統(tǒng)中創(chuàng)建更多ranges時，將更新的向量時鐘分配給這些ranges分區(qū)。

消息：系統(tǒng)中的消息表示為(VectorClock(R)，R中的所有鍵和值)。由于數據密集型機器學習(ML)應用程序中的通信量很大，因此可以通過高速緩存來減少帶寬。在迭代算法中多次傳遞相同的密鑰，因此節(jié)點可以緩存密鑰。在迭代期間，這些值也可能包含許多未更改的值，因此可以有效地壓縮。ParameterServer使用snappy compression 來有效地壓縮大量零。

一致哈希：一致哈希用于輕松添加和刪除系統(tǒng)的新節(jié)點。散列環(huán)上的每個服務器節(jié)點都負責一些密鑰空間。密鑰空間的分區(qū)和所有權由服務器管理器管理。

復制： 復制是由相鄰節(jié)點完成的。每個節(jié)點復制它的k個相鄰節(jié)點的鍵空間。負責密鑰空間的主服務器通過同步通信與neighbors保持協調，以保持副本。每當master拉key ranges時，它將被復制到它的neighbors。當worker將數據推送到服務器時，在數據復制到從服務器之前，任務不會被確認為已完成。很明顯，如果每次推和拉的時候都這樣做的話，就會變得很繁瑣。因此，系統(tǒng)還允許在聚合一定數量的數據之后進行復制。這個聚合如下圖所示。s1和s2之間只交換一條復制消息。它是在x和y都被推送到S1之后，然后是S1上的函數計算任務，然后是復制的最后一條消息，隨后確認(4,5a, 5b)流回worker1和worker2以完成任務。

聚合后復制

• 服務器節(jié)點管理： 能夠通過向系統(tǒng)添加新服務器節(jié)點進行擴展是有用的。發(fā)生這種情況時，服務器管理器會為新節(jié)點分配一個鍵空間。此鍵可以來自之前終止的某個節(jié)點，或者通過拆分負載很重的服務器節(jié)點的鍵空間。然后，這個新節(jié)點拉出它負責的密鑰空間，并從k個neighbors中抽取副本作為從屬。通常，可能需要兩階段提取來提取在被這個新節(jié)點提取時被覆蓋的數據。然后，服務器管理器將此所有權分配消息廣播到環(huán)上的其他節(jié)點，然后這些其他服務器節(jié)點可以根據此新的所有權分配縮小其密鑰空間使用量。對于離開的節(jié)點，服務器管理器將密鑰空間分配給某個新的傳入節(jié)點。服務器管理器通過心跳維護節(jié)點運行狀況。
• worler節(jié)點：添加新的工作節(jié)點相對簡單。任務調度程序將數據范圍分配給工作節(jié)點。這個新節(jié)點將從NFS或其他一些workers中提取數據。然后，調度程序將此消息廣播給其他workers，以便其他workers可以通過放棄一些訓練數據來回收一些空間。當工作節(jié)點離開時，它將由算法的所有者決定是否恢復數據 - 取決于數據的大小。

結論

本文闡述了分布式機器學習的一些重要概念。從系統(tǒng)的角度來看，本文結合使用了一些很好的技術，比如一致哈希?；诜秶耐ㄐ藕椭С窒鬟f的本機機器學習(ML)構造似乎是構建高效機器學習(ML)框架的良好洞察力。

本文題目：分布式機器學習的參數服務器
文章地址：http://fisionsoft.com.cn/article/cccgojj.html