分布式云端機器學習

原文作者：微軟云信息服務實驗室研究員 Dhruv Mahajan, Sundararajan Sellamanickam, 
Keerthi Selvaraj

譯者：張彤

如今，各類企業都在積聚越來越龐大的數據資產，比如用戶行為、系統訪問、使用模式等數據記錄。而運用像微軟 Azure 機器學習平臺這樣的云端服務平臺，企業不僅僅可以用它來儲存數據，做一些經典的“后視”商務智能分析，更能使用云端的強大力量做出具有“前瞻性”的預測分析。使用 Azure 機器學習這樣的現代化工具，企業可以獲得關于其業務未來發展的切實見解——這將成為它們的競爭優勢。

對“大數據”的收集和維護已經成為許多應用程序的普遍需求。隨著數據量的劇增，分布式儲存已成為必然趨勢。在許多應用中，收集數據本身就是一個 分散的過程，自然導致了分布式的數據儲存。這種情況下，建立起以分布式計算處理分布式數據的機器學習（以下簡稱“ML”）方案就十分必要。這些方案包括： 通過在線廣告領域的邏輯回歸分析來估計點擊率，應用于大量圖像和語音訓練的數據集的深度學習方案，或為檢測異常模式而進行的記錄分析。

因此，在一個集群中對 ML 方案進行高效的分布式訓練，是微軟云信息服務實驗室（CISL——Microsoft Cloud & Information Services Lab，發音像“sizzle”:-)）的重要研究領域。本文，我們將對這一主題進行一些較為深入的探討。下面所闡述的一些細節可能技術性略強，但我們會 盡可能以簡單易懂的方式來闡明它的中心思想。理解了這些想法，任何對大數據分布式 ML 感興趣的人都會有所收獲，我們也很期待你們的評論和反饋。

選擇合適的基礎設施

John Langford 在近期發表的一篇文章中，介紹了用于快速學習的 Vowpal Wabbit (VW) 系統，并簡要談及了對兆級數據集的分布式學習。因為大多 ML 的算法本質上是迭代，因此選擇合適的分布式框架來運行它們就變得十分關鍵。

Map Reduce 和它的開源實現 Hadoop，是目前較為流行的分布式數據處理平臺。但由于 ML 每次迭代都有巨大的開銷——如作業調度，數據傳送和數據解析，因此以上的分布式數據處理平臺并不能很好的用于迭代性的 ML 算法。

一個更好的選擇是增加通信基礎設施，如與 Hadoop 兼容的 All Reduce（像在 VW 中那樣），或者采用更新的分布框架，如支持有效迭代運算的 REEF。

統計查詢模型 (SQM)

目前分布式 ML 最先進的算法，如用于 VW 中的是基于統計查詢模型（SQM--Statistical Query Model） 的算法。在 SQM 中，學習是基于對每個數據點進行計算，然后將對所有數據點的運算結果進行累加。舉例來說，假設線性 ML 問題的結果是一個特征向量與其權重參數向量的點積。這包含了邏輯回歸、支持向量機（SVMs）和最小二乘方擬合(least squares fitting)等重要的預測模型。在這種情況下，每次迭代時的訓練目標函數的整體梯度是由各個數據點的梯度相加而成的。每個節點形成與該節點的訓練數據 相一致的局部梯度，然后用 All Reduce 運算來獲得整體梯度。

通信瓶頸

分布式運算常常要面臨一個關鍵瓶頸，即運算與通信寬帶之間的巨大比例差。舉例來說，通信速度比運算速度慢 10 倍到 50 倍都很常見。

以 Tcomm 和 Tcomp 分別表示通信和運算的單次迭代時間，那么一個迭代性 ML 算法的總時間花費可用下列算式表示：

總時間 =（Tcomm + Tcomp）* #迭代次數

當節點增多時，Tcomp 通常為線性下降，而 Tcomm 則上升或保持不變（All Reduce 良好實施的情況下）。涉及大數據的 ML 方案經常有眾多的權重參數(d)，這些參數在每次迭代時都會在集群中的節點間通信、更新。此外，其他步驟如 SQM 中的梯度運算也需要復雜度為O(d)的通信。這種情況在 Map Reduce 中更加不理想——每次迭代都需要一次獨立的 Map Reduce 工作。因此，當參數d很大時，Tcomm 也會變得很大。SQM 并未在這方面的低效率問題上給予足夠的重視。

攻克通信瓶頸問題

我們近期的研究正是 針對這一關鍵問題，并建立在下述現象之上：假設 Tcomm 節點間權重參數的通信時間非常大。在每次迭代中，采用 SQM 這種標準方法會使得 Tcomp 每個節點內與運算相關的時間，遠小于 Tcomm。因此我們提出以下問題，有沒有可能修改算法和其迭代，使 Tcomp 與 Tcomm 接近，并且在這個過程中，將該算法轉變成為迭代次數較少的理想方案呢？

當然，回答這個問題并不簡單，因為它意味著一次根本性的算法改變。

更多的具體細節

接下來讓我們考慮 ML 學習線性模型的問題。在我們的算法中，節點中權重更新和漸變的方式與 SQM 方式類似。然而，在每個節點中的漸變梯度（用 All Reduce 算出）和本地數據經過復雜的方式形成對全局問題的本地近似值。每個節點解決自己的近似問題，形成權重變量的本地更新，隨后所有節點的本地更新結合形成權重 變量的全局更新。每個節點解決近似問題時會導致其計算量增多，但不需要任何額外的通信。這樣一來，雖然 Tcomp 增高，但因為 Tcomm 本身就很高，因此每次迭代花費的時間并未受到顯著影響。但是，由于每個節點現在解決的是近似全局視圖的問題，解決問題需要的迭代數量將大大減少。設想在無 比龐大的數據中，每個節點自身的數據就足以實現良好的學習。這種情況下，每個節點形成的近似問題就近似于全局問題，這樣 SQM 的算法需要幾百次甚至幾千次的迭代時，我們的算法只需要一或兩次迭代就能完成。此外，我們的方法也較為靈活，允許出現一系列的近似值而不只是一個特定值。 總體來說，我們的算法比 SQM 平均快了兩到三倍。

也可以考慮將權重向量分散到多個集群節點中，建立分布式數據儲存和運算方式，使任何一個權重變量的更新只發生在一個集群節點上。這在一些情況下非常有效，比如對線性 ML 問題中相關權重變量的歸零問題，或者做分布式深度訓練時。這樣我們又一次建立了特殊的迭代算法，增加了每節點內的運算但減少了迭代的次數。

評估

上述我們重點關注的算法比較適合通信負擔較重的情況，但這并不能解決在實際中的所有問題。對于一般的情況，最近的學術文獻中有很多好的分布式 ML 算法，但目前對這些方法還沒有一個細致的評測。最好的方法還在尋找它們通往云端 ML 庫的道路上。

根據用戶需求的自動分布式 ML

另外，還有一個重要的部分，即在云端上使用分布式 ML 的用戶擁有不同的需求。他們也許對最短時間內產生方案感興趣，也許認為最少花費產生方案很重要。在考慮上述變量進行最優選擇時，用戶愿意犧牲一些精確度。 另一種可能是，他們也許迫切地想知道最確切的結果，而不計時間和花費。考慮到問題描述、用戶的不同要求和系統配置的可應用性細節，擁有一個能夠選擇合適算 法和參數設定的自動程序十分重要。我們目前的研究也集中在這一方面。

在我們未來的產品發展中，自動分布式機器學習方案將會是微軟 Azure ML 重要的一個研究領域。