蒙特卡羅方法與人工智能

目 錄
第1 章 蒙特卡羅方法簡介··············································································.1
1.1 引言·······························································································.1
1.2 動機和目標······················································································.1
1.3 蒙特卡羅計算中的任務·······································································.2
1.3.1 任務1：採樣和模擬········································································.3
1.3.2 任務2：通過蒙特卡羅模擬估算未知量···················································.5
1.3.3 任務3：優化和貝葉斯推理································································.7
1.3.4 任務4：學習和模型估計···································································.8
1.3.5 任務5：可視化能級圖·····································································.9
本章參考文獻··························································································13
第2 章 序貫蒙特卡羅方法··············································································14
2.1 引言·······························································································14
2.2 一維密度採樣···················································································14
2.3 重要性採樣和加權樣本·······································································15
2.4 序貫重要性採樣（SIS） ······································································18
2.4.1 應用：表達聚合物生長的自避游走························································18
2.4.2 應用：目標跟蹤的非線性/粒子濾波·······················································20
2.4.3 SMC 方法框架總結·········································································23
2.5 應用：利用SMC 方法進行光線追蹤·······················································24
2.6 在重要性採樣中保持樣本多樣性···························································25
2.6.1 基本方法····················································································25
2.6.2 Parzen 窗討論··············································································28
2.7 蒙特卡羅樹搜索················································································29
2.7.1 純蒙特卡羅樹搜索··········································································30
2.7.2 AlphaGo ·····················································································32
2.8 本章練習·························································································33
本章參考文獻··························································································35
第3 章 馬爾可夫鏈蒙特卡羅方法基礎·······························································36
3.1 引言·······························································································36
蒙特卡羅方法與人工智能
·X ·
3.2 馬爾可夫鏈基礎················································································37
3.3 轉移矩陣的拓撲：連通與周期······························································38
3.4 Perron-Frobenius 定理··········································································41
3.5 收斂性度量······················································································42
3.6 連續或異構狀態空間中的馬爾可夫鏈·····················································44
3.7 各態遍歷性定理················································································45
3.8 通過模擬退火進行MCMC 優化·····························································46
3.9 本章練習·························································································49
本章參考文獻··························································································51
第4 章 Metropolis 算法及其變體······································································52
4.1 引言·······························································································52
4.2 Metropolis-Hastings 算法······································································52
4.2.1 原始Metropolis-Hastings 算法······························································53
4.2.2 Metropolis-Hastings 算法的另一形式·······················································54
4.2.3 其他接受概率設計··········································································55
4.2.4 Metropolis 算法設計中的關鍵問題·························································55
4.3 獨立Metropolis 採樣···········································································55
4.3.1 IMS 的特徵結構············································································56
4.3.2 有限空間的一般首中時·····································································57
4.3.3 IMS 擊中時分析············································································57
4.4 可逆跳躍和跨維MCMC ······································································59
4.4.1 可逆跳躍····················································································59
4.4.2 簡單例子：一維圖像分割··································································60
4.5 應用：計算人數················································································63
4.5.1 標值點過程模型············································································64
4.5.2 MCMC 推理·················································································64
4.5.3 結果·························································································65
4.6 應用：傢具佈置················································································65
4.7 應用：場景合成················································································67
4.8 本章練習·························································································71
本章參考文獻··························································································72
第5 章 吉布斯採樣器及其變體········································································73
5.1 引言·······························································································73
5.2 吉布斯採樣器···················································································74
目 錄
·XI·
5.2.1 吉布斯採樣器介紹··········································································74
5.2.2 吉布斯採樣器的一個主要問題·····························································75
5.3 吉布斯採樣器擴展·············································································76
5.3.1 擊中逃跑····················································································77
5.3.2 廣義吉布斯採樣器··········································································77
5.3.3 廣義擊中逃跑···············································································77
5.3.4 利用輔助變量採樣··········································································78
5.3.5 模擬退火····················································································78
5.3.6 切片採樣····················································································79
5.3.7 數據增強····················································································80
5.3.8 Metropolized 吉布斯採樣器·································································80
5.4 數據關聯和數據增強··········································································82
5.5 Julesz 系綜和MCMC 紋理採樣······························································83
5.5.1 Julesz 系綜：紋理的數學定義······························································84
5.5.2 吉布斯系綜和系綜等價性··································································85
5.5.3 Julesz 系綜採樣·············································································86
5.5.4 實驗：對Julesz 系綜進行採樣·····························································87
5.6 本章練習·························································································89
本章參考文獻··························································································90
第6 章 聚類採樣方法····················································································91
6.1 引言·······························································································91
6.2 Potts 模型和SW 算法·········································································92
6.3 SW 算法詳解····················································································94
6.3.1 解釋1：Metropolis-Hastings 觀點··························································94
6.3.2 解釋2：數據增強··········································································97
6.4 SW 算法的相關理論結果··································································.100
6.5 任意概率的SW 切分算法·································································.102
6.5.1 步驟一：數據驅動的聚類·······························································.102
6.5.2 步驟二：顏色翻轉·······································································.103
6.5.3 步驟三：接受翻轉·······································································.104
6.5.4 復雜性分析···············································································.105
6.6 聚類採樣方法的變體·······································································.106
6.6.1 聚類吉布斯採樣：“擊中逃跑”觀點·····················································.106
6.6.2 多重翻轉方案············································································.107
6.7 應用：圖像分割·············································································.107
蒙特卡羅方法與人工智能
·X II·
6.8 多重網格和多級SW 切分算法···························································.110
6.8.1 多重網格SW 切分算法··································································.111
6.8.2 多級SW 切分算法·······································································.113
6.9 子空間聚類···················································································.114
6.9.1 通過SW 切分算法進行子空間聚類·····················································.115
6.9.2 應用：稀疏運動分割····································································.117
6.10 C 4：聚類合作競爭約束··································································.121
6.10.1 C 4 算法綜述············································································.123
6.10.2 圖形、耦合和聚類······································································.124
6.10.3 平面圖上的C 4 算法····································································.128
6.10.4 在平面圖上的實驗······································································.131
6.10.5 棋盤Ising 模型·········································································.132
6.10.6 分層圖上的C 4··········································································.136
6.10.7 C 4 分層實驗············································································.138
6.11 本章練習·····················································································.139
本章參考文獻·······················································································.140
第7 章 MCMC 的收斂性分析·······································································.144
7.1 引言····························································································.144
7.2 關鍵收斂問題················································································.144
7.3 實用的監測方法·············································································.145
7.4 洗牌的耦合方法·············································································.146
7.4.1 置頂洗牌·················································································.147
7.4.2 Riffle 洗牌················································································.147
7.5 幾何界限、瓶頸和連通率·································································.149
7.5.1 幾何收斂·················································································.149
7.5.2 交易圖（轉換圖）·······································································.150
7.5.3 瓶頸······················································································.150
7.5.4 連通率····················································································.151
7.6 Peskun 有序和遍歷性定理·································································.152
7.7 路徑耦合和精確採樣·······································································.153
7.7.1 從過去耦合···············································································.154
7.7.2 應用：對Ising 模型進行採樣···························································.155
7.8 本章練習······················································································.157
本章參考文獻·······················································································.159
目 錄
·XIII·
第8 章 數據驅動的馬爾可夫鏈蒙特卡羅方法···················································.160
8.1 引言····························································································.160
8.2 圖像分割和DDMCMC 方法概述························································.160
8.3 DDMCMC 方法解釋········································································.161
8.3.1 MCMC 方法設計的基本問題····························································.163
8.3.2 計算原子空間中的提議概率：原子粒子················································.164
8.3.3 計算對象空間中的提議概率：對象粒子················································.166
8.3.4 計算多個不同的解：場景粒子··························································.167
8.3.5 Ψ-世界實驗··············································································.167
8.4 問題表達和圖像建模·······································································.168
8.4.1 用於分割的貝葉斯公式··································································.169
8.4.2 先驗概率·················································································.169
8.4.3 灰度圖像的似然·········································································.169
8.4.4 模型校準·················································································.171
8.4.5 彩色圖像模型············································································.172
8.5 解空間分析···················································································.173
8.6 使用遍歷馬爾可夫鏈探索解空間························································.174
8.6.1 五類馬爾可夫鏈動態過程·······························································.174
8.6.2 瓶頸問題·················································································.175
8.7 數據驅動方法················································································.176
8.7.1 方法一：原子空間中的聚類·····························································.176
8.7.2 方法二：邊緣檢測·······································································.180
8.8 計算重要性提議概率·······································································.180
8.9 計算多個不同的解··········································································.183
8.9.1 動機和數學原理·········································································.183
8.9.2 用於多種解的K-冒險家算法····························································.184
8.10 圖像分割實驗···············································································.185
8.11 應用：圖像解析············································································.188
8.11.1 自上而下和自下而上的處理···························································.190
8.11.2 生成和判別方法········································································.190
8.11.3 馬爾可夫鏈核和子核···································································.191
8.11.4 DDMCMC 和提議概率·································································.193
8.11.5 馬爾可夫鏈子核········································································.200
8.11.6 圖像解析實驗···········································································.207
8.12 本章練習·····················································································.210
蒙特卡羅方法與人工智能
·X IV·
本章參考文獻·······················································································.211
第9 章 哈密頓和朗之萬蒙特卡羅方法····························································.215
9.1 引言····························································································.215
9.2 哈密頓力學···················································································.215
9.2.1 哈密頓方程···············································································.215
9.2.2 HMC 的簡單模型········································································.216
9.3 哈密頓力學的性質··········································································.217
9.3.1 能量守恆·················································································.217
9.3.2 可逆性····················································································.218
9.3.3 辛結構和體積保持·······································································.219
9.4 哈密頓方程的蛙跳離散化·································································.220
9.4.1 歐拉方法·················································································.220
9.4.2 改良的歐拉方法·········································································.220
9.4.3 蛙跳積分器···············································································.221
9.4.4 蛙跳積分器的特性·······································································.222
9.5 哈密頓蒙特卡羅方法和朗之萬蒙特卡羅方法·········································.223
9.5.1 HMC 建模················································································.223
9.5.2 HMC 算法················································································.224
9.5.3 LMC 算法················································································.226
9.5.4 HMC 調參················································································.228
9.5.5 HMC 的細致平衡證明···································································.229
9.6 黎曼流形HMC···············································································.230
9.6.1 HMC 中的線性變換·····································································.230
9.6.2 RMHMC 動力學·········································································.233
9.6.3 RMHMC 算法和變體····································································.235
9.6.4 RMHMC 中的協方差函數·······························································.236
9.7 HMC 實踐·····················································································.237
9.7.1 受約束正態分佈的模擬實驗·····························································.237
9.7.2 使用RMHMC 對邏輯回歸系數進行採樣···············································.241
9.7.3 使用LMC 採樣圖像密度：FRAME、GRADE 和DeepFRAME ·······················.243
9.8 本章練習······················································································.248
本章參考文獻·······················································································.249
第10 章 隨機梯度學習················································································.250
10.1 引言···························································································.250
目 錄
·XV·
10.2 隨機梯度：動機和性質···································································.250
10.2.1 引例·····················································································.251
10.2.2 Robbins-Monro 定理····································································.253
10.2.3 隨機梯度下降和朗之萬方程···························································.254
10.3 馬爾可夫隨機場（MRF）模型的參數估計···········································.257
10.3.1 利用隨機梯度學習FRAME 模型······················································.258
10.3.2 FRAME 的替代學習方法·······························································.259
10.3.3 FRAME 算法的四種變體·······························································.261
10.3.4 紋理分析實驗···········································································.264
10.4 用神經網絡學習圖像模型································································.267
10.4.1 對比發散與持續對比發散······························································.267
10.4.2 使用深度網絡學習圖像的勢能模型：DeepFRAME···································.268
10.4.3 生成器網絡和交替反向傳播···························································.271
10.4.4 協作網絡和生成器模型································································.275
10.5 本章練習·····················································································.279
本章參考文獻·······················································································.279
第11 章 可視化能級圖················································································.282
11.1 引言···························································································.282
11.2 能級圖的示例、結構和任務·····························································.282
11.2.1 基於能量的狀態空間劃分······························································.285
11.2.2 構造非連通圖（DG）··································································.286
11.2.3 二維ELM 示例·········································································.287
11.2.4 表徵學習任務的難度（或復雜度）····················································.289
11.3 廣義Wang-Landau 算法··································································.290
11.3.1 GWL 映射的能壘估計··································································.291
11.3.2 用GWL 估算體積······································································.292
11.3.3 GWL 收斂性分析·······································································.294
11.4 GWL 實驗···················································································.295
11.4.1 高斯混合模型的GWL 映射····························································.295
11.4.2 語法模型的GWL 映射·································································.301
11.5 用吸引-擴散可視化能級圖······························································.305
11.5.1 亞穩定性和宏觀劃分···································································.306
11.5.2 吸引-擴散簡介·········································································.307
11.5.3 吸引-擴散和Ising 模型································································.309
11.5.4 吸引-擴散ELM 算法（ADELM 算法）···············································.311
蒙特卡羅方法與人工智能
·X VI·
11.5.5 調優ADELM ···········································································.313
11.5.6 AD 能壘估計···········································································.314
11.6 用GWL 和ADELM 可視化SK 自旋玻璃模型······································.315
11.7 使用吸引?擴散可視化圖像空間························································.318
11.7.1 圖像星系的結構········································································.318
11.7.2 可視化實驗·············································································.319
11.8 本章練習·····················································································.324
本章參考文獻·······················································································.324