焦嘉烽，李 云

(南京郵電大學(xué) 計算機(jī)學(xué)院,軟件學(xué)院,網(wǎng)絡(luò)空間安全學(xué)院，南京 210003)

大數(shù)據(jù)下的典型機(jī)器學(xué)習(xí)平臺綜述

焦嘉烽，李 云*

(南京郵電大學(xué) 計算機(jī)學(xué)院,軟件學(xué)院,網(wǎng)絡(luò)空間安全學(xué)院，南京 210003)

由于大數(shù)據(jù)海量、復(fù)雜多樣、變化快，傳統(tǒng)的機(jī)器學(xué)習(xí)平臺已不再適用,因此，設(shè)計一個高效的、通用的大數(shù)據(jù)機(jī)器學(xué)習(xí)平臺成為目前的研究熱點。通過介紹和分析機(jī)器學(xué)習(xí)算法的特點以及大規(guī)模機(jī)器學(xué)習(xí)的數(shù)據(jù)和模型并行化，引出常見的并行計算模型。簡單介紹了整體同步并行模型(BSP)、SSP并行計算模型以及BSP、SSP模型與AP模型的區(qū)別，主要介紹了基于這些并行模型的典型的機(jī)器學(xué)習(xí)平臺和這些平臺的優(yōu)缺點，并指出各個平臺最適合處理何種大數(shù)據(jù)問題。最后從采用的抽象數(shù)據(jù)結(jié)構(gòu)、并行計算模型、容錯機(jī)制等方面對典型的機(jī)器學(xué)習(xí)平臺進(jìn)行了總結(jié)，并提出一些建議和展望。

大數(shù)據(jù)；機(jī)器學(xué)習(xí)平臺；并行計算模型；參數(shù)服務(wù)器

0 引言

近年來，隨著數(shù)據(jù)收集手段的豐富及數(shù)據(jù)存儲能力的提升，公司、企業(yè)存儲的以及科學(xué)研究(如：腦電信號分析等)產(chǎn)生的數(shù)據(jù)量急劇增加。對大數(shù)據(jù)進(jìn)行科學(xué)的分析來獲取更加有價值的信息是一項具有挑戰(zhàn)性的任務(wù)，大數(shù)據(jù)機(jī)器學(xué)習(xí)則是完成這項任務(wù)的關(guān)鍵技術(shù)。目前機(jī)器學(xué)習(xí)應(yīng)用廣泛，但是機(jī)器學(xué)習(xí)處理大數(shù)據(jù)的效率不高，主要面臨兩大類挑戰(zhàn)：大數(shù)據(jù)和大模型。當(dāng)需要處理的數(shù)據(jù)量達(dá)到PB、EB級別時，單臺高性能計算機(jī)已經(jīng)無法在較短的時間內(nèi)給出計算結(jié)果, 因此學(xué)術(shù)界提出了許多并行計算模型，為提高計算效率提供了新的方案。常見的并行計算模型[1-2]有并行隨機(jī)存取器(Parallel Random Access Machine, PRAM)、LogP[3]、塊分布模型(Block Distributed Model，BDM)、整體同步并行模型(Bulk Synchr-onous Parallel model, BSP)[4-5]、AP(Asynchronous Parallel)[4]和SSP(Stale Synchronous Parallel)模型[6]等。由于并行計算模型眾多，因此如何設(shè)計出一個高效的大數(shù)據(jù)機(jī)器學(xué)習(xí)平臺[7]或者框架成為了目前的一個研究熱點，并取得了一些成果。圖1列舉了常見的機(jī)器學(xué)習(xí)平臺，這些機(jī)器學(xué)習(xí)平臺是基于BSP、AP、SSP并行模型的，并且采用各自的編程范式。

圖1中的機(jī)器學(xué)習(xí)平臺借助高級編程語言實現(xiàn)各自的編程模型，并基于這些編程模型實現(xiàn)各類機(jī)器學(xué)習(xí)算法[8]，編程模型能夠?qū)ο鄳?yīng)的并行計算模型進(jìn)行仿真。圖1中還列舉了部分商業(yè)機(jī)器學(xué)習(xí)平臺：AmazonMachineLearning(https://aws.amazon.com/cn/machine-learning/)、微軟Azure(https://azure.microsoft.com/zh-cn/services/machine-learning/)、百度BML(https://cloud.baidu.com/product/bml.html)、GoogleCloudPlatform(https://cloud.google.com/products/machine-learning/)、阿里云DTPAI(https://data.aliyun.com/product/learn?spm=5176.8142029.388261.122.CnBRoG)、IBMSystemML(http://systemml.incubator.apache.org/)、騰訊TML(https://cloud.tencent.com/product/tml)等。

圖1 典型的機(jī)器學(xué)習(xí)平臺架構(gòu)Fig. 1 Architecture of typical machine learning platforms

1 機(jī)器學(xué)習(xí)算法的特點及并行化

1.1 機(jī)器學(xué)習(xí)算法的數(shù)學(xué)表達(dá)

(1)

A(t)=F(A(t-1),ΔL(A(t-1),D))

(2)

其中t表示迭代輪數(shù)，該等式表示從模型參數(shù)A(t-1)和數(shù)據(jù)D通過更新函數(shù)ΔL()和聚合函數(shù)F()生成下一次迭代的模型參數(shù)A(t)，通過迭代上述等式至L達(dá)到最優(yōu)值或者達(dá)到收斂條件。綜上所述，這類迭代式機(jī)器學(xué)習(xí)算法由如下部分組成：

1) 數(shù)據(jù)D和模型參數(shù)A；

2) 損失函數(shù)f(D,A)；

3) 正則化項r(A)；

4) 最優(yōu)化算法(例如隨機(jī)梯度下降法、坐標(biāo)下降法)。

1.2 機(jī)器學(xué)習(xí)算法的特點

由于機(jī)器學(xué)習(xí)問題通常采用梯度下降類算法求解，因此機(jī)器學(xué)習(xí)算法有如下特點[12]：

1) 容錯(Error Tolerance)。在使用隨機(jī)梯度下降等最優(yōu)化算法求解機(jī)器學(xué)習(xí)問題時通過迭代的方式來求解，因此只需保證每一步計算得到的梯度是在收斂的方向上，而不需要保證每一步的梯度都完全計算正確。該特點為大數(shù)據(jù)機(jī)器學(xué)習(xí)系統(tǒng)的設(shè)計提供了折中的空間。

2) 依賴結(jié)構(gòu)(Dependency Structure)。在更新函數(shù)ΔL()中有些變量依賴于其他算式的值而無法實現(xiàn)并行化。

3) 非一致收斂(Non-uniform Convergence)。指不是所有模型參數(shù)A都能在相同的迭代次數(shù)之后收斂到最優(yōu)值A(chǔ)*。

在大規(guī)模機(jī)器學(xué)習(xí)中,數(shù)據(jù)D和模型參數(shù)A將會非常巨大,因此需要采用并行化方式來提高效率，即數(shù)據(jù)并行化和模型并行化。

1.3 數(shù)據(jù)并行化

在數(shù)據(jù)并行化中，數(shù)據(jù)D被分片后分配給P個計算節(jié)點(用p=1,2,…,P進(jìn)行編號)，這里假設(shè)數(shù)據(jù)是獨立同分布的，更新函數(shù)ΔL()在每一個數(shù)據(jù)分片計算得出的結(jié)果之后，采用求和的方式進(jìn)行聚合(隨機(jī)梯度下降法和基于采樣的算法使用的就是這種聚合方式)。梯度下降優(yōu)化算法有三種變型形式：1)批梯度下降法(batch gradient descent)；2)隨機(jī)梯度下降法(Stochastic Gradient Descent，SGD)；3)小批量梯度下降法(mini-batch gradient descent)，詳細(xì)內(nèi)容見文獻(xiàn)[13]。例如在采用隨機(jī)梯度下降法進(jìn)行最優(yōu)化的機(jī)器學(xué)習(xí)問題中，更新函數(shù)在每個Dp上計算出中間結(jié)果(次梯度)，將這些次梯度求和之后乘以學(xué)習(xí)率η再更新模型參數(shù)A(t)，針對隨機(jī)梯度下降法的學(xué)習(xí)率用AdaGrad[14]和AdaDelta[15]算法進(jìn)行計算,則可得到如下數(shù)據(jù)并行的更新等式(省略了學(xué)習(xí)率)：

(3)

1.4 模型并行化

(4)

2 并行計算模型

并行計算模型通常指從并行算法的設(shè)計和分析出發(fā)，抽象出各類并行計算機(jī)(至少某一類并行計算機(jī))的基本特征，形成一個抽象的計算模型。從廣義上來說，并行計算模型為并行計算提供了硬件和軟件界面，在該界面的約定下，并行系統(tǒng)硬件設(shè)計者和軟件設(shè)計者可以開發(fā)對并行性的支持機(jī)制，從而提高系統(tǒng)的性能。常見的并行計算模型有PRAM、AP、BSP、LogP、SSP模型等。因為BSP、SSP模型常被大數(shù)據(jù)機(jī)器學(xué)習(xí)平臺所采用，所以本文主要介紹BSP、SSP模型以及與AP模型的差異。由于AP模型較為簡單，所以只介紹一下AP模型的基本思想，即將計算和通信重疊，從而提高了計算效率。另外需要說明的是MapReduce[16]模型也常被大數(shù)據(jù)平臺所采用，本文將MapReduce看作一種編程范式。

2.1 BSP并行計算模型

BSP[5]模型的創(chuàng)始人是英國著名的計算機(jī)科學(xué)家Valiant，BSP模型的目標(biāo)是為現(xiàn)有和未來可能出現(xiàn)的各種并行體系結(jié)構(gòu)提供一個獨立于具體體系結(jié)構(gòu)的理論模型基礎(chǔ)，故又稱之為橋接模型(Bridging Model)。

BSP模型是包含如下3個部分的并行計算模型：

1) 計算組件(至少由處理器和存儲器組成)；

2) 路由器,為各個計算組件提供一個可通信的網(wǎng)絡(luò),實現(xiàn)各計算組件之間點對點的消息傳遞；

3) 執(zhí)行間隔為T的柵欄同步器(Barrier Synchronisation)。

在BSP模型中，整個計算過程是由柵欄同步器分開的一系列計算部分組成(如圖2所示)，這些計算部分稱為超步(Super Step)(如圖3所示)。BSP模型的獨特之處就在于“超步”的引入，一個超步包括以下3個階段：

1) 本地計算階段。計算節(jié)點對本地數(shù)據(jù)進(jìn)行計算，將計算的結(jié)果存儲在本地的存儲器，將需要發(fā)送到其他計算節(jié)點的消息數(shù)據(jù)存儲到本地消息隊列，等待發(fā)送。

2) 全局通信階段。計算節(jié)點之間以點對點的方式進(jìn)行通信。

3) 柵欄同步階段。超步以柵欄同步為結(jié)束點，本次超步的數(shù)據(jù)通信在柵欄同步結(jié)束之后才生效，供下一超步使用。在確保通信過程中交換的數(shù)據(jù)被傳送到目的計算節(jié)點上，并且每個計算節(jié)點完成當(dāng)前超步中執(zhí)行的計算和通信之后，才可以進(jìn)入下一超步；否則停止等待其他節(jié)點完成計算和通信。

圖2 BSP模型結(jié)構(gòu)

Fig. 2 Structure of BSP model

圖3 超步的結(jié)構(gòu)Fig. 3 Structure of super step

綜上所述，BSP模型可以理解為是水平方向的并行(各個計算節(jié)點并行計算)和垂直方向的串行(超步之間串行執(zhí)行)，有如下特點：

1)將整個計算過程細(xì)分為多個串行的超步，超步內(nèi)并行計算，將通信和同步解耦，從而有效避免死鎖；

2)強(qiáng)調(diào)計算任務(wù)和通信任務(wù)分離，而通信任務(wù)僅僅完成點對點的消息傳遞，不提供組合、復(fù)制和廣播等功能，簡化了通信協(xié)議；

3)超步之內(nèi)各計算節(jié)點之間無需同步，超步之間各計算節(jié)點之間需要同步，因此BSP模型是介于嚴(yán)格同步的并行計算模型和異步的并行計算模型之間的模型。

2.2 SSP并行計算模型

BSP模型在實際應(yīng)用中存在慢機(jī)(Straggler)現(xiàn)象，由于計算節(jié)點的實際性能有差異，整個計算進(jìn)度由最慢的計算節(jié)點決定。于是Cipar等[6]提出了SSP模型來解決這個問題。

SSP模型是一個有界異步的橋接模型，該模型不僅可以解決BSP模型中的慢機(jī)問題，同時保留了BSP模型中同步機(jī)制的優(yōu)點。假設(shè)應(yīng)用SSP模型時采用主從式架構(gòu)，其基本原理如下：假設(shè)有P個從計算節(jié)點，以迭代的方式來優(yōu)化機(jī)器學(xué)習(xí)問題(Δ、F)，每一個計算節(jié)點維護(hù)迭代計數(shù)器t和模型參數(shù)A的本地視圖(相當(dāng)于一份拷貝)，在完成一輪迭代計算之后，每個計算節(jié)點提交本次運算得出的參數(shù)更新Δ，然后執(zhí)行如下操作：

1) 調(diào)用clock()函數(shù)，表示完成了該次迭代計算；

2) 迭代計數(shù)器t增加1；

3) 通知主節(jié)點將該節(jié)點的參數(shù)更新Δ傳播給其他的計算節(jié)點，以便其他計算節(jié)點更新其模型參數(shù)的本地視圖Aloc；

這里的clock()函數(shù)的作用類似于BSP模型中的柵欄同步，不同的是在SSP模型中，由于每個節(jié)點是異步計算，所以一個計算節(jié)點提交的更新Δ不會立刻傳遞給其他節(jié)點，這就導(dǎo)致其他節(jié)點進(jìn)行下一輪迭代時可能只接收到了部分參數(shù)更新，那么這些節(jié)點的模型參數(shù)Apt(在第t輪第p個節(jié)點保存的模型參數(shù))的本地視圖就變得陳舊(Stale)。對于一個給定的陳舊閾值s≥0(s表示節(jié)點之間的迭代輪數(shù)差)，基于SSP模型的并行系統(tǒng)必須滿足以下有界陳舊條件(如圖4所示)：

1) 迭代輪數(shù)之差不大于給定的閾值。運行最快的和最慢的計算節(jié)點的迭代輪數(shù)之差必須不大于s，否則最快的計算節(jié)點將被強(qiáng)制等待最慢的計算節(jié)點。

2) 提交的更新帶有標(biāo)簽。在第t輪迭代結(jié)束，調(diào)用clock()函數(shù)之前，提交的更新Δ需要帶有迭代輪數(shù)t。

3) 能夠保證模型狀態(tài)。一個計算節(jié)點第t輪計算更新Δ時，需保證該節(jié)點接收到了在[0,t-s-1]輪內(nèi)的所有模型參數(shù)更新。

4) 能夠讀取本地緩存。每一個計算節(jié)點直接用自己提交的更新Δ來更新模型參數(shù)A的本地視圖。

SSP模型的理論分析和收斂性分析參見文獻(xiàn)[12，17]。

2.3 并行計算模型小結(jié)

作BSP、SSP、AP模型各有優(yōu)缺點，適用于不同的應(yīng)用場景，下面對BSP、SSP和AP模型作對比。這些模型之間的主要區(qū)別就在于運行原理不同(如圖4～6)。其中AP模型是異步并行模型，其優(yōu)點是由于沒有柵欄同步，因此不存在慢機(jī)問題，并且計算節(jié)點在運算的同時可以與其他節(jié)點進(jìn)行通信，傳遞更新；但是難以維護(hù)數(shù)據(jù)一致性。BSP模型中的同步機(jī)制保證了數(shù)據(jù)一致性，但是存在慢機(jī)問題。SSP模型放松了一致性要求，解決了BSP模型中的慢機(jī)問題，并借鑒了AP模型的優(yōu)點，在指定迭代輪數(shù)范圍內(nèi)允許各計算節(jié)點異步執(zhí)行計算任務(wù)。因此這些模型之間不存在孰優(yōu)孰劣，只是各個模型適用于解決不同的大數(shù)據(jù)問題。AP模型適合于解決實時的大數(shù)據(jù)問題；BSP模型和MapReduce模型類似，適合于解決離線的大數(shù)據(jù)問題以及圖計算；因為有界異步的執(zhí)行方式與機(jī)器學(xué)習(xí)算法的容錯特點契合，所以SSP模型相比BSP模型更適合于解決大數(shù)據(jù)機(jī)器學(xué)習(xí)問題。

圖4 BSP模型的運行原理示意圖Fig. 4 Execution of BSP model

圖5 SSP模型的運行原理示意圖Fig. 5 Execution of SSP model

圖6 AP模型的運行原理示意圖Fig. 6 Execution of AP model

3 大數(shù)據(jù)機(jī)器學(xué)習(xí)平臺及相關(guān)編程模型

介紹完機(jī)器學(xué)習(xí)的相關(guān)背景和并行計算模型之后，接下來重點介紹大數(shù)據(jù)機(jī)器學(xué)習(xí)平臺(包括框架)。GraphLab[18-19]由卡內(nèi)基·梅隆大學(xué)(Carnegie Mellon University, CMU)的Select實驗室于2010年提出，是面向機(jī)器學(xué)習(xí)的流處理并行框架。GraphLab適用于圖計算，其基本思想是將數(shù)據(jù)抽象成Graph結(jié)構(gòu)，將算法的執(zhí)行過程抽象成Gather、Apply、Scatter三個步驟，其并行化的核心思想是對頂點的切分。還有DMLC(http://dmlc.ml/)是一個開源分布式機(jī)器學(xué)習(xí)項目，集成了XGBoost、MXNet、Minerva等機(jī)器學(xué)習(xí)庫與dmlc-core、Rabit、mshadow和參數(shù)服務(wù)器ps-lite等系統(tǒng)組件。因為Apache Mahout框架、Apache Spark平臺以及Petuum較為流行，所以本文主要介紹這三種平臺(框架)。

3.1 Apache Mahout 框架

基于Chu等[20]的文章，Apache Lucene(開源搜索)社區(qū)中對機(jī)器學(xué)習(xí)感興趣的成員于2008年發(fā)起了Mahout，2010年Mahout成為了Apache頂級項目，Apache Mahout的目標(biāo)是為快速創(chuàng)建可擴(kuò)展的高性能的機(jī)器學(xué)習(xí)應(yīng)用提供運行和開發(fā)環(huán)境。在Apache Mahout 0.10.0版本之前，Mahout主要是基于MapReduce，運行于Hadoop平臺。從Apache Mahout 0.10.0版本開始支持運行于Apache Spark平臺。Apache Mahout的主要特征有：

1) 是一個開源的機(jī)器學(xué)習(xí)軟件庫；

2) 是為創(chuàng)建可擴(kuò)展算法的一個既簡單又?jǐn)U展性好的編程環(huán)境和框架；

3) 為Hadoop、Scala+Apache Spark、H2O等平臺提供多種預(yù)制的機(jī)器學(xué)習(xí)算法；

4) 提供類似于R語言語法的矢量數(shù)學(xué)實驗環(huán)境Samsara。

Apache Mahout有3個核心主題：推薦引擎(協(xié)同過濾、頻繁項集挖掘)，聚類和分類。下面列出一些Mahout中的算法：隨機(jī)矩陣的奇異值分解算法(SSVD(Stochastic Singular Value Decomposition)、DSSVD(Distributed Stochastic Singular Value Decomposition))、隨機(jī)主成分分析算法(SPCA(Stochastic Principal Component Analysis)、DSPCA(Distributed Stochastic Principal Component Analysis))、樸素貝葉斯分類算法、協(xié)同過濾算法(Item和Row的相似性)、分布式正則化交替最小二乘法(Distributed Alternating Least Squares, DALS)等。在結(jié)合開源的協(xié)同過濾項目Taste后，協(xié)同過濾算法成為Apache Mahout中最受歡迎的算法。下面簡單介紹Apache Mahout 0.10.0版本之前所采用的MapReduce編程模型。

3.1.1 MapReduce編程模型

MapReduce[21]是一種面向大規(guī)模數(shù)據(jù)處理的并行程序設(shè)計模式(parallel programming paradigm)，由兩名Google的研究員Jeffrey Dean和Sanjay Ghemawat在2004年時提出。Google公司設(shè)計MapReduce的初衷主要是為了實現(xiàn)在搜索引擎中大規(guī)模網(wǎng)頁數(shù)據(jù)的并行化處理，MapReduce的推出給大數(shù)據(jù)并行處理帶來了革命性的影響，一度成為大數(shù)據(jù)處理的工業(yè)標(biāo)準(zhǔn)。圖7描述了典型的大數(shù)據(jù)處理的過程，MapReduce將以上的處理過程抽象為兩個基本操作。把前兩步(a，b)操作抽象為Map操作,把后兩步(d，e)操作抽象為Reduce操作。Map操作主要負(fù)責(zé)對一組數(shù)據(jù)記錄進(jìn)行某種重復(fù)處理，而Reduce操作主要負(fù)責(zé)對Map的中間結(jié)果進(jìn)行某種進(jìn)一步的結(jié)果整理和輸出。

圖7 典型的順序式大數(shù)據(jù)處理的過程Fig. 7 Typical sequential process to deal with big data

由于MapReduce模型在完成一次同步通信需要消耗大量時間(每一次迭代后的中間結(jié)果需要寫入磁盤，下一次迭代又從磁盤讀取數(shù)據(jù))，以及粗粒度的容錯機(jī)制(主要采用檢查點checkpoint方式，階段任務(wù)有一個失敗需要全部重新計算)，已經(jīng)不能夠滿足用戶對實時性、高效運算等方面的要求。隨著內(nèi)存計算Apache Spark的流行，Mahout因其強(qiáng)大的可擴(kuò)展能力，已經(jīng)支持運行于Apache Spark平臺。接下來介紹繼承了MapReduce的可擴(kuò)展性以及容錯能力并且克服了部分MapReduce缺陷的Apache Spark平臺，Apache Spark涉及圖處理、機(jī)器學(xué)習(xí)、流處理等多個大數(shù)據(jù)處理領(lǐng)域。

3.1.2 Apache Mahout小結(jié)

Apache Mahout簡化了編程人員的工作。通常，在Hadoop云平臺下編程不僅要求編程人員對Hadoop云平臺框架比較熟悉，還要熟悉Hadoop云平臺下底層數(shù)據(jù)流、Map和Reduce原理，這是基本的編程要求。此外，在編寫某一個算法時需要對算法原理有透徹的理解。因此，編寫云平臺下的算法程序是高難度的開發(fā)工作。但是，如果使用Apache Mahout，那么編程人員就不用自己編寫復(fù)雜的算法，不需要非常了解云平臺的框架和數(shù)據(jù)流程的理論知識。只需要了解算法的大概原理、算法實際應(yīng)用環(huán)境和如何調(diào)用Apache Mahout相關(guān)算法的程序接口。當(dāng)然，在具體的項目中，編程人員需要根據(jù)實際需求在Apache Mahout源代碼基礎(chǔ)上進(jìn)行二次開發(fā)以滿足具體的實際應(yīng)用情況。

3.2 Apache Spark平臺

Spark[22]誕生于伯克利大學(xué)的AMPLab(Algorithms Machines and People Lab)，于2010年正式開源，于2014年成為Apache的頂級項目。 Spark在2014年11月的Daytona Gray Sort 100 TB Benchmark競賽中打破了由Hadoop MapReduce保持的排序紀(jì)錄。Spark利用1/10的節(jié)點數(shù)，把100 TB數(shù)據(jù)的排序時間從72 min降低到了23 min。在介紹Apache Spark之前，先介紹一下AMPLab的伯克利數(shù)據(jù)分析棧(BDAS(https://amplab.cs.berkeley.edu/software/))。如圖8所示，BDAS包括5層：資源虛擬化(Resource Virtualization)、存儲系統(tǒng)(Storage)、處理引擎(Processing Engine)、訪問接口(Access and Interfaces)以及內(nèi)部應(yīng)用(In-house Apps)。資源虛擬化主要指集群的管理和計算資源的調(diào)度；存儲系統(tǒng)主要指分布式存儲系統(tǒng)，具有高度容錯性，提供高吞吐量的數(shù)據(jù)訪問；處理引擎指通用的大數(shù)據(jù)處理引擎；訪問接口指BDAS為各類大數(shù)據(jù)問題提供的解決方案的APIs。圖8中粗框中的就是Apache Spark平臺。Spark主要具有如下特點：

1) 速度極快。使用有向無環(huán)圖(Directed Acyclic Graph，DAG)執(zhí)行引擎以支持循環(huán)數(shù)據(jù)流，并將中間數(shù)據(jù)放到內(nèi)存中，迭代運算效率高。

2) 易于使用。支持使用Scala、Java、Python 和R語言進(jìn)行編程，可以通過Spark Shell進(jìn)行交互式編程。

3) 通用性強(qiáng)。Spark提供了完整而強(qiáng)大的組件庫，包括SQL查詢、流式計算、機(jī)器學(xué)習(xí)和圖算法組件。

4) 模式多樣?？蛇\行于獨立的集群模式中，可運行于Hadoop平臺，也可運行于Amazon EC2等云環(huán)境中，并且可以訪問HDFS、Cassandra、HBase、Hive等多種數(shù)據(jù)源。

Spark具有上述諸多優(yōu)點主要是由于其采用了不同于MapReduce的數(shù)據(jù)結(jié)構(gòu)，即彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset，RDD)[23]，下面就介紹一下RDD。

圖8 伯克利數(shù)據(jù)分析棧Fig. 8 Berkeley data analytics stack

3.2.1 RDD

RDD是Apache Spark平臺的基礎(chǔ)，RDD有兩層含義：

1) 數(shù)據(jù)結(jié)構(gòu)RDD是一個只讀的、可分區(qū)的記錄集合，一個RDD可以包含多個分區(qū)，每個分區(qū)就是一個數(shù)據(jù)集片段。RDD本質(zhì)上是一個內(nèi)存數(shù)據(jù)集，解決了MapReduce中將中間結(jié)果寫入磁盤或者HDFS帶來的密集的磁盤讀寫和大量的網(wǎng)絡(luò)通信開銷問題。

2) 編程模型Spark在RDD上定義了兩類操作(如圖9所示)：轉(zhuǎn)換(Transformation)和動作(Action)，使得開發(fā)人員不必關(guān)心數(shù)據(jù)的分布式特性，只需將具體的應(yīng)用邏輯編寫為一系列RDD的操作。轉(zhuǎn)換操作返回新的RDD，而動作操作的結(jié)果是一個值或是將數(shù)據(jù)導(dǎo)入到存儲系統(tǒng)。

Apache Spark平臺為了節(jié)約計算資源，在RDD上定義的采用惰性調(diào)用機(jī)制，只有在調(diào)用動作操作時才會真正觸發(fā)所有定義的操作。由轉(zhuǎn)換操作得到的父子RDD之間存在依賴關(guān)系(如圖10所示)，如果一個父RDD中的一個分區(qū)只被一個子RDD的一個分區(qū)使用，則稱之為窄依賴(Narrow Dependency)；若被一個子RDD的多個分區(qū)使用，則稱之為寬依賴(Wide Dependency)。如果RDD之間是窄依賴，則可以在同一個計算節(jié)點上以管道形式(pipeline)執(zhí)行這些RDD上的操作，從而避免了多個操作之間的數(shù)據(jù)同步。

圖9 RDD上的兩大類操作Fig. 9 Two kinds of operations on RDD

Spark在容錯性能方面有較大的提升，增加了Lineage容錯機(jī)制。實際編程時，在一個RDD上調(diào)用的各種轉(zhuǎn)換操作構(gòu)成了計算鏈(Compute Chain)，把這個Compute Chain看作是RDD之間演化的Lineage(如圖9所示)。因此在部分計算結(jié)果丟失時，只需要根據(jù)這個Lineage重算即可。因為當(dāng)RDD之間是窄依賴時，重新計算中間丟失的RDD不需要依賴其他計算節(jié)點參與，所以此時采用Lineage容錯的效率才比采用數(shù)據(jù)檢查點(Check point)的高。當(dāng)RDD之間是寬依賴或者Lineage過長時，設(shè)置數(shù)據(jù)檢查點比采用Lineage的效率更高。

圖10 RDD之間的依賴關(guān)系Fig. 10 Dependency between RDDs

下面介紹一下基于RDD構(gòu)建的Spark生態(tài)系統(tǒng)(如圖11所示)，由如下部分組成。

圖11 Spark生態(tài)系統(tǒng)Fig. 11 Spark ecosystem

1) Spark Core。定義了Spark的基本功能，包含任務(wù)調(diào)度、內(nèi)存管理、容錯恢復(fù)、與存儲系統(tǒng)交互等。Spark Core為上層組件提供了Scala、Java、Python和R語言的編程接口即Spark核心應(yīng)用編程接口(Spark Core API)。

2) Spark Streaming。是構(gòu)建在Spark上的流數(shù)據(jù)處理框架，基本原理是將流數(shù)據(jù)分成小的時間片斷(例如：每2秒分割為一個片段)，以類似批量處理的方式來處理這小部分?jǐn)?shù)據(jù)。這種小批量處理的方式使得Spark Streaming可以同時兼容批量和實時數(shù)據(jù)處理的邏輯和算法。

3) Spark SQL。用于處理結(jié)構(gòu)化數(shù)據(jù)，可使用類似于Hive查詢語言(Hive Query Language， HQL)的SQL語句來查詢數(shù)據(jù)。

4) Spark MLlib。是一個可擴(kuò)展的Spark機(jī)器學(xué)習(xí)庫，由通用的機(jī)器學(xué)習(xí)算法和工具組成，包括二元分類、線性回歸、聚類、協(xié)同過濾、梯度下降等。

5) Spark GraphX。用于操作圖(如社交網(wǎng)絡(luò)的好友圖)和執(zhí)行基于圖的并行計算。通過引入彈性分布式屬性圖(Resilient Distributed Property Graph)，一種頂點和邊都帶有屬性的有向多重圖，可以使用與每個節(jié)點和邊綁定的任意屬性來創(chuàng)建一個有向圖。GraphX還提供了各種各樣的操作圖的操作符，以及通用的圖算法。

其中Spark Core是其他4個部分的基礎(chǔ)，Apache Spark通過Spark SQL、Spark Streaming、MLLib、GraphX這些組件近乎完美地解決了大數(shù)據(jù)處理中批處理(Batch Processing)、流處理(Streaming Processing)和即席查詢(Ad-Hoc Query)三大核心問題。下面詳細(xì)介紹一下Spark機(jī)器學(xué)習(xí)庫MLLib。

3.2.2 Spark機(jī)器學(xué)習(xí)庫

Spark MLlib是Spark的分布式機(jī)器學(xué)習(xí)庫，包含豐富的機(jī)器學(xué)習(xí)算法實現(xiàn)。需要注意的是，Spark機(jī)器學(xué)習(xí)庫從1.2版本之后被分為兩個包：

1) spark.mllib。是Spark最原始的機(jī)器學(xué)習(xí)庫，其中的機(jī)器學(xué)習(xí)算法都是基于RDD實現(xiàn)。但是使用spark.mllib構(gòu)建完整的機(jī)器學(xué)習(xí)工作流比較困難，需要用到spark.ml。

2) spark.ml。在Spark 1.2版本中加入spark.ml，spark.ml引入了ML Pipeline。ML Pipeline提供了基于DataFrame的一套統(tǒng)一的高級APIs，幫助用戶創(chuàng)建和調(diào)整機(jī)器學(xué)習(xí)工作流。

使用機(jī)器學(xué)習(xí)來解決實際問題時通常包含一系列基本的步驟：數(shù)據(jù)預(yù)處理、特征提取、訓(xùn)練模型、模型驗證等，可以將其看作是一個包含多個步驟的工作流。許多機(jī)器學(xué)習(xí)庫不提供工作流中所需要的全部功能，大多數(shù)機(jī)器學(xué)習(xí)庫只專注于一項功能，比如數(shù)據(jù)預(yù)處理或者特征提??；因此往往需要使用各種庫來拼湊出一條機(jī)器學(xué)習(xí)工作流，這樣做既費時又費力?，F(xiàn)在只需要借助spark.ml便可完成這樣的機(jī)器學(xué)習(xí)工作流的構(gòu)建，而且從Spark2.0開始，spark.mllib進(jìn)入維護(hù)模式(即不增加任何新的特性)，并預(yù)期于3.0版本的時候被移除出spark.mllib，spark.ml將成為Spark主要的機(jī)器學(xué)習(xí)庫。Spark機(jī)器學(xué)習(xí)庫提供了通用機(jī)器學(xué)習(xí)算法的實現(xiàn)，目前支持4 種常見的機(jī)器學(xué)習(xí)問題：分類、回歸、聚類和協(xié)同過濾。表1列出了Spark機(jī)器學(xué)習(xí)庫中主要的機(jī)器學(xué)習(xí)算法。

表1 MLlib中主要的機(jī)器學(xué)習(xí)算法Tab. 1 Main machine learning algorithms in MLlib

Spark機(jī)器學(xué)習(xí)庫還提供了一系列低級原語和基礎(chǔ)工具用于凸優(yōu)化、分布式線性代數(shù)、統(tǒng)計分析、特征提取等，還支持對各種輸入輸出格式化，并針對分布式機(jī)器學(xué)習(xí)有許多優(yōu)化措施。例如在交替最小二乘法中，使用阻塞來減少Java虛擬機(jī)(Java Virtual Machine, JVM)垃圾回收的開銷；在決策樹算法中，離散化依賴數(shù)據(jù)的特征來降低通信開銷。

3.2.3 Apache Spark小結(jié)

Spark提供了豐富的編程接口，支持多種編程語言，為開發(fā)人員帶來了極大的便利。Spark支持多種部署方式，包括單機(jī)模式、分布式模式。采用分布式模式部署時，通常采用主從式架構(gòu)，雖然在高效的通信原語的基礎(chǔ)上，Spark機(jī)器學(xué)習(xí)算法能夠高效運行，并且Spark能夠快速將規(guī)模較大的模型分配給計算節(jié)點。但是主節(jié)點通常只有一個，這就導(dǎo)致Spark在訓(xùn)練大規(guī)模的機(jī)器學(xué)習(xí)模型，尤其是迭代式機(jī)器學(xué)習(xí)模型時，就有點力不從心。因為Apache Mahout和Spark都是基于BSP模型，在通信上的開銷占據(jù)了整個計算過程開銷的較大部分，而且每個計算節(jié)點都需要和主節(jié)點通信，因此訓(xùn)練大規(guī)模模型將十分緩慢。如果需要解決這個問題，可以采用SSP模型作為底層的并行計算模型。下面就介紹基于SSP模型的機(jī)器學(xué)習(xí)平臺Petuum。

3.3 Petuum

Petuum[24,29]是一個分布式機(jī)器學(xué)習(xí)平臺。為了應(yīng)對機(jī)器學(xué)習(xí)在大規(guī)模場景下的挑戰(zhàn)：大數(shù)據(jù)(數(shù)據(jù)樣本數(shù)目龐大) 以及大模型(模型參數(shù)眾多)，Petuum為數(shù)據(jù)并行和模型并行提供了通用的APIs，從而簡化了相關(guān)機(jī)器學(xué)習(xí)算法的實現(xiàn)。與通用的大數(shù)據(jù)處理平臺(如Hadoop、Spark)不同，Petuum專門為處理機(jī)器學(xué)習(xí)問題而設(shè)計。Petuum通過充分利用機(jī)器學(xué)習(xí)算法的特征(如迭代性、容錯性、參數(shù)收斂的不均勻性等)來提高訓(xùn)練機(jī)器學(xué)習(xí)模型的效率。Petuum系統(tǒng)由調(diào)度器(Scheduler)、參數(shù)服務(wù)器、計算節(jié)點(Workers)和Petuum機(jī)器學(xué)習(xí)算法組成,如圖12所示。接下來介紹一下各部分的功能：

圖12 Petuum系統(tǒng)的結(jié)構(gòu)Fig. 12 Structure of Petuum system

調(diào)度器 該模塊負(fù)責(zé)模型并行化，允許開發(fā)人員通過自定義函數(shù)schedule()(類似于式(4)中的)來控制計算節(jié)點在本輪迭代中僅對指定的模型參數(shù)子集進(jìn)行更新。調(diào)度器通過調(diào)度控制通道將這些參數(shù)的標(biāo)識(函數(shù)schedule()的輸出值)傳遞給計算節(jié)點，而實際的參數(shù)值由參數(shù)服務(wù)器通過參數(shù)交換通道分發(fā)。

計算節(jié)點 計算節(jié)點p在接收到由參數(shù)服務(wù)器分配的模型參數(shù)之后，在數(shù)據(jù)D或者數(shù)據(jù)分片上并行地執(zhí)行更新函數(shù)push()(類似于式(3)中的)。當(dāng)計算節(jié)點執(zhí)行push()時，模型參數(shù)的本地視圖Aloc會自動地通過參數(shù)交換通道與參數(shù)服務(wù)器進(jìn)行同步。在push()執(zhí)行完畢之后，調(diào)度器將使用新的模型參數(shù)來決策下一輪迭代的調(diào)度。在Petuum系統(tǒng)中沒有定義固定的數(shù)據(jù)抽象，所以計算節(jié)點可以讀取內(nèi)存中的數(shù)據(jù)、磁盤中的數(shù)據(jù)或者分布式文件系統(tǒng)中的數(shù)據(jù)；而且開發(fā)人員可以控制計算節(jié)點讀取數(shù)據(jù)的順序，在隨機(jī)優(yōu)化算法中計算節(jié)點可以一次僅采樣一個數(shù)據(jù)點，在批處理算法中計算節(jié)點可以在一輪迭代中讀遍所有的數(shù)據(jù)。

參數(shù)服務(wù)器 通過一個類似于鍵值存儲的分布式共享內(nèi)存API為開發(fā)人員提供了對模型參數(shù)A的全局訪問。為了利用機(jī)器學(xué)習(xí)算法的特點，參數(shù)服務(wù)器是基于SSP并行計算模型實現(xiàn)的。機(jī)器學(xué)習(xí)算法大多是基于優(yōu)化的算法，而且用遞歸來實現(xiàn)，有一定的容錯能力，這些特點恰好與SSP模型中的有界陳舊相契合。

上述Petuum系統(tǒng)的功能主要由以下3個組件實現(xiàn)：

1) B?sen。針對數(shù)據(jù)并行機(jī)器學(xué)習(xí)編程是具備高效通信機(jī)制的分布式鍵值存儲系統(tǒng)。

2) Strads。一個高速、高精度的可編程參數(shù)調(diào)度器,為了模型并行化的機(jī)器學(xué)習(xí)問題而設(shè)計。

3) Poseidon。一個基于Caffe的分布式多GPU深度學(xué)習(xí)編程框架。

Petuum能夠高效地運行在集群和云計算平臺(比如Amazon EC2和Google GCE)上。其中的參數(shù)服務(wù)器被譽為“MapReduce的替代者”，下一節(jié)將詳細(xì)闡述參數(shù)服務(wù)器。

3.3.1 參數(shù)服務(wù)器

參數(shù)服務(wù)器到目前為止可分為三代，Petuum采用的是第二代參數(shù)服務(wù)器。第一代的原型可以追溯到文獻(xiàn)[25]，如圖13所示。其中每個sampler處理與之相關(guān)的數(shù)據(jù)子集，同時有一個用于同步的線程，使本地模型參數(shù)和全局模型參數(shù)保持一致，采用一個分布式的Memcached存放全局模型參數(shù)，這樣就提供了有效的機(jī)制用于在分布式系統(tǒng)不同的Worker節(jié)點之間同步模型參數(shù)，而每個Worker只需要保存它計算時所依賴的一小部分參數(shù)即可。當(dāng)然，這里存放模型參數(shù)的不是普通的Key-Value抽象，因為以Key-Value為單元進(jìn)行頻繁的模型參數(shù)同步會導(dǎo)致過高的通信開銷，因此參數(shù)服務(wù)器通常采用數(shù)學(xué)封裝來進(jìn)行參數(shù)同步，比如向量、張量、矩陣的行列等。但是這個原型在可擴(kuò)展性方面有所欠缺，并且通信延遲高。Ahmed等[26]提出的框架擴(kuò)展了該原型，并引入了新的特性：為異步更新全局變量提供一個更高效的通信機(jī)制，為本地變量提供一個基于磁盤的有計劃的緩存機(jī)制以及一個全新的容錯機(jī)制等，并且開源了該系統(tǒng)的實現(xiàn)YahooLDA(https://github.com/sudar/Yahoo_LDA)。

圖13 第一代參數(shù)服務(wù)器Fig. 13 The 1st generation parameter server architecture

第二代參數(shù)服務(wù)器[27]可以在Dean等[28]提出的DistBelief框架中找到原型，基本架構(gòu)如圖14所示。Dai等[29]提出的Petuum-PS結(jié)合SSP模型降低了第一代參數(shù)服務(wù)器的同步和通信開銷。

圖14 第二代參數(shù)服務(wù)器架構(gòu)Fig. 14 The 2nd generation parameter server architecture

Li等[30-31]提出了第三代參數(shù)服務(wù)器，克服了第兩代的缺點(只能采用單一的一致性模型等)，其基本架構(gòu)如圖15 所示，參數(shù)服務(wù)器中的節(jié)點分為服務(wù)組(Server Group)和多個工作組(Worker Group)：1)服務(wù)組中包含一個服務(wù)管理節(jié)點(Server Manager)和多個服務(wù)節(jié)點(Server Node)。服務(wù)管理節(jié)點負(fù)責(zé)維護(hù)元數(shù)據(jù)的一致性，比如服務(wù)節(jié)點的狀態(tài)、參數(shù)的分配等；服務(wù)節(jié)點負(fù)責(zé)各自的參數(shù)，服務(wù)節(jié)點之間可以互相通信，復(fù)制或者遷移參數(shù)；服務(wù)組共同維護(hù)所有參數(shù)的更新。2)工作組包含一個任務(wù)調(diào)度器(Task Scheduler)和多個計算節(jié)點(Worker Node)。一個工作組運行一個應(yīng)用，任務(wù)調(diào)度器負(fù)責(zé)向計算節(jié)點分配任務(wù)，并且監(jiān)控計算節(jié)點的運行狀態(tài)，當(dāng)有計算節(jié)點被加入或者移除，任務(wù)調(diào)度器則重新分配任務(wù)；計算節(jié)點之間不進(jìn)行通信，只和對應(yīng)的服務(wù)節(jié)點進(jìn)行通信。第三代參數(shù)服務(wù)器有如下5個特點：

1) 高效的通信(Efficient Communication)。采用異步通信模型，完成一輪計算的節(jié)點不必等待(除非被請求)其他節(jié)點完成計算，這樣的機(jī)制能夠減少延時，并且優(yōu)化機(jī)器學(xué)習(xí)任務(wù)的調(diào)度，提高效率。

2) 靈活的一致性模型(Flexible Consistency models)。寬松的一致性要求允許算法設(shè)計者根據(jù)自身的情況(數(shù)據(jù)量、硬件等) 權(quán)衡算法收斂速度和系統(tǒng)性能。

3) 靈活的可擴(kuò)展性(Elastic Scalability)。采用一致性哈希算法[32-33]進(jìn)行節(jié)點管理，在添加刪除節(jié)點時無需重新運行系統(tǒng)。

4) 容錯和穩(wěn)定性(Fault Tolerance and Durability)。從非災(zāi)難性機(jī)器故障中恢復(fù)只需1 s，不中斷計算；Vector clocks[34-35]保證在經(jīng)歷網(wǎng)絡(luò)分區(qū)和故障之后系統(tǒng)能夠良好運行。

5) 易用(Ease of Use)。為了簡化機(jī)器學(xué)習(xí)應(yīng)用開發(fā)，全局共享的參數(shù)被表示成(稀疏的)向量和矩陣，并且提供的線性代數(shù)的數(shù)據(jù)類型支持多線程。

綜上所述，參數(shù)服務(wù)器由服務(wù)節(jié)點和計算節(jié)點組成，基本結(jié)構(gòu)如圖16所示，其中機(jī)器學(xué)習(xí)算法的參數(shù)由服務(wù)節(jié)點管理，機(jī)器學(xué)習(xí)算法的訓(xùn)練由計算節(jié)點完成；計算節(jié)點只能與對應(yīng)的服務(wù)節(jié)點通信，服務(wù)節(jié)點之間相互復(fù)制或遷移參數(shù)。

圖15 第三代參數(shù)服務(wù)器架構(gòu)Fig. 15 The 3rd generation parameter server architecture

3.3.2 Petuum小結(jié)

Petuum創(chuàng)新之處是將參數(shù)服務(wù)器和SSP并行模型結(jié)合，較好地實現(xiàn)了數(shù)據(jù)和模型同時并行化。因此，與Spark相比，Petuum能夠處理更大規(guī)模的數(shù)據(jù)和訓(xùn)練更大規(guī)模的模型。由于Petuum采用第二代參數(shù)服務(wù)器，第三代參數(shù)服務(wù)器在第二代的基礎(chǔ)上進(jìn)行了很多優(yōu)化，比如采用更靈活的一致性模型，支持ASP、BSP、SSP多種并行計算模型；更強(qiáng)的可擴(kuò)展性，支持動態(tài)添加和刪除計算節(jié)點，因此Petuum系統(tǒng)還有較大的提升空間。由于只提供了簡單的編程接口，而且目前提供的機(jī)器學(xué)習(xí)算法實現(xiàn)較少，所以相對于Spark，在Petuum系統(tǒng)上實現(xiàn)自定義的機(jī)器學(xué)習(xí)算法的難度較大。

圖16 參數(shù)服務(wù)器基本架構(gòu)Fig. 16 Basic structure of parameter server

4 結(jié)語

本文從歸納大部分機(jī)器學(xué)習(xí)算法的數(shù)學(xué)表達(dá)式開始，分析介紹了機(jī)器學(xué)習(xí)算法的特點及其理論上的數(shù)據(jù)并行化和模型并行化，進(jìn)而介紹相關(guān)的并行計算模型以及基于這些模型的大數(shù)據(jù)機(jī)器學(xué)習(xí)框架和平臺。下面從采用的抽象數(shù)據(jù)結(jié)構(gòu)、并行計算模型、容錯機(jī)制等方面總結(jié)一下上述典型的機(jī)器學(xué)習(xí)平臺，如表2所示。在機(jī)器學(xué)習(xí)平臺(框架)設(shè)計上，沒有普適的最好平臺，只有最適合實際計算問題的平臺。在訓(xùn)練機(jī)器學(xué)習(xí)模型時有一個共享的中間狀態(tài)：模型參數(shù)，計算過程中會不斷地讀寫中間狀態(tài)。在基于ASP并行模型的系統(tǒng)中，因為計算節(jié)點之間完全異步執(zhí)行，所以這種一致性模型的計算效率很高，但是模型參數(shù)沒有一致性保證，不同節(jié)點獲取到的是不同版本的模型參數(shù)，這樣的訓(xùn)練過程是不穩(wěn)定的，將會影響算法收斂性；在基于BSP并行模型的系統(tǒng)中，所有的計算節(jié)點在計算過程中都獲取一致的模型參數(shù)，因此能保證算法的收斂性，但是代價是同步造成的計算資源和時間的浪費；CMU的Xing教授提出了介于BSP和ASP兩者之間的SSP，通過限制模型參數(shù)的最大不一致版本數(shù)來控制整體的同步節(jié)奏，這樣既能緩解慢機(jī)問題，又使得算法相對于ASP在收斂性上有更好的保證。基于不同的并行模型可以很好地在運行速度和算法效果上進(jìn)行權(quán)衡。因此：1)Spark是一個通用的大數(shù)據(jù)平臺，適用于進(jìn)行大規(guī)模數(shù)據(jù)處理和小規(guī)模的機(jī)器學(xué)習(xí)，不適合于大規(guī)模機(jī)器學(xué)習(xí)；另外由于RDD 的不可變性，不適合參數(shù)反復(fù)更新的需求。這也是Spark不適合大規(guī)模機(jī)器學(xué)習(xí)的另一個原因。2)基于AP模型的GraphLab適合于進(jìn)行大規(guī)模圖計算的平臺，但是AP模型缺乏一致性保證，不適合于大規(guī)模機(jī)器學(xué)習(xí)。3)Petuum采用了SSP模型結(jié)合參數(shù)服務(wù)器，適合于大規(guī)模機(jī)器學(xué)習(xí)。

表2 典型機(jī)器學(xué)習(xí)平臺對比Tab. 2 Comparison of typical machine learning platforms

參數(shù)服務(wù)器有較高的可擴(kuò)展性和靈活性，能夠仿真AP、BSP、SSP等并行計算模型。參數(shù)服務(wù)器將模型表示成(Key,Value)向量，所以其在處理稀疏矩陣上有明顯的優(yōu)勢。而Spark的RDD數(shù)據(jù)抽象在處理低維稠密矩陣時有明顯的優(yōu)勢。針對參數(shù)服務(wù)器各類優(yōu)化將會成為未來主要的研究方向之一，比如服務(wù)節(jié)點和計算節(jié)點解耦來進(jìn)一步提高靈活性，提供更好的編程接口，方便編程人員開發(fā)復(fù)雜的機(jī)器學(xué)習(xí)算法；合并同一臺機(jī)器中多個線程的請求，因為同一次機(jī)器學(xué)習(xí)訓(xùn)練過程中，不同線程之間大概率會有很多重復(fù)的模型參數(shù)請求；使用或開發(fā)更好的緩存機(jī)制，來提升查詢效率。對于基于BSP模型的平臺，可以借鑒文獻(xiàn)[31]中提出的User-defined Filters過濾掉一些不重要的更新來提高通信效率，另外可以加入小任務(wù)調(diào)度控制，將慢機(jī)上未完成的小任務(wù)調(diào)度到處于等待狀態(tài)的節(jié)點上運行等等。另外，基于BSP模型的Spark平臺亦可嘗試更參數(shù)服務(wù)器結(jié)合，來提高性能和靈活性。對于基于SSP模型的平臺(如Petuum)，可以結(jié)合Li等提出的第三代參數(shù)服務(wù)器來取得更好的容錯性和穩(wěn)定性?？偠灾磥泶笠?guī)模機(jī)器學(xué)習(xí)平臺將會主要圍繞參數(shù)服務(wù)器來設(shè)計。

References)

[1] 王慶先, 孫世新, 尚明生,等. 并行計算模型研究[J]. 計算機(jī)科學(xué), 2004, 31(9):128-131.(WANG Q X, SUN S X, SHANG M S, et al. Research on parallel computing model[J]. Computer Science, 2004, 21(9):128-131.)

[2] 王歡, 都志輝. 并行計算模型對比分析[J]. 計算機(jī)科學(xué), 2005, 32(12):142-145.(WANG H, DU Z H. Contrastive analysis of parallel computation model[J]. Computer Science, 2005, 32(12):142-145.)

[3] 涂碧波, 鄒銘, 詹劍鋒,等. 多核處理器機(jī)群Memory層次化并行計算模型研究[J]. 計算機(jī)學(xué)報, 2008, 31(11):1948-1955.(TU B B, ZOU M, ZHAN J F, et al. Research on parallel computation model with memory hierarchy on multi-core cluster[J]. Chinese Journal of Computers, 2008, 31(11):1948-1955.)

[4] 劉方愛, 劉志勇, 喬香珍. 一種異步BSP模型及其程序優(yōu)化技術(shù)[J]. 計算機(jī)學(xué)報, 2002, 25(4):373-380. (LIU F A, LIU Z Y, QIAO X Z. An asynchronous BSP model and optimization techniques[J]. Chinese Journal of Computers, 2002, 25(4):373-380.)

[5] VALIANT L G. A bridging model for parallel computation[J]. Communications of the ACM, 1990, 33(8):103-111.

[6] CIPAR J, HO Q, KIM J K, et al. Solving the straggler problem with bounded staleness[C]// Proceedings of the 14th USENIX Conference on Hot Topics in Operating Systems. Berkeley, CA: USENIX Association, 2013: Article No. 22.

[7] 黃宜華. 大數(shù)據(jù)機(jī)器學(xué)習(xí)系統(tǒng)研究進(jìn)展[J]. 大數(shù)據(jù), 2015, 1(1):28-47.(HUANG Y H. Research progress on big data machine learning system[J]. Big Data Research, 2015, 1(1):28-47.)

[8] 何清, 李寧, 羅文娟,等. 大數(shù)據(jù)下的機(jī)器學(xué)習(xí)算法綜述[J]. 模式識別與人工智能, 2014, 27(4): 327-336.(HE Q, LI N, LUO W J, et al. A survey of machine learning algorithms for big data[J]. Pattern Recognition and Artificial Intelligence, 2014, 27(4):327-336.)

[9] BOTTOU L. Large-scale machine learning with stochastic gradient descent[C]// Proceedings of the 19th International Conference on Computational Statistics Paris France. Berlin: Springer, 2010:177-186.

[10] FERCOQ O, RICHTRIK P. Accelerated, parallel and proximal coordinate descent[J]. SIAM Journal on Optimization, 2014, 25(4): 1997-2023.

[11] BLEI D M, KUCUKELBIR A, MCAULIFFE J D. Variational inference: a review for statisticians[EB/OL].[2016- 11- 20]. https://www.cse.iitk.ac.in/users/piyush/courses/pml_winter16/VI_Review.pdf.

[12] XING E P, HO Q, XIE P, et al. Strategies and principles of distributed machine learning on big data[J]. Engineering Sciences, 2016, 2(2):179-195.

[13] RUDER S. An overview of gradient descent optimization algorithms[EB/OL].[2016- 11- 20]. http://128.84.21.199/pdf/1609.04747.pdf.

[14] DUCHI J, HAZAN E, SINGER Y. Adaptive subgradient methods for online learning and stochastic optimization[J]. Journal of Machine Learning Research, 2011, 12(7):2121-2159.

[15] ZEILER M D. ADADELTA: an adaptive learning rate method[EB/OL].[2016- 11- 20]. http://www.matthewzeiler.com/wp-content/uploads/2017/07/googleTR2012.pdf.

[16] 郝樹魁. Hadoop HDFS和MapReduce架構(gòu)淺析[J]. 郵電設(shè)計技術(shù), 2012(7):37-42.(HAO S K. Brief analysis of the architecture of Hadoop HDFS and MapReduce[J]. Designing Techniques of Posts and Telecommunications, 2012(7):37-42.)

[17] HO Q, CIPAR J, CUI H, et al. More effective distributed ML via a stale synchronous parallel parameter server[C]// Proceedings of the 26th International Conference on Neural Information Processing Systems. Lake Tahoe, Nevada: Curran Associates Inc., 2013:1223-1231.

[18] LOW Y, GONZALEZ J E, KYROLA A, et al. GraphLab: a new framework for parallel machine learning[EB/OL].[2016- 11- 20]. http://wwwdb.inf.tu-dresden.de/misc/SS15/PSHS/paper/GraphLab/Low_2010.pdf.

[19] LOW Y, BICKSON D, GONZALEZ J, et al. Distributed GraphLab: a framework for machine learning and data mining in the cloud[J]. Proceedings of the VLDB Endowment, 2012, 5(8): 716-727.

[20] CHU C T, KIM S K, LIN Y A, et al. Map-Reduce for machine learning on multicore[C]// Proceedings of the 19th International Conference on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2006:281-288.

[21] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[C]// Proceedings of the 6th USENIX Conference on Symposium on Opearting Systems Design and Implementation. Berkeley, CA: USENIX Association, 2004: Article No. 10.

[22] ZAHARIA M, CHOWDHURY M, FRANKLIN M J, et al. Spark: cluster computing with working sets[C]// Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. Berkeley, CA: USENIX Association, 2010: Article No. 10.

[23] ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]// Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: Article No. 2.

[24] XING E P, HO Q, DAI W, et al. Petuum: a new platform for distributed machine learning on big data[J]. IEEE Transactions on Big Data, 2015, 1(2):49-67.

[25] SMOLA A, NARAYANAMURTHY S. An architecture for parallel topic models[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2):703-710.

[26] AHMED A, ALY M, GONZALEZ J, et al. Scalable inference in latent variable models[C]// Proceedings of the 5th ACM International Conference on Web Search and Data Mining. New York: ACM, 2012:123-132.

[27] DAI W, KUMAR A, WEI J, et al. High-performance distributed ML at scale through parameter server consistency models[C]// Proceedings of the 29th AAAI Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press, 2015:79-87.

[28] DEAN J, CORRADO G S, MONGA R, et al. Large scale distributed deep networks[C]// Proceedings of the 25th International Conference on Neural Information Processing Systems. Lake Tahoe, Nevada: Curran Associates Inc., 2012:1223-1231.

[29] DAI W, WEI J, ZHENG X, et al. Petuum: a framework for iterative-convergent distributed ML[EB/OL].[2016- 11- 20]. http://www.u.arizona.edu/～junmingy/papers/Dai-etal-NIPS13.pdf.

[30] LI M, ZHOU L, YANG Z, et al. Parameter server for distributed machine learning[EB/OL].[2016- 11- 20]. http://www-cgi.cs.cmu.edu/～muli/file/ps.pdf.

[31] LI M, ANDERSEN D G, PARK J W, et al. Scaling distributed machine learning with the parameter server[C]// Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2014:583-598.

[32] KARGER D, LEHMAN E, LEIGHTON T, et al. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide Web[C]// Proceedings of the 29th ACM Symposium on Theory of Computing. New York: ACM, 1997:654-663.

[33] BYERS J, CONSIDINE J, MITZENMACHER M. Simple load balancing for distributed hash tables[C]// Proceedings of the 2nd International Workshop Peer-to-Peer Systems Ⅱ. Berlin: Springer, 2003:80-87.

[34] CHOUDHARI R, JAGADISH D. Paxos made simple[J]. ACM SIGACT News, 2001, 32(4): 51-58.

[35] DECANDIA G, HASTORUN D, JAMPANI M, et al. Dynamo: Amazon’s highly available key-value store[C]// Proceedings of the 21st ACM SIGOPS Symposium on Operating Systems Principles. New York: ACM, 2007:205-220.

This work is partially supported by the National Natural Science Foundation of China (61603197), the Natural Science Foundation of Jiangsu Province (BK20140885).

JIAOJiafeng, born in 1991, M. S. candidate. His research interests include large scale machine learning.

LIYun, born in 1974, Ph. D., professor. His research interests include machine learning, feature engineering.

Reviewoftypicalmachinelearningplatformsforbigdata

JIAO Jiafeng,LI Yun*

(SchoolofComputerScience,NanjingUniversityofPostsandTelecommunications,NanjingJiangsu210003,China)

Due to the volume, complex and fast-changing characteristics of big data, traditional machine learning platforms are not applicable. Therefore, designing an efficient and general machine learning platform for big data has become an important research issue. By introducing and analyzing the characteristics of machine learning algorithms and the data and model parallelization for large-scale machine learning, some common parallel computing models were presented. Bulk Synchronous Parallel (BSP), Stale Synchronous Parallel (SSP) computing models and the differences between BSP, SSP, and Asynchronous Parallel model (AP) were introduced. Then the typical machine learning platforms based on these parallel models and the advantages and disadvantages of these platforms were mainly introduced, and what kind of big data each typical machine learning platform was best suited for was pointed out. Finally, the typical machine learning platforms were summarized from the aspects of abstract data structure, parallel computing model and fault tolerance mechanism. Some suggestions and prospects were put forward.

big data; machine learning platform; parallel computing model; parameter server

2017- 05- 16;

2017- 07- 21。

國家自然科學(xué)基金資助項目(61603197); 江蘇省自然科學(xué)基金資助項目(BK20140885)。

焦嘉烽(1991—)，男，江蘇江陰人，碩士研究生，主要研究方向：大規(guī)模機(jī)器學(xué)習(xí)； 李云(1974—)，男，安徽望江人，教授，博士生導(dǎo)師，博士，主要研究方向：機(jī)器學(xué)習(xí)、特征工程。

1001- 9081(2017)11- 3039- 09

10.11772/j.issn.1001- 9081.2017.11.3039

(*通信作者電子郵箱liyun@njupt.edu.cn)

TP311

A