编译 | Don
编辑 | 陈大鑫
机器学习算法十分强悍，能够对输入的数据进行深入的观察，建立从现实世界到所要解决问题的高质量的映射，从而让冷冰冰的机器做出近似于人类的高质量的预测和识别。
如今，随着机器学习算法的高速发展，机器学习算法已经被广泛地应用于生活中，它们在潜移默化中影响并帮助着我们，比如在输入一段文本的时候，机器能理解我们的意思，这就是基于机器学习的自然语言处理以及文本挖掘技术；比如看到一张图片，机器就能迅速帮我们找出其中的人脸或者目标事物，这就是基于机器学习的图像处理技术；比如网购平台总是能高效精准地为我们推送令人怦然心动（忍不住剁手）的精美商品，这就是基于机器学习的推荐系统。
然而，机器学习算法是个消耗算力的怪兽。当处理大规模数据的时候，现有机器学习技术通常都要付出巨大的时间成本来进行训练和学习。这个领域就叫做大规模机器学习（Largescale Machine Learning, LML），大规模机器学习的目标是想方设法从大数据中高效地挖掘和学习到数据之间的模式和联系，深入挖掘其中的有效信息。
《A Survey on Large-scale Machine Learning》对大规模机器学习方法LML进行了系统的综述，为这个领域的未来发展描绘出了一个宏大的蓝图。
以下是论文内容，AI科技评论对关键内容进行了编译。
论文链接：https://arxiv.org/pdf/2008.03911.pdf
我们首先根据算法的可扩展性（Scalability）对LML方法进行了三方面的划分，它们分别是：1、计算复杂度的模型简化；2、计算效率的优化逼近；3、计算能力上的计算并行性。然后我们根据目标情景再对这些话题进行细分，并根据它们的内在算法策略上的差异再次细分并详细介绍。最后我们分析了它们的局限性，并讨论了大规模机器学习方法未来可能的发展方向，以及需要进一步改善和解决的问题。
1
200 大规模机器学习论文综述
机器学习是一个很神奇的方向，它能够给冰冷的机器赋以“智能”，让它们能够从繁杂无序的数据中“抽丝剥茧”，从而学习其中潜在的规律和“模式”。以往我们都是需要人类专家对数据进行“生无可恋"的研究、讨论和思考之后才能得到一些有用的信息，而如今机器学习能够自动完成这一切，而无需我们手动对这些抽象的信息进行发现和编码。
机器学习方法固然好，但是它也有着一摞“难念的经”，其中最让它头疼的就是在面对大规模数据模型训练的“二次时间复杂性”问题。近年来，随着各种可穿戴设备的发展、手机等终端的普及，以及摄像头等数据源的疯狂增长，人们所拥有的数据大规模增长。想要从这些庞大的数据集中挖掘出有效的信息是一件很累人的事情，即便是对于拥有强大算力的计算机来说也是一样，这就让机器学习算法变得不堪重负。在实际中，甚至会出现数据过期没用了，但是模型还没训练结束的问题，让人哭笑不得。
因此，为了充分挖掘大数据这座金矿，人们开始研究大规模机器学习这个领域。通常意义上来说，大规模机器学习的宗旨在于在有限的计算资源上解决一般化的机器学习任务，尤其是针对那些基于大规模数据集的场景。因此，大规模机器学习领域已经成为大数据分析的核心技术之一，如果没有它，可能后续的一切技术和操作都将不复存在。举例来说，在Waymo和Tesla Autopilot等自动驾驶汽车中，需要对感知的多种图像和传感器数据进行快速而实时的卷积计算处理，从而感知到周围的环境并作出及时的车辆操作（因为自动驾驶汽车的感知数据很丰富，包括视频、声音、雷达和距离传感器等，计算比较复杂，我们可不想看到出车祸了之后算法才告诉我们要刹车的“马后炮”）。又比如在线媒体和电商网站，如Netflix和Amazon，它们需要根据用户的浏览历史和购买记录建立实时高效的协作过滤模型，从而进行精准的推荐（应该没啥人会太关注昨天的娱乐圈热点，因为已经过时了嘛）。不论如何，大规模机器学习对于我们的日常生活起着至关重要的作用。
在近些年，人们意识到数据才是企业资本的核心，因此人们对于大数据的青睐和分析需求与日俱增！而随着数据的爆炸性增长，大规模机器学习这一领域急需一些系统的调研和回顾文章，用以指导人们建立高效的机器学习算法平台，并设计与之配套的高效的机器学习解决方案。目前来说，学术界虽然已经发表了一些该领域的综述和调研报告，但是它们都多多少少存在着一些问题，而且不够全面。
首先，它们都只关注大规模机器学习的一个方面，而忽略了各个方面之间的联系和互补。这就限制了它们对这一领域的系统理解，也让它们难以宏观地把握大规模机器学习的全貌，从而提出有助于该领域未来发展的建设性意见。比如，有些文章只关注预测模型部分，而忽略了之前的模型训练和优化部分；有些文章则忽略了处理高维数据的优化算法；还有的文章的关注点则比较独立和专一：仅局限于Hadoop生态系统中的分布式数据分析，而没有涉及其他工具和系统中的相关研究。
在本文中，我们从计算技术的角度对200多篇关于大规模机器学习的论文进行了深入的分析，并讨论了该领域未来的研究和发展方向。同时，本文也为这个领域的研究者和从业人员列出了一系列查找表，以方便根据自己的需求和现有资源对号入座、有选择性地挑选合适的预测模型、优化算法和学习策略。我们将贡献总结如下：
第一、我们从三个计算角度对大规模机器学习进行了全面的综述：
1、模型简化：通过简化预测模型来降低计算复杂性；
2、近似优化：通过设计更好的优化算法（大多数都是近似算法）来提高计算效率；
3、计算并行性：通过调度多台计算设备来提高系统的整体计算能力。
第二，我们对现有的大规模机器学习方法进行了深入的分析。
为此，我们根据目标场景将每个上述分类中的方法进行更精细的划分。我们分析了它们加速机器学习过程的动机和内在方法，并且据此对它们进行分门别类的介绍。在介绍中我们会结合它们各自领域中的代表性成果和特点进行深入的介绍。此外，我们还回顾了这些方法的混合方法即结合各个部分的优势，协同地对系统计算性能进行优化研究。
第三，我们分析了大规模机器学习方法在各个方面的局限性，并在其扩展的基础上提出了该方向未来可能的发展方向。
此外，我们还讨论了相关领域中的一些有待解决的问题，希望我们的这个总结能够为读者们带来一些指引，为大规模机器学习的发展“抛砖引玉”，提供一些参考。
2
大规模机器学习的三个方面
在本节中，我们将详细回顾大规模机器学习。具体来说，我们先详细介绍了前文所述的三种分类中的方法，并且在最后介绍各方法之间的协同方法。对于其中的每个部分，我们根据目标场景对这些方法进行了分类，并且根据他们的技术方法和内在策略对其进行分门别类的具体介绍。我们也进行了一些实验，来证明这些策略的有效性，并且总结各自的利弊。为了方便起见，我们在图1中展示了本小节的组成结构，采用头脑风暴图，由浅入深。
图1. 介绍结构图，我们从三个方面展示了将普通机器学习扩展到大规模机器学习的方法。
2.1 模型简化
在前文中，我们从计算复杂性的角度回顾了各种大规模机器学习方法。现在我们来讨论上述方法的优缺点。首先，相对于深度模型来说，基于核技术和基于图的相关模型拥有更好的扩展性和可优化性。此外，利用基于核以及基于图相关的模型时，人类专家能够将自己的先验知识和领域经验量化进去，融入模型，省得从零开始进行复杂的模型训练。在数学中，半正定矩阵的和仍然是半正定矩阵，因此，当我们将不同类型特征的相似性合并到一个模型中的时候，这种方法将会十分容易和便利。值得我们注意的是，尽管基于图的方法相对于基于核的方法所需的内存开销更少，但是它们只能处理满足聚类假设（Cluster Assumption）的数据场景，如果数据不满足该假设，图方法也就束手无策了。
其次，由于结构示例的层次特征提取的优秀性质，深度模型能够据此获得更好的分类精度。但是天下没有免费的午餐，因为加大了网络规模，所以就得需要花费大量的时间来训练这些过参数化的模型(over -parameterized models)。滤波器分解方法虽然能够显著地减少系统的计算量，但是与此同时必须对要体系结构进行仔细的设计。此外，一些深层模型在数学上等同于核化岭回归，它们可以从数据中学习到自己的核，但是它们只能在有限维空间中构建该核，而且这些核的构建结果通常是很晦涩、让人难以理解的，这就使得系统的可解释性进一步下降，也让预测的逻辑更难被理性解释。相比之下，基于树的分层分割模型则更易于解释。此外，这些模型还可以直接集成到许多其他的加速方法中，例如使用二元分类器的标签树算法中。
表1. 一种用于模型简化的大规模机器学习方法查找表。
2.2 最优化近似
为了在提高计算效率的同时保持解的可靠性，本节中介绍的方法更倾向于减少优化误差的计算。首先，MGD和CGD方法都考虑了算法中使用实例或参数的重要性，并据此引入了不少决策方法来减少计算时间的成本。同时，上述两者都可以利用Nesterov的外推步骤（extrapolation steps），用累积梯度调整学习速率，或者使用直线搜索来加快收敛的速度。其次，CGD更适合在参数量较大的模型优化场景中使用，特别是对于以倒排索引存储的线性模型数据。相比之下，如果特征的数量远远小于样本数量，那么就应该基于MGD进行求解。
第三，对于处理具有大量实例的大型模型，我们自然而然地想到将MGD和CGD联合在一起，即在每次迭代中用几个实例更新参数子集。例如，最近学术界提出了一种叫做“小批量随机块坐标下降（mini-batch randomized block coordinate descent）”的方法：每次迭代中都基于随机小批量数据来估计所选参数的部分梯度。最后，小批量梯度MCMC算法提高了样本的质量，加快了贝叶斯推理的执行速度。
此外，这些算法通常能够从不同的角度，比如说加性噪声和动量等方面来近似等价MGD。然而，由于这些来自于本机的部分数据是有局限性的，它们很可能无法收敛到期望的分布，因此，我们必须引入一些必要的修正项来替代矫正步骤。除此之外，如何将前文所述的这些额外算法与贝叶斯算法与优化算法区分开是一个重要的课题，这个方面仍然有待研究。
同时，我们讨论的大部分的大规模机器学习方法都是集中在处理凸问题上，凸问题的优化和求解是一个相对来说比较系统的数学方向。而非凸优化的问题则是难以解决的。此外，我们可以利用“那些普遍被IEEE认可的知识工程和数据工程中的10种方法”直接解决目标问题。相反，人们可以通过参考其他领域的相关工作来寻找问题的近似形式、转化形式，并且转而为其开发出更加合适和高效的算法。
表2. 基于优化逼近的大规模机器学习方法的查找表
图2. 小批量梯度下降示意图，红色的步骤是提高计算效率的关键
图3. 坐标梯度下降示意图，红色的步骤是提高计算效率的关键所在
2.3 计算并行性
现在我们来聊聊计算并行化的那些事。首先是对CPU的优化，这样的优化是为了处理具有复杂顺序操作的模型。例如，通过对激活神经元的稀疏选择引入局部敏感排列，在CPU上训练全卷积神经网络的速度能够比使用GPU的最佳性能快3.5倍！相反，GPU可以大大提高密集计算模型的计算能力，这些模型的特点是具有大量的密集矩阵和向量运算。
第二，虽然机器学习方法可以兼容多种提取方法极其抽象的提取结果，但是为特定的设置选择恰当的提取方法和抽象空间也是至关重要的。一般来说，图并行技术适合于图模型，而环并行技术（ring-allreduce）则更适合于深度学习模型。第三，我们可以利用现有的系统来简化更高层次的系统开发。例如，在YARN的基础上，Angel开发了一个通用大规模机器学习的参数服务器系统，这个系统支持模型和数据的并行。类似的，Glint将Spark应用于内存中常用数据的处理，并且为大型主题模型引入了异步参数服务器。此外，PS2将Spark和参数服务器作为两个独立的应用程序，并且独立发布，而不对Spark进行魔改，这使得它能够兼容任何版本的Spark平台。最后，GraphX还引入了图并行化（Graph Parallel）来加速基于Spark的图形模型。
但是，在实际的项目开发中，针对不同项目最佳的大规模机器学习配置其实是各不相同的，它们会因为数据的大小而出现差异，不能一概而论，需要进一步的研究。例如，对于训练支持向量机来说，当数据集的大小增加到一定规模时，使用GPU训练的效率才会比CPU高。此外，由于系统开销的增加，分布式系统的训练收益会随着处理器数量的增多而降低（虽然很难理解但事实确实如此）。因此无论我们抽象的程度如何，提取的方法如何，都必须控制处理器的投入和算法执行平台的硬件配置，以获取最佳的训练回报率。否则钱投进去了，性能越来越差可不行。例如，较大的CNN网络通常需要更大的算力来支持，也就是需要在更多的机器上进行训练，从而快速收敛。但是一个有17亿参数的模型在81台机器上运行时，它的加速比其实只有12倍左右，这就不太值当了。
表3 用于计算并行性的大规模机器学习方法速查表
图4. 分布式处理系统示意图. (a) 是mapreduce系统的结构图，(b)是图并行系统的结构图，(c)是基于参数服务器的集群示意图，(d)是基于环的allreduce抽象的数据通信流程。
2.4 联合合作
基于文中的实验，我们在本小节中对联合合作方法进行汇总讨论。首先，我们可以发现，梯度压缩不仅可以减少每次迭代的时间开销，而且可以降低优化的总体开销。例如，与完整的32位梯度相比，使用4位QSGD对16-GPU的AlexNet进行训练的实验中，当我们维持训练精度相同时，算法的通信加速比会超过4倍，而且总体的成本仅提高了2.5倍。特别是对于线性模型，SketchML可以加速原有的优化器，并实现4倍以上的提升。值得注意的是，根据实验结果的对比我们发现，通信与计算比率较大的模型和带宽较小的网络可以从压缩中获益更多。其次，梯度延迟还减少了数据通信量，显著增加了人工在计算上的参与比例。例如，在使用本地更新算法时，CoCoA能够以比非本地化的最佳更新方法快25倍的速度实现收敛，也能实现更高的模型精度。此外，在有大量人工参与的情况下，通信成本的降低与随之带来的延迟几乎呈现了线性关系。
表4 用于联合协作方法的大规模机器学习方法的策略速查表
3
未来方向
大规模机器学习方法在近些年受到广泛的关注，也得到了长足的发展和进步。现有的大规模机器学习方法为大数据分析技术奠定了坚实的基础。下面我们将概述一些未来该领域的发展方向，并讨论一些重要的未解决的问题。
3.1 扩展方向
模型简化算法能够利用人类的先验知识来降低模型的计算复杂性。因此，我们可以进一步探索实例的分布和结构，并以此提高预测模型的可扩展性
探索数据的分布。核低秩近似假设RKHS中的映射实例几乎位于低维流形上，我们可以在低维空间上估计它的内积。基于图的方法也会根据邻近点更可能共享标签的假设进行放大。因此，为了使用大规模的非结构化数据，系统必须考虑底层的全局和局部数据分布。基于这个动机和发现，HSE和AER在未标记的实例上建立分层索引，并将其用于从粗到细的查询选择。结果发现，虽然每个候选者的质量估计的成本并没有降低，但是它们能够通过减少候选者的数量来显著地降低计算复杂度，从而加速大规模机器学习的速度。
探索样本的内部结构。在深度学习中，一种常见的压缩深度网络模型的方法是使用基于滤波器的分解方法，也就是在CNN中使用filter分解方法降低特征图的尺寸和通道数量。这些工作说明，设计更加有效的变换后的特征空间（Receptive Fields）也是一种有效的大规模机器学习加速方法。这其中，一个关键的方向是考虑具有多尺度不变性的特征，并且利用实例的结构信息来减小模型加速训练。DCNs技术就是这个想法的一个践行者，它提出了可变形卷积技术，来构建更加有效的变换，但是所带来的参数增加量和计算量的开销却很小。
分析目标任务。对目标任务进行更深入的分析也是一种简化模型的强有力的方法。例如，层次卷积网络（Hierarchical CNN）就是受到视觉领域中scene-selective cortex中粗粒度到细粒度的分类方法的启发而创造出来的。层次卷积网络现在广泛地应用于图像分类工作中。这些网络减少了参数的数据量，也减少了每次迭代所引入的计算量。此外，根据客观观测的频率分布参数和计算，该方法也降低了算法的复杂度。
3.2 优化近似
为了提高计算效率，人们使用优化逼近方法来减少优化误差。但是这些研究大多数都关注凸优化的问题，除此之外，研究人员通常会遵循传统的方法和管理来解决新出现的问题，而不去关注寻找新的解决方案。为了进一步加快这个领域的发展，并且加强对更加广泛的场景的适用性和优化，可以考虑以下的扩展：
对非凸问题的优化方法研究。当问题是非凸时，优化可能陷入较差的局部极小值，导致实际任务中性能极其不稳定。因此，有必要提高算法的随机逃逸能力，或算法绕过不良极小值的跳出能力。为此，研究可以考虑各种随机操作，例如随机权重初始化和梯度上的随机噪声。此外，受到“课程学习方法(Curriculum Learning)”的启发，我们可以先使用易于拟合的实例，然后逐渐转向困难的实例，例如边界实例。因此，它允许算法在早期阶段获得一个好的解决方案，然后调整到一个更好的最小值。
向数学模型靠拢的解决方案。通过将目标问题转化为几何等经典数学领域的模型，我们可以加速模型的优化。例如，简单的寻找最小包围球（MEB）的迭代解决方法可以用来解决大规模的支持向量机计算问题。之所以能够这样做，是因为MEB和SVM的对偶问题可以转化为相同的数学形式。类似地，论文《Training linear svms in linear time》中引入了割平面算法，这个算法迭代地细化一个可行集来求解高维稀疏特征上的支持向量机。
3.3 计算并行化
计算并行化操作提高了基于多个计算设备的计算能力。由于现有的计算系统都拥有良好的接口和合作机制，所以我们可以利用灵活的编程接口和较低的数据通信代价实现并行数据的处理。然而，当随着硬件、软件和预测模型的快速变大和升级，以下的几个方面的问题在近些年日益受到关注：
灵活的硬件抽象问题。快速的数据通信能力是高效的并行计算的基础。虽然allreduce能够最大限度地减少大多数方法的通信开销，但是它假设了不同节点的内存和计算能力处于同一水平。如果这个假设无法满足的话，资源利用率就会出现瓶颈。它的短板，也就是性能的上限就是其中最弱的计算机的性能。现实世界中，分布式系统通常由异构的设备组成，所以它们的计算性能、存储性能可能各不相同，那么使用该方法的性能就会大打折扣。因此，我们需要研究更加灵活的硬件抽象技术。利用特定领域的知识是一种很有希望的解决方案，比如通过集群调度的作业内的可预测性，来建立抽象硬件。此外，我们可以进一步探索混合抽象，并且考虑流量优化来平衡计算资源。
模块化的开源软件。不论是学术界还是工业界，科研人员和工程师们对开源项目的关注和支持都与日剧增。这是因为，在通用机器学习平台上开发并行系统，无论对于个人开发者还是大公司来说都是一个巨大的挑战。而基于开源软件的后续开发则轻松许多。此外，开源软件可以使更多的社区从中受益，能够使数据科学更加的普及和民主化。
为此，标准化和模块化的学习框架（类似于计算机架构）是这个发展方向的首选项。正所谓众人拾柴火焰高，当我们拥有了一套开源的模块化的软件，任何开发者都能结合自己的理解和领悟，对特定的方向提出贡献，从而整体提高系统的效率。此外，为了构建一个充满活力和生机的开源社区，我们有必要提供使用不同编程语言的接口，以使更多的研究人员能够参与到其中，并为产品化提供简单的后处理。
