蒙特卡羅方法與人工智能

本書全面敘述了蒙特卡羅方法，包括序貫蒙特卡羅方法、馬爾可夫鏈蒙特卡羅方法基礎、Metropolis算法及其變體、吉布斯採樣器及其變體、聚類採樣方法、馬爾可夫鏈蒙特卡羅的收斂性分析、數據驅動的馬爾可夫鏈蒙特卡羅方法、哈密頓和朗之萬蒙特卡羅方法、隨機梯度學習和可視化能級圖等。為了便於學習，每章都包含了不同領域的代表性應用實例。本書旨在統計學和電腦科學之間架起一座橋梁以彌合它們之間的鴻溝，以便將其應用於電腦視覺、電腦圖形學、機器學習、機器人學、人工智能等領域解決更廣泛的問題，同時使這些領域的科學家和工程師們更容易地利用蒙特卡羅方法加強他們的研究。

目 錄
第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