数据与模型并行
利用计算机集群，使机器学习算法更好地从大数据中训练出性能优良的大模型是分布式机器学习的目标。为了实现这个目标，一般需要根据硬件资源与数据/模型规模的匹配情况，考虑到计算任务、训练数据和模型进行划分，分布式存储、分布式训练。
分布式机器学习可以分为计算并行模式、数据并行模式和模型并行模式。
- 分布式并行模式
- 数据并行模式
如果工作节点没有公共内存，只有容量受限的本地内存，而训练数据的规模很大，无法存储于本地内存，我么就需要对数据集进行划分，分配到各个工作节点上，然后工作节点依据各自分配的局部数据对模型进行训练，我们称此种并行模式为：“数据并行模式”
经典的数据样本划分方法有两种：
- 基于“随机采样”的方法
随机采样可以保证每台机器上的局部训练数据与原始训练数据是独立同分布的
但弊端是：1. 训练数据较大，实现全局采样的计算复杂度比较高；2. 如果随机采样的次数小于数据向本数目，可能有些训练样本一直未被选中，导致训练样本未被充分利用。 - 基于“置乱切分”的方法
该方法将训练数据进行随机置乱，然后按照工作节点的个数将打乱后的数据顺序划分为相应的小份，随后将这些小份数据分配到各个工作节点上。
随机切分方法相比于随机采样方法，虽然数据的分布与原始的数据分布略有偏差，但是其计算复杂度比全局随机采样要小很多，而且置乱切分能保留每一个样本，直观上对样本利用更充分。
-
模式并行模式
如果机器学习模型的规模比较大，无法存储于本地内存，则需要对模型进行划分。
对于线性模型、我们可以将对应于不同数据纬度的模型参数划分到不同的工作节点上。
对于高度非线性的神经网络，各个工作节点不能相对独立地完成对自己负责的参数训练和更新，必须依赖与其他工作节点的协作，那么，如何利用神经网络的结果特点和优化过程，以尽量小的通信代价实现对神经网络的模型并行？常用的针对神经网络的模型并行方法有：横向按层划分、纵向跨层划分和模型随机划分。
并行模式总结
计算并行模式
假设系统中的工作节点拥有共享内存（比如单机多线程环境），可以存储下数据和模型，并且每个工作节点对数据有完全地访问权限，对数据有读写权限。那么，在此类系统中实现分布式机器学习算法，对数据和模型不需要特殊处理，只需要把注意力集中在如何并行的执行相应的优化算法上。我们称这种并行模式为计算并行模式。
公式详见书中P119
数据并行模式
数据样本划分和数据维度划分是两种常见的数据划分方法。其中，对于样本划分方法，又有随机采样和（全局/局部）置乱切分等方法。总体来说，进行数据划分时要考虑以下两个因素。
一是数据量和数据维度与本地内存的相对大小，以此判断数据按照样本划分和维度划分后能否合适地存储到本地内存
二是优化方法的特点。通常，样本划分更适合于随机抽取样本的优化方法（比如随机梯度下降法），维度划分更适用于随机抽取维度的优化方法（比如随机坐标下降法）。
数据样本划分
那么为什么数据划分是合理的？因为在于机器学习中的目标函数，也就是训练数据集的经验风险函数，关于样本是可分的。因为经验风险函数是所有训练样本对应的损失函数取值的总和，所以如果将训练样本划分成多个数据子集，计算各个子集上的局部梯度值，再将局部梯度函数，任然可以得到整个经验风险函数的梯度值。
置乱切分相比于随机采样有以下好处：
- 置乱切分的复杂度比较低。所以然一次置乱操作的调用无法实现对数据的完全随机打乱，但是可以证明调用若干次置乱操作后，其置乱的效果已经可以很好地逼近完全随机了。置乱切分的复杂度为
,而n次有放回抽样的复杂度为
。
- 置乱切分的数据信息量比较大。置乱切分相比于无放回抽样，每个样本都会出现在某个工作节点，每个工作节点的本地数据没有重置，因为用于训练的数据的信息量一般会更大。
当划分到本地的训练数据被优化算法依照顺序使用完一遍之后，有两种对数据进行再处理的方法：再次进行全局置乱切分和仅对本地数据进行局部置乱。为引用方便，我们分别称其为：“全局置乱切分”和“局部置乱切分”。
· 带有置乱切分的随机梯度下降法相比带有随机采样的随机梯度下降法，收敛速率要慢一些，这是因为置乱切分后样本不在是独立的，影响了收敛速率。
· 带有局部置乱切分的随机梯度下降法的收敛速率比带有全局置乱切分的随机梯度下降法的收敛速率慢。原因在于，局部置乱切分中，数据第一次切分之后，将不再进行全局置乱，局部数据的差异性始终保持，相比全局置乱的情形对于数据独立同分布假设的违背更加严重。
数据维度划分
- 决策树方法。决策树算法中，对维度的处理相对独立可分，将数据按维度划分后，各个工作节点可以独立计算局部维度子集中具有最优信息增益的维度，然后进行交互汇总，
2.线性模型。对于线性模型而言，数据参数与数据维度量一一对应的，因此数据维度划分常常与模型并行相互结合。
模型并行模式
如果机器学习任务中所涉及的模型规模很大，不能存储到工作节点的本地内存，就需要对模型进行划分，然后各个工作节点负责本地局部模型的参数更新。对具有变量可分性的线性模型和变量相关性很强的非线性模型（比如神经网络），模型并行的方式有所不同。
线性模型
把模型和数据按维度均等均分，分配到不同的工作节点，在每个工作节点使用坐标下降法进行优化。
对于线性模型而言，目标函数针对各个变量是可分的，也就是说某个维度的参数更新/梯度只依赖一些与目标函数值有关的全局变量，而不依赖与其他维度的参数取值。于是，为了实现本地参数的更新，我们只需要对这些全局变量进行通信，不需要对其他节点的模型参数进行通信。这是可分性模型进行模型并行的基本原理
神经网络
神经网络由于具有很强的非线性，参数之间的依赖关系比线性模型严重的很多，不能进行简单的划分，也无法使用类似线性模型那样的技巧通过一个全局中间变量实现高效的模型并行，但是事务总是有两面性，神经网络的层次化借故偶也为模型并行带来了一定的便利性，比如我们可以横向按层划分、纵向跨层划分和利用神经网络参数的冗余性进行随机划分。不同划分模式对应的通信内容和通信量是不相同的。
1.横向按层划分
如果神经网络很深，一个自然并且易于实现的模型并行方法就是整个神经网络横向划分为K个部分，每个工作节点承担一层或者几层的计算任务。如果计算所需要的信息本工作节点没有，则向相应的其他工作节点请求相关的信息。模型横向划分的时候，通常我们会结合各层的节点数目，尽可能使得各个工作节点的计算量平衡。
横向按层划分
2.纵向跨层划分
神经网络除了深度还有宽度（而且通常情况下宽度会大于深度），因此除了上一小节介绍的横向按层划分外，自然地可以纵向跨层划分网络，也就是将每一层的隐含节点分配给不同的工作节点。工作节点存储并更新这些纵向子网络。在前向和后传过程中，如果需要子模型以外的激活函数和误差传播值，向对应的工作节点请求相关信息进行通信。
纵向按层划分
横向按层划分和纵向跨层划分这两种方法，在存储量和存储形式、传输量以及传输等待时间等方面都有不同。实际应用中，可以根据具体的网络结构来选取合适地方法。一般而言，如果每层的神经元数目不多而层数较多，可以考虑横向按层划分，反之，如果每层的神经元数目很多而层数较少，则应该考虑纵向跨层划分。如果学习任务中的神经网络层数和每层的神经元数目都很大，则可能需要把横向按层划分和纵向跨层结合使用。
神经网络混合划分
-
模型随机并行
由于纵向和横向划分的通信代价都比较大，最近研究人员有提出了针对大规模神经网络的随机切分。
其基本思路是:人们发现神经网络具有一定的冗余性，可以找到一个规模小很多的子网络（称为骨架网络），其效果与原网络差不多。于是，我们可以首先按照其某种准则，在原网络中选出骨架网络，作为公用子网络存储于每个工作节点，除骨架网络之外，每个工作节点还会随机选取一些其他节点存储，以探索（exploration）骨架网络之外的信息。骨架网络周期性的依据新的网络重新选取，而用于探索的节点也会每次随机选取。
神经网络随机划分示意图
实验表明：1，模型随机并行的速度比纵向按层划分快，尤其对于复杂任务下的大模型更是如此；2.选取适当的骨架比列会使并行速度进一步提高。
