概率图模型：原理与技术 [美]Daphne Koller著 王飞跃译 PDF下载

概率图模型将概率论与图论相结合，是当前非常热门的一个机器学习研究方向。本书详细论述了有向图模型（又称贝叶斯网）和无向图模型（又称马尔可夫网）的表示、推理和学习问题，全面总结了人工智能这一前沿研究领域的最新进展。为了便于读者理解，书中包含了大量的定义、定理、证明、算法及其伪代码，穿插了大量的辅助材料，如示例（examples）、技巧专栏（skill boxes）、实例专栏（case study boxes）、概念专栏（concept boxes）等。另外，在第 2章介绍了概率论和图论的核心知识，在附录中介绍了信息论、算法复杂性、组合优化等补充材料，为学习和运用概率图模型提供了完备的基础。

本书可作为高等学校和科研单位从事人工智能、机器学习、模式识别、信号处理等方向的学生、教师和研究人员的教材和参考书。

== 序 言 ==

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

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

Daphne Koller

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

目 录
致谢 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
13.6.1 使用图割的推理 . 572
13.6.2 非二元变量 . 575
13.7 局部搜索算法 * . 579
13.8 小结 ... 580
13.9 相关文献 ... 582
13.10习题 . 584
第 14章混合网络中的推理 589
14.1 引言 ... 589
14.1.1 挑战. 589
14.1.2 离散化 . 590
14.1.3 概述. 591
14.2 高斯网络中的变量消除 ... 592
14.2.1 标准型 . 592
14.2.2 和-积算法 ... 595
14.2.3 高斯置信传播 . 596
14.3 混合网络 ... 598
14.3.1 面临的困难 . 599
14.3.2 混合高斯网络的因子运算 . 601
14.3.3 CLG网络的 EP .. 604
14.3.4 一个“准确的” CLG算法* .. 609
14.4 非线性依赖 ... 613
14.4.1 线性化 . 614
14.4.2 使用高斯近似的期望传播 . 620
14.5 基于粒子的近似方法 ... 624
14.5.1 在连续空间中采样 . 625
14.5.2 贝叶斯网中的前向采样 . 626
14.5.3 马尔可夫链 -蒙特卡罗方法 626
14.5.4 坍塌的粒子 . 627
14.5.5 非参数消息传递 . 628
14.6 总结与讨论 ... 629
14.7 相关文献 ... 630
14.8 习题 ... 631
第 15章时序模型中的推理 635
15.1 推理任务 ... 636
15.2 精确推理 ... 637
15.2.1 状态观测模型的滤波 . 637
15.2.2 作为团树传播的滤波 . 638
15.2.3 DBN中的团树推理 ... 639
15.2.4 复杂情况探讨 . 640
15.3 近似推理 ... 644
15.3.1 核心思想 . 645
15.3.2 因子分解的置信状态方法 . 646
15.3.3 粒子滤波 . 648
15.3.4 确定性搜索方法 . 658
15.4 混合 DBN.. 659
15.4.1 连续模型 . 659
15.4.2 混合模型 . 667
15.5 小结 ... 671
15.6 相关文献 ... 672
15.7 习题 ... 674
第 Ⅲ部分学习
第 16章图模型学习：概述 681
16.1 动机 ... 681
16.2 学习目标 ... 682
16.2.1 密度估计 . 682
16.2.2 具体的预测任务 . 684
16.2.3 知识发现 . 685
16.3 优化学习 ... 686
16.3.1 经验风险与过拟合 . 686
16.3.2 判别式与生成式训练 . 693
16.4 学习任务 ... 695
16.4.1 模型限制 . 695
16.4.2 数据的可观测性 . 696
16.4.3 学习任务的分类 . 697
16.5 相关文献 ... 698
第 17章参数估计 699
17.1 昀大似然估计( MLE) 699
17.1.1 图钉的例子 . 699
17.1.2 昀大似然准则 . 701
17.2 贝叶斯网的 MLE.. 704
17.2.1 一个简单的例子 . 704
17.2.2 全局似然分解 . 706
17.2.3 CPD表 707
17.2.4 高斯贝叶斯网 *... 709
17.2.5 作为 M-投影的昀大似然估计* . 713
17.3 贝叶斯参数估计 ... 714
17.3.1 图钉例子的回顾 . 714
17.3.2 先验分布与后验分布 . 719
17.4 贝叶斯网中的贝叶斯参数估计 ... 723
17.4.1 参数独立性与全局分解 . 723
17.4.2 局部分解 . 727
17.4.3 贝叶斯网学习的先验分布 . 729
17.4.4 MAP估计* . 732
17.5 具有共享参数的学习模型 ... 735
17.5.1 全局参数共享 . 736
17.5.2 局部参数共享 . 741
17.5.3 具有共享参数的贝叶斯推断 . 742
17.5.4 层次先验 *... 744
17.6 泛化分析 * . 750
17.6.1 渐近性分析 . 750
17.6.2 PAC界 751
17.7 小结 ... 757
17.8 相关文献 ... 758
17.9 习题 ... 759
第 18章贝叶斯网中的结构学习 767
18.1 引言 ... 767
18.1.1 问题定义 . 767
18.1.2 方法概述 . 769
18.2 基于约束的方法 ... 769
18.2.1 总体框架 . 769
18.2.2 独立性检验 . 771
18.3 结构得分 ... 774
18.3.1 似然得分 . 774
18.3.2 贝叶斯得分 . 778
18.3.3 单个变量的边缘似然 . 780
18.3.4 贝叶斯网的贝叶斯得分 . 782
18.3.5 理解贝叶斯得分 . 785
18.3.6 先验性 . 787
18.3.7 得分等价性 *... 790
18.4 结构搜索 ... 791
18.4.1 学习树结构网络 . 791
18.4.2 给定顺序 . 793
18.4.3 一般图 . 794
18.4.4 用等价类学习 *... 804
18.5 贝叶斯模型平均 * . 807
18.5.1 基本理论 . 807
18.5.2 基于给定序的模型平均 . 809
18.5.3 一般的情况 . 811
18.6 带有附加结构的学习模型 ... 815
18.6.1 带有局部结构的学习 . 816
18.6.2 学习模板模型 . 819
18.7 总结与讨论 ... 821
18.8 相关文献 ... 822
18.9 习题 ... 825
第 19章部分观测数据 833
19.1 基础知识 ... 833
19.1.1 数据的似然和观测模型 . 833
19.1.2 观测机制的解耦 . 837
19.1.3 似然函数 . 840
19.1.4 可识别性 . 843
19.2 参数估计 ... 846
19.2.1 梯度上升方法 . 846
19.2.2 期望昀大化（ EM）... 852
19.2.3 比较：梯度上升与 EM.. 870
19.2.4 近似推理 *... 876
19.3 使用不完备数据的贝叶斯学习 *.. 880
19.3.1 概述. 880
19.3.2 MCMC采样 ... 881
19.3.3 变分贝叶斯学习 . 887
19.4 结构学习 ... 890
19.4.1 结构得分 . 891
19.4.2 结构搜索 . 898
19.4.3 结构 EM.. 902
19.5 带有隐变量的学习模型 ... 907
19.5.1 隐变量的信息内容 . 908
19.5.2 确定基数 . 909
19.5.3 引入隐变量 . 912
19.6 小结 ... 914
19.7 相关文献 ... 915
19.8 习题 ... 917
第 20章学习无向模型 927
20.1 概述 ... 927
20.2 似然函数 ... 928
20.2.1 一个例子 . 928
20.2.2 似然函数的形式 . 930
20.2.3 似然函数的性质 . 930
20.3 昀大（条件）似然参数估计 ... 932
20.3.1 昀大似然估计 . 933
20.3.2 条件训练模型 . 934
20.3.3 用缺失数据学习 . 937
20.3.4 昀大熵和昀大似然 *... 939
20.4 参数先验与正则化 ... 941
20.4.1 局部先验 . 942
20.4.2 全局先验 . 944
20.5 用近似推理学习 ... 945
20.5.1 信念传播 . 945
20.5.2 基于 MAP的学习* 950
20.6 替代目标 ... 953
20.6.1 伪似然及其推广 . 953
20.6.2 对比优化准则 . 957
20.7 结构学习 ... 962
20.7.1 使用独立性检验的结构学习 . 962
20.7.2 基于得分的学习：假设空间 . 964
20.7.3 目标函数 . 965
20.7.4 优化任务 . 968
20.7.5 评估模型的改变 . 975
20.8 小结 ... 978
20.9 相关文献 ... 981
20.10习题 . 984
第 Ⅳ部分行为与决策
第 21章因果关系 993
21.1 动机与概述 ... 993
21.1.1 条件作用与干预 . 993
21.1.2 相关关系和因果关系 . 996
21.2 因果关系模型 ... 998
21.3 结构性因果关系的可识别性 . 1000
21.3.1 查询简化规则 ... 1001
21.3.2 迭代的查询简化 ... 1003
21.4 机制与响应变量 * ... 1009
21.5 函数因果模型中的部分可识别性 * 1013
21.6 虚拟查询 * ... 1017
21.6.1 成对的网络 ... 1017
21.6.2 虚拟查询的界 ... 1020
21.7 学习因果模型 . 1021
21.7.1 学习没有混合因素的因果模型 ... 1022
21.7.2 从干预数据中学习 ... 1025
21.7.3 处理隐变量 *. 1029
21.7.4 学习功能因果关系模型 *.. 1032
21.8 小结 . 1033
21.9 相关文献 . 1034
21.10习题 ... 1035
第 22章效用和决策 .. 1039
22.1 基础：期望效用昀大化 . 1039
22.1.1 不确定性情况下的决策制定 ... 1039
22.1.2 理论证明 *. 1041
22.2 效用曲线 . 1044
22.2.1 货币效用 ... 1044
22.2.2 风险态度 ... 1046
22.2.3 合理性 ... 1047
22.3 效用的获取 . 1048
22.3.1 效用获取过程 ... 1048
22.3.2 人类生命的效用 ... 1049
22.4 复杂结果的效用 . 1050
22.4.1 偏好和效用独立性 *. 1051
22.4.2 加法独立性特性 ... 1053
22.5 小结 . 1060
22.6 相关文献 . 1061
22.7 习题 . 1063
第 23章结构化决策问题 .. 1065
23.1 决策树 . 1065
23.1.1 表示... 1065
23.1.2 逆向归纳算法 ... 1067
23.2 影响图 . 1068
23.2.1 基本描述 ... 1068
23.2.2 决策规则 ... 1070
23.2.3时间与记忆 ... 1071
23.2.4 语义与昀优性准则 ... 1072
23.3 影响图的逆向归纳 . 1075
23.3.1 影响图的决策树 ... 1075
23.3.2 求和-昀大化-求和规则 1077
23.4 期望效用的计算 . 1079
23.4.1 简单的变量消除 ... 1079
23.4.2 多个效用变量：简单的方法 ... 1080
23.4.3 广义变量消除 *. 1081
23.5 影响图中的昀优化 . 1086
23.5.1 昀优化一个单一的决策规则 ... 1086
23.5.2 迭代优化算法 ... 1087
23.5.3 策略关联与全局昀优性 *. 1089
23.6 忽略无关的信息 * ... 1097
23.7 信息的价值 . 1100
23.7.1 单一观察 ... 1100
23.7.2 多重观察 ... 1103
23.8 小结 . 1105
23.9 相关文献 . 1106
23.10习题 ... 1108
第 24章结束语 .. 1113
附录 A背景材料 1117
A.1信息论 .. 1117
A.1.1 压缩和熵 . 1117
A.1.2 条件熵与信息 . 1119
A.1.3 相对熵和分布距离 . 1120
A.2收敛界 .. 1123
A.2.1 中心极限定理 . 1124
A.2.2 收敛界 . 1125
A.3算法与算法复杂性 .. 1126
A.3.1 基本图算法 .. 1126
A.3.2 算法复杂性分析 .. 1127
A.3.3 动态规划 .. 1129
A.3.4 复杂性理论 .. 1130
A.4组合优化与搜索 .. 1134
A.4.1 优化问题 .. 1134
A.4.2 局部搜索 .. 1134
A.4.3 分支限界搜索 .. 1141
A.5连续昀优化 .. 1142
A.5.1 连续函数昀优解的刻画 .. 1142
A.5.2 梯度上升方法 .. 1144
A.5.3 约束优化 .. 1148
A.5.4 凸对偶性 .. 1152
参考文献 1155
符号索引 1191
主题索引 1195