掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
機器學習中的交替方向乘子法 版權信息
- ISBN：9787030747587
- 條形碼：9787030747587 ; 978-7-03-074758-7
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
機器學習中的交替方向乘子法 內容簡介
本書將介紹一種非常常用的優化算法--交替方向乘子法，將完整介紹交替方向法的各種來源和各種主流的變種，并給出完整的證明和解釋。本書涵蓋了求解確定性凸問題、非凸問題、隨機問題和分布式問題的各類算法。本書將作為交替方向法的重要參考資料。該書更關注收斂速度，而不僅僅是收斂性，這樣的理論分析能給使用者提供極為有用的信息。該書對優化、信號處理和機器學習等不同領域的研究者和使用者來說，都毫無疑問是很有價值的參考。
機器學習中的交替方向乘子法 目錄
目錄
《大數據與數據科學專著系列》序
序一
序二
前言
符號表
第1章緒論 1
1.1 機器學習中的帶約束優化問題舉例 1
1.2 ADMM的代表性工作綜述 3
1.3 關于本書 5
第2章 ADMM的推導 6
2.1 從拉格朗日視角推導ADMM 6
2.1.1 對偶上升法 6
2.1.2 增廣拉格朗日法 7
2.1.3 交替方向乘子法（ADMM） 10
2.1.4 與分裂布雷格曼算法的聯系 11
2.2 從算子分裂視角推導ADMM 13
2.2.1 Douglas-Rachford分裂（DRS） 13
2.2.2 從DRS到ADMM 15
第3章 確定性凸優化問題中的ADMM 18
3.1 經典ADMM 18
3.1.1 收斂性分析 18
3.1.2 次線性收斂速度 23
3.1.3 線性收斂速度 27
3.2 布雷格曼ADMM 31
3.2.1 次線性收斂速度 35
3.2.2 線性收斂速度 41
3.3 加速線性化ADMM 45
3.3.1 次線性收斂速度 45
3.3.2 線性收斂速度 63
3.4 特例：線性化增廣拉格朗日算法及其加速 70
3.5 多變量塊ADMM 73
3.5.1 使用高斯回代的ADMM 74
3.5.2 使用預測-校正的ADMM 78
3.5.3 使用并行分裂的線性化ADMM 81
3.5.4 結合串行與并行更新 83
3.6 變分不等式視角下的ADMM 84
3.6.1 統一的變分不等式框架 86
3.6.2 統一的收斂速度分析 89
3.7 非線性約束問題 90
第4章 確定性非凸優化問題中的ADMM 97
4.1 多變量塊布雷格曼ADMM 97
4.1.1 滿射條件下的收斂性分析 98
4.1.2 對目標函數做更多假設下的收斂性分析 102
4.2 使用指數平均的鄰近ADMM 106
4.3 多線性約束優化問題的ADMM 118
第5章 隨機優化問題中的ADMM 124
5.1 隨機ADMM 125
5.2 方差縮減 132
5.3 沖量加速 142
5.4 非凸隨機ADMM及其加速 167
5.4.1 非凸隨機ADMM 167
5.4.2 SPIDER加速 172
第6章 分布式優化問題中的ADMM 181
6.1 中心化優化 181
6.1.1 ADMM 181
6.1.2 線性化ADMM 183
6.1.3 加速線性化ADMM 185
6.2 去中心化優化 187
6.2.1 ADMM 187
6.2.2 線性化ADMM 193
6.2.3 加速線性化ADMM 194
6.3 異步分布式ADMM 196
6.3.1 收斂性分析 197
6.3.2 線性收斂速度 203
6.4 非凸分布式ADMM 209
6.5 求解一般線性約束問題的分布式ADMM 210
第7章 實踐中的問題和總結 212
7.1 實踐中的問題 212
7.1.1 停止條件 212
7.1.2 懲罰系數的選擇 213
7.1.3 避免過多的輔助變量 215
7.1.4 非精確求解子問題 215
7.1.5 其他考慮 216
7.2 總結 216
參考文獻 217
附錄A 數學基礎 224
A.1 代數與概率 224
A.2 凸分析 225
A.3 非凸分析 231
縮略語 233
索引 234
后記 237
致謝 238
《大數據與數據科學專著系列》已出版書目 239
《大數據與數據科學專著系列》序
序一
序二
前言
符號表
第1章緒論 1
1.1 機器學習中的帶約束優化問題舉例 1
1.2 ADMM的代表性工作綜述 3
1.3 關于本書 5
第2章 ADMM的推導 6
2.1 從拉格朗日視角推導ADMM 6
2.1.1 對偶上升法 6
2.1.2 增廣拉格朗日法 7
2.1.3 交替方向乘子法（ADMM） 10
2.1.4 與分裂布雷格曼算法的聯系 11
2.2 從算子分裂視角推導ADMM 13
2.2.1 Douglas-Rachford分裂（DRS） 13
2.2.2 從DRS到ADMM 15
第3章 確定性凸優化問題中的ADMM 18
3.1 經典ADMM 18
3.1.1 收斂性分析 18
3.1.2 次線性收斂速度 23
3.1.3 線性收斂速度 27
3.2 布雷格曼ADMM 31
3.2.1 次線性收斂速度 35
3.2.2 線性收斂速度 41
3.3 加速線性化ADMM 45
3.3.1 次線性收斂速度 45
3.3.2 線性收斂速度 63
3.4 特例：線性化增廣拉格朗日算法及其加速 70
3.5 多變量塊ADMM 73
3.5.1 使用高斯回代的ADMM 74
3.5.2 使用預測-校正的ADMM 78
3.5.3 使用并行分裂的線性化ADMM 81
3.5.4 結合串行與并行更新 83
3.6 變分不等式視角下的ADMM 84
3.6.1 統一的變分不等式框架 86
3.6.2 統一的收斂速度分析 89
3.7 非線性約束問題 90
第4章 確定性非凸優化問題中的ADMM 97
4.1 多變量塊布雷格曼ADMM 97
4.1.1 滿射條件下的收斂性分析 98
4.1.2 對目標函數做更多假設下的收斂性分析 102
4.2 使用指數平均的鄰近ADMM 106
4.3 多線性約束優化問題的ADMM 118
第5章 隨機優化問題中的ADMM 124
5.1 隨機ADMM 125
5.2 方差縮減 132
5.3 沖量加速 142
5.4 非凸隨機ADMM及其加速 167
5.4.1 非凸隨機ADMM 167
5.4.2 SPIDER加速 172
第6章 分布式優化問題中的ADMM 181
6.1 中心化優化 181
6.1.1 ADMM 181
6.1.2 線性化ADMM 183
6.1.3 加速線性化ADMM 185
6.2 去中心化優化 187
6.2.1 ADMM 187
6.2.2 線性化ADMM 193
6.2.3 加速線性化ADMM 194
6.3 異步分布式ADMM 196
6.3.1 收斂性分析 197
6.3.2 線性收斂速度 203
6.4 非凸分布式ADMM 209
6.5 求解一般線性約束問題的分布式ADMM 210
第7章 實踐中的問題和總結 212
7.1 實踐中的問題 212
7.1.1 停止條件 212
7.1.2 懲罰系數的選擇 213
7.1.3 避免過多的輔助變量 215
7.1.4 非精確求解子問題 215
7.1.5 其他考慮 216
7.2 總結 216
參考文獻 217
附錄A 數學基礎 224
A.1 代數與概率 224
A.2 凸分析 225
A.3 非凸分析 231
縮略語 233
索引 234
后記 237
致謝 238
《大數據與數據科學專著系列》已出版書目 239
展開全部
機器學習中的交替方向乘子法 節選
第1章緒論 優化是信號處理、機器學習等需要做數學建模的研究領域的支撐技術.AAAI會士、華盛頓大學教授P.Domingos曾提出如下著名的公式[17]: 機器學習=表示+優化+評估， 可見優化在機器學習中的重要性. 除了應用廣泛的無約束優化問題(可參見文獻[56])，很多數學模型也可以被建模成或重寫成帶約束的優化問題.約束可以為數學模型增加更多的先驗知識(例如非負性、有界性等)，也可以為了方便求解而引入(例如使用輔助變量).交替方向乘子法(ADMM)是求解帶約束問題的有力工具，包括經典的線性等式約束、目標函數可分離的問題和一般的非線性或不等式約束的問題.受限于熟悉程度，本書主要介紹機器學習界研究的ADMM. 1.1機器學習中的帶約束優化問題舉例 我們給出三個可以使用ADMM求解的代表性機器學習問題.**個是經典的魯棒主成分分析(RPCA)模型[10]，第二個是分布式優化中應用廣泛的一致性(Consensus)模型，第三個是非負矩陣填充模型[94]. RPCA模型[10]將一個觀測矩陣分解成一個低秩矩陣和一個稀疏矩陣，該模型可以建模成如下帶線性約束、目標函數可分離的凸優化問題: (1.1) 其中表示核范數，定義為矩陣奇異值之和，表示.1范數à，定義為矩陣元素絕對值之和，這兩個范數分別是秩函數和范數的凸松弛.在實際應用中，觀測矩陣M可能被噪聲污染.相應地，我們可以改為求解如下問題: (1.2) 其中統一表示矩陣的弗羅貝尼烏斯(Frobenius)范數和向量的歐幾里得(Euclid)范數.在某些實際應用中，的維度可能很大，因此計算它的奇異值分解見定義不可行.為了節省計算時間，人們常將低秩矩陣分解成兩個小得多的矩陣的乘積，并求解如下替代問題: (1.3) 這是因為.另一方面，有時我們想直接使用秩函數和.范數，而不是它們的凸松弛，因此會求解如下非凸問題: (1.4) 問題(1.1)和(1.2)分別是具有兩個變量塊和三個變量塊的凸優化問題，而問題(1.3)和(1.4)是非凸問題.所有這些問題都可以使用相應形式的ADMM求解，并保證一定的收斂性. 第二個例子是一致性問題[8].我們希望在分布式環境下*小化m個函數的和，問題描述如下 (1.5) 其中個節點構成了一個連通無向網絡，由于存儲限制或隱私考慮，局部函數的信息只能由節點獲得，其他節點無法獲得.當網絡有一個中心節點時，我們可以將上述問題重寫成如下等式約束的*優化問題: 其中中心節點負責更新，其他工作節點負責更新.當網絡沒有中心節點時，我們無法使用約束，這是由于現在我們沒有一個中心節點來計算.在這種情況下，如果網絡中的一條邊連接了節點和，我們可以把這條邊關聯一個變量.于是問題(1.5)就可以重寫成如下*優化問題: 其中E表示邊的集合.上述兩個問題都可以使用ADMM有效求解(分別見6.1節和6.2節). 第三個例子是非負矩陣低秩填充模型[94]，該模型在降維、文本挖掘、協同過濾、聚類等問題中應用廣泛.該模型描述如下 (1.6) 其中b是矩陣X中被噪聲污染的觀測數據;Ω是矩陣中被觀測到的元素的位置的集合;PΩ是一個線性映射，它從矩陣中選擇位置在集合Ω中的元素.直接求解上述問題不太容易，我們可以通過引入輔助變量Y和e重寫為下述問題 (1.7) 其中χ為指示函數: 重寫之后的問題(1.7)可以使用多變量塊ADMM有效求解. 1.2ADMM的代表性工作綜述 ADMM首先由Glowinski和Marrocco[28]以及Gabay和Mercier[24]在20世紀70年代中期提出.ADMM原來在機器學習領域并不受關注，直到人們在2010年左右使用它來求解低秩問題，例如RPCA[10]和低秩表示模型[60]，那時稀疏和低秩學習是機器學習的研究熱點.較早的工作包括文獻[10，55，58，60，83].Boyd等的教程[8]對ADMM在機器學習領域的推廣也起到了很大作用. ADMM在求解凸問題時的收斂性被很多人證明，例如Gabay[22]以及Eckstein和Bertsekas[19].但是其收斂速度一直懸而未決，直到He和Yuan[38]于2012年使用變分不等式證明了遍歷意義下(也就是考慮迭代序列的平均)的收斂速度，其中k表示迭代次數.為了使ADMM的子問題容易求解，很多人通過線性化增廣項以及光滑目標函數將ADMM擴展到線性化版本，見文獻[31，58，79，89]等.一些研究者(見文獻[73]和[52])將線性化ADMM和Nesterov加速結合.但是對于一般凸的問題，收斂速度并沒有提升，仍然是O(1/k).若假設光滑性和強凸性，則可以得到更快的收斂速度.與遍歷意義下的收斂速度相比，人們可能對非遍歷意義下(即*后一次迭代點)的收斂速度更感興趣.非遍歷意義下的收斂速度首先由He和Yuan[39]于2015年給出，之后由Davis和Yin[14]于2016年擴展.他們證明了對一般凸問題ADMM具有O(1/√k)的收斂速度，Davis和Yin[14]進一步證明了這個速度是緊的.ADMM*初是用來求解兩個變量塊的問題的，即變量被分成兩組，每一組中的變量同時更新，但是機器學習中的很多模型都有多塊變量.將兩變量塊ADMM直接套用在多變量塊凸優化問題上的做法在實踐中很常見，并且在某些問題上看起來是有效的，例如文獻[83]，但這么做是否會收斂并不清楚.Chen等[13]首先舉出了反例，證明了將兩變量塊ADMM直接應用到多變量塊凸問題上不一定能收斂.因此，為了保證收斂，我們需要做一些調整，例如添加高斯回代(GaussianBackSubstitution)[33]或收縮步驟(ContractiveStep)[32]或使用并行分裂(ParallelSplitting)[34，57，61]等à.ADMM*初是用來求解帶線性約束的凸優化問題的，為了更廣泛地應用，一些研究者將它擴展到更一般的約束，包括線性等式約束、線性不等式約束和非線性約束，見文獻[26].基于學習的ADMM是近來一個很有意思的研究課題，它將迭代算法看作一個結構化的深度神經網絡，通過松弛ADMM中的參數為可學習的，從而使得算法更適合于特定的數據或問題，見文獻[92，96].但是基于學習的ADMM目前尚不成熟，只有文獻[92]給出了一些理論分析. 非凸ADMM作為近年來的研究熱點之一，已被很多人研究(見文獻[7，43，47，51，90])，特別是使用布雷格曼距離的鄰近ADMM[87].Zhang和Luo[99]提出了另一個鄰近ADMM，它使用了到所有歷史迭代的指數平均的布雷格曼距離，而不是到前一次迭代.上述工作用于求解帶線性約束的非凸問題.另一方面，Gao等[25]提出了一個求解多線性約束問題的非凸ADMM，這類問題在機器學習中有著廣泛的應用，例如非負矩陣分解[30]、RPCA[10]和訓練神經網絡[54，85].求解帶一般非線性甚至非凸約束的問題的ADMM的研究要少得多，相關工作主要集中在增廣拉格朗日法(AugmentedLagrangianMethod)，見文獻[76]及其中的參考文獻. 在機器學習和統計學中，目標函數多是期望形式，隨機變量與數據樣本關聯.這時，我們一般使用隨機算法*小化期望形式的目標函數，即每次迭代只隨機選擇一個或多個樣本作為全樣本下的對應量的估計進行計算，因此極大地減少了計算量.隨機ADMM較早的工作有文獻[72]和[82]等，當目標函數是凸函數時，隨機ADMM具有O(1/√k)的收斂速度.Azadi等[4]進一步將隨機ADMM與Nesterov加速相結合，同樣給出了O(1/√k)的收斂速度.另一方面，當目標函數是有限個子函數的平均但函數的個數不是太多時，方差縮減(VarianceReduction，VR)是控制隨機梯度的方差并加速算法收斂的有效技術(例如，見文獻[15，48，77]).方差縮減技術被Zhong和Kwok[101]及Zheng和Kwok[100]等擴展到隨機ADMM，并得到了O(1/k)的遍歷意義下的收斂速度.Fang等[20]和Liu等[63]進一步將方差縮減和Nesterov加速結合，在適當條件下得到了在階上更快的收斂速度.在非凸優化中，隨機ADMM同樣有人研究[44].近來Huang等[45]和Bian等[6]使用另一種被稱為隨機路徑積分差分估計子(StochasticPath-IntegratedDifferentialEstimatoR，SPIDER)[21]的強有力的方差縮減技術，無論目標函數是有限個子函數的和還是無限個的，都能得到更快的收斂速度. 在分布式優化中使用ADMM求解具有中心節點的一致性問題可以追溯到20世紀80年代[5]，詳細描述可見文獻[8].當求解一致性問題的分布式網絡沒有中心節點時，Shi等[81]證明了ADMM等價于線性化增廣拉格朗日法(LinearizedAugmentedLagrangianMethod).一般來說，ADMM不是求解無中心分布式優化問題的首選，人們更傾向于原始-對偶算法[50]、線性化增廣拉格朗日法[1，80]、梯度跟蹤(GradientTracking)法[68，75，93]等.異步是實用分布式優化中的熱點課題.Wei和Ozdaglar[91]使用隨機ADMM建模異步，即每次迭代隨機激活部分節點.Chang等[11，12]給出了一個求解中心化一致性問題的完全異步的ADMM，并給出了收斂性和收斂速度分析.文獻[91]和[11，12]主要研究中心化分布式優化中的異步ADMM，關于無中心分布式優化中的異步ADMM的研究相對來說要少得多. 1.3關于本書 在前面一節，我們簡要介紹了ADMM的代表性工作.在接下來的章節，我們將詳細介紹ADMM及其在不同設定下的各種變種，包括求解凸優化問題的確定性ADMM(第3章)、非凸優化問題的確定性ADMM(第4章)、隨機優化問題中的ADMM(第5章)和分布式優化問題中的ADMM(第6章).為了內容的完備性，我們基本上都給出了每個算法的收斂性及收斂速度證明.因為時間有限，也為了保持本書中各個算法之間的差異性(以免讀者感到厭煩)，我們并沒有介紹前面一節中所有的代表性算法. 本書作為ADMM部分*新進展的有用的參考資料，可作為相關專業的研究生教學參考書，也可供對機器學習和優化感興趣的研究人員閱讀參考. 第2章ADMM的推導 本章將分別從拉格朗日視角和算子分裂視角推導ADMM，前者提供了更多有用的背景和動機. 2.1從拉格朗日視角推導ADMM 我們首先簡要介紹兩個基于拉格朗日函數的算法，然后導出ADMM. 2.1.1對偶上升法 考慮如下帶線性等式約束的凸優化問題 (2.1) 其中f(x)是正常(Proper，見定義A.25)、閉(Closed，見定義A.12)的凸函數(見定義A.4)à.我們可以使用對偶上升法求解該問題.引入拉格朗日函數(見定義A.17): 其中λ是拉格朗日乘子.問題(2.1)的對偶函數(見定義A.18)為 (2.2) 其中f( )表示f( )的共軛函數(見定義A.16).對偶函數d(λ)是凹函數(見定義A.5)并且其定義域為D={λ|d(λ)>-∞}.對偶問題(見定義A.19)定義為 (2.3)
書友推薦
- >
推拿
- >
唐代進士錄
- >
巴金－再思錄
- >
龍榆生：詞曲概論/大家小書
- >
姑媽的寶刀
- >
自卑與超越
- >
月亮虎
- >
朝聞道
本類暢銷
