分布式交替方向乘子法研究.doc

分布式交替方向乘子法研究随着数据信息的爆炸式增长,传统的运行在单机上的机器学习方法不能有效地处理现实应用中的大规模数据,而且分布式数据的集中化处理会造成数据采集的额外开销,这些情况都给大数据分析带来了新的挑战。分布式机器学习是随着"大数据"概念兴起的,而且分布式技术被用来解决大规模机器学习等问题。在众多的分布式算法中,交替方向乘子法(AlternatingDirectionMethodofMultipliers,ADMM)是因其高分解性和收敛性得到广泛的关注。ADMM通过将原始问题转化为全局一致性问题,能够灵活地采用分布式方式解决许多机器学习问题。在分布式ADMM中,计算节点通过训练自己局部模型参数来并行地优化子问题,然后将所有的局部变量合并起来对全局变量进行优化,最后迭代得到全局解。而且许多研究学者已经证明了在一定的假设前提下,ADMM算法具有次线性的收敛率。因此,本文围绕"分布式ADMM研究"这一主线,对分布式ADMM中的关键问题展开了针对性的研究工作,具体而言,本文的主要工作和创新如下:1.分布式机器学习全局一致性框架:为构建分布式机器学习研究框架,本文提出了一个基于分布式交替方向乘子法的全局一致性框架。该框架首先将原始问题拆分成子问题,然后对子问题进行并行优化,最后对子问题的解进行融合得到全局解。该框架为分布式机器学习算法的研究提供了基础,而且全局一致性约束能够使得所有子问题的解达到全局一致。2.基于分组交替方向乘子法的分布式线性分类:为解决分布式线性分类算法存在收效速度慢,时间开销大等问题,本文提出一种新颖的基于分组交替方向乘子法(Group-BasedAlternatingDirectionMethodofMultipliers,GADMM)的方法来解决分布式线性分类问题。为了追求较快的收敛速度和更好的全局一致性,GADMM将原问题转为一系列的中等规模的子问题,而这些子问题可以采用对偶坐标下降方法有效地并行优化。特别地,采用基于模型相似的分组方法,本文将所有的具有相似局部变量的节点分成同一组。在分组层中,局部变量被收集起来生成分组变量,然后采用分组变量来更新全局变量,整个过程迭代重复直至达到全局收敛。理论分析证明GADMM算法具有O(1/k)的收敛率,而且收敛速度比分布式ADMM要快,其中k是外迭代次数。而且实验结果表明GADMM算法能够有效地减少迭代次数,提高收敛速度,从而节省大量的训练时间。该实验结果和理论分析保持一致。3.快速的大规模不平衡数据分布式分类算法:在以往的文献中,首先广泛存在的类不平衡问题并没有得到很好的研究,此外,先前的不平衡分类算法缺少对分布式环境中存在的复杂不平衡问题的研究。针对以上问题,本文阐述了一种分布式数据不平衡的概念,该概念包括三类不平衡问题:单节点正负样本不平衡、节点间样本数目不平衡和节点间数据结构不平衡三个不平衡问题。为了充分地处理不平衡数据同时提高时间效率,本文提出一种有效的基于分组交替方向乘子法的分布式代价敏感分类算法(Cost-SensitiveGroup-BasedAlternatingDirectionMethodofMultipliers,CS-GADMM)。具体地,CS-GADMM将原始问题分割成一系列带有单节点正负样本不平衡问题的子问题,然后,为了减轻由节点间样本数目不平衡问题造成的计算和通信延迟,本文扩展了对偶坐标下降方法对子问题进行优化。同时,对于节点间数据结构不平衡问题,本文谨慎地研究局部函数之间的关系,并利用同组的局部变量对全局变量进行更新,进行预测。在多个基准不平衡数据集上的实验结果表明CS-GADMM是一个有效的不平衡分类算法。4.集成方差缩减和Nesterov’s加速的分布式交替方向乘子法:交替方向乘子法(ADMM)是机器学习中广泛应用的优化算法。近年来,一些先进的技术被用来加速ADMM收敛速度,其中包括方差缩减和Nesterov’s加速。而且ADMM的并行化也用来减轻大数据问题。一个自然而然的问题就是以上加速技术是否能够无缝地与ADMM集成,提高ADMM的收敛速度。本文关注以上问题,并提出一种新颖的集成方差缩减和Nesterov’s加速算法的分布式加速ADMM算法(DistributedAcceleratedAlternatingDirectionMethodofMultipliers,D-A2DM2)用于分布式学习和优化。具体地,对子问题的优化,本文采用集成方差缩减的随机ADMM的方法对子问题进行优化。除此基于Nesterov方法的加速策略,本文还在分布式框架中引入了修正的局部更新对称对偶更新。对于理论分析,收敛性证明了这些加速策略可以很好的集成到ADMM框架,并提高算法的收敛率。对于实验分析,在多个基准数据集上进行了实验测试,实验结果表明本文提