機(jī)器學(xué)習(xí)-分布式機(jī)器學(xué)習(xí)

機(jī)器學(xué)習(xí)第10章分布式機(jī)器學(xué)習(xí)章節(jié)介紹機(jī)器學(xué)習(xí)方法是計算機(jī)利用已有的數(shù)據(jù)生成某種模型，并利用此模型預(yù)測的一種方法。在確定模型結(jié)構(gòu)之后，根據(jù)已知模型尋找模型參數(shù)的過程就是訓(xùn)練，訓(xùn)練過程中不斷依據(jù)訓(xùn)練數(shù)據(jù)來迭代調(diào)整模型的參數(shù)值，從而使模型的預(yù)測結(jié)果更為準(zhǔn)確。在現(xiàn)實應(yīng)用中，要達(dá)到好的效果，訓(xùn)練數(shù)據(jù)集可能很大，模型參數(shù)量劇增，會帶來很多性能和算法設(shè)計問題，單臺機(jī)器難以勝任，需要分布式的機(jī)器學(xué)習(xí)架構(gòu)。本章主要介紹分布式機(jī)器學(xué)習(xí)基礎(chǔ)知識，并介紹主流的分布式機(jī)器學(xué)習(xí)框架，結(jié)合實例介紹一些機(jī)器學(xué)習(xí)算法。章節(jié)結(jié)構(gòu)分布式機(jī)器學(xué)習(xí)基礎(chǔ)參數(shù)服務(wù)器分布式并行計算類型分布式機(jī)器學(xué)習(xí)框架MapReduce編程模型Hadoop

MapReduce框架SparkPMLSTensorFlow并行決策樹并行k-均值算法分布式機(jī)器學(xué)習(xí)基礎(chǔ)分布式機(jī)器學(xué)習(xí)中的一些核心問題：如何提高各分布式任務(wù)節(jié)點之間的網(wǎng)絡(luò)傳輸效率；如何解決參數(shù)同步問題，傳統(tǒng)訓(xùn)練模型是采用同步方法，如果機(jī)器性能不統(tǒng)一，必然會產(chǎn)生訓(xùn)練任務(wù)之間的協(xié)作；分布式環(huán)境下如何提高容錯能力，需要避免單點故障，并能合理處理異常，訓(xùn)練子節(jié)點出錯不影響全局任務(wù)。議程參數(shù)服務(wù)器應(yīng)用傳統(tǒng)的大數(shù)據(jù)處理框架訓(xùn)練大型的機(jī)器學(xué)習(xí)模型時，由于數(shù)據(jù)量比較大并且訓(xùn)練方法多樣，存在著一致性、擴(kuò)展性、穩(wěn)定性的問題。較大的模型也意味著參數(shù)較多，因而需要實現(xiàn)分布式并行訓(xùn)練，參數(shù)服務(wù)器是分布式并行訓(xùn)練框架之一，存放著模型的參數(shù)和狀態(tài)。參數(shù)服務(wù)器具有如下特點：高效通信寬松一致性靈活可擴(kuò)展容錯能力強(qiáng)易用議程高效通信參數(shù)服務(wù)器采用異步通信的方式，模型訓(xùn)練和參數(shù)存儲各自獨立，使各迭代之間并行訓(xùn)練，大大減少了延時。議程寬松一致性傳統(tǒng)的梯度下降由于梯度下降方向是在一次完整迭代（可能是mini-batch）之后才確定，而并行訓(xùn)練從多個子訓(xùn)練集中隨機(jī)選擇梯度方向，對一致性要求較寬松。議程靈活可擴(kuò)展訓(xùn)練過程中支持動態(tài)擴(kuò)展節(jié)點，不需要重啟訓(xùn)練任務(wù)就可以動態(tài)插入新節(jié)點到集合中，這一特性無疑有利于那些訓(xùn)練周期較長（長達(dá)數(shù)天或數(shù)周）的機(jī)器學(xué)習(xí)項目，可節(jié)省大量訓(xùn)練時間。議程容錯能力強(qiáng)在大型服務(wù)器集群中，由于節(jié)點較多，小概率故障往往常態(tài)化，所以需要節(jié)點的恢復(fù)（狀態(tài)清理、任務(wù)重啟）時間要短，而且不能中斷訓(xùn)練過程，這就要求并行化系統(tǒng)具有較強(qiáng)的容錯能力。議程易用目前機(jī)器學(xué)習(xí)項目開發(fā)者數(shù)量較少，為了減少學(xué)習(xí)難度，需要盡可能的使用常用語言或?qū)?shù)表示成通用的形式，如向量、矩陣等，并與現(xiàn)有機(jī)器學(xué)習(xí)框架無縫拼接。議程分布式并行計算框架分布式并行計算的類型一般分為三種：模型并行數(shù)據(jù)并行混合并行議程模型并行模型并行是指將模型按照其結(jié)構(gòu)放在不同的分布式機(jī)器上進(jìn)行訓(xùn)練，一般用在那些內(nèi)存要求較高的機(jī)器學(xué)習(xí)項目，例如，單機(jī)訓(xùn)練一個1000層的DNN網(wǎng)絡(luò)，內(nèi)存容易溢出，而使用模型并行，用不同的機(jī)器負(fù)責(zé)不同的層進(jìn)行訓(xùn)練，通過維護(hù)各層間參數(shù)同步實現(xiàn)整個DNN網(wǎng)絡(luò)的并行訓(xùn)練。議程數(shù)據(jù)并行數(shù)據(jù)并行是指各機(jī)器上的模型相同，對訓(xùn)練數(shù)據(jù)進(jìn)行分割，并分配到各機(jī)器上，最后將計算結(jié)果按照某種方式合并。該方法主要應(yīng)用在海量訓(xùn)練數(shù)據(jù)的情況，數(shù)據(jù)以并行化方式訓(xùn)練，訓(xùn)練過程中組合各工作節(jié)點的結(jié)果，實現(xiàn)模型參數(shù)的更新。參數(shù)并行常用的方法有參數(shù)平均和異步梯度下降的方法。議程參數(shù)平均參數(shù)平均是在每次訓(xùn)練迭代完成后計算各節(jié)點各模型參數(shù)平均值，這一方法操作簡單，主要依賴網(wǎng)絡(luò)同步更新，如果更新頻率較慢會導(dǎo)致參數(shù)差別較大，平均之后的模型參數(shù)的局部差異化被抵消，效果較差，影響模型的精確性，反之，如果更新較快，對網(wǎng)絡(luò)壓力較大，通信和同步的成本較高，所以在應(yīng)用中需要結(jié)合模型復(fù)雜度和優(yōu)化方法進(jìn)行平衡。議程異步梯度下降異步梯度下降是一種基于更新的數(shù)據(jù)并行化，它傳遞的是模型訓(xùn)練過程中的梯度、動量等信息，而沒有直接傳遞參數(shù)值，這樣一方面可以減少傳輸數(shù)據(jù)量，提高網(wǎng)絡(luò)傳輸效率，另一方面不同計算節(jié)點通過共享梯度，可以提高模型收斂速度。該方法的不足之處在于會隨著引入?yún)?shù)數(shù)量的增多出現(xiàn)梯度值過時的問題。議程混合并行混合并行的方式是指綜合應(yīng)用模型并行和數(shù)據(jù)并行，在訓(xùn)練集群的設(shè)計中，將上述兩種方式進(jìn)行合并，各取所長，形成互補(bǔ)。例如，可以在同一臺機(jī)器上采用模型并行化，在GPU和CPU之間使用模型并行，然后在機(jī)器之間采用數(shù)據(jù)并行化，將數(shù)據(jù)分配在不同的機(jī)器上，既實現(xiàn)了計算資源利用的最大化，也減少了數(shù)據(jù)分發(fā)的壓力。分布式機(jī)器學(xué)習(xí)框架分布式機(jī)器學(xué)習(xí)是機(jī)器學(xué)習(xí)領(lǐng)域的一大主要研究方向，其中MapReduce適合做離線計算，Storm適合做流式計算，Spark是內(nèi)存計算框架，能快速得到計算結(jié)果。分布式機(jī)器學(xué)習(xí)平臺歸類為三種基本設(shè)計方法：基本數(shù)據(jù)流、參數(shù)服務(wù)器模型以及高級數(shù)據(jù)流?；谶@三種方法來介紹分布式機(jī)器學(xué)習(xí)框架。議程MapReduce編程模型MapReduce是一個能處理和生成超大數(shù)據(jù)集的算法模型，該架構(gòu)能夠在大量硬件配置不高的計算機(jī)上實現(xiàn)并行化處理，這一編程模型結(jié)合用戶自定義的Map和Reduce函數(shù)。Map函數(shù)處理一個輸入的基于<Key,value>對的集合，輸出中間基于<Key,value>對的集合，Reduce函數(shù)是將所有具有相同key值的value值進(jìn)行合并，將數(shù)據(jù)集合進(jìn)行壓縮。議程MapReduce編程模型一個典型的MapReduce程序的執(zhí)行流程如下圖所示。議程Hadoop

MapReduce框架Hadoop

MapReduce是Hadoop三大組件之一，包括JobTracker和一定數(shù)量的TaskTracker。JobTracker負(fù)責(zé)任務(wù)分配和調(diào)度，一個MapReduce作業(yè)通常會把輸入的數(shù)據(jù)集切分為若干獨立的數(shù)據(jù)塊，由Map任務(wù)以并行方式處理它們，框架會對Map的輸出先進(jìn)行排序，然后把結(jié)果輸入到Reduce任務(wù)中。通常作業(yè)的輸入和輸出都會被存儲在文件系統(tǒng)HDFS中，由JobTracker負(fù)責(zé)任務(wù)的調(diào)度和監(jiān)控，以及重新執(zhí)行已經(jīng)失敗的任務(wù)。議程Hadoop

MapReduce框架Hadoop

MapReduce框架由一個單獨的主JobTracker和每個集群節(jié)點對應(yīng)一個備TaskTracker組成。JobTracker負(fù)責(zé)調(diào)度作業(yè)的所有任務(wù)，并監(jiān)控它們的執(zhí)行，這些任務(wù)分布在不同的備TaskTracker上。如果TaskTracker上的任務(wù)執(zhí)行失敗，還會調(diào)度其重新執(zhí)行。而TaskTracker僅負(fù)責(zé)執(zhí)行指派的任務(wù)。議程Hadoop

MapReduce框架作業(yè)的提交和執(zhí)行的過程如右圖所示。議程Hadoop

MapReduce框架Hadoop

MapReduce的作業(yè)提交執(zhí)行過程如下：MapReduce程序通過runJob()方法新建一個JobClient實例;通過JobTracker的getNewJobId()獲取新jobID；檢查作業(yè)輸入輸出的合法性，如果驗證失敗，作業(yè)將不會被提交，錯誤返回給MapReduce。通過調(diào)用JobTracker的submitJob()方法提交作業(yè)；將提交的作業(yè)放到隊列中，交由作業(yè)調(diào)度器進(jìn)行調(diào)度，并對其進(jìn)行初始化。查詢數(shù)據(jù)分片，并創(chuàng)建Map、Reduce任務(wù)：數(shù)據(jù)分片個數(shù)Map個數(shù)，Reduce任務(wù)的數(shù)量由JobConf的mapred.reduce.tasks屬性決定；TaskTracker定期發(fā)送心跳（heartbeat）給JobTracker報告狀態(tài)；TaskTracker從文件系統(tǒng)提取任務(wù)需要的資源文件；開始執(zhí)行TaskTracker相關(guān)任務(wù)運行TaskTracker中的Map、Reduce方法并輸出結(jié)果。議程Spark與Hadoop

MapReduce相比，Spark的優(yōu)勢在于處理迭代計算的機(jī)器學(xué)習(xí)任務(wù)，尤其是內(nèi)存要求小的應(yīng)用，性能提升很大，Spark還可以進(jìn)行批處理、實時數(shù)據(jù)處理、機(jī)器學(xué)習(xí)以及圖算法等計算模塊。使用Spark平臺無需關(guān)心分布式并行計算的細(xì)節(jié)，可以智能地進(jìn)行數(shù)據(jù)切分、算法復(fù)制、分布執(zhí)行、結(jié)果合并，以支持?jǐn)?shù)據(jù)分析人員快速開發(fā)分布式應(yīng)用。議程SparkSpark的基本框架如下圖所示。議程SparkSpark應(yīng)用核心由啟動環(huán)境和執(zhí)行程序兩部分組成，其中執(zhí)行程序負(fù)責(zé)執(zhí)行任務(wù)，運行執(zhí)行程序的機(jī)器是工作節(jié)點，而啟動環(huán)境由用戶程序啟動，通過集群管理器與各個執(zhí)行程序進(jìn)行通信。集群管理器主要負(fù)責(zé)集群的資源管理和調(diào)度，目前支持Standalone、Apache

Mesos和YARN三種類型的管理器。議程SparkSpark使用彈性分布式數(shù)據(jù)集（RDD）抽象分布式計算，RDD是Spark并行數(shù)據(jù)處理的基礎(chǔ)，它是一種只讀的分區(qū)記錄的集合，用戶可以通過RDD對數(shù)據(jù)顯示地控制存儲位置和選擇數(shù)據(jù)的分區(qū)。RDD主要通過轉(zhuǎn)換和動作操作來進(jìn)行分布式計算，轉(zhuǎn)換是根據(jù)現(xiàn)有數(shù)據(jù)集創(chuàng)建新數(shù)據(jù)集，動作是在數(shù)據(jù)集上進(jìn)行計算后返回值給Driver程序。使用RDD可以用基本一致的方式應(yīng)對不同的大數(shù)據(jù)處理場景，還能夠提高分布式計算的容錯性。議程SparkSpark是一種粗粒度、基于數(shù)據(jù)集的并行計算框架。其計算范式是數(shù)據(jù)集上的計算，在使用Spark的時候，要按照這一范式編寫算法。所謂的數(shù)據(jù)集操作，就是成堆的數(shù)據(jù)，如果源數(shù)據(jù)集是按行存儲的話，就需要對其進(jìn)行適配，將若干記錄組成一個集合。因此在提交給Spark任務(wù)時，需要先構(gòu)建數(shù)據(jù)集，然后通過數(shù)據(jù)集的操作，實現(xiàn)目標(biāo)任務(wù)。議程PMLSPMLS是面向機(jī)器學(xué)習(xí)任務(wù)設(shè)計的，核心解決非均勻收斂、并行訓(xùn)練中容錯能力和動態(tài)結(jié)構(gòu)依賴等問題。非均勻收斂采用模型并行的方式減少各工作器對模型參數(shù)的依賴。PMLS的架構(gòu)中主要包括參數(shù)服務(wù)器、調(diào)度器和工作節(jié)點組成，通過引入?yún)?shù)服務(wù)器實現(xiàn)結(jié)構(gòu)的動態(tài)擴(kuò)展和快速迭代訓(xùn)練，參數(shù)服務(wù)器用于分布式內(nèi)存鍵值參數(shù)的存儲和更新。調(diào)度器通過向參數(shù)交換通道發(fā)送參數(shù)子集實現(xiàn)模型的并行化調(diào)度。工作節(jié)點從參數(shù)服務(wù)器上獲取的參數(shù)子集對分區(qū)數(shù)據(jù)集進(jìn)行處理，每個工作節(jié)點上都有參數(shù)更新客戶端和調(diào)度客戶端，前者通過參數(shù)交換通道收發(fā)參數(shù)值，后者通過調(diào)度控制通道收發(fā)調(diào)度命令。議程PMLSPMLS為了提高參數(shù)傳輸效率，采用過時同步并行策略提高容錯能力。在動態(tài)結(jié)構(gòu)依賴方面，PMLS在運行時分析參數(shù)間的依賴關(guān)系，使用調(diào)度器實現(xiàn)參數(shù)子集的并行獨立更新。在非均勻收斂方面，PMLS對不同參數(shù)的更新優(yōu)先級進(jìn)行量化，減少優(yōu)先級較低的參數(shù)的更新頻率，避免資源浪費，從而提高了每次迭代的收斂性能。議程TensorFlowTensorFlow為用戶封裝了底層的分布式操作，使其可以專注于編寫機(jī)器學(xué)習(xí)代碼。使用數(shù)據(jù)流圖進(jìn)行數(shù)值計算，用有向圖中的節(jié)點表示，節(jié)點的狀態(tài)是可變的，邊是張量，對應(yīng)為多維數(shù)組。TensorFlow中數(shù)據(jù)并行化的方式由In-graph、Between-graph、異步訓(xùn)練、同步訓(xùn)練幾種方式，通過將模型訓(xùn)練分配給不同的工作節(jié)點，并使用參數(shù)服務(wù)器共享參數(shù)。議程In-graph模式這一模式與單機(jī)多GPU模式相比，是由一個數(shù)據(jù)節(jié)點和多機(jī)多計算節(jié)點組成，通過數(shù)據(jù)節(jié)點實現(xiàn)訓(xùn)練數(shù)據(jù)分發(fā)，一般采用gRPC協(xié)議，即Google通過對RPC協(xié)議進(jìn)行封裝，簡化了網(wǎng)絡(luò)調(diào)用方式。計算節(jié)點通過使用join操作公開一個網(wǎng)絡(luò)接口，等待接收計算任務(wù)，客戶端在使用時將任務(wù)指定到某一個計算節(jié)點上進(jìn)行計算，調(diào)用方法與單機(jī)模式下指定GPU是一樣的。議程Between-graph模式這一模式的訓(xùn)練參數(shù)保存在參數(shù)服務(wù)器，數(shù)據(jù)分片包存在各個計算節(jié)點上，各計算節(jié)點算完之后將最新的參數(shù)提交給參數(shù)服務(wù)器，由其進(jìn)行更新保存。這一模式的優(yōu)點在于無需訓(xùn)練數(shù)據(jù)的分發(fā)，特別是處理TB級數(shù)據(jù)量時，節(jié)省大量數(shù)據(jù)傳輸時間，所以在大數(shù)據(jù)深度學(xué)習(xí)應(yīng)用中推薦使用此模式。議程異步和同步訓(xùn)練在In-graph以及Between-graph模式下，參數(shù)更新都支持同步和異步兩種方式。其中，同步更新是指每次梯度更新都要等所有節(jié)點計算完成后返回結(jié)果，結(jié)果處理完成后統(tǒng)一更新參數(shù)。這種方式訓(xùn)練過程穩(wěn)定，不會抖動，但模型處理速度存在木桶效應(yīng)，計算較慢的節(jié)點會對整體訓(xùn)練過程有拖累。異步更新的方式不存在這種問題，計算性能強(qiáng)，所以模型訓(xùn)練速度快，但是各計算節(jié)點的更新不同步導(dǎo)致梯度下降不穩(wěn)定，抖動較大。并行決策樹隨著大數(shù)據(jù)時代的到來，算法需要處理的數(shù)據(jù)量急劇增加，僅依靠原始的決策樹算法進(jìn)行分類無論在效率上還是準(zhǔn)確性上都不足以滿足需求。高效出色的在大數(shù)據(jù)量下使用決策樹算法，需要將決策樹算法并行化。并行決策樹并行決策樹算法基于MapReduce框架，核心思想是分而治之的策略。MapReduce通過將海量數(shù)據(jù)集分割成多個小數(shù)據(jù)集交給多臺不同計算機(jī)進(jìn)行處理，實現(xiàn)并行化數(shù)據(jù)處理。應(yīng)用到?jīng)Q策樹算法上，通過MapReduce將決策樹算法并行處理，將耗時的屬性相似度計算的步驟并行執(zhí)行。Map階段，以單元組形式分解數(shù)據(jù)，計算屬性相似度，以<屬性名，相似度>形式輸出。Reduce階段，匯