分布式机器学习:算法、理论与实践

全面展示分布式机器学习理论、方法与实践

微软亚洲研究院机器学习核心团队潜心力作

鄂维南院士、周志华教授倾心撰写推荐序

内容前沿全面，讨论系统深刻，全彩印刷

本书旨在全面介绍分布式机器学习的现状，深入分析其中的核心技术问题，并且讨论该领域未来的发展方向。

全书共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 会士
南京大学教授、计算机科学与技术系主任、人工智能学院院长

序言一

序言二

前 言

作者介绍

第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

近年来，人工智能取得了飞速的发展，实现了一个又一个技术突破。这些成功的幕后英雄是海量的训练数据、超大规模的机器学习模型以及分布式的训练系统。一系列有关分布式机器学习的研究工作，从并行模式、跨机通信到聚合机制，从算法设计、理论推导到系统构建，都在如火如荼地展开。人们不仅发表了大量的学术论文，也开发出一批实用性很强的分布式机器学习系统。本书的目的是向读者全面展示分布式机器学习的现状，深入分析其中的核心技术问题，并且讨论该领域未来发展的方向。本书既可以作为研究生从事分布式机器学习方向研究的参考文献，也可以作为人工智能从业者进行算法选择和系统设计的工具书。
全书共12章。第1章是绪论，向大家展示分布式机器学习这个领域的全景。第2章介绍机器学习的基础知识，其中涉及的基本概念、模型和理论，会为读者在后续章节中更好地理解分布式机器学习的各项技术奠定基础。第3章到第8章是本书的核心部分，向大家细致地讲解分布式机器学习的框架及其各个功能模块。其中第3章对整个分布式机器学习框架做综述，而第4章到第8章则针对其中的数据与模型划分模块、单机优化模块、通信模块、数据与模型聚合模块分别加以介绍，展示每个模块的不同选项并讨论其长处与短板。接下来的三章是对前面内容的总结与升华。其中第9章介绍由分布式机器学习框架中不同选项所组合出来的各式各样的分布式机器学习算法，第10章讨论这些算法的理论性质（例如收敛性），第11章则介绍几个主流的分布式机器学习系统（包括Spark MLlib、Multiverso参数服务器系统和TensorFlow数据流系统）。最后的第12章是全书的结语，在对全书内容进行简要总结之后，着重讨论分布式机器学习这个领域未来的发展方向。
有关本书的写作，因为涉及分布式机器学习的不同侧面，不同的章节对读者预备知识的要求有所不同。尤其是涉及优化算法和学习理论的部分，要求读者对于最优化理论和概率统计有一定的知识储备。不过，如果读者的目的只是熟悉主流的分布式机器学习框架和系统，则可以跳过这些相对艰深的章节，因为其余章节自成体系，对于理论部分没有过多的依赖。
我仍然清晰地记得，两年以前华章公司的姚蕾编辑多次找到我，希望我能撰写一本关于分布式机器学习的图书。一方面被姚蕾的诚意打动，另一方面也考虑到这样一本书对于在校研究生和人工智能从业者可能有所帮助，我最终欣然应允。然而，平时工作过于繁忙，真正可以用来写书的时间非常有限，所以一晃就是两年的时光，直至今日本书才与读者见面，内心十分惭愧。
回顾这两年的写作过程，有很多人需要感谢。首先，我要感谢本书的联合作者：陈薇博士负责书中与优化算法和学习理论有关的内容，王太峰和高飞则主要负责通信机制、聚合模式和分布式机器学习系统等方面的内容。没有他们夜以继日的努力，本书无法成文。在写作过程中，本书的各位作者得到了家人的大力支持。写书之路实属不易，如果没有她（他）们的默默奉献，作者们很难集中精力，攻克这个艰巨的任务。其次，我要感谢诸多为本书的写作做出过重要贡献的人：我在中国科学技术大学的博士生郑书新花费了大量的精力和时间帮助我们整理了全书的参考文献；北京大学的孟琪同学则帮助我们对全书做了细致的校验；华章公司的编辑姚蕾和迟振春对我们的书稿提出了很多宝贵的意见；普林斯顿大学教授、中国科学院院士鄂维南博士，以及南京大学教授周志华博士分别为本书题写了推荐序。正是因为这么多幕后英雄的奉献，本书才得以顺利面世。最后，我还要感谢微软亚洲研究院院长洪小文博士，他的大力支持使得我们在分布式机器学习这个领域做出了很多高质量的研究工作，也使得我们有机会把这些成果记录下来，编纂成书，与更多的同行分享。
惭愧的是，即便耗时两载，即便集合了多人的智慧和努力，本书的写作仍然略显仓促。加之分布式机器学习这个领域飞速发展，本书成稿之时，又有很多新的研究成果发表，难以周全覆盖。再则，本书的作者才疏学浅，书中难免有疏漏、错误之处，还望读者海涵，不吝告知，日后加以勘误，不胜感激。
刘铁岩
于北京中关村
2018年6月