吉布斯分布的局部、动态与快速采样算法

作者: 凤维明著

出版社: 机械工业出版社

出版时间: 2023-03

版次: 1

ISBN: 9787111716853

定价: 89.00

装帧: 其他

开本: 32开

纸张: 胶版纸

页数: 512页

字数: 305千字

分类: 计算机与互联网

7 张插图图片

2人买过

《吉布斯分布的局部、动态与快速采样算法》由爱丁堡大学博士后凤维明撰写，内容荣获2021年度CCF优秀博士学位论文奖。全书立足大数据背景下的新问题，从分布式采样和动态采样两个具体问题入手，给出了有理论保障的算法并研究了新模型下采样问题的复杂性。
  《吉布斯分布的局部、动态与快速采样算法》共十章，分为四个部分：
  第零部分（第1~2章）主要介绍了全书的研究背景、研究问题、研究成果，向读者讲解了全书的结构和章节安排，之后给出了吉布斯分布和采样问题的严格数学定义，介绍全书中经常使用的相关概念，并总结一部分已有的算法设计和分析技术。
  第一部分（第3~5章）从算法和复杂性两个层面介绍有关局部采样的研究成果。
  第二部分（第6~8章）给出了两种不同的动态采样算法设计技术，并分析相应的算法性能。
  第三部分（第9~10章）研究了经典的公开问题，给出了一种新的快速采样算法设计技术和一种新的马尔可夫链收敛时间分析技术。
  所有介绍新结果的章节都给出了相应的本章小结，总结了该章的研究成果，列举了该方向遗留的公开问题。凤维明，爱丁堡大学博士后。于2016年在电子科技大学信息与通信工程学院获得工学学士学位，并于2021年在南京大学计算机科学与技术系获得工学博士学位。主要研究方向包括采样和计数算法、随机算法、分布式图算法。在STOC、FOCS、SODA等国际顶级会议以及JACM、SICOMP等权威期刊上发表多篇论文。曾获得博士研究生国家奖学金、微软学者奖学金、江苏省省级优秀毕业生和南京大学优秀毕业生等荣誉。博士毕业论文曾获得2021年度CCF优秀博士学位论文奖和江苏省优秀博士学位论文奖。第1部分　绪论与预备知识

第1章　绪论

1.1　研究背景2

1.2　研究问题6

1.3　主要成果11

1.4　本书结构与章节安排15

第2章　吉布斯分布与预备知识

2.1　吉布斯分布17

2.1.1　概率图模型17

2.1.2　自旋系统与具体模型21

2.2　采样与近似计数23

2.3　马尔可夫链25

2.3.1　基本概念25

2.3.2　马尔可夫链蒙特卡洛方法26

2.3.3　混合时间分析工具29

第2部分　分布式采样

第3章　分布式采样总览

3.1　分布式计算与LOCAL模型44

3.2　分布式采样与分布式计数46

3.3　分布式采样部分章节安排48

第4章　分布式采样算法

4.1　问题定义50

4.2　局部梅特罗波利斯算法51

4.2.1　算法与主要结论51

4.2.2　局部梅特罗波利斯算法的平稳分布54

4.2.3　局部梅特罗波利斯算法的混合时间61

4.3　梅特罗波利斯算法的分布式模拟68

4.3.1　主要结论71

4.3.2　模拟算法74

4.3.3　算法分析84

4.4　本章小结101

第5章　分布式采样复杂性

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　强空间混合性质与分布式采样/计数138

5.4　本章小结143

第3部分　动态采样

第6章　动态采样总览

6.1　研究背景146

6.2　问题定义147

6.3　主要结论149

第7章　条件吉布斯采样技术

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　本章小结209

第8章　动态马尔可夫链技术

8.1　动态吉布斯采样算法210

8.1.1　动态自旋系统上马尔可夫链的耦合211

8.1.2　动态马尔可夫链的数据结构215

8.1.3　动态吉布斯采样算法分析217

8.2　动态马尔可夫链在推断问题上的应用223

8.2.1　支持多参数更新的动态马尔可夫链226

8.2.2　算法的实现与分析233

8.3　本章小结241

第4部分　快速采样算法

第9章　洛瓦兹局部引理采样问题

9.1　研究背景244

9.2　主要结论246

9.3　基本定义与背景知识252

9.4　采样算法256

9.4.1　CNF公式满足解采样算法256

9.4.2　状态压缩技术265

9.4.3　一般约束满足问题采样算法273

9.5　算法分析278

9.5.1　主定理证明279

9.5.2　投影策略的构造290

9.5.3　InvSample子程序分析301

9.5.4　混合时间分析316

9.6　局部引理问题实例的近似计数389

9.7　本章小结406

第10章　谱独立性与混合时间

10.1　研究背景408

10.2　主要结论410

10.2.1　谱独立性与吉布斯采样算法混合时间410

10.2.2　图染色模型上的应用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　本章小结458

致谢459

参考文献462

附录　文中部分专业名词中英翻译对照表481

攻读博士学位期间的科研成果484

攻读博士学位期间参与的科研课题486
内容简介:
《吉布斯分布的局部、动态与快速采样算法》由爱丁堡大学博士后凤维明撰写，内容荣获2021年度CCF优秀博士学位论文奖。全书立足大数据背景下的新问题，从分布式采样和动态采样两个具体问题入手，给出了有理论保障的算法并研究了新模型下采样问题的复杂性。
  《吉布斯分布的局部、动态与快速采样算法》共十章，分为四个部分：
  第零部分（第1~2章）主要介绍了全书的研究背景、研究问题、研究成果，向读者讲解了全书的结构和章节安排，之后给出了吉布斯分布和采样问题的严格数学定义，介绍全书中经常使用的相关概念，并总结一部分已有的算法设计和分析技术。
  第一部分（第3~5章）从算法和复杂性两个层面介绍有关局部采样的研究成果。
  第二部分（第6~8章）给出了两种不同的动态采样算法设计技术，并分析相应的算法性能。
  第三部分（第9~10章）研究了经典的公开问题，给出了一种新的快速采样算法设计技术和一种新的马尔可夫链收敛时间分析技术。
  所有介绍新结果的章节都给出了相应的本章小结，总结了该章的研究成果，列举了该方向遗留的公开问题。
作者简介:
凤维明，爱丁堡大学博士后。于2016年在电子科技大学信息与通信工程学院获得工学学士学位，并于2021年在南京大学计算机科学与技术系获得工学博士学位。主要研究方向包括采样和计数算法、随机算法、分布式图算法。在STOC、FOCS、SODA等国际顶级会议以及JACM、SICOMP等权威期刊上发表多篇论文。曾获得博士研究生国家奖学金、微软学者奖学金、江苏省省级优秀毕业生和南京大学优秀毕业生等荣誉。博士毕业论文曾获得2021年度CCF优秀博士学位论文奖和江苏省优秀博士学位论文奖。
目录:
第1部分　绪论与预备知识

第1章　绪论

1.1　研究背景2

1.2　研究问题6

1.3　主要成果11

1.4　本书结构与章节安排15

第2章　吉布斯分布与预备知识

2.1　吉布斯分布17

2.1.1　概率图模型17

2.1.2　自旋系统与具体模型21

2.2　采样与近似计数23

2.3　马尔可夫链25

2.3.1　基本概念25

2.3.2　马尔可夫链蒙特卡洛方法26

2.3.3　混合时间分析工具29

第2部分　分布式采样

第3章　分布式采样总览

3.1　分布式计算与LOCAL模型44

3.2　分布式采样与分布式计数46

3.3　分布式采样部分章节安排48

第4章　分布式采样算法

4.1　问题定义50

4.2　局部梅特罗波利斯算法51

4.2.1　算法与主要结论51

4.2.2　局部梅特罗波利斯算法的平稳分布54

4.2.3　局部梅特罗波利斯算法的混合时间61

4.3　梅特罗波利斯算法的分布式模拟68

4.3.1　主要结论71

4.3.2　模拟算法74

4.3.3　算法分析84

4.4　本章小结101

第5章　分布式采样复杂性

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　强空间混合性质与分布式采样/计数138

5.4　本章小结143

第3部分　动态采样

第6章　动态采样总览

6.1　研究背景146

6.2　问题定义147

6.3　主要结论149

第7章　条件吉布斯采样技术

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　本章小结209

第8章　动态马尔可夫链技术

8.1　动态吉布斯采样算法210

8.1.1　动态自旋系统上马尔可夫链的耦合211

8.1.2　动态马尔可夫链的数据结构215

8.1.3　动态吉布斯采样算法分析217

8.2　动态马尔可夫链在推断问题上的应用223

8.2.1　支持多参数更新的动态马尔可夫链226

8.2.2　算法的实现与分析233

8.3　本章小结241

第4部分　快速采样算法

第9章　洛瓦兹局部引理采样问题

9.1　研究背景244

9.2　主要结论246

9.3　基本定义与背景知识252

9.4　采样算法256

9.4.1　CNF公式满足解采样算法256

9.4.2　状态压缩技术265

9.4.3　一般约束满足问题采样算法273

9.5　算法分析278

9.5.1　主定理证明279

9.5.2　投影策略的构造290

9.5.3　InvSample子程序分析301

9.5.4　混合时间分析316

9.6　局部引理问题实例的近似计数389

9.7　本章小结406

第10章　谱独立性与混合时间

10.1　研究背景408

10.2　主要结论410

10.2.1　谱独立性与吉布斯采样算法混合时间410

10.2.2　图染色模型上的应用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　本章小结458

致谢459

参考文献462

附录　文中部分专业名词中英翻译对照表481

攻读博士学位期间的科研成果484

攻读博士学位期间参与的科研课题486