机器学习问题通常会转换成一个目标函数去求解,优化算法是求解目标函数中参数的重要工具.在大数据环境下,需要设计并行与分布式的优化算法,通过多核计算和分布式计算技术来加速训练过程.近年来,该领域涌现了大量研究工作,部分算法也在各机器学习平台得到广泛应用.针对梯度下降算法、二阶优化算法、邻近梯度算法、坐标下降算法、交替方向乘子算法这5类最常见的优化方法展开研究,每一类算法分别从单机并行和分布式并行来分析相关研究成果,并从模型特性、输入数据特性、算法评价、并行计算模型等角度对每种算法进行详细对比.随后,对有代表性的可扩展机器学习平台中优化算法的实现和应用情况进行对比分析.同时,对所介绍的所有优化算法进行多层次分类,方便用户根据目标函数类型选择合适的优化算法,也可以通过该多层次分类图交叉探索如何将优化算法应用到新的目标函数类型.最后分析了现有优化算法存在的问题,提出可能的解决思路,并对未来研究方向进行展望.
Machine learning problems can be viewed as optimization-centric programs, and the optimization algorithm is an important tool to solve the objective function. In the era of big data, in order to speed up the training process, it is essential to design parallel and distributed optimization algorithms by multi-core computing and distributed computing technologies. In recent years, there are a lot of research works in this field, and some algorithms have been widely applied on machine learning platforms. In this paper, five common optimization algorithms, including gradient descent algorithm, second order optimization algorithm, proximal gradient algorithm, coordinate descent algorithm and alternating direction method of multiplier, are studied. Each type of algorithm is analyzed from the view of parallel and distributed respectively, and algorithms of the same type are compared by their model type, input data characteristic, algorithm evaluation and parallel communication mode. In addition, the implementations and applications of the optimization algorithm on representative scalable machine learning platforms are analyzed. Meanwhile, all the optimization algorithms introduced in this paper are categorized by a hierarchical classification diagram, which can be used as a tool to select the appropriate optimization algorithm according to the objective function type, and also to cross explore how to apply optimization algorithms to the new objective function type. Finally, the problems of the existing optimization algorithms are discussed, and the possible solutions and the future research directions are proposed.
机器学习问题通常会转换成一个目标函数去求解, 优化算法是求解目标函数中参数的重要工具[
为研究可扩展机器学习的优化算法在并行与分布式环境下的优化策略, 本文对多种机器学习优化算法进行分析总结.首先介绍本文对算法的分析维度、原始优化算法基本原理和并行计算模型, 然后对GD、Second-order、PG、CD和ADMM这5种优化算法分别从单机多核并行优化和分布式并行优化角度进行阐述, 并从模型特性、输入数据特性、算法评价标准和并行计算模型对每种算法的具体优化策略进行对比分析.通过综述研究发现:各种优化算法大多是对传统机器学习的凸函数问题进行优化, 不同算法再根据自身特点对目标函数的不同特性进行优化, 对于非凸函数的优化求解研究较少; 在多核、分布式环境下, 基于不同并行计算模型对不同算法进行改进, 通过并行化来提高运行速率, 解决大规模数据处理问题; 输入数据样本大多具有稀疏性, 从而保证特征之间关联程度较小, 便于多节点并行训练更新, 保证算法收敛.同时, 算法的更新策略需要依赖于不同计算模型的具体平台, 因此, 本文分类研究流行的可扩展机器学习系统, 总结其中实现的算法, 进而了解各优化算法在目前系统的实际实现和部署情况.最后绘制了根据目标函数进行分类的多层次分类图, 对论文中介绍的各优化算法进行划分, 帮助开发者根据目标函数选择优化算法, 交叉探索应用优化算法到新的目标函数类型上.
本文第1节介绍算法分析维度、原始优化算法和并行计算模型.第2节~第6节分别综述各优化算法并行与分布式改进.第7节综述现有机器学习系统优化算法实现情况.第8节给出全文算法的多层次分类图, 对目前优化算法存在的问题进行分析, 并展望未来的研究工作.第9节进行总结.
在机器学习的模型训练中, 要优化的目标函数一般都可以表示为以下形式:
其中, 函数
针对不同算法, 本文从4个维度——模型特性(目标函数特性)、输入数据特性、算法评价标准(收敛率和扩展性)、所应用平台的计算模型进行说明.下文中, 每类算法的对比分析表格即根据这4个维度, 按照时间顺序对每种算法进行比较.对于表格中的方法一栏, 如果在论文中对算法名称有说明, 则为算法名称加年份; 否则, 为作者姓名加年份.对于表格中的单横线, 表示论文没有分析该维度, 无法客观评价进行填写.下面对各个维度进行介绍.
机器学习问题中建立的优化模型通常可以转换为一个目标函数, 因此, 模型特性即指目标函数特性, 是优化算法要解决的目标.本文将目标函数按照属性特征分为凸函数和非凸函数两大类, 其中, 凸函数分为强凸函数与非强凸函数:强凸是指在到达极小值区域时函数曲线陡峭, 而非强凸函数是指在到达极小值区域时函数曲线平缓.传统的机器学习问题通常为凸函数优化问题, 其又可细分为对变量有约束的凸函数和对变量无约束的凸函数.凸函数根据多项式各变量是否可以求导分为可微和不可微凸函数, 其中, 函数连续可微则称函数平滑.神经网络相关的深度学习问题的损失函数通常为非凸函数, 由于目前非凸函数的优化算法的理论研究较少, 本文仅包含几种深度学习领域中的非凸函数优化算法.
目标函数从组成上包含损失函数和正则项, 其中, 损失函数表示真实值与拟合函数值之间的差值; 正则项是对模型参数规范化, 从而达到避免函数过拟合或者简化函数的目的.损失函数可按照上述函数属性来进行细分.正则项主要分为L1正则项(‖
训练模型输入样本数据的不同将带来不同的运行效果, 是影响算法结果、性能的重要因素.本文按照稀疏性、维数、规模来对数据特性进行评价:稀疏性是指样本特征值非零的比例, 分为稀疏和稠密; 维数是指样本特征的个数, 分为高维和低维; 规模是指模型训练数据样本的多少, 在分布式环境下, 数据规模通常是大规模.
优化算法的评价体系一般包括收敛率、扩展性、时间复杂度、空间复杂度、通信复杂度和结果准确率等.通常, 论文中会证明算法的收敛率, 从理论上说明算法的正确性, 所以, 是否收敛是我们重要的评价标准.部分算法会对扩展性进行说明, 由于如何划分算法来并行更新是并行与分布式实现的重点, 因此, 将扩展性纳入到评价标准中.时间、空间、通信复杂度和结果准确度在大多数优化算法论文中都没有进行理论说明, 但是部分算法在实验验证部分对这些指标进行了对比.由于机器学习问题与实验数据有关, 不同的实验数据所需要的循环迭代次数、运行结果会有所不同, 部分数据的结果对这些指标概括性不足会造成以偏概全, 因此, 我们不对这些指标进行详细分析.
收敛率是指连续两次误差的比值的极限, 可以表示为下式:
其中,
(1) 如果
(2) 如果
(3) 如果
扩展性是指算法是否随着线程的增加, 或者系统的物理(内、外存)资源、计算框架的扩展, 或者样本数据的增加达到一定程度的加速比, 其中, 加速比是指同一个任务在单处理器系统和并行处理器系统中运行所消耗的时间的比率, 用来衡量并行系统或程序并行化的性能和效果.
(1) 线性加速比是指
(2) 超线性加速比是指
(3) 病态加速比是指
并行计算模型是并行算法设计和分析的基础.为提高系统性能, 研究者们提出多种并行计算模型:第1代为单机多核环境下的共享存储计算模型; 第2代为分布式存储模型, 包括整体同步并行计算模型(BSP)[
本节简要介绍梯度下降算法[
梯度下降法是求解无约束优化问题最常用的方法, 存在大量改进的算法变种.梯度下降法是沿梯度下降的方向, 即以负梯度方向作为搜索方向, 不断迭代求解目标函数的最优值.由于梯度下降法需要求解目标函数导数, 因此理论上, 梯度下降法主要解决可微凸函数.当目标函数为连续可微强凸函数时, 算法是线性收敛的.当放松目标函数属性条件为利普希茨连续凸函数时, 收敛率会降低至次线性.
梯度下降法的计算过程如下.
(1) 对参数
(2) 改变
其中,
(3) 将
在原始梯度下降法中, 由于需要计算所有样本的梯度, 耗时大、易陷入局部最优解等问题, 相继有研究者提出批量梯度下降法(batch GD)[
二阶优化算法与梯度下降法的问题域相同, 但梯度下降法主要利用目标函数的局部性质, 即求解目标函数的一阶导数, 具有一定的“盲目性”.二阶优化算法的代表算法——牛顿法, 利用目标函数的一阶和二阶导数信息, 带有一定的全局性, 因此牛顿法的收敛速率更快.当目标函数二阶可导且导数连续时可以获得二次收敛率.
牛顿法的计算过程如下.
(1) 将目标函数
(2) 取其前3项, 对方程求导求其最小值, 即
其中, 将函数的二阶导表示为Hesse矩阵(假设其可逆), 函数的一阶导表示为Jacobi矩阵, 上述等式可改写为
(3) 将
原始牛顿法中, 由于Hesse矩阵的逆矩阵可能不存在, 同时, 由于Hesse矩阵计算复杂性高、存储消耗大等原因, 相继有一些研究者提出改进算法, 如阻尼牛顿法、拟牛顿法、L-BFGS算法等[
梯度下降法和二阶优化算法通常只能解决整体可微凸函数, 对于目标函数
则使用次梯度法[
首先定义函数
即, 在当前点
邻近梯度法的计算过程如下.
(1) 对参数
(2) 利用邻近点梯度算法的迭代公式, 求得新的
通常,
(3) 将
不同于上述算法需要计算目标函数的梯度、存在步长难确定等问题, 坐标下降法是一种非梯度优化算法, 并且不用设定步长.在每次迭代中, 在当前点处沿一个坐标方向进行一维线搜索, 固定其他坐标方向, 以求得目标函数的一个局部最小值, 循环使用不同的坐标方向.一个周期的一维搜索迭代过程相当于一个梯度迭代.当目标函数连续可微且每个子问题均可解或非平滑部分可分离时, 算法是次线性收敛.
坐标下降法的计算过程如下.
(1) 沿一个方向寻求多变量目标函数
(2) 循环最小化各个坐标方向上的目标函数值:
(3) 从一个初始的
(4) 将
原始坐标下降法中, 按序求解每一维的最小值可能最终的结果并不是全局最优解.如何选择求解方向, 使得目标函数结果最优, 相继有研究者提出随机坐标法[
上述算法通常解决无约束问题.对于有约束的凸函数问题, Gabay和Mercier[
其中,
不断循环迭代公式(14)~公式(16), 直至收敛.当目标函数为闭实集上的凸函数时为次线性收敛.同时, 该形式便于在对目标函数更一般的属性条件下并行优化, 因此, ADMM适用于大规模分布式优化问题.
优化算法对比
Comparison of optimization algorithms
算法 | 优势 | 不足 | 收敛率适用范围 |
梯度下降法 |
(1)求解方法简单, 只需求解函数的一阶导数 |
(1)步长难以确定 |
(1)目标函数为平滑强凸函数时线性收敛 |
二阶优化算法 |
(1)严格局部极小值附近收敛很快 |
(1)二阶导退化, 牛顿法将失效 |
目标函数为二阶可导, 导数连续的凸函数, 同时, 函数的Hesse矩阵正定且存在局部极小值时超线性收敛 |
邻近梯度法 |
可以解决由函数非平滑带来的不可求导问题 | (1)步长难以确定 |
目标函数为具有利普希茨连续导数的平滑凸函数与非平滑凸函数之和时次线性收敛 |
坐标下降法 |
(1)不用设定初始步长 |
(1)目标函数不可分时, 无法在较小的迭代步数得到最优解 |
(1)目标函数连续可微凸且每个子问题均可解时次线性收敛 |
交替方向乘子法 |
(1)融合对偶分解和Lagrange乘子法优点, 适合分布式并行求解 |
在高精度要求下, 算法收敛很慢 | 目标函数为非空闭实集上的凸函数, 且增广Lagrangian算子有鞍点时次线性收敛 |
随着单机多核系统的发展, 处理器写共享内存速度可达12GB/s, 延迟可达纳秒级别, 并行计算的优势逐渐得到体现[
并行计算模型作为并行算法设计和分析的基础, 本节主要介绍与论文中优化算法实现相关的流行的并行计算模式, 即共享存储、BSP、SSP和ASP计算模型.
共享存储计算模型即为共享内存模型, 其计算模型如
共享存储计算模型
Shared memory model
某个进程对共享内存中数据的改动, 将立即影响到可以访问同一段共享内存的任何其他进程.数据的共享不需要进程间的数据传送, 而是直接访问内存, 加快了程序效率.共享存储模型根据多线程锁机制又可细分为同步、异步模式.结合数据划分, 同步模式可解释为:各线程利用部分数据对全局模型参数进行计算, 计算完成后, 将结果同步到共享内存中进行聚合操作; 随后, 各线程读取更新后的全局参数.结合模型划分、异步模式可解释为:各线程更新部分模型参数, 计算完成后即更新共享内存中参数的值, 其他线程在下一次读取模型参数时, 可直接读取到更新的参数.由于目前普通机器均为多核CPU, 因此大多分布式系统中的单一节点也均采用这种计算模型.
整体同步并行计算模型BSP(bulk synchronous parallel)是由一组具有局部内存的分布式处理器和支持所有处理单元间全局同步的路障组成, 其计算模型如
整体同步并行计算模型
Bulk synchronous parallel model
异步并行计算模型ASP(asychronous parallel)是由具有局部内存的分布式处理器和管理全局参数的总节点组成, 其计算模型如
异步并行计算模型
Asynchronous parallel model
异步更新流程为:各节点以不同步调在主节点上对模型进行更新.结合数据划分可解释为:各节点利用本地数据对全部模型参数进行计算, 节点计算完一轮后, 即可在主节点处对模型进行参数更新, 然后从主节点处获取最新全局参数进行下一轮更新, 各节点不需要互相等待.但是对各节点的迭代轮数差不加限制会造成结果最终不收敛, 为了解决ASP模型计算结果的不稳定性, 提出下面的延迟同步并行计算模型.
延迟同步并行计算模型SSP(staleness synchronous parallel)是由具有局部内存的分布式处理器、总节点和延迟参数(stale)组成, 其计算模型如
延迟同步并行计算模型
Staleness synchronous parallel model
并行GD算法的优化主要基于多线程不同的锁操作模式进行改进.通过对共享内存中管理全局模型的锁机制进行优化, 从而加快算法的运行速度.
John等人提出的Round-robin[
由于Round-robin的加锁并发控制使得算法收敛速率较慢, Niu等人提出了无锁并行随机梯度下降算法Hogwild![
针对Hogwild!只能获取次线性的收敛率, Zhao等人提出了无锁线性收敛的AsySVRG[
并行梯度下降算法对比
Comparison of parallel gradient descent algorithms
方法 | 模型 | 数据特性 | 评价标准 | 计算模型 | ||
目标函数类型 | 正则项 | 收敛率 | 扩展性 | |||
Round-Robin, 2009 | 每个函数凸 | L1, L2 | 高维数据集 | 次线性 | 当梯度计算时间远大于参数更新时间有线性加速比 | 同步共享内存模型 |
Hogwild!, 2011 | 函数整体强凸, 连续可微 | L1, L2 | 稀疏高维数据集 | 次线性 | 线性 | 添加部分写锁的异步共享内存模型 |
AsySVRG, 2016 | 函数整体强凸, 子函数平滑凸 | L1, L2 | - | 线性 | 在大规模数据集上具有线性加速比 | 异步共享内存模型 |
分布式GD算法主要是对标准SGD算法、异步SGD算法、噪声削减方法的分布式实现, 以及对提高结果准确度及运行效率等其他方面的优化进行改进.
在标准SGD算法的基础上, Martin等人开创性地提出了基于MapReduce计算模型的分布式SGD算法[
在标准SGD的迭代过程中, 同步往往造成较大的延迟.为了避免这个问题, Meng等人提出异步SGD算法AASGD[
由于标准SGD易受噪声梯度影响而降低收敛速度, 于是, 基于SGD的噪声去除方法大量涌现.基于原始单线程去噪方法SVRG, Jason等人提出分布式去噪随机梯度下降法DSVRG[
为了提高标准SGD算法的准确度和效率, Zhang等人提出了Splash[
分布式梯度下降算法对比
Comparison of distributed gradient descent algorithms
方法 | 模型 | 数据特性 | 评价标准 | 计算模型 | ||
目标函数类型 | 正则项 | 收敛率 | 扩展性 | |||
SGD, 2010 | 凸函数 | L1, L2 | 大规模稀疏高维数据集 | 次线性 | 近线性 | 基于MapReduce计算模型 |
DSVRG, 2015 | 每个子函数凸 | L1, L2 | 大规模数据集 | 线性 | 没有理论保证扩展至上百个节点可以得到线性加速比 | 整体同步并行计算模型 |
CentralVR, 2016 | 函数整体强凸 | L1, L2 | 大规模数据集 | 线性 | 随节点数线性扩展 | 整体同步并行计算模型或异步并行计算模型 |
Splash, 2016 | 函数整体平滑强凸 | L1, L2 | 大规模高维数据集 | 线性 | - | 整体同步并行计算模型 |
AASGD, 2016 | 每个子函数平滑凸 | L2 | 大规稠密集高维数据集 | 线性 | 节点数在1~16之间, 加速比介于平方根和线性加速之间.扩展至上百个节点时没有保证 | 异步并行计算模型 |
SCOPE, 2017 | 函数整体强凸 | L1, L2 | 大规模数据集 | 线性 | 线性 | 整体同步并行计算模型 |
并行二阶优化算法主要对原始的牛顿法及其变种进行改进, 利用数据特征划分使得算法适用于多核环境, 从而解决应用问题.原始的截断牛顿法运用于非线性网络优化问题中, Stephen等人提出改进后的截断牛顿法使其适用于大规模问题的求解[
并行二阶优化算法对比
Comparison of parallel second order optimization algorithms
方法 | 模型 | 数据特性 | 评价标准 | 计算模型 | ||
目标函数类型 | 正则项 | 收敛率 | 扩展性 | |||
Stephen, 1989 | 平滑凸/非凸函数 | - | 大规模数据集 | 数据维度固定, 当处理器个数增加时, 收敛率为超线性或二次; 当处理器个数固定、数据维度增加时, 收敛率将从超线性变为线性 | - | 同步共享内存模型 |
Stavros, 1992 | 凸函数 | - | 大规模稀疏数据集 | 超线性 | - | 同步共享内存模型 |
原始牛顿法中, 由于二阶导数Hesse矩阵过于庞大, 使得计算、存储、通信成为算法瓶颈, 因此, 其分布式优化主要关注于减少Hesse矩阵的计算、存储和通信消耗.
在大规模逻辑回归问题, 即目标函数为凸函数的问题中, Lin等人发现:对于梯度难以收敛到最优以及目标函数二阶导数Hesse矩阵太大难以存储的情况, 分别可以通过信任域方法和共轭梯度迭代法来解决.因此, Lin等人提出信任域牛顿法[
对于平滑凸函数, 为了获得更好的通信效率, Zhang等人提出分布式不精确阻尼牛顿法DISCO[
分布式二阶优化算法对比
Comparison of distributed second order optimization algorithms
方法 | 模型 | 数据特性 | 评价标准 | 计算模型 | ||
目标函数类型 | 正则项 | 收敛率 | 扩展性 | |||
Lin, 2007 | 二次可导凸函数 | L2 | 大规模稀疏高维数据集 | 二次 | - | 整体同步并行计算模型 |
L-BFGS | 可微凸函数 | L2 | 大规模稀疏高维数据集 | 超线性 | - | 整体同步并行计算模型 |
VL-BFGS, 2014 | 可微凸函数 | L2 | 大规模高维数据集 | 超线性 | 强扩展性 | 基于Map-Reduce的计算模型 |
DISCO, 2015 | 二次连续可微凸函数 | L2 |
大规模高维数据集 | 超线性 | - | 整体同步并行计算模型 |
并行邻近梯度法主要用来解决应用问题, 在多核环境下, 对数据特征进行拆分来加速求解过程.Pustelnik等人将邻近梯度法应用于噪音图像处理领域[
并行邻近梯度算法对比
Comparison of parallel proximal gradient algorithms
方法 | 模型 | 数据特性 | 评价标准 | 计算模型 | ||
目标函数类型 | 正则项 | 收敛率 | 扩展性 | |||
Accelerated PPXA, 2011 | 凸函数 | 不可微函数 | 稀疏数据集 | 次线性 | - | 同步共享内存模型 |
Kamilov, 2016 | 凸函数 | L1 | 稀疏数据集 | 超线性 | - | 同步共享内存模型 |
分布式邻近梯度法主要是基于不同的并行计算模型, 针对数据不均衡等问题进行优化以及分布式实现, 从而提高算法运行效率.
在分布式计算环境中, 各节点数据的差异可能带来各节点计算结果的不均衡, 从而影响最终结果.Chen等人针对该问题提出快速分布式邻近梯度法Accelerated PG[
上述优化工作基于同步并行计算模型, 随后, 诸多学者对邻近梯度法进行异步、半异步计算模型下的分布式优化.在延迟同步模型下, Li等人基于参数服务器提出分布式延迟同步邻近梯度法[
分布式邻近梯度算法对比
Comparison of distributed proximal gradient algorithms
方法 | 模型 | 数据特性 | 评价标准 | 计算模型 | ||
目标函数类型 | 正则项 | 收敛率 | 扩展性 | |||
Accelerated PG, 2012 | 凸函数=可微子函数+全局不可微函数 | L1 | 高维数据集 | 次线性 | - | 整体同步并行计算模型 |
MuLi, 2013 | 连续可微+块可分凸函数 | L1 | 大规模稀疏高维数据集 | 如果延迟参数在限制范围内, 即可收敛 | - | 基于参数服务器的延迟同步模型 |
Prox-SVRG, 2014 | 强凸函数=平滑凸+凸函数 | L1, L2 | 大规模数据集 | 线性 | - | 整体同步并行计算模型 |
DFAL, 2015 | 有约束的凸函数=平滑凸+非平滑凸 | L1 | 大规模稀疏数据集 | 算法精度 |
精度与扩展性满足 |
去中心化异步模型 |
msPG, 2016 | 平滑凸+非平滑凸函数 | 非平滑如L1 | 大规模高维数据 | 次线性 | - | 延迟同步并行模型 |
并行CD算法主要是对传统单线程下的随机坐标下降法[
对于随机坐标下降法, 原始的串行随机坐标下降法是每轮迭代随机地从所有特征中选取一维特征进行更新, 多轮迭代直到收敛.Bradley等人基于原始随机坐标下降法提出并行随机坐标下降算法Shotgun[
随机坐标下降法是随机地选择特征进行更新, 在特征关联的情况下并行更新会出现收敛速度慢甚至发散的问题, 贪婪坐标下降法对其进行了改进:选择可以迅速减少目标函数值的特征进行模型更新.Scherrer等人提出块-贪婪坐标下降算法族Block-Greedy CD[
Liu等人将坐标下降法与邻近梯度法相结合, 提出异步随机邻近坐标下降算法ASYSPCD[
由于同步环境下并行对偶坐标下降法收敛速度慢, Hsieh等人提出了异步并行随机对偶坐标下降算法PASS-CoDe[
并行坐标下降算法对比
Comparison of parallel coordinate descent algorithms
方法 | 模型 | 数据特性 | 评价标准 | 计算模型 | ||
目标函数类型 | 正则项 | 收敛率 | 扩展性 | |||
Shotgun, 2011 | 凸函数 | L1 | 高维数据集 | 次线性 | 近线性 | 异步共享内存模型 |
PCDM, 2012 | 可分平滑凸+可分凸函数 | 凸函数 | 稀疏数据集 | 线性 | 当函数可分, 线性加速比 | 同步共享内存模型 |
Block-Greedy CD, 2012 | 可微凸函数 | L1 | 高维数据集 | 收敛率依赖于坐标块的谱半径 | - | 同步共享内存模型 |
AsySPCD, 2014 | 平滑凸+可分凸函数 | 凸函数 | 大规模稀疏数据集 | 目标函数强凸, 则线性; 目标函数一般凸, 则次线性 | 处理器个数为 |
异步共享内存模型 |
AsySCD, 2015 | 平滑无约束或者有约束可分凸函数 | L1 | 稀疏数据集 | 目标函数强凸, 则线性; 目标函数一般凸, 则次线性 | 处理器个数为 |
异步共享内存模型 |
PASS-CoDe, 2015 | 平滑凸函数 | L2 | 大规模稀疏数据集 | 线性 | - | 异步共享内存模型 |
AGCD, 2016 | 有约束的平滑凸函数 | - | 大规模稠密数据集 | 线性 | 增加线程数量, 有强扩展性 | 异步共享内存模型 |
线性支持向量机(SVM)、线性回归(Lasso)等模型是处理大规模稀疏高维数据应用的很好的工具, 而坐标下降法可以利用分块求解的特性去求解高维数据模型.因此, 在大数据环境下, 优化集中在对其变种——随机对偶坐标下降法、块坐标下降、混杂优化以及网络扩展上的改进, 从而更好地求解线性SVM和Lasso模型.
SVM模型通常利用对偶坐标下降法求解, Hsieh等人提出改进版的分布式对偶坐标下降法DCD-SVM[
对于Lasso模型求解, Mahajan等人提出了分布式块坐标下降法DBCD[
对于广义线性模型, 收敛率通常会随着集群节点的数目而发生变化.同时, 当集群数量发生变化时, 分布式随机梯度法不能随着节点的增加而呈线性扩展, 尤其是在共享云环境下, 很难预测算法运行效率等.因此, Steffen等人提出了可扩展坐标下降法SCD[
分布式坐标下降算法对比
Comparison of distributed coordinate descent algorithms
方法 | 模型 | 数据特性 | 评价标准 | 计算模式 | ||
目标函数类型 | 正则项 | 收敛率 | 扩展性 | |||
DCD-SVM, 2008 | 非强凸函数 | L1, L2 | 稀疏高维数据集 | 为达到 |
- | 整体同步并行计算模型 |
DisDCA, 2013 | 利普希茨连续凸+连续可微凸函数 | L1, L2 | 大规模高维数据集 | 线性 | 趋近于线性 | 整体同步并行计算模型 |
COCOA, 2014 | 利普希茨连续凸函数 | L2 | 大规模数据集 | 线性 | - | 整体同步并行计算模型 |
DBCD, 2015 | 连续可微凸函数 | L1 | 稀疏高维数据集 | 线性 | 随着节点的增多, 无线性加速比 | 整体同步并行计算模型 |
Hydra, 2016 | 平滑凸+凸函数 | L1, L2 | 大规模高维数据集 | 次线性 | 当数据的谱范数较小时, 增加处理器个数, 加速比可达近线性 | 整体同步并行计算模型 |
SCD, 2016 | 凸函数 | L1, L2 | 大规模稀疏数据集 | 次线性 | 线性 | 整体同步并行计算模型 |
ADMM算法独特的分布式结构使其非常适用于分布式环境, 通常用来并行求解大规模问题.因此, 本文只对ADMM算法的分布式改进加以总结.
在分布式环境下, ADMM算法的优化不关注于算法结构的改变, 主要关注于如何结合不同的体系结构进行算法的部署及应用, 包括主从网络(中心化)结构下以及去中心化(图)结构下的同步和异步更新.
基于主从结构的同步计算模型, Sauptik等人[
主从结构下的计算模型总会存在延迟等待、单节点压力过大等问题, 因此, 诸多学者对ADMM算法的去中心化分布式优化展开研究.
对于有约束的强凸目标函数, Shi等人提出去中心双边图模型下的分布式ADMM算法[
对于有线性约束的可分目标函数, Wei等人提出了基于边通信的去中心化异步ADMM算法[
ADMM算法通常求解有约束问题, 而Wei等人利用ADMM算法求解无约束问题, 提出了基于节点排序的分布式ADMM算法[
除了传统机器学习的凸函数问题外, ADMM算法也可用于神经网络非凸函数的训练.针对大规模数据集、集群, 传统的随机梯度优化方法对非凸函数不能很好地加以扩展, Gavin等人提出, 将ADMM算法与Bregman方法迭代地结合起来[
分布式交替方向乘子算法对比
Comparison of distributed alternating direction method of multipliers algorithms
方法 | 模型 | 数据特性 | 评价标准 | 计算模式 | ||
目标函数类型 | 正则项 | 收敛率 | 扩展性 | |||
Wei E, 2012 | 无约束凸函数 | - | 大规模数据集 | 次线性 | - | 相邻节点异步并行计算模型 |
Async-ADMM, 2012 | 凸函数 | 凸函数 | 大规模高维数据集 | 次线性 | 每轮迭代中节点数越多运行时间越少 | 延迟同步并行计算模型 |
Shi Wei, 2013 | 有线性约束的强凸函数 | - | 维数适中 | 线性 | - | 去中心化异步并行计算模型 |
D-ADMM, 2013 | 有约束的强凸函数 | L1 | 大规模稀疏数据集 | 线性 | - | 相邻节点异步并行计算模型 |
Wei E, 2013 | 有线性约束的凸函数 | - | - | 次线性 | - | 基于边通信的异步图计算模型 |
Ali Makhdoumi, 2014 | 有线性约束的凸函数 | L2 | 大规模稀疏数据集 | 次线性 | - | 基于顶点广播通信的异步图计算模型 |
ADMM on Spark, 2015 | 凸函数 | 凸函数 | - | 次线性 | - | 整体同步并行计算模型 |
Gavin Taylor, 2016 | 非凸函数 | L2 | 大规模数据集 | 次线性 | 线性 | 整体同步并行计算模型 |
为了应对大数据机器学习问题, 出现了一批采用分布式架构的可扩展的机器学习系统.分布式架构大致可以分为两类:第1类是不含参数服务器架构的系统, 其大多为整体同步并行计算模型; 第2类是采用参数服务器架构的系统, 也是目前机器学习系统的主流发展方向, 主要为延迟同步并行计算模型.在原始的主从架构平台中, 从节点在完成计算后需要和主节点进行交互.然而在大数据环境下, 单一节点难以存储大规模参数集, 同时对节点通信、参数计算等造成单点瓶颈, 因此, 为应对分布式环境下的大规模数据集, 参数服务器架构应运而生.参数服务器架构是指模型的参数采用一个统一的分布式服务器组作为主节点来进行存储管理, 参数服务器组中的每个服务器分别对应不同的从节点组, 从而不存在单点故障.由于算法的实现离不开平台, 因此, 本节对分布式平台进行简介, 包括其实现的适用于该系统的分布式优化算法, 并总结分析不同平台中算法的应用场景.
第1类中, 基于整体同步并行计算模型的机器学习系统主要包括Hadoop Mahout[
第2类机器学习系统都采用参数服务器架构加SSP更新策略, 主要包括CMU的Parameter Server[
综合来看, 大多数分布式机器学习平台都实现了SGD算法, 但是仅限于基本的Mini-Batch SGD, 用于求解机器学习问题.其中, 新一代的机器学习平台都采用了分布式参数服务器架构, 实现了数据并行和模型并行, 这些架构本身就是一种新的算法实现, 不同于本文前面介绍的算法理论.从深度学习角度来看, 由于非凸函数的求解理论研究不足, 目前, 实验结果表明, 添加自适应学习率的SGD算法可以满足求解要求, 是主流的方法.Google Distbelief和Spark MLlib都还实现了L-BFGS算法, 同时, 实验结果还表明:在一些情况下, 其运行效率要优于SGD.但是, 为了避免系统过于复杂, Tensorflow并未实现L-BFGS算法.虽然各个平台都可以解决机器学习问题, 但是具体问题的求解需要考虑具体的应用场景, 例如数据特性、数据规模、运行结果需求等.同时, 可以结合具体系统的特性与其已有的优化算法来进行平台与算法的选择.例如, 想要保证结果的准确性, 对运行时间没有太高要求, 则可优先选择BSP模型的平台.对于决定了运行平台, 选择哪种优化算法来求解具体模型, 可根据求解模型和数据的特性来选择优化算法.例如, 如果模型是SVM, 则可选择实现坐标下降法; 如果带有约束条件, 则可选择ADMM算法.
现有机器学习平台优化算法实现情况
Implementation of optimization algorithms on existing machine learning platforms
通信模式 | 系统 | 内置算法 | |
无参数服务器架构 | 主从架构机器学习系统 | Mahout | SGD |
Spark | Mini-BatchSGD, PG, L-BFGS | ||
图架构机器学习系统 | GraphLab | Mini-BatchSGD, Bias-SGD | |
参数服务器架构 | 通用机器学习系统 | Parameter server | Mini-Batch SGD |
Petuum | Mini-BatchSGD | ||
Angel | SGD, Hogwild! | ||
深度学习系统 | DistBelief | Downpour SGD, L-BFGS | |
Tensorflow | SGD, Adadelta_SGD, Adam_SGD, Adagrad_SGD, Momentum_SGD, Ftrl_SGD, RMSProp_SGD | ||
MxNet | Mini-Batch SGD, PG |
飞速增长的数据量使得模型处理需要更快的速度, 机器学习算法的效率是最关键的问题之一.而机器学习算法的效率更多地依赖于优化方法的改进, 因此, 优化算法作为机器学习的重要组成部分, 近年来在并行与分布式机器学习领域获得了广泛关注, 取得了诸多研究成果, 得到了快速发展.本文从模型训练优化角度出发, 对梯度下降算法、二阶优化算法、邻近梯度算法、坐标下降算法和交替方向乘子算法这5种不同类型的优化算法的并行与分布式优化策略进行综述.通过层次化分类, 将各种算法按照目标函数类型总结为如
基于目标函数类型的优化算法层次化分类
Hierarchical classification of optimization algorithm by objective functions
图中箭头表示论文中该算法可用于求解此类目标函数, 不代表其不能求解其他类型的目标函数, 只是每一种算法针对目标函数从理论上有一定的优势, 实际应用中的性能还需基于数据集进行评测分析.从图中可知:大部分优化算法求解的问题域与其原始理论解释保持一致, 部分算法突破了原有设定, 进行了相关的改进.通过查看
尽管机器学习优化算法在并行与分布式方面取得了众多的进展, 但仍然存在如下几点不足.
(1) 在算法使用多样性方面.
在现有大规模数据环境下, 应用最广泛、关注最多的优化算法是梯度下降法, 因为其实现简单, 使用场景广泛.但是由于应用的精细化, 不同的应用场景需要不同的机器学习模型, 对于不同的目标函数、数据规模可能需要不同的优化策略, 不能一概而论.然而, 其他优化算法在实际应用中并不常见, 如何结合各种优化算法的特性、提高具体应用的运行效率, 还有待进一步加以研究.
(2) 在算法扩展性方面.
对于分布式算法, 扩展性作为重要指标在现有分布式算法中没有得到重视.随着数据规模的扩大, 在分布式环境下可以配置更多的机器, 如何有效地利用这些计算资源, 分布式机器学习优化算法的可扩展性至关重要.
(3) 在与系统结合方面.
随着集群机器的普通化, 异构环境下不同机器的速度不一, 同步将会造成大量的同步等待, 从而越来越多的研究转变到异步更新策略上.对于更新策略为异步的情况, 高维稀疏数据往往能取得更好的加速效果.因此, 如何更好地利用现有系统、如何将现有算法移植到异步环境下、如何应用到稠密数据上还有待研究.
(4) 在非凸函数优化方面.
现有优化算法的目标函数主要针对凸函数, 然而关注度逐渐升高的深度学习的目标函数主要为非凸函数.目前, 非凸函数的主要求解策略是添加自适应学习率的随机梯度下降法.虽然梯度下降法能够较好地解决问题, 但是对于求解大规模深度学习问题仍存在较大难度, 存在收敛速度较慢等不足.利用其他优化算法求解神经网络相关的非凸函数问题仍有待进一步加以研究.
由于机器学习优化方法的研究方兴未艾, 对其所进行的研究工作尚不完善, 在与平台相结合的并行与分布式方面仍需要做大量工作.未来的研究方向主要可以从如下几个方面加以展开.
(1) 与系统相结合的分布式优化算法.
随着数据体量的增大, 与系统相结合的分布式优化算法进行模型求解将需要更大的内存以及更快的计算效率.然而现有分布式算法大多只是理论研究, 基于真实应用平台的分布式算法研究仍处于探索阶段.未来可以基于真实的分布式机器学习平台运行多种优化算法, 找出影响运行速度的优化算法或平台因素, 从而进行相应的改进.
(2) 与深度学习相关的优化算法.
现有分布式优化算法对非凸函数的研究较少, 主要是利用添加自适应学习率的随机梯度下降法, 但是梯度下降法并不能解决全部的深度学习问题.因此, 针对非凸优化机器学习问题, 还需要大量的理论研究.同时, 还需要基于分布式深度学习平台进行实例测试, 从理论和实践上改进非凸函数的优化求解问题.
综上所述, 现有并行与分布式优化方法已经取得了较好的科研和实际应用成果, 不同的优化算法在并行与分布式环境下针对不同的目标函数有不同的改进, 对于不同的应用也可以得到较高的处理效率, 在实际应用平台上部署效果较好.但仍有创新的空间, 如果在现有优化算法优化策略的基础上, 将优化策略与现有并行与分布式机器学习平台相结合, 推出更加适用于不同应用场景的优化算法, 将会形成更多创新的算法, 有利于大规模机器学习问题的优化求解, 满足实际应用需求, 使其应用前景更加广阔.
Léon B, Frank EC, Jorge N. Optimization methods for large-scale machine learning. arXiv:1606.04838v1, 2016.
Neal P, Stephen B. Proximal algorithms. Foundations and Trends in Optimization, 2014, 1(3):127-239.[doi:10.1561/2400000003]
Stephen JW. Coordinate descent algorithms. arXiv:1502.04759v1, 2015.
Stephen B, Neal P, Eric C, Borja P, Jonathan E. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 2011, 3(1):1-122.
Eric X, Qirong H, Xie PT, Wei D. Strategies and principles of distributed machine learning on big data. Engineering, 2016, 2(2):179-195.[doi:10.1016/J.ENG.2016.02.008]
10.1007/11428848_132]]]>
Nesterov Y. Introductory Lectures on Convex Optimization:A Basic Course. Springer-Verlag, 2004. ⅹⅷ-236.
Meng XR, Joseph B, Burak Y, Evan S, Shivaram V, Davies L, Jeremy F, DB T, Manish M, Sean O, Doris X, Reynold X, Michael JF, Reza Z, Matei Z, Ameet T. MLlib:Machine learning in apache spark. The Journal of Machine Learning Research, 2016, 17(1):1235-1241.
http://papers.nips.cc/paper/4006-parallelized-stochastic-gradient-descent.pdf]]>
http://papers.nips.cc/paper/772-optimal-stochastic-search-and-adaptive-momentum.pdf]]>
http://papers.nips.cc/paper/4937-accelerating-stochastic-gradient-descent-using-predictive-variance-reduction.pdf]]>
http://papers.nips.cc/paper/5258-saga-a-fast-incremental-gradient-method-with-support-for-non-strongly-convex-composite-objectives.pdf]]>
Nicol S, Yu J, Simon G. A stochastic quasi-newton method for online convex optimization. The Journal of Machine Learning Research, 2007, 2:436-443.
Goldfarb D. A family of variable metric updates derived by variational means. Mathematics of Computation, 1970, 24(109):23-26.[doi:10.1090/S0025-5718-1970-0258249-6]
Liu DC, Nocedal J. On the limited memory BFGS for large scale optimization. Mathematical Programming, 1989, 45(1):503-528.[doi:10.1007/BF01589116]
Combettes PL, Wajs VR. Signal recovery by proximal forward-backward splitting. Multiscale Modeling & Simulation, 2005, 4(4):1168-1200.[doi:10.1137/050626090]
Ram SS, Nedich A, Veeravalli VV. Incremental stochastic subgradient algorithms for convex optimization. SIAM Journal on Optimization, 2009, 20(2):691-717.[doi:10.1137/080726380]
Luo ZQ, Tseng P. On the convergence of the coordinate descent method for convex differentiable minimization. Journal of Optimization Theory and Applications, 1992, 72(1):7-35.[doi:10.1007/BF00939948]
Nesterov Y. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 2012, 22(2):341-362.[doi:10.1137/100802001]
http://papers.nips.cc/paper/4425-nearest-neighbor-based-greedy-coordinate-descent.pdf]]>
Canutescu A, Dunbrack R. Cyclic coordinate descent:A robotics algorithm for protein loop closure. Protein Science, 2003, 12(5):963-972.[doi:10.1110/ps.0242703]
Zhao SY, Xiang R, Shi YH, Gao P, Li WJ. SCOPE:Scalable composite optimization for learning on spark. In:Proc. of the Association for the Advancement of Artificial Intelligence. 2017. 2928-2934.
http://papers.nips.cc/paper/4894-more-effective-distributed-ml-via-a-stale-synchronous-parallel-parameter-server.pdf]]>
Mu L, David A, Jun P, Alexander S, Amr A, Vanja J, James L, Eugene S, Bor-Yiing S. Scaling distributed machine learning with the parameter server. OSDI, 2014, 1(10.4):3.[doi:10.1145/2640087.2644155]
Chen TQ, Li M, Li YT, Lin M, Wang NY, Wang MJ, Xiao TJ, Xu B, Zhang CY, Zhang Z. MXNet:A flexible and efficient machine learning library for heterogeneous distributed systems. arXiv:1512.01274, 2015.
http://papers.nips.cc/paper/4687-large-scale-distributed-deep-networks.pdf]]>
https://www.usenix.org/system/files/conference/osdi16/osdi16-abadi.pdf]]>
https://papers.nips.cc/paper/3888-slow-learners-are-fast.pdf]]>
http://papers.nips.cc/paper/4390-hogwild-a-lock-free-approach-to-parallelizing-stochastic-gradient-descent.pdf]]>
http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/download/12442/11887]]>
https://www.ijcai.org/Proceedings/16/Papers/265.pdf]]>
10.1109/ICDM.2016.0022]]]>
Zhang YC, Michael IJ. Splash:User-Friendly programming interface for parallelizing stochastic algorithms. arXiv:1506.07552, 2015.
10.1145/2939672.2939790]]]>
Stavros Z, Mustafa CP. Parallel block-partitioning of truncated newton for nonlinear network. SIAM Journal on Scientific and Statistical Computing, 1992, 13(5):1173-1193.[doi:10.1137/0913068]
10.1145/1390681.1390703]]]>
http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf]]>
Zhang YC, Lin X. DiSCO:Distributed optimization for self-concordant empirical loss. The Journal of Machine Learning Research, 2015, 37:362-370.
Nelly P, Caroline C, Jean-Christophe P. Parallel proximal algorithm for image restoration using hybrid regularization. IEEE Trans. on Image Processing, 2011, 20(9):2450-2462.[doi:10.1109/TIP.2011.2128335]
10.1109/ICASSP.2016.7472568]]]>
Kamilov US. A parallel proximal algorithm for anisotropic total variation minimization. IEEE Trans. on Image Processing, 2017, 26(2):539-548.[doi:10.1109/TIP.2016.2629449]
10.1109/Allerton.2012.6483273]]]>
Lin X, Zhang T. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 2014, 24(4):2057-2075.[doi:10.1137/140961791]
http://www.cs.cmu.edu/afs/cs/user/muli/www/file/ddp.pdf]]>
Zhou Y, Yu YL, Dai W, Liang YB, Eric X. On convergence of model parallel proximal gradient algorithm for stale synchronous parallel system. The Journal of Machine Learning Research, 2016, 51:713-722.
Aybat NS, Wang Z, Iyengar G. An asynchronous distributed proximal gradient method for composite convex optimization. arXiv:1409.8547v2, 2015.
Mota JF, Xavier JM, Aguiar PM, Püschel M. D-ADMM:A communication-efficient distributed algorithm for separable optimization. IEEE Trans. on Signal Processing, 2013, 61(10):2718-2723.[doi:10.1109/TSP.2013.2254478]
Peter R, Martin T. Parallel coordinate descent methods for big data optimization. Mathematical Programming, 2016, 156(1-2):433-484.[doi:10.1007/s10107-015-0901-6]
Liu J, Stephen JW, Christopher R, Victor B, Srikrishna S. An asynchronous parallel stochastic coordinate descent algorithm. The Journal of Machine Learning Research, 2015, 16(1):285-322.
http://papers.nips.cc/paper/4674-feature-clustering-for-accelerating-parallel-coordinate-descent.pdf]]>
Scherrer C, Tewari A, Halappanavar M, Haglin D. Scaling up coordinate descent algorithms for large L1 regularization problems. In:Proc. of the 29th Int'l Conf. on Machine Learning. Omnipress, 2012. 355-362.
http://papers.nips.cc/paper/6070-asynchronous-parallel-greedy-coordinate-descent.pdf]]>
Liu J, Stephen JW. Asynchronous stochastic coordinate descent:Parallelism and convergence properties. SIAM Journal on Optimization, 2015, 25(1):351-376.[doi:10.1137/140961134]
Hsieh CJ, Yu HF, Dhillon IS. PASSCoDe:Parallel asynchronous stochastic dual co-ordinate descent. The Journal of Machine Learning Research, 2015, 37:2370-2379.
10.1145/1390156.1390208]]]>
http://papers.nips.cc/paper/5114-trading-computation-for-communication-distri-buted-stochastic-dual-coordinate-ascent.pdf]]>
Yang TB, Zhu SH, Jin R, Lin YQ. Analysis of distributed stochastic dual coordinate ascent. arXiv:1312.1031, 2013.
http://papers.nips.cc/paper/5599-communi-cation-efficient-distributed-dual-coordinate-ascent.pdf]]>
Mahajan D, Keerthi SS, Sundararajan S. A distributed block coordinate descent method for training L1 regularized linear classifiers. arXiv:1405.4544, 2014.
10.1109/BigData.2015.7363871]]]>
Stephen GN, Ariela S. Block truncated-newton methods for parallel optimization. Mathematical Programming, 1989, 45(1):529-546.[doi:10.1007/BF01589117]
Gavin T, Ryan B, Xu Z, Bharat S, Ankit P, Tom G. Training neural networks without gradients:A scalable ADMM approach. The Journal of Machine Learning Research, 2016, 48:2722-2731.
http://proceedings.mlr.press/v32/zhange14.pdf]]>
10.1109/TSP.2014.2304432]]]>
Bradley JK, Kyrola A, Bickson D, Guestrin C. Parallel coordinate descent for L1-regularized loss minimization. arXiv:1105.5379, 2011.
10.1109/GlobalSIP.2013.6736937]]]>
10.1109/ALLERTON.2014.7028466]]]>
10.1109/CDC.2012.6425904]]]>
Peter R, Martin T. Distributed coordinate descent method for learning with big data. The Journal of Machine Learning Research, 2016, 17(1):2657-2681.
https://arxiv.org/ftp/arxiv/papers/1408/1408.2041.pdf]]>