第 10 章 图模型中的推断即求导Chapter 10 Inference in graphical models as differentiation

考虑一组 $K$ 个变量 ${\bm{s}}\coloneqq({\bm{s}}_{1},\dots,{\bm{s}}_{K})$，它们可以是有序的，也可以是无序的。每个 ${\bm{s}}$ 都属于笛卡尔积 $\mathcal{S}\coloneqq\mathcal{S}_{1}\times\dots\times\mathcal{S}_{K}$。为具体起见，本章始终假设各集合 $\mathcal{S}_{k}$ 是离散的，且 $\mathcal{S}_{k}\coloneqq\{{\bm{v}}_{1},\dots,{\bm{v}}_{M_{k}}\}$。注意，由于 $\mathcal{S}_{k}$ 是离散的，我们总可以将其与 $\{1,\dots,M_{k}\}$ 等同起来。图模型指定了一个联合概率分布We consider a collection of $K$ variables ${\bm{s}}\coloneqq({\bm{s}}_{1},\dots,{\bm{s}}_{K})$, potentially ordered or unordered. Each ${\bm{s}}$ belongs to the Cartesian product $\mathcal{S}\coloneqq\mathcal{S}_{1}\times\dots\times\mathcal{S}_{K}$. Throughout this chapter, we assume that the sets $\mathcal{S}_{k}$ are discrete for concreteness, with $\mathcal{S}_{k}\coloneqq\{{\bm{v}}_{1},\dots,{\bm{v}}_{M_{k}}\}$. Note that because $\mathcal{S}_{k}$ is discrete, we can always identify it with $\{1,\dots,M_{k}\}$. A graphical model specifies a joint probability distribution

其中 $p$ 是该联合概率分布的概率质量函数。对所有可能配置构成的笛卡尔积求和，可得where $p$ is the probability mass function of the joint probability distribution. Summing over the Cartesian product of all possible configurations, we obtain

正如我们将要看到的，图模型的图结构编码了变量 $(S_{1},\dots,S_{K})$ 之间的依赖关系，从而也编码了它们的联合分布如何分解。给定一个联合概率分布，通常需要解决若干推断问题。As we shall see, the graph of a graphical model encodes the dependencies between the variables $(S_{1},\dots,S_{K})$ and therefore how their joint distribution factorizes. Given access to a joint probability distribution, there are several inference problems one typically needs to solve.

一个简单的任务是计算某些观测 ${\bm{s}}=({\bm{s}}_{1},\dots,{\bm{s}}_{K})$ 的似然，A simple task is to compute the likelihood of some observations ${\bm{s}}=({\bm{s}}_{1},\dots,{\bm{s}}_{K})$,

计算对数似然也很常见，It is also common to compute the log-likelihood,

另一个常见任务是计算最可能的配置，Another common task is to compute the most likely configuration,

这是联合概率分布的众数。在文献中，这也被称为最大后验（MAP）推断 [206]。This is the mode of the joint probability distribution. This is also known as maximum a-posteriori (MAP) inference in the literature [206].

边缘化操作是指对联合概率分布中某个给定变量的所有可能取值求和（或积分），由此可以计算其余变量的边缘概率。例如，我们可能希望除 $S_{k}={\bm{s}}_{k}$ 之外，对所有其他变量进行边缘化。为此，我们定义笛卡尔积The operation of marginalization consists in summing (or integrating) over all possible values of a given variable in a joint probability distribution. This allows us to compute the marginal probability of the remaining variables. For instance, we may want to marginalize all variables but $S_{k}={\bm{s}}_{k}$. To do so, we define the Cartesian product

对所有变量求和（$S_{k}$ 除外），得到 $S_{k}={\bm{s}}_{k}$ 的边缘概率，即Summing over all variables but $S_{k}$, we obtain the marginal probability of $S_{k}={\bm{s}}_{k}$ as

类似地定义Defining similarly

可得we obtain

特别地，我们可能希望计算两个相邻变量的边缘概率，$\mathbb{P}(S_{k-1}={\bm{s}}_{k-1},S_{k}={\bm{s}}_{k})$。In particular, we may want to compute the marginal probability of two consecutive variables, $\mathbb{P}(S_{k-1}={\bm{s}}_{k-1},S_{k}={\bm{s}}_{k})$.

另一种常见操作是计算 $\phi(S)$ 在分布 $p$ 下的期望，其定义为Another common operation is to compute the expectation of $\phi(S)$ under a distribution $p$. It is defined by

对于 $p_{\bm{\theta}}$ 下的期望，我们记作For the expectation under $p_{\bm{\theta}}$, we write

在指数族分布（3.4 节）中，函数 $\phi$ 称为统计量，它可以分解为In exponential family distributions (Section 3.4), the function $\phi$ is called a statistic. It decomposes as

其中 $\mathcal{C}\subseteq[K]$。直观地说，$\phi({\bm{s}})$ 可以看作 ${\bm{s}}$（一个可能离散的对象，例如一个整数序列）在向量空间中的编码或嵌入。在这种分解下，我们还可以计算where $\mathcal{C}\subseteq[K]$. Intuitively, $\phi({\bm{s}})$ can be thought of as an encoding or embedding of ${\bm{s}}$ (a potentially discrete object such as a sequence of integers) in a vector space. Under this decomposition, we can also compute

除了计算似然（这是平凡的）之外，用暴力方法计算边缘概率、众数和期望需要 $O(\prod_{k=1}^{K}|\mathcal{S}_{k}|)$ 时间。特别地，若 $|\mathcal{S}_{k}|=M \ \forall k\in[K]$，暴力计算需要 $O(M^{K})$ 时间。Apart from computing the likelihood, which is trivial, computing the marginal, mode and expectation by brute force takes $O(\prod_{k=1}^{K}|\mathcal{S}_{k}|)$ time. In particular, if $|\mathcal{S}_{k}|=M \ \forall k\in[K]$, brute force takes $O(M^{K})$ time.

当随机变量按顺序组织为 $S_{1},\dots,S_{K}$ 时，条件独立的一个简单例子是：每个变量 $S_{k}\in\mathcal{S}_{k}$ 只依赖于前一个变量 $S_{k-1}\in\mathcal{S}_{k-1}$，即When random variables are organized sequentially as $S_{1},\dots,S_{K}$, a simple example of conditional independence is when each variable $S_{k}\in\mathcal{S}_{k}$ only depends on the previous variable $S_{k-1}\in\mathcal{S}_{k-1}$, that is,

满足上述条件的概率分布称为满足马尔可夫性质，并称为马尔可夫链。计算链由函数 $f_{k}$ 指定，这些函数以 ${\bm{s}}_{k-1}$ 为输入，输出 ${\bm{s}}_{k}$。与之类似，马尔可夫链由给定 $S_{k-1}$ 时 $S_{k}$ 的条件概率分布 $p_{k}$ 指定。于是便可定义如下生成过程A probability distribution satisfying the above is said to satisfy the Markov property, and is called a Markov chain. A computation chain is specified by the functions $f_{k}$, that take ${\bm{s}}_{k-1}$ as input and output ${\bm{s}}_{k}$. In analogy, a Markov chain is specified by the conditional probability distributions $p_{k}$ of $S_{k}$ given $S_{k-1}$. We can then define the generative process

严格说来，我们应当写作 $S_{k}\mid S_{k-1}\sim p_{k}(\cdot\mid S_{k-1})$。之所以采用这一记号，既是为了简洁，也是为了与计算链相类比。此外，为简化记号，我们不失一般性地假设 $S_{0}$ 是确定性的（若非如此，我们总可以把 $S_{0}$ 移入 $S_{1}$，并添加一个哑变量作为 $S_{0}$）。也就是说，$\mathbb{P}(S_{0}={\bm{s}}_{0})=p_{0}({\bm{s}}_{0})\coloneqq 1$，且 $\mathcal{S}_{0}\coloneqq\{{\bm{s}}_{0}\}$。这相当于将 $S_{1}$ 的初始分布设为Strictly speaking, we should write $S_{k}\mid S_{k-1}\sim p_{k}(\cdot\mid S_{k-1})$. We choose our notation both for conciseness and for analogy with computation chains. Furthermore, to simplify the notation, we assume without loss of generality that $S_{0}$ is deterministic (if this is not the case, we can always move $S_{0}$ to $S_{1}$ and add a dummy variable as $S_{0}$). That is, $\mathbb{P}(S_{0}={\bm{s}}_{0})=p_{0}({\bm{s}}_{0})\coloneqq 1$ and $\mathcal{S}_{0}\coloneqq\{{\bm{s}}_{0}\}$. This amounts to setting the initial distribution of $S_{1}$ as

于是，马尔可夫链的联合概率可按如下方式计算We can then compute the joint probability of the Markov chain by

其中对 ${\bm{s}}_{0}$ 的依赖被隐含，因为 $p_{0}({\bm{s}}_{0})=1$。具有 $\mathcal{S}_{k}=\{1,2,3\}$ 的马尔可夫链如图 10.1 所示。链定义了一个全序集 $\{1,\dots,K\}$，因为图中的任意两个节点都必定由某条路径相连。where we left the dependence on ${\bm{s}}_{0}$ implicit, since $p_{0}({\bm{s}}_{0})=1$. A Markov chain with $\mathcal{S}_{k}=\{1,2,3\}$ is illustrated in Fig. 10.1. A chain defines a totally ordered set $\{1,\dots,K\}$, since two nodes in the graph are necessarily linked to each other by a path.

时间齐次离散时间马尔可夫链对应于如下情形：无论 $k$ 取何值，给定 $S_{k-1}$ 时 $S_{k}$ 的分布都相同：A time-homogeneous discrete-time Markov chain corresponds to the case when the distribution of $S_{k}$ given $S_{k-1}$ is the same regardless of $k$:

有限空间情形是指每个 $S_{k}\in\mathcal{S}$ 只能取有限集合 $\mathcal{S}=\{{\bm{v}}_{1},\dots,{\bm{v}}_{M}\}$ 中的值，并且The finite-space case corresponds to when each $S_{k}\in\mathcal{S}$ can take a finite set of values $\mathcal{S}=\{{\bm{v}}_{1},\dots,{\bm{v}}_{M}\}$ and

其中 $\pi_{i,j}\in[0,1]$ 是从 ${\bm{v}}_{i}$ 到 ${\bm{v}}_{j}$ 的转移概率。由于集合 $\mathcal{S}=\{{\bm{v}}_{1},\dots,{\bm{v}}_{M}\}$ 是离散的，我们总可以把它与 $\{1,\dots,M\}$ 等同起来。也就是说，我们可以改写成where $\pi_{i,j}\in[0,1]$ is the transition probability from ${\bm{v}}_{i}$ to ${\bm{v}}_{j}$. Because the set $\mathcal{S}=\{{\bm{v}}_{1},\dots,{\bm{v}}_{M}\}$ is discrete, we can always identify it with $\{1,\dots,M\}$. That is, we can instead write

更一般地，$n^{\text{th}}$ 阶马尔可夫链可能不仅依赖于最后一个变量，还依赖于最后 $n$ 个变量，More generally, a $n^{\text{th}}$-order Markov chain may depend, not only on the last variable, but on the last $n$ variables,

诸如 Transformer（4.8 节）等自回归模型，可以看作是在指定一个高阶马尔可夫链，其上下文窗口大小为 $n$。上下文越大，用动态规划进行精确推断在计算上就越不可行。正因如此，实践者才改用束搜索或祖先采样（10.5.3 节）。Autoregressive models such as Transformers (Section 4.8) can be seen as specifying a higher-order Markov chain, with a context window of size $n$. The larger context makes exact inference using dynamic programming computationally intractable. This is why practitioners use beam search or ancestral sampling (Section 10.5.3) instead.

马尔可夫链以及更一般的高阶马尔可夫链，都是贝叶斯网络的特例。与 8.3 节所回顾的计算图类似，变量之间的依赖关系可以用有向无环图（DAG）$\mathcal{G}=(\mathcal{V},\mathcal{E})$ 来表示：顶点 $\mathcal{V}=\{1,\dots,K\}$ 表示变量，边 $\mathcal{E}$ 表示变量间的依赖关系。集合 $\{i_{1},\dots,i_{n_{k}}\}={\operatorname{pa}}(k)\subseteq\mathcal{V}$（其中 $n_{k}\coloneqq|{\operatorname{pa}}(k)|$）指明了 $S_{k}$ 所依赖的变量 $S_{i_{1}},\dots,S_{i_{n_{k}}}$。由此定义出一个偏序集（poset）。为记号简便起见，我们再次不失一般性地假设 $S_{0}$ 是确定性的。计算图由按拓扑序排列的函数 $f_{1},\dots,f_{K}$ 指定。与之类似，贝叶斯网络则由给定 $S_{{\operatorname{pa}}(k)}$ 时 $S_{k}$ 的条件概率分布 $p_{k}$ 指定。于是我们可以定义如下的生成过程Markov chains and more generally higher-order Markov chains are a special case of Bayesian network. Similarly to computation graphs reviewed in Section 8.3, variable dependencies can be expressed using a directed acyclic graph (DAG) $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where the vertices $\mathcal{V}=\{1,\dots,K\}$ represent variables and edges $\mathcal{E}$ represent variable dependencies. The set $\{i_{1},\dots,i_{n_{k}}\}={\operatorname{pa}}(k)\subseteq\mathcal{V}$, where $n_{k}\coloneqq|{\operatorname{pa}}(k)|$, indicates the variables $S_{i_{1}},\dots,S_{i_{n_{k}}}$ that $S_{k}$ depends on. This defines a partially ordered set (poset). For notational simplicity, we again assume without loss of generality that $S_{0}$ is deterministic. A computation graph is specified by functions $f_{1},\dots,f_{K}$ in topological order. In analogy, a Bayesian network is specified by conditional probability distributions $p_{k}$ of $S_{k}$ given $S_{{\operatorname{pa}}(k)}$. We can then define the generative process

借助概率的链式法则以及由 DAG 所表达的变量独立性，联合概率分布即为（假设 $S_{0},S_{1},\dots,S_{K}$ 采用拓扑序）Using the chain rule of probability and variable independencies expressed by the DAG, the joint probability distribution is then (assuming a topological order for $S_{0},S_{1},\dots,S_{K}$)

这种表示方式非常适合刻画随机变量之间的因果关系。This representation is well suited to express causal relationships between random variables.

在贝叶斯框架中，观测数据、隐变量、参数和噪声变量统统被视为随机变量。若与节点 $k$ 相关联的条件分布 $p_{k}$ 依赖于某些参数，则可以把这些参数经由父节点作为条件提供给 $p_{k}$。In a Bayesian framework, observed data, latent variables, parameters and noise variables are all treated as random variables. If the conditional distribution $p_{k}$ associated to node $k$ depends on some parameters, they can be provided to $p_{k}$ as conditioning, using parent nodes.

贝叶斯网络由条件分布 $p_{k}$ 指定。因此，与计算图不同，贝叶斯网络中并没有函数 $f_{k}$ 这一概念。不过，贝叶斯网络的根节点可以是神经网络的输出。例如，RNN 或 Transformer 等自回归模型指定了在给定先前 token 的条件下下一个 token 的条件概率分布，再借助概率的链式法则得到整个序列上的概率分布。A Bayesian network is specified by the conditional distributions $p_{k}$. Therefore, unlike computation graphs, there is no notion of function $f_{k}$ in a Bayesian network. However, the root nodes of the Bayesian network can be the output of a neural network. For instance, autoregressive models, such as RNNs or Transformers, specify the conditional probability distribution of a token given past tokens, and the chain rule of probability is used to obtain a probability distribution over entire sequences.

贝叶斯网络的一大优势在于：只要每个条件分布 $p_{k}$ 都已归一化，$S=(S_{1},\dots,S_{K})$ 的联合分布便自动归一化。这意味着，我们只需遵循生成过程，就能轻而易举地从联合分布中抽取独立同分布的样本：按拓扑序 $k=1,\dots,K$ 依次进行，在第 $k$ 次迭代中，以先前的取值 ${\bm{s}}_{{\operatorname{pa}}(k)}$ 为条件抽取取值 ${\bm{s}}_{k}\sim p_{k}(\cdot|{\bm{s}}_{{\operatorname{pa}}(k)})$。这一过程称为祖先采样。A major advantage of Bayesian networks is that, provided that each conditional distribution $p_{k}$ is normalized, the joint distribution of $S=(S_{1},\dots,S_{K})$ is automatically normalized. This means that we can very easily draw i.i.d. samples from the joint distribution, by following the generative process: we follow the topological order $k=1,\dots,K$ and on iteration $k$ we draw a value ${\bm{s}}_{k}\sim p_{k}(\cdot|{\bm{s}}_{{\operatorname{pa}}(k)})$ conditioned on the previous values ${\bm{s}}_{{\operatorname{pa}}(k)}$. This is known as ancestral sampling.

马尔可夫随机场（MRF），又称无向图模型，所指定的分布可分解为A Markov random field (MRF), a.k.a. undirected graphical model, specifies a distribution that factorizes as

其中 $C$ 是 $\mathcal{G}$ 的极大团集合，即 $\mathcal{V}$ 中完全连通的子集；$Z$ 是归一化常数，定义为where $C$ is the set of maximal cliques of $\mathcal{G}$, that is, subsets of $\mathcal{V}$ that are fully connected, $Z$ is a normalization constant defined by

而 $\psi_{\mathcal{C}}\colon\mathcal{S}_{\mathcal{C}}\to\mathbb{R}_{+}$ 是势函数（又称相容函数），满足 $\mathcal{S}_{\mathcal{C}}\coloneqq(\mathcal{S}_{j})_{j\in\mathcal{C}}$。根据 Hammersley-Clifford 定理，马尔可夫随机场亦可等价地用马尔可夫性质来定义；感兴趣的读者可参阅 [206]。就本章而言，上述定义已足以满足需要。and $\psi_{\mathcal{C}}\colon\mathcal{S}_{\mathcal{C}}\to\mathbb{R}_{+}$ is a potential function (a.k.a. compatibility function), with $\mathcal{S}_{\mathcal{C}}\coloneqq(\mathcal{S}_{j})_{j\in\mathcal{C}}$. According to the Hammersley-Clifford theorem, an MRF can be equivalently defined in terms of Markov properties; we refer the interested reader to [206]. For the sake of this chapter, the definition above is sufficient for our purposes.