机器学习分布式计算概览_带有延迟补偿的异步并行 adam 算法

分布式训练的优势在于做并行化，按照并行方式，模型训练可以分为数据并行和模型并行：
• 模型并行：对不同的机器，数据输入相同，运行网络模型的不同部分。
• 数据并行：对不同机器，数据输入不同，运行的网络模型相同，然后将所有机器的计算结果按照某种方式合并。
数据并行，各个部分相互独立，集群扩展性更好，是目前的主流方式

数据并行时，每台机器上都会有一份模型梯度，因此需要将集群中多台机器的梯度累加求均值（这里是有问题的），并用得到全局Average gradients 更新权重。这里就涉及两个问题:
• 什么时候进行多台机器的梯度累加？
• 如何高效的在多台机器间做梯度累加？

• 问题一：什么时候进行多台机器的梯度累加？

  其实本质上是梯度更新方式，目前存在两种：
  同步更新：所有worker都在同一个时间点做梯度更新，也就是等待所有worker的梯度都计算完毕后再统一做更新，因此计算最慢的机器会成为更新效率的瓶颈
  
  异步更新： 只要worker计算完梯度并发起更新请求时，就会立即对参数发起更新，而不等待其他worker。但是可能会存在收敛效率不佳，因为一些速度慢的节点总会提供过时的梯度方向，导致梯度方向有偏差。对于落后于当前迭代的梯度，常见做法就是直接丢掉。
  

• 针对异步机制中的梯度延迟问题，我们为深度学习设计了“带有延迟补偿的异步算法”DC-ASGD算法：

  随机梯度下降法（SGD）是目前最流行的深度学习的优化算法之一，更新公式为：
  
  其中，wt为当前模型，(xt, yt)为随机抽取的数据，g(wt; xt, yt)为(xt, yt)所对应的经验损失函数关于当前模型wt的梯度，η为步长/学习率
  异步随机梯度下降法（Asynchronous SGD）在每轮迭代中，每个工作节点在计算出随机梯度后直接更新到模型上，不再等待所有的计算节点完成梯度计算。因此，异步随机梯度下降法的迭代速度较快，也被广泛应用到深度神经网络的训练中。然而，Async SGD虽然快，但是用以更新模型的梯度是有延迟的，会对算法的精度带来影响。什么是“延迟梯度”？我们来看下图
  
  在Async SGD运行过程中，某个工作节点Worker(m)在第t次迭代开始时获取到模型的最新参数wt和数据(xt, yt)，计算出相应的随机梯度gt，并将其返回并更新到全局模型w上。由于计算梯度需要一定的时间，当这个工作节点传回随机梯度gt时，模型wt已经被其他工作节点更新了τ轮，变为了wt+τ。也就是说，Async SGD的更新公式为：
  
  对比公式1，公式2中对模型wt+τ上更新时所使用的随机梯度是g(wt; xt, yt)，相比SGD中应该使用的随机梯度g(wt+τ; xt+τ, yt+τ)产生了τ步的延迟。因而，我们称Async SGD中随机梯度为“延迟梯度”。
  延迟梯度所带来的最大问题是，由于每次用以更新模型的梯度并非是正确的梯度（请注意g(wt; xt, yt) ≠ g(wt+τ; xt+τ, yt+τ)），所以导致Async SGD会损伤模型的准确率，并且这种现象随着机器数量的增加会越来越严重。
  那么，如何能让异步随机梯度下降法在保持训练速度的同时，获得更高的精度呢？为了研究正确梯度g(wt+τ)和延迟梯度g(wt)之间的关系，我们将g(wt+τ)在wt处进行泰勒展开：
  
  其中，∇g(wt)为梯度的梯度，也就是损失函数的Hessian矩阵，H(g(wt))为梯度的Hessian矩阵。由于余项拥有无穷项，所以无法被准确计算。因此，我们选择用上述公式中的一阶项进行延迟补偿
  
  计算和存储Hessian矩阵∇g(wt)成为了一件几乎无法完成的事情。因此，寻找Hessian矩阵的一个良好近似是能否补偿梯度延迟的关键。根据费舍尔信息矩阵的定义，梯度的外积矩阵
  
  是Hessian矩阵的一个渐近无偏估计，因此我们选择用G(wt)来近似估计Hessian矩阵。
  在神经网络模型中用Hessian矩阵的对角元来近似Hessian矩阵，于是我们采用diag(G(wt))作为Hessian矩阵的近似。为了进一步降低近似的方差，我们使用一个(0,1]之间参数λ来对偏差和方差进行调节。综上，我们设计了如下带有延迟补偿的异步随机梯度下降法（DC-ASGD）：
  

• 问题二：如何高效的在多台机器间做梯度累加？

  • Parameter server 方式

  首先单独分出一台或者多台机器做梯度累加，一般称为Parameter Server(简称PS)。PS会收集所有worker的梯度，做完累加求均值后，再将结果broadcast到worker上
  

  • AllReduce 方式
    所谓All reduce，其目标是高效地将不同机器中的数据归并（reduce）之后再把结果分发给各个机器。其实All Reduce算法是从高性能计算领域引入到深度学习模型训练中的，这类算法也被称为集合通信（Collective Communication ）算法。AllReduce有很多种不同的实现，目前比较高效是实现之一就是Ring All reduce，下面我们以3台机器为例给大家介绍下。
    • 将3个worker分布在一个环上，并且把每个worker的数据分成3份
    • 第k个worker会把第k份数据发给下一个worker，同时从前一个worker收到第k-1份数据
    • worker会把收到的第k-1份数据和自己的第k-1份数据整合，再将整合的数据发送给下一个worker
    • 以此循环3次之后，每一个worker都会包含最终整合结果的一份
    • 将每个worker中已经拿到的部分全局数据发送给下一个worker。Worker在收到数据之后更新自身数据对应的部分即可
    

• 在finish阶段当某个worker拿到所worker的梯度信息是否可以做累加求平均即可？

如果损失函数关于模型参数是凸的，以下不等式成立：

其中，K为计算节点个数，wk是局部模型，为参数平均后的模型，(x, y)为任意样本数据。

根据凸函数性质：左端是平均模型所对应的损失函数，右端是各个局部模型的损失函数值的平均值。可见，凸问题中参数平均可以保持模型的性能。但是，对于非凸的神经网络模型，以上不等式将不再成立，因而平均模型的性能不再具有保证
我们提出用模型集成替代模型平均，作为分布式深度学习中的模型聚合方式。虽然神经网络的损失函数关于模型参数是非凸的，但是关于模型的输出一般是凸的（比如，交叉熵）。这时，利用凸性可以得到如下不等式：

其中，不等式左侧是集成（ensemble）模型的损失函数取值。只要保证loss function是凸的，集成模型可以保持性能。
一种同时基于模型集成和模型压缩的模型聚合方法, 即集成-压缩（ensemble-compression）方法
算法具体分为三个步骤：
• 各个计算节点依照本地优化算法训练和局部数据训练出局部模型；
• 计算节点之间相互通信局部模型得到集成模型，并对（一部分）局部数据标注上集成模型对它们的输出值；
• 利用模型压缩技术（比如知识蒸馏），结合数据的再标注信息，在每个工作节点上分别进行模型压缩，获得与局部模型大小相同的新模型作为最终的聚合模型。为了进一步节省计算量，可以将蒸馏的过程和本地模型训练的过程结合在一起。

参考链接：https://zhuanlan.zhihu.com/p/192811562
参考链接：https://zhuanlan.zhihu.com/p/39701269