輕量級大規模機器學習算法庫Fregata開源：快速，無需調參
一. 大規模機器學習的挑戰
隨著互聯網，移動互聯網的興起，可以獲取的數據變得越來越多，也越來越豐富。數據資源的豐富，給機器學習帶來了越來越多，越來越大創造價值的機會。 機器學習在計算廣告，推薦系統這些價值上千億美元的應用中起到的作用越來越大，創造的價值也越來越大。但是越來越大的數據規模也給機器學習帶來了很多挑戰。
最大的挑戰就是龐大的數據量使得對計算資源的需求也急劇增長。首先經典的機器學習算法其計算量基本上都是與訓練數據條數或者特征數量呈二次方甚至是三次方關系的[1]。即是說數據量或者特征數每翻一倍，則計算量就要增加到原來的四倍，甚至是八倍。這樣的計算量增長是十分可怕的，即使是采用可擴展的計算機集群一難以滿足這樣的計算量增長。好在對于很多依賴于凸優化方法的算法，可以采用隨機梯度下降方法，將計算量的增長降到基本與數據量和特征數呈線性關系。但是，大規模機器學習在計算上依然有三個比較大的困難。
第一，因為幾乎所有的機器學習算法都需要多次掃描數據，對于大規模數據無論在什么平臺上，如果不能全部存儲在內存中，就需要反復從磁盤存儲系統中讀取數據，帶來巨大的IO開銷。在很多情況下，IO開銷占到整個訓練時間的90%以上。
第二，即使有足夠的資源將所有數據都放到內存中處理，對于分布式的計算系統，模型訓練過程中對模型更新需要大量的網絡通信開銷。無論是同步更新還是異步更新，龐大的數據量和特征數都足以使得通信量爆炸，這是大規模機器學習的另外一個瓶頸。
第三，大規模的模型使得無法在一個節點上存儲整個模型，如何將模型進行分布式的管理也是一個比較大的挑戰。
圖 1
目前的主流大數據處理技術都是以Map Reduce計算模式為核心的(包括Hadoop和Spark)。而Map Reduce計算模式下對第一個問題只能通過增加內存，SSD存儲來解決或者緩解，但同時也需要付出高昂的成本。對于第二，和第三個個問題，Map Reduce模式的局限是很難克服這兩個問題的。
而Parameter Server[2]作為目前最新的大規模機器學習系統設計模式，主要解決的其實是第三個問題，通過參數服務器以及模型參數的分布式管理來實現對超大規模模型的支持。同時在模型更新過程中的通信模式可以采用異步更新模式，來減小數據同步的開銷，提高通信效率，但是Parameter Server模式下模型的更新量計算和模型的更新是分離的，其龐大的通信開銷在原理上就是不可避免的。幸運的是，常見的大規模機器學習問題，都是高維稀疏問題，在很大程度上緩解了通信開銷的問題，而Parameter Server突破了模型規模限制的優點是Map Reduce模式無法取代的，所以Parameter Server成為了目前大規模機器學習最先進，最受認可的模式。
圖 2
雖然Parameter Server解決了模型分布式管理的瓶頸，異步通信模式和問題本身的稀疏性大大降低了通信的壓力。 但是機器學習算法本身對數據的多次掃描帶來的計算和通信開銷依然是大規模機器學習效率的很大瓶頸。
除此之外還有一個很大的挑戰就是算法的調參工作， 一般機器學習算法都會依賴一個或者多個參數，對于同一問題，不同的參數設定對模型精度的影響是很大的，而同一參數設定在不同的問題上的效果也有很大的不同。對于從事機器學習工作的人來說，調參始終是一個令人的頭疼的問題。知乎上有個問題是“調參這事兒，為什么越干越覺得像老中醫看病?”[3]，里面有不少關于機器學習調參的經驗，心得，吐槽和抖機靈。
對于大規模機器學習問題，調參的難度顯然是更大的：
首先，一次訓練和測試過程的時間和計算資源開銷都是龐大的，不管采用什么調參方法，多次實驗都會帶來很大的時間和計算資源消耗。
其次，大規模機器學習問題通常都是數據變化很快的問題，如計算廣告和推薦系統，之前確定好的參數在隨著數據的變化，也有劣化的風險。
目前來說大規模機器學習存在的主要挑戰是兩個：第一是計算資源的消耗比較大，訓練時間較長的問題，第二是調參比較困難，效率較低。TalkingData在大規模機器學習的實踐中也深受這兩個問題的困然，特別是公司在早起階段硬件資源十分有限，這兩個問題特別突出。我們為了解決這個問題，做了很多努力和嘗試。TalkingData最近開源的Fregata項目[4]，就是我們在這方面取得的一些成果的總結。
二. Fregata的優點
Fregata是TalkingData開源的大規模機器學習算法庫，基于Spark，目前支持Spark 1.6.x, 很快會支持Spark 2.0。目前Fregata包括了Logistic Regression, Softmax, 和Random Decision Trees三中算法。
三種算法中Logistic Regression, Softmax可以看作一類廣義線性的參數方法，其訓練過程都依賴于凸優化方法。我們提出了Greedy Step Averaging[5]優化方法，在SGD優化方法基礎上實現了學習率的自動調整，免去了調參的困擾，大量的實驗證明采用GSA 優化方法的Logstic Regression和Softmax算法的收斂速度和穩定性都是非常不錯的，在不同數據規模，不同維度規模和不同稀疏度的問題上都能取得很好的精度和收斂速度。
基于GSA優化方法，我們在Spark上實現了并行的Logistic Regression和Softmax算法，我們測試了很多公開數據集和我們自己的數據，發現在絕大部分數據上都能夠掃描一遍數據即收斂。這就大大降低了IO開銷和通信開銷。
其中Logsitic Regression算法還有一個支持多組特征交叉的變種版本，其不同點是在訓練過程中完成維度交叉，這樣就不需要在數據準備過程中將多組特征維度預先交叉準備好，通常這意味著數據量級上的數據量膨脹，給數據存儲和IO帶來極大壓力。而這種多組特征交叉的需求在計算廣告和推薦系統中又是非常常見的，因此我們對此做了特別的支持。
而Random Decision Trees[6][7]算法是高效的非參數學習方法，可以處理分類，多標簽分類，回歸和多目標回歸等問題。而且調參相對也是比較簡單的。但是由于樹結構本身比較復雜而龐大，使得并行比較困難，我們采用了一些Hash Trick使得對于二值特征的數據可以做到掃描一遍即完成訓練，并且在訓練過程中對內存消耗很少。
總結起來，Fregata的優點就兩個，第一是速度快，第二是算法無需調參或者調參相對簡單。這兩個優點降低了減少了計算資源的消耗，提高了效率，同時也降低了對機器學習工程師的要求，提高了他們的工作效率。
三. GSA算法介紹
GSA算法是我們最近提出的梯度型隨機優化算法,是Fregata采用的核心優化方法。它是基于隨機梯度下降法(SGD)的一種改進：保持了SGD易于實現，內存開銷小，便于處理大規模訓練樣本的優勢，同時免去了SGD不得不人為調整學習率參數的麻煩。
事實上，最近幾年關于SGD算法的步長選取問題也有一些相關工作，像Adagrad, Adadelta, Adam等。但這些方法所聲稱的自適應步長策略其實是把算法對學習率的敏感轉移到了其他參數上面，并未從本質上解決調參的問題，而且他們也引入了額外的存儲開銷。GSA和這些算法相比更加輕量級，易于實現且易于并行，比起SGD沒有額外的內存開銷，而且真正做到了不依賴任何參數。
我們把GSA算法應用于Logistic回歸和Softmax回歸，對libsvm上16個不同類型規模不等的數據集，和SGD，Adadelta，SCSG(SVRG的變種)這些目前流行的隨機優化算法做了對比實驗。結果顯示，GSA算法在無需調任何參數的情況下，和其他算法做參數調優后的最佳表現不相上下。此外，GSA比起這些流行的方法在計算速度和內存開銷方面也有一定的優勢。
GSA算法的核心原理非常簡單：在迭代的每一步對單個樣本的損失函數做線搜索。具體來說，我們對邏輯回歸和softmax回歸的交叉熵損失函數，推導出了一套僅用當前樣本點的梯度信息來計算精確線搜索步長的近似公式。我們把利用這套近似公式得到的步長做時間平均來計算當前迭代步的學習率。這樣做有兩方面的好處：基于精確線搜索得到的步長包含了當前迭代點到全局極小的距離信息——接近收斂時步長比較小，反之則更大，因而保證收斂速度;另一方面平均策略使算法對離群點更魯棒，損失下降曲線不至劇烈抖動，為算法帶來了額外的穩定性。
四. GSA算法Spark上的并行化實現
GSA算法是基本的優化方法，在Spark上還需要考慮算法并行化的問題。機器學習算法的并行化有兩種方式，一種是數據并行，另一種是模型并行。但是Spark只能支持數據并行，因為模型并行會產生大量細粒度的節點間通信開銷，這是Spark采用的BSP同步模式無法高效處理的。
數據并行模式下進行機器學習算法的并行化又有三種方法，分別是梯度平均，模型平均，以及結果平均。梯度平均是在各個數據分片上計算當前的梯度更新量然后匯總平均各分片上的梯度更新量總體更新模型。模型平均是各分片訓練自己的模型，然后再將模型匯總平均獲得一個總體的模型。而結果平均實際上就是Ensemble Learning， 在大規模問題上因為模型規模的問題，并不是一個好的選擇。
實際上是目前采用得最多的是梯度平均，當前Parameter Server各種實現上主要還是用來支持這種方式，Spark MLLib的算法實現也是采用的該方式。但是在Spark上采用梯度平均在效率上也有比較大的瓶頸，因該方法計算當前的梯度更新量是要依賴于當前的最新模型的，這就帶來了在各數據分片之間頻繁的模型同步開銷，這對Map Reuce計算模式的壓力是較大的。
模型平均一直被認為其收斂性在理論上是沒有保證的，但是最近Rosenblatt[8]等人證明了模型平均的收斂性。而我們在大量的測試中，也發現模型平均通常能取得非常好的模型精度。考慮到模型平均的計算模式更適合Map Reduce計算模型，我們在Fregata中對于GSA算法的并行方法采用的就是模型平均方法。模型平均的并行方法中，每個數據分片在Map階段訓練自己的模型，最后通過Reduce操作對各個分片上的模型進行平均，掃描一次數據僅需要做一次模型同步。而且在大量的實驗中，該方法在掃描一次數據后，模型的精度就可達到很高的水平，基本接近于更多次迭代后的最好結果。
五. Fregata與MLLib對比
Fregata是基于Spark的機器學習算法庫，因此與Spark內置算法庫MLLib具有很高的可比性。我們這里簡要介紹了三個數據集，兩種算法(Logistic Regression和Softmax)上的精度和訓練時間對比。精度指標我們采用的是測試集的AUC。對于精度和訓練時間，算法每掃描完一次數據記錄一次。
Fregata的算法不需要調參，因此我們都只做了一次實驗。而對于MLLib上的算法，我們在各種參數組合(包括優化方法的選擇)中進行了網格搜索，選取了測試集AUC能達到最高的那組參數作為對比結果。
Lookalike是一個基于Fregata平臺運用比較成熟的服務，其目標在于根據種子人群進行人群放大以尋找潛在客戶。我們將Lookalike作為二分類問題來處理，因此可以采用Logistic Regression算法來處理。在訓練模型時以種子人群為正樣本，其他為負樣本，通常種子人群的數量不會很多，因此Lookalike通常是正樣本比例非常少的class imblance問題。 在一個大規模數據集(4億樣本，2千萬個特征)上的Lookalike問題的模型訓練中，我們對比了Fregata LR和MLLib LR的性能。
從圖4中可以看到Fregata的LR算法掃描一次數據即收斂達到AUC(測試集上)的最高值0.93。在這個數據樣本中 而MLLib的LR算法，即使我們通過調參選取了最好的AUC結果，其AUC也僅為0.55左右。模型預測精度差別非常大。另外，MLLib的訓練時間(達到最高精度的時間)也是Fregata大的6倍以上。
在公開數據集eplison[9]上(40萬訓練集，2000特征), Fregata LR無論從收斂速度還是模型效果與MLLib LR相比也有較大的優勢。從圖5中可以看到，在這個數據集上Fregata LR在迭代一次以后就在測試集上非常接近最好的結果了，而MLLib LR需要5次迭代而且最高的精度比Fregata LR相差很大，而訓練時間MLLib LR也是Fregata LR的5倍以上。
另外圖6展示了Fregata LR與MLLib LR在6個不同問題上的測試集AUC曲線，可以看到Fregata LR算法在不同問題上收斂速度和穩定性相較于MLLib LR都是有較大的優勢。Fregata LR在第一次迭代后，AUC就已經基本收斂，即使與最高值還有一些差距，但是也是非常接近了。
我們也在公開數據集MNIST上測試了Softmax算法。 從圖7中可以看到， Fregata Softmax也是一次掃描數據后在測試集上的AUC就非常接近最好的結果， 而MLLib Softmax需要掃描數據多達40多次以后才接近Fregata Softmax一次掃描數據的結果。對比兩個算法在達到各自最優結果所花的時間，MLLib Softmax是Fregata Softmax的50倍以上。
六. Fregata的使用簡介
前面簡要介紹了Fregata算法庫涉及到的一些技術原理和性能對比，我們再來看看Fregata的使用方式。可以通過3種不同的方式來獲取Fregata如果使用Maven來管理工程，則可以通過添加如下代碼在pom.xml中進行引入，
- <dependency>
- <groupId>com.talkingdata.fregata</groupId>
- <artifactId>core</artifactId>
- <version>0.0.1</version>
- </dependency>
- <dependency>
- <groupId>com.talkingdata.fregata</groupId>
- <artifactId>spark</artifactId>
- <version>0.0.1</version>
- </dependency>
如果使用SBT來管理工程，則可以通過如下代碼在build.sbt中進行引入，
- // 如果手動部署到本地maven倉庫，請將下行注釋打開
- // resolvers += Resolver.mavenLocal
- libraryDependencies += "com.talkingdata.fregata" % "core" % "0.0.1"
- libraryDependencies += "com.talkingdata.fregata" % "spark" % "0.0.1"
如果希望手動部署到本地maven倉庫，可以通過在命令中執行如下命令來完成：
- git clone https://github.com/TalkingData/Fregata.git
- cd Fregata
- mvn clean package install
接下來，讓我們以Logistic Regression為例來看看如何快速使用Fregata完成分類任務：
1.引入所需包
- import fregata.spark.data.LibSvmReader
- import fregata.spark.metrics.classification.{AreaUnderRoc, Accuracy}
- import fregata.spark.model.classification.LogisticRegression
- import org.apache.spark.{SparkConf, SparkContext}
2. 通過Fregata的LibSvmReader接口加載訓練及測試數據集，訓練及測試數據集為標準LibSvm格式，可參照[10]
- val (_, trainData) = LibSvmReader.read(sc, trainPath, numFeatures.toInt)
- val (_, testData) = LibSvmReader.read(sc, testPath, numFeatures.toInt)
3. 針對訓練樣本訓練Logsitic Regression 模型
- val model = LogisticRegression.run(trainData)
4. 基于已經訓練完畢的模型對測試樣本進行預測
- val pd = model.classPredict(testData)
5. 通過Fregata內置指標評價模型效果
- val auc = AreaUnderRoc.of( pd.map{
- case ((x,l),(p,c)) =>
- p -> l
- })
在Fregata中，使用breeze.linalg.Vector[Double]來存儲一個樣本的特征，如果數據格式已經是LibSvm，則只需通過Fregata內部的接口LibSvmReader.read(…)來加載即可。否則，可以采用如下的方法將代表實例的一組數據封裝成breeze.linalg.Vector[Double]即可放入模型中進行訓練及測試。
- // indices Array類型，下標從0開始，保存不為0的數據下標
- // values Array類型， 保存相應于indices中對應下標的數據值
- // length Int類型，為樣本總特征數
- // label Double類型，為樣本的標簽。如果是測試數據，則不需該字段
- sc.textFile(input).map{
- val indicies = ...
- val values = ...
- val label = ...
- ...
- (new SparseVector(indices, values, length).asInstanceOf[Vector], asNum(label))
- }
七. Freagata的發展目標
Fregata目前集成的算法還不多，未來還會繼續擴充更多的高效的大規模機器學習算法。Fregata項目追求的目標有3個：輕量級，高性能，易使用。
輕量級是指Fregata將盡可能在標準Spark版本上實現算法，不另外搭建計算系統，使得Fregata能夠非常容易的在標準Spark版本上使用。雖然Spark有一些固有的限制，比如對模型規模的限制，但是作為目前大數據處理的基礎工具，Fregata對其的支持能夠大大降低大規模機器學習的應用門檻。畢竟另外搭建一套專用大規模機器學習計算平臺，并整合到整個大數據處理平臺和流程中，其成本和復雜性也是不可忽視的。
高性能就是堅持高精度和高效率并舉的目標，盡可能從算法上和工程實現上將算法的精度和效率推到極致，使得大規模機器學習算法從笨重的牛刀變成輕快的匕首。目前對Fregata一個比較大的限制就是模型規模的問題，這是基于Spark天生帶來的劣勢。未來會采用一些模型壓縮的方法來緩解這個問題。
易使用也是Fregata追求的一個目標，其中最重要的一點就是降低調參的難度。目前的三個算法中有兩個是免調參的，另一個也是相對來說調參比較友好的算法。降低了調參的難度，甚至是免去了調參的問題，將大大降低模型應用的難度和成本，提高工作效率。
另一方面我們也會考慮某些常用場景下的特殊需求，比如LR算法的特征交叉需求。雖然通用的LR算法效率已經很高，但是對于特征交叉這種常見需求，如果不把特征交叉這個過程耦合到算法中去，就需要預先將特征交叉好，這會帶來巨大的IO開銷。而算法實現了對特征交叉的支持，就規避了這個效率瓶頸。未來在集成更多的算法的同時，也會考慮各種常用的場景需要特殊處理的方式。
Fregata項目名稱的中文是軍艦鳥，TalkingData的開源項目命名都是用的鳥名，而軍艦鳥是世界上飛得最快的鳥，最高時速達到418km/小時，體重最大1.5公斤，而翼展能夠達到2.3米，在全球分布也很廣泛。我們希望Fregata項目能夠像軍艦鳥一樣，體量輕盈，但是能夠支持大規模，高效的機器學習，而且具有很強的適用性。目前Fregata還是只雛鳥, 期望未來能夠成長為一只展翅翱翔的猛禽。
引用
[1] Cheng T. Chu, Sang K. Kim, Yi A. Lin, Yuanyuan Yu, Gary R. Bradski, Andrew Y. Ng, Kunle Olukotun， Map-Reduce for Machine Learning on Multicore, NIPS, 2006.
[2]
[3] https://www.zhihu.com/question/48282030
[4] https://github.com/TalkingData/Fregata
[5] http://arxiv.org/abs/1611.03608
[6] http://www.ibm.com/developerworks/cn/analytics/library/ba-1603-random-decisiontree-algorithm-1/index.html
[7] http://www.ibm.com/developerworks/cn/analytics/library/ba-1603-random-decisiontree-algorithm-2/index.html
[8] Rosenblatt J D, Nadler B. On the optimality of averaging in distributed statistical learning[J]. Information and Inference, 2016: iaw013 MLA
[9] https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html#epsilon
[10] https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/
作者介紹
張夏天：TalkingData首席數據科學家，12年大規模機器學習和數據挖掘經驗，對推薦系統、計算廣告、大規模機器學習算法并行化、流式機器學習算法有很深的造詣;在國際頂級會議和期刊上發表論文12篇，申請專利9項;前IBM CRL、騰訊、華為諾亞方舟實驗室數據科學家;KDD2015、DSS2016國際會議主題演講;機器學習開源項目Dice創始人。
