概率图模型 原理与技术PDF电子书下载

第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

第Ⅰ部分 表示 45

第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

第Ⅱ部分 推理 281

第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

第Ⅲ部分 学习 681

第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.1 0习题 984

第Ⅳ部分 行为与决策 993

第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