香港赛马会体育在线博彩网:分布式機器學習的故事(轉 )

jopen 6年前發布 | 21K 次閱讀 sequelize

赛马会一码三中三资料 www.iclqr.icu

從畢業加入Google開始做分布式機器學習,到后來轉戰騰訊廣告業務,至今已經七年了。我想說說我見到的故事和我自己的實踐經歷。這段經歷給我的感覺是:雖然在驗證一個新的并行算法的正確性的時候,我們可以利用現有框架,盡量快速實現,但是任何一個有價值的機器學習思路,都值得擁有自己獨特的架構。所以重點在有一個分布式操作系統,方便大家開發自己需要的架構(框架),來支持相應的算法。如果你關注大數據,聽完我說的故事,應該會有感觸。

大數據和分布式機器學習

特點

說故事之前,先提綱挈領的描述一下我們要解決的問題的特點。我見過的有價值的大規?;餮跋低?,基本都有三個特點:

  1. 可擴展??衫┱溝囊饉際恰巴度敫嗟幕?,能處理更大的數據”。而傳統的并行計算要的是:“投入更多機器,數據 大小不變,計算速度更快”。這是我認識中“大數據”和傳統并行計算研究目標不同的地方。如果只是求速度快,那么multicore和GPU會比分布式機器 學習的ROI更高。

    • 有一個框架(比如MPI或者MapReduce或者自己設計的),支持fault recovery。Fault recovery是可擴展的基礎。現代機群系統都是很多用戶公用的,其中任何一個進程都有可能被更高優先級的進程preempted。一個job涉及數千 個進程(task processes),十分鐘里一個進程都不掛的概率很小。而如果一個進程掛了,其他進程都得重啟,那么整個計算任務可能永遠都不能完成。
    </li>

  2. 數學模型要根據架構和數據做修改。這里有兩個原因:

    • 因為大數據基本都是長尾分布的,而papers里的模型基本都假設數據是指數分布的(想想用SVD做component analysis其實假設了Gaussian distributed,latent Dirichlet allocation假設了multimonial distribution。)。真正能處理大數據的數學模型,都需要能更好的描述長尾數據。否則,模型訓練就是忽視長尾,而只關注從“大頭”數據部分挖掘 “主流”patterns了。

      </li>

    • 很多機器學習算法(比如MCMC)都不適合并行化。所以往往需要根據模型的特點做一些算法的調整。有時候會是approximation。比如 AD-LDA算法是一種并行Gibbs sampling算法,但是只針對LDA模型有效,對其他大部分模型都不收斂,甚至對LDA的很多改進模型也不收斂。

      </li> </ul> </li>

    • 引入更多機器的首要目的不是提升性能,而是能處理更大的數據。用更多的機器,處理同樣大小的數據,期待 speedup提高——這是傳統并行計算要解決的問題——是multicore、SMP、MPP、GPU還是Beowolf cluster上得分布式計算不重要。在大數據情況下,困難點在問題規模大,數據量大。此時,引入更多機器,是期待能處理更大數據,總時間消耗可以不變甚 至慢一點。分布式計算把數據和計算都分不到多臺機器上,在存儲、I/O、通信和計算上都要消除瓶頸。

      </li> </ol>

      上述三個特點,會在實踐中要求“一個有價值的算法值得也應該有自己獨特的框架”。

      概念

      在開始說故事之前,先正名幾個概念:Message Passing和MapReduce是兩個有名的并行程序編程范式(paradigm),也就是說,并行程序應該怎么寫都有規范了——只需要在預先提供的框架(framework)程序里插入一些代碼,就能得到自己的并行程序。Message Passing范式的一個框架叫做MPI。MapReduce范式的框架也叫MapReduce。而MPICH2和Apache Hadoop分別是這MPI和MapReduce兩個框架的實現(implementations)。另一個本文會涉及的MapReduce實現是我用C++寫的MapReduce Lite。后面還會提到BSP范式,它的一個著名的實現是Google Pregel。

      MPI這個框架很靈活,對程序結構幾乎沒有太多約束,以至于大家有時把MPI稱為一組接口(interface)——MPI的I就是interface的意思。

      這里,MPICH2和Hadoop都是很大的系統——除了實現框架(允許程序員方便的編程),還實現了資源管理和分配,以及資源調度的功能。這些功 能在Google的系統里是分布式操作系統負責的,而Google MapReduce和Pregel都是在分布式操作系統基礎上開發的,框架本身的代碼量少很多,并且邏輯清晰易于維護。當然Hadoop已經意識到這個問 題,現在有了YARN操作系統。(YARN是一個仿照UC Berkeley AMPLab的Mesos做的系統。關于這個“模仿”,又有另一個故事。)

      分布式機器學習的故事

      pLSA和MPI:大數據的首要目標是“大”而不是“快”

      我2007年畢業后加入Google做研究。我們有一個同事叫張棟,他的工作涉及pLSA模型的并行化。這個課題很有價值,因為 generalized matrix decomposition實際上是collaborative filtering的generalization,是用戶行為分析和文本語義理解的共同基礎。幾年后的今天,我們都知道這是搜索、推薦和廣告這三大互聯 網平臺產品的基礎。

      當時的思路是用MPI來做并行化。張棟和宿華合作,開發一套基于MPI的并行pLSA系統。MPI是1980年代流行的并行框架,進入到很多大學的 課程里,熟悉它的人很多。MPI這個框架提供了很多基本操作:除了點對點的Send, Recv,還有廣播Bdcast,甚至還有計算加通信操作,比如AllReduce。

      MPI很靈活,描述能力很強。因為MPI對代碼結構幾乎沒有什么限制——任何進程之間可以在任何時候通信——所以很多人不稱之為框架,而是稱之為“接口”。

      但是Google的并行計算環境上沒有MPI。當時一位叫白宏杰的工程師將MPICH2移植到了Google的分布式操作系統上。具體的說,是重新實現MPI里的Send, Recv等函數,調用分布式操作系統里基于HTTP RPC的通信API。

      MPI的AllReduce操作在很多機器學習系統的開發里都很有用。因為很多并行機器學習系統都是各個進程分別訓練模型,然后再合適的時候(比如 一個迭代結束的時候)大家對一下各自的結論,達成共識,然后繼續迭代。這個“對一下結論,達成共識”的過程,往往可以通過AllReduce來完成。

      如果我們關注一下MPI的研究,可以發現曾經有很多論文都在討論如何高效實現AllReduce操作。比如我2008年的博文里提到一種當時讓我們都覺得很聰明的一種算法。這些長年累月的優化,讓MPICH2這樣的系統的執行效率(runtime efficiency)非常出色。

      基于MPI框架開發的pLSA模型雖然效率高,并且可以處理相當大的數據,但是還是不能處理Google當年級別的數據。原因如上節『概念』中所述 ——MPICH2沒有自動錯誤恢復功能,而且MPI這個框架定義中提供的編程靈活性,讓我們很難改進框架,使其具備錯誤恢復的能力。

      具體的說,MPI允許進程之間在任何時刻互相通信。如果一個進程掛了,我們確實可以請分布式操作系統重啟之。但是如果要讓這個“新生”獲取它“前 世”的狀態,我們就需要讓它從初始狀態開始執行,接收到其前世曾經收到的所有消息。這就要求所有給“前世”發過消息的進程都被重啟。而這些進程都需要接收 到他們的“前世”接收到過的所有消息。這種數據依賴的結果就是:所有進程都得重啟,那么這個job就得重頭做。

      一個job哪怕只需要10分鐘時間,但是這期間一個進程都不掛的概率很小。只要一個進程掛了,就得重啟所有進程,那么這個job就永遠也結束不了了。

      雖然我們很難讓MPI框架做到fault recovery,我們可否讓基于MPI的pLSA系統支持fault recovery呢?原則上是可以的——最簡易的做法是checkpointing——時不常的把有所進程接收到過的所有消息寫入一個分布式文件系統(比 如GFS)?;蛘吒苯右壞悖航套刺蚸ob狀態寫入GFS。Checkpointing是下文要說到的Pregel框架實現fault recovery的基礎。

      但是如果一個系統自己實現fault recovery,那還需要MPI做什么呢?做通信?——現代后臺系統都用基于HTTP的RPC機制通信了,比如和Google的Stubby、 非死book的Thrift、騰訊的Poppy還有Go語言自帶的rpc package。做進程管理?——在開源界沒有分布式操作系統的那些年里有價值;可是今天(2013年),Google的Borg、AMPLab的 Mesos和Yahoo!的YARN都比MPICH2做得更好,考慮更全面,效能更高。

      LDA和MapReduce:“可擴展”的基礎——數據并行。

      因為MPI在可擴展性上的限制, 我們可以大致理解為什么Google的并行計算架構上沒有實現經典的MPI。同時,我們自然的考慮Google里當時最有名的并行計算框架MapReduce。

      MapReduce的風格和MPI截然相反。MapReduce對程序的結構有嚴格的約束——計算過程必須能在兩個函數中描述:map和 reduce;輸入和輸出數據都必須是一個一個的records;任務之間不能通信,整個計算過程中唯一的通信機會是map phase和reduce phase之間的shuffuling phase,這是在框架控制下的,而不是應用代碼控制的。

      pLSA模型的作者Thomas Hoffmann提出的機器學習算法是EM。EM是各種機器學習inference算法中少數適合用MapReduce框架描述的——map phase用來推測(inference)隱含變量的分布(distributions of hidden variables),也就是實現E-step;reduce phase利用上述結果來更新模型,也即是M-step。

      但是2008年的時候,pLSA已經被新興的LDA掩蓋了。LDA是pLSA的generalization:一方面LDA的 hyperparameter設為特定值的時候,就specialize成pLSA了。從工程應用價值的角度看,這個數學方法的 generalization,允許我們用一個訓練好的模型解釋任何一段文本中的語義。而pLSA只能理解訓練文本中的語義。(雖然也有ad hoc的方法讓pLSA理解新文本的語義,但是大都效率低,并且并不符合pLSA的數學定義。)這就讓繼續研究pLSA價值不明顯了。

      另一方面,LDA不能用EM學習了,而需要用更generalized inference算法。學界驗證效果最佳的是Gibbs sampling。作為一種Markov Chain Monte Carlo(MCMC)算法,顧名思義,Gibbs sampling是一個順序過程,按照定義不能被并行化。

      但是2007年的時候,UC Irvine的David Newman團隊發現,對于LDA這個特定的模型,Gibbs sampling可以被并行化。具體的說,把訓練數據拆分成多份,用每一份獨立的訓練模型。每隔幾個Gibbs sampling迭代,這幾個局部模型之間做一次同步,得到一個全局模型,并且用這個全局模型替換各個局部模型。這個研究發表在NIPS上,題目 是:Distributed Inference for Latent Dirichlet Allocation。

      上述做法,在2012年Jeff Dean關于distributed deep leearning的論文中,被稱為data parallelism(數據并行)。如果一個算法可以做數據并行,很可能就是可擴展(scalable)的了。

      David Newman團隊的發現允許我們用多個map tasks并行的做Gibbs sampling,然后在reduce phase中作模型的同步。這樣,一個訓練過程可以表述成一串MapReduce jobs。我用了一周時間在Google MapReduce框架上實現實現和驗證了這個方法。后來在同事Matthew Stanton的幫助下,優化代碼,提升效率。但是,因為每次啟動一個MapReduce job,系統都需要重新安排進程(re-schedule);并且每個job都需要訪問GFS,效率不高。在當年的Google MapReduce系統中,1/3的時間花在這些雜碎問題上了。后來實習生司憲策在Hadoop上也實現了這個方法。我印象里Hadoop環境下,雜碎事 務消耗的時間比例更大。

      隨后白紅杰在我們的代碼基礎上修改了數據結構,使其更適合MPI的AllReduce操作。這樣就得到了一個高效率的LDA實現。我們把用MapReduce和MPI實現的LDA的Gibbs sampling算法發表在這篇論文里了。

      當我們躊躇于MPI的擴展性不理想而MapReduce的效率不理想時,Google MapReduce團隊的幾個人分出去,開發了一個新的并行框架Pregel。當時Pregel項目的tech lead訪問中國。這個叫Grzegorz Malewicz的波蘭人說服了我嘗試在Pregel框架下驗證LDA。但是在說這個故事之前,我們先看看Google Rephil——另一個基于MapReduce實現的并行隱含語義分析系統。

      Rephil和MapReduce:描述長尾數據的數學模型

      Google Rephil是Google AdSense背后廣告相關性計算的頭號秘密武器。但是這個系統沒有發表過論文。只是其作者(博士Uri Lerner和工程師Mike Yar)在2002年在灣區舉辦的幾次小規模交流中簡要介紹過。所以Kevin Murphy把這些內容寫進了他的書《Machine Learning: a Probabilitic Perspecitve》里。在吳軍博士的《數學之美》里也提到了Rephil。

      Rephil的模型是一個全新的模型,更像一個神經元網絡。這個網絡的學習過程從Web scale的文本數據中歸納海量的語義——比如“apple”這個詞有多個意思:一個公司的名字、一種水果、以及其他。當一個網頁里包含”apple”, “stock”, “ipad”等詞匯的時候,Rephil可以告訴我們這個網頁是關于apple這個公司的,而不是水果。

      這個功能按說pLSA和LDA也都能實現。為什么需要一個全新的模型呢?

      從2007年至今,國內外很多團隊都嘗試過并行化pLSA和LDA。心靈手巧的工程師們,成功的開發出能學習數萬甚至上十萬語義(latent topics)的訓練系統。但是不管大家用什么訓練數據,都會發現,得到的大部分語義(相關的詞的聚類)都是非常類似,或者說“重復”的。如果做一個“去 重”處理,幾萬甚至十萬的語義,就只剩下幾百幾千了。

      這是怎么回事?

      如果大家嘗試著把訓練語料中的低頻詞去掉,會發現訓練得到的語義和用全量數據訓練得到的差不多?;瘓浠八?,pLSA和LDA模型的訓練算法沒有在意低頻數據。

      為什么會這樣呢?因為pLSA和LDA這類概率模型的主要構造單元都是指數分布(exponential distributions)。比如pLSA假設一個文檔中的語義的分布是multinomial的,每個語義中的詞的分布也是multinomial 的。因為multinomial是一種典型的指數分布,這樣整個模型描述的海量數據的分布,不管哪個維度上的marginalization,都是指數分 布。在LDA中也類似——因為LDA假設各個文檔中的語義分布的multinomial distributions的參數是符合Dirichlet分布的,并且各個語義中的詞的分布的multinomial distributions的參數也是符合Dirichlet分布的,這樣整個模型是假設數據是指數分布的。

      可是Internet上的實際數據基本都不是指數分布的——而是長尾分布的。至于為什么是這樣?可以參見2006年紐約時報排名暢銷書The Long Tail: Why the Future of Business is Selling Less of More?;蛘嚦純雌渥髡逤hris Anderson的博客The Long Tail。

      長尾分布的形狀大致如下圖所示:

      其中x軸表示數據的類型,y軸是各種類型的頻率,少數類型的頻率很高(稱為大頭,圖中紅色部分),大部分很低,但是大于0(稱為長尾,圖中黃色部分)。一個典型的例子是文章中詞的分布,有個具體的名字Zipf’s law,就是典型的長尾分布。而指數分布基本就只有大頭部分——換句話說,如果我們假設長尾數據是指數分布的,我們實際上就把尾巴給割掉了。

      割掉數據的尾巴——這就是pLSA和LDA這樣的模型做的——那條長尾巴覆蓋的多種多樣的數據類型,就是Internet上的人生百態。理解這樣的 百態是很重要的。比如百度和Google為什么能如此賺錢?因為互聯網廣告收益。傳統廣告行業,只有有錢的大企業才有財力聯系廣告代理公司,一幫西裝革履 的高富帥聚在一起討論,競爭電視或者紙媒體上的廣告機會?;チ愀胬?,任何人都可以登錄到一個網站上去投放廣告,即使每日廣告預算只有幾十塊人民幣。這 樣一來,劉備這樣織席販屢的小業主,也能推銷自己做的席子和鞋子。而搜索引擎用戶的興趣也是百花齊放的——從人人愛戴的陳老師蒼老師到各種小眾需求包括 “紅酒木瓜湯”(一種豐胸秘方,應該出豐胸廣告)或者“蘋果大尺度”(在搜索范冰冰主演的《蘋果》電影呢)。把各種需求和各種廣告通過智能技術匹配起來, 就醞釀了互聯網廣告的革命性力量。這其中,理解各種小眾需求、長尾意圖就非常重要了。

      實際上,Rephil就是這樣一個能理解百態的模型。因為它把Google AdSense的盈利能力大幅提升,最終達到Google收入的一半。兩位作者榮獲Google的多次大獎,包括Founders’ Award。

      而切掉長尾是一個很糟糕的做法。大家還記得小說《1984》里有這樣一個情節嗎?老大哥要求發布“新話”——一種新的語言,刪掉自然英語中大部分詞 匯,只留下那些主流的詞匯??純蔥∷道锏娜嗣巧畹氖瀾?,讓人渾身發毛,咱們就能體會“割尾巴”的惡果了。沒有看過《1984》的朋友可以想象一下水木首頁上只有“全站十大”,連“分類十大”都刪掉之后的樣子。

      既然如此,為什么這類模型還要假設數據是指數分布的呢?——實在是不得已。指數分布是一種數值計算上非常方便的數學元素。拿LDA來說,它利用了 Dirichlet和multinomial兩種分布的共軛性,使得其計算過程中,模型的參數都被積分給積掉了(integrated out)。這是AD-LDA這樣的ad hoc并行算法——在其他模型上都不好使的做法——在LDA上好用的原因之一?;瘓浠八?,這是為了計算方便,掩耳盜鈴地假設數據是指數分布的。

      實際上,這種掩耳盜鈴在機器學習領域很普遍。比如有個兄弟聽了上面的故事后說:“那我們就別用概率模型做語義分析了,咱們還用矩陣分解吧?SVD分 解怎么樣?” 很不好意思的,當我們把SVD分解用在語義分析(稱為LSA,latent semantic analysis)上的時候,我們還是引入了指數分布假設——Gaussian assumption或者叫normality assumption。這怎么可能呢?SVD不就是個矩陣分解方法嗎?確實傳統SVD沒有對數據分布的假設,但是當我們用EM之類的算法解決存在missing data的 問題——比如LSA,還有推薦系統里的協同過濾(collaborative filtering)——這時不僅引入了Gaussian assumption,而且引入了linearity assumption。當我們用其他很多矩陣分解方法做,都存在同樣的 問題。

      掩耳盜鈴的做法怎么能存在得如此自然呢?這是因為指數分布假設(尤其是Gaussian assumption)有過很多成功的應用,包括通信、數據壓縮、制導系統等。這些應用里,我們關注的就是數據中的低頻部分;而高頻部分(或者說距離 mean比較遠的數據)即使丟掉了,電話里的聲音也能聽懂,壓縮還原的圖像也看得明白,導彈也還是能沿著“最可能”靠譜的路線飛行。我們當然會假設數據是 指數分布的,這樣不僅省計算開銷,而且自然的忽略高頻數據,我們還鄙夷地稱之為outlier或者noise。

      可是在互聯網的世界里,正是這些五花八門的outliers和noise,蘊含了世間百態,讓數據不可壓縮,從而產生了“大數據”這么個概念。處理好大數據的公司,賺得盆滿缽滿,塑造了一個個傳奇。這里有一個聽起來比較極端的說法大數據里無噪聲——很多一開始頻率很低,相當長尾,會被詞過濾系統認為是拼寫錯誤的queries,都能后來居上成為主流。比如“神馬”,“醬紫”。

      Rephil系統實現的模型是一個神經元網絡模型(neural network)。它的設計的主要考慮,就是要能盡量好的描述長尾分布的文本數據和其中蘊含的語義。Rephil模型的具體技術細節因為沒有在論文中發表 過,所以不便在這里透露。但是Rephil模型描述長尾數據的能力,是下文將要介紹的Peacock系統的原動力,雖然兩者在模型上完全不同。

      Rephil系統是基于Google MapReduce構建的。如上節所述,MapReduce在用來實現迭代算法的時候,效率是比較低的。這也是Peacock要設計全新框架的原動力—— 使其比MapReduce高效,但同時像MapReduce一樣支持fault recovery。

      LDA和Pregel

      Clustering和Pregel

      分類器和GBR

      SETI:Online pCTR

      MapReduce Lite

      Deep Learning和DistBelief

      Peacock

      來自://cxwangyi.github.io/2014/01/20/distributed-machine-learning/

 本文由用戶 jopen 自行上傳分享,僅供網友學習交流。所有權歸原作者,若您的權利被侵害,請聯系管理員。
 轉載本站原創文章,請注明出處,并保留原始鏈接、圖片水印。
 本站是一個以用戶分享為主的開源技術平臺,歡迎各類分享!