本文讨论最小二乘拟合问题的并行优化方法,对突破大数据环境下机器学习的计算瓶颈有重要帮助和启示。提出的最大分划松弛交替方向乘子法(MS-RADMM)算法,是对交替方向乘子法(ADMM)的一个有趣扩展。MS-RADMM算法在超限学习机(ELM)中的应用,从算法并行结构角度为ELM的并行实现提供一条有效途径。原文链接:/stamp/stamp.jsp?tp=&arnumber=8789676最小二乘拟合问题广泛存在于机器学习、统计分析、信号处理、最优控制等研究和应用领域。用于训练单隐层前馈神经网络(SLFN)的ELM算法,其核心步骤之一是随机产生并固定隐层神经元,之二是求解输出权矩阵优化的最小二乘问题。基于逆矩阵的最小二乘解,使ELM算法高效并易于实现。
但是在大数据环境下,最小二乘拟合问题的求解,仍然面临计算负担过重的挑战。以下文章从并行优化角度出发,应用具有天生并行结构的ADMM方法,提出最小二乘拟合问题的MS-RADMM算法,具有高度的并行性和可扩展性。
ADMM是求解大规模优化问题的一个强有力工具。通过模型分划,ADMM把一个优化问题分解为规模相对较小且可并行执行的多个子问题。论文提出,对最小二乘拟合问题
进行优化模型的最大分划,使每个子问题只含一个优化变量,得到如下最大分划ADMM (MS-ADMM)算法。
MS-ADMM算法的每个迭代步,对变量的更新都可标量化,即可按标量分量同时分别进行。这个标量化特性,使算法具有极高的并行性。若有足够多得处理器来并行更新每个迭代步的所有标量分量,算法的单次循环计算复杂度是M和N的一次方。
论文还提出了一种新的松弛技术,以加速算法的收敛。将这种松弛技术与MS-ADMM结合后,得到MS-RADMM算法。该算法也包含x-更新、y-更新、z-更新和u-更新等4个迭代步,其中的y-更新、z-更新和u-更新与MS-ADMM算法一样,但对x-更新做了如下修改:
论文应用线性系统理论和矩阵谱分析理论,建立了MS-RADMM算法收敛的充分必要条件和线性收敛率,并得到了最优收敛率及对应的算法参数。
将MS-RADMM算法应用到训练SLFN的RELM,即用MS-RADMM求解正则化最小二乘问题
为验证算法性能,在下表的10个基准数据集上进行实验:
在Gisette数据集上,MS-RADMM算法、MS-ADMM算法及最速下降法的收敛曲线如下图。可见,算法是线性收敛的,且比MS-ADMM和最速下降法收敛快。
Gisette数据集上,MS-RADMM算法(C++实现)在有不同数目计算核心的计算机上获得的加速比,与计算核心数的关系接近线性关系,表明算法优良的并行性。
在10个基准数据集上,MS-RADMM获得的训练和测试精度,与基于矩阵逆的方法得到的结果非常接近。
在MATLAB环境下做了GPU加速实验。GPU加速后,MS-RADMM算法的计算时间接近基于矩阵逆的方法,随着数据集规模的增大,计算时间有可能少于基于矩阵逆的方法。
在10个数据集上,MS-RADMM获得的GPU加速比都超过了50,而基于矩阵逆的方法只有10左右,进一步表明MS-RADMM算法具有优良的并行性。
目前的ELM,其目标函数是无约束二次型的,有基于矩阵逆的高效求解方法。当目标函数不是无约束二次型时,基于矩阵逆的方法将失效,这时MS-RADMM算法将更有其用武之地。