介紹

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

主要設(shè)計理念

Parameter Server提出了以下設(shè)計要求：

• 高效通信：一種異步任務(wù)模型和API，可以減少機器學(xué)習(xí)(ML)算法的整體網(wǎng)絡(luò)帶寬

• 靈活的一致性模型：寬松的一致性有助于降低同步成本。它還允許開發(fā)人員在算法收斂和系統(tǒng)性能之間進行選擇。

• 添加資源的彈性：允許添加更多容量而無需重新啟動整個計算。

• 高效的容錯：在高故障率和大量數(shù)據(jù)的情況下，如果機器故障不是災(zāi)難性的，可以在一秒鐘左右的時間內(nèi)快速恢復(fù)任務(wù)。

• 易用性：構(gòu)造API以支持ML構(gòu)造，例如稀疏向量，矩陣或張量。

分布式機器學(xué)習(xí)算法的示例

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

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

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

分布式訓(xùn)練算法

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

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

• 在每個worker上，計算數(shù)據(jù)子集的梯度(偏導(dǎo)數(shù))

• 將此部分梯度推送到服務(wù)器

• 在服務(wù)器準備就緒時從服務(wù)器中提取新的權(quán)重集

在每臺服務(wù)器上：

• 匯總所有'm'個worker的梯度，例如g =Σgi

• new_weights = old_weights - learning_rate *(g +* Norm(old_weights))

架構(gòu)

High level architecture

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

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

讓我們看一下構(gòu)建這種架構(gòu)所需的一些原語

鍵值A(chǔ)PI

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

Range based push and pull

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

異步任務(wù)和依賴

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

靈活的一致性模型

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

一致性模型

實施細節(jié)

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

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

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

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

聚合后復(fù)制

• 服務(wù)器節(jié)點管理： 能夠通過向系統(tǒng)添加新服務(wù)器節(jié)點進行擴展是有用的。發(fā)生這種情況時，服務(wù)器管理器會為新節(jié)點分配一個鍵空間。此鍵可以來自之前終止的某個節(jié)點，或者通過拆分負載很重的服務(wù)器節(jié)點的鍵空間。然后，這個新節(jié)點拉出它負責(zé)的密鑰空間，并從k個neighbors中抽取副本作為從屬。通常，可能需要兩階段提取來提取在被這個新節(jié)點提取時被覆蓋的數(shù)據(jù)。然后，服務(wù)器管理器將此所有權(quán)分配消息廣播到環(huán)上的其他節(jié)點，然后這些其他服務(wù)器節(jié)點可以根據(jù)此新的所有權(quán)分配縮小其密鑰空間使用量。對于離開的節(jié)點，服務(wù)器管理器將密鑰空間分配給某個新的傳入節(jié)點。服務(wù)器管理器通過心跳維護節(jié)點運行狀況。

• worler節(jié)點：添加新的工作節(jié)點相對簡單。任務(wù)調(diào)度程序?qū)��?shù)據(jù)范圍分配給工作節(jié)點。這個新節(jié)點將從NFS或其他一些workers中提取數(shù)據(jù)。然后，調(diào)度程序?qū)⒋讼�息廣播給其他workers，以便其他workers可以通過放棄一些訓(xùn)練數(shù)據(jù)來回收一些空間。當(dāng)工作節(jié)點離開時，它將由算法的所有者決定是否恢復(fù)數(shù)據(jù) - 取決于數(shù)據(jù)的大小。

結(jié)論

本文闡述了分布式機器學(xué)習(xí)的一些重要概念。從系統(tǒng)的角度來看，本文結(jié)合使用了一些很好的技術(shù)，比如一致哈希�；�于范圍的通信和支持消息傳遞的本機機器學(xué)習(xí)(ML)構(gòu)造似乎是構(gòu)建高效機器學(xué)習(xí)(ML)框架的良好洞察力。

標(biāo)簽： [db:TAGG]

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。