推荐星级：
- 1
- 2
- 3
- 4
- 5
可扩展机器学习的并行与分布式优化算法综述
资料介绍
机器学习问题通常会转换成一个目标函数去求解,优化算法是求解目标函数中参数的重要工具.在大数据环境下,需要设计并行与分布式的优化算法,通过多核计算和分布式计算技术来加速训练过程.近年来,该领域涌现了大量研究工作,部分算法也在各机器学习平台得到广泛应用.针对梯度下降算法、二阶优化算法、邻近梯度算法、坐标下降算法、交替方向乘子算法这5类最常见的优化方法展开研究,每一类算法分别从单机并行和分布式并行来分析相关研究成果,并从模型特性、输入数据特性、算法评价、并行计算模型等角度对每种算法进行详细对比.随后,对有代表性的可扩展机器学习平台中优化算法的实现和应用情况进行对比分析.同时,对所介绍的所有优化算法进行多层次分类,方便用户根据目标函数类型选择合适的优化算法,也可以通过该多层次分类图交叉探索如何将优化算法应用到新的目标函数类型.最后分析了现有优化算法存在的问题,提出可能的解决思路,并对未来研究方向进行展望.
部分文件列表
| 文件名 | 大小 |
| 可扩展机器学习的并行与分布式优化算法综述.pdf | 850K |
部分页面预览
（完整内容请下载后查看）软件学报 ISSN 1000-9825, CODEN RUXUEW
Journal of Software,2018,29(1):109-130 [doi: 10.13328/j.cnki.jos.005376]
©中国科学院软件研究所版权所有.
E-mail:
Tel: +86-10-62562563
可扩展机器学习的并行与分布式优化算法综述*
1,2
1,2
1,3
1
亢良伊
,
王建飞
,
刘
杰
,
叶
丹
1(中国科学院 软件研究所 软件工程技术研发中心,北京 100190)
2(中国科学院大学,北京 100190)
3(计算机科学国家重点实验室(中国科学院 软件研究所),北京 100190)
通讯作者: 刘杰, E-mail:
摘
要: 机器学习问题通常会转换成一个目标函数去求解,优化算法是求解目标函数中参数的重要工具.在大数
据环境下,需要设计并行与分布式的优化算法,通过多核计算和分布式计算技术来加速训练过程.近年来,该领域涌
现了大量研究工作,部分算法也在各机器学习平台得到广泛应用.针对梯度下降算法、二阶优化算法、邻近梯度算
法、坐标下降算法、交替方向乘子算法这 5 类最常见的优化方法展开研究,每一类算法分别从单机并行和分布式并
行来分析相关研究成果,并从模型特性、输入数据特性、算法评价、并行计算模型等角度对每种算法进行详细对比.
随后,对有代表性的可扩展机器学习平台中优化算法的实现和应用情况进行对比分析.同时,对所介绍的所有优化算
法进行多层次分类,方便用户根据目标函数类型选择合适的优化算法,也可以通过该多层次分类图交叉探索如何将
优化算法应用到新的目标函数类型.最后分析了现有优化算法存在的问题,提出可能的解决思路,并对未来研究方向
进行展望.
关键词: 机器学习;优化算法;并行算法;分布式算法
中图法分类号: TP181
中文引用格式: 亢良伊,王建飞,刘杰,叶丹.可扩展机器学习的并行与分布式优化算法综述.软件学报,2018,29(1):109-130.
英文引用格式: Kang LY, Wang JF, Liu J, Ye D. Survey on parallel and distributed optimization algorithms for scalable machine
learning. Ruan Jian Xue Bao/Journal of Software, 2018,29(1):109-
Survey on Parallel and Distributed Optimization Algorithms for Scalable Machine Learning
KANG Liang-Yi1,2
,
WANG Jian-Fei1,2
,
LIU Jie1,3
,
YE Dan1
1(Technology Center of Software Engineering, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China)
2(University of Chinese Academy of Sciences, Beijing 100190, China)
3(State Key Laboratory of Computer Science (Institute of Software, The Chinese Academy of Sciences), Beijing 100190, China)
Abstract: 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
* 基金项目: 国家自然科学基金(U1435220); 北京市科技重大项目(D171100003417002); 民航科技重大专项(MHRD20160109)
Foundation item: National Natural Science Foundation of China (U1435220); Beijing Major Science and Technology Projects
(D171100003417002); Civil Aviation Science and Technology Major Project (MHRD20160109)
收稿时间: 2017-05-05; 修改时间: 2017-06-09, 2017-07-05; 采用时间: 2017-08-24; jos 在线出版时间: 2017-10-09
CNKI 网络优先出版: 2017-10-09 16:20:51, http://kns.cnki.net/kcms/detail/11.2560.TP.20171009.1620.003.html
110
Journal of Software 软件学报 Vol.29, No.1, January 2018
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.
Key words: machine learning; optimization algorithm; parallel algorithm; distributed algorithm
机器学习问题通常会转换成一个目标函数去求解,优化算法是求解目标函数中参数的重要工具[1].目前,机
器学习常用的优化算法主要包括梯度下降(gradient decent,简称 GD)算法[1]、二阶优化(second-order)算法[1]、邻
近梯度(proximal gradient,简称 PG)算法[2]、坐标下降(cooridinate decent,简称 CD)算法[3]、交替方向乘子
(alternating direction method of multipliers,简称 ADMM)算法[4],分别适用于不同类型的优化问题:梯度法和二阶
法适用于可微凸函数、邻近梯度法适用于可微凸函数与不可微凸函数的和问题、坐标法适用于不可求导凸函
数问题、交替方向乘子法适用于有约束的凸函数问题.然而,在大数据环境下,单线程优化算法已经不能适应大
规模机器学习应用的需求,基于不同计算模型的并行与分布式优化算法成为研究热点.在多核环境下,研究者们
提出了基于共享存储的并行优化算法,通过对样本数据或者模型参数的划分,使用多线程并行训练更新共享内
存中的模型参数.但是单机存储的数据量非常有限,为了应对大数据量难以存储、单机计算量有限的问题,分布
式优化算法逐渐涌现出来,基于不同的并行计算模型解决多节点任务划分和参数更新的问题,同时尽可能地降
低通信成本.
为研究可扩展机器学习的优化算法在并行与分布式环境下的优化策略,本文对多种机器学习优化算法进
行分析总结.首先介绍本文对算法的分析维度、原始优化算法基本原理和并行计算模型,然后对 GD、Second-
order、PG、CD 和 ADMM 这 5 种优化算法分别从单机多核并行优化和分布式并行优化角度进行阐述,并从模
型特性、输入数据特性、算法评价标准和并行计算模型对每种算法的具体优化策略进行对比分析.通过综述研
究发现:各种优化算法大多是对传统机器学习的凸函数问题进行优化,不同算法再根据自身特点对目标函数的
不同特性进行优化,对于非凸函数的优化求解研究较少;在多核、分布式环境下,基于不同并行计算模型对不同
算法进行改进,通过并行化来提高运行速率,解决大规模数据处理问题;输入数据样本大多具有稀疏性,从而保
证特征之间关联程度较小,便于多节点并行训练更新,保证算法收敛.同时,算法的更新策略需要依赖于不同计
算模型的具体平台,因此,本文分类研究流行的可扩展机器学习系统,总结其中实现的算法,进而了解各优化算
法在目前系统的实际实现和部署情况.最后绘制了根据目标函数进行分类的多层次分类图,对论文中介绍的各
优化算法进行划分,帮助开发者根据目标函数选择优化算法,交叉探索应用优化算法到新的目标函数类型上.
本文第 1 节介绍算法分析维度、原始优化算法和并行计算模型.第 2 节~第 6 节分别综述各优化算法并行
与分布式改进.第 7 节综述现有机器学习系统优化算法实现情况.第 8 节给出全文算法的多层次分类图,对目前
优化算法存在的问题进行分析,并展望未来的研究工作.第 9 节进行总结.
1
基础知识简介
在机器学习的模型训练中,要优化的目标函数一般都可以表示为以下形式:
min J(x,θ) or max J(x,θ),其中, J(x,θ) = f ({xi , yi}iN=1;θ) + r(θ)
(1)
其中,函数 J(θ)为目标函数,f 为表示真实值与拟合值之差的损失函数,r(θ)为正则项(为防止参数过拟合问题)[5]
.
各种优化算法通过不同的方式求解该方程以得到使 J(θ)最优的参数θ.为了更加清晰地理解优化算法的求解过
程,本节首先对优化算法的分析维度进行拆分介绍;随后,从优化算法解决的问题域出发,对 5 种优化算法的原始
单线程版本进行简要介绍,分析对比它们的收敛率、求解优势和存在的不足,为后续的并行与分布式算法改进
提供算法理论基础.同时,在设计并行与分布式算法时,算法需要依赖于具体平台,系统软件层次的并行计算模
全部评论(0)