本文內(nèi)容源自Erix Xing教授16年初的文章[1]，盡管大規(guī)模機(jī)器學(xué)習(xí)的手段和方法在業(yè)界已經(jīng)研究多年，也已經(jīng)形成了不少工業(yè)界使用的手段和方法，但這篇文章真正系統(tǒng)地從機(jī)器學(xué)習(xí)算法的本質(zhì)總結(jié)并歸納出如何解決這類問(wèn)題的原則，并在相應(yīng)的開源項(xiàng)目上給予工程實(shí)現(xiàn)，非常值得閱讀和參考。

解決大規(guī)模機(jī)器學(xué)習(xí)問(wèn)題，系統(tǒng)框架需要在容易編程和性能，以及正確性之間取得平衡。傳統(tǒng)基于Dataflow的框架如Hadoop/Spark，都是采用BSP，集群所有節(jié)點(diǎn)都需要等待執(zhí)行最慢的完成后才能繼續(xù)。一些基于圖的方案，如GraphLab，則引入了新的問(wèn)題，比如如何切分機(jī)器學(xué)習(xí)程序，計(jì)算調(diào)度，還有一致性模型。另一方面，機(jī)器學(xué)習(xí)任務(wù)抽象成圖并不是很直接，把已有的算法移植到基于圖的抽象上需要不少工作，而且，基于圖的抽象有時(shí)還會(huì)導(dǎo)致程序不正確，或者陷入次優(yōu)化。參數(shù)服務(wù)器是近年浮現(xiàn)出來(lái)的針對(duì)機(jī)器學(xué)習(xí)算法的良好抽象，然而單純的參數(shù)服務(wù)器還缺乏從頭打造機(jī)器學(xué)習(xí)算法的良好編程接口，還不能跟Hadoop/Spark這樣的項(xiàng)目相提并論。

絕大多數(shù)機(jī)器學(xué)習(xí)算法都可以歸結(jié)為類似下面的最優(yōu)化問(wèn)題：

其中優(yōu)化目標(biāo)L包含兩部分，一個(gè)是損失函數(shù)f，用來(lái)描述數(shù)據(jù)如何適應(yīng)模型，另一部份是一個(gè)結(jié)構(gòu)誘導(dǎo)函數(shù)，主要用來(lái)引入領(lǐng)域知識(shí)來(lái)給參數(shù)施加限制或者懲罰因子。上面這個(gè)式子隱藏了解決機(jī)器學(xué)習(xí)問(wèn)題面臨的大數(shù)據(jù)挑戰(zhàn)，比如一個(gè)典型的用于圖像分類的卷積神經(jīng)網(wǎng)絡(luò)，包含數(shù)十億乃至萬(wàn)億的矩陣型模型參數(shù)，而損失函數(shù)則呈現(xiàn)出深度遞歸形式f=f1(f2(f3(...)+...)+...)用來(lái)學(xué)習(xí)類似人類視覺皮層的圖像分層表示。圖模型，特別是主題模型，經(jīng)常從數(shù)十億的文檔中發(fā)現(xiàn)主題，比如從社交媒體中，為了捕捉豐富的語(yǔ)義信息，這也會(huì)有數(shù)以萬(wàn)億的參數(shù)。

把上面的最優(yōu)化問(wèn)題更進(jìn)一步細(xì)化，就變成為找到優(yōu)化目標(biāo)L對(duì)應(yīng)的模型參數(shù)A而迭代的表達(dá)式：

A(t) = F(A(t ? 1), ?_L(A(t ? 1), x))

t表示第幾輪迭代。在訓(xùn)練中，計(jì)算程序反復(fù)迭代執(zhí)行直到收斂條件或者其他停止條件滿足。下一次迭代需要的模型參數(shù)A(t)從上一次的迭代參數(shù)A(t-1)和數(shù)據(jù)x中產(chǎn)生，用到2個(gè)函數(shù)：一個(gè)是更新函數(shù)?，其優(yōu)化目標(biāo)(或損失函數(shù))為L(zhǎng)，它利用A(t-1)和數(shù)據(jù)x產(chǎn)生中間結(jié)果，另一個(gè)是聚合函數(shù)F，它用于把中間結(jié)果和A(t-1)結(jié)合生成A(t)。大部分機(jī)器學(xué)習(xí)算法都可以簡(jiǎn)化成為這種結(jié)構(gòu)，例如隨機(jī)梯度下降，坐標(biāo)下降，MCMC，變分等。

看兩個(gè)具體例子：

第一個(gè)是Lasso。它的最優(yōu)化表達(dá)式可寫為：

也可簡(jiǎn)化寫成矩陣表達(dá)式

采用坐標(biāo)下降迭代收斂表達(dá)式：

可進(jìn)一步總結(jié)出更新函數(shù)?和聚合函數(shù)F：

另一個(gè)例子是主題模型。它的最優(yōu)化表達(dá)式可寫為：

它的參數(shù)推導(dǎo)通常借助于變分或者Gibbs取樣。以后者為例：

其中-=，+=代表自減，自增操作。更新函數(shù)?分為兩階段執(zhí)行：1) 在所有文檔的詞上執(zhí)行上述取樣操作；2) 輸出A(t)，形式暫略，聚合函數(shù)F形式為簡(jiǎn)單的識(shí)別函數(shù)(identify function)。

以上兩個(gè)例子，對(duì)于算法不熟悉的可能難以理解，這里僅列出大致的優(yōu)化結(jié)果，其目的在于闡明機(jī)器學(xué)習(xí)算法的通用表達(dá)式。有了這些例子，我們?yōu)榱司涂梢陨钊肓私鈾C(jī)器學(xué)習(xí)算法的特性，從而總結(jié)出執(zhí)行大規(guī)模分布式程序時(shí)，跟傳統(tǒng)分布式程序的區(qū)別。

比如一個(gè)傳統(tǒng)的MapReduce程序---排序，框架首先把數(shù)據(jù)x_1,x_2,...,x_n隨機(jī)分發(fā)到M個(gè)Mapper，這些Mapper隨后把元素哈希成為鍵值對(duì)(h(x_i),x_i)，其中h是order-preserving的，就是說(shuō)如果x<>

額外的復(fù)雜努力，來(lái)提供容錯(cuò)，比如基于磁盤的快照，并且跟任務(wù)調(diào)度結(jié)合起來(lái)，這里邊的工程設(shè)計(jì)十分復(fù)雜。

對(duì)于機(jī)器學(xué)習(xí)程序來(lái)說(shuō)，需要對(duì)中間結(jié)果的錯(cuò)誤更加健壯。如果一些參數(shù)在?函數(shù)執(zhí)行時(shí)沒(méi)有正確得出，也不妨礙整個(gè)程序的收斂性。例如SGD程序，不論深度學(xué)習(xí)，矩陣分解，還是邏輯回歸，都會(huì)經(jīng)常使用。在運(yùn)行時(shí)，比如每次迭代后增加小的隨機(jī)錯(cuò)誤ε，這樣A(t)=A(t)+ε，即便如此，收斂仍然能夠保證，因?yàn)镾GD總能向正確的方向更新參數(shù)(根據(jù)梯度)。機(jī)器學(xué)習(xí)算法的這種特性能夠很大的影響分布式框架的設(shè)計(jì)——系統(tǒng)并不需要完美地確保所有任務(wù)無(wú)誤運(yùn)行，也無(wú)須確保機(jī)器之間通信正確，乃至從錯(cuò)誤中恢復(fù)。當(dāng)資源有限時(shí)(比如機(jī)器之間帶寬有限)，簡(jiǎn)易容錯(cuò)設(shè)計(jì)能夠讓系統(tǒng)更簡(jiǎn)單和高效。這是大規(guī)模機(jī)器學(xué)習(xí)問(wèn)題跟傳統(tǒng)分布式問(wèn)題的第一點(diǎn)重要區(qū)別。

然而，另一方面，機(jī)器學(xué)習(xí)算法卻比傳統(tǒng)的MapReduce程序擁有更加復(fù)雜的結(jié)構(gòu)依賴，而這些依賴并不能夠從優(yōu)化的目標(biāo)函數(shù)L和更新函數(shù)?容易得出。例如在MapReduce排序中，Reducer等待Mapper結(jié)束，這種依賴是確定性的，而在Lasso中，似乎從前面更新函數(shù)?的表達(dá)式里能夠得出容易并行的結(jié)論，然而實(shí)際并非如此，因?yàn)榈趈個(gè)模型參數(shù)A_j，它的更新實(shí)際上可能依賴所有其他A_k，不正確地并行執(zhí)行可能會(huì)影響程序執(zhí)行的正確性。

上圖中展示了數(shù)據(jù)并行和模型并行的區(qū)別。在機(jī)器學(xué)習(xí)中，這兩種并行是互補(bǔ)的，同時(shí)也是非對(duì)稱的，意思是：數(shù)據(jù)并行可以應(yīng)用到任何對(duì)數(shù)據(jù)采樣具備獨(dú)立同分布假設(shè)的機(jī)器學(xué)習(xí)算法中，包含深度學(xué)習(xí)，Lasso，主題模型等。相比之下，模型并行需要仔細(xì)對(duì)待，因?yàn)槟Ｐ蛥?shù)A_j并不總是具備獨(dú)立同分布假設(shè)，例如前邊提到的Lasso。下面從更廣義的角度來(lái)看兩者：

在數(shù)據(jù)并行中，數(shù)據(jù)x被劃分到不同計(jì)算節(jié)點(diǎn)，如果更新函數(shù)?可以表達(dá)成對(duì)各節(jié)點(diǎn)計(jì)算結(jié)果的和，那么就可以應(yīng)用數(shù)據(jù)并行。例如把Lasso改寫為數(shù)據(jù)并行模式：

在模型并行中，模型A被劃分到不同計(jì)算節(jié)點(diǎn)后，還需要引入一個(gè)調(diào)度函數(shù)S，用來(lái)限制更新函數(shù)?只工作在模型參數(shù)的子集上，避免不同節(jié)點(diǎn)都來(lái)更新相同的參數(shù)。把Lasso以模型并行的方式改寫：

這里調(diào)度函數(shù)S_p,(t-1)對(duì)于節(jié)點(diǎn)p在每次迭代時(shí)只更新固定子集的參數(shù)。由于每個(gè)節(jié)點(diǎn)操作的模型參數(shù)都會(huì)依賴于其他節(jié)點(diǎn)的參數(shù)，并行更新參數(shù)會(huì)得出跟順序更新不同的結(jié)果，這會(huì)導(dǎo)致更慢地收斂，因此對(duì)于調(diào)度器來(lái)說(shuō)，不能浪費(fèi)計(jì)算資源去試圖并行執(zhí)行相互依賴的任務(wù)，而應(yīng)尋找到不依賴的子任務(wù)讓它們并行運(yùn)行。因此對(duì)于調(diào)度器來(lái)說(shuō)，應(yīng)當(dāng)尋找到依賴成立的邊界條件，

再來(lái)看個(gè)在LDA中通過(guò)綜合數(shù)據(jù)并行和模型并行實(shí)現(xiàn)大規(guī)模主題模型的例子：

在圖中，有3個(gè)計(jì)算節(jié)點(diǎn)并行的在每次迭代中只操作一個(gè)數(shù)據(jù)和參數(shù)的子集z_1，z_2，z_3，當(dāng)完成后進(jìn)行下一次迭代時(shí)，更換相應(yīng)子集，以此類推，實(shí)現(xiàn)大規(guī)模并行主題模型。

這是大規(guī)模機(jī)器學(xué)習(xí)問(wèn)題和傳統(tǒng)分布式問(wèn)題的第二點(diǎn)重要區(qū)別。

第三個(gè)重要區(qū)別是非均勻性收斂。MapReduce排序把數(shù)據(jù)分發(fā)到不同節(jié)點(diǎn)執(zhí)行，各節(jié)點(diǎn)的任務(wù)和負(fù)載基本上是均衡的，然而對(duì)于機(jī)器學(xué)習(xí)問(wèn)題來(lái)說(shuō)，數(shù)十億，甚至更多的參數(shù)能夠以不同的迭代數(shù)目收斂，有的2-3輪迭代即可，有的則需要上百次。

第四個(gè)重要特性在于緊湊更新。例如上面的Lasso和LDA，更新函數(shù)?只會(huì)涉及到一小部分模型參數(shù)，這是由數(shù)據(jù)的稀疏本質(zhì)決定的。另一個(gè)例子是深度學(xué)習(xí)，模型參數(shù)A是矩陣，更新函數(shù)?可以只涉及小的向量結(jié)構(gòu)。在設(shè)計(jì)大規(guī)模機(jī)器學(xué)習(xí)框架時(shí)考慮到這種緊湊更新的特性，可以大大減少存儲(chǔ)，計(jì)算，以及網(wǎng)絡(luò)的開銷。

因此為了能夠讓機(jī)器學(xué)習(xí)程序高效執(zhí)行，需要做三件事情：

1 決定如何更好的切分成多個(gè)任務(wù)，究竟采用數(shù)據(jù)并行，還是模型并行，或者混合方案。

2 決定如何調(diào)度子任務(wù)。

3 均衡各節(jié)點(diǎn)的負(fù)載。

這些問(wèn)題在傳統(tǒng)MapReduce類任務(wù)框架里已經(jīng)解決得很好，但對(duì)于機(jī)器學(xué)習(xí)算法來(lái)說(shuō)則是挑戰(zhàn)。調(diào)度器需要能夠很好的判定模型參數(shù)依賴的邊界條件，這是個(gè)算法相關(guān)的問(wèn)題，例如Lasso和LDA的條件就不一樣。在獲取邊界條件之后，需要通過(guò)調(diào)度來(lái)平衡節(jié)點(diǎn)負(fù)載，傳統(tǒng)分布式任務(wù)的BSP肯定是無(wú)法勝任該工作，因?yàn)闄C(jī)器學(xué)習(xí)任務(wù)是一種有限異步(非完全異步)，完全同步等待就會(huì)造成大量浪費(fèi)。在機(jī)器學(xué)習(xí)中，需要一種有限異步的同步原語(yǔ)，稱為SSP，SSP的背景材料本號(hào)之前在參數(shù)服務(wù)器的介紹中已經(jīng)提及，點(diǎn)擊原文可以閱讀參數(shù)服務(wù)器的背景材料。

Eric Xing教授在其Petuum系統(tǒng)里完整地提出了解決分布式機(jī)器問(wèn)題的框架，以參數(shù)服務(wù)器和并行，調(diào)度為核心，稱之為SAP(Structure Aware Parallelization)，結(jié)構(gòu)感知的并行計(jì)算。SAP提供類似MapReduce一樣的簡(jiǎn)易編程抽象接口，所有機(jī)器學(xué)習(xí)程序只需要實(shí)現(xiàn)3個(gè)函數(shù)：

1 schedule，用來(lái)確定更新的模型參數(shù)以及提供參數(shù)依賴檢查

2 push，用來(lái)執(zhí)行?更新函數(shù)

3 pull，用來(lái)執(zhí)行F聚合函數(shù)

其中，push和pull就是參數(shù)服務(wù)器的原語(yǔ)。根據(jù)文獻(xiàn)[1]提到的證明，SAP基本上可以做到分布式機(jī)器學(xué)習(xí)算法的理想抽象，據(jù)此實(shí)現(xiàn)的算法，可以有甚至不止一個(gè)數(shù)量級(jí)的性能提升。在Petuum項(xiàng)目中，Strads調(diào)度器就實(shí)現(xiàn)了SAP抽象，并應(yīng)用到若干典型算法，包含Lasso，矩陣分解，還有主題模型等。

那么，Petuum框架和Strads調(diào)度器，應(yīng)用于深度學(xué)習(xí)時(shí)，相比已有的方案有哪些特色呢？Petuum有一個(gè)集成Caffe的工作叫做Poseidon，利用SSP和數(shù)據(jù)并行，Poseidon可以在普通網(wǎng)絡(luò)組成的GPU集群上實(shí)現(xiàn)大規(guī)模深度集群，而無(wú)須Infiniband和RDMA。更進(jìn)一步的對(duì)比，尤其是和最新版支持分布式訓(xùn)練的Tensorflow，以及MXNet，本號(hào)將在接下來(lái)給出對(duì)比和分析。

[1] Strategies and Principles of Distributed Machine Learning on Big DataEric P. Xing, Qirong Ho, Pengtao Xie, Wei Dai.arXiv:1512.09295 (2015)