第 11 章　概率图模型

第三部分 · 进阶模型课件 80 页讲义约 40 分钟Probabilistic Graphical Models

▶ 浏览课件⬇ 课件 PDF（5 MB）📖 教材原书 PDF✎ 习题

学习目标

• 理解概率图模型用图结构分解高维联合分布的思想，以及“表示—学习—推断”三个基本问题；
• 掌握贝叶斯网络的因子分解和局部马尔可夫性质，能判断几种典型结构中的条件独立性；
• 掌握马尔可夫随机场的团势能分解（Hammersley–Clifford 定理），了解对数线性模型与条件随机场；
• 掌握 EM 算法的推导（ELBO）及其在高斯混合模型上的应用，理解与 K 均值的关系；
• 理解变量消除与信念传播（和积算法）；
• 掌握拒绝采样、重要性采样、Metropolis–Hastings 和吉布斯采样。

课件幻灯片

1 / 80

跳转到1. 概率图模型2. 如何表示高维随机向量的概率密度？3. 概率图模型4. 概率图模型5. 概率图模型6. 模型表示7. 贝叶斯网络8. 练习9. 局部马尔可夫性质10. 条件独立性11. 常见的有向图模型12. 隐马尔可夫模型（Hidden Markov Model，HMM）13. 高斯混合模型14. 高斯混合模型15. 概率主题模型16. 概率主题模型17. 有向图模型18. 马尔可夫随机场19. 无向图的马尔可夫性20. 团（Clique）21. Hammersley-Clifford定理22. 无向图模型23. Illustration: Image De-Noising (1)24. Illustration: Image De-Noising (2)25. Illustration: Image De-Noising (3)26. Illustration: Image De-Noising (4)27. 常见的无向图模型28. 模型对比29. 有向图和无向图的转换30. 有向图和无向图的转换31. 道德图（Moral Graph ）32. 有向图和无向图33. 有向图和无向图34. 学习35. 有向图模型36. 无向图模型37. 含隐变量的参数估计38. 含隐变量的参数学习39. 高斯混合模型40. 一个简单的解法：K-means41. K-means算法42. K-means算法43. 期望最大化（Expectation-Maximum，EM ）算法44. 另外一种推导45. EM算法46. 收敛性47. GMM Revisit48. GMM Revisit49. GMM Revisit50. GMM的参数学习51. GMM的参数学习52. k-means clustering vs. EM clustering53. 推断（ Inference ）54. Inference in Graphical Models55. 推断56. 如何有效地计算边际概率？57. 变量消去法58. 信念传播算法59. 链上的消息传递60. 链上的消息传递61. 链式结构图模型的信念传播过程62. 更一般的推断63. 近似推断64. 基于采样法的近似推断65. 采样法（ Sampling Method ）66. 采样法67. 拒绝采样68. 拒绝采样69. 重要性采样70. 马尔可夫过程71. 马尔可夫链72. 平稳分布（ Stationary Distribution ）73. 细致平稳条件74. 马尔可夫链蒙特卡罗方法75. Metropolis-Hastings算法76. （图示）77. Metropolis算法78. 吉布斯采样79. 使用MCMC方法的注意事项80. https://nndl.github.io/

PDF

提示：点击幻灯片左右两侧或使用 ← → 键翻页，手机上左右滑动；按 F 全屏。

讲义

11.1 为什么需要概率图模型

一个 $K$ 维的离散随机向量 $\mathit{X}=[X_1,\cdots ,X_K]$，若每个变量有 $m$ 个取值，其联合概率表需要 $m^K-1$ 个参数——参数数量随维数指数增长。如果变量之间存在条件独立性，联合分布就可以分解为若干局部条件概率的乘积，参数大大减少。幻灯片 2

概率图模型用图来描述这种依赖关系：节点表示随机变量，边表示变量之间的概率依赖。它涉及三个基本问题：幻灯片 3 幻灯片 5

• 表示问题：如何用图结构描述变量之间的依赖关系（有向图 / 无向图）；
• 学习问题：图结构的学习和参数的估计；
• 推断问题：已知部分变量时，计算其他变量的条件概率分布。

flowchart LR
  P["概率图模型"] --> R["表示"]
  P --> L["学习"]
  P --> I["推断"]
  R --> R1["有向图：贝叶斯网络"]
  R --> R2["无向图：马尔可夫随机场"]
  L --> L1["完全观测：最大似然"]
  L --> L2["含隐变量：EM 算法"]
  I --> I1["精确推断：变量消除、信念传播"]
  I --> I2["近似推断：采样法、变分法"]

11.2 有向图模型：贝叶斯网络

贝叶斯网络用有向无环图表示变量间的因果关系。若 ${\pi }_k$ 为 $X_k$ 的父节点集合，则联合分布可分解为局部条件概率的乘积：幻灯片 7

$$p(\mathit{x})=\prod _{k=1}^{K}p(x_k\mid {\mathit{x}}_{{\pi }_k}).$$

条件独立性。对三个变量的四种典型结构：幻灯片 10

结构	示意	独立性
间接因果	$X_1\to X_2\to X_3$	已知 $X_2$ 时 $X_1\perp X_3$
间接果因	$X_1\leftarrow X_2\leftarrow X_3$	已知 $X_2$ 时 $X_1\perp X_3$
共因	$X_1\leftarrow X_2\to X_3$	已知 $X_2$ 时 $X_1\perp X_3$
共果（V 结构）	$X_1\to X_2\leftarrow X_3$	$X_1\perp X_3$；已知 $X_2$ 时反而不独立

局部马尔可夫性质：每个变量在给定父节点时，与其非后代变量条件独立，$X_k\perp Z\mid X_{{\pi }_k}$。幻灯片 9

常见的有向图模型：幻灯片 11

• Sigmoid 信念网络：$p(x_k=1\mid {\mathit{x}}_{{\pi }_k};\theta )=\sigma ({\theta }_0+\sum _{x_i\in {\mathit{x}}_{{\pi }_k}}{\theta }_i{x}_i)$，局部条件概率由 Logistic 函数参数化，参数量从指数级降为线性；
• 朴素贝叶斯：给定类别 $y$ 时各特征条件独立，$p(y\mid \mathit{x})\propto p(y)\prod _{d}p(x_d\mid y)$；
• 隐马尔可夫模型（HMM）：隐状态序列构成马尔可夫链，观测只依赖当前隐状态，$p(\mathit{x},\mathit{y})=\prod _{t=1}^{T}p(y_t\mid y_{t-1})p(x_t\mid y_t)$；幻灯片 12
• 高斯混合模型（GMM）：先按 ${\pi }_k$ 选择一个成分 $z$，再从对应高斯分布生成 $\mathit{x}$，$p(\mathit{x})=\sum _{k=1}^K{\pi }_k\mathcal{N}(\mathit{x};{\mathit{\mu }}_k,{\mathbf{\Sigma }}_k)$；幻灯片 13
• 概率主题模型（LDA）：每篇文档有一个主题分布，每个词先选主题、再从主题的词分布中生成。幻灯片 15

11.3 无向图模型：马尔可夫随机场

马尔可夫随机场（马尔可夫网络）用无向图表示变量间的相互作用（无明确因果方向），满足局部马尔可夫性：给定一个变量的所有邻居，它与其他所有变量条件独立，$X_k\perp {\mathit{X}}_{\setminus \mathcal{N}(k),\setminus k}\mid {\mathit{X}}_{\mathcal{N}(k)}$。幻灯片 18 幻灯片 19

无向图的联合分布用团来分解。团是全连通的节点子集，不能再加入任何节点的团称为最大团。幻灯片 20 Hammersley–Clifford 定理：如果一个分布 $p(\mathit{x})>0$ 满足无向图中的局部马尔可夫性质，当且仅当它可以表示为一系列定义在最大团上的非负函数的乘积：幻灯片 21

$$p(\mathit{x})=\frac{1}{Z}\prod _{c\in \mathcal{C}}{\varphi }_c({\mathit{x}}_c),Z=\sum _{\mathit{x}}\prod _{c\in \mathcal{C}}{\varphi }_c({\mathit{x}}_c).$$

${\varphi }_c$ 称为势能函数，$Z$ 为配分函数。由于势能函数必须为正，一般定义为 ${\varphi }_c({\mathit{x}}_c)=\exp (-E_c({\mathit{x}}_c))$，这样的分布也称为吉布斯分布或玻尔兹曼分布：$p(\mathit{x})=\frac{1}{Z}\exp (-\sum _c{E}_c({\mathit{x}}_c))$。

示例：图像去噪。把每个像素的真实值作为隐变量 $y_i$，观测的带噪像素为 $x_i$；能量函数包括“$y_i$ 与 $x_i$ 尽量一致”和“相邻像素 $y_i,y_j$ 尽量一致”两项，最小化能量即可得到去噪后的图像。幻灯片 23 幻灯片 26

常见的无向图模型：幻灯片 27

• 对数线性模型（最大熵模型）：势能函数取 ${\varphi }_c({\mathit{x}}_c\mid {\theta }_c)=\exp ({\theta }_c^{\mathrm{\top }}{f}_c({\mathit{x}}_c))$，$p(\mathit{x};\theta )=\frac{1}{Z(\theta )}\exp (\sum _c{\theta }_c^{\mathrm{\top }}{f}_c({\mathit{x}}_c))$；用于分类时 $p(y\mid \mathit{x})=\frac{1}{Z(\mathit{x};\theta )}\exp ({\theta }^{\mathrm{\top }}f(\mathit{x},y))$，这正是 Softmax 回归。
• 条件随机场（CRF）：直接建模条件概率 $p(\mathit{y}\mid \mathit{x})$ 的无向图模型，常用于序列标注。线性链条件随机场：$p(\mathit{y}\mid \mathit{x};\theta )=\frac{1}{Z(\mathit{x};\theta )}\exp (\sum _{t=1}^T{\theta }_1^{\mathrm{\top }}{f}_1(\mathit{x},y_t)+\sum _{t=1}^{T-1}{\theta }_2^{\mathrm{\top }}{f}_2(\mathit{x},y_t,y_{t+1}))$。

有向图与无向图的转换。把有向图转换为无向图时，需要保证每个局部条件概率 $p(x_k\mid {\mathit{x}}_{{\pi }_k})$ 都落在某个团中，因此要把同一节点的所有父节点两两相连，并去掉边的方向，这个过程称为道德化，得到的无向图称为道德图。道德化可能会丢失一些条件独立性（例如 V 结构的边缘独立性）。幻灯片 29 幻灯片 31

11.4 学习

完全观测时的参数估计：有向图模型的对数似然分解为各局部条件概率的对数似然之和，可以分别独立地估计。幻灯片 35 无向图模型的对数似然为

$$\mathcal{L}(\theta )=\frac{1}{N}\sum _{n=1}^N\log p({\mathit{x}}^{(n)};\theta ),\frac{\partial \mathcal{L}}{\partial {\theta }_c}={\mathbb{E}}_{\mathit{x}\sim \tilde{p}}[f_c({\mathit{x}}_c)]-{\mathbb{E}}_{\mathit{x}\sim p(\mathit{x};\theta )}[f_c({\mathit{x}}_c)],$$

即“经验分布下的期望 − 模型分布下的期望”。后者因为配分函数通常难以计算，需要采样近似（见第 12 章的对比散度）。幻灯片 36

含隐变量的参数学习：EM 算法。当模型包含隐变量 $\mathit{z}$ 时，边际似然 $\log p(\mathit{x};\theta )=\log \sum _{\mathit{z}}p(\mathit{x},\mathit{z};\theta )$ 中对数里有求和，难以直接优化。引入一个关于 $\mathit{z}$ 的分布 $q(\mathit{z})$，由 Jensen 不等式得到证据下界（ELBO）：幻灯片 37 幻灯片 38

$$\log p(\mathit{x};\theta )=\underset{\mathrm{ELBO}(q,\mathit{x};\theta )}{\underbrace{\sum _{\mathit{z}}q(\mathit{z})\log \frac{p(\mathit{x},\mathit{z};\theta )}{q(\mathit{z})}}}+\mathrm{KL}(q(\mathit{z})\parallel p(\mathit{z}\mid \mathit{x};\theta ))\ge \mathrm{ELBO}(q,\mathit{x};\theta ).$$

期望最大化（EM）算法交替地优化 ELBO：幻灯片 43 幻灯片 45

• E 步：固定 ${\theta }_t$，令 $q_{t+1}(\mathit{z})=p(\mathit{z}\mid \mathit{x};{\theta }_t)$，此时 KL 为 0，ELBO 等于对数似然；
• M 步：固定 $q_{t+1}$，求 ${\theta }_{t+1}=\arg \underset{\theta }{max}\mathrm{ELBO}(q_{t+1},\mathit{x};\theta )$。

每次迭代都不会使对数似然下降，因此 EM 算法收敛到似然函数的局部最优（或鞍点）。幻灯片 46

示例：高斯混合模型。幻灯片 47 幻灯片 50 E 步计算每个样本属于第 $k$ 个成分的后验概率（“责任”）：

$${\gamma }_{nk}=p(z^{(n)}=k\mid {\mathit{x}}^{(n)})=\frac{{\pi }_k\mathcal{N}({\mathit{x}}^{(n)};{\mathit{\mu }}_k,{\mathit{\sigma }}_k)}{\sum _{j=1}^K{\pi }_j\mathcal{N}({\mathit{x}}^{(n)};{\mathit{\mu }}_j,{\mathit{\sigma }}_j)};$$

M 步令 $N_k=\sum _n{\gamma }_{nk}$，更新

$${\pi }_k=\frac{N_k}{N},{\mathit{\mu }}_k=\frac{1}{N_k}\sum _{n=1}^N{\gamma }_{nk}{\mathit{x}}^{(n)},{\sigma }_k^2=\frac{1}{N_k}\sum _{n=1}^N{\gamma }_{nk}({\mathit{x}}^{(n)}-{\mathit{\mu }}_k{)}^2.$$

K 均值可以看作 GMM 的一个特例：当所有成分共享方差且方差趋于 0 时，“软”的责任 ${\gamma }_{nk}$ 变成“硬”的 0/1 指派——E 步把样本分给最近的中心，M 步把中心更新为簇内样本的均值。幻灯片 40 幻灯片 42

11.5 推断

推断是指在观测到部分变量 $\mathit{e}$ 时，计算其他变量的某个子集 $\mathit{q}$ 的条件概率 $p(\mathit{q}\mid \mathit{e})=\frac{p(\mathit{q},\mathit{e})}{p(\mathit{e})}$。因此推断的关键是计算边际概率 $p(\mathit{q},\mathit{e})=\sum _{\mathit{z}}p(\mathit{q},\mathit{e},\mathit{z})$。直接求和的复杂度随变量个数指数增长。幻灯片 55 幻灯片 56

变量消除法：利用乘法对加法的分配律，把求和“推”到只与相关因子有关的位置，逐个消去变量。例如对链 $x_1-x_2-x_3-x_4$：幻灯片 57

$$p(x_4)=\sum _{x_3}\varphi (x_3,x_4)\sum _{x_2}\varphi (x_2,x_3)\sum _{x_1}\varphi (x_1,x_2),$$

计算量从 $O(m^4)$ 降为 $O(3m^2)$。但每计算一个边际概率都要重新消除一遍，存在重复计算。

信念传播算法（和积算法）把变量消除中的中间结果看作在相邻节点之间传递的消息，并加以复用。幻灯片 58 在链上，第 $t$ 个节点向第 $t+1$ 个节点传递的前向消息为 ${\mu }_{t,t+1}(x_{t+1})=\sum _{x_t}\varphi (x_t,x_{t+1}){\mu }_{t-1,t}(x_t)$，反向消息类似。一个节点的边际概率正比于它收到的所有消息的乘积：$p(x_t)\propto {\mu }_{t-1,t}(x_t){\mu }_{t+1,t}(x_t)$。只需一次前向、一次反向传递，就能得到所有节点的边际概率。幻灯片 59 幻灯片 61 对树结构的图同样可以精确推断；对有环图，可以把它转换为联合树，或者直接迭代传递消息（环路信念传播，近似推断）。幻灯片 62

11.6 近似推断：采样法

在实际应用中，精确推断往往不可行，需要近似推断：环路信念传播、变分推断（用简单分布近似复杂后验，见第 13 章 VAE）和采样法。幻灯片 63

采样法（蒙特卡罗方法）：要计算 ${\mathbb{E}}_p[f(x)]=\int f(x)p(x)dx$，可以从 $p(x)$ 中独立采样 $x^{(1)},\cdots ,x^{(N)}$，用 ${\hat{f}}_N=\frac{1}{N}\sum _{n}f(x^{(n)})$ 近似。根据大数定律，$N$ 足够大时它收敛到真实期望。关键问题是：如何从复杂分布中采样？幻灯片 65 幻灯片 66

• 拒绝采样：选一个容易采样的提议分布 $q(x)$ 和常数 $k$，使得 $kq(x)\ge \hat{p}(x)$（$\hat{p}$ 为未归一化的目标分布）。从 $q(x)$ 采样 $\hat{x}$，以接受概率 $\alpha (\hat{x})=\frac{\hat{p}(\hat{x})}{kq(\hat{x})}$ 接受。$kq(x)$ 与 $\hat{p}(x)$ 越接近，接受率越高；高维时接受率往往非常低。幻灯片 67 幻灯片 68
• 重要性采样：不直接从 $p$ 采样，而是从 $q$ 采样并加权：${\mathbb{E}}_p[f(x)]={\mathbb{E}}_q[f(x)w(x)]$，其中重要性权重 $w(x)=\frac{p(x)}{q(x)}$。幻灯片 69

马尔可夫链蒙特卡罗（MCMC）：构造一个马尔可夫链，使其平稳分布恰好是目标分布 $p(x)$；从任意初始状态出发运行足够长时间（预烧期）后，链上的状态就近似服从 $p(x)$。幻灯片 70 幻灯片 74 马尔可夫链满足细致平稳条件 $p(x)T(x^{\prime }\mid x)=p(x^{\prime })T(x\mid x^{\prime })$ 时，$p(x)$ 就是它的平稳分布。幻灯片 72 幻灯片 73

• Metropolis–Hastings 算法：从提议分布 $q(\hat{x}\mid x_t)$ 采样候选 $\hat{x}$，以概率幻灯片 75$$\alpha (\hat{x},x_t)=min(1,\frac{p(\hat{x})q(x_t\mid \hat{x})}{p(x_t)q(\hat{x}\mid x_t)})$$接受（$x_{t+1}=\hat{x}$），否则 $x_{t+1}=x_t$。可以验证这样构造的转移满足细致平稳条件。若提议分布对称，$q(\hat{x}\mid x_t)=q(x_t\mid \hat{x})$，接受率简化为 $min(1,\frac{p(\hat{x})}{p(x_t)})$，即 Metropolis 算法。幻灯片 77
• 吉布斯采样：每次只更新一个变量，从其全条件分布 $p(x_i\mid {\mathit{x}}_{\setminus i})$ 中采样。它是 MH 算法的特例，接受率恒为 1。在图模型中，全条件分布只依赖于该变量的马尔可夫毯，计算很方便。幻灯片 78

使用 MCMC 时需注意：预烧期长短难以确定；相邻样本高度相关，可以每隔若干步取一个样本；提议分布的选择会显著影响混合速度。幻灯片 79

本章小结

• 概率图模型用图分解联合分布：有向图 $p(\mathit{x})=\prod _{k}p(x_k\mid {\mathit{x}}_{{\pi }_k})$，无向图 $p(\mathit{x})=\frac{1}{Z}\prod _c{\varphi }_c({\mathit{x}}_c)$。
• 学习：完全观测时最大似然；含隐变量时用 EM 交替最大化 ELBO（GMM、K 均值）。
• 精确推断：变量消除、信念传播（消息传递）；近似推断：采样（拒绝、重要性、MCMC）与变分推断。

思考题与习题

1. （概念，课件练习） 对贝叶斯网络 $X_1\to X_3\leftarrow X_2,X_3\to X_4$，写出联合分布的分解；判断 $X_1\perp X_2$、$X_1\perp X_2\mid X_4$ 是否成立。
2. （计算） 10 个二值变量，完全联合分布需要多少参数？若它们构成一条马尔可夫链，需要多少参数？
3. （推导） 推导 $\log p(\mathit{x};\theta )=\mathrm{ELBO}+\mathrm{KL}(q\parallel p(\mathit{z}\mid \mathit{x};\theta ))$，并说明 EM 算法为什么单调提升似然。
4. （推导） 推导 GMM 中 ${\mathit{\mu }}_k$ 的 M 步更新公式。
5. （推导） 证明 Metropolis–Hastings 算法的转移核满足细致平稳条件。
6. （编程） 用 EM 算法拟合一维两成分 GMM（数据由 $\mathcal{N}(-2,1)$ 和 $\mathcal{N}(3,{0.5}^2)$ 按 3:7 混合生成），画出对数似然随迭代的变化；再用吉布斯采样对同一模型做推断并比较。

部分提示

• 第 1 题：$p=p(x_1)p(x_2)p(x_3\mid x_1,x_2)p(x_4\mid x_3)$。$X_1\perp X_2$ 成立；给定 $X_4$（$X_3$ 的后代）后 V 结构被“激活”，不再独立。
• 第 2 题：$2^{10}-1=1023$；链：$1+9\times 2=19$。
• 第 5 题：对 $x\ne x^{\prime }$，$p(x)q(x^{\prime }\mid x)\alpha (x^{\prime },x)=min(p(x)q(x^{\prime }\mid x),p(x^{\prime })q(x\mid x^{\prime }))$，关于 $x,x^{\prime }$ 对称。

延伸阅读

• 教材：邱锡鹏《神经网络与深度学习》第 11 章「概率图模型」。
• Koller D, Friedman N. Probabilistic Graphical Models: Principles and Techniques, MIT Press, 2009。
• Bishop C M. Pattern Recognition and Machine Learning, 第 8–9、11 章。
• 第二版对应章节：第 14 章「概率图模型」。