大數(shù)據(jù)的分布式機器學(xué)習(xí)的策略與原則

Eric P.Xing *, Qirong Ho, Pengtao Xie, Wei Dai

School of Computer Science, Car negie Mellon University, Pittsburgh, PA 15213, USA

大數(shù)據(jù)的分布式機器學(xué)習(xí)的策略與原則

Eric P.Xing *, Qirong Ho, Pengtao Xie, Wei Dai

School of Computer Science, Car negie Mellon University, Pittsburgh, PA 15213, USA

article info

Article history:

Received 29 December 2015 Revised 1 May 2016

Accepted 23 May 2016

Available online 30 June 2016

機器學(xué)習(xí)

人工智能大數(shù)據(jù)

大型模型

分布式系統(tǒng)

原則

理論

數(shù)據(jù)并行性

模型并行性

大數(shù)據(jù)的發(fā)展已經(jīng)引領(lǐng)了對能夠?qū)W習(xí)包含數(shù)百萬至數(shù)十億參數(shù)的復(fù)雜模型的機器學(xué)習(xí)系統(tǒng)的新需求，以保證足夠的能力來消化海量的數(shù)據(jù)集，提供強大的預(yù)測分析（如高維潛特征、中介表示和決策功能）。為了在這樣的尺度上，在成百上千臺的分布式機器集群中運行機器學(xué)習(xí)算法，關(guān)鍵往往是要投入顯著的工程性的努力——有人可能會問，這樣的工程是否還屬于機器學(xué)習(xí)的研究領(lǐng)域？考慮到如此“大”的機器學(xué)習(xí)系統(tǒng)可以極大地從根植于機器學(xué)習(xí)的統(tǒng)計和算法的理解中受益——因此，機器學(xué)習(xí)的研究人員應(yīng)該不會回避這樣的系統(tǒng)設(shè)計——我們討論了一系列從我們近來對工程尺度的機器學(xué)習(xí)解決方案的研究中提煉的原則和策略。這些原則和策略從機器學(xué)習(xí)的應(yīng)用連續(xù)跨越到它的工程和理論研究，以及大型機器學(xué)習(xí)的系統(tǒng)和架構(gòu)的發(fā)展，目標(biāo)是了解如何使其有效、廣泛地適用，并以收斂和縮放保證支持。它們關(guān)注的是機器學(xué)習(xí)研究傳統(tǒng)上注意較少的四個關(guān)鍵問題：一個機器學(xué)習(xí)程序怎樣能分布到一個集群中去？機器學(xué)習(xí)計算怎樣能通過機器間的交流連接起來？這樣的交流是如何被執(zhí)行的？機器間應(yīng)該交流的內(nèi)容是什么？通過揭示機器學(xué)習(xí)程序所獨有的，而非常見于傳統(tǒng)計算機程序中的基礎(chǔ)性的統(tǒng)計和算法上的特點，并通過剖析成功案例，以揭示我們?nèi)绾卫眠@些原則來同時設(shè)計和開發(fā)高性能的分布式機器學(xué)習(xí)軟件以及通用的機器學(xué)習(xí)框架，我們?yōu)闄C器學(xué)習(xí)的研究人員和從業(yè)者提供了進一步塑造并擴大機器學(xué)習(xí)與系統(tǒng)之間的領(lǐng)域的機會。

? 2016 THE AUTHORS.Published by Elsevier LTD on behalf of Chinese Academy of Engineering and Higher Education Press Limited Company.This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

1.引言

機器學(xué)習(xí)已經(jīng)成為從原始數(shù)據(jù)中提取結(jié)構(gòu)化信息和知識，將其轉(zhuǎn)變成為不同應(yīng)用的自動預(yù)測和運用假說的首要機制。這些應(yīng)用如分析社會網(wǎng)絡(luò)[1]、推理客戶行為[2]；轉(zhuǎn)譯文本、圖像和視頻[3]；確定疾病和治療方法[4]；操縱無人駕駛汽車[5]；跟蹤網(wǎng)絡(luò)安全異?；顒覽6]，及其他。機器學(xué)習(xí)的大多數(shù)應(yīng)用都是由一個中等數(shù)量的發(fā)達的機器學(xué)習(xí)方法族系支持，其中，每種方法都體現(xiàn)了從模型設(shè)計到對算法的創(chuàng)新，甚至對軟件應(yīng)用的完善這一連串的技術(shù)要點，并吸引了來自研究和發(fā)展團體的日益增長的創(chuàng)新貢獻。這些方法現(xiàn)代的例子包括圖形模型[7-9]、正則貝葉斯模型[10-12]、非參數(shù)貝葉斯模型[13,14]、稀疏結(jié)構(gòu)模型[15,16]、大幅度方法[17,18]、深度學(xué)習(xí)[19,20]、矩陣分解[21,22]、稀疏編碼[23,24]以及潛在空間建模[1,25]。一個能確保數(shù)學(xué)合理性和結(jié)果可重復(fù)性的機器學(xué)習(xí)的普遍做法，是從業(yè)者和研究人員為某種機器學(xué)習(xí)方式(比如，通過一個卷積神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)模型，提供圖像的語義解釋)的一個特定應(yīng)用的實例編寫一個機器學(xué)習(xí)程序(使用任何通用的高級編程語言)。理想的情況是，這個程序預(yù)計將依托于各種硬件和云基礎(chǔ)設(shè)施——筆記本電腦、服務(wù)器、圖形處理單元(GPU)、云計算和虛擬機、分布式網(wǎng)絡(luò)存儲、以太網(wǎng)和Infi niBand網(wǎng)絡(luò)(僅舉幾例)，以得到快速、準(zhǔn)確的執(zhí)行。這樣，程序就是硬件無關(guān)但機器學(xué)習(xí)明確的(即無論硬件如何選取，對于數(shù)據(jù)都遵循相同的數(shù)學(xué)原理，并獲得相同的結(jié)果)。

隨著感官、數(shù)字存儲和網(wǎng)絡(luò)通信技術(shù)的進步，傳統(tǒng)機器學(xué)習(xí)的研究與發(fā)展——擅長模型、算法和理論的創(chuàng)新——正面臨日益盛行的大數(shù)據(jù)收集的挑戰(zhàn)，如每分鐘上傳到視頻共享網(wǎng)站的數(shù)百小時視 頻①https://www.youtube.com/yt/press/statistics.html，或社交媒體中上億用戶產(chǎn)生的幾千萬億字節(jié)(PB)數(shù)據(jù)②https://code.facebook.com/posts/229861827208629/scaling-the-facebook-data-warehouse-to-300-pb/。大數(shù)據(jù)的興起也伴隨著對包括數(shù)百萬至數(shù)十億參數(shù)的更高維也更復(fù)雜的機器學(xué)習(xí)模型的興趣的增加，以支持日益復(fù)雜的數(shù)據(jù)，或者為了獲得更高的預(yù)測精度(比如為客戶提供更好的服務(wù)和醫(yī)療診斷)，支持更智能的任務(wù)(比如無人駕駛車輛和視頻數(shù)據(jù)的語義解釋)[26,27]。對這樣大規(guī)模的數(shù)據(jù)運作如此大型的機器學(xué)習(xí)模型是超出單一機器的存儲和計算能力的。這一差距已經(jīng)激發(fā)了近來越來越多對于分布式機器學(xué)習(xí)的工作，其中，機器學(xué)習(xí)程序由研究集群、數(shù)據(jù)中心和云提供商使用成千上萬的機器加以執(zhí)行。從得到數(shù)學(xué)上等價的或類似于由單一機器產(chǎn)生的解的意義上說，以機器集群(p個機器)代替一個機器，就可以通過分布式機器學(xué)習(xí)程序?qū)崿F(xiàn)幾乎p倍的加速；然而，報告過的加速往往還遠低于這個限度。例如，即使近來使用最先進的技術(shù)對主題模型的實現(xiàn)[28](文本分析的一種常用的方法)，由于在實現(xiàn)中的數(shù)學(xué)錯誤(如在文獻[25]所示)，也無法用4×機達到2×加速，而利用MapReduce-like系統(tǒng)進行的深度學(xué)習(xí)，如Spark，也尚未用10×機達到5×加速 [29]。因此解決這種可量測性挑戰(zhàn)就是分布式機器學(xué)習(xí)研究的一個主要目標(biāo)，以減少運行大型機器學(xué)習(xí)應(yīng)用的資本和運營成本。

考慮到大多數(shù)——如果不是全部的——主要支撐了當(dāng)代大規(guī)模應(yīng)用的機器學(xué)習(xí)算法的迭代收斂性質(zhì)，一個人在第一眼可能自然地確定兩種向可量測性發(fā)展的途徑：以迭代次數(shù)度量的更快的收斂(在機器學(xué)習(xí)團體中也被稱為收斂速度)，和以系統(tǒng)執(zhí)行一個迭代的實際速度量度的更快的單次迭代時間(也被稱為在系統(tǒng)中的吞吐量)。事實上，當(dāng)前許多分布式機器學(xué)習(xí)研究者關(guān)注的主要焦點是算法的正確性和在大范圍的機器學(xué)習(xí)方法中更快的收斂速度[30,31]。 然而，從算法研究到工業(yè)級的實現(xiàn)，由于其在系統(tǒng)上理想化的假設(shè)——例如，網(wǎng)絡(luò)是無限快的假設(shè)(即零同步成本)，或所有機器以相同的速率執(zhí)行算法(意味著沒有背景任務(wù)，只有一個單一用戶的集群，這對于許多用戶共享的現(xiàn)實世界的研究和生產(chǎn)集群來說是不切實際的期望)，對于許多“加速”算法都很困難。另外，系統(tǒng)的研究者們聚焦在高吞吐量(每秒更多次迭代)和故障恢復(fù)的保證上，或許會選擇假設(shè)機器學(xué)習(xí)算法將在非理想的執(zhí)行模式下正常工作(如完全異步執(zhí)行)，或者它可以容易地在一個給定的抽象概念上被改寫(如MapReduce系統(tǒng)或頂點編程)[32-34]。在機器學(xué)習(xí)和系統(tǒng)的研究中，來自另一個方面的問題會變得簡單化，從而可能會反過來掩蓋降低分布式機器學(xué)習(xí)的資本成本的新機會。在本文中，我們提出了一個將以機器學(xué)習(xí)為中心和以系統(tǒng)為中心的想法相結(jié)合，并將機器學(xué)習(xí)算法(數(shù)學(xué)屬性)和系統(tǒng)硬件(物理性能)的細微差別匯集起來，以讓思想和設(shè)計從兩端各自協(xié)力工作，并彼此增強的策略。

現(xiàn)有的許多通用的大數(shù)據(jù)軟件平臺提供了一種在正確性、執(zhí)行速度和機器學(xué)習(xí)應(yīng)用編程難易中特有的折衷方式。例如，數(shù)據(jù)流系統(tǒng)，如Hadoop和Spark[34]是建立在一個MapReduce系統(tǒng)的抽象概念上[32]，并提供了一個易于使用的編程接口，但較少關(guān)注機器學(xué)習(xí)性能，如容錯、細粒度計算排序和加快機器學(xué)習(xí)程序的通信。因此，它們提供正確的機器學(xué)習(xí)程序執(zhí)行，編程容易，但比機器學(xué)習(xí)的專業(yè)平臺速度慢[35,36]。這種(相對的)速度欠缺可部分歸因于用于Hadoop和Spark中的批量同步并行(BSP)的同步模型，其中，被分配給一組任務(wù)的機器必須等待最慢的機器完成，再進行任務(wù)的下一組程序(例如，所有程序必須在減速器開始前完成)[37]。其他的例子包括以圖形為中心的平臺，如GraphLab和Pregel，它們依存于一個為機器學(xué)習(xí)程序劃分、計算排序、靈活的一致性控制開辟了新機會的基于圖形的“頂點編程”的抽象概念；因此，它們通常對于機器學(xué)習(xí)來說較為準(zhǔn)確、快速。然而，機器學(xué)習(xí)程序通常不被視為頂點程序(相反，它們在數(shù)學(xué)上表示為迭代收斂的定點方程)，需要通過不平凡的努力將其重寫成頂點程序。在少數(shù)情況下，圖像的抽象化可能會導(dǎo)致不正確的執(zhí)行或達不到最佳的執(zhí)行速度[38,39]。最近報告中介紹了參數(shù)服務(wù)器模式[28,36,37,40,41]，其為編寫分布式機器學(xué)習(xí)程序提供了一個完全的“設(shè)計模板”或思考模式，但這不是一個像Hadoop，Spark，GraphLab和Pregel的編程平臺或工作分配系統(tǒng)?？紤]到為具體應(yīng)用的實例編寫機器學(xué)習(xí)程序的普遍機器學(xué)習(xí)實踐，對機器學(xué)習(xí)從業(yè)者來說，一個有用的軟件平臺(作為替代)可以提供兩種應(yīng)用：①一套準(zhǔn)備好的機器學(xué)習(xí)工具的實施，如隨機近下降算法[42,43]、坐標(biāo)下降算法[44]，或馬爾可夫鏈蒙特卡羅算法[45]——可以在不同的機器學(xué)習(xí)算法族系中重復(fù)使用；②以及分布式機器學(xué)習(xí)集群操作系統(tǒng)，跨多種硬件分區(qū)和執(zhí)行以支持這些工具的實施。這樣的軟件平臺不僅降低了分布式機器學(xué)習(xí)研究的資本成本，而且通過更容易使用的編程庫和集群管理接口降低了大型應(yīng)用程序的人力成本(科學(xué)家和工程師的工作時間)，從而對研究有所促進。

隨著對數(shù)據(jù)驅(qū)動的知識提煉、決策制定和持久學(xué)習(xí)越來越多的需要——這些是機器智能領(lǐng)域有代表性的標(biāo)志——在未來幾年中，計算大數(shù)據(jù)方面工作負載的主要形式可能會經(jīng)歷一個從用于確定性存儲、索引和查詢的數(shù)據(jù)庫風(fēng)格的操作，到機器學(xué)習(xí)風(fēng)格的操作，如概率推理、約束優(yōu)化和幾何變換的快速轉(zhuǎn)變。為了最好地完成這些計算任務(wù)，必須進行大量的數(shù)據(jù)傳遞，解決高維的數(shù)學(xué)程序，有必要重新審視傳統(tǒng)系統(tǒng)架構(gòu)中的原則和策略，并探討在正確性、速度、可編程性和可配置性中達到最佳平衡的新設(shè)計。指導(dǎo)這樣的探索所必需和關(guān)鍵的洞察力是：理解機器學(xué)習(xí)程序是以優(yōu)化為中心，經(jīng)常允許迭代收斂算法的解決方案，而不是一步或封閉形式的解決方案。此外，機器學(xué)習(xí)程序具有三個特性：①容錯性，這使得機器學(xué)習(xí)程序能抵御中間計算中有限的錯誤；②動態(tài)結(jié)構(gòu)的依存關(guān)系，其中，在模型參數(shù)間變化的相關(guān)性必須得到說明，以實現(xiàn)高效、近乎線性的并行加速比；③非一致收斂，其中，每10億(或萬億)的機器學(xué)習(xí)參數(shù)都可以在大不相同的迭代次數(shù)下收斂(通常情況下，一些參數(shù)將收斂在2～3次迭代，而另一些則需要數(shù)百次)。這些性能可以與傳統(tǒng)程序(如排序和數(shù)據(jù)庫查詢)相比，即傳統(tǒng)程序以處理為中心，并且僅能保證如果每一步都是在原子正確的情況下進行，才能正確執(zhí)行[32,34]。在本文中，我們將基于這些特性推導(dǎo)出分布式機器學(xué)習(xí)系統(tǒng)的獨特設(shè)計原則；這些設(shè)計原則在機器學(xué)習(xí)正確性、速度和可編程性(同時通用于幾乎所有機器學(xué)習(xí)程序)之間取得更高效的平衡，并組織成以下四個部分：①如何分配機器學(xué)習(xí)程序；②如何將機器學(xué)習(xí)計算和通信連接起來；③如何通信；以及④通信的內(nèi)容。在深入探討這些原則之前，首先讓我們回顧一些關(guān)于機器學(xué)習(xí)迭代收斂算法的必要背景信息。

2.背景：機器學(xué)習(xí)迭代收斂算法

在存在少數(shù)特例的情況下，幾乎所有的機器學(xué)習(xí)程序都可以被看作是以優(yōu)化為中心，并固定為一個通用的數(shù)學(xué)形式的程序：

在本質(zhì)上，一個機器學(xué)習(xí)程序嘗試將N個數(shù)據(jù)樣本(已標(biāo)記或未標(biāo)記，由實際應(yīng)用決定)以表示(其中，yi只有在已標(biāo)記的數(shù)據(jù)樣本中出現(xiàn))，代入由A表示的模型中。這種代入通過優(yōu)化(最大化或最小化)一個綜合目標(biāo)函數(shù)L而實現(xiàn)，它由兩部分組成：一個是損失函數(shù)f，用來描述數(shù)據(jù)如何適應(yīng)模型；另一個是結(jié)構(gòu)誘導(dǎo)函數(shù)r，通過給參數(shù)θ施加限制或者懲罰因子，將特定領(lǐng)域知識的預(yù)期應(yīng)用具體化。方程(1)的簡單性掩蓋了函數(shù)f和r潛在的復(fù)雜結(jié)構(gòu)及數(shù)據(jù)x和模型A潛在的巨大規(guī)模。此外，機器學(xué)習(xí)算法族系往往是由其中f，r，x和A的特點所定義。例如，用于圖像分類的一種典型的深度學(xué)習(xí)模型，如文獻 [20]中介紹的，模型A中會包含千萬至十億計的矩陣型模型參數(shù)，而損失函數(shù)f具有深度遞歸結(jié)構(gòu)用來學(xué)習(xí)類似人類視覺皮層的圖像分層表示。用于識別遺傳疾病標(biāo)志的結(jié)構(gòu)化稀疏回歸模型[4]可以使用重疊結(jié)構(gòu)誘導(dǎo)函數(shù)+…，其中，Aa, Ab和 Ac是A的重疊子集，以遵守染色體重組的復(fù)雜過程。圖形化的模型，尤其是主題模型，通常出現(xiàn)在數(shù)十億的文件x中，即 N≥109，這數(shù)量很容易由社交媒體諸如臉譜網(wǎng)和推特產(chǎn)生——并且可能涉及數(shù)萬億的參數(shù)θ，以在如此多的數(shù)據(jù)中捕捉豐富的語義概念[26]。

除了指定方程(1)，還必須找到能夠優(yōu)化L的模型A參數(shù)。這通過在諸如隨機梯度下降[42]、坐標(biāo)下降[44]、馬爾可夫鏈蒙特卡羅(MCMC)[45]和變分推理(僅舉幾例)等算法技術(shù)中選取一種算法來完成。將所選擇的算法技術(shù)應(yīng)用于方程(1)來產(chǎn)生一組迭代收斂的方程，其由機器學(xué)習(xí)從業(yè)者編寫的程序代碼實現(xiàn)，并可重復(fù)，直到收斂或滿足停止準(zhǔn)則(或常常是直到超出一個固定的計算預(yù)計值)。迭代收斂方程有以下一般形式：

式中，t表示迭代次數(shù)。這個一般形式利用先前的迭代中的一個A(t - 1) 和數(shù)據(jù)x，產(chǎn)生下一個迭代的模型參數(shù)A(t)，其中使用了兩個函數(shù)：①計算執(zhí)行數(shù)據(jù)x和之前的模型狀態(tài)A(t - 1)，并輸出中間結(jié)果的更新函數(shù)ΔL(添加目標(biāo)L)；以及②之后將這些中間結(jié)果組合產(chǎn)生A(t)的聚合函數(shù)F。為了符號的簡單化，我們之后將從Δ的下標(biāo)中省去L——毫無疑問本文中談及的所有機器學(xué)習(xí)程序被認(rèn)為具有一個明確的損失函數(shù)L(而不是缺乏這樣一個損失函數(shù)的啟發(fā)式算法或程序)。

現(xiàn)在讓我們來看方程(1)和方程(2)這兩個具體的例子，它們對于理解機器學(xué)習(xí)程序的獨特性質(zhì)將很有用。我們會特別關(guān)注任何機器學(xué)習(xí)程序的四個關(guān)鍵部分：①數(shù)據(jù)x和模型A；②損失函數(shù)f(x, A)；③結(jié)構(gòu)誘導(dǎo)函數(shù)r(A)；以及④可用于這個程序的算法技術(shù)。

(1) 套索回歸。套索回歸[46]也許是結(jié)構(gòu)化稀疏回歸機器學(xué)習(xí)算法族系中最簡單的例子，被用于以給定的向量值特征xi(即回歸，它使用已標(biāo)記的數(shù)據(jù))預(yù)測響應(yīng)變量yi——但基于在xi中只有幾個維度或特征為yi提供信息的假設(shè)。作為輸入，套索回歸給出了N個訓(xùn)練樣本x，以的形式，其中的特征都是m維向量。我們的目標(biāo)是找到一個由權(quán)重向量A參數(shù)化的線性函數(shù)，這樣，① ATxi≈yi，②m維參數(shù)是稀疏的(大多數(shù)要素都是零)：

或者更簡潔的矩陣表示：

(2) 隱含狄利克雷分布主題模型。隱含狄利克雷分布(LDA)[47]是圖形模型機器學(xué)習(xí)算法族系中的一員，也因其在一個文本文件的大型語料庫中確定常見主題的能力，而被稱為一個“主題模型”。作為輸入，LDA是給定N個未標(biāo)記的文件，其中，每個文件xi含有Ni個單詞(在LDA文書中簡稱“記號”)，表示為xi=xi1,…,xij,…,xiNi。每個記號xij∈｛1,…,V ｝ 為一個整數(shù)，用來表示詞匯集合V中的一個單詞——例如，“機器學(xué)習(xí)算法”這個短語可以表示為xi=xi1,xi2,xi3=25,60,13(單詞和整數(shù)之間的對應(yīng)關(guān)系是任意的，且對LDA算法的精度沒有關(guān)系)。

其中，

其中，+=和-=是自增、自減運算符(即δ，B和z都被原位修正)；～ P( )的意思是“抽樣分布”，是給定現(xiàn)有值的zij的條件概率。更新在兩個階段進行：①在所有文件記號xij上執(zhí)行方程(8)；②輸出集合FLDA(A(t - 1), …)僅為恒等函數(shù)。

2.1.機器學(xué)習(xí)程序的獨特性

為了在一個分布式的集群中加快執(zhí)行大規(guī)模的機器學(xué)習(xí)程序，我們希望通過著眼于其如何通知分布式機器學(xué)習(xí)系統(tǒng)的設(shè)計來理解它們的屬性。先了解機器學(xué)習(xí)程序“不”是什么會很有幫助：讓我們考慮一個傳統(tǒng)的、非機器學(xué)習(xí)的程序，比如用MapReduce排序。該算法首先隨機在一個M映射集中分配要素進行排序x1,..., xN。映射將每個要素xi散列成鍵值對 (h(xi), xi)，其中，h是一個滿足h(x) ＞ h(y)(如果 x ＞ y)的“保序”哈希函數(shù)。其次，對每一個獨特的鍵a，MapReduce系統(tǒng)發(fā)送所有鍵值對(a, x)至標(biāo)記“a”的減速器。然后每個減速器對其接收的值x運行順序排序算法，最后減速器輪流(按鍵的升序排列)輸出自己的排序值。

關(guān)于MapReduce排序要注意的第一件事，就是它是單通和非迭代的——只有單一Map和單一Reduce步驟是必需的。這與迭代收斂和重復(fù)方程(2)多次的機器學(xué)習(xí)程序相反。更重要的是，MapReduce是以操作為中心和確定性的，不能容許個人操作的錯誤。例如，如果一些映射器輸出一個MIS散列對(a, x)，而a ≠ h(x) (作為討論的基礎(chǔ)，我們可以說這是由于斷電恢復(fù)不當(dāng))，之后的最終輸出將是錯序的，因為x將在錯誤的位置輸出。正是因為這一原因，Hadoop和Spark(支持MapReduce的系統(tǒng))通過魯棒容錯系統(tǒng)提供強大的、可操作的正確性保證。這些容錯系統(tǒng)當(dāng)然需要額外的工程，需要額外更多基于硬盤的檢查點和譜系樹的形式的運行時長費用[34,49] ——但這些對不通過容錯系統(tǒng)就可能無法正確執(zhí)行的以操作為中心的程序是必要的。

這就引出機器學(xué)習(xí)程序的第一個屬性：容錯。不像MapReduce排序的例子，機器學(xué)習(xí)程序?qū)χ虚g計算的小錯誤通常是穩(wěn)定的。在方程(2)中，即使有限數(shù)量的ΔL更新沒有被正確計算或發(fā)送，機器學(xué)習(xí)程序仍然可以在數(shù)學(xué)上保證收斂模型參數(shù)A*達到最佳的設(shè)置——也就是說，機器學(xué)習(xí)算法能以正確的輸出終止(盡管這樣做可能需要更多的迭代)[37,40]。一個很好的例子是隨機梯度下降(SGD)，這是很多機器學(xué)習(xí)程序常用的一種主力算法，應(yīng)用范圍從深入學(xué)習(xí)到矩陣分解和邏輯回歸[50-52]。執(zhí)行一個使用SGD的機器學(xué)習(xí)程序時，即使一個小的隨機向量ε在每次迭代后添加到模型中，即A(t) = A(t) + ε，收斂仍有保證；直觀地說，這是因為SGD總是為更新ΔL計算出最佳的A*的正確方向，所以移動A(t)會簡單地以重新計算以適配的方向結(jié)束[37,40]。這個屬性對分布式系統(tǒng)設(shè)計有重要的影響，因為系統(tǒng)不再需要保證完美的執(zhí)行、機器間的通信，或從失敗中恢復(fù)(這需要大量的工程開銷和長運行時間)。進行近似的執(zhí)行往往更便宜，特別是在資源被約束或限制的情況下(如有限的機間網(wǎng)絡(luò)帶寬)[37,40]。

除了容錯，由于依存結(jié)構(gòu)不是在對目標(biāo)L或更新函數(shù)ΔL和F一次粗略的審視就能明確的，機器學(xué)習(xí)程序?qū)嶋H上比以操作為中心的程序更難執(zhí)行。而依存結(jié)構(gòu)出現(xiàn)在以操作中心的程序中就肯定是這樣：在MapReduce排序中，減速器必須等待映射完成，否則排序?qū)⒉徽_。為了看看是什么使機器學(xué)習(xí)的依存結(jié)構(gòu)獨特，讓我們在方程(3)中考慮套索回歸的例子。乍一看，這個ΔLasso更新方程(6)可能看起來可以并行執(zhí)行，但這只是部分正確。更仔細的審視

表明，對于第j個模型參數(shù)Aj，其更新取決于(t - 1)。換句話說，潛在的每個其他參數(shù)Ak都是可能的相關(guān)因素，因此模型參數(shù)A的更新順序?qū)C器學(xué)習(xí)程序的進程甚至正確性都會產(chǎn)生影響[39]。甚至還有一個在以操作為中心的程序中不存在的額外的細微差別：套索參數(shù)的相關(guān)因素不是二進制的(即不僅是“上”或“下”)，但可以通過機器學(xué)習(xí)程序狀態(tài)和輸入數(shù)據(jù)進行軟賦值和影響。注意，如果= 0 (即數(shù)據(jù)列j與列k之間沒有相關(guān)性)，則Aj和Ak互相不存在相關(guān)性，并且可以安全地并行更新[39]。同樣，即使＞ 0，只要Ak= 0，那么Aj就不取決于Ak。這樣的依存結(jié)構(gòu)不受機器學(xué)習(xí)程序所限；對LDA主題模型更新方程(8)的仔細審視可以表明，吉布斯采樣器更新xij(文檔i中的單詞記號j)取決于：①所有其他文件i中的單詞記號，和②其他文件a中代表相同單詞(即xij= xab)的所有其他單詞記號b[25]。如果這些機器學(xué)習(xí)程序的依存結(jié)構(gòu)沒有被遵守，結(jié)果或者是用額外的機器(如用4×同樣的機器得到＜ 2×加速)達到次理想的縮放比例[25]，甚至是壓倒機器學(xué)習(xí)程序固有誤差的完全的程序失敗[39]。

機器學(xué)習(xí)程序的第三個特性是不均勻收斂，觀察發(fā)現(xiàn)并非所有的模型參數(shù)Aj都將在相同數(shù)量的迭代后收斂至其最佳值A(chǔ)j*——一種在單通道算法如MapReduce排序中出現(xiàn)的特性。在套索例子的方程(3)中，r(A)項促使模型參數(shù)Aj正好為零，實證發(fā)現(xiàn)，一旦參數(shù)在算法的執(zhí)行過程中成為零，那它是不可能恢復(fù)到一個非零的值[39]。換句話說，成為零的參數(shù)已經(jīng)(以雖然不是100%的高概率)收斂。這表明，通過對參數(shù)更頻繁地執(zhí)行ΔLasso，計算可能更優(yōu)先向其仍然非零進行——這個策略的確降低了機器學(xué)習(xí)程序完成所花費的時間[39]。類似的不均勻收斂已在PageRank——另一種迭代收斂的算法中得到觀察和利用[53]。

最后，值得注意的是，機器學(xué)習(xí)程序的一個子集具有緊湊的更新，經(jīng)過仔細審視，發(fā)現(xiàn)更新ΔLasso比矩陣參數(shù)|A|的尺度明顯縮小。在套索[方程(3)]和LDA主題模型[47]中，更新ΔLasso由于數(shù)據(jù)中的稀疏結(jié)構(gòu)，通常只接觸到模型參數(shù)的一小部分。另一個突出的例子是“矩陣參數(shù)化”模型，其中，A是一個矩陣(就像在深度學(xué)習(xí)中一樣[54])，但個別更新ΔLasso可以被分解成幾個小的載體(一種所謂的“低等級”的更新)。如果分布式機器學(xué)習(xí)系統(tǒng)在設(shè)計中將它考慮進去，那么這種緊湊可以大大減少存儲、計算和通信成本，帶來數(shù)量級上的加速[55,56]。

2.2.論數(shù)據(jù)與模型并行性

對于涉及百萬兆字節(jié)數(shù)據(jù)、擁有上至數(shù)萬億模型參數(shù)的復(fù)雜機器學(xué)習(xí)程序的機器學(xué)習(xí)應(yīng)用，使用單一的臺式機或筆記本電腦來執(zhí)行往往需要數(shù)天或數(shù)周時間[20]。這種計算瓶頸促使了許多機器學(xué)習(xí)程序用集群并行執(zhí)行的分布式系統(tǒng)的發(fā)展[33-36]。機器學(xué)習(xí)程序通過在數(shù)據(jù)x或模型上A細分更新ΔL來并行執(zhí)行——分別稱為數(shù)據(jù)并行性和模型并行性。

需要注意的是，這兩種類型的并行分別是互補和非對稱互補的，因為同步數(shù)據(jù)和模型并行性是可能的(在某些情況下甚至是必要的)和非對稱的，而數(shù)據(jù)并行性一般可應(yīng)用于任何在數(shù)據(jù)樣本x1,..., xN中具有獨立同分布(i.i.d.)假設(shè)的機器學(xué)習(xí)程序。這樣獨立同分布的機器學(xué)習(xí)程序(從深度學(xué)習(xí)到邏輯回歸、主題建模和其他許多方面)占據(jù)了大部分的實際機器學(xué)習(xí)使用，很容易通過目標(biāo)L中的數(shù)據(jù)指標(biāo)i求和驗證[如套索方程(3)]。因此，當(dāng)一個主力算法技術(shù)(如SGD)應(yīng)用于L，得到的更新方程ΔL也將對i求和，這可以很容易地用多臺機器并行處理，尤其是當(dāng)數(shù)據(jù)樣本數(shù)量N達到數(shù)百萬或數(shù)十億時。相反，模型并行性需要特殊注意，因為模型參數(shù)Aj并不總是能符合這種方便的獨立同分布假設(shè)(圖1)——因此，哪些參數(shù)Aj是并行更新的，以及更新ΔL所發(fā)生的順序，可以導(dǎo)致多種結(jié)果：從用P臺機器達到接近理想的P次加速，到?jīng)]有用額外的機器帶來額外的加速，甚至徹底的程序失敗。先前討論的套索依存結(jié)構(gòu)(2.1部分)是模型參數(shù)的非獨立同分布性質(zhì)的一個很好的例子。現(xiàn)在讓我們分別討論數(shù)據(jù)和模型并行的一般數(shù)學(xué)形式。

(1)數(shù)據(jù)并行。在數(shù)據(jù)并行機器學(xué)習(xí)執(zhí)行中，數(shù)據(jù)x = {x1,...,xN} 被劃分和分配到并行計算的執(zhí)行器或機器上(按p = 1,..., P索引)；我們可以用xp表示第p個數(shù)據(jù)分區(qū)。如果更新函數(shù)ΔL對數(shù)據(jù)樣本i求最外層的總和(與平常的對數(shù)據(jù)獨立同分布假設(shè)的機器學(xué)習(xí)程序一樣)，我們就可以將ΔL進行數(shù)據(jù)子集的劃分，并獲得數(shù)據(jù)的并行更新方程，其中,ΔL(A(t - 1), xp)由第p個并行執(zhí)行器執(zhí)行：

圖1.數(shù)據(jù)和模型并行性之間的差異：數(shù)據(jù)樣本總是有條件獨立的給定模型，但有一些模型參數(shù)不是相互獨立的。

(2)模型并行性。在模型并行的機器學(xué)習(xí)執(zhí)行中，模型A被劃分和分配給執(zhí)行器/機器p = 1,..., P，并通過運行并行更新函數(shù)ΔL在其中更新。與數(shù)據(jù)并行性不同，每個更新函數(shù)ΔL也需要調(diào)度或選擇函數(shù)Sp,(t-1)，這也就限制了ΔL對一組模型參數(shù)A子集的操作(一個基本的用途是為了防止不同的執(zhí)行器試圖更新同一些參數(shù))：

其中，我們省略了數(shù)據(jù)x，因為它沒有被劃分。Sp,(t-1)輸出一組指數(shù){j1, j2,...}，所以ΔL只在Aj1, Aj2,...執(zhí)行更新；我們將這樣的模型參數(shù)選擇稱為調(diào)度。模型參數(shù)Aj在一般情況下都不是相互獨立的，可以確定的是模型并行算法只有當(dāng)每個迭代并行更新被限制為一組相互獨立(或弱相關(guān))參數(shù)的子集時，可由Sp,(t-1)表示，才是有效的 [39,57-59]。

套索塊坐標(biāo)下降更新[方程(6)]能夠以一個簡單模型并行形式被容易地編寫。在這里，Sp,(t-1)為執(zhí)行器p在每次迭代選擇同一組固定參數(shù)，我們稱為 jp1,..., jpmp：

總之，劃分?jǐn)?shù)據(jù)樣本和模型參數(shù)(xi, Aj)的空間成不相交的塊，同時數(shù)據(jù)和模型并行性也是可能的。為了用P機器達到幾乎完美的加速，LDA主題模型的吉布斯抽樣方程[方程(8)]可以用這樣一種塊方式被劃分(圖2)[25]。

3.機器學(xué)習(xí)系統(tǒng)設(shè)計原則

機器學(xué)習(xí)程序的獨特性質(zhì)，再加上數(shù)據(jù)和模型并行性的互補策略，相互作用下會產(chǎn)生超出了由一般迭代收斂的更新方程(2)代表的理想數(shù)學(xué)觀的設(shè)計考慮的復(fù)雜空間。在這種理想的觀點下，我們希望Δ和F函數(shù)簡單地需要平衡方程式(之前給出的套索回歸數(shù)據(jù)和模型并行方程)來實現(xiàn)，然后由一個廣泛目的的分布式系統(tǒng)執(zhí)行——例如，如果我們選擇了一個MapReduce抽象，就能編寫Δ作為地圖，F(xiàn)作為Reduce，之后再使用一種系統(tǒng)，如Hadoop或Spark來執(zhí)行它們。然而，現(xiàn)實是最高性能機器學(xué)習(xí)的實現(xiàn)并非是建立在這樣一種樸素的方式上；此外，它們還往往出現(xiàn)在機器學(xué)習(xí)的專業(yè)系統(tǒng)中，而不是廣泛目的的MapReduce系統(tǒng)中[26,31,35,36]。原因是，高性能的機器學(xué)習(xí)遠遠超過了理想化的類MapReduce觀點，并涉及并非在數(shù)學(xué)方程中顯而易見的眾多因素：對諸如用于數(shù)據(jù)并行性的數(shù)據(jù)批量大小，如何出于模型并行性進行模型劃分，何時在執(zhí)行器之間同步模型視圖，算法的步長梯度選擇，甚至是執(zhí)行Δ更新的順序等的考慮。

對機器學(xué)習(xí)性能空間的考慮即使對資深從業(yè)人員來說也可能是有難度的，我們的觀點是，一個并行機器學(xué)習(xí)的系統(tǒng)接口是必要的，既便于對機器學(xué)習(xí)注意事項的組織性、科學(xué)性的研究，也能將這些注意事項安排到一系列開發(fā)新的分布式機器學(xué)習(xí)系統(tǒng)的高層次原則。作為安排這些原則的第一步，我們會將其根據(jù)四個層次的問題進行劃分：如果一個機器學(xué)習(xí)程序方程[方程(2)]告訴系統(tǒng)“計算什么”，然后系統(tǒng)就必須考慮：①如何分配計算；②如何將計算與機器之間的通信連接起來；③機器之間如何通信；還有④通信的對象是什么。通過系統(tǒng)地解決在每一個問題上機器學(xué)習(xí)的注意事項，我們認(rèn)為建立彼此補充和增益，并組裝成一個在機器學(xué)習(xí)程序執(zhí)行時間上獲得數(shù)量級加速的完整分布式機器學(xué)習(xí)系統(tǒng)的子系統(tǒng)是可行的。

圖2.LDA主題模型中同步數(shù)據(jù)和模型并行性高水平的說明。在這個例子中，三個并行的執(zhí)行器在數(shù)據(jù)/模型塊 在迭代1中操作，然后在迭代2中轉(zhuǎn)移到塊等。

3.1.如何分配：調(diào)度和平衡工作負載

為了并行化一個ML程序，我們首先必須確定如何最好地將其劃分成多個任務(wù)——也就是說，我們必須將方程(2)中的單片Δ按照數(shù)據(jù)并行的形式[方程(9)]或模型并行的形式[方程(11)]，劃分為一組平行的任務(wù)——甚至一種更復(fù)雜的混合形式。之后我們?yōu)榱嗽谟邢薜腜執(zhí)行器或機器池上執(zhí)行，必須安排和平衡這些任務(wù)，那就是：①決定哪些任務(wù)并行在一起(更重要的是，其任務(wù)不應(yīng)該被并行執(zhí)行)；②決定任務(wù)將被執(zhí)行的順序；以及③同時確保每臺機器分配的工作負荷均衡。

這三個決定已在以操作為中心程序的背景下經(jīng)過了仔細研究(如MapReduce排序的例子)，帶來了如Hadoop和Spark中使用的調(diào)度系統(tǒng)[34]。這樣的以操作為中心的調(diào)度系統(tǒng)或許與不同的執(zhí)行計劃相結(jié)合——決定①～③的結(jié)合——取決于集群的配置、現(xiàn)有的工作負荷，甚至機器故障；然而更重要的是，它們確保以操作為中心的程序結(jié)果是完全一致，且每次是可重復(fù)的。然而，對于機器學(xué)習(xí)迭代收斂的程序，目標(biāo)不是完美可重復(fù)的執(zhí)行，而是模型參數(shù)A收斂至目標(biāo)函數(shù)L的最優(yōu)(即A以一個小的距離ε接近最佳值A(chǔ)*)。因此，我們要制定一個調(diào)度策略，其執(zhí)行計劃允許機器學(xué)習(xí)程序可以每次以同樣的收斂性終止——我們把這個稱為對于機器學(xué)習(xí)程序的“正確執(zhí)行”。這樣的策略之后可以被實現(xiàn)為一個調(diào)度系統(tǒng)，它能夠創(chuàng)建不同于以操作為中心的機器學(xué)習(xí)程序執(zhí)行計劃。

(1)機器學(xué)習(xí)程序中的依存結(jié)構(gòu)。為了產(chǎn)生一個對于機器學(xué)習(xí)程序正確的執(zhí)行計劃，有必要了解機器學(xué)習(xí)程序有著怎樣的內(nèi)部依存關(guān)系，以及如何通過單純的并行化打破或違反這些依存關(guān)系以減緩收斂。不同于以操作為中心的程序比如排序，機器學(xué)習(xí)程序具有容錯性，并能自動地從數(shù)量有限的違反函數(shù)依賴的數(shù)據(jù)中恢復(fù)，但太多的違反會增加收斂所需要的迭代數(shù)量，使并行機器學(xué)習(xí)程序利用P機器的加速未達最佳標(biāo)準(zhǔn)、達不到P次階。讓我們通過套索和LDA主題模型的實例程序，了解這些依存關(guān)系。在套索模型的并行版本[方程(12)]，每個并行執(zhí)行器p∈{1,…, P}執(zhí)行一個或更多(t - 1)形式的ΔLasso計算，之后可以用于更新Aj。注意到這個計算通過(t - 1)項依存于所有其他參數(shù)Ak, k ≠ j ，依存關(guān)系的量級與第j項和第k項的數(shù)據(jù)維度之間的相關(guān)性，以及參數(shù) Ak(t - 1)的當(dāng)前值成正比。在最壞的情況下，相關(guān)性和Ak(t - 1)都可能很大，因此順序更新Aj, Ak(即在兩個不同的迭代中t, t + 1)會導(dǎo)致與并行更新(即同時在迭代t中)不同的結(jié)果。文獻[57]指出，如果相關(guān)性大，則并行更新將比順序更新需要更多的迭代收斂。它直觀地表明，我們不應(yīng)該“浪費”計算來試圖并行更新高度相關(guān)的參數(shù)；相反，我們應(yīng)該尋求為并行更新調(diào)度非相關(guān)的參數(shù)組，同時對相關(guān)參數(shù)進行順序更新[39]。

對于LDA主題模型，讓我們來回憶一下ΔLDA更新[方程(8)]：對于每個單詞記號wij(在文件i的位置j)，LDA吉布斯采樣器更新模型參數(shù)B、δ(A的一部分)的四個要素：Bkold,wij(t - 1) - =1，Bknew,wij(t - 1) + =1，δi,kold(t - 1) - =1，以及δi,knew(t - 1) + =1，其中，kold= zij(t - 1)且 knew= zij(t - 1)～ P(zij|xij, δi(t - 1), B(t - 1))。這些方程產(chǎn)生不同單詞記號wij和 wuν之間的依存關(guān)系。其中一個明顯的依存關(guān)系出現(xiàn)在wij= wuν，導(dǎo)致了它們將更新與B相同要素的可能(這發(fā)生在kold或knew對于兩個記號相同時)。此外，在條件概率P(zij|xij, δi(t - 1), B (t - 1))中還有更復(fù)雜的依存關(guān)系，為了使本文保持在一個適當(dāng)?shù)母叨?，我們可以總結(jié)指出元素在列B·,ν中是相互依存的，而在δ行即δi,·要素，也是互相依存的。由于這些錯綜復(fù)雜的依賴關(guān)系，高性能并行LDA主題模型需要同步數(shù)據(jù)和模型并行策略(圖2)，其中，單詞記號wij必須由其值ν = wij和文件i仔細分組，以避免違反在B和δ中列/行的依存關(guān)系[25]。

(2)機器學(xué)習(xí)程序中的調(diào)度。根據(jù)這些依存關(guān)系，我們?nèi)绾卧诒M可能避免違反依存結(jié)構(gòu)(注意由于機器學(xué)習(xí)的容錯性，我們并非必須避免所有的依存關(guān)系)的程度上調(diào)度更新Δ——然而同時，難道由于缺乏任務(wù)或負荷的不平衡就不留下任何的P執(zhí)行器機器閑置嗎？這兩種考慮會對機器學(xué)習(xí)程序執(zhí)行時間有不同但互補的影響：避免違反依存關(guān)系，防止每次機器學(xué)習(xí)程序的迭代相比于順序執(zhí)行的降級(即該程序?qū)⒉恍枰嗟牡諗?，而保持執(zhí)行器機器完全從事有用的計算，能夠確保來自P機器的迭代吞吐量(每秒執(zhí)行的迭代)是單一機器的接近P倍?？傊跬昝赖腜次機器學(xué)習(xí)加速來自于將每次迭代(相當(dāng)于順序執(zhí)行)近乎理想的進程與近乎理想的迭代吞吐量(P倍順序執(zhí)行)結(jié)合起來。因此，我們希望有一個達到這兩個目標(biāo)的理想的機器學(xué)習(xí)調(diào)度策略。

為了解釋理想化的調(diào)度是如何實現(xiàn)的，我們回到運行套索和LDA的例子。在套索例子中，Aj和Ak這兩個參數(shù)相互依存的程度是由在第j個和第k個特征維度之間的相關(guān)性影響——我們把這個和其他類似的操作稱作一種依存關(guān)系的檢查。對于一個小的閾值κ，如果＜ κ，那么Aj和Ak會彼此影響不大。因此，理想的調(diào)度策略是找到所有滿足＜ κ的參數(shù)對(j, k)，之后劃分參數(shù)指標(biāo)j∈{1,..., m}為獨立子集A1, A2,...——其中，Aa和Ab兩個亞子集被認(rèn)為是獨立的，如果任何j∈Aa而任何k∈Ab，我們就會有＜ κ。這些子集A之后可以被安全地分配到并行執(zhí)行器機器(圖3)，而每臺機器將順序更新參數(shù)j∈A(這樣防止違反依存關(guān)系)[39]。

至于LDA，仔細審視可以發(fā)現(xiàn)，對于單詞記號wij[方程(8)]，更新方程ΔLDA可能觸及列B·,wij的任何要素以及行δi,·的任何要素。為了防止并行執(zhí)行器機器在同一行/列B和δ上操作，我們必須將單詞{1,..., V}的空間(對應(yīng)列B)劃分至P子集V1,..., VP，也要劃分文件{1,..., N}的空間(對應(yīng)行δ)至P子集D1,…, DP。我們現(xiàn)在可以進行理想的數(shù)據(jù)和模型并行化如下：首先，我們把文件子集Dp從P機器中分配至p機器；然后，每臺機器只有吉布斯采樣單詞記號wij，使得i∈Dp,wij∈Vp。一旦所有的機器完成工作，它們彼此輪換單詞子集Vp，從而p機器現(xiàn)在可以吉布斯采樣wij，使得i∈Dp，wij∈Vp+1(或?qū)τ赑機器，wij∈V1)。這個過程一直持續(xù)到P次輪換完成，此時迭代完成(每個單詞記號已采樣)[25]。圖2說明了這個過程。

圖3.理想的套索調(diào)度圖解，其中的參數(shù)對(j, k)被分為子集(紅色塊)且不同子集中參數(shù)之間的相關(guān)性低。多個子集可以被多執(zhí)行器機器并行更新，這就避免了違反依存結(jié)構(gòu)，因為執(zhí)行器順序更新每個子集中的參數(shù)。

在實踐中，如以上所描述的理想的調(diào)度可能并不切實可行。例如，在套索中，為所有O(m2) 對(j, k)進行的計算對于有較大m(數(shù)百萬到數(shù)十億)的高維問題十分棘手。在介紹感知結(jié)構(gòu)的并行化(SAP)——一種可以被快速計算的接近理想的可行調(diào)度策略時，我們很快就會回到這個問題。

(3)機器學(xué)習(xí)程序中的計算優(yōu)先化。因為機器學(xué)習(xí)程序表現(xiàn)出非均勻參數(shù)收斂，一個機器學(xué)習(xí)調(diào)度器就有機會優(yōu)先慢收斂參數(shù)Aj，從而促進機器學(xué)習(xí)算法的每次迭代過程(即因為它需要更少的迭代收斂)。例如，在套索中，經(jīng)驗觀察到稀疏性誘導(dǎo)的l1范數(shù)[方程(4)]使大多數(shù)參數(shù)Aj幾次迭代后完全變?yōu)榱?，而之后它們不太可能再變?yōu)榉?。剩下的參數(shù)，通常是一小部分，則需要更長時間來收斂(如超過10倍的迭代)[39]。

一個通用但有效的優(yōu)化策略是以其平方變化率的概率比例[Aj(t - 1) - Aj(t - 2)2+ ε，其中，ε是一個保證固定參數(shù)仍有機會被選擇到的很小的常數(shù)]來選擇參數(shù)Aj。根據(jù)快收斂和慢收斂參數(shù)的比例，此優(yōu)化策略可以導(dǎo)致套索回歸需要進行的收斂次數(shù)呈數(shù)量級地減少[39]。類似的策略已經(jīng)應(yīng)用到另一個迭代收斂算法PageRank中[53]。

(4)在機器學(xué)習(xí)程序中平衡工作負荷。在用分布式集群執(zhí)行機器學(xué)習(xí)程序時，為了交換參數(shù)更新，它們可能不得不停止，即同步——例如，在Hadoop和Spark中的Map和Reduce階段結(jié)束時。為了減少花在等待上的時間，對每臺機器上的工作進行負荷平衡是可取的，以使得它們繼續(xù)以接近相同的速度推進。這對于可能會出現(xiàn)扭曲的數(shù)據(jù)分布的機器學(xué)習(xí)程序尤其重要；例如，在LDA主題模型中，單詞記號wij以冪律方式分布，其中一些單詞會出現(xiàn)在許多文件里，而其他大多數(shù)單詞會很少出現(xiàn)。一個典型的機器學(xué)習(xí)負荷均衡策略可以應(yīng)用在計算機科學(xué)中的經(jīng)典裝箱算法(每個執(zhí)行器機器都是要包裝的“箱”之一)，或任何其他以操作為中心的分布式系統(tǒng)如Hadoop和Spark工作的策略。

然而，不太起眼的第二個挑戰(zhàn)是，機器的性能可能由于微妙的原因，諸如改變數(shù)據(jù)中心溫度、機械故障、背景工作或者其他用戶等在實際集群中發(fā)生波動。因此，預(yù)定在一次迭代開始的負荷均衡策略，會經(jīng)常遭遇落后者，即隨機變得比集群的其他部分慢的機器，當(dāng)一次迭代結(jié)束、運行參數(shù)同步時其他所有的機器必須等待這些機器[37,40,60]。解決這個問題的一個簡單方法是應(yīng)用慢速執(zhí)行器的不可知論[38]，即系統(tǒng)直接利用機器學(xué)習(xí)算法的迭代收斂性，并允許更快的執(zhí)行器在等待落后者趕上來的時候重復(fù)其更新Δ。這不僅解決了落后者的問題，甚至可以糾正不完美均衡的工作負荷。我們注意到的另一個解決方案是使用有界的異步執(zhí)行(而不是同步的MapReduce式執(zhí)行)，在3.2中將更詳細地討論這一方案。

(5)結(jié)構(gòu)感知并行化。調(diào)度、優(yōu)先次序和負荷均衡彼此互補又相互纏結(jié)；參數(shù)Aj優(yōu)先級的選擇會影響依存關(guān)系需要執(zhí)行哪些調(diào)度，反過來，調(diào)度產(chǎn)生的“獨立子集”可使負荷均衡問題變得更困難或更簡單。這三個功能可以被組合成一個單一的編程抽象概念，作為機器學(xué)習(xí)分布式系統(tǒng)的一部分被實施。我們稱這種抽象概念為結(jié)構(gòu)感知的并行化(SAP)，其中，機器學(xué)習(xí)程序員可以指定如何：①優(yōu)先處理參數(shù)來加快收斂速度；②對這些參數(shù)執(zhí)行依存關(guān)系檢查，并安排其至獨立子集中；③在執(zhí)行器機器中對獨立子集進行負荷均衡。SAP提供了一個簡單的MapReduce類編程接口，機器學(xué)習(xí)程序員能在接口上實現(xiàn)三個功能：①“調(diào)度()”，其中，一小部分參數(shù)被優(yōu)先考慮，之后接觸到依存關(guān)系檢查；②“推()”，在執(zhí)行器機器上并行執(zhí)行ΔL；③“拉()”，執(zhí)行F。負荷均衡是由SAP執(zhí)行通過結(jié)合經(jīng)典裝箱算法和慢速執(zhí)行器不可知論自動處理。

重要的是，SAP 調(diào)度()不單純執(zhí)行O(m2)依存關(guān)系檢查；相反，一些參數(shù)A是首先通過優(yōu)先考慮(當(dāng)A＜＜m)而被選擇。之后對A進行依存關(guān)系檢查，由此產(chǎn)生的獨立子集通過推()和拉()被更新。這樣，SAP每次調(diào)度()，推()和拉()的迭代都只更新幾個參數(shù)Aj，而不是完整的模型A。這個策略被證明對于一類廣泛的模型并行性機器學(xué)習(xí)程序來說接近理想化。

定理1(改編自參考文獻[35])：SAP接近了理想化的執(zhí)行。考慮形式的目標(biāo)函數(shù)是可分的，A∈Rd和f在下列意義上有 β-Lipschitz 連續(xù)梯度：

設(shè)X = [x1,...,xd]是重新表示為d個特征向量的數(shù)據(jù)樣本。W.l.o.g.（不失一般性），我們假設(shè)每個特征向量xi歸一化，即因此，對于所有的i和j，

假設(shè)我們想通過模型并行坐標(biāo)下降盡量減少L。設(shè)Sideal()是總能提出零相關(guān)的P隨機特征的Oracle(即理想化)的調(diào)度。設(shè)作為它的參數(shù)軌跡，并設(shè)為SAP調(diào)度的參數(shù)軌跡。那么，對常數(shù)C，m，L和P?：

這個定理說明SSAP()參數(shù)預(yù)測ASAP與理想Oracle預(yù)測Aideal之間的差異會以一個快速的1/(t + 1)2= O(t-2) 比率迅速消失。換句話說，誰也不能做得比SSAP()調(diào)度好很多——它已經(jīng)接近最優(yōu)了。

SAP的慢速執(zhí)行器不可知論負荷均衡還帶來一種理論性能保證——它不僅保留正確的機器學(xué)習(xí)收斂，還會促進單純調(diào)度下每次迭代的收斂。

定理2(改編自參考文獻[38])：SAP慢速執(zhí)行器不可知論促進了每次迭代的收斂。設(shè)模型中當(dāng)前的方差(直觀地說就是不確定性)是Var (A)，設(shè)np＞ 0是由執(zhí)行器p進行更新的數(shù)量(包括由于慢速執(zhí)行器不可知論的附加更新)。在np更新后，Var (A)降低至其中，ηt＞0，是當(dāng)t→∞時接近零的步長參數(shù)；c1, c2, c3＞ 0，是特異性問題的常數(shù)；L是該機器學(xué)習(xí)目標(biāo)函數(shù)L的隨機梯度；CoVar(a, b)是a和b之間的協(xié)方差；O(cubic)代表迅速向零收縮的三階或更高的項。

一個較低的方差Var (A)表明，機器學(xué)習(xí)程序接近收斂(因為參數(shù)A已經(jīng)快速地停止變化)。上述定理表明，額外的更新np確實降低了方差——因此，機器學(xué)習(xí)程序的收斂得到了加速。為了理解為什么是這樣的情況，我們注意到第二和第三項總是為負；此外，它們是O(ηt)，所以支配了為正的第四項[即O(并因此更快地縮小到零]以及為正的第五項(第三階甚至比第四項收縮更快)。

根據(jù)經(jīng)驗，SAP系統(tǒng)能夠在非調(diào)度、非均衡的分布式機器學(xué)習(xí)系統(tǒng)上實現(xiàn)數(shù)量級的速度提升。一個例子是轉(zhuǎn)換系統(tǒng)[39]，它實現(xiàn)了多種算法的SAP調(diào)度，比如套索回歸、矩陣分解，以及LDA主題模型，并且相比于其他系統(tǒng)實現(xiàn)了出色的收斂次數(shù)(圖4)。

3.2.如何連接計算和通信：橋連模型和有限異步性

許多并行程序要求執(zhí)行機器可以互相交換程序狀態(tài)。例如，諸如Hadoop的MapReduce系統(tǒng)接受由所有Map(映射)執(zhí)行器產(chǎn)生的鍵值對 (a, b) ，然后將所有擁有鍵a的鍵值對傳給同一個Reduce(歸約)執(zhí)行器。對于以操作為中心的程序來說，這一步的執(zhí)行必須準(zhǔn)確無誤?；叵隡apReduce分類的例子(第二部分)，由于鍵傳給了不同的Reducer，結(jié)果導(dǎo)致了分類錯誤。BSP并行編程中的操作準(zhǔn)確性這一概念由BSP模型支撐[61,62]。BSP模型是一種橋連模型，它抽象地展示了并行程序計算是如何與執(zhí)行器間的通信相交錯的。采用BSP橋連模型的程序在計算階段和通信階段或同步柵欄(synchronization barrier)(圖5)間切換，且在下一個同步障礙完成前，每個計算階段的影響對執(zhí)行機器是不可見的。

由于BSP模型清楚地分離了計算階段和通信階段，許多在BSP下運行的并行機器學(xué)習(xí)程序是可序列化的。也就是說，它們等同于順序機器學(xué)習(xí)程序。序列化BSP機器學(xué)習(xí)程序可以保證所有順序隊列的正確性，這使得BSP成為頗受以操作為中心的程序以及機器學(xué)習(xí)程序歡迎的橋連模型[32,34,63]。BSP的一個缺點是，執(zhí)行器必須互相等待進入下一個同步柵欄。這意味著高效的BSP執(zhí)行對負載均衡有嚴(yán)苛的要求。但是，即使是非常均衡的工作負載也會成為一些“問題機器”的犧牲品——這些機器變得比其余機器緩慢，這是隨機和不可預(yù)測的[60]，是由于真實世界的一些條件，諸如數(shù)據(jù)中心的溫度波動、網(wǎng)絡(luò)擁塞以及其他用戶的程序或后臺任務(wù)。發(fā)生這種情況時，為了配合最慢的機器，程序的效率就會降低——而在擁有上千部機器的機群里，這樣的問題機器可能有許多。第二個缺點是，執(zhí)行器間的通信不是瞬時的，所以同步柵欄本身需要大量的時間。例如，LDA(Latent Dirichlet Allocation)主題模型在BSP下運行于32臺機器上時，同步柵欄所需時間至多可以達到迭代的6倍[37]。由于這兩個缺點，BSP機器學(xué)習(xí)程序的迭代吞吐量很低，即P臺機器并不能帶來P倍吞吐量的增加。

圖4.三種機器學(xué)習(xí)程序目標(biāo)函數(shù)L的進展的時間圖表比較——(a) 套索回歸(1億條特征、9臺機器)，(b) 矩陣分解(MF)(80個秩、9臺機器)，(c) 隱含Dirichlet分配(LDA)主題建模(250萬詞匯、5 000個主題、32臺機器)——在實現(xiàn)了結(jié)構(gòu)感知并行化系統(tǒng)(SAP)的抽象概念的系統(tǒng)Strads下執(zhí)行。通過使用SAP促進機器學(xué)習(xí)算法每次迭代的過程，Strads相比其他通用和專用目的的實施工具——套索-RR(又名獵槍算法)、GraphLab和YahooLDA實現(xiàn)了更快的收斂時間(更陡峭的曲線)。改編自參考文獻[39]。

作為在BSP上運行機器學(xué)習(xí)程序的一種替代，人們又研發(fā)了異步并行執(zhí)行模型(圖6)[28,33,52]。在這一模型中，執(zhí)行機器無需互相等待，而是在每次迭代進程中交換模型信息。異步執(zhí)行可以獲得近乎理想的P倍吞吐量增加。但是和BSP(能夠確保可序列化性以及機器學(xué)習(xí)程序準(zhǔn)確性)不同，異步并行每個迭代的收斂進程會減弱。原因是異步通信會使模型信息變得延后或過時(因為機器不需要互相等待)，這反過來會造成Δ和F計算的錯誤。錯誤的大小隨信息的延后而增加。如果不仔細約束這些延遲，會導(dǎo)致收斂極其緩慢，甚至錯誤[37,40]。在某種意義上，沒有“免費的午餐”——模型信息的通信必須在執(zhí)行器間及時進行。

BSP和異步執(zhí)行在實現(xiàn)理想化的P倍機器學(xué)習(xí)程序加速中面臨著不同的挑戰(zhàn)——從經(jīng)驗出發(fā)，BSP機器學(xué)習(xí)程序難以實現(xiàn)理想化的P倍迭代吞吐量增加，而異步機器學(xué)習(xí)程序則很難保持順序機器學(xué)習(xí)程序中每個迭代的理想化進程[25,37,40]。有限異步執(zhí)行有望解決這一問題，在該模型中異步執(zhí)行被加以限制。為了更好地探索這一想法，我們展示了一種在BSP基礎(chǔ)上提升而來的橋連模型，稱為“過時同步并行”(stale synchronous parallel / SSP)[37,64]。

圖5.整體同步并行(bulk synchronous parallel, BSP)橋連模型。在機器學(xué)習(xí)程序中，執(zhí)行機器等在每次迭代結(jié)束時，在同步柵欄階段中交換參數(shù)A的信息。

圖6.異步并行執(zhí)行模型。運行機器學(xué)習(xí)程序的機器無需互相等待。模型參數(shù)Aj的信息交換在執(zhí)行器間異步持續(xù)進行。由于執(zhí)行器無需等待，所以存在一個風(fēng)險，即某臺機器可能多次迭代、結(jié)束得比其他機器緩慢，這可能會給機器學(xué)習(xí)程序帶來不可恢復(fù)的錯誤。而BSP系統(tǒng)由于其同步柵欄而不會發(fā)生這種情況。

過時同步并行(SSP)是一種有限異步橋連模型，它擁有與常見的BSP橋連模型相似的編程接口。一個直觀高端的闡釋如下：我們有P個并行執(zhí)行器或機器以迭代的方式進行機器學(xué)習(xí)計算Δ和F。在每次迭代t結(jié)束時，SSP 執(zhí)行器發(fā)出信號告知它們已完成迭代。在這一節(jié)點上，如果執(zhí)行器是在BSP下運行，同步柵欄就會啟動進行機器間的通信。但是，SSP則不會發(fā)生同步柵欄，而是以其認(rèn)為合適的方式選擇停止或允許執(zhí)行器繼續(xù)進行下去；更具體地說，如果該執(zhí)行器有多于s個迭代先于其他執(zhí)行器，SSP就會停止它，這個s稱為過時閥值(staleness threshold)(圖7)。

更正式一點的說法是，在SSP下，每個執(zhí)行機器都有一個迭代計數(shù)t和模型參數(shù)A的本地視圖。SSP執(zhí)行機器“提交”它們的更新Δ，然后調(diào)用一個clock() 函數(shù)，該函數(shù)：① 發(fā)出信號告知迭代已結(jié)束，② 增加迭代計數(shù)t，③通知SSP系統(tǒng)將Δ信息傳送給其他機器，這樣它們就可以更新關(guān)于A的本地視圖。這個clock() 和BSP的同步柵欄類似，不同的是，來自一個執(zhí)行器的更新不需要立即傳遞給其他執(zhí)行器——這就使執(zhí)行器即使只收到更新的部分子集，也可以繼續(xù)工作。這意味著，如果一些更新尚未接收，A的本地視圖可能變得過時。給定一個用戶選擇的過時閥值s ≥ 0，SSP實現(xiàn)或系統(tǒng)至少會強制執(zhí)行以下有限過時條件：

(1) 有限clock差值：最慢的執(zhí)行器和最快的執(zhí)行器之間的迭代計數(shù)差值必須≤ s，否則SSP會強制最快的執(zhí)行器等最慢的執(zhí)行器趕上來。

(2) 加上時間戳記的更新：每次迭代結(jié)束時t[就在調(diào)用clock()前]，每個執(zhí)行器提交一個更新Δ，該更新用時間戳記t進行標(biāo)記。

圖7.過時同步并行(SSP)橋連模型。和BSP相比，運行機器學(xué)習(xí)語言的執(zhí)行機器可以互相領(lǐng)先，直至相隔s個迭代(這里s被稱為過時閾值)。領(lǐng)先太多的執(zhí)行器會被強制停止，直到落后的執(zhí)行器趕上來。和異步并行執(zhí)行模型一樣，模型參數(shù)Aj的信息交換在執(zhí)行器間異步持續(xù)進行(加進來一些附加條件以保證機器學(xué)習(xí)收斂的正確性)，無需進行同步柵欄。SSP的優(yōu)點是它大多數(shù)時間是像異步并行執(zhí)行一樣運行，但卻可以根據(jù)需要停止執(zhí)行器以保證機器學(xué)習(xí)執(zhí)行的正確性。

(3) 模型狀態(tài)保證：當(dāng)一個執(zhí)行器以clock t計算Δ時，保證其關(guān)于A的本地視圖包含所有時間戳記≤ t - s - 1。本地視圖可能包含也可能不包含其他機器時間戳記＞ t - s - 1的更新Δ。

(4) 自我寫入讀?。好總€執(zhí)行器會一直將自己的更新Δ包含進A的本地視圖中。

因為最快的執(zhí)行器和最慢的執(zhí)行器相隔≤ s個clock，迭代t時執(zhí)行器的A本地視圖會包含所有時間戳記在區(qū)間[0, t - s - 1]內(nèi)的執(zhí)行器的更新，以及部分(也有可能沒有)時間戳記在[t - s, t+ s - 1]范圍的更新。注意，SSP是BSP模型針對機器學(xué)習(xí)程序的一種嚴(yán)格泛化：當(dāng)s = 0時，第一個范圍就變成了[0, t - 1]，而第二個區(qū)間則空了，這就和一個機器學(xué)習(xí)程序的BSP執(zhí)行完全一樣了。

因為SSP總是會限制任意兩個執(zhí)行器間的最大過時值s，所以它理論上可以強有力地保證數(shù)據(jù)并行執(zhí)行和模型并行執(zhí)行的收斂。為此我們給出下面兩個互補定理。

定理3(改編自參考文獻[40])：SSP數(shù)據(jù)并行收斂定理?？紤]凸目標(biāo)函數(shù)L = f (A) =f (A)，其中,單個t組件ft也是凸的。在SSP下，我們通過在各個組件ft上進行數(shù)據(jù)并行SGD算法尋找一個最小值A(chǔ)*，過時參數(shù)為s，共P臺機器。使數(shù)據(jù)并行更新為Δt∶= -ηttft(At)，其中，ηt=。在適當(dāng)?shù)臈l件下[ft為利普希茨連續(xù)，且有屆散度D（AA′）≤F2]，我們可以獲得以下收斂速度保證：

該數(shù)據(jù)并行SSP定理具有兩個含義：首先，SSP下的數(shù)據(jù)并行執(zhí)行是準(zhǔn)確的(就像BSP一樣)，因為R[A]/T(SSP參數(shù)的估值和實際最優(yōu)值之間的差值)依指數(shù)尾界的概率收斂至O(T-1/2)；其次，重要的是要使實際過時值和異步性盡可能小，最大過時值越小，執(zhí)行器經(jīng)歷的平均過時值μγ和過時方差σγ越小，收斂的界就越緊。由于這一原因，樸素異步系統(tǒng)(如Hogwild! [31] 和 YahooLDA [28])在復(fù)雜生產(chǎn)環(huán)境中的收斂性可能較差，機器可能由于其他的任務(wù)或用戶暫時變慢，這就使最大過時值s和過時方差σγ變得任意大，進而導(dǎo)致較差的收斂速度。

定理4(出現(xiàn)于2016年)：SSP模型并行漸進相合性?？紤]使用一個保持集中“全局視圖”A(如在鍵值存儲上)以及每臺執(zhí)行機器上的過時視圖Ap的模型并行近側(cè)梯度下降過程，來最小化目標(biāo)函數(shù)L = f(A, D) + g(A)，其中，A∈Rd。如果下降步長滿足η ＜ 1/(Lf+ 2Ls)，則全局視圖A和本地視圖Ap滿足：

(3) {A(t)}的極限點和{Ap(t)}極限點一致，且兩者都是L的臨界點。

(1)和(2)意味著全局視圖A會逐漸停止改變(即會收斂)，過時本地執(zhí)行器視圖Ap會收斂至全局視圖；換句話說，SSP模型并行執(zhí)行會終止于一個穩(wěn)定的結(jié)果。(3)則進一步保證了本地和全局視圖Ap(t)和A(t) 會取得L的最優(yōu)解；換句話說，SSP模型并行執(zhí)行輸出的是正確的解決方案。若給定其他的技術(shù)條件，我們可以進一步健全，使SSP模型并行執(zhí)行以速度O(t-1)收斂。

上述兩個定理證明，SSP下的數(shù)據(jù)并行和模型并行機器學(xué)習(xí)程序都能夠?qū)崿F(xiàn)每次迭代近乎理想的收斂(接近BSP和順序執(zhí)行)。例如，B?sen系統(tǒng)[37,40,41] 利用SSP達到了相比于BSP橋連模型短十倍的收斂時間——而和異步執(zhí)行不同，選取了合適過時值的SSP不會出現(xiàn)不收斂的情況(圖8)。總之，如果能有效地執(zhí)行和調(diào)節(jié)SSP，它幾乎可以在兩方面達到最佳：接近BSP的近乎理想的每次迭代進程，以及類似于異步執(zhí)行的近乎理想的P倍迭代吞吐量，因此可以實現(xiàn)機器學(xué)習(xí)程序執(zhí)行時間近乎理想的P倍加速。

3.3.如何通信：管理通信和拓撲

為了保證機器學(xué)習(xí)程序的正確執(zhí)行，剛剛討論的橋連模型(BSP和SSP)會在發(fā)生關(guān)于將更新Δ傳遞給模型參數(shù)A的機器學(xué)習(xí)計算時，進行約束。但是，在由橋連模型設(shè)定的約束內(nèi)，仍然存在空間來規(guī)定如何或者以什么順序在網(wǎng)絡(luò)中傳遞更新Δ?？紤]MapReduce類的例子在BSP橋連模型下運行：各Mapper需要將帶有同一鍵值a的鍵值對 (a, b) 傳給同一個Reducer。這可以通過二分拓撲結(jié)構(gòu)進行，但也可以采用星型拓撲結(jié)構(gòu)，第三組機器首先收集各個Mapper的所有鍵值對，然后將它們傳遞給各個Reducer。

圖8.三種機器學(xué)習(xí)程序下目標(biāo)函數(shù)L進程和時間曲線圖—— (a)LDA主題建模，(b)套索回歸，(c)矩陣因子分解(MF)—— 在B?sen系統(tǒng)下執(zhí)行，B?sen系統(tǒng)實現(xiàn)了SSP橋連模型。通過使用SSP(選取不同的過時值)提高機器學(xué)習(xí)算法的迭代吞吐量，B?sen實現(xiàn)了比BSP橋連模型(在Hadoop和Spark中使用)和完全異步執(zhí)行模式都要快的收斂(陡峭的曲線)。尤其是，完全異步執(zhí)行在套索回歸和矩陣因子分解中沒有成功收斂，因此沒有畫出它們的曲線。改編自參考文獻[37]。

SSP橋連模型下的機器學(xué)習(xí)算法則具有更廣闊的設(shè)計空間：因為SSP只要求更新Δ“不晚于s個迭代到達”，我們可以選擇先傳送更重要的更新，如果直覺告訴我們這一定可以提高每個迭代的算法進程。這些考慮是非常重要的，因為每個機組或數(shù)據(jù)中心都有它自己的物理交換機拓撲以及沿各個環(huán)節(jié)的可用帶寬。選擇正確的通信管理策略可以大大改善機器學(xué)習(xí)算法每次迭代的進程和提高迭代吞吐量，我們會以這一觀點來討論這些問題?，F(xiàn)在我們來討論幾種可以將通信管理應(yīng)用于分布式機器學(xué)習(xí)系統(tǒng)的方法。

連續(xù)通信。在SSP橋連模型的首次實現(xiàn)中，所有機器間的通信發(fā)生在每次迭代結(jié)束時[也就是說，在SSP clock()命令之后][37]，大多數(shù)時間下網(wǎng)絡(luò)則是閑置的(圖9)。由此產(chǎn)生的通信突發(fā)(千兆字節(jié)到兆兆字節(jié))可能會引起同步延遲(如果更新到達目的地所需的時間比預(yù)期要長)，而這可以通過采用連續(xù)式通信優(yōu)化掉，系統(tǒng)會等正在進行的更新完成傳輸后才開始新的更新傳輸[41]。

連續(xù)通信可以通過一個速度限制器在SSP過程中實現(xiàn)，該限制器讓發(fā)送的通信列隊等候，直到前面的通信完成后才將其發(fā)出。重要的是，不論該機器學(xué)習(xí)算法是數(shù)據(jù)并行還是模型并行，連續(xù)通信都仍然可以維持SSP的有限過時條件——因此，它還是會有和SSP一樣的每次迭代最糟糕的收斂進程問題。此外，因為管理通信減少了同步延遲，它會略微加速(兩至三倍)整個收斂時間，部分要歸因于每個迭代進程的提升(延遲減少同時也意味著本地參數(shù)視圖A的平均過時值降低；因此，SSP每個迭代的進程會根據(jù)定理3提升)。

免等待反向傳播。機器學(xué)習(xí)模型的深度學(xué)習(xí)家族由于其高度分層結(jié)構(gòu)，為連續(xù)通信提供了一個特別的機會。兩個觀察結(jié)果特別突出：① “反向傳播”梯度下降算法——常用于訓(xùn)練諸如卷積神經(jīng)網(wǎng)絡(luò)(CNN)的深度學(xué)習(xí)模型——以分層模式進行；② 典型CNN(如AlexNet[20])層次的模型大小高度不對稱，要求進行反向傳播計算——通常，頂部完全連接層有大約90%的參數(shù)，底部卷積層負責(zé)90%的反向傳播計算[56]。這就允許了一個特殊類型的連續(xù)通信，我們將其稱作免等待反向傳播：在頂層執(zhí)行完反向傳播后，系統(tǒng)會在執(zhí)行底部反向傳播時傳遞參數(shù)。這使計算和通信以最優(yōu)的方式展開，本質(zhì)上就是“90%的計算和90%的通信重疊”。

圖9.整個計算過程中，SSP下的管理通信均勻地分布在網(wǎng)絡(luò)通信中，而不是在迭代邊界后就馬上傳遞所有的更新。

更新優(yōu)先化。另一種通信管理策略是劃分可用帶寬的優(yōu)先級，傳遞對收斂貢獻最大的更新(或部分更新)Δ。這一概念與3.1節(jié)中討論的SAP有很緊密的聯(lián)系。SAP優(yōu)先計算更重要的參數(shù)，而更新優(yōu)先化則確保這些重要參數(shù)的改變可以很快地傳播給其他執(zhí)行機器，感受到它們的影響。舉一個具體的例子，在使用SGD的機器學(xué)習(xí)算法(如邏輯回歸和套索回歸)中，目標(biāo)函數(shù)L隨參數(shù)Aj按比例變化，因此變化最快的參數(shù)Aj通常對求解質(zhì)量貢獻最大。

因此，SSP的實現(xiàn)可以通過一個優(yōu)先器進一步增強，該優(yōu)先器重新排列速度限制器中的傳出隊列，這樣更重要的更新會首先傳出。優(yōu)先器可以支持下列策略。

(1) 絕對參量優(yōu)先化：根據(jù)Aj最近累積的變化 |δj| 重新排列Aj，這非常適用于使用SGD的機器學(xué)習(xí)算法。

(2) 相對參量優(yōu)先化：和絕對參量一樣，只是排序標(biāo)準(zhǔn)是|δj|/Aj，即用實時參數(shù)值A(chǔ)j標(biāo)準(zhǔn)化積累的變化|δj|。根據(jù)經(jīng)驗，這些優(yōu)先化策略可以產(chǎn)生25%的加速，在SSP和連續(xù)通信之上[41]，并且仍有潛力探索出為特殊機器學(xué)習(xí)程序量身定制的策略(類似為套索設(shè)計的SAP優(yōu)先化標(biāo)準(zhǔn))。

參數(shù)存儲和通信拓撲結(jié)構(gòu)。第三種通信管理策略是考慮通過網(wǎng)絡(luò)放置模型參數(shù)A(參數(shù)存儲)，以及參數(shù)更新Δ的通信路徑網(wǎng)絡(luò)路由(通信拓撲結(jié)構(gòu))。參數(shù)存儲的選擇會大大影響可用通信拓撲結(jié)構(gòu)，這反過來影響參數(shù)更新Δ在網(wǎng)絡(luò)中傳遞的速度(以及過時值)。因此，我們接下來開始討論兩種常見的存儲模型參數(shù)的范例(圖10)。

(1) 集中存儲：參數(shù)A的“全局視圖”通過一組服務(wù)器進行分區(qū)存儲，而執(zhí)行機器則保留參數(shù)的本地視圖。通信在以下意義上是不對稱的：更新Δ從執(zhí)行器傳到服務(wù)器，執(zhí)行器從服務(wù)器接收到最新版本的參數(shù)A。

(2) 分散存儲：每個執(zhí)行器保持自己的參數(shù)本地視圖，沒有一個集中的服務(wù)器。通信是對稱的：執(zhí)行器互相傳遞更新Δ，以使它們的本地視圖A達到最新狀態(tài)。

主從式拓撲結(jié)構(gòu)可以支持集中存儲式范例(圖11)，機器以二分圖形式排列，一邊為服務(wù)器，另一邊為執(zhí)行器；而分散存儲式范例可以通過對等(P2P)拓撲結(jié)構(gòu)(圖12)來支持，每個執(zhí)行機器向其他執(zhí)行機器進行傳播。主從式網(wǎng)絡(luò)拓撲結(jié)構(gòu)的一個優(yōu)勢是它減少了需要通過網(wǎng)絡(luò)被傳遞的信息的數(shù)量：執(zhí)行器只需要將更新Δ傳送給服務(wù)器，服務(wù)器使用F聚合它們，然后更新參數(shù)A的主視圖。接著，更新后的參數(shù)可以作為一條單獨的信息傳輸，而不是作為單個更新Δ的集合?？偟膩碚f，只需要傳遞O(P)條信息。而P2P拓撲結(jié)構(gòu)每次迭代必須發(fā)送O(P2)條信息，因為每個執(zhí)行器必須將Δ傳遞給其他所有執(zhí)行器。

但是，如果δ結(jié)構(gòu)緊湊或可壓縮——例如，深度學(xué)習(xí)之類矩陣參數(shù)化機器學(xué)習(xí)程序中的低秩性，或者套索回歸中的稀疏性——與主從拓撲結(jié)構(gòu)相比，P2P拓撲結(jié)構(gòu)可以大大節(jié)省通信。通過以一種更低秩或稀疏的形式壓縮或再呈現(xiàn)Δ，O(P2)條 P2P消息中的每條消息可以變得比O(P)條主從式消息更小，因為主從式消息不允許壓縮(因為消息是由實時參數(shù)A組成，而不是可壓縮的更新Δ)。此外，可以通過將完全P2P轉(zhuǎn)換成部分連接Halton序列拓撲結(jié)構(gòu)(圖13)，減少O(P2)條 P2P消息[65]，在該結(jié)構(gòu)中，每個執(zhí)行器只和執(zhí)行器的一個子集通信。執(zhí)行器可以通過經(jīng)中間節(jié)點路由消息，與其他機器通信。例如，路由路徑1→2→5→6是將消息從1號執(zhí)行器傳遞至6號執(zhí)行器一條路。中間節(jié)點可以將要發(fā)送至同一目的地的消息結(jié)合在一起，這樣就減少了每次迭代消息的數(shù)量(并進一步減少了網(wǎng)絡(luò)負載)。但是，Halton序列的一個缺點是，路由增加了消息到達目的地的時間，這就增大了SSP橋連模型下參數(shù)的平均過時值。例如，消息從1號執(zhí)行器傳遞到6號執(zhí)行器過時三次迭代。但是，Halton序列拓撲結(jié)構(gòu)對于P2P帶寬受限的大型機組網(wǎng)絡(luò)仍然是一個非常好的選擇。

通過結(jié)合“如何通信”的不同方面——連續(xù)通信，更新優(yōu)先化，以及參數(shù)存儲和通信拓撲結(jié)構(gòu)的合理結(jié)合——我們可以設(shè)計一個擁有各方面速度優(yōu)勢疊加的分布式機器學(xué)習(xí)系統(tǒng)，獲得相比SAP(如何分布)以及SSP(橋連模型)幾乎是數(shù)量級的速度提升。例如，B?sen SSP系統(tǒng)可以獲得比連續(xù)通信和更新優(yōu)先化高達額外四倍的加速，如圖14和圖15所示[41]。 3.4.通信的對象

圖10.參數(shù)存儲的兩種范例。注意，兩種范例的通信模式不同：集中存儲將更新Δ從執(zhí)行器傳遞到服務(wù)器、實時參數(shù)A從服務(wù)器到執(zhí)行器；分散存儲只在執(zhí)行器間傳遞更新Δ。

圖11.集中參數(shù)存儲的主從(二分)網(wǎng)絡(luò)拓撲結(jié)構(gòu)。服務(wù)器只和執(zhí)行器通信，反之亦然。沒有服務(wù)器間或執(zhí)行器間的通信。

圖12.分散參數(shù)存儲的對等(P2P)網(wǎng)絡(luò)拓撲結(jié)構(gòu)。所有執(zhí)行器與其他執(zhí)行器通信。

圖13.分散參數(shù)存儲的Halton序列拓撲結(jié)構(gòu)。執(zhí)行器通過中間機器與其他執(zhí)行器進行通信，例如，1號執(zhí)行器可以通過將更新Δ轉(zhuǎn)交給2號執(zhí)行器來與5號執(zhí)行器通信。

圖14.矩陣分解：連續(xù)通信加SSP，其收斂時間比單用SSP提升了1.8倍。實驗設(shè)置：網(wǎng)飛(Netflix)公司數(shù)據(jù)集，400秩，8臺機器(每臺16核)，千兆以太網(wǎng)(GbE)。改編自參考文獻[41]。

圖15.LDA主題模型：連續(xù)通信加SSP，其收斂時間比單用SSP提升了三倍。而且，如果同時采用更新優(yōu)先化，收斂時間還能再減少25%。實驗設(shè)置：NYTimes數(shù)據(jù)集，1 000個主題，16臺機器(每臺16核)，千兆以太網(wǎng)。改編自參考文獻[41]。

除了在執(zhí)行器機器之間如何存儲和傳遞更新Δ，我們還會問在每次更新Δ時需要通信“什么”。尤其是有沒有什么方法可以減少發(fā)送Δ需要的字節(jié)數(shù)，從而進一步緩解分布式機器學(xué)習(xí)程序中的交流瓶頸[55]？這個問題與以操作為中心的項目中無損壓縮的思想有關(guān)，如Hadoop MapReduce能夠壓縮鍵值對(a，b)來降低從映射器到減速器的傳輸成本。對于數(shù)據(jù)并行機器學(xué)習(xí)程序，一種常用的降低Δ消息大小的策略是利用F內(nèi)可加結(jié)構(gòu)[就像套索數(shù)據(jù)并行的例子，方程(10)]，在網(wǎng)絡(luò)傳輸前將其聚合(即總計)。這種早期的聚合是為了從服務(wù)器到執(zhí)行器交流完整的參數(shù)A[37,40]的集中參數(shù)存儲模式服務(wù)，我們很自然要問是否還有其他或許可以更好地適應(yīng)不同存儲模式的策略。

要回答這個問題，我們可以審視一下機器學(xué)習(xí)參數(shù)A的數(shù)學(xué)結(jié)構(gòu)，及其更新Δ的性質(zhì)。許多流行的機器學(xué)習(xí)程序都有矩陣結(jié)構(gòu)的參數(shù)A(我們使用傳統(tǒng)的粗體字以區(qū)別于一般的A)。例子包括多類Logistic回歸(MLR)、神經(jīng)網(wǎng)絡(luò)(NN)[60]、距離度量學(xué)習(xí)(DML)[66]，以及稀疏編碼[23]。我們把這些稱為矩陣參數(shù)化模型(MPMS)，要注意A在目前的應(yīng)用可以是非常大的：在一個MLR對維基百科的應(yīng)用中[67]，A是一個包含數(shù)十億條目(幾十兆字節(jié))的325K-by-10K矩陣。值得指出的是，典型的計算機集群網(wǎng)絡(luò)最多可以在兩臺機器間每秒傳送幾個字節(jié)；因此，這樣單純不同步的矩陣A及其更新Δ就不是瞬時性的。由于參數(shù)同步在一個迭代收斂的機器學(xué)習(xí)程序的壽命中會發(fā)生很多次，同步所需的時間就可以成為一個巨大的瓶頸。

更正式地說，MPM是一種特殊形式的機器學(xué)習(xí)目標(biāo)函數(shù)如下：

其中，模型參數(shù)是一個K-by-D矩陣A∈RK×D；每個損失函數(shù)fi被定義在A上，數(shù)據(jù)取樣為。具體來說， fi必須取決于結(jié)果Aui(而不是單獨地由A或ui決定)。r(A)是一種像正則化矩陣一樣的結(jié)構(gòu)誘導(dǎo)函數(shù)。方程(16)一個著名的例子就是MLR，用于涉及成千上萬種類K(如網(wǎng)絡(luò)數(shù)據(jù)的集合，像維基百科)的分類問題。在MLR中，A是權(quán)重系數(shù)矩陣，ui是數(shù)據(jù)樣本i的D維特征向量，vi是一個表示數(shù)據(jù)樣本i的類標(biāo)簽的K維特征向量，損失函數(shù)fi由一個交叉熵誤差函數(shù)和一個Aui的Soft-Max映射組成。MPM的一個關(guān)鍵性質(zhì)是，每個更新Δ是一個低秩矩陣，可分解成被稱為充分因素的小的向量，通過網(wǎng)絡(luò)發(fā)送較為便宜。

充足因素傳播(SFB)。為了利用MPM充足因素的性質(zhì)，讓我們仔細觀察更新Δ。機器學(xué)習(xí)目標(biāo)函數(shù)方程 (16)還可以通過隨機梯度下降(SPGD)[37,52,60,65]或隨機雙坐標(biāo)上升(SDCA)[68-72]算法技術(shù)解決。例如，在SPGD中，更新函數(shù)Δ可以被分解為向量 biciT的總和，其中，ci= ui；SDCA更新Δ也允許類似的分解[55]。作為發(fā)送(總大小KD)的代替，我們可以發(fā)送個別矢量bi和ci[總大小S(K + D)]，其中S是樣本數(shù)據(jù)在當(dāng)前迭代處理的數(shù)量)，并在目標(biāo)機上重建Δ。

這種充足因素傳播(SFB)策略適合于分散式存儲模式，其中，只有更新Δ是在執(zhí)行器之間傳播。它也可以被應(yīng)用到集中存儲的模式，不過只用于從執(zhí)行器到服務(wù)器的傳輸；服務(wù)器到執(zhí)行器的工作方向發(fā)送不再具有充足因素屬性的完整矩陣A[60]。在這一點上，我們很自然要問分散存儲和SFB的組合如何與SSP橋連模型相互作用，機器學(xué)習(xí)算法仍然會在這樣的P2P設(shè)定下輸出正確的答案嗎？下面的定理提供了一個肯定的答案。

定理5(改編自參考文獻[55])：在SSP下的SFB收斂定理。設(shè)對于在與過時的s連接的SSP模型下被SFB解決的方程(16)中的機器學(xué)習(xí)目標(biāo)函數(shù)L(假設(shè)r ≡ 0)，Ap(t), p = 1,…, P, A(t)分別是本地執(zhí)行器視圖和一個“參考”視圖。在溫和的假設(shè)下，我們有

直觀地說，定理5表明本地執(zhí)行器視圖Ap(t)最終收斂到目標(biāo)函數(shù)L的穩(wěn)定點(局部極小值)，即使更新Δ在高達s次迭代后是過時的。因此，分散式存儲下SFB在SSP橋連模型下是穩(wěn)健的——對于比如Halton序列的加快了更新過時速度以交換較低帶寬的拓撲結(jié)構(gòu)尤其有效。

根據(jù)經(jīng)驗，SFB可以大大降低MPM的通信成本：圖16顯示了對于各種MPM使用BSP橋連模型達到一個固定函數(shù)值所花費的時間。在SFB下運行的MPM要比在發(fā)送全面更新Δ(稱為“全矩陣同步”或FMS)的集中式存儲模式下運行收斂更快。我們也把在SFB下運行的MPM比作包括Spark v1.3.1的基線的實現(xiàn)(不是所有被評估的MPM都可在Spark上使用)。這是因為SFB具有更低的通信成本，所以更大比例的算法運行時間就花在了計算而不是網(wǎng)絡(luò)等候上。我們用圖17表示，圖上繪制了在BSP一致性和不同Minibatch大小下，MLR每秒處理的數(shù)據(jù)樣本(即迭代吞吐量)和每個樣本的算法處理(即每次迭代的處理)。圖17(b)顯示SFB每秒處理的樣本比FMS會多很多，而圖17(c)顯示SFB和FMS在BSP下每個樣本得到完全相同的算法處理。

要了解SFB在Δ通信成本上的影響，讓我們看看圖18，顯示了在一系列的SSP過時值上的總計算時間以及SFB和FMS收斂所需的網(wǎng)絡(luò)通信時間。一般來說，更高的Δ通信成本和較少的過時會增加機器學(xué)習(xí)程序花在等待網(wǎng)絡(luò)通信上的時間。對于所有的過時值，SFB需要更少的網(wǎng)絡(luò)等待(因為SFB比FMS中的全矩陣要小得多)。SFB的計算時間比FMS略長，因為：①更新矩陣Δ必須在每一個執(zhí)行器上重建，以及②SFB比起FMS需要更多的迭代來進行收斂，這是因為相比于FMS，SFB參數(shù)過時平均值稍高?？偟膩碚f，SFB在網(wǎng)絡(luò)等待上減少的時間遠遠超過增加的計算時間，因此SFB勝過了FMS。

圖16.(a)多類Logistic回歸(MLR)、(b)距離度量學(xué)習(xí)(DML)和(c)L2- MLR的收斂時間與模型大小對照。

圖17.(a)MLR任務(wù)與運行時間對照；(b)樣本與運行時間對照；(c)任務(wù)與樣本對照。

圖18.計算時間與網(wǎng)絡(luò)等待時間對照：(a) MLR；(b) DML； (c) L2- MLR。

最后一點，有些情況自然要求SFB和完整Δ傳送的混合。一個很好的例子是使用卷積神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)(先前在3.3節(jié)中討論了免等待反向傳播的話題)：一個典型CNN的頂層被完全連接起來，使用了包含數(shù)百萬要素的矩陣參數(shù)，而底層是卷積的，并涉及至多幾百個要素的小矩陣。由此得出結(jié)論，應(yīng)用SFB到頂層的更新[傳輸成本為S(K + D)KD，因為K和D很大程度上與S相關(guān)]、傳輸之前聚合(總計)底層的更新[成本為KD S(K + D)，因為S很大程度上與K和D相關(guān)] [56]，這兩種方法都會更加有效。

4.Petuum：一種機器學(xué)習(xí)系統(tǒng)設(shè)計原則的實現(xiàn)方式

我們通過指出機器學(xué)習(xí)系統(tǒng)設(shè)計的四條原則已經(jīng)由一些高度專用于一個或多個機器學(xué)習(xí)程序的系統(tǒng)部分實現(xiàn)，來對本文做出總結(jié)[28,31,36,58,60]。這就為機器學(xué)習(xí)從業(yè)人員提供了在上述的專、精但高性能的“塔”(需要大量的工程作業(yè)以進行維護、升級的專業(yè)化系統(tǒng))，與更通用但速度也更慢的“平臺”，如Hadoop和Spark(相對易于部署和維護)之間的選擇。為了解決這種對立，我們已經(jīng)得出了機器學(xué)習(xí)系統(tǒng)設(shè)計在Petuum分布式機器學(xué)習(xí)框架[35]中的原則，其結(jié)構(gòu)如圖19所示。Petuum蘊含的目的是為進行大數(shù)據(jù)運算的機器學(xué)習(xí)算法提供一種通用的分布式系統(tǒng)，通過從ML程序員那里提取系統(tǒng)的實施細節(jié)和設(shè)計的四個原則，ML程序員得到釋放之后可以專注于對機器學(xué)習(xí)的關(guān)鍵函數(shù)L、Δ和F進行編程。

圖19.Petuum結(jié)構(gòu)，一種為大數(shù)據(jù)和大模型工作的分布式機器學(xué)習(xí)系統(tǒng)。

相比于對于以操作為中心的程序通用的分布式編程平臺(如Hadoop和Spark)，Petuum利用迭代收斂機器學(xué)習(xí)程序的獨特性能——容錯性、依存結(jié)構(gòu)、非一致收斂、緊湊更新——以提高機器學(xué)習(xí)算法的收斂速度和每次迭代的時間，從而用P臺機器實現(xiàn)接近理想化的P倍加速。Petuum運行集群計算和云計算，以幾十到數(shù)千臺機器進行支持，并提供C++和Java的編程接口，同時也支持另一種資源協(xié)調(diào)者(YARN)和Hadoop分布式文件系統(tǒng)(HDFS)在現(xiàn)有的Hadoop集群上執(zhí)行。Petuum的基礎(chǔ)為以下兩大系統(tǒng)(圖 19)。

(1)B?sen，一種為數(shù)據(jù)并行機器學(xué)習(xí)編程服務(wù)的有限異步分布式關(guān)鍵值存儲。B?sen使用SSP一致性模型，它提供優(yōu)于MapReduce的異步類性能和整體同步執(zhí)行，也并不犧牲機器學(xué)習(xí)算法的準(zhǔn)確性。

(2)Strads，一種為模型并行機器學(xué)習(xí)編程服務(wù)的動態(tài)調(diào)度。Strads進行細粒度的機器學(xué)習(xí)更新操作調(diào)度，優(yōu)先計算機器學(xué)習(xí)程序中最需要計算的部分，同時避免可能會導(dǎo)致ML程序不收斂的危險的并行操作。

目前，Petuum描畫出了一個含有超過10種隨時可以運行的算法的機器學(xué)習(xí)庫(在B?sen和Strads之上實現(xiàn))，包括經(jīng)典算法諸如Logistic回歸、K-均值、隨機森林，以及更新穎的算法，比如監(jiān)督學(xué)習(xí)的主題模型(MedLDA)、深度學(xué)習(xí)、距離度量學(xué)習(xí)以及稀疏編碼。尤其是Petuum深度學(xué)習(xí)系統(tǒng)Poseidon[56]，充分體現(xiàn)了Petuum“平臺”的性質(zhì)：Poseidon以有效但單機的Caffe項目①http://caff e.berkeleyvision.org/，并通過用B?sen分布式關(guān)鍵值存儲的分布式共享內(nèi)存編程接口來更換在Caffe中的內(nèi)存訪問例程，把它變成一個分布式圖形處理單元(GPU)系統(tǒng)。這個平臺方式最大的好處是熟悉性和可用性——現(xiàn)有的Caffe用戶不必為了利用GPU在整個集群中的分布就要學(xué)習(xí)一個新的工具。

展望未來，我們想象Petuum可能會成為為機器學(xué)習(xí)應(yīng)用程序用戶或程序員提供單機或筆記本電腦類經(jīng)驗的機器學(xué)習(xí)分布式集群操作系統(tǒng)的基礎(chǔ)，同時充分利用由成千上萬的機器的數(shù)據(jù)中心規(guī)模的集群所提供的計算能力。要實現(xiàn)這一愿景，肯定還需要開發(fā)新的系統(tǒng)，比如集裝箱化、集群資源管理和調(diào)度，以及待開發(fā)的用戶界面，這些都是減少數(shù)據(jù)中心環(huán)境中大規(guī)模應(yīng)用的大量的人力或運營成本部署的必要步驟。通過在以機器學(xué)習(xí)為中心的Petuum平臺上建立這樣的系統(tǒng)——使其能夠用更少的機器運行得更快，以降低機器學(xué)習(xí)應(yīng)用的資本成本——我們可以因此準(zhǔn)備好將最終的大數(shù)據(jù)計算從數(shù)據(jù)庫風(fēng)格的操作轉(zhuǎn)變?yōu)闄C器學(xué)習(xí)風(fēng)格的操作。

Compliance with ethics guidelines

Eric P.Xing, Qirong Ho, Pengtao Xie, and Dai Wei declare that they have no conflict of interest or financial conflicts to disclose.

[1] Airoldi EM, Blei DM, Fienberg SE, Xing EP.Mixed membership stochastic blockmodels. J Mach Learn Res 2008;9:1981-2014.

[2] Ahmed A, Ho Q, Eisenstein J, Xing EP, Smola AJ, Teo CH.U nified analysis of streaming news.In: Proceedings of the 20th International Conference on World Wide Web; 2011 Mar 28-Apr 1; Hyderabad, India; 2011.p.267-76.

[3] Zhao B, Xing EP.Qua si real-time summarization for consumer videos.In: Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR); 2014 Jun 23-28; Columbus, OH, USA; 2014.p.2513-20.

[4] Lee S, Xing EP.Leve raging input and output structures for joint mapping of epistatic and marginal eQTLs.Bioinformatics 2012;28(12):i137-46.

[5] Thrun S, Montemerlo M, Dahlkamp H, Stavens D, Aron A, Diebel J, et al.Stanle y: the robot that won the DARPA Grand Challenge.J Field Robot 2006;23(9):661-92.

[6] Chandola V, Banerjee A, Kumar V.Anomaly detection: a survey.ACM Comput Surv 2009;41(3):15:1-15:58.

[7] Wainwright MJ, Jordan MI.Graphica l models, exponential families, and variational inference.Hanover: Now Publishers Inc.; 2008.

[8] Koller D, Friedman N.Probabil istic graphical models: principles and techniques.Cambridge: MIT Press; 2009.

[9] Xing EP.Probabilistic graphical models [Internet].[cited 2016 Jan 1].Available from: https://www.cs.cmu.edu/～epxing/Class/10708/lecture.html.

[10] Zhu J, Xing EP.Maximum entropy discrimination markov networks.J Mach Learn Res 2009;10:2531-69.

[11] Zhu J, Ahmed A, Xing EP.MedLDA: maximum margin supervised topic models for regression and classication.In: Proceedings of the 26th Annual International Conference on Machine Learning; 2009 Jun 14-18; Montreal, Canada; 2009.p.1257-64.

[12] Zhu J, Chen N, Xing EP.Bayesian i nference with posterior regularization and applications to innite latent SVMs.J Mach Learn Res 2014;15(1):1799-847.

[13] Griffiths TL, Ghahramani Z.Infinite latent feature models and the Indian buffet process.In: Weiss Y, Sch?lkopf B, Platt JC, editors Proceedings of the Neural Information Processing Systems 2005; 2005 Dec 5-8; Vancouver, Canada; 2005.p.475-82.

[14] Teh YW, Jordan MI, Beal MJ, Blei DM.Hierarchical d irichlet processes.J Am Stat Assoc 2006;101(476):1566-81.

[15] Yuan M, Lin Y.Model selection and estimation in regression with grouped variables.J R Stat Soc B 2006;68(1):49-67.

[16] Kim S, Xing EP.Tree-guided group lasso for multi-response regression with structured sparsity, with applications to eQTL mapping.Ann Appl Stat 2012;6(3):1095-117.

[17] Burges CJC.A tutorial on support vector machines for pattern recognition.Wires Data Min Knowl 1998;2(2):121-67.

[18] Taskar B, Guestrin C, Koller D.Max-margin Markov networks.In: Thrun S, Saul LK, Sch?lkopf B, editors Proceedings of the Neural Information Processing Systems 2003; 2003 Dec 8-13; Vancouver and Whistler, Canada; 2003.p.25-32.

[19] Hinton G, Deng L, Yu D, Dahl GE, Mohamed A, Jaitly N, et al.Deep neural netw orks for acoustic modeling in speech recognition: the shared views of four research groups.IEEE Signal Proc Mag 2012;29(6):82-97.

[20] Krizhevsky A, Sutskever I, Hinton GE.ImageNet classificati on with deep convolutional neural networks.In: Pereira F, Burges CJC, Bottou L, Weinberger KQ, editors Proceedings of the Neural Information Processing Systems 2012; 2012 Dec 3-8, Lake Tahoe, USA; 2012.p.1097-105.

[21] Lee DD, Seung HS.Learning the parts of o bjects by non-negative matrix factorization.Nature 1999;401(6755):788-91.

[22] Salakhutdinov R, Mnih A.Probabilistic matrix fac torization.In: Platt JC, Koller D, Singer Y, Roweis ST, editors Proceedings of the Neural Information Processing Systems 2007; 2007 Dec 3-6; Vancouver, Canada; 2007.p.1257-64.

[23] Olshausen BA, Field DJ.Sparse coding with an ov ercomplete basis set: a s trategy employed by V1? Vision Res 1997;37(23):3311-25.

[24] Lee H, Battle A, Raina R, Ng AY.Efficient sparse coding algorithms.In: Sch?lkopf B, Platt JC, Hoffman T, editors Proceedings of the Neural Information Processing Systems 2006; 2006 Dec 4-7; Vancouver, Canada; 2006.p.801-8.

[25] Zheng X, Kim JK, Ho Q, Xing EP.Model-parallel inference for big topic models.2014.Eprint arXiv:1411.2305.

[26] Yuan J, Gao F, Ho Q, Dai W, Wei J, Zheng X, et al.LightLDA: big topic models o n modest compute clusters.2014.Eprint arXiv:1412.1576.

[27] Coates A, Huval B, Wang T, Wu DJ, Ng AY, Catanzaro B.Deep learning with COTS HPC systems.In: Proceedings of the 30th International Conference on Machine Learning; 2013 Jun 16-21; Atlanta, GA, USA; 2013.p.1 337-45.

[28] Ahmed A, Aly M, Gonzalez J, Narayanamurthy S, Smola AJ.Scalable inference in latent variable models.In: Proceedings of the 5th International Conference on Web Search and Data Mining; 2012 Feb 8-12; Seattle, WA, USA; 2012.p.123-32.

[29] Moritz P, Nishihara R, Stoica I, Jordan MI.SparkNet: training deep network s in spark.2015.Eprint arXiv:1511.06051.

[30] Agarwal A, Duchi JC.Distributed delayed stochastic optimization.In: Shawe-Taylor J, Zemel RS, Bartlett PL, Pereira F, Weinberger KQ, editors Proceedings of the Neural Information Processing Systems 2011; 2011 Dec 12-17; Granada, Spain; 2011.p.873-81.

[31] Niu F, Recht B, Re C, Wright SJ.HOGWILD!: a lock-free approach to parallelizing stochastic gradient descent.In: Shawe-Taylor J, Zemel RS, Bartlett PL, Pereira F, Weinberger KQ, editors Proceedings of the Neural Information Processing Systems 2011; 2011 Dec 12-17; Granada, Spain; 2011.p.693-701.

[32] Dean J, Ghemawat S.MapReduce: simplified data processi ng on large clusters.Commun ACM 2008;51(1):107-13.

[33] Gonzalez JE, Low Y, Gu H, Bickson D, Guestrin C.PowerGraph: distributed graph-parallel computation on natural graphs.In: Proc eedings of the 10th USENIX Symposium on Operating Systems Design and Implementation; 2012 Oct 8-10; Hollywood, CA, USA; 2012.p.17-30.

[34] Zaharia M, Chow dhury M, Das T, Dave A, Ma J, McCauley M, et al.Resilient distributed datasets: a faul t-tolerant abstraction for in-memory cluster computing.In: Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation; 2012 Apr 25-27; San Jose, CA, USA; 2012.p.2:1-2:14.

[35] Xing EP, Ho Q, Dai W, Kim JK, Wei J, Lee S, et al.Petuum: a new platform for distributed machine learning on big data.IEEE Trans Big Data 2015;1(2):49-67.

[36] Li M, Andersen DG, Park JW, Smola AJ, Ahmed A, Josifovski V, et al.Scaling distributed machine learning with the parameter server.In: Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation; 2014 Oct 6-8; Broomfi eld, CO, USA; 2014.p.583-98.

[37] Ho Q, Cipar J, Cui H, Kim JK, Lee S, Gibbon s PB, et al.More effective distributed ML via a stale synchronous parallel parameter server.In: Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, editors Proceedings of the Neural Information Processing Systems 2013; 2013 Dec 5-10; Lake Tahoe, USA; 2013.p.1223-31.

[38] Kum ar A, Beutel A, Ho Q, Xing EP.Fugue: slow-worker-agnostic distributed learning for big models on big data.In: Kaski S, Corander J, editors Proceedings of the 17th International Conference on Artificial Intelligence and Statistics (AISTATS) 2014; 2014 Apr 22-25; Reykjavik, Iceland; 2014.p.531-9.

[39] Lee S, Kim JK, Zheng X, Ho Q, Gibson GA, Xing EP.On model parallelization and scheduling strateg ies for distributed machine learning.In: Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, editors Proceedings of the Neural Information Processing Systems 2014; 2014 Dec 8-13; Montreal, Canada; 2014.p.2834- 42.

[40] Dai W, Kumar A, Wei J, Ho Q, Gibson G, Xing EP.High-performance distributed ML at scale through parameter server consistency models.In: Proceedings of the 29th AAAI Conference on Artificial Intelligence; 2015 Jan 25-30; Austin, TX, USA; 2015.p.79-87.

[41] Wei J, Dai W, Qiao A, Ho Q, Cui H, Ganger GR, et al.Managed communication and consistency for fast data -parallel iterative analytics.In: Proceedings of the 6th ACM Symposium on Cloud Computing; 2015 Aug 27-29; Kohala Coast, HI, USA, 2015.p.381-94.

[42] Bottou L.Large-scale machine learning with stochastic gradient descent.In: Lechevallier Y, Saporta G, editors Proceedings of COMPSTAT’2010; 2010 Aug 22-27; Paris France.New York: Springer; 2010.p.177-86.

[43] Zhou Y, Yu Y, Dai W, Liang Y, Xing EP.On convergence of model parallel proximal gradient algor ithm for stale synchronous parallel system.In: Gretton A, Robert CC, editors Proceedings of the 19th International Conference on Artificial Intellige nce and Statistics (AISTATS) 2016; 2016 May 7-11; Cadiz, Spain; 2016.p.713-22.

[44] Fercoq O, Richtárik P.Accelerated, parallel and proximal coordinate descent.SIAM J Optim 2013;25(4):1997-2023.

[45] Gilks WR.Markov Chain Monte Carlo.In: Encyclopedia of bios tatistics.2nd ed.New York: John Wiley and Sons, Inc., 2005.

[46] Tibshirani R.Regression shrinkage and selection via the lasso.J R Statist Soc B 1996;58(1):267-88.

[47] Blei DM, Ng AY, Jordan MI.Latent dirichlet allocation.J Mach Learn Res 2003;3:993-1022.

[48] Yao L, Mimno DM, McCallum A.Effcient methods for topic model inference on streaming documen t collections.In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2009 Jun 28-Jul 1; Paris, France; 2009.p.937-46.

[49] Dean J, Ghemawat S.MapReduce: simplified data processing on large clusters.In: Proc eedings of the 6th Conference on Symposium on Operating Systems Design & Implementation-Volume 6; 2004 Dec 6-8; San Francisco, CA, USA; 2004.p.137-50.

[50] Zhang T.Solving large scale linear prediction problems using stochastic grad ient descent algorithms.In: Proceedings of the 21st International Conference on Machine Learning; 2004 Jul 4-8; Banff , Canada; 2004.p.116.

[51] Gemulla R., Nijkamp E, Haas PJ, Sismanis Y.Large-scale matrix factorization with distributed stochastic gradien t descent.In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2011 Aug 21-24; San Diego, CA, USA; 2011.p.69-77.

[52] Dean J, Corrado G, Monga R, Chen K, Devin M, Mao M, et al.Large scale distributed deep networks.In: Pereira F, Burges CJC, Bottou L, Weinberger KQ, editors Proceedings of the Neural Information Processing Systems 2012; 2012 Dec 3-8, Lake Tahoe, USA; 2012.p.1232-40.

[53] Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM.GraphLab: a new framework for parallel machine learning.In: Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010); 2010 Jul 8-11, Catalina Island, CA, USA; 2010.

[54] Hinton GE, Salakhutdinov RR.Reducing the dimensionality of data with neural networks.Science 2006;313(5786):504-7.

[55] Xie P, Kim JK, Zhou Y, Ho Q, Kumar A, Yu Y, et al.Distributed machine learning via suffi cient factor broadcasting.2015.Epri nt arXiv:1409.5705.

[56] Zhang H, Hu Z, Wei J, Xie P, Kim G, Ho Q, et a l.Poseidon: a system architecture for effcient GPU-based deep learning on multiple machines.2015.Eprint arX-iv:1512.06216.

[57] Bradley JK, Kyrola A, Bickson D, Guestrin C.Parallel coordinate descent for L1-regularized loss minimization.In: Proce edings of the 28th International Conference on Machine Learning; 2011 Jun 28-Jul 2; Bellevue, WA, USA; 2011.

[58] Scherrer C, Tewari A, Halappanavar M, Haglin D.Feature clustering for accelerating parallel coordinate descent.In: Pereira F, Burges CJC, Bottou L, Weinberger KQ, editors Proceedings of the Neural Information Processing Systems 2012; 2012 Dec 3-8, Lake Tahoe, USA; 2012.p.28-36.

[59] Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM.Distributed GraphLab: a framework for machine learning and data mining in the cloud.In: Proceedings of the VLDB Endowment; 2012 Aug 27-31; Istanbul, Turkey; 2012;5(8): 716-27.

[60] Chilimbi T, Suzue Y, Apacible J, Kalyanaraman K.Project Adam: building an efficient and scalable deep learning training system. In: Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implem entation; 2014 Oct 6-8; Broomfi eld, CO, USA; 2014.p.571-82.

[61] Valiant LG.A bridging model for parallel computation.Commun ACM 1990;33(8):103-11.

[62] McCo ll WF.Bulk synchronous parallel computing.In: Davy JR, Dew PM, editors Abstract machine models for highly parallel computers.Oxford: Oxford University Press; 1995.p.41-63.

[63] Malewicz G, Austern MH, Bik AJC, Dehnert JC, Horn I, Leiser N, et al.Pregel: a system for large-scale graph processing.In: Proceedings of the 2010 ACM S IGMOD International Conference on Management of Data; 2010 Jun 6-11; Indianapolis, IN, USA; 2010.p.135-46.

[64] Terry D.Replicated data consistency explained through baseball.Commun ACM 2013;56(12):82-9.

[65] Li H, Kadav A, Kruus E, Ungurean u C.MALT: distributed data- parallelism for existing ML applications.In: Proceedings of the 10th European Conference on Computer Systems; 2015 Apr 21-25; Bordeaux, France; 2015.Article No.: 3.

[66] Xing EP, Jordan MI, Russell SJ, Ng AY.Distance metric learning with application to clustering with side-information.In: Becke r S, Thrun S, Obermayer K, editors Proceedings of the Neural Information Processing Systems 2002; 2002 Dec 9-14; Vancouver, Canada; 2002.p.505-12.

[67] Partalas I, Kosmopoulos A, Baskiotis N, Artieres T, Paliouras G, Gaussier E, et al.LSHTC: A benchmark for large-scale text classification.2015.Eprint arX-iv:1503.085 81.

[68] Hsieh CJ, Chang KW, Lin CJ, Sathiya Keerthi S, Sundararajan S.A dual coordinate descent method for large-scale linear SVM.In: Proceedings of the 25th International Conference on Machine Learning; 2008 Jul 5-9; Helsinki, Finland; 2008.p.408-15.

[69] Shalev-Shwartz S, Zhang T.Stochastic dual coordinate ascent methods for regularized loss.J Mach Learn Res 2013;14(1): 567-99.

[70] Yang T.Trading computation for communication: distributed stochastic dual coordinate ascent.In: Bur ges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, editors Proceedings of the Neural Information Processing Systems 2013; 2013 Dec 5-10; Lake Tahoe, USA; 2013.p.629-37.

[71] Jaggi M, Smith V, Takac M, Terhorst J, Krishnan S, Hofmann T, et al.Communication-efficient distributed dual coordinate ascent.In: Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, editors Proceedings of the Neural Information Processing Systems 2014; 2014 Dec 8-13; Montreal, Canada; 2014.p.3068-76.

[72] Hsieh CJ, Yu HF, Dhillon IS.PASSCoDe: parallel asynchronous stochastic dual co-ordinate descent.In: Bach F, Blei D, editors Proceedings of the 32nd International Conference on Machine Learning; 2015 Jul 6-11; Lille, France; 2015.p.2370-9.

* Corresponding author.

E-mail address: epxing@cs.cmu.edu

2095-8099/? 2016 THE AUTHORS.Published by Elsevier LTD on behalf of Chinese Academy of Engineering and Higher Education Press Limited Company.This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

英文原文: Engineering 2016, 2(2): 179-195

Eric P Xing, Qirong Ho, Dai Wei, Pengtao Xie.Strategies a nd principles of distributed machine learning on big data.Engineering,

http://dx.doi.org/10.1016/J.ENG.2016.02.008