一、前言

從畢業(yè)加入Google 開始做分布式機(jī)器學(xué)習(xí)，到后來轉(zhuǎn)戰(zhàn)騰訊廣告業(yè)務(wù)，至今已經(jīng)七年了。我想說說我見到的故事和我自己的實(shí)踐經(jīng)歷。這段經(jīng)歷給我的感覺是：雖然在驗(yàn)證一個(gè)新的并 行算法的正確性的時(shí)候，我們可以利用現(xiàn)有框架，盡量快速實(shí)現(xiàn)，但是任何一個(gè)有價(jià)值的機(jī)器學(xué)習(xí)思路，都值得擁有自己獨(dú)特的架構(gòu)。所以重點(diǎn)在有一個(gè)分布式操作 系統(tǒng)，方便大家開發(fā)自己需要的架構(gòu)(框架)，來支持相應(yīng)的算法。如果你關(guān)注大數(shù)據(jù)，聽完我說的故事，應(yīng)該會(huì)有感觸。

大數(shù)據(jù)帶來的新機(jī)遇

起源

分布式機(jī)器學(xué)習(xí)是隨著“大數(shù)據(jù)”概念興起的。在有大數(shù)據(jù)之前，有很多研究工作為了讓機(jī)器學(xué)習(xí)算法更快，而利多多個(gè)處理器。這類工作通常稱為“并行計(jì) 算”或者“并行機(jī)器學(xué)習(xí)”，其核心目標(biāo)是把計(jì)算任務(wù)拆解成多個(gè)小的任務(wù)，分配到多個(gè)處理器上做計(jì)算。分布式計(jì)算或者分布式機(jī)器學(xué)習(xí)除了要把計(jì)算任務(wù)分布到 多個(gè)處理器上，更重要的是把數(shù)據(jù)(包括訓(xùn)練數(shù)據(jù)以及中間結(jié)果)分布開來。因?yàn)樵诖髷?shù)據(jù)時(shí)代，一臺(tái)機(jī)器的硬盤往往裝不下全部數(shù)據(jù)，或者即使裝下了，也會(huì)受限 于機(jī)器的I/O通道的帶寬，以至于訪問速度很慢。為了更大的存儲(chǔ)容量、吞吐量以及容錯(cuò)能力，我們都希望把數(shù)據(jù)分布在多臺(tái)計(jì)算機(jī)上。

那么什么樣的數(shù)據(jù)大到一臺(tái)機(jī)器甚至幾百臺(tái)機(jī)器的硬盤都裝不下呢?要知道，現(xiàn)在很多服務(wù)器的硬盤空間都是數(shù)TB的了!其實(shí)這樣的大數(shù)據(jù)有很多。比如搜 索引擎要爬下很多很多的網(wǎng)頁，對(duì)其內(nèi)容做分析并建立索引。有多少網(wǎng)頁呢?這個(gè)數(shù)字很難估計(jì)，因?yàn)檫@是隨時(shí)間變化的。在Web 2.0出現(xiàn)之前，全球網(wǎng)頁數(shù)量的增長相對(duì)穩(wěn)定，因?yàn)榫W(wǎng)頁都是專業(yè)人員編輯的。而由于各種Web 2.0工具幫助用戶建立自己的網(wǎng)頁，比如博客、甚至微博，所以網(wǎng)頁數(shù)量呈指數(shù)速度遞增。

另一種典型的大數(shù)據(jù)是電商網(wǎng)站上的用戶行為數(shù)據(jù)。比如在亞馬遜或者淘寶上，每天都很多用戶看到了很多推薦的商品，并且點(diǎn)擊了其中一些。這些用戶點(diǎn)擊 推薦商品的行為會(huì)被亞馬遜和淘寶的服務(wù)器記錄下來，作為分布式機(jī)器學(xué)習(xí)系統(tǒng)的輸入。輸出是一個(gè)數(shù)學(xué)模型，可以預(yù)測一個(gè)用戶喜歡看到哪些商品，從而在下一次 展示推薦商品的時(shí)候，多展示那些用戶喜歡的。

類似的，在互聯(lián)網(wǎng)廣告系統(tǒng)中，展示給用戶的廣告、以及用戶點(diǎn)擊的廣告也都會(huì)被記錄下來，作為機(jī)器學(xué)習(xí)系統(tǒng)的數(shù)據(jù)，訓(xùn)練點(diǎn)擊率預(yù)估模型。在下一次展示 推薦商品時(shí)，這些模型會(huì)被用來預(yù)估每個(gè)商品如果被展示之后，有多大的概率被用戶點(diǎn)擊。其中預(yù)估點(diǎn)擊率高的商品，往往展示在預(yù)估點(diǎn)擊率低的商品之前，從而贏 得實(shí)際上比較高的點(diǎn)擊率。

從上面的例子我們可以看出來，這些大數(shù)據(jù)之所以大，是因?yàn)樗鼈冇涗浀氖菙?shù)十億互聯(lián)網(wǎng)用戶的行為。而人們每天都會(huì)產(chǎn)生行為，以至于百度、阿里、騰訊、 奇虎、搜狗這樣的公司的互聯(lián)網(wǎng)服務(wù)每天收集到很多很多塊硬盤才能裝下的數(shù)據(jù)。而且這些數(shù)據(jù)隨時(shí)間增加，永無止境。雖然對(duì)“大數(shù)據(jù)”的具體定義見人見智，但 是互聯(lián)網(wǎng)用戶的行為數(shù)據(jù)，毫無疑問地被公認(rèn)為大數(shù)據(jù)了。

價(jià)值

機(jī)器學(xué)習(xí)的應(yīng)用由來已久。大家可能還記得十幾年前IBM推出的語音識(shí)別和輸入系統(tǒng)ViaVoice。這個(gè)系統(tǒng)使用的聲學(xué)模型和語言模型是用人工收集 整理和標(biāo)注的數(shù)據(jù)訓(xùn)練的。當(dāng)年因?yàn)镮BM財(cái)大氣粗，收集和整理了很多數(shù)據(jù)，所以ViaVoice的識(shí)別準(zhǔn)確率在同類產(chǎn)品中遙遙領(lǐng)先。但 是，ViaVoice很難保證能識(shí)別各種口音的人。所以IBM的工程師們?cè)O(shè)計(jì)了一個(gè)自動(dòng)適應(yīng)的功能——通過讓用戶標(biāo)注沒能正確識(shí)別的語音對(duì)應(yīng)的文 本，ViaVoice可以針對(duì)主任的口音做特別的優(yōu)化。

今天，大家可以通過互聯(lián)網(wǎng)使用Google的語音識(shí)別系統(tǒng)。我們會(huì)發(fā)現(xiàn)，不管使用者口音如何，Google的語音識(shí)別系統(tǒng)幾乎都能準(zhǔn)確識(shí)別，以至于幾乎不再需要“適應(yīng)主人的口音”。而且Google的系統(tǒng)支持的語言種類也更多。這其中的奧妙就在于“大數(shù)據(jù)”。

在Google發(fā)布語音識(shí)別引擎之前，先有語音搜索服務(wù)。在語音搜索服務(wù)之前，有一個(gè)打電話查詢的服務(wù)。實(shí)際上，正式這個(gè)電話服務(wù)收集了很多用戶的 語音輸入。這部分?jǐn)?shù)據(jù)經(jīng)過人工標(biāo)注，稱為了訓(xùn)練語言模型和聲學(xué)模型的第一批數(shù)據(jù)。隨后發(fā)布的語音搜索收集了世界各地更多互聯(lián)網(wǎng)用戶的聲音，加上半自動(dòng)標(biāo)注 系統(tǒng)的引入，訓(xùn)練數(shù)據(jù)大大豐富了。訓(xùn)練數(shù)據(jù)越多，能覆蓋的口音和語種越多，機(jī)器學(xué)習(xí)得到的模型的識(shí)別準(zhǔn)確率也就越高。以至于當(dāng)Google發(fā)布語音識(shí)別引 擎之初，識(shí)別率就遠(yuǎn)高于依賴人工標(biāo)注訓(xùn)練數(shù)據(jù)的IBM ViaVoice。隨著語音識(shí)別服務(wù)被很多手機(jī)應(yīng)用和桌面應(yīng)用使用，它能采集更多用戶的語音輸入，模型的準(zhǔn)確性會(huì)不斷得到提高。

從上面例子我們可以看出，因?yàn)榛ヂ?lián)網(wǎng)服務(wù)收集的數(shù)據(jù)是萬萬千千用戶的行為的體現(xiàn)，而人類行為是人類智能的結(jié)果。所以如果我們能設(shè)計(jì)分布式機(jī)器學(xué)習(xí)系 統(tǒng)，能從大數(shù)據(jù)中歸納規(guī)律，我們實(shí)際上就在歸納整個(gè)人類的知識(shí)庫。這個(gè)聽起來很神奇，實(shí)際上在上面的例子里，Google已經(jīng)做到了。在這一系列的最后一 節(jié)里，我們會(huì)介紹我們開發(fā)的一個(gè)語義學(xué)習(xí)系統(tǒng)，它從上千億條文本數(shù)據(jù)中，歸納漢語中上百萬的“語義”。隨后，只要用戶輸入任何一段文本，這個(gè)系統(tǒng)可以利用 訓(xùn)練好的模型在一毫秒之內(nèi)，理解文本中表達(dá)的“語義”。這個(gè)理解過程確保消除文本中的歧義，從而讓搜索引擎、廣告系統(tǒng)、推薦系統(tǒng)等應(yīng)用更好地理解用戶需 求。

簡言之，互聯(lián)網(wǎng)使得人類第一次有機(jī)會(huì)收集全人類的行為數(shù)據(jù)。從而為機(jī)器學(xué)習(xí)這一持續(xù)了數(shù)十年的研究方向提供了全新的機(jī)會(huì)——分布式機(jī)器學(xué)習(xí)——從互聯(lián)網(wǎng)數(shù)據(jù)中歸納這個(gè)人類的知識(shí)，從而讓機(jī)器比任何一個(gè)個(gè)人都要“聰明”。

大數(shù)據(jù)和分布式機(jī)器學(xué)習(xí)特點(diǎn)

說故事之前，先提綱挈領(lǐng)的描述一下我們要解決的問題的特點(diǎn)。我見過的有價(jià)值的大規(guī)模機(jī)器學(xué)習(xí)系統(tǒng)，基本都有三個(gè)特點(diǎn)：

1. 可擴(kuò)展?？蓴U(kuò)展的意思是“投入更多的機(jī)器，能處理更大的數(shù)據(jù)”。而傳統(tǒng)的并行計(jì)算要的是：“投入更多機(jī)器，數(shù)據(jù)大小不變，計(jì)算速度更快”。這是我認(rèn)識(shí)中“大 數(shù)據(jù)”和傳統(tǒng)并行計(jì)算研究目標(biāo)不同的地方。如果只是求速度快，那么multicore和GPU會(huì)比分布式機(jī)器學(xué)習(xí)的ROI更高。有一個(gè)框架(比如MPI或 者M(jìn)apReduce或者自己設(shè)計(jì)的)，支持fault recovery。Fault recovery是可擴(kuò)展的基礎(chǔ)?，F(xiàn)代機(jī)群系統(tǒng)都是很多用戶公用的，其中任何一個(gè)進(jìn)程都有可能被更高優(yōu)先級(jí)的進(jìn)程preempted。一個(gè)job涉及數(shù)千 個(gè)進(jìn)程(task processes)，十分鐘里一個(gè)進(jìn)程都不掛的概率很小。而如果一個(gè)進(jìn)程掛了，其他進(jìn)程都得重啟，那么整個(gè)計(jì)算任務(wù)可能永遠(yuǎn)都不能完成。

2. 數(shù)學(xué)模型要根據(jù)架構(gòu)和數(shù)據(jù)做修改。這里有兩個(gè)原因：因?yàn)榇髷?shù)據(jù)基本都是長尾分布的，而papers里的模型基本都假設(shè)數(shù)據(jù)是指數(shù)分布的(想想用SVD做 component analysis其實(shí)假設(shè)了Gaussian distributed，latent Dirichlet allocation假設(shè)了multimonial distribution。)。真正能處理大數(shù)據(jù)的數(shù)學(xué)模型，都需要能更好的描述長尾數(shù)據(jù)。否則，模型訓(xùn)練就是忽視長尾，而只關(guān)注從“大頭”數(shù)據(jù)部分挖掘 “主流”patterns了。很多機(jī)器學(xué)習(xí)算法(比如MCMC)都不適合并行化。所以往往需要根據(jù)模型的特點(diǎn)做一些算法的調(diào)整。有時(shí)候會(huì)是 approximation。比如AD-LDA算法是一種并行Gibbs sampling算法，但是只針對(duì)LDA模型有效，對(duì)其他大部分模型都不收斂，甚至對(duì)LDA的很多改進(jìn)模型也不收斂。

3. 引入更多機(jī)器的首要目的不是提升性能，而是能處理更大的數(shù)據(jù)。用更多的機(jī)器，處理同樣大小的數(shù)據(jù)，期待 speedup提高——這是傳統(tǒng)并行計(jì)算要解決的問題 ——是multicore、SMP、MPP、GPU還是Beowolf cluster上得分布式計(jì)算不重要。在大數(shù)據(jù)情況下，困難點(diǎn)在問題規(guī)模大，數(shù)據(jù)量大。此時(shí)，引入更多機(jī)器，是期待能處理更大數(shù)據(jù)，總時(shí)間消耗可以不變甚 至慢一點(diǎn)。分布式計(jì)算把數(shù)據(jù)和計(jì)算都分不到多臺(tái)機(jī)器上，在存儲(chǔ)、I/O、通信和計(jì)算上都要消除瓶頸。

上述三個(gè)特點(diǎn)，會(huì)在實(shí)踐中要求“一個(gè)有價(jià)值的算法值得也應(yīng)該有自己獨(dú)特的框架”。

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

MPI這個(gè)框架很靈活，對(duì)程序結(jié)構(gòu)幾乎沒有太多約束，以至于大家有時(shí)把MPI稱為一組接口(interface)——MPI的I就是interface的意思。

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

二、pLSA和MPI——大數(shù)據(jù)的首要目標(biāo)是“大”而不是“快”

我2007年畢業(yè)后加入 Google做研究。我們有一個(gè)同事叫張棟，他的工作涉及pLSA模型的并行化。這個(gè)課題很有價(jià)值，因?yàn)間eneralized matrix decomposition實(shí)際上是collaborative filtering的generalization，是用戶行為分析和文本語義理解的共同基礎(chǔ)。幾年后的今天，我們都知道這是搜索、推薦和廣告這三大互聯(lián) 網(wǎng)平臺(tái)產(chǎn)品的基礎(chǔ)。

當(dāng)時(shí)的思路是用MPI來做并行 化。張棟和宿華合作，開發(fā)一套基于MPI的并行pLSA系統(tǒng)。MPI是1980年代流行的并行框架，進(jìn)入到很多大學(xué)的課程里，熟悉它的人很多。MPI這個(gè) 框架提供了很多基本操作：除了點(diǎn)對(duì)點(diǎn)的Send, Recv，還有廣播Bdcast，甚至還有計(jì)算加通信操作，比如AllReduce。

MPI很靈活，描述能力很強(qiáng)。因?yàn)镸PI對(duì)代碼結(jié)構(gòu)幾乎沒有什么限制——任何進(jìn)程之間可以在任何時(shí)候通信——所以很多人不稱之為框架，而是稱之為“接口”。

但是Google的并行計(jì)算環(huán)境上沒有MPI。當(dāng)時(shí)一位叫白宏杰的工程師將MPICH2移植到了Google的分布式操作系統(tǒng)上。具體的說，是重新實(shí)現(xiàn)MPI里的Send, Recv等函數(shù)，調(diào)用分布式操作系統(tǒng)里基于HTTP RPC的通信API。

MPI的AllReduce操作在很多機(jī)器學(xué)習(xí)系統(tǒng)的開發(fā)里都很有用。因?yàn)楹芏嗖⑿袡C(jī)器學(xué)習(xí)系統(tǒng)都是各個(gè)進(jìn)程分別訓(xùn)練模型，然后再合適的時(shí)候(比如一個(gè)迭代結(jié)束的時(shí)候)大家對(duì)一下各自的結(jié)論，達(dá)成共識(shí)，然后繼續(xù)迭代。這個(gè)“對(duì)一下結(jié)論，達(dá)成共識(shí)”的過程，往往可以通過AllReduce來完成。

如果我們關(guān)注一下MPI的研究，可以發(fā)現(xiàn)曾經(jīng)有很多論文都在討論如何高效實(shí)現(xiàn)AllReduce操作。比如我2008年的博文里提到一種當(dāng)時(shí)讓我們都覺得很聰明的一種算法。這些長年累月的優(yōu)化，讓MPICH2這樣的系統(tǒng)的執(zhí)行效率(runtimeefficiency)非常出色。

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

具體的說，MPI允許進(jìn)程之間在任何時(shí)刻互相通信。如果一個(gè)進(jìn)程掛了，我們確實(shí)可以請(qǐng)分布式操作系統(tǒng)重啟之。但是如果要讓這個(gè)“新生”獲取它“前世”的狀態(tài)，我們就需要讓它從初始狀態(tài)開始執(zhí)行，接收到其前世曾經(jīng)收到的所有消息。這就要求所有給“前世”發(fā)過消息的進(jìn)程都被重啟。而這些進(jìn)程都需要接收到他們的“前世”接收到過的所有消息。這種數(shù)據(jù)依賴的結(jié)果就是：所有進(jìn)程都得重啟，那么這個(gè)job就得重頭做。

一個(gè)job哪怕只需要10分鐘時(shí)間，但是這期間一個(gè)進(jìn)程都不掛的概率很小。只要一個(gè)進(jìn)程掛了，就得重啟所有進(jìn)程，那么這個(gè)job就永遠(yuǎn)也結(jié)束不了了。

雖然我們很難讓MPI框架做到faultrecovery，我們可否讓基于MPI的pLSA系統(tǒng)支持faultrecovery呢?原則上是可以的——最簡易的做法是checkpointing——時(shí)不常的把有所進(jìn)程接收到過的所有消息寫入一個(gè)分布式文件系統(tǒng)(比如GFS)?；蛘吒苯右稽c(diǎn)：進(jìn)程狀態(tài)和job狀態(tài)寫入GFS。Checkpointing是下文要說到的Pregel框架實(shí)現(xiàn)faultrecovery的基礎(chǔ)。

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

三、LDA和MapReduce——可擴(kuò)展的基礎(chǔ)是數(shù)據(jù)并行

因?yàn)镸PI在可擴(kuò)展性上的限制， 我們可以大致理解為什么Google的并行計(jì)算架構(gòu)上沒有實(shí)現(xiàn)經(jīng)典的MPI。同時(shí)，我們自然的考慮Google里當(dāng)時(shí)最有名的并行計(jì)算框架MapReduce。

MapReduce 的風(fēng)格和MPI截然相反。MapReduce對(duì)程序的結(jié)構(gòu)有嚴(yán)格的約束——計(jì)算過程必須能在兩個(gè)函數(shù)中描述：map和reduce;輸入和輸出數(shù)據(jù)都必須 是一個(gè)一個(gè)的records;任務(wù)之間不能通信，整個(gè)計(jì)算過程中唯一的通信機(jī)會(huì)是map phase和reduce phase之間的shuffuling phase，這是在框架控制下的，而不是應(yīng)用代碼控制的。

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

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

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

但 是2007年的時(shí)候，UC Irvine的David Newman團(tuán)隊(duì)發(fā)現(xiàn)，對(duì)于LDA這個(gè)特定的模型，Gibbs sampling可以被并行化。具體的說，把訓(xùn)練數(shù)據(jù)拆分成多份，用每一份獨(dú)立的訓(xùn)練模型。每隔幾個(gè)Gibbs sampling迭代，這幾個(gè)局部模型之間做一次同步，得到一個(gè)全局模型，并且用這個(gè)全局模型替換各個(gè)局部模型。這個(gè)研究發(fā)表在NIPS上，題目 是：Distributed Inference for Latent Dirichlet Allocation。

上述做法，在2012年Jeff Dean關(guān)于distributed deep leearning的論文中，被稱為data parallelism(數(shù)據(jù)并行)。如果一個(gè)算法可以做數(shù)據(jù)并行，很可能就是可擴(kuò)展(scalable)的了。

David Newman團(tuán)隊(duì)的發(fā)現(xiàn)允許我們用多個(gè)map tasks并行的做Gibbs sampling，然后在reduce phase中作模型的同步。這樣，一個(gè)訓(xùn)練過程可以表述成一串MapReduce jobs。我用了一周時(shí)間在Google MapReduce框架上實(shí)現(xiàn)實(shí)現(xiàn)和驗(yàn)證了這個(gè)方法。后來在同事Matthew Stanton的幫助下，優(yōu)化代碼，提升效率。但是，因?yàn)槊看螁?dòng)一個(gè)MapReduce job，系統(tǒng)都需要重新安排進(jìn)程(re-schedule);并且每個(gè)job都需要訪問GFS，效率不高。在當(dāng)年的Google MapReduce系統(tǒng)中，1/3的時(shí)間花在這些雜碎問題上了。后來實(shí)習(xí)生司憲策在Hadoop上也實(shí)現(xiàn)了這個(gè)方法。我印象里Hadoop環(huán)境下，雜碎事 務(wù)消耗的時(shí)間比例更大。

隨后白紅杰在我們的代碼基礎(chǔ)上修改了數(shù)據(jù)結(jié)構(gòu)，使其更適合MPI的AllReduce操作。這樣就得到了一個(gè)高效率的LDA實(shí)現(xiàn)。我們把用MapReduce和MPI實(shí)現(xiàn)的LDA的Gibbs sampling算法發(fā)表在這篇論文里了。

當(dāng) 我們躊躇于MPI的擴(kuò)展性不理想而MapReduce的效率不理想時(shí)，Google MapReduce團(tuán)隊(duì)的幾個(gè)人分出去，開發(fā)了一個(gè)新的并行框架Pregel。當(dāng)時(shí)Pregel項(xiàng)目的tech lead訪問中國。這個(gè)叫Grzegorz Malewicz的波蘭人說服了我嘗試在Pregel框架下驗(yàn)證LDA。但是在說這個(gè)故事之前，我們先看看Google Rephil——另一個(gè)基于MapReduce實(shí)現(xiàn)的并行隱含語義分析系統(tǒng)。

四、Rephil和MapReduce——描述長尾數(shù)據(jù)的數(shù)學(xué)模型

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

Rephil 的模型是一個(gè)全新的模型，更像一個(gè)神經(jīng)元網(wǎng)絡(luò)。這個(gè)網(wǎng)絡(luò)的學(xué)習(xí)過程從Web scale的文本數(shù)據(jù)中歸納海量的語義——比如“apple”這個(gè)詞有多個(gè)意思：一個(gè)公司的名字、一種水果、以及其他。當(dāng)一個(gè)網(wǎng)頁里包含”apple”, “stock”, “ipad”等詞匯的時(shí)候，Rephil可以告訴我們這個(gè)網(wǎng)頁是關(guān)于apple這個(gè)公司的，而不是水果。

這個(gè)功能按說pLSA和LDA也都能實(shí)現(xiàn)。為什么需要一個(gè)全新的模型呢?

從 2007年至今，國內(nèi)外很多團(tuán)隊(duì)都嘗試過并行化pLSA和LDA。心靈手巧的工程師們，成功的開發(fā)出能學(xué)習(xí)數(shù)萬甚至上十萬語義(latent topics)的訓(xùn)練系統(tǒng)。但是不管大家用什么訓(xùn)練數(shù)據(jù)，都會(huì)發(fā)現(xiàn)，得到的大部分語義(相關(guān)的詞的聚類)都是非常類似，或者說“重復(fù)”的。如果做一個(gè)“去 重”處理，幾萬甚至十萬的語義，就只剩下幾百幾千了。

這是怎么回事?

如果大家嘗試著把訓(xùn)練語料中的低頻詞去掉，會(huì)發(fā)現(xiàn)訓(xùn)練得到的語義和用全量數(shù)據(jù)訓(xùn)練得到的差不多。換句話說，pLSA和LDA模型的訓(xùn)練算法沒有在意低頻數(shù)據(jù)。

為什么會(huì)這樣呢?因?yàn)閜LSA和LDA這類概率模型的主要構(gòu)造單元都是指數(shù)分布(exponential distributions)。比如pLSA假設(shè)一個(gè)文檔中的語義的分布是multinomial的，每個(gè)語義中的詞的分布也是multinomial 的。因?yàn)閙ultinomial是一種典型的指數(shù)分布，這樣整個(gè)模型描述的海量數(shù)據(jù)的分布，不管哪個(gè)維度上的marginalization，都是指數(shù)分 布。在LDA中也類似——因?yàn)長DA假設(shè)各個(gè)文檔中的語義分布的multinomial distributions的參數(shù)是符合Dirichlet分布的，并且各個(gè)語義中的詞的分布的multinomial distributions的參數(shù)也是符合Dirichlet分布的，這樣整個(gè)模型是假設(shè)數(shù)據(jù)是指數(shù)分布的。

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

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

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

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

實(shí)際上，Rephil就是這樣一個(gè)能理解百態(tài)的模型。因?yàn)樗袵oogleAdSense的盈利能力大幅提升，最終達(dá)到Google收入的一半。兩位作者榮獲Google的多次大獎(jiǎng)，包括Founders’Award。

而切掉長尾是一個(gè)很糟糕的做法。大家還記得小說《1984》里有這樣一個(gè)情節(jié)嗎?老大哥要求發(fā)布“新話”——一種新的語言，刪掉自然英語中大部分詞匯，只留下那些主流的詞匯?？纯葱≌f里的人們生活的世界，讓人渾身發(fā)毛，咱們就能體會(huì)“割尾巴”的惡果了。沒有看過《1984》的朋友可以想象一下水木首頁上只有“全站十大”，連“分類十大”都刪掉之后的樣子。

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

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

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

可是在互聯(lián)網(wǎng)的世界里，正是這些五花八門的outliers和noise，蘊(yùn)含了世間百態(tài)，讓數(shù)據(jù)不可壓縮，從而產(chǎn)生了“大數(shù)據(jù)”這么個(gè)概念。處理好大數(shù)據(jù) 的公司，賺得盆滿缽滿，塑造了一個(gè)個(gè)傳奇。這里有一個(gè)聽起來比較極端的說法大數(shù)據(jù)里無噪聲——很多一開始頻率很低，相當(dāng)長尾，會(huì)被詞過濾系統(tǒng)認(rèn)為是拼寫錯(cuò) 誤的queries，都能后來居上成為主流。比如“神馬”，“醬紫”。

Rephil 系統(tǒng)實(shí)現(xiàn)的模型是一個(gè)神經(jīng)元網(wǎng)絡(luò)模型(neural network)。它的設(shè)計(jì)的主要考慮，就是要能盡量好的描述長尾分布的文本數(shù)據(jù)和其中蘊(yùn)含的語義。Rephil模型的具體技術(shù)細(xì)節(jié)因?yàn)闆]有在論文中發(fā)表 過，所以不便在這里透露。但是Rephil模型描述長尾數(shù)據(jù)的能力，是下文將要介紹的Peacock系統(tǒng)的原動(dòng)力，雖然兩者在模型上完全不同。

Rephil 系統(tǒng)是基于Google MapReduce構(gòu)建的。如上節(jié)所述，MapReduce在用來實(shí)現(xiàn)迭代算法的時(shí)候，效率是比較低的。這也是Peacock要設(shè)計(jì)全新框架的原動(dòng)力—— 使其比MapReduce高效，但同時(shí)像MapReduce一樣支持fault recovery。