吉布斯分布的局部、動態(tài)與快速采樣算法

第1部分　緒論與預(yù)備知識
第1章　緒論
1.1　研究背景2
1.2　研究問題6
1.3　主要成果11
1.4　本書結(jié)構(gòu)與章節(jié)安排15
第2章　吉布斯分布與預(yù)備知識
2.1　吉布斯分布17
2.1.1　概率圖模型17
2.1.2　自旋系統(tǒng)與具體模型21
2.2　采樣與近似計數(shù)23
2.3　馬爾可夫鏈25
2.3.1　基本概念25
2.3.2　馬爾可夫鏈蒙特卡洛方法26
2.3.3　混合時間分析工具29
第2部分　分布式采樣
第3章　分布式采樣總覽
3.1　分布式計算與LOCAL模型44
3.2　分布式采樣與分布式計數(shù)46
3.3　分布式采樣部分章節(jié)安排48
第4章　分布式采樣算法
4.1　問題定義50
4.2　局部梅特羅波利斯算法51
4.2.1　算法與主要結(jié)論51
4.2.2　局部梅特羅波利斯算法的平穩(wěn)分布54
4.2.3　局部梅特羅波利斯算法的混合時間61
4.3　梅特羅波利斯算法的分布式模擬68
4.3.1　主要結(jié)論71
4.3.2　模擬算法74
4.3.3　算法分析84
4.4　本章小結(jié)101
第5章　分布式采樣復(fù)雜性
5.1　分布式采樣下界102
5.2　分布式JerrumValiantVazirani（JVV）定理117
5.2.1　基本定義117
5.2.2　近似采樣和近似推斷之間的歸約122
5.2.3　分布式JVV采樣算法123
5.3　強(qiáng)空間混合性質(zhì)與分布式采樣/計數(shù)138
5.4　本章小結(jié)143
第3部分　動態(tài)采樣
第6章　動態(tài)采樣總覽
6.1　研究背景146
6.2　問題定義147
6.3　主要結(jié)論149
第7章　條件吉布斯采樣技術(shù)
7.1　局部拒絕采樣算法161
7.2　精確吉布斯采樣算法164
7.3　正確性分析167
7.3.1　均衡條件167
7.3.2　局部拒絕采樣算法均衡條件驗證174
7.3.3　精確吉布斯采樣算法均衡條件驗證181
7.3.4　推廣版算法185
7.4　收斂性分析189
7.4.1　局部拒絕采樣算法收斂性分析189
7.4.2　精確吉布斯采樣算法收斂性分析195
7.5　本章小結(jié)209
第8章　動態(tài)馬爾可夫鏈技術(shù)
8.1　動態(tài)吉布斯采樣算法210
8.1.1　動態(tài)自旋系統(tǒng)上馬爾可夫鏈的耦合211
8.1.2　動態(tài)馬爾可夫鏈的數(shù)據(jù)結(jié)構(gòu)215
8.1.3　動態(tài)吉布斯采樣算法分析217
8.2　動態(tài)馬爾可夫鏈在推斷問題上的應(yīng)用223
8.2.1　支持多參數(shù)更新的動態(tài)馬爾可夫鏈226
8.2.2　算法的實現(xiàn)與分析233
8.3　本章小結(jié)241
第4部分　快速采樣算法
第9章　洛瓦茲局部引理采樣問題
9.1　研究背景244
9.2　主要結(jié)論246
9.3　基本定義與背景知識252
9.4　采樣算法256
9.4.1　CNF公式滿足解采樣算法256
9.4.2　狀態(tài)壓縮技術(shù)265
9.4.3　一般約束滿足問題采樣算法273
9.5　算法分析278
9.5.1　主定理證明279
9.5.2　投影策略的構(gòu)造290
9.5.3　InvSample子程序分析301
9.5.4　混合時間分析316
9.6　局部引理問題實例的近似計數(shù)389
9.7　本章小結(jié)406
第10章　譜獨(dú)立性與混合時間
10.1　研究背景408
10.2　主要結(jié)論410
10.2.1　譜獨(dú)立性與吉布斯采樣算法混合時間410
10.2.2　圖染色模型上的應(yīng)用414
10.3　混合時間分析418
10.3.1　主定理證明418
10.3.2　局部隨機(jī)游走的耦合423
10.4　圖染色模型的譜獨(dú)立性430
10.4.1　一般性定理的證明433
10.4.2　邊緣概率上界分析450
10.4.3　邊緣概率上界分析的緊致性456
10.5　本章小結(jié)458
致謝459
參考文獻(xiàn)462
附錄　文中部分專業(yè)名詞中英翻譯對照表481
攻讀博士學(xué)位期間的科研成果484
攻讀博士學(xué)位期間參與的科研課題486