《吉布斯分布的局部、動態(tài)與快速采樣算法》由愛丁堡大學(xué)博士后鳳維明撰寫，內(nèi)容榮獲2021年度CCF優(yōu)秀博士學(xué)位論文獎。全書立足大數(shù)據(jù)背景下的新問題，從分布式采樣和動態(tài)采樣兩個具體問題入手，給出了有理論保障的算法并研究了新模型下采樣問題的復(fù)雜性。
《吉布斯分布的局部、動態(tài)與快速采樣算法》共十章，分為四個部分：
第零部分（第1~2章）主要介紹了全書的研究背景、研究問題、研究成果，向讀者講解了全書的結(jié)構(gòu)和章節(jié)安排，之后給出了吉布斯分布和采樣問題的嚴格數(shù)學(xué)定義，介紹全書中經(jīng)常使用的相關(guān)概念，并總結(jié)一部分已有的算法設(shè)計和分析技術(shù)。
第一部分（第3~5章）從算法和復(fù)雜性兩個層面介紹有關(guān)局部采樣的研究成果。
第二部分（第6~8章）給出了兩種不同的動態(tài)采樣算法設(shè)計技術(shù)，并分析相應(yīng)的算法性能。
第三部分（第9~10章）研究了經(jīng)典的公開問題，給出了一種新的快速采樣算法設(shè)計技術(shù)和一種新的馬爾可夫鏈收斂時間分析技術(shù)。
所有介紹新結(jié)果的章節(jié)都給出了相應(yīng)的本章小結(jié)，總結(jié)了該章的研究成果，列舉了該方向遺留的公開問題。
適讀人群 ：研究生、科研人員、從業(yè)者等
◆中國計算機領(lǐng)域具有重要突破或重要創(chuàng)新的博士研究生科研成果
◆2021年度CCF優(yōu)秀博士學(xué)位論文獎
◆剖析當前技術(shù)的本質(zhì)障礙，從原理層面創(chuàng)新解決方法
◆關(guān)注并行的、動態(tài)的采樣算法
◆基于大數(shù)據(jù)背景思考新采樣理論體系的建立
吉布斯分布是一類重要的概率模型，它在概率論、統(tǒng)計物理和計算機科學(xué)等領(lǐng)域有著非常廣泛的應(yīng)用。采樣是關(guān)于吉布斯分布的核心計算任務(wù)，它要求算法按照給定的分布生成一個隨機樣本。吉布斯分布的采樣問題是理論計算機 科學(xué)的重要課題之一，人們致力于探索有嚴格理論保障的算法以及采樣問題的計算復(fù)雜性。經(jīng)過數(shù)十年的深入研究，拒絕采樣、馬爾可夫鏈蒙特卡洛方法等采樣技術(shù)逐漸被發(fā)展起來，很多重要的采樣問題被成功解決。
雖然先前的研究回答了關(guān)于采樣的若干基本問題，但是目前已知的采樣算法較少，分析工具也有待加強，一些重要的問題沒有得到很好的解決。例如對于均勻采樣邏輯公式滿足解的問題，因為很多經(jīng)典算法無法適用，所以長期缺乏高效算法；對于均勻采樣合法圖染色問題，因為缺乏有力的分析工具，所以目前已知的算法收斂條件和猜想依然有很大差距。這些公開問題代表了當前技術(shù)上的本質(zhì)障礙，解決這些問題需要在原理層面上做出創(chuàng)新。另一方面，在大數(shù)據(jù)時代，很多新的采樣問題涌現(xiàn)出來。一些經(jīng)典的采樣技術(shù)只能給出高度串行、適用于靜態(tài)數(shù)據(jù)的采樣算法。而在如今的應(yīng)用中，并行的、動態(tài)的采樣算法越來越受到關(guān)注。傳統(tǒng)的采樣理論難以勝任新的問題，在大數(shù)據(jù)背景下，人們需要建立新的采樣理論體系。
鳳維明，愛丁堡大學(xué)博士后。于2016年在電子科技大學(xué)信息與通信工程學(xué)院獲得工學(xué)學(xué)士學(xué)位，并于2021年在南京大學(xué)計算機科學(xué)與技術(shù)系獲得工學(xué)博士學(xué)位。主要研究方向包括采樣和計數(shù)算法、隨機算法、分布式圖算法。在STOC、FOCS、SODA等國際頂級會議以及JACM、SICOMP等權(quán)威期刊上發(fā)表多篇論文。曾獲得博士研究生國家獎學(xué)金、微軟學(xué)者獎學(xué)金、江蘇省省級優(yōu)秀畢業(yè)生和南京大學(xué)優(yōu)秀畢業(yè)生等榮譽。博士畢業(yè)論文曾獲得2021年度CCF優(yōu)秀博士學(xué)位論文獎和江蘇省優(yōu)秀博士學(xué)位論文獎。
第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 分布式JerrumValiantVazirani（JVV）定理117
5.2.1 基本定義117
5.2.2 近似采樣和近似推斷之間的歸約122
5.2.3 分布式JVV采樣算法123
5.3 強空間混合性質(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章 譜獨立性與混合時間
10.1 研究背景408
10.2 主要結(jié)論410
10.2.1 譜獨立性與吉布斯采樣算法混合時間410
10.2.2 圖染色模型上的應(yīng)用414
10.3 混合時間分析418
10.3.1 主定理證明418
10.3.2 局部隨機游走的耦合423
10.4 圖染色模型的譜獨立性430
10.4.1 一般性定理的證明433
10.4.2 邊緣概率上界分析450
10.4.3 邊緣概率上界分析的緊致性456
10.5 本章小結(jié)458
致謝459
參考文獻462
附錄 文中部分專業(yè)名詞中英翻譯對照表481
攻讀博士學(xué)位期間的科研成果484
攻讀博士學(xué)位期間參與的科研課題486
書單推薦
