【摘要】：隨著數(shù)據(jù)信息的爆炸式增長,傳統(tǒng)的運(yùn)行在單機(jī)上的機(jī)器學(xué)習(xí)方法不能有效地處理現(xiàn)實(shí)應(yīng)用中的大規(guī)模數(shù)據(jù),而且分布式數(shù)據(jù)的集中化處理會(huì)造成數(shù)據(jù)采集的額外開銷,這些情況都給大數(shù)據(jù)分析帶來了新的挑戰(zhàn)。分布式機(jī)器學(xué)習(xí)是隨著"大數(shù)據(jù)"概念興起的,而且分布式技術(shù)被用來解決大規(guī)模機(jī)器學(xué)習(xí)等問題。在眾多的分布式算法中,交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)是因其高分解性和收斂性得到廣泛的關(guān)注。ADMM通過將原始問題轉(zhuǎn)化為全局一致性問題,能夠靈活地采用分布式方式解決許多機(jī)器學(xué)習(xí)問題。在分布式ADMM中,計(jì)算節(jié)點(diǎn)通過訓(xùn)練自己局部模型參數(shù)來并行地優(yōu)化子問題,然后將所有的局部變量合并起來對全局變量進(jìn)行優(yōu)化,最后迭代得到全局解。而且許多研究學(xué)者已經(jīng)證明了在一定的假設(shè)前提下,ADMM算法具有次線性的收斂率。因此,本文圍繞"分布式ADMM研究"這一主線,對分布式ADMM中的關(guān)鍵問題展開了針對性的研究工作,具體而言,本文的主要工作和創(chuàng)新如下:1.分布式機(jī)器學(xué)習(xí)全局一致性框架:為構(gòu)建分布式機(jī)器學(xué)習(xí)研究框架,本文提出了一個(gè)基于分布式交替方向乘子法的全局一致性框架。該框架首先將原始問題拆分成子問題,然后對子問題進(jìn)行并行優(yōu)化,最后對子問題的解進(jìn)行融合得到全局解。該框架為分布式機(jī)器學(xué)習(xí)算法的研究提供了基礎(chǔ),而且全局一致性約束能夠使得所有子問題的解達(dá)到全局一致。2.基于分組交替方向乘子法的分布式線性分類:為解決分布式線性分類算法存在收效速度慢,時(shí)間開銷大等問題,本文提出一種新穎的基于分組交替方向乘子法(Group-Based Alternating Direction Method of Multipliers,GADMM)的方法來解決分布式線性分類問題。為了追求較快的收斂速度和更好的全局一致性,GADMM將原問題轉(zhuǎn)為一系列的中等規(guī)模的子問題,而這些子問題可以采用對偶坐標(biāo)下降方法有效地并行優(yōu)化。特別地,采用基于模型相似的分組方法,本文將所有的具有相似局部變量的節(jié)點(diǎn)分成同一組。在分組層中,局部變量被收集起來生成分組變量,然后采用分組變量來更新全局變量,整個(gè)過程迭代重復(fù)直至達(dá)到全局收斂。理論分析證明GADMM算法具有O(1/k)的收斂率,而且收斂速度比分布式ADMM要快,其中k是外迭代次數(shù)。而且實(shí)驗(yàn)結(jié)果表明GADMM算法能夠有效地減少迭代次數(shù),提高收斂速度,從而節(jié)省大量的訓(xùn)練時(shí)間。該實(shí)驗(yàn)結(jié)果和理論分析保持一致。3.快速的大規(guī)模不平衡數(shù)據(jù)分布式分類算法:在以往的文獻(xiàn)中,首先廣泛存在的類不平衡問題并沒有得到很好的研究,此外,先前的不平衡分類算法缺少對分布式環(huán)境中存在的復(fù)雜不平衡問題的研究。針對以上問題,本文闡述了一種分布式數(shù)據(jù)不平衡的概念,該概念包括三類不平衡問題:單節(jié)點(diǎn)正負(fù)樣本不平衡、節(jié)點(diǎn)間樣本數(shù)目不平衡和節(jié)點(diǎn)間數(shù)據(jù)結(jié)構(gòu)不平衡三個(gè)不平衡問題。為了充分地處理不平衡數(shù)據(jù)同時(shí)提高時(shí)間效率,本文提出一種有效的基于分組交替方向乘子法的分布式代價(jià)敏感分類算法(Cost-Sensitive Group-Based Alternating Direction Method of Multipliers,CS-GADMM)。具體地,CS-GADMM將原始問題分割成一系列帶有單節(jié)點(diǎn)正負(fù)樣本不平衡問題的子問題,然后,為了減輕由節(jié)點(diǎn)間樣本數(shù)目不平衡問題造成的計(jì)算和通信延遲,本文擴(kuò)展了對偶坐標(biāo)下降方法對子問題進(jìn)行優(yōu)化。同時(shí),對于節(jié)點(diǎn)間數(shù)據(jù)結(jié)構(gòu)不平衡問題,本文謹(jǐn)慎地研究局部函數(shù)之間的關(guān)系,并利用同組的局部變量對全局變量進(jìn)行更新,進(jìn)行預(yù)測。在多個(gè)基準(zhǔn)不平衡數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明CS-GADMM是一個(gè)有效的不平衡分類算法。4.集成方差縮減和Nesterov's加速的分布式交替方向乘子法:交替方向乘子法(ADMM)是機(jī)器學(xué)習(xí)中廣泛應(yīng)用的優(yōu)化算法。近年來,一些先進(jìn)的技術(shù)被用來加速ADMM收斂速度,其中包括方差縮減和Nesterov's加速。而且ADMM的并行化也用來減輕大數(shù)據(jù)問題。一個(gè)自然而然的問題就是以上加速技術(shù)是否能夠無縫地與ADMM集成,提高ADMM的收斂速度。本文關(guān)注以上問題,并提出一種新穎的集成方差縮減和Nesterov's加速算法的分布式加速ADMM算法(Distributed Accelerated Alternating Direction Method of Multipliers,D-A2DM2)用于分布式學(xué)習(xí)和優(yōu)化。具體地,對子問題的優(yōu)化,本文采用集成方差縮減的隨機(jī)ADMM的方法對子問題進(jìn)行優(yōu)化。除此基于Nesterov方法的加速策略,本文還在分布式框架中引入了修正的局部更新對稱對偶更新。對于理論分析,收斂性證明了這些加速策略可以很好的集成到ADMM框架,并提高算法的收斂率。對于實(shí)驗(yàn)分析,在多個(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)測試,實(shí)驗(yàn)結(jié)果表明本文提出的算法D-A2DM2比分布式ADMM的收斂速度要快,在實(shí)際應(yīng)用中將會(huì)是非常有效的分布式算法。
[Abstract]:......
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：TP181
，

本文編號：2276287