1️⃣ 有向概率图模型概述
〖摘要〗 有向概率图模型又称贝叶斯网络，
〖原文〗ccs228-notes
〖参考〗CMU 10-708 Slides / CMU 10-708 Lecture Notes / Jordan TextBook, Ch.2(section 2.1) / Koller’s Textbook,Ch. 3
1 简介
我们从 “表示” 的主题开始：如何选择概率分布来模拟世界的某些有趣的方面？
想出一个好的模型并不总是那么容易：在前面已经看到，一个简单的垃圾邮件分类模型需要我们指定一些参数，这些参数与英语单词的数量成指数关系！
在本章中，我们将学习一种避免这些症状的方法。我们准备：
- 学习一种有效且通用的技术，仅使用几个参数来参数化概率分布。
- 了解如何通过有向无环图 (DAG) 优雅地描述生成模型。
- 研究 DAG 的结构与其所描述的分布以及建模假设之间的联系；这不仅会使这些建模假设更加明确，而且还将帮助我们设计更有效的推断算法。
本文中的各种模型都是有向图，也被称为『贝叶斯网络』。我们在后面还会看到另外一种方法：无向图，也称为马尔可夫随机场 (MRF)。 贝叶斯网络能够有效地展示因果关系，而马尔可夫随机场不能。因此，对于随机变量之间没有明确因果关系的问题，马尔可夫随机场更可取。
@QI2AVC7W#Gal_Ghahramani_2015
2 基本符号
为了表示概率图模型，我们为每个重要概念指定了某些符号：
- 变量：$X$，作为一种概念符号，为已实现的值 $(x)$ 提供占位符。
- 值：$x$，变量的一次实现，例如 $x \in [0,1]$ 。
- 索引：可以对变量进行索引 $X^{(i)}_i$ 。通常，下标为维度索引，上标为数据索引（即第几个观测）。
- 随机变量：$X$
- 随机向量：$\boldsymbol{X}$
- 随机矩阵：$\boldsymbol{X}= {X_{i,j}}$
- 参数：通常使用希腊字母，例如 $\alpha,\beta,\theta$ ，参数也可以如变量一样被索引。
2 有向图模型
贝叶斯网络是一个有向无环图 (DAG)，其节点对应于随机变量，边对应于父变量对子变量的直接影响。贝叶斯网络能够以因子分解方式表示随机变量的联合概率，从而实现一组关于分布的条件独立假设的紧凑表示。贝叶斯网络中的每个变量（节点）都可以被视为其父项的随机函数。
有向图模型（贝叶斯网络）指一个概率分布族，该分布族允许紧凑的参数化，并可以使用有向图自然地进行描述。 这种参数化背后的总体思路非常简单。
回想一下，通过链式法则，我们可以将任何概率 $p$ 写为：
$$
p(x_1, x_2, \dotsc, x_n) = p(x_1) p(x_2 \mid x_1) \cdots p(x_n \mid x_{n-1}, \dotsc, x_2, x_1)。
$$
紧凑的贝叶斯网络是一个分布，其中右侧的每个因子仅取决于少数 祖先变量 $x_{A_i}$：
$$
p(x_i \mid x_{i-1}, \dotsc, x_1) = p(x_i \mid x_{A_i})
$$
例如，在一个有五个变量的模型中，我们可以选择用 $p(x_5 \mid x_4, x_3)$ 来近似因子 $p(x_5 \mid x_4, x_3, x_2, x_1)$。在这种情况下，我们写成 $x_{A_5} = {x_4, x_3}$。
当变量是离散型时（现实问题中经常出现），我们可以将因子 $p(x_i\mid x_{A_i})$ 视为一个 概率表，其中行对应于 $x_{A_i}$ 而列对应于 $x_i$ 的可选值；这些条目包含了实际概率 $p(x_i\mid x_{A_i})$。如果每个变量可以取 $d$ 个值并且最多有 $k$ 个祖先，那么整个表将最多包含 $O(d^{k+1})$ 个条目。由于每个变量都有一个表，因此整个概率分布只需要最多 $O(nd^{k+1})$ 个参数来紧凑地描述（与朴素的 $O(d^n)$ 相比）。
2.1 有向图表示
这种形式的分布可以自然地表示为 有向无环图（Directed Acyclic Graphics, DAG），其中顶点对应于随机变量 $x_i$，边表示随机变量之间的依赖关系。特别地，我们将每个节点 $x_i$ 的父节点设置为其祖先 $x_{A_i}$。
例如，考虑一个学生在考试中的成绩 $g$ 的模型。
该成绩取决于考试的难度 $d$ 和学生智力 $i$；同时它会影响该课程教师的推荐信质量 $l$。学生智力 $i$ 也会影响 SAT 分数 $s$。上述变量中，除了 $g$ 可以取 3 个可能值，其他变量都是二值的。下图为该模型的有向概率图：
图中 5 个变量的联合概率分布自然地可以分解为：
$$
p(l, g, i, d, s) = p(l \mid g), p(g \mid i, d), p(i), p(d), p(s \mid i)
$$
此分布的概率图表示显然是一个有向无环图，它直观地指定随机变量之间的相互依赖关系。该图清楚地表明：推荐信取决于成绩等级，而成绩等级又取决于学生智力和考试难度。
另一种解释有向图的方法是描述数据的生成方式。在上例中，为了确定推荐信的质量，我们首先对智力水平和考试难度进行采样；得到这些参数后，对学生成绩等级进行采样；最后，根据该成绩生成推荐信。
回顾前面的垃圾邮件分类示例，我们隐含地假设了电子邮件是根据两步过程生成的：
- 首先，我们选择垃圾邮件/非垃圾邮件标签 $y$；
- 然后，我们以该标签为条件，独立地为每个单词采样是否存在。
2.2 形式定义
形式上，贝叶斯网络是一个有向图 $G = (V,E)$，该图中
- 每个节点 $i \in V$ 对应于随机变量 $x_i$。
- 每个节点都有一个条件概率分布 (CPD) $p(x_i \mid x_{A_i})$，指明了以 $x_i$ 的父节点取值为条件的节点概率。
因此，贝叶斯网络定义了一个概率分布 $p$。我们可以说，如果概率分布 $p$ 能够被分解为一组由有向无环图 $G$ 指定的因子乘积，则可以称概率 $p$ 被 因子分解 在图 $G$ 上。
不难看出，由贝叶斯网络表示的概率是有效的：显然，它将是非负的，并且可以使用归纳法（使用 CPD 是有效概率的事实）证明图中所有变量的所有可能赋值概率之和都为 “1”。相反，我们也可以通过反例证明，当 $G$ 包含环路时，其相应的概率之和可能不等于 “1”。
3 贝叶斯网络的依赖关系
总而言之，贝叶斯网络表示了一个 “可以通过较小的局部条件概率分布（每个变量一个）的乘积形成” 的概率分布。通过这种表达概率的形式，我们能够在模型中引入一些变量独立性假设。
这同时也提出了一个问题：通过使用由指定结构的 $G$ 描述的贝叶斯网络模型，我们究竟做出了哪些独立性假设？这个问题非常重要，有两个原因：
- 我们应当也必须准确地知道正在做出何种模型假设（以及它们是否正确）
- 这些信息将直接影响后面的统计推断任务，帮助我们设计更有效的推断算法。
让我们使用符号 $I(p)$ 来表示在联合分布 $p$ 中成立的所有独立性的集合。例如，如果 $p(x,y) = p(x) p(y)$，那么我们说 $x \perp y \in I(p)$。
3.1 有向图描述的独立性
事实证明，贝叶斯网络 $p$ 非常优雅地描述了 $I(p)$ 中的许多独立性；通过查看三种类型的结构，可以从贝叶斯网络中恢复这些独立性。
为简单起见，让我们首先查看具有 $A，B，C$ 三个节点的贝叶斯网络 $G$。在这种情况下，$G$ 本质上只有三种可能的结构，每一种都导致不同的独立性假设。感兴趣的读者可以使用一些代数轻松证明这些结果。
共同父亲：如果 $G$ 的形式为 $A \leftarrow B \rightarrow C$，并且观测到 $B$，则有 $A \perp C \mid B$ 。但如果未观测到 $B$ ，则有 $A \not\perp C$。直观地说，这源于 $B$ 包含决定 $A$ 和 $C$ 结果的所有信息；一旦被观测到，就没有其他因素会影响这些变量的结果。
级联：如果 $G$ 的形式为 $A \rightarrow B \rightarrow C$，并且观测到 $B$，则 $A \perp C \mid B$。但是，如果 $B$ 未被观测到，则 $A \not\perp C$。在这里，直觉再次是 $B$ 持有决定 $C$ 结果的所有信息；因此，$A$ 取什么值并不重要。
V-结构（也称为 explaining away）：如果 $G$ 的形式为 $A \rightarrow C \leftarrow B$，则知道 $C$ 将耦合 $A$ 和 $B$。换句话说，如果 $C$ 未被观测到，则 $A \perp B$，但如果 $C$ 被观测到，则 $A \not\perp B \mid C$。这种情况需要额外的解释。假设 $C$ 是一个布尔变量，表示我们的草坪是否在一天早上潮湿； $A$ 和 $B$ 是它潮湿的两种解释：要么下雨（以 $A$ 表示），要么洒水器打开（以 $B$ 表示）。如果知道草是湿的（$C$ 为真）并且洒水器没有开（$B$ 为假），那么 $A$ 为真的概率必须为 $1$，因为这是唯一可能的解释。因此，在给定 $C$ 的情况下，$A$ 和 $B$ 之间并不是独立的。
上述三种结构清楚地描述了由三变量贝叶斯网络编码的各种独立性。我们可以在任何更大的概率图上递归地使用它们，以扩展到更一般的贝叶斯网络上。这导致了一个称为 $d$-分离（$d$-separation） 的新概念（其中 $d$ 代表有向）。
假设 $Q$、$W$ 和 $O$ 是贝叶斯网络 $G$ 中的三组节点。我们称 $Q$ 和 $W$ 之间在给定 $O$ （即观测到 $O$）时是 $d$ -分离的，如果 $Q$ 和$W$ 之间没有其他 活动路径 连接。
这涉及活跃路径的定义，$G$ 中的无向路径在给定观测变量 $O$ 的情况下被称为 活跃的，如果对于路径上每个连续的变量 $X,Y,Z$ 三元组，以下其中一项成立：
- $X \leftarrow Y \leftarrow Z$，并且 $Y$ 未被观测到 $Y \not\in O$
- $X \rightarrow Y \rightarrow Z$，$Y$ 未被观测到 $Y \not\in O$
- $X \leftarrow Y \rightarrow Z$，$Y$ 未被观测到 $Y \not\in O$
- $X \rightarrow Y \leftarrow Z$，并观测到$Y$ 或其任何后代。
例如，在上图中，给定 $X_2、X_3$，$X_1$ 和 $X_6$ 是 $d$ -分隔的。但是，给定 $X_1, X_6$ 时，$X_2, X_3$ 之间不是 $d$ -分离的，因为可以找到一条活动路径 $(X_2, X_6, X_5, X_3)$
$d$ -分离的概念很有用，因为它让我们能够描述模型中的大块依赖项。设 $I(G) = {(X \perp Y \mid Z) : \text{X,Y are d-sep given Z}}$ 是 $G$ 中一组 $d$ -分离的变量。
事实 ：如果 $p$ 对 $G$ 上做因子分解，则 $I(G) \subseteq I(p)$。在这种情况下，我们说 $G$ 是 $p$ 的 $I$ -映射（独立映射的意思）。
换句话说，在 $G$ 中编码的所有独立性都是正确的：在 $G$ 中 $d$ 分隔的变量在 $p$ 中也是真正独立的。然而，反之则不成立：一个分布可能会在 $G$ 上因子分解，但可能具有 $G$ 中未捕获的独立性。
在某种程度上，这几乎是一个微不足道的陈述。如果 $p(x,y) = p(x)p(y)$，那么这个分布仍然在图 $y \rightarrow x$ 上进行因子分解，因为我们总是可以把它写成 $p(x ,y) = p(x\mid y)p(y)$ 带一个 CPD $p(x\mid y)$ ，其中 $x$ 的概率实际上不随 $y$ 变化。但是，我们可以通过简单地删除不必要的边来构造一个与 $p$ 结构匹配的图。
3.2 有向图的表示能力
这提出了我们最后一个或许也是最重要的问题：有向图能否表达任何分布 $p$ 的所有独立性？更正式地说，给定一个分布 $p$，我们可以构造一个图 $G$ 使得 $I(G) = I(p)$ 吗？
首先，注意很容易构造一个 $G$ 使得 $I(G) \subseteq I(p)$。一个完全连接的有向无环图 $G$ 对于任何分布都是一个 $I$-映射，因为 $I(G) = \emptyset$。
一个更有趣的问题是，我们是否可以为 $p$ 找到一个最小的 $I$ -映射 $G$，也就是说，找到一个 $I$ -映射 $G$，使得即使从 $G$ 中删除一条边也会导致它不再是 $I$-映射。这很简单：我们可以从一个完全连接的 $G$ 开始并删除边，直到 $G$ 不再是 $I$-映射为止。一种方法是遵循图的自然拓扑排序，并删除节点祖先，直到不再可能为止；在进行结构学习时，我们将在课程结束时重新审视这种修剪方法。
然而，我们真正感兴趣的是确定任何概率分布 $p$ 是否总是承认一个 完美 映射 $G$，其中 $I(p)=I(G)$。不幸的是，答案是否定的。例如，考虑以下三个变量 $X,Y,Z$ 上的分布 $p$：我们从伯努利分布中采样 $X,Y \sim \text{Ber}(0.5)$，并且设置 $Z = X \text{ xor } Y$（我们称之为 “含嘈异或” ）。可以使用一些代数 ${X \perp Y, Z \perp Y, X \perp Z} \in I(p), \text{but}, Z \perp {Y,X} \not\in I(p)$ 来验证。因此，$X \rightarrow Z \leftarrow Y$ 是 $p$ 的 $I$ -映射，但是我们之前讨论的 3 节点图结构都无法完美描述 $I(p)$，因此这个分布没有完美映射。
一个相关的问题是完美映射在存在时是否是唯一的。同样，情况并非如此，因为 $X \rightarrow Y$ 和 $X \leftarrow Y$ 编码相同的独立性，但会形成不同的图。更一般地说，如果两个贝叶斯网络 $G_1、G_2$ 编码相同的依赖关系 $I(G_1) = I(G_2)$，则它们是 $I$-等价的。
两个贝叶斯网络何时 $I$ -等效呢？为了回答这个问题，让我们回到包含三个变量的简单示例（图 2）。图中的所有有向图都有具有相同的 框架，意味着如果放弃箭头的方向性，我们在所有情况下都会获得相同的无向图。
事实： 如果 $G,G’$ 具有相同的骨架和相同的 $v$ 结构，则 $I(G) = I(G’)$
同样，很容易直观地理解为什么成立。如果变量之间的 $d$ -分离相同，则两个图是 $I$ -等价的。我们可以翻转任何边的方向性，除非它形成一个 $v$ -结构，并且图的 $d$-连接性将保持不变。我们请读者参考 Koller 和 Friedman 的教科书，以获得定理 3.7（第 77 页）的完整证明。
