概率图模型：原理与技术

致谢 29

插图目录 31

算法目录 39

专栏目录 41

第 1章引言 .. 1

1.1动机 . 1

1.2结构化概率模型 . 2

1.2.1 概率图模型 . 3

1.2.2 表示、推理、学习 . 5

1.3概述和路线图 . 6

1.3.1 各章的概述 . 6

1.3.2 读者指南 . 9

1.3.3 与其他学科的联系 ... 10

1.4历史注记 ... 12

第 2章 基础知识 15

2.1概率论 ... 15

2.1.1 概率分布 ... 15

2.1.2 概率中的基本概念 ... 17

2.1.3 随机变量与联合分布 ... 19

2.1.4 独立性与条件独立性 ... 22

2.1.5 查询一个分布 ... 25

2.1.6 连续空间 ... 27

2.1.7 期望与方差 ... 30

2.2图 ... 33

2.2.1 节点与边 ... 33

2.2.2 子图... 34

2.2.3 路径与迹 ... 35

2.2.4 圈与环 ... 36

2.3相关文献 ... 37

2.4习题 ... 38

第Ⅰ部分表示 第 3章贝叶斯网表示 45

3.1独立性性质的利用 ... 45

3.1.1 随机变量的独立性 ... 45

3.1.2 条件参数化方法 ... 46

3.1.3 朴素贝叶斯模型 ... 48

3.2贝叶斯网 ... 51

3.2.1 学生示例回顾 ... 51

3.2.2 贝叶斯网的基本独立性 ... 55

3.2.3 图与分布 ... 59

3.3图中的独立性 ... 68

3.3.1 d-分离 ... 68

3.3.2 可靠性与完备性 ... 71

3.3.3 d-分离算法 ... 73

3.3.4 I-等价 75

3.4从分布到图 ... 77

3.4.1 昀小 I-map 78

3.4.2 P-map 80

3.4.3 发现 P-map* . 82

3.5小结 ... 91

3.6相关文献 ... 92

3.7习题 ... 95

第 4章无向图模型 .. 103

4.1误解示例 . 103

4.2参数化 . 106

4.2.1 因子. 106

4.2.2 吉布斯分布与马尔可夫网 . 107

4.2.3 简化的马尔可夫网 . 110

4.3马尔可夫网的独立性 . 113

4.3.1 基本独立性 . 113

4.3.2 独立性回顾 . 116

4.3.3 从分布到图 . 119

4.4参数化回顾 . 121

4.4.1 细粒度参数化方法 . 121

4.4.2 过参数化 . 127

4.5贝叶斯网与马尔可夫网 . 132

4.5.1 从贝叶斯网到马尔可夫网 . 132

4.5.2 从马尔可夫网到贝叶斯网 . 136

4.5.3 弦图. 138

4.6部分有向模型 . 140

4.6.1 条件随机场 . 141

4.6.2 链图模型 *... 146

4.7总结与讨论 . 149

4.8相关文献 . 150

4.9习题 . 151

第 5章局部概率模型 .. 155

5.1 CPD表 155

5.2确定性 CPD 156

5.2.1 表示. 156

5.2.2 独立性 . 157

5.3特定上下文 CPD 160

5.3.1 表示. 160

5.3.2 独立性 . 168

5.4因果影响的独立性 . 172

5.4.1 Noisy-or模型 . 172

5.4.2 广义线性模型 . 175

5.4.3 一般公式化表示 . 179

5.4.4 独立性 . 180

5.5连续变量 . 181

5.5.1 混合模型 . 185

5.6条件贝叶斯网 . 187

5.7总结 . 189

5.8相关文献 . 189

5.9习题 . 191

第 6章基于模板的表示 .. 195

6.1引言 . 195

6.2时序模型 . 196

6.2.1 基本假设 . 196

6.2.2 动态贝叶斯网 . 198

6.2.3 状态-观测模型 ... 203

6.3模板变量与模板因子 . 208

6.4对象-关系领域的有向概率模型 211

6.4.1 Plate模型 211

6.4.2 概率关系模型 . 217

6.5无向表示 . 223

6.6结构不确定性 * ... 227

6.6.1 关系不确定性 . 227

6.6.2 对象不确定性 . 230

6.7小结 . 235

6.8相关文献 . 236

6.9习题 . 237

第 7章高斯网络模型 .. 241

7.1多元高斯分布 . 241

7.1.1 基本参数化方法 . 241

7.1.2 高斯分布的运算 . 243

7.1.3 高斯分布的独立性 . 244

7.2高斯贝叶斯网 . 245

7.3高斯马尔可夫随机场 . 248

7.4小结 . 251

7.5相关文献 . 251

7.6习题 . 252

第 8章指数族 .. 255

8.1引言 . 255

8.2指数族 . 255

8.2.1 线性指数族 . 257

8.3因式化的指数族( factored exponential families)... 260

8.3.1 乘积分布( product distributions) 260

8.3.2 贝叶斯网 . 261

8.4熵和相对熵 . 263

8.4.1 熵. 263

8.4.2 相对熵 . 266

8.5投影 . 267

8.5.1 比较. 268

8.5.2 M-投影 270

8.5.3 I-投影 .. 275

8.6小结 . 275

8.7相关文献 . 276

8.8习题 . 276

第Ⅱ部分推理 第 9章精确推理：变量消除 .. 281

9.1复杂性分析 . 281

9.1.1 精确推理分析 . 282

9.1.2 近似推理分析 . 284

9.2变量消除：基本思路 . 286

9.3变量消除 . 290

9.3.1 基本消除 . 290

9.3.2 证据处理 . 295

9.4复杂度与图结构：变量消除 . 298

9.4.1 简单分析 . 298

9.4.2 图论分析 . 299

9.4.3 寻找消除顺序 *... 302

9.5条件作用 * ... 308

9.5.1 条件作用算法 . 308

9.5.2 条件作用与变量消除 . 309

9.5.3 图论分析 . 313

9.5.4 改进的条件作用算法 . 314

9.6用结构 CPD推理*.. 316

9.6.1 因果影响的独立性 . 316

9.6.2 上下文特定的独立性 . 319

9.6.3 讨论. 326

9.7总结和讨论 . 327

9.8相关文献 . 328

9.9习题 . 329

第 10章精确推理：团树 337

10.1 变量消除与团树 ... 337

10.1.1 聚类图 . 337

10.1.2 团树. 338

10.2 消息传递：和积 ... 340

10.2.1 团树中的变量消除 . 341

10.2.2 团树校准 . 346

10.2.3 将校准团树作为一个分布 . 352

10.3 消息传递：置信更新 ... 355

10.3.1 使用除法的消息传递 . 356

10.3.2 和-积与置信-更新消息的等价性 .. 359

10.3.3 回答查询 . 360

10.4 构建一个团树 ... 364

10.4.1 源自变量消除的团树 . 364

10.4.2 源自弦图的团树 . 365

10.5 小结 ... 367

10.6 相关文献 ... 368

10.7 习题 ... 369

第 11章作为优化的推理 373

11.1引言 ... 373

11.1.1 再议精确推理 * ... 374

11.1.2 能量泛函 . 376

11.1.3 优化能量泛函 . 377

11.2作为优化的精确推理 ... 378

11.2.1 不动点刻画 . 379

11.2.2 推理优化 . 382

11.3基于传播的近似 ... 382

11.3.1 一个简单的例子 . 383

11.3.2 聚类图置信传播 . 387

11.3.3 聚类图置信传播的性质 . 391

11.3.4 收敛性分析 * ... 393

11.3.5 构建聚类图 . 395

11.3.6 变分分析 . 401

11.3.7 其他熵近似 * ... 404

11.3.8 讨论. 417

11.4近似消息传播 *.. 419

11.4.1 因子分解的消息 . 419

11.4.2 近似消息计算 . 422

11.4.3 近似消息推理 . 425

11.4.4 期望传播 . 431

11.4.5 变分分析 . 434

11.4.6 讨论. 436

11.5结构化的变分近似 ... 437

11.5.1 平均场近似 . 438

11.5.2 结构化的近似 . 445

11.5.3 局部变分法 * ... 456

11.6总结与讨论 ... 460

11.7相关文献 ... 462

11.8习题 ... 464

第 12章基于粒子的近似推理 475

12.1 前向采样 ... 476

12.1.1 从贝叶斯网中采样 . 476

12.1.2 误差分析 . 478

12.1.3 条件概率查询 . 479

12.2 似然加权与重要性采样 ... 480

12.2.1 似然加权：直觉 . 480

12.2.2 重要性采样 . 482

12.2.3 贝叶斯网的重要性采样 . 486

12.2.4 重要性采样回顾 . 492

12.3 马尔可夫链的蒙特卡罗方法 ... 492

12.3.1 吉布斯采样算法 . 493

12.3.2 马尔可夫链 . 494

12.3.3 吉布斯采样回顾 . 499

12.3.4 马尔可夫链的一个更广泛的类 * ... 502

12.3.5 马尔可夫链的使用 . 505

12.4 坍塌的粒子 ... 512

12.4.1 坍塌的似然加权 *... 513

12.4.2 坍塌的 MCMC ... 517

12.5 确定性搜索方法 * . 522

12.6 小结 ... 525

12.7 相关文献 ... 527

12.8 习题 ... 529

第 13章最大后验概率推理 537

13.1 综述 ... 537

13.1.1 计算复杂性 . 537

13.1.2 解决方法综述 . 538

13.2 (边缘) MAP的变量消除.. 540

13.2.1 昀大-积变量消除 ... 540

13.2.2 找到昀可能的赋值 . 542

13.2.3 边缘 MAP的变量消除* 545

13.3 团树中的昀大 -积.. 547

13.3.1 计算昀大 -边缘 ... 548

13.3.2 作为再参数化的信息传递 . 549

13.3.3 昀大-边缘解码 ... 550

13.4 多圈聚类图中的昀大 -积置信传播 .. 553

13.4.1 标准昀大 -积消息传递 ... 553

13.4.2 带有计数的昀大 -积 BP* 557

13.4.3 讨论. 560

13.5 作为线性优化问题的 MAP* 562

13.5.1 整数规划的公式化 . 562

13.5.2 线性规划松弛 . 564

13.5.3 低温极限 . 566

13.6 对 MAP使用图割. 572

很高兴能够看到我们所著的《概率图模型》一书被翻译为中文出版。我们了解到这本书涵盖的课题已在中国引起了巨大的兴趣。已有众多中国读者写信向我们解释这本书对于他们的学习的重要性，并希望获得更易理解的版本。随着众多来自中国研究机构或国外研究机构的中国学者署名或共同署名的文章的发表，中国研究者已在概率图领域中扮演了非常重要的角色。这些文章对于概率图模型领域的发展起到了非常重要的作用。我们相信《概率图模型》中文版的出版将帮助许多中国读者学习并掌握这一重要课题的基础。同时，这也将进一步提高中国学者应用概率图模型思想的能力，并为这一领域的发展做出贡献。

本书的翻译工作由王飞跃研究员主导，并得到了王珏研究员及其众多助手和合作者的支持。这是一份历时 5年、具有里程碑意义的努力，我深深地感谢该团队所有为本书翻译做出贡献的人员。我尤其希望借此机会感谢王珏研究员——一位中国机器学习领域的开拓者。王珏研究员是此项翻译工作的十分重要的推动者。没有他的支持，没有他的众多杰出的机器学习领域的学生的帮助，可能这项工作到现在还没有结果。很遗憾王珏研究员于 2014年 12月死于癌症，终年 66岁，已不能看到他努力的结果。然而，他的思想活在他的学生们的工作中，与本书的出版同在。

Daphne Koller

（复杂系统管理与控制国家重点实验室王晓翻译）