內容簡介
本書 旨在全面介紹分散式機器學習的現狀，深入分析其中的核心技術問題，並且討論該領域未來的發展方向。
全書共12章。第1章是緒論，向大家展示分散式機器學習這個領域的全景。第2章介紹機器學習的基礎知識。第3章到第8章是本書的核心部分，向大家細緻地講解分散式機器學習的框架及其各個功能模組。其中第3章給出整個分散式機器學習框架的綜述，而第4章到第8章則分別針對其中的數據與模型劃分模組、單機最佳化模組、通信模組、數據與模型聚合模組加以介紹。接下來的三章是對前面內容的總結與升華。其中第9章介紹由分散式機器學習框架中不同選項所組合出來的各式各樣的分散式機器學習算法，第10章討論這些算法的理論性質，第11章則介紹幾個主流的分散式機器學習系統（包括Spark MLlib 疊代式MapReduce系統，Multiverso參數伺服器系統，TensorFlow數據流系統）。最後的第12章是全書的結語，在對全書內容進行簡要總結之後，著重討論分散式機器學習這個領域未來的發展方向。
本書基於微軟亞洲研究院機器學習研究團隊多年的研究成果和實踐經驗寫成，既可以作為研究生從事分散式機器學習方向研究的參考文獻，也可以作為人工智慧從業者進行算法選擇和系統設計的工具書。
人工智慧大潮中，市場上已有許多機器學習書籍，但是分散式機器學習的專門書籍還很少見。本書是希望學習和了解分散式機器學習的讀者的福音。
作者簡介
劉鐵岩
微軟亞洲研究院副院長。劉博士的先鋒性研究促進了機器學習與信息檢索之間的融合，被國際學術界公認為“排序學習”領域的代表人物。近年來在深度學習、分散式學習、強化學習等方面也頗有建樹，發表論文200餘篇，被引用近兩萬次。多次獲得最佳論文獎、最高引用論文獎、Springer十大暢銷華人作者、Elsevier 最高引中國學者等。被聘為卡內基-梅隆大學（CMU）客座教授，諾丁漢大學榮譽教授，中國科技大學教授、博士生導師；被評為國際電子電氣工程師學會（IEEE）會士，國際計算機學會（ACM）傑出會員。
陳薇
微軟亞洲研究院機器學習組主管研究員，研究機器學習各個分支的理論解釋和算法改進，尤其關注深度學習、分散式機器學習、強化學習、博弈機器學習、排序學習等。2011年於中國科學院數學與系統科學研究院獲得博士學位，同年加入微軟亞洲研究院，負責機器學習理論項目，先後在NIPS、ICML、AAAI、IJCAI等相關領域頂級國際會議和期刊上發表文章30餘篇。
王太峰
螞蟻金服人工智慧部總監、資深算法專家。在螞蟻金服負責AI算法組件建設，算法工作服務於螞蟻金服的支付、國際、保險等多條業務線。在加入螞蟻之前在微軟亞洲研究院工作11年，任主管研究員，他的研究方向包括大規模機器學習、數據挖掘、計算廣告學等。在國際頂級的機器學習會議上發表近20篇的論文，在大規模機器學習工具開源方面也做出過很多貢獻，在微軟期間主持開發過DMTK的開源項目。
高飛
微軟亞洲研究院副研究員，主要從事分散式機器學習和深度學習的研究工作，並在國際會議上發表多篇論文。2014年設計開發了當時規模最大的主題模型算法和系統LightLDA。他還開發了一系列分散式機器學習系統，並通過微軟分散式機器學習工具包（DMTK）開源在GitHub上。
專家推薦
機器學習在許多領域取得了前所未有的成功，由此也徹底改變了人工智慧的發展方向，引發了大數據時代的到來。其中*富有挑戰性的問題是由分散式機器學習解決的。所以，要了解機器學習究竟能夠帶來什麼樣前所未有的新機遇、新突破，就必須了解分散式機器學習。
相比較而言，機器學習這個領域本身是比較單純的領域,其模型和算法問題基本上都可以被看成純粹的套用數學問題。而分散式機器學習則不然,它更像是一個系統工程，涉及數據、模型、算法、通信、硬體等許多方面，這更增加了系統了解這個領域的難度。劉鐵岩博士和他的合作者的這本書，從理論、算法和實踐等多個方面,對這個新的重要學科給出了系統、深刻的討論，對整個機器學習、大數據和人工智慧領域都是很大的貢獻。我看了這本書受益匪淺。相信對眾多關注機器學習的工作人員和學生，這也是一本難得的好書。
——鄂維南中國科學院院士，美國數學學會、美國工業與套用數學學會會士
普林斯頓大學、北京大學教授，北京大數據研究院院長
如果說人工智慧技術將造就人類的未來時代，那么作為人工智慧的核心支撐，機器學習將會像電力一樣無處不在。如何讓機器學習技術在業界的大規模任務中更充分地發揮威力，則成為熱議的話題，更為主流的解決方案是分散式機器學習。分散式機器學習並非分散式處理技術與機器學習的簡單結合。一方面，它必須考慮機器學習模型構成與算法流程本身的特點，否則分散式處理的結果可能失之毫釐、謬以千里；另一方面，機器學習內含的算法隨機性、參數冗餘性等，又會帶來一般分散式處理過程所不具備的、宜於專門利用的便利。
值得一提的是，市面上關於機器學習的書籍已有許多，但是分散式機器學習的專門書籍還頗少見。劉鐵岩博士是機器學習與信息檢索領域的國際著名專家，帶領的微軟亞洲研究院機器學習研究團隊成果斐然。此次他們基於分散式機器學習方面的豐富經驗推出《分散式機器學習：算法、理論與實踐》一書，將是希望學習和了解分散式機器學習的中文讀者的福音，必將有力促進相關技術在我國的推廣和發展。
——周志華歐洲科學院外籍院士，ACM / AAAS / AAAI / IEEE / IAPR 會士
南京大學教授、計算機科學與技術系主任、人工智慧學院院長
前言
近年來，人工智慧取得了飛速的發展，實現了一個又一個技術突破。這些成功的幕後英雄是大量的訓練數據、超大規模的機器學習模型以及分散式的訓練系統。一系列有關分散式機器學習的研究工作，從並行模式、跨機通信到聚合機制，從算法設計、理論推導到系統構建，都在如火如荼地展開。人們不僅發表了大量的學術論文，也開發出一批實用性很強的分散式機器學習系統。本書的目的是向讀者全面展示分散式機器學習的現狀，深入分析其中的核心技術問題，並且討論該領域未來發展的方向。本書既可以作為研究生從事分散式機器學習方向研究的參考文獻，也可以作為人工智慧從業者進行算法選擇和系統設計的工具書。
全書共12章。第1章是緒論，向大家展示分散式機器學習這個領域的全景。第2章介紹機器學習的基礎知識，其中涉及的基本概念、模型和理論，會為讀者在後續章節中更好地理解分散式機器學習的各項技術奠定基礎。第3章到第8章是本書的核心部分，向大家細緻地講解分散式機器學習的框架及其各個功能模組。其中第3章對整個分散式機器學習框架做綜述，而第4章到第8章則針對其中的數據與模型劃分模組、單機最佳化模組、通信模組、數據與模型聚合模組分別加以介紹，展示每個模組的不同選項並討論其長處與短板。接下來的三章是對前面內容的總結與升華。其中第9章介紹由分散式機器學習框架中不同選項所組合出來的各式各樣的分散式機器學習算法，第10章討論這些算法的理論性質（例如收斂性），第11章則介紹幾個主流的分散式機器學習系統（包括Spark MLlib、Multiverso參數伺服器系統和TensorFlow數據流系統）。最後的第12章是全書的結語，在對全書內容進行簡要總結之後，著重討論分散式機器學習這個領域未來的發展方向。
有關本書的寫作，因為涉及分散式機器學習的不同側面，不同的章節對讀者預備知識的要求有所不同。尤其是涉及最佳化算法和學習理論的部分，要求讀者對於最最佳化理論和機率統計有一定的知識儲備。不過，如果讀者的目的只是熟悉主流的分散式機器學習框架和系統，則可以跳過這些相對艱深的章節，因為其餘章節自成體系，對於理論部分沒有過多的依賴。
我仍然清晰地記得，兩年以前華章公司的姚蕾編輯多次找到我，希望我能撰寫一本關於分散式機器學習的圖書。一方面被姚蕾的誠意打動，另一方面也考慮到這樣一本書對於在校研究生和人工智慧從業者可能有所幫助，我最終欣然應允。然而，平時工作過於繁忙，真正可以用來寫書的時間非常有限，所以一晃就是兩年的時光本書才與讀者見面，內心十分慚愧。
回顧這兩年的寫作過程，有很多人需要感謝。首先，我要感謝本書的聯合作者：陳薇博士負責書中與最佳化算法和學習理論有關的內容，王太峰和高飛則主要負責通信機制、聚合模式和分散式機器學習系統等方面的內容。沒有他們夜以繼日的努力，本書無法成文。在寫作過程中，本書的各位作者得到了家人的大力支持。寫書之路實屬不易，如果沒有她（他）們的默默奉獻，作者們很難集中精力，攻克這個艱巨的任務。其次，我要感謝諸多為本書的寫作做出過重要貢獻的人：我在中國科學技術大學的博士生鄭書新花費了大量的精力和時間幫助我們整理了全書的參考文獻；北京大學的孟琪同學則幫助我們對全書做了細緻的校驗；華章公司的編輯姚蕾和遲振春對我們的書稿提出了很多寶貴的意見；普林斯頓大學教授、中國科學院院士鄂維南博士，以及南京大學教授周志華博士分別為本書題寫了推薦序。正是因為這么多幕後英雄的奉獻，本書才得以順利面世。最後，我還要感謝微軟亞洲研究院院長洪小文博士，他的大力支持使得我們在分散式機器學習這個領域做出了很多高質量的研究工作，也使得我們有機會把這些成果記錄下來，編纂成書，與更多的同行分享。
慚愧的是，即便耗時兩載，即便集合了多人的智慧和努力，本書的寫作仍然略顯倉促。加之分散式機器學習這個領域飛速發展，本書成稿之時，又有很多新的研究成果發表，難以周全覆蓋。再則，本書的作者才疏學淺，書中難免有疏漏、錯誤之處，還望讀者海涵，不吝告知，日後加以勘誤，不勝感激。
劉鐵岩
於北京中關村
2018年6月
目錄
序言一
序言二
前 言
作者介紹
第1章 緒論/ 1
1.1 人工智慧及其飛速發展/ 2
1.2 大規模、分散式機器學習/ 4
1.3 本書的安排/ 6
參考文獻/ 7
第2章 機器學習基礎/ 9
2.1 機器學習的基本概念/ 10
2.2 機器學習的基本流程/ 13
2.3 常用的損失函式/ 16
2.3.1 Hinge損失函式/ 16
2.3.2 指數損失函式/ 16
2.3.3 交叉熵損失函式/ 17
2.4 常用的機器學習模型/ 18
2.4.1 線性模型/ 18
2.4.2 核方法與支持向量機/ 18
2.4.3 決策樹與Boosting/ 21
2.4.4 神經網路/ 23
2.5 常用的最佳化方法/ 32
2.6 機器學習理論/ 33
2.6.1 機器學習算法的泛化誤差/ 34
2.6.2 泛化誤差的分解/ 34
2.6.3 基於容度的估計誤差的上界/ 35
2.7 總結/ 36
參考文獻/ 36
第3章 分散式機器學習框架/ 41
3.1 大數據與大模型的挑戰/ 42
3.2 分散式機器學習的基本流程/ 44
3.3 數據與模型劃分模組/ 46
3.4 單機最佳化模組/ 48
3.5 通信模組/ 48
3.5.1 通信的內容/ 48
3.5.2 通信的拓撲結構/ 49
3.5.3 通信的步調/ 51
3.5.4 通信的頻率/ 52
3.6 數據與模型聚合模組/ 53
3.7 分散式機器學習理論/ 54
3.8 分散式機器學習系統/ 55
3.9 總結/ 56
參考文獻/ 57
第4章 單機最佳化之確定性算法/ 61
4.1 基本概述/ 62
4.1.1 機器學習的最佳化框架/ 62
4.1.2 最佳化算法的分類和發展歷史/ 65
4.2 一階確定性算法/ 67
4.2.1 梯度下降法/ 67
4.2.2 投影次梯度下降法/ 69
4.2.3 近端梯度下降法/ 70
4.2.4 Frank-Wolfe算法/ 71
4.2.5 Nesterov加速法/ 72
4.2.6 坐標下降法/ 75
4.3 二階確定性算法/ 75
4.3.1 牛頓法/ 76
4.3.2 擬牛頓法/ 77
4.4 對偶方法/ 78
4.5 總結/ 81
參考文獻/ 8
第5章 單機最佳化之隨機算法/ 85
5.1 基本隨機最佳化算法/ 86
5.1.1 隨機梯度下降法/ 86
5.1.2 隨機坐標下降法/ 88
5.1.3 隨機擬牛頓法/ 91
5.1.4 隨機對偶坐標上升法/ 93
5.1.5 小結/ 95
5.2 隨機最佳化算法的改進/ 96
5.2.1 方差縮減方法/ 96
5.2.2 算法組合方法/ 100
5.3 非凸隨機最佳化算法/ 101
5.3.1 Ada系列算法/ 102
5.3.2 非凸理論分析/ 104
5.3.3 逃離鞍點問題/ 106
5.3.4 等級最佳化算法/ 107
5.4 總結/ 109
參考文獻/ 109
第6章 數據與模型並行/ 113
6.1 基本概述/ 114
6.2 計算並行模式/ 117
6.3 數據並行模式/ 119
6.3.1 數據樣本劃分/ 120
6.3.2 數據維度劃分/ 123
6.4 模型並行模式/ 123
6.4.1 線性模型/ 123
6.4.2 神經網路/ 127
6.5 總結/ 133
參考文獻/ 133
第7章 通信機制/ 135
7.1 基本概述/ 136
7.2 通信的內容/ 137
7.2.1 參數或參數的更新/ 137
7.2.2 計算的中間結果/ 137
7.2.3 討論/ 138
7.3 通信的拓撲結構/ 139
7.3.1 基於疊代式MapReduce/AllReduce的通信拓撲/ 140
7.3.2 基於參數伺服器的通信拓撲/ 142
7.3.3 基於數據流的通信拓撲/ 143
7.3.4 討論/ 145
7.4 通信的步調/ 145
7.4.1 同步通信/ 146
7.4.2 異步通信/ 147
7.4.3 同步和異步的平衡/ 148
7.4.4 討論/ 150
7.5 通信的頻率/ 150
7.5.1 時域濾波/ 150
7.5.2 空域濾波/ 153
7.5.3 討論/ 155
7.6 總結/ 156
參考文獻/ 156
第8章 數據與模型聚合/ 159
8.1 基本概述/ 160
8.2 基於模型加和的聚合方法/ 160
8.2.1 基於全部模型加和的聚合/ 160
8.2.2 基於部分模型加和的聚合/ 162
8.3 基於模型集成的聚合方法/ 167
8.3.1 基於輸出加和的聚合/ 168
8.3.2 基於投票的聚合/ 171
8.4 總結/ 174
參考文獻/ 174
第9章 分散式機器學習算法/ 177
9.1 基本概述/ 178
9.2 同步算法/ 179
9.2.1 同步SGD方法/ 179
9.2.2 模型平均方法及其改進/ 182
9.2.3 ADMM算法/ 183
9.2.4 彈性平均SGD算法/ 185
9.2.5 討論/ 186
9.3 異步算法/ 187
9.3.1 異步SGD/ 187
9.3.2 Hogwild!算法/ 189
9.3.3 Cyclades算法/ 190
9.3.4 帶延遲處理的異步算法/ 192
9.3.5 異步方法的進一步加速/ 199
9.3.6 討論/ 199
9.4 同步和異步的對比與融合/ 199
9.4.1 同步和異步算法的實驗對比/ 199
9.4.2 同步和異步的融合/ 201
9.5 模型並行算法/ 203
9.5.1 DistBelief/ 203
9.5.2 AlexNet/ 204
9.6 總結/ 205
參考文獻/ 205
第10章 分散式機器學習理論/ 209
10.1 基本概述/ 210
10.2 收斂性分析/ 210
10.2.1 最佳化目標和算法/ 211
10.2.2 數據和模型並行/ 213
10.2.3 同步和異步/ 215
10.3 加速比分析/ 217
10.3.1 從收斂速率到加速比/ 218
10.3.2 通信量的下界/ 219
10.4 泛化分析/ 221
10.4.1 最佳化的局限性/ 222
10.4.2 具有更好泛化能力的非凸最佳化算法/ 224
10.5 總結/ 226
參考文獻/ 226
第11章 分散式機器學習系統/ 229
11.1 基本概述/ 230
11.2 基於IMR的分散式機器學習系統/ 231
11.2.1 IMR和Spark/ 231
11.2.2 Spark MLlib/ 234
11.3 基於參數伺服器的分散式機器學習系統/ 236
11.3.1 參數伺服器/ 236
11.3.2 Multiverso參數伺服器/ 237
11.4 基於數據流的分散式機器學習系統/ 241
11.4.1 數據流/ 241
11.4.2 TensorFlow數據流系統/ 243
11.5 實戰比較/ 248
11.6 總結/ 252
參考文獻/ 252
第12章 結語/ 255
12.1 全書總結/ 256
12.2 未來展望/ 257
索引/ 260
