分散式機器學習的故事：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的inference很麻煩，沒法做精確inference，只有近似演算法，比如variational inference。如果EM演算法中的E-step採用variational infernece，那麼EM演算法就被稱為variational EM。EM本來就是一個比較容易陷入局部最優的演算法，E-step用了variational inference，總體效果就更差了。另一種近似inference演算法是Gibbs sampling。雖然我們可以在E-step里用Gibbs sampling替換variational inference，但是Thomas Griffiths發現一個有趣的特點——稍微修改LDA之後，就可以利用Dirichlet和multinomial分布的共軛性，把模型參數都積分積掉。沒有參數了，也就所謂M-step里的「更新參數」了。這樣，只需要做Gibbs sampling即可。這個路子發表在PNAS上，題目是Finding Scientific Topics。

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實現的並行隱含語義分析系統。