?兔子和分布式機器學習

兔子和分布式機器學習

        上個學習的時候，我除了TA機器學習以外，另外一半的時間就是上了System課程。因為上課的緣故，需要做一個課程項目，于是我決定做一些和分布式機器學習相關的事情。

         來到UW之后每一個和engineering的課程設計都會想做一些高效實用的東西。這一次一開始想到的目標之一，就是寫一個自己可以寫出的最高效的分布式boostedtree（也就是大家常說的GBDT）工具。想這么做也并非沒有基礎，之前我們完成的xgboost，已經是很快的單機多線程版本了，可以輕松處理百萬到千萬級別的數據。

        不過一個顯然的問題是，分布式機器學習程序并非systems而僅僅算是系統的應用而已。并不足以作為一個系統課程的課程設計來做。因此我到了直到學期結束前三周依然沒有明確題目，只是在空閑的時間嘗試去實現分布式的tree。

目標：

      在一開始設計這個東西的時候，我有一些心中的目標。一開始的目標基本總結下來就是，速度快，可移植，少寫代碼。 速度快是自然的目標，體現這個目標的一個的想法是在寫的似乎機器內部依然沿用單機多線程的優化來減少通信，只在機器之間來進行通信。

     可移植性是一個更大的困難，要做分布式機器學習必須有分布式的通信框架。而每個分布式系統本身的抽象各不相同，hadoop/spark做的是MapReduceabstraction，graphlab做graph parallel，MPI提供的是 Allreduce/Broadcast，PS提供的是異步的更新。要想要讓分布式程序可以運行在不同的環境下比起讓一個單機機器學習程序從linux移植到windows困難許多。但是其實本質上，這個東西和把linux移植到windowss又沒有差別。之所以一個程序可以從linux移植到windows，是因為程序僅僅依賴一些系統調用的接口，而我們只需要在每個平臺下面提供一套這類接口就可以了。同樣的，我也在之前就表示過，我不想讓自己的機器學習代碼往一個特殊的平臺上面去靠，而是希望根據算法本身的需求，抽象出合理的接口，通過通用的庫讓平臺往接口需求上面去走。原因也很簡單，比起很多平臺一開始支持的比較好的數據處理問題，機器學習往往需要消耗更多的計算資源和時間，根據機器學習的需求去設計通信庫也是很自然的事情。

    因此我在設計的時候定的目標是想一想需要什么，大不了自己寫通信，不要依賴平臺。。經過這樣思考之后我考慮了對于boostedtree可能的分布式算法。發現Allreduce的交互比較自然，于是決定使用Allreduce作為算法依賴的通信。

為什么用Allreduce：

       決定使用Allreduce并非偶然。之前我在weibo上面提分布式機器學習需要依賴的基本通信抽象的時候，老師木就說過他覺得應該是MPI。大部分的分布式機器學習算法的結構都是分布數據，在每個子集上面算出一些局部的統計量，然后整合出全局的統計量，并且在分配給各個計算節點去進行下一輪的迭代。這樣一個過程就是Allreduce。分布式機器學習和傳統的數據處理有一些區別。其中一個大的區別是分布式機器學習算法往往會用比較多的資源，包括臨時空間，線程，結果緩存等。這樣機器學習程序往往顯得更加“重量級”。因此為了優化這一特點，我們往往需要讓一個程序在必要的時候占領一臺機器，并且在所有迭代的時候一直跑到底，來防止重新分配資源的開銷。一開始為數據處理而設計的MapReduce采用的是多stage執行的方式，沒有具備這一特點。而 Allreduce和基于異步通信的Parameter Server框架則具備了這一特點，因此更加有利于高效的機器學習算法。我個人認為同步的Allreduce和異步的PS抽象會是高效機器學習算法最常用的兩個抽象，越來越多地出現在以機器學習為中心的分布式平臺中。

實現一個 Allreduce：

       我實現的分布式xgboost第一個版本，是基于Allreduce接口的。而并非直接依賴于MPI。原因也很簡單， 我希望算法依賴僅僅需要的最少的接口，來方便后面最大的可移植性。在第一個版本中Allreduce接口的實現本身直接采用了MPI的實現。為了實現更大的可移植性，我又到后來自己手碼了一個Allreduce的庫，使得程序運行不再依賴于MPIcluster。實現到這里，有一個比較有趣的地方是我發現可移植和少寫代碼這兩個目標其實出奇地一致。因為采用了簡單的接口，分布式的代碼對于多線程代碼的不過僅僅是加入了一些同步函數而已，而這樣同步函數也可以直接關掉，讓分布式程序和單機程序共享一份代碼。

Rabit: 可容錯的Allreduce

       當我搞完第一個版本的分布式的時候，我發現離學期末只有兩周時間了。。。當時一下子拿不定主意想要做什么，因為分布式機器學習程序有了，但是不夠交作業。但是想要改進boostedtree的愿望促使我開始想另外一個常見需求：容錯。

       Allreduce是MPI提供的一個主要功能，但是MPI一般不是特別受到廣泛歡迎，原因之一就是它本身不容錯。 經過考慮，我們發現其實分布式機器學習程序里面只需要Allreduce，這一點JohnLangford也在他的博客里面經常提到。而更加重要的一點是，如果砍掉MPI多余的接口，就保留Allreduce和Broadcast，支持容錯會變得容易許多。原因是Allreduce有一個很好的性質，每一個節點最后拿到的是一樣的結果，這意味著我們可以讓一些節點記住結果。當有節點掛掉重啟的時候，可以直接向還活著的節點索要結果就可以了。

      基于這個基本的想法，和機器學習的需求，我們設計了一個可以容錯的Allreduce庫。叫做Rabit(ReliableAllreduce and Broadcast Interface)。然后這個庫了就成為我最后系統作業交差的內容。目前的Rabit支持python和C++，并且可以運行在包括MPI和Hadoop 等各種平臺上面。基于rabit寫的程序也可以自然地移植到各個平臺上。值得一提的是因為通信是Allreduce，那個原來一直被當作分布式機器學習龜速baseline的Hadoop也可以跑高效的分布式機器學習程序了。

      而Rabit的設計理念也和兔子的特性差不多：到處跑（可移植），可以挖坑不怕死（容錯），跑得快。并且輕量級。不做解決一切問題的框架，但是做可移植，精確解決一部分機器學習問題的高效容錯通信庫。

最后是代碼鏈接，歡迎，使用拍磚以及貢獻代碼：）

 Rabit庫 https://github.com/tqchen/rabit

Rabit的教程：https://github.com/tqchen/rabit/tree/master/guide

分布式的boosted tree(GBDT): https://github.com/tqchen/xgboost/tree/master/multi-node

來自：http://weibo.com/p/1001603801281637563132