1. why 分布式机器学习？

业界的大规模机器学习任务往往涉及如何充分地利用“大数据 ” 、如何有效地训练 “大模型” 。使用价格昂贵的高性能设备，例如TB级内存的计算服务器未尝不可，但硬件能力的增长速度显然比不上机器学习所面对数据的增长速度，因此目前业界更主流的解决方案是分布式机器学习。

分布式机器学习并非分布式处理技术与机器学习的简单结合。一方面，它必须考虑机器学习模型构成与算法流程本身的特点，否则分布式处理的结果可能失之毫厘、谬以千里 ; 另一方面，机器学习内含的算法随机性、参数冗余性等，又会带来一般分布式处理过程所不具备的、宜于专门利用的便利。

2. 分布式系统的鲁棒性：

允许不同实现，但需要（跟单机）基本一致的模型和规律。
为了泛化，允许一定噪音。

3. 分布式器学基本流程 P45：

分布式机器学习的三种情形：计算量太大、训练数据太多、模型规模太大。

计算量太大：多线程、多机计算。
训练数据太多（key problem）：划分数据，分配多工作结点训练。
- 拿到子模型，然后按照一定的规律和其他工作结点进行通信，将子模型及参数进行更新等，最后整合得到全局学习模型。
模型规模太大：划分模型，分配多个工作结点进行训练。
- 此处拿到的子模型间 maybe 相互依赖。
- 对通信要求高。
- 四大模块：数据与模型划分、单机优化模块、通信模块、数据与模型聚合模块。
- 因为四大模型存在不同的组合方法，产生出了多种多样的分布式机器学习算法（每个模块都有各自的设计准则，可按需选取并组合）。

3.1. 数据与模型划分模块

数据划分。有随机采样、置乱切分（训练时可以定期打乱局部数据）这两种常用做法。还可以在特征维度的切分，P47 。
模型划分。一个机器学习的模型对应多个子模型，一个子模型对应多个模型参数，每个子模型放在一个 worker 上进行计算。

3.2. 单机优化模块

传统的单机机器学习任务。
训练数据、计算经验风险、利用优化算法通过最小化经验风险来学习模型的参数。
在分布式环境下，单机算法的收敛、泛化能力都可能发生变化。

3.3. 通信模块

通信内容：子模型或者子模型的更新（如梯度）、甚至重要样本（如支持向量）、计算的中间结果等。
拓扑结构：基于迭代式MapReduce的通信拓扑、基于参数服务器的通信拓扑、基于数据流的通信拓扑。
1. （早期做法）基于迭代式MapReduce的通信拓扑：如 Spark MLlib。在继承 MR 基础上增加了迭代式，具备了内存运行、持久化等优点。但仍需要完成全部 Mapper 后，进入 Reduce 过程中。单机的优化算法需要较大改动后才能完全符合 Map 和 Reduce 的编程接口。
2. 基于参数服务器（数据并行）的通信拓扑：如 CMU 的 Parameter Server，微软的 Multiverso。把工作结点和模型存储结点在逻辑上区分开来。（lee 理解：一个做计算，一个保存模型参数）P50。worker 只与 ps 交互，各个 worker 之间不需要交互，因此快 worker 不需要等待慢 worker。全局参数拆分到多个 ps 上，可以平衡负载提高通信效率，而且对稀疏模型访问的情况比较友好（达到模型并行的效果）。
3. 基于数据流（模型并行）的通信拓扑：如 TensorFlow。数据流，也就是 dag。每个节点有两个通信通道：控制信息流和计算数据流。
  1. 控制信息流：input[data、参数],calculate,output[interval data, 参数update]
  2. 控制信息流：worker 应该接受什么 data、data 是否完整，计算是否完成，是否可以开始下游等。lee理解[一些配置信息，以及状态维持等]。
  3. 通信步调：同步 or 异步？
    1. 同步：应用于早期，逻辑清晰，但上千结点同时工作情况下等待时间过长。
      1. 基于同步的通信算法：例BSP 的随机下降算法、模型平均法、ADMM 法、弹性平均随机梯度下降法等。
    2. 异步：每个 worker 在完成本地一定量训练后，不等待其他 worker，而将自己的 output 推送到 ps 上，随即继续本地的模型训练 P52。
      1. 基于异步的通信算法：例异步随机梯度下降法ASGD、HogWild！、Cyclades 等。
      2. 优化：对延迟不敏感的算法：AdaptiveRevision、AdaDelay; 补偿延迟算法，DC-ASGD。
      3. 分为有锁、无锁两种。是指局部模型并入全局模型时是否加锁。
    3. 半同步：例SSP。当检测到延迟过大时，会要求最快的结点停下工作等待较慢的结点。
    4. 混合同步：工作结点分组，组内同步通信，组间异步通信。

3.4. 数据与模型聚合模块

其实就是将来自不同 worker 的data、模型进行聚合的过程。以下以 ps 为例：

ps 拿到多个局部模型后，可以进行 ①模型参数的简单平均；②做一致性优化（如 ADMM、BMUF）； ③模型集成。但各有利弊。模型参数的简单平均和一致性优化：不适合非凸函数（例如深度学习）。模型集成会增加模型的规模，严重时导致模型爆炸，解决办法：模型集成+压缩；考虑子模型的延迟生成，模型集成可能需要异步聚合。
当 ps 将全局模型推送到 worker 上时，worker 可以无条件信任全局模型，也可以部分信任并概率更新本地模型。
典型分布式机器学习系统的比较，P56

	MapReduce	Multiverso	TensorFlow
通信拓扑	迭代式 MR	ps	dag
灵活性	低，需要遵从 Map+Reduce 步骤	高，它只是提供了全局存储的服务器和访问全局存储的 API，对分布式程序自身执行的流程以及具体的运算都没有作要求	中等，任务需要描述成 dag
运行效率	低，同步逻辑	较高，异步	较高，异步
学习任务	浅层任务，如 LR 等	无限制，但需要用户自己实现器学算法	提供一些算子和优化器，用户可自由搭建类深度学习的模型等
用户使用	较多现成算子	生态系统较薄弱	较多现成算子

4.数据和模型切分类型

计算并行模式
- data 和 model 都在同一块内存中，所有 worker 结点共享，可以并行计算。如单机多线程环境。
数据并行模式
- 训练数据量很大，但本地内存容量受限，所以要切分数据。
- 数据会被分配到各个 worker 上，worker 依据局部数据训练模型。
模型并行模式
- 模型规模比较大，但本地内存容量受限，所以要切分模型。
- 模型切分跟模型的结构特点有关。线性模型可以按照特征维度进行划分；深层 NN 划分时，可以考虑逐层横向划分（接口清晰，但并行度可能不高）或者跨层纵向划分（子模型间依赖关系复杂、通信代价高）。

#5.通信机制

分布式机器学习的通信特点：通信频率高、通信数据量大，但数值优化算法的容错性较好。
通信的内容：参数(或参数的更新)、计算的中间结果。
1. 参数(或参数的更新)：基于数据并行的机器学习（不同 worker 用的同一份 model，参数的重叠度高，所以采用参数进行通信）。稀疏更新，而且随着模型趋于收敛，参数的更新会越来越少，相应通信量会降低。
2. 计算的中间结果：基于模型并行的机器学习（不同 worker 的 model 不同，参数重叠度低，所以通信传递的不是参数，而是相互依赖的中间计算结果）。
通信的拓扑：参考上文第 3 节内容
- 发展历史：>通信拓扑结构的演化与分布式机器学习的发展历史有关。早期，当人们用于训练模型的数据量还不够大，预测模型还不够复杂时，分布式机器学习常常利用已有的分布式计算框架来实现通信，如消息通信接口( MPI)或者 MapReduce 计算框架。这类通用的
  计算框架，有利于快速实现分布式机器学习任务，但也有本身的局限性，例如，使用MPI 的方式，各个节点之间仅支持同步计算。随着数据量增大，模型变得越来越复杂，人们设计了参数服务器这样的分布式机器学习系统。通过采用二部图的网络拓扑结构,参数服务器可以支持基于异步通信的并行训练。后来，随着深度学习的普及，机器学习系统将计算和通信统一抽象为一个数据图模型，通信可以在任意两个相连的图节点之间产生。