目 錄
緻謝 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
· · · · · · (收起)