Fork me on GitHub

《分布式机器学习算法、理论与实践_刘铁岩》读书记录

注:此书偏公式理论,本文仅对部分章节进行记录,标*表示跳过不读,文中使用 P54,表示《分布式机器学习算法、理论与实践_刘铁岩》中对应页码 54 页有详细解释。

  1. 绪论
  2. 机器学习基础*
  3. 分布式机器学习框架
  4. 单机优化之确定性算法*
  5. 单机优化之随机算法*
  6. 数据与模型并行
  7. 通信机制
  8. 数据与模型聚合
  9. 分布式机器学习算法
  10. 分布式机器学习理论
  11. 分布式机器学习系统
  12. 结语

1. why 分布式机器学习?

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

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

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

  1. 允许不同实现,但需要(跟单机)基本一致的模型和规律。

  2. 为了泛化,允许一定噪音。

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

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

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

3.1. 数据与模型划分模块

  1. 数据划分。有随机采样、置乱切分(训练时可以定期打乱局部数据)这两种常用做法。还可以在特征维度的切分,P47 。

  2. 模型划分。一个机器学习的模型对应多个子模型,一个子模型对应多个模型参数,每个子模型放在一个 worker 上进行计算。

    1. 模型划分还跟模型的结构特点有关。线性模型可以按照特征维度进行划分;深层 NN 划分时,可以考虑逐层横向划分(几口清晰,但并行度可能不高)或者跨层纵向划分(子模型间依赖关系复杂、通信代价高)。

3.2. 单机优化模块

  • 传统的单机机器学习任务。

  • 训练数据、计算经验风险、利用优化算法通过最小化经验风险来学习模型的参数。

  • 在分布式环境下,单机算法的收敛、泛化能力都可能发生变化。

3.3. 通信模块

  1. 通信内容:子模型或者子模型的更新(如梯度)、甚至重要样本(如支持向量)、计算的中间结果等。

  2. 拓扑结构:基于迭代式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 为例:
  1. ps 拿到多个局部模型后,可以进行 ①模型参数的简单平均;②做一致性优化(如 ADMM、BMUF); ③模型集成。但各有利弊。模型参数的简单平均和一致性优化:不适合非凸函数(例如深度学习)。模型集成会增加模型的规模,严重时导致模型爆炸,解决办法:模型集成+压缩;考虑子模型的延迟生成,模型集成可能需要异步聚合。

  2. 当 ps 将全局模型推送到 worker 上时,worker 可以无条件信任全局模型,也可以部分信任并概率更新本地模型。

  3. 典型分布式机器学习系统的比较,P56

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