基于大数据的分布式机器学习策略与原理研究

工程2（2016）179研究iCity大数据-评论基于大数据的分布式机器学习策略与原理Eric P. Xing*，Qirong Ho，Pengtao Xie，Dai Wei计算机科学学院，卡内基梅隆大学，匹兹堡，PA 15213，美国ARt i clEINf oA b s tRAC t文章历史记录：2015年12月29日收到2016年5月1日修订2016年5月23日接受2016年6月30日在线发布保留字：机器学习人工智能大数据大模型分布式系统原理理论数据并行模型并行大数据的兴起导致了对机器学习（ML）系统的新需求，以学习具有数百万到数十亿参数的复杂模型，这些模型承诺有足够的能力来消化海量数据集并提供强大的预测分析（例如高维潜在特征，中间表示和决策函数）。为了在这样的规模上运行ML算法，在具有数万台机器的分布式集群上，通常需要大量的工程工作-人们可能会问这样的工程是否真正属于ML研究的领域。考虑到这些原则和策略涵盖了从应用到工程，再到大型ML系统和架构的理论研究和开发的连续统一体，其目标是了解如何使它们高效，普遍适用，并得到融合和扩展保证的支持。它们涉及传统上在ML研究中很少受到关注的四个关键问题：ML程序如何在集群中分布？ML计算如何与机器间通信连接？如何进行这种沟通？机器之间应该进行哪些通信？通过揭示机器学习程序特有的、但在传统计算机程序中通常看不到的基本统计和算法特征，并通过剖析成功案例来揭示我们如何利用这些原则来设计和开发高性能分布式机器学习软件以及通用机器学习框架，我们为机器学习研究人员和从业者提供了进一步塑造和扩大机器学习与系统之间区域的机会。.© 2016 The Bottoms.由爱思唯尔有限公司代表中国工程院和高等教育出版社有限公司出版这是CCBY-NC-ND下的开放获取文章许可证（http：//creati v ecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍机器学习（ML）已成为从原始数据中提取结构化信息和知识的主要机制，将其转化为各种应用的自动预测和可操作假设，例如：分析社交网络[1];推理客户行为[2];解释文本，图像和视频[3];识别疾病和治疗路径[4];驾驶车辆而无需人类[5];以及跟踪网络安全的异常活动[6]等。大多数ML应用程序都由数量适中的开发良好的ML方法，每一种方法都体现了从模型设计到算法创新，甚至到软件实现的完善的一系列技术元素，并且吸引了来自研究和开发社区的不断增长的新贡献。这种方法的现代示例包括图形模型[7-9]、正则化贝叶斯模型[10-12]、非参数贝叶斯模型[13，14]、稀疏结构模型[15，16]、大边缘方法[17，18]、深度学习[19，20]、矩阵分解[21，22]、稀疏编码[23，24]和潜在空间建模[1，25]。一个常见的ML实践，确保医疗合理性和结果的再现性是为从业者，* 通讯作者。电子邮件地址：epxing@cs.cmu.eduhttp://dx.doi.org/10.1016/J.ENG.2016.02.0082095-8099/© 2016 THE COVERORS.由爱思唯尔有限公司代表中国工程院和高等教育出版社有限公司出版。这是CC BY-NC-ND许可证下的开放获取文章（http：//creati v ecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect工程杂志主页：www.elsevier.com/locate/eng180E.P. Xing等/工程2（2016）179研究人员为特定ML方法的特定应用实例编写ML程序（使用任何通用高级编程语言）（例如，经由诸如卷积神经网络的深度学习模型对图像进行语义解释理想情况下，该程序有望在各种硬件和云基础设施上快速准确地执行：笔记本电脑、服务器机器、图形处理单元（GPU）、云计算和虚拟机、分布式网络存储、以太网和Infiniband网络，仅举几例。因此，程序是硬件不可知的，但ML显式的（即，当在数据上训练时遵循相同的数学原理并且不管硬件选择如何都获得相同的结果）。随着感官、数字存储和互联网传统的ML研究和开发在模型、算法和理论创新方面表现出色，但现在受到大数据收集日益普及的挑战，例如每分钟有数百小时的视频上传到视频共享网站，或超过十亿用户的社交网络上有PB级的社交媒体。大数据的兴起也伴随着对具有数十亿到数万亿参数的更高维和更复杂的ML模型的需求不断增加，以便支持不断增加的数据复杂性，或者获得更高的预测准确性（例如，用于更好的客户服务和医疗诊断）并支持更智能的任务（例如，无人驾驶车辆和视频数据的语义解释）[26，27]。在如此大的数据上训练如此大的ML模型超出了单个机器的存储和计算能力这一差距激发了越来越多的分布式机器学习工作，其中机器学习程序在研究集群、数据中心和云提供商之间执行，拥有数十到数千台机器。给定P台机器而不是一台机器，人们会期望分布式ML程序完成所需时间的近P倍加速，从某种意义上说，获得与单台机器产生的数学等效或可比的解决方案;然而，报告的加速往往远远低于这个标志。例如，即使是最近最先进的主题模型实现[28]（一种流行的文本分析方法）也无法在4倍机器上实现2倍加速，因为实现中存在数学错误（如参考文献[25]所示），而Spark等MapReduce系统上的深度学习尚未在10倍机器上实现5倍加速[29]。因此，解决这种可扩展性挑战是分布式ML研究的主要目标，以降低运行大型ML应用程序的资本和运营成本鉴于大多数（如果不是全部）主要ML算法的迭代收敛性质，为当代大规模应用提供动力，乍一看，人们可能会自然地确定两种可能的可扩展性途径：通过迭代次数测量的更快收敛（在ML社区中也称为收敛率），以及由系统执行迭代的实际速度（也称为系统社区中的吞吐量）测量的更快的每次迭代时间。事实上，许多分布式机器学习研究人员目前的主要关注点是算法正确性以及在广泛的机器学习方法中更快的收敛速度[30，31]。然而，由于对系统的理想化假设，许多来自这一研究领域的“加速”算法很难零同步成本），或者假设所有机器都以相同的速率执行算法（这意味着没有后台任务，只有集群的单个用户，这是不切实际的期望用于由许多用户共享的真实世界研究和生产集群）。另一方面，系统研究人员专注于高迭代吞吐量（每秒更多的迭代）和故障恢复保证，但可能会选择假设ML算法将在非理想执行模型下正确工作（例如完全异步执行），或者它可以在给定的抽象下轻松重写（例如MapReduce或Vertex Programming）[32-34]。在机器学习和系统研究中，来自另一方的问题可能被过度简化，这反过来可能会掩盖降低分布式机器学习资本成本的新机会。在本文中，我们提出了一种结合ML中心和系统中心思想的策略，其中ML算法（数学属性）和系统硬件（物理属性）的细微差别被结合在一起，以允许来自两端的见解和设计协同工作并相互放大。现有的许多通用大数据软件平台，表单在ML应用程序的正确性、执行速度和易编程性例如，Hadoop和Spark[34]等Hadoop系统构建在类似MapReduce的抽象[32]上，并提供易于使用的编程接口，但对ML属性的关注较少，例如容错，细粒度的计算调度和通信，以加速ML程序。因此，它们提供正确的ML程序执行和简单的编程，但比ML专用平台慢[35，36]。这种（相对）速度的缺乏可以部分归因于Hadoop和Spark中使用的批量同步并行（BSP）同步模型，其中分配给一组任务的机器必须在屏障处等待最慢的机器完成，然后才能继续下一组任务（例如，所有映射器必须在还原器开始之前完成）[37]。其他例子包括以图形为中心的平台，如GraphLab和Pregel，它们依赖于基于图形的然而，ML程序通常不被认为是顶点程序（相反，它们在数学上被公式化为迭代收敛的不动点方程），并且将它们重写为顶点程序需要付出不小的努力。在少数情况下，图形抽象可能会导致不正确的执行或次优的执行速度[38，39]。最近的记录是参数服务器范式[28，36，37，40，41]，它提供了一个考虑到为应用程序特定实例编写ML程序的常见ML实践，ML从业者的可用软件平台可以提供两种实用程序：①一组准备运行的ML主力实现-例如随机邻近下降算法[42，43]，坐标下降算法[44]或马尔可夫链蒙特卡罗（MCMC）算法[45]-可以在不同的ML算法家族中重用;以及②支持这些主力实现的ML分布式集群操作系统，它在各种硬件上分区和执行这些主力。这样的软件平台不仅实现了通过分布式机器学习研究获得的资本成本降低，甚至还通过减少大型机器学习应用程序的人力成本（科学家和工程师的时间），通过开发者使用编程库和集群管理接口来补充它们。随着对数据驱动的知识管理需求的日益增长，† https：//www.youtubwww.example.come.com/yt/press/s t atistics.html‡https://code.facebook.com/posts/229861827208629/scaling-the-facebook-data-warehouse-to-300-pb/我我第一章1年，第AAME.P. Xing等/ Engineering 2（2016）179计算、决策和永久学习--这是机器智能愿景的代表性标志--在未来几年，大数据上的计算工作负载的主要形式可能会经历从用于确定性存储、索引和查询的数据库式操作到ML式操作（如概率推理、约束优化和几何变换）的快速转变。为了最好地完成这些计算任务，必须执行大量的数据传递并解决高维数学程序，需要重新审视传统系统架构中的原则和策略，并探索新的设计，以最佳地平衡正确性，速度，可编程性和可部署性。指导这种探索所需的一个关键见解是理解ML程序是以优化为中心的，并且经常承认迭代收敛的算法解决方案，而不是一步或封闭形式的解决方案。此外，ML程序的特征在于三个属性：①容错性，这使得ML程序在有限的中间计算中的误差;②动态结构依赖性，其中必须考虑模型参数之间的变化相关性，以便实现有效的、近线性的参数加速;以及③非均匀收敛，其中数十亿（或数万亿）ML参数中的每一个都可以在非常不同的迭代次数下收敛（通常，一些参数将在2这些属性可以与传统程序（如排序和数据库查询）形成对比，传统程序是以事务为中心的，只有在每一步都以原子正确的方式执行时才能保证正确数据x和模型A。此外，ML算法家族通常通过它们在f，r，x和A上的独特特征来识别。例如，用于图像分类的典型深度学习模型，例如Ref.[20]，将包含数千万到数十亿的矩阵形状的模型参数在A中，而损失函数f表现出深度递归结构ff1f2f3学习类似于人类视觉皮层的图像分层表示。用于识别遗传疾病标志物的结构化稀疏回归模型[4]可以使用重叠结构诱导函数rr1r2Abr3Ac，其中Aa、Ab和Ac是A的重叠子集，以尊重染色体重组的复杂过程。图形模型，特别是主题模型，通常部署在数十亿个文档x上-即N≥ 109，这是很容易由Facebook和Twitter等社交媒体生成的量-并且可以涉及高达数万亿个参数θ，以便在如此多的数据上捕获丰富的语义概念[26]。除了指定Eq。(1)，还必须找到优化L的模型参数A。这是通过从一小组算法技术中选择一个来实现的，例如随机梯度下降[42]，坐标下降[44]，MCMC[45]和变分推理（仅举几例）。所选择的算法技术应用于Eq. (1)以生成一组迭代收敛方程，其由ML从业者实现为程序代码，并且重复直到达到收敛或停止标准（或者，同样经常地，直到超过固定的计算预算迭代收敛方程具有以下一般性形式：[32，34]。在本文中，我们将基于这些属性导出分布式ML系统的独特设计原则;这些设计一个很好的例子，L，x（二）原则在ML正确性，速度和可编程性之间取得了更有效的平衡（同时仍然普遍适用于几乎所有ML程序），并被组织成四个即将到来的部分：①如何分发ML程序;②如何桥接ML计算和通信;③如何通信;以及你知道要沟通什么。在深入研究这些原理之前，让我们首先回顾一下有关迭代收敛ML算法的一些必要背景信息。2. 背景：迭代收敛机器学习（ML）算法除了少数例外，几乎所有ML程序都可以被视为以优化为中心的程序，这些程序遵循一般的数学形式：maxLx，orminLx，A，当 ，A，N ; 本质上，ML程序试图拟合N个数据样本（根据实际应用，可能有标记或无标记其中，括号（t）表示迭代次数。这种一般形式使用两个函数从前一次迭代的A（t-1）和数据x产生下一次迭代①一个更新函数F（其增加目标L），其对数据x和先前模型状态A（t-1）执行计算，并输出中间结果;以及②一个聚合函数F，其然后组合这些中间结果以形成A（t）。为了简化符号，我们将在下面的下标中省略L-隐含的理解是，本文中考虑的所有ML程序都有一个显式的损失函数L（与缺乏这种损失函数的算法或程序相反）。现在让我们看两个具体的例子方程。(1)和（2），这将被证明有助于理解ML程序的独特属性。特别是，我们将特别关注任何ML程序的四个关键组成部分：①数据x和模型A;②损失函数f（x，A）;③结构诱导函数r（A）;以及可用于程序的算法技术。套索回归。Lasso回归[46]可能是结构化稀疏回归ML算法家族中最简单的范例，并且用于在给定向量值特征xi的情况下预测响应变量yi（即，回归，它使用标记数据）-但根据正在审议中），用xN我我第一章1（其中yi存在假设在xi中只有几个维度或特征是已知的，仅用于标记的数据样本），到由A表示的模型。关于我的这个问题。作为输入，Lasso被给予N个训练对x，其形式为拟合是通过优化（最大化或最小化）Δxi，yiΔR，i= 1，总体目标函数L由两部分组成：损失函数f，tors。目标是找到一个线性函数，由权重参数化它描述了数据应该如何适应模型，以及一个结构诱导，向量A，使得①ATxiyi，②m维参数，结合了关于项A的领域特定知识的ing函数r是稀疏的（大多数元素为零）：预期的应用，通过对最小Lx，A，其中Lx，A 一（三）A可以取的值Eq的简单性(1)掩盖了套索Lasso2i1伊因Jj1函数f和r的结构，以及潜在的巨大尺寸xi，yN;Ar†严格地说，MCMC算法不执行等式中的优化。(1)相反，它们直接从函数L生成样本，并且对这些样本应用附加过程以找到优化器A *。稀疏性有两个好处：它自动控制模型的复杂性（即，如果数据需要更少的参数，那么ML算法将根据需要进行调整），并通过将ML从业者的注意力集中在几个参数上来改善人类解释（一）IJJii1N第11nJ拉拉克KnIJIJ我NiBδ182E.P. Xing等/工程2（2016）179或者更简洁地用矩阵表示：最小值1XA，最小值2A类（4）i,j,BkB老 ，，但是，A22n1k新，wij当re，XT，x，Rmn;y，y，yRn;是欧几里德-δi，t11，老1n1n2（八）是Rm上的l范数;λ是某个常数，δi，k但是，平衡模型拟合（f项）和稀疏性（g项）。很多算法-wherekoldzhi可以将诸如随机邻近梯度下降或坐标下降的算法技术应用于该问题。我们将介绍k新ijxij，δ，1坐标下降迭代收敛方程：其中，+=和-=是自递增和自递减运算符（即，δ、B和z正在就地修改）;~P（）表示ATyXTX1，（五）“to sample from distribution拉克斯x，δt1，B克杰其中，Aj，：符号jj是是给定当前值δt1和B1。更新将分两步进行tor”，并且我们假设数据未被归一化，使得对于所有j，X T X <$1。阶段：①执行Eq. (8)在所有文档令牌xij上;以及②out-将其与一般的迭代收敛更新形式联系起来，我们putzN ，δ1N ，1. 聚合反应iji1ii1kk1有以下明确的形式为Δ和F：FLDA（A（t-1），XTY中国1XTX拉索 A，xk11克K2.1. ML程序XTY中国XTX A1F1，u布勒姆10001，乌斯季 格姆布勒姆克K（六）为了加速分布式集群上大规模ML程序的执行，我们希望了解它们的属性，并着眼于它们如何为分布式ML系统的设计提供信息。um,n 当re，uj 潜在Dirichlet分配主题模型。 潜在狄利克雷分配（LDA）[47]是图模型ML算法的成员家族，并且由于其在文本文档的大型语料库中识别通常重复出现的主题的能力而被称为因此，LDA是给定的N个不受约束的数据集x，其中每 个 文 档 xi 包 含 Ni 个 单 词 （ 在 L D A li t e r at u r e 中 称 为.Eachtookenx1，，V是表示词汇表中的一个单词的整数例如，短语tems.首先了解ML程序“不是”什么是有帮助的：让我们考虑一个传统的非ML程序，例如MapReduce上的排序。该算法首先将元素在M个映射器的池中随机排序，x1，映射器将每个元素xi散列为键值对（h（xi），xi），其中h是接下来，对于每个唯一键a，MapReduce系统将所有键值对（a，x）发送到标记为“a”的Reducer每个Reducer然后对其接收到的值x运行顺序排序算法，最后，Reducer轮流（按升序键顺序）输出其排序值。可以表示为xixi1，xi2，xi325，60，13（相应的-关于MapReduce排序，需要注意的第一件事是，它是单排序的。字和整数之间的关系是任意的，与LDA算法的准确性这一目标是在一个数据库中， ，δN ，传递和非迭代-只有一个Map和一个Reduce步骤are required.这与ML程序相反，ML程序是迭代收敛的，并重复Eq。(2)多次更重要的是，i ji 1i i 1kk1-每个文档的“文档-主题向量”δ i = Simplex K =，以及K个“词-主题向量”（或简称“主题”）B k = Simplex V =-，最大化以下对数似然MapReduce排序是以操作为中心的，具有确定性，容忍个别操作中的错误。例如，如果一些映射器输出一个错误的散列对（a，x），其中一个哈希（x）（为了讨论起见，让我们说这是由于从最大LLDA一阿克斯，LDA凯特。IJ兹伊季凯特。IJ我的电源故障），则最终输出将被错误排序，因为x将在错误的位置输出正因为如此，Hadoop和Spark（支持MapReduce的系统）提供了i2011j2011xN;A（七）通过强大的容错系统保证强大的操作正确性。这些容错系统当然需要额外的其中，NKlnDir ic hle tδilnDir ic hle tBki1k 1r新乌勒 这是意大利的一个城市。k. a. ，discrete）proba-工程工作，并强加额外的运行时间开销的形式，基于硬盘的检查点和世系树[34，49]-但他们是必要的操作为中心的程序，这可能无法正确执行，在他们的缺席。这将我们带到ML程序的第一个属性：容错-凯特。能力分布;LLDirichlet vv 是狄利克雷概率安斯。与MapReduce排序示例不同，ML程序通常以及α和β构成了平衡模型fit（f项）与从业者关于文档主题向量δ i和主题B k（r项）先验领域知识。与Lasso类似，许多算法技术，如吉布斯采样和变分推理（仅举两例），都可以用于LDA模型;我们将考虑折叠的吉布斯采样方程：对中间计算中的微小错误具有鲁棒性。由方程式(2)，即使有限数量的更新Δ L被不正确地计算或传输，ML程序仍然在数学上保证收敛到模型参数A * 的最佳集合-也就是说，ML算法以正确的输出终止（即使可能需要更多的迭代来这样做）[37，40]。一个很好的例子是随机的† 更具体地说，我们提出的形式被称为对数似然是概率分布的自然对数。作为图模型ML算法家族的一员，LDA指定概率分布，因此具有相关的对数似然。†† 注意，塌陷吉布斯采样将δi和Bk重新表示为整数值向量而不是单纯形向量。详情可参见参考文献。48.有许多有效的方法来计算这个概率。为了保持本文的重点，我们建议读者参考参考文献[48]以获得适当的介绍。拉新其中L阿克斯恩阿克斯拉阿维尼翁拉X XL·j拉IJik第不E.P. Xing等/ Engineering 2（2016）179梯度下降（SGD）是许多ML程序经常使用的算法主力，从深度学习到矩阵因子化和逻辑回归[50当执行使用SGD的ML程序时，即使在每次迭代后向模型添加一个小的随机向量ε，即A（t）=A（t）+ε，仍然可以确保收敛;直观地说，这是因为SGD总是计算更新ΔL的最佳A *的正确方向，因此移动A（t）只会导致重新计算方向以适应[37，40]。这个属性对分布式系统设计有重要的意义，因为系统不再需要保证完美的执行、机器间通信或从故障中恢复（这需要大量的工程和运行时间开销）。近似地做这些通常更便宜，特别是当资源受到约束或限制时（例如，有限的机器间网络带宽）[37，40]。尽管有容错性，ML程序实际上可能比以操作为中心的程序更难以执行，因为依赖性结构从粗略地看目标L或更新函数ΔL和F并不立即明 显 。 当 然 ， 依 赖 结 构 出 现 在 以 操 作 为 中 心 的 程 序 中 ： 在MapReduce排序中，Reducer必须等待Map- pers完成，否则排序将不正确。为了了解ML依赖结构的独特之处，让我们考虑等式中的Lasso回归示例（三）、乍一看，ΔLasso更新Eq.（6）看起来它们可以并行执行，但这只是部分正确。更仔细的检查表明，对于第j个模型，在另一种迭代收敛算法PageRank中也观察到并利用了类似的非均匀收敛[53]。最后，值得注意的是，ML程序的一个子集表现出紧凑的更新，因为在仔细考虑后，更新ΔLasso明显小于矩阵参数的大小|.|. InbothLasso（方程式（3））和LDAtopic模型[47]，由于数据中的稀疏结构，更新Δ Lasso通常仅涉及少量模型参数。另一个突出的例子是“矩阵参数化”模型，其中A是一个矩阵（例如在深度学习[54]中），但单个更新Δ Lasso可以分解为几个小向量（所谓的“低秩”更新）。如果分布式ML系统在设计时考虑到这一点，这种紧凑性可以大大降低存储、计算和通信成本，从而实现数量级的加速[55，56]。2.2. 关于数据和模型并行性对于涉及TB数据的ML应用程序，使用具有高达数万亿模型参数的复杂ML程序，在单个台式机或笔记本电脑上执行通常需要数天或数周。这种计算瓶颈刺激了许多分布式系统的发展，用于在集群上并行执行ML程序[33ML程序通过在数据x或模型A上细分更新ΔL来并行化-分别称为数据并行化和模型并行化。重要的是要注意，这两种类型的并行性是复杂的-参数Aj，其更新取决于克杰·j·k Ak （t- 1）。换句对称和非对称互补，同时换句话说，潜在地每隔一个参数Ak是可能的依赖性，因此模型参数A更新的顺序对ML程序的进度甚至正确性有影响更重要的是，还有一个在以操作为中心的程序中不存在的细微差别：Lasso参数依赖关系不是二进制的（即，不仅是通知如果XTX= 0（意味着数据列j与数据和模型并行性是可能的（在某些情况下甚至是必要的），并且是不对称的，因为数据并行性可以一般地应用于具有独立和同分布（i.i.d.）假设数据样本为x1，等i.i.d. ML程序（从深度学习到逻辑回归，再到top-ic建模等）构成了实际ML使用的大部分，并且很容易通过对数据索引i的求和来识别，物镜L（例如，Lasso设备（3））。因此，当一个工作狂·j·k列k），则Aj和Ak彼此具有零依赖性，并且算法技术（例如，SGD）被应用于L，导出的更新可以安全地并行更新[39]。 同样地，即使XTX>0，方程Δ也将对i求和，这可以很容易地只要Ak= 0，则Aj不依赖于Ak。这样的依赖结构并不局限于一个ML程序;仔细检查LDA主题模型更新Eq. (8)揭示了xij（文档i中的单词标记j）的吉布斯采样器更新取决于①文档i中的所有其他单词标记，以及②其 他 文 档 a 中 表 示 完 全 相 同 单 词 的 所 有 其 他 单 词 标 记 b ， 即xij=xab[25]。如果不尊重这些ML程序依赖性结构，则结果是使用附加机器的次理想缩放（例如，2倍的加速比，4倍的机器）[25]甚至是彻底的程序失败，这会破坏ML程序的内在容错能力[39]。ML程序的第三个特性是非一致收敛，即并非所有模型参数Aj都将在相同次数的迭代中收敛到它们的最优值Aj *，这是MapReduce排序等单遍算法中不存在的一个特性。在等式中的Lasso示例中，(3)，r（A）项促使模型参数Aj恰好为零，并且已经根据经验观察到，一旦参数在算法执行期间达到零，则不太可能恢复到非零值[39]。换句话说，达到零的参数已经收敛（虽然不是100%，但概率很高）。 这表明，通过更频繁地对参数执行Δ Lasso，计算可以更好地优先考虑仍然为非零的参数-这种策略确实减少了ML程序完成所 需 的 时 间[39]。在多个机器上并行化，特别是当数据样本的数量N是数百万或数十亿时。相比之下，模型并行性需要特别注意，因为模型参数Aj并不总是享受这种方便的i.i.d.。 假设（图） 1）-因此，哪些参数A j被并行更新，以及更新Δ L发生的顺序，可以导致各种结果：从接近理想的P倍加速与P机器，到没有额外的加速与额外的机器，甚至完成程序图1.一、 数据和模型并行性之间的区别：给定模型，数据样本总是条件独立的，但有些模型参数彼此并不独立。† 对于Lasso坐标下降ΔLasso（等式(5))，对i的求和是在内积中，联系我们 XX克·k1 2 3 1 23第1Lassop2001年1月，pLassop，Lassop，Lasso p， 拉索布勒姆P1我的屁股我的屁股L  1 1 184E.P. Xing等/工程2（2016）179失败Lasso中讨论的依赖结构（第2.1节）是非i.i.d.的一个很好的例子模型参数的性质现在让我们分别讨论数据和模型并行性的一般数学形式。数据并行。 在数据并行ML执行中，数据x= {x1，如果更新函数ΔL对数据样本i具有最外求和（如在具有常见i.i.d.假设数据），我们可以在数据子集上拆分ΔL，并获得数据并行更新方程，其中ΔL（A（t-图二、LDA顶层建模中同时数据和模型并行性的高级说明。在本例中，三个并行工作进程对数据/模型块进行操作A，P A t1，x Lp（九）Z（1）、Z（1）和Z（1），然后在迭代2期间继续移动到块Z（2）、Z（2）和Z（2），依此类推。值得注意的是，是主机的基础已建立的加速数据并行执行的技术，如小批量和有界异步执行[37，40]。作为一个具体的例子，我们可以写Lasso块坐标下降方程。（6）在数据并行形式中，通过应用一点代数：最后，通过将数据样本和模型参数（xi，Aj）的空间划分为不相交的块，同时数据和模型并行也是可能的。LDA主题模型Gibbs中国大陆 关于我们X Xt采样方程（Eq. (8))可以被划分成这样的块At1,xixpi1ik1I1ikk方式（图） 2），为了达到接近完美的加速比与P机器[25]。ixXimyi kmXimXikAkt1p（十）联系我们我的屁股我的屁股3. ML系统设计原则F1，u第1页1ML程序的独特属性，当与CUP联系我们m数据和模型并行的互补策略，相互作用，产生一个复杂的设计考虑空间，Where，意味着（带有一点滥用）总结所有数据索引i包含在xp中。模型并行性。在模型并行ML执行中，模型A被划分并分配给工作者/机器p= 1，与数据并行性不同，每个更新函数ΔL也接受一个调度或选择函数Sp，（t-1），它限制ΔL对模型参数A的子集进行操作（一个基本用途是防止不同的工作者试图更新相同的参数）：A1， A，1（11）p1其中，我们省略了数据x，因为它没有被分割。 Sp，（t−1）输出一组索引{j1，j2，.}，因此Δ L只对A j，A j，.执行更新。;我们指的是模型参数超越了一般迭代收敛更新方程，Eq.（二）、在这种理想的观点中，人们希望Δ和F函数只需要一个方程接一个方程地实现（例如，遵循前面给出的Lasso回归数据和模型并行方程），然后由通用分布式系统执行-例如，如果我们选择MapReduce抽象，可以将Δ写为Map，F写为Reduce，然后使用Hadoop或Spark等系统执行它们。然而，现实情况是，最高性能的ML实现并不是以这种天真的方式构建的;而且，它们往往出现在ML专用系统中，而不是通用MapReduce系统[26，31，35，36]。原因在于，高性能ML远远超出了理想化的MapReduce类视图，并且涉及到许多并非迫在眉睫的考虑因素从数学方程中可以明显看出：1 2作为日程安排。一般来说，模型参数Aj不是相互独立的，并且已经确定，只有当并行更新的每次迭代被限制为相互独立（或弱相关）参数的子集时，模型并行算法才有效[39，57Lasso块坐标下降更新（等式（6））可以容易地写成简单的模型并行形式。这里，Sp，（t-1）在每次迭代中为工作者p选择相同的固定参数集，我们将其称为j p1，.，下午三时三十分：例如用于数据并行的数据批量大小，如何划分模型以实现模型并行，何时在工作器之间同步模型视图，基于梯度的算法的步长选择，甚至执行Δ更新的顺序。ML性能考虑因素的空间甚至对资深从业者来说都是令人生畏的，我们认为需要一个并行ML的系统接口，以①促进ML考虑因素的有组织的科学研究，②将这些考虑因素组织成一系列高级原则，以开发 XTY中国XTX A分布式ML系统。作为组织这些活动的第一步At1,SAt1p1不kjp1p1不克k原则，我们将根据四个高层次的问题来划分它们如果一个ML程序（2）告诉系统X 和克鲁杰XjXkA下午ppmp你好，我是一个很好的人。At1 ,SA t1 ,to compute,” then the system must consider: ①计算;②如何将计算与机器间通信联系起来;③如何在机器之间进行通信;沟通什么。通过系统地解决ML问题，F拉索 一个1000万美元，  拉索1，1M中国（12）考虑到每个问题下，我们表明，这是可能的你好，我是一个很好的朋友，我的朋友建立子系统，其效益与彼此，并且可以组装成完整的分布式ML阿斯塔纳1号公路，SP，t P，中国在ML程序执行时间上享受数量级加速的系统。第1·j·j·k·j·k jkE.P. Xing等/ Engineering 2（2016）1793.1. 如何分配：调度和平衡工作负载δi，k（t- 1）+ =1，其中k old = z ij（t - 1）且k new = z ij（t - 1）~ P（zij|x ij，δ i（t- 1），为了并行化ML程序，我们必须首先确定如何最好地将其划分为多个任务-也就是说，我们必须将等式中的单片Δ划分。(2)分成一组并行任务，遵循数据并行形式（等式2）。（9））或模型并行形式（Eq.（11））-或者甚至是两种形式的更复杂的混合体。然后，我们必须调度和平衡这些任务，以便在有限的池中执行 也就是说，我们①决定哪些任务是并行的（同样重要的是，哪些任务不应该并行执行）;②决定任务执行的顺序;③同时确保每台机器的工作负载份额是平衡的这三个决定已经在以操作为中心的程序（例如MapReduce排序示例）的背景下进行了仔细研究，从而产生了（例如）Hadoop和Spark中使用的调度器系统[34]。这种以操作为中心的调度器系统可能会根据集群配置、现有工作负载甚至机器故障提出不同的执行计划（决策①到③的组合）;但至关重要的是，它们确保以操作为中心的程序的结果每次都是完全一致和可再现的然而，对于ML迭代收敛程序，目标不是完全可再现的执行，而是模型参数A收敛到目标函数L的最优值（即，A接近于最优值A * 的某个小距离ε内因此，我们想开发一种执行策略，其执行计划允许ML程序每次都以相同的收敛质量可证明地终止-我们将其称为这样的策略可以作为调度系统来实现，它可以创建与以操作为中心的ML程序执行计划不同的ML程序执行计划。ML程序中的依赖结构。以便生成为了给ML程序提供一个正确的执行计划，有必要了解ML程序是如何具有内部依赖性的，以及通过简单的并行化来破坏或违反这些依赖性将如何减慢收敛。与以运营为中心的计划不同，B（t- 1））。这些方程在不同的单词标记wij和wuv之间产生了许多依赖性。当wij=wuv时，会出现一个明显的依赖关系，导致它们有可能更新B的相同元素（当两个令牌的kold或knew相同时此外，在条件概率P（zij）内部存在更复杂的依赖性|x ij，δ i（t- 1），B（t - 1））;为了使本文保持在适当的高水平，我们将通过注意到的元素来进行总结，即B ·，v，是相互依赖的，而δ的行中的元素，即δ i，·，也是相互依赖的。由于这些复杂的依赖关系，LDA主题建模的高性能并行性需要同时的数据和模型并行策略（图1）。 2），其中单词标记w ij必须通过它们的值v = w ij和它们的文档i小心地分组，这避免违反B中的列/行依赖性，并且 δ[25]。ML程序中的调度 鉴于这些依赖关系，我们如何以避免违反尽可能多的依赖关系结构的方式来调度更新Δ（注意，由于ML容错，我们不必避免所有依赖关系）-但同时不会由于缺乏任务或负载平衡差而使P个工作机器中的任何一个空闲？这两个考虑因素对ML程序执行时间具有不同但互补的影响：与顺序执行相比，避免依赖性违反可以防止ML程序的每次迭代的进度程序将不需要更多的迭代来收敛），同时保持工作机器完全被有用的计算占用，确保来自P台机器的迭代吞吐量（每秒执行的迭代）接近于单个机器的P倍。简而言之，接近完美的P倍ML加速是由接近理想的每次迭代进度（等于顺序执行）与接近理想的迭代吞吐量（P倍顺序执行）相结合而产生的。因此，我们希望有一个理想的ML调度策略来实现这两个目标。为了解释如何实现理想的调度，我们回到我们运行的Lasso和LDA示例。在Lasso中，两个参数Aj和Ak相互依赖的程度受数据的影响例如排序，ML程序是容错的，并且可以自动化，相关性XTX在第j个和第k个特征维度之间-我们·j·k可以从有限数量的依赖关系违规中恢复-但将此操作和其他类似操作称为依赖关系检查。如果太多的违规将增加所需XTX <对于一个小的阈值κ，那么A和A将有很小的影响。为了收敛，并导致并行ML程序相互影响因此，理想的调度策略是找到次优的，少于P倍的加速比。所有对（j，k）使得XTX

下载后可阅读完整内容，剩余1页未读，立即下载