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

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

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

MapReduce框架Hadoop

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

MapReduce框架Hadoop

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

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

MapReduce框架Hadoop

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

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

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