優化在機器學習中扮演著重要的角色。作為理論上收斂速度最快的一階優化算 法,加速梯度法在機器學習領域取得了廣泛的應用。本文將研究經典加速算法在帶 約束凸優化問題、隨機凸優化問題、分布式凸優化問題和非凸優化問題上的應用。本文首先介紹加速技巧在交替方向乘子法(ADMM)中的應用,并提出了具有最優 非遍歷意義收斂速度的加速ADMM算法。經典ADMM算法在求解非強凸非光滑問題 時具有遍歷意義下O ( 1 K ) 收斂速度和非遍歷意義下O ( 1 √ K ) 收斂速度。在稀疏和低秩學 習中,遍歷意義中的取平均操作會破壞解的稀疏性和低秩性,因此在實際應用中我們 往往使用非遍歷意義解。我們提出的加速ADMM具有非遍歷意義下更快的O ( 1 K ) 收斂 速度。并且我們還證明了經典ADMM的非遍歷意義下O ( 1 √ K ) 收斂速度是緊的,即經 典ADMM具有較慢的非遍歷意義收斂速度是算法本身的特性,并非由于證明技巧不足 所致。另外,我們證明了當求解非強凸非光滑問題時,ADMM類型算法的復雜度下界 是O ( 1 K ) ,即任何ADMM類型算法都不可能比O ( 1 K ) 更快。
在大數據背景下,加速技巧不僅應用于傳統優化,而且在隨機優化和分布式優化 中也有廣泛應用。本文研究了在隨機優化領域經典的加速隨機對偶坐標上升算法,并 對其原問題解的復雜度進行分析。該算法使用加速隨機坐標下降法求解對偶問題,當 目標函數是強凸非光滑函數時,對偶問題解具有O ( 1 √ ? ) 的復雜度。在實際應用中,我 們需要使用的是原問題解,而非對偶問題解,因此我們需要度量原問題解的復雜度。已有結論顯示,對于一般的帶約束凸優化問題,當對偶問題解具有O ( 1 √ ? ) 的復雜度時, 原問題解只有O ( 1 ? ) 的復雜度。我們證明了如果對原問題解合適地進行加權平均,原 問題解具有和對偶問題解一樣的O ( 1 √ ? ) 的復雜度。當將加速隨機對偶坐標上升算法應 用到機器學習中經典的經驗損失最小問題時,我們的收斂速度比當前已有結論提高 了O ( log 1 ? ) 因子。
除了隨機優化領域,本文還研究了分布式優化領域的加速算法。我們首先對分布 式優化中經典的EXTRA算法重新分析,并給出了更快的O ( ( L μ + 1 1?σ2 (W) ) log 1 ? ) 的計算 復雜度和通信復雜度。然后我們使用Catalyst框架對EXTRA加速,得到了強凸情況下 復雜度為O (√ L μ(1?σ2 (W)) log L μ(1?σ2 (W)) log 1 ? ) 和非強凸情況下復雜度為O (√ L ?(1?σ2 (W)) log 1 ? ) 的加速EXTRA算法。除了對EXTRA進行擴展,我們還使用加速罰函數法對經典的分 布式加速梯度法進行解釋,并給出了具有最優計算復雜度(強凸情況下 O (√ L μ log 1 ? ) 和非強凸情況下O (√ L ? ) )和接近最優通信復雜度(強凸情況下O (√ L μ(1?σ2 (W)) log2 1 ? ) 和 非強凸情況下O (√ L ?(1?σ2 (W)) log 1 ? ) )的分布式加速算法。與已有分布式算法相比,我們提出的加速EXTRA算法和加速罰函數法具有更低的計算復雜度,同時我們的通信復 雜度或者與當前最好算法一樣,或者只比當前最好算法高 O ( log L μ(1?σ2 (W))) 或O ( log 1 ? ) 因子。最后,我們研究了加速算法在非凸低秩優化中的應用。我們首先分析了該問題中 目標函數的曲面性質,證明了當受限于某個特定凸集時,目標函數是受限制的局部強 凸函數。基于該性質,我們提出了交替約束加速梯度法并證明了該算法能夠局部線性 收斂到最優解。相比于梯度下降法,我們的收斂速度對條件數具有最優的 √ L/μ的依賴 關系。另外,當初始值為任意值時,我們的算法能夠全局收斂到梯度為0的點。
近年來,由于互聯網的高速發展和大數據時代的來臨,人工智能隨之大熱,而推動人工智能迅猛發展的正是深度學習的崛起。大數據時代需要迫切解決的問題是如何將極為復雜繁多的數據進行有效的分析使用,進而充分挖掘利用數據的價值并造福人類。深度學習作為一種實現機器學習的技術,正是解決這一問題的重要法寶,它在處理數據過程中發揮著重要作用并且改變了傳統的機器學習方法,已被廣泛應用于語音識別、圖像識別和自然語言處理等研究領域。如何有效加速深度學習的計算能力一直是科研研究的重點。FPGA憑借其強大的并行計算能力和低功耗等優勢成為GPU在加速深度學習領域的有力競爭者。從深度學習的幾種典型模型出發,在FPGA加速技術現有特點的基礎上從針對神經網絡模型的加速器、針對具體問題的加速器、針對優化策略的加速器和針對硬件模板的加速器四方面概括總結了FPGA加速深度學習的研究現狀,然后對比了不同加速技術和模型的性能,最后對未來可能發展的方向進行了展望。
摘要: 約束優化問題廣泛存在于科學研究和工程實踐中,其對應的約束優化進化算法也成為了進化領域的重要研究方向。約束優化進化算法的本質問題是如何有效地利用不可行解和可行解的信息,平衡目標函數和約束條件,使得算法更加高效。首先對約束優化問題進行定義;然后詳細分析了目前主流的約束進化算法,同時,基于不同的約束處理機制,將這些機制分為約束和目標分離法、懲罰函數法、多目標優化法、混合法和其他算法,并對這些方法進行了詳細的分析和總結;接著指出約束進化算法亟待解決的問題,并明確指出未來需要進一步研究的方向;最后對約束進化算法在工程優化、電子和通信工程、機械設計、環境資源配置、科研領域和管理分配等方面的應用進行了介紹。
多層圖分析技術研究
近年來,越來越多的領域都使用“圖”來表示和管理數據,稱為“圖數據”。針對 圖數據的分析可以發現其中的結構特征、頻繁模式、演變規律等有用的知識,具有 重要的科研意義和應用價值。隨著研究的深入,人們發現現實世界的圖數據往往 包含數據對象間多種類型的關系。例如,社交網絡數據包括多個社交媒體組成的 網絡;交通網絡數據涵蓋了多種交通工具組成的網絡。這種圖數據稱為“多層圖”, 其每一層包含了數據對象間某種特定類型的關系。
多層圖分析可以發現準確可靠、價值更高的知識。然而,多層圖分析面臨兩 方面的挑戰:一方面,單層圖上的計算語義在多層圖場景下不再適用,多層圖上 的計算語義更加復雜;另一方面,多層圖分析涉及多個圖層上的計算任務,使得 問題的固有計算復雜性大大增加。現有的多層圖分析方法在計算語義和算法設計 兩個方面都存在缺陷,不能很好的解決多層圖分析的有關問題。
本文綜合運用數據分析的相關理論、技術和方法,對于多層圖分析進行了系統研究。本文同時考慮了無概率的普通多層圖和帶概率的多層圖,從圖數據的稠 密性、可靠性、傳播性和相似性四方面重要性質出發,對多層圖分析領域中的一 系列重要問題進行了深入研究,主要研究成果如下:
本文研究了多層圖上的多樣化稠密區域發現問題,該問題在生物蛋白復合 體檢測和社區發現上具有重要應用。在無概率的普通多層圖模型基礎上,本文提 出了一種新的稠密區域概念 d-Coherent-Core(簡稱 d-CC),設計了兩種近似比為 1/4 的高效搜索算法來求解該 NP-難問題,算法在結果質量和執行時間兩個方面 均優于基于準團的傳統算法。d-CC 概念同時刻畫了稠密區域的稠密度和支持度兩 方面重要特性,滿足唯一性、包含性和層次性 3 個重要數學性質。自底向上和自 頂向下兩種搜索算法采用了高效的搜索策略和剪枝方法,分別適用于支持度參數 較小和較大兩種情況。真實數據上的實驗結果表明:自底向上和自頂向下兩種搜 索算法是高效、準確的。
本文研究了多層圖上的 top-k 可靠頂點搜索問題,該問題在通信網絡中具 有重要的研究意義,相比基于閾值的搜索問題自適應性更好。本文給出了一種圖 層帶概率的多層圖模型,提出了一種新的多層圖計算框架——共享計算,其可以 有效利用多層圖不同圖層間的重疊結構以減少搜索代價、提高算法效率。基于此,本文設計了求解 top-k 可靠頂點搜索問題的共享 BFS 精確算法和隨機算法。真實 數據上的實驗結果表明:共享 BFS 精確算法具有很高的效率和擴展性;共享 BFS 隨機算法具有很高的準確率。
本文研究了多層圖上的影響力最大化問題,該問題在病毒式營銷和輿情控 制中應用廣泛。為描述影響力最大化問題中的圖數據,本文給出了一種帶概率的 多層圖模型,其可以表示由于邊的不確定性而形成的多層圖。針對已有算法的缺 陷,本文設計了一種能夠同時達到高時間效率、高結果質量、低內存開銷和高健 壯性的影響力最大化算法,具有線性的時間和空間復雜度。該算法采用高質量的 分數估計方法和增量式的分數更新方法,在實際社交網絡中表現出良好的性能和 很高的擴展性。
本文研究了多層圖上 SimRank 頂點相似性測度問題,該問題是推薦系統、 實體識別等眾多應用的基礎。在帶概率的多層圖模型基礎上,本文嚴格給出了符 合其可能世界語義的 SimRank 相似性測度定義,設計了高效、準確的計算頂點間 SimRank 相似性的方法。同時,作為 SimRank 相似性測度的基礎,本文提出了多 層圖上隨機游走的定義,嚴格證明了這一定義滿足馬爾可夫性,設計了計算隨機 游走概率的高效算法。真實數據上的實驗結果表明:本文提出的 SimRank 算法是 高效、準確的;本文提出的 SimRank 測度比傳統測度在實際應用中效果更好。
機器學習中部分非凸和隨機優化算法研究
機器學習是一門多領域交叉學科,涉及概率論、統計學、逼近論、凸分析、算 法復雜度理論等多門學科。算法理論與應用是機器學習中最為重要的核心之一。其中一階優化算法因其簡單有效性,而被廣泛研究與應用。另一方面由于近年來 數據規模的不斷增大,數據集的規模使得二階或更高階的算法應用受阻。這使得 一階算法進一步成為機器學習的研究重點。隨著機器學習中問題模型的不斷擴張, 例如深度學習,非凸問題和模型也激發了學者們廣泛的研究興趣。這使得研究非 凸算法顯得更加急迫。而且由于數據集的龐大性,確定算法難以逃出鞍點,因此 隨機算法受到了史無前例的關注。本文主要結果可以歸納如下:
一、研究了三種 ADMM 算法。第一個 ADMM 的工作是關于一般的 ADMM 收 斂性分析統一框架。在此框架下,很多現有的 ADMM 收斂性分析可以歸納進該 框架。除了現有的 ADMM 算法,根據統一框架還能夠設計出新的 ADMM 算法。第二個和第三個 ADMM 都是針對結構非凸優化問題提出的:一個是針對泛 ?q 正 則化約束優化問題,而另一個是針對 ?1?2 正則化約束優化。給出了后面兩種非凸 ADMM 算法的收斂性分析,所得到的結果可以指導用戶選擇合適的超參數。
二、研究了兩種一階優化領域常用的非精確算法。第一種是非精確的加速算 法。相較于之前的研究,該算法的假設更為真實。而且還囊括了一大類隨機噪聲 的情況,使得算法更為實用。而機器學習中的一階催化劑算法由于是該加速算法 帶上了隨機噪聲,因此可以看做本算法的特例。在第二部分給出了非精確非凸算 法的收斂性框架理論。可以被廣泛應用到各種一階非凸算法。
三、證明了在有界和無界延遲以及隨機和確定性塊選擇下異步并行梯度下降法 的收斂結果。這些結果不需要迄今為止絕大多數其他工作中出現的獨立性假設。這是由于本文使用了 Lyapunov 函數技術,可直接處理延遲,而不是像之前的工作 一樣僅僅將它們建模為噪聲。
四、分析了馬爾可夫鏈隨機梯度下降法,其中樣本采用了某個馬爾可夫鏈的軌跡。主要貢獻之一是給出了馬爾可夫鏈隨機梯度下降法的在凸情況下的非遍歷收 斂分析。結果然后擴展到不精確的格式。這種分析使得能夠建立不可逆有限狀態 馬爾可夫鏈和非凸最小化問題的收斂性。這樣的結果適用于不知道具體的概率分 布,但可以通過馬爾可夫鏈進行采樣的情形。
基于深度學習的圖像處理算法研究
隨著智能手機和微單相機的普及,拍照已經變成人們日常生活中不可缺少的一部分,圖像也已成為人類社會的重要信息媒介。然而受到拍照環境、設備和技術的影響,圖像中難免會出現退化現象,如何從圖像處理的角度提升拍攝照片的質量具有重要的研究意義與應用價值。近年來,深度學習技術得到了巨大的發展,并廣泛應用于圖像處理領域。相對于許多傳統算法,深度學習技術從海量的訓練數據中學習到的先驗知識具有更強的泛化能力和更復雜的參數化表達,且無需調節算法參數以適應不同的應用場景。得益于上述優勢,深度學習技術已經廣泛應用于圖像處理領域,如何利用深度學習算法提升圖像處理的效果也變成了一個重要的研究方向。
盡管深度學習技術顯著促進了圖像處理領域的發展,但是受限于其對訓練數據的敏感性,在面對無標簽、僅有弱標簽或者合成偽標簽的數據時,深度學習技術的優勢難以充分體現。本學位論文針對以上挑戰,重點研究了缺失完整數據標簽的經典圖像處理問題,包括圖像平滑、反光去除和本征圖像分解等。本文通過將上述問題抽象為對圖像結構敏感的圖像分解問題,將顯著的目標邊緣信息通過優化或者濾波的方式編碼進深度學習的算法設計中。根據圖像處理問題中數據標簽的類型和數量不同,本文依次提出了基于無監督學習、弱監督學習和多標簽聯合訓練的深度學習解決方案。本文的最后提出了解耦學習框架,通過對10種不同圖像處理問題的聯合訓練,提煉出了圖像處理問題的核心解空間。該算法對于理解深度學習技術在圖像處理領域的應用有重要的研究價值和意義。本文的創新點和貢獻包括以下幾個方面:
(1) 一種基于無監督學習的空間自適應圖像平滑算法
該算法通過使用卷積神經網絡,以無監督的方式從無標簽數據中學習圖像平滑的優化過程,并實現可靈活調節的圖像平滑效果。該算法提出了一個由邊緣保持項和空間自適應平滑項構成的能量函數,前者用于保持重要但易破壞的圖像結構,后者用于將多種形式的正則器(Lp范數)施加至圖像的不同區域。由于缺乏平滑圖像的真值數據,本文采用一個無監督學習的能量優化框架,用來實現多種基于圖像平滑的視覺應用,譬如圖像抽象化、鉛筆素描、細節增強、紋理去除和基于內容的圖像處理等。實驗結果表明,該基于無監督學習的空間自適應圖像平滑算法獲得了更好的視覺結果。
(2) 一種基于弱監督學習的圖像反光去除算法
該算法提出了一個多階段卷積神經網絡,用以解決圖像分解領域中經典的反光去除問題。本算法框架由兩個結構相似的卷積神經網絡串聯而成,前者預測目標圖像的邊緣結構,后者依據預測邊緣信息的引導重建目標圖像;整個過程既不需要任何人工設計,也不依賴于其他圖像處理應用。通過從真實反光圖像觀察得到的圖像亮度和結構先驗,該算法設計了一種針對模糊強反光的反光圖像合成算法;通過將合成數據以弱監督信號的形式融入到多階段神經網絡訓練中,該算法獲得了在真實反光圖像上的良好泛化性能。實驗結果表明,該基于弱監督學習的圖像反光去除算法在不同程度的反光場景中均獲得更優的視覺效果。
(3) 一種基于多標簽聯合訓練的本征圖像分解算法
本征圖像分解往往存在數據集冗雜、數據標簽不一致等問題。為解決該問題,本文提出了一個通用的核心神經網絡,用以在不同類型的數據標簽中共享本征圖像形成過程的稀疏先驗。該神經網絡由三個不同的基礎模塊組成:直接本征圖像估計網絡、導向網絡和域濾波器;其中,直接本征圖像估計網絡通過對本征圖像的直接監督獲得初始的預測結果,導向網絡負責生成稀疏的反射結構先驗,并引導域濾波器獲得干凈的反射估計。該算法設計了一個靈活的能量損失層以實現多標簽數據聯合訓練的目的。實驗結果表明,該本征圖像分解算法在所有的主流基準數據集上都獲得了更高的精確度。
(4) 一種基于解耦學習的實時參數化圖像處理框架
傳統的深度學習算法在面對不同的圖像處理應用時,需要重復地訓練神經網絡。為了解決這個問題,該算法提出了由基礎網絡和權重學習網絡組成的解耦學習框架,其中前者用來實現具體的圖像處理應用,后者用來學習基礎網絡的權重。該算法通過對基礎網絡的結構和權重進行解耦,達到根據圖像處理應用的變化實時動態調整基礎網絡權重的效果,并因此實現了利用單一神經網絡融合多種圖像處理應用的目的。實驗結果表明,該解耦學習框架成功應用在10種不同的參數化圖像算子中,并減少了網絡參數的存儲空間。
在生態學、流行病學和天文學等許多應用領域中,仿真模型被用來研究發生在自然界中的復雜現象。通常,這些模型的似然函數的分析形式要么是不可用的,要么是太昂貴而無法評估,從而使統計推斷復雜化。無概率推理(LFI)方法,如近似貝葉斯計算(ABC),基于用模型的正演模擬代替難以處理的似然評估,已成為對仿真模型進行推理的一種流行方法。然而,當前的LFI方法在計算和統計方面存在一些挑戰。特別是,標準的ABC算法需要大量的仿真,這使得它們在前向仿真代價昂貴的情況下不可行。
本文討論了計算代價高的模型的無概率推理。主要貢獻是基于高斯過程代理模型的LFI一致性框架。GP模型允許對仿真模型輸出的平滑假設進行編碼,以減少所需的仿真量。此外,由于模擬預算有限,所產生的基于模型的后驗逼近的不確定性可以被量化。我們提出貝葉斯實驗設計策略來選擇評估地點,以使計算成本最小化。順序設計(每次選擇一個模擬)和批處理策略(允許利用并行計算)都是推導出來的。除了LFI場景外,本文提出的方法也適用于可能性可以評估但代價昂貴的情況。
本質上,所提出的框架可以被視為概率數值方法的LFI對等物,如貝葉斯優化,用于優化昂貴的目標函數,貝葉斯求積,用于計算昂貴函數的積分。我們通過大量的經驗模擬證明了所提出的LFI方法的優點。文中還對所提算法進行了理論分析,并討論了它們與其他GP代理方法的關系。
摘要:隨著日益劇增的海量數據信息的產生以及數據挖掘算法的廣泛應用,人們已經進入了大數據時代.在數據規模飛速增長的前提下,如何高效穩定的存取數據信息以及加快數據挖掘算法的執行已經成為學術界和工業界急需解決的關鍵問題.機器學習算法作為數據挖掘應用的核心組成部分,吸引了越來越多研究者的關注,而利用新型的軟硬件手段來加速機器學習算法已經成為了目前的研究熱點之一.本文主要針對基于ASIC和FPGA等硬件平臺設計的機器學習加速器進行了歸納與總結.首先,本文先介紹了機器學習算法,對代表性的算法進行了分析和歸納.接下來對加速器可能的著眼點進行了列舉綜述,以各種機器學習硬件加速器為主要實例介紹了目前主流的加速器設計和實現,并圍繞加速器結構進行簡單分類和總結.最后本文對機器學習算法硬件加速這個領域進行了分析,并對目前的發展趨勢做出了展望.