概率图模型

概率图模型是之前一直搁置的内容，然而躲得过初一躲不过十五，看葫芦书时发现其中有整整一章关于概率图，方才意识到概率图模型的重要性，回过头来重新补上这部分内容。

概率图模型（Probabilistic Graphical Model,PGM），简称图模型，是指一种用图结构来描述多元随机变量之间条件独立关系的概率模型。给研究高维空间中的概率模型带来了很大的便捷性。

对于一个 $K$ 维随机向量 $X = [X_1,X_2,\dots,X_K]^T$ ，其联合概率为高维空间中的分布，一般难以直接建模。假设每个变量为离散变量并有 $m$ 个取值，在不作任何独立假设条件下，则需要 $m^K-1$ 个参数才能表示其概率分布（因为我们需要给出每一组可能的 $[x_1,x_2,\dots,x_K]^T$ 的概率，共 $m^K$ 种可能，由于概率和为1因此在此基础上减1）。不难看出，参数数量是指数级的，这在实际应用中是不可接受的。

一种有效减少参数量的方法是独立性假设。将 $K$ 维随机向量的联合概率分解为 $K$ 个条件概率的乘积：

$\begin{aligned} p(\mathbf{x}) & \triangleq P(\mathbf{X}=\mathbf{x}) \\ &=p\left(x_{1}\right) p\left(x_{2} | x_{1}\right) \cdots p\left(x_{K} | x_{1}, \cdots, x_{K-1}\right) \\ &=\prod_{k=1}^{K} p\left(x_{k} | x_{1}, \cdots, x_{k-1}\right) \\ \end{aligned}$

其中 $x_k$ 表示变量 $X_k$ 的取值。如果某些变量之间存在条件独立，其参数量就可以大幅减少。

假设有四个二值变量 $X_1,X_2,X_3,X_4$ ，在不知道这几个变量依赖关系的情况下以用一个联合概率表来记录每一种取值的概率需要 $2^4−1=15$ 个参数。假设在已知 $X_1$ 时 $X_2$ 和 $X_3$ 独立，即有：

$p(x_2|x_1,x_3)=\frac{p(x_2,x_3|x_1)}{p(x_3|x_1)}=\frac{p(x_2|x_1)p(x_3|x_1)}{p(x_3|x_1)}=p(x_2|x_1)$

同理：

$p(x_3|x_1,x_2)=p(x_3|x_1)$

在已知 $X_2$ 和 $X_3$ 时 $X_1$ 也和 $X_4$ 独立，即有：

$p(x_4|x_1,x_2,x_3)=p(x_4|x_2,x_3)$

那么其联合概率 $p(x)$ 可以分解为：

$\begin{aligned} p(x)&=p(x_1)p(x_2|x_1)p(x_3|x_1,x_2)p(x_4|x_1,x_2,x_3)\\ &=p(x_1)p(x_2|x_1)p(x_3|x_1)p(x_4|x_2,x_3)\\ \end{aligned}$

是 $4$ 个局部条件概率的乘积。如果分别用 $4$ 个表格来记录这 $4$ 个条件概率的话，只需要 $1 + 2 + 2 + 4 = 9$ 个独立参数。

当概率模型中的变量数量比较多时，其条件依赖关系也比较复杂。我们可以使用图结构的方式将概率模型可视化，以一种直观、简单的方式描述随机变量之间的条件独立性的性质，并可以将一个复杂的联合概率模型分解为一些简单条件概率模型的组合。下图给出了上述例子中 $4$ 个变量之间的条件独立性的图形化描述。

图模型有三个基本问题：

表示问题：对于一个概率模型，如何通过图结构来描述变量之间的依赖关系。
推断问题：在已知部分变量时算其它变量的后验概率分布。
学习问题：图模型的学习包括图结构的学习和参数的学习。

很多机器学习模型都可以归结为概率模型，即建模输入和输出之间的条件概率分布。因此，图模型提供了一种新的角度来解释机器学习模型，并且这种角度有很多优点，比如了解不同机器学习模型之间的联系，方便设计新模型等。

1、模型表示

图由一组节点和节点之间的边组成。在概率图模型中，每个节点都表示一个随机变或一组随机变量，边表示这些随机变量之间的概率依赖关系。

常见的概率图模型可以分为两类向图模型和无向图模型。有向图模型的图结构为有向非循环图，如果两个节点之间有连边，表示对于的两个变量为因果关系。无向图模型使用无向图来描述变量之间的关系。每条边代表两个变量之间有概率依赖关系，但是并不一定是因果关系。

1.1、有向图模型

有向图模型，也称贝叶斯网络（Bayesian Network）或信念网络（Belief Network），是指用有向图来表示概率分布的图模型。

贝叶斯网络：对于一个随机向量 $X = [X_1,X_2,\dots,X_K]^T$ 和一个有 $K$ 个节点的有向非循环图 $G$ ， $G$ 中的每个节点都对应一个随机变量，可以是可观测的变量，隐变量或是未知参数。 $G$ 中的每个连接 $e_{ij}$ 表示两个随机变量 $X_{i}$ 和 $X_{j}$ 之间具有非独立的因果关系。 $X_{\pi_k}$ 表示变量 $X_k$ 的所有父节点变量集合，每个随机变量的局部条件概率分布（local conditional probability distribution）为 $P(X_k|X_{\pi_k})$ 。

若 $X$ 的联合概率分布可以分解为每个随机变量 $X_k$ 的局部条件概率的连乘形式，即：

$p(x)=\prod_{i=1}^K p(x_k|x_{\pi_k})$

那么 $(G, X)$ 构成了一个贝叶斯网络。

条件独立性：在贝叶斯网络中，如果两个节点是直接连接的，它们肯定是非条件独立的直接因果关系。父节点是“因”，子节点是“果”。

如果两个节点不是直接连接的，但是它们之间有一条经过其它节点的路径来连接，那么这两个节点之间的条件独立性就比较复杂，例如：

(a)(b)(c)(d)分别代表间接因果关系、间接果因关系、共因关系、共果关系。

局部马尔可夫性质：对一个更一般的贝叶斯网络，其局部马尔可夫性质为：每个随机变量在给定父节点的情况下，条件独立于它的非后代节点。

$X_{k} \perp Z | X_{\pi_{k}}$

其中 $Z$ 为 $X_k$ 的非后代变量。

1.2、常见的有向图模型

1.2.1、Sigmoid信念网络

一种简单的参数化模型为Sigmoid信念网络。Sigmoid信念网络种变量取值为 $\{0,1 \}$ ，对于变量 $X_k$ 和它的父节点集合 $\pi_k$ ，条件概率分布表示为：

$P(X_k=1|\pi_k;\theta)=\sigma(\theta_0+\sum_{x_i\in X_{\pi_k}} \theta_i x_i)$

其中 $σ(·)$ 是Logistic sigmoid函数， $\theta_i$ 是可学习的参数。假设变量 $X_k$ 的父节点数量为 $M$ ，如果使用表格来记录条件概率需要 $2^M$ 个参数，如果使用参数化模型只需要 $M + 1$ 个参数。如果对不同的变量的条件概率都共享使用一个参数化模型，其参数数量又可以大幅减少。

值得一提的是Sigmoid信念网络与Logistic回归模型都采用Logistic函数来计算条件概率。如果假设Sigmoid信念网络中只有一个叶子节点，其所有的父节点之间没有连接，且取值为实数，那么sigmoid信念网络的网络结构和Logistic回归模型类似，如图所示。

这两个模型区别在于Logistic回归模型中的 $x$ 作为一种确定性的参数，而非变量。因此Logistic回归模型只建模条件概率 $p(y|x)$ ，是一种判别模型，而Sigmoid信念网络建模 $p(x, y)$ ，是一种生成模型。

1.2.2、朴素贝叶斯分类器

朴素贝叶斯分类器是一类简单的概率分类器，在强（朴素）独立性假设的条件下运用贝叶斯公式来计算每个类别的后验概率。

给定一个有 $d$ 维特征的样本 $x$ 和类别 $y$ ，类别的后验概率为：

$p(y | \mathbf{x} ; \theta)=\frac{p\left(x_{1}, \cdots, x_{d} | y\right) p(y)}{p\left(x_{1}, \cdots, x_{d}\right)}∝ p\left(x_{1}, \cdots, x_{d} | y;\theta\right) p(y;\theta)$

其中 $\theta$ 是概率分布的参数。

朴素贝叶斯分类器中，假设在给定 $Y$ 的情况下 $X_i$ 之间条件独立，即 $X_i \perp X_j|Y$ 。下图给出了朴素贝叶斯分类器的图形表示。

条件概率分布 $p(y|x)$ 可以分解为：

$p(y|x;\theta)∝p(y|\theta_c)\prod_{i=1}^d p(x_i|y;\theta_{i,y})$

其中 $θ_c$ 是 $y$ 的先验概率分布的参数， $\theta_{i,y}$ 是条件概率分布 $p(x_i|y;θ_{i,y})$ 的参数。若 $x_i$ 为连续值， $p(x_i|y;θ_{i,y})$ 可以用高斯分布建模。若 $x_i$ 为离散值， $p(x_i|y;θ_{i,y})$ 可以用多项分布建模。

虽然朴素贝叶斯分类器的条件独立性假设太强，但是在实际应用中，朴素贝叶斯分类器在很多任务上也能得到很好的结果，并且模型简单，可以有效防止过拟合。

1.2.3、隐马尔科夫模型

隐马尔科夫模型是一种含有隐变量的马尔可夫过程。下图给出隐马尔可夫模型的图模型表示。

隐马尔可夫模型的联合概率可以分解为：

$p(x,y;\theta)=\prod_{i=1}^T p(y_t|y_{t-1},\theta_s)p(x_t|y_t,\theta_t)$

其中 $p(x_t|y_t,\theta_t)$ 为输出概率， $p(y_t|y_{t-1},\theta_s)$ 为转移概率， $\theta_s,\theta_t$ 分别表示两类条件概率的参数。

1.3、无向图模型

无向图模型，也称为马尔可夫随机场或马尔科夫网络，是一类用无向图来描述一组具有局部马尔可夫性质的随机向量 $X$ 的联合概率分布的模型。

马尔可夫随机场：对于一个随机向量 $X = [X_1,X_2,\dots,X_K]^T$ 和一个有 $K$ 个节点的无向图 $G(V,\epsilon)$ （可有循环）， $G$ 中节点 $k$ 表示随机变量 $X_k$ ， $1\leq k \leq K$ 。如果 $(G,X)$ 满足局部马尔可夫性质，即一个变量 $X_k$ 在给定它的邻居的情况下独立于所有其它变量：

$p\left(x_{k} | \mathbf{x}_{\backslash k}\right)=p\left(x_{k} | \mathbf{x}_{N(k)}\right)$

其中 $N(k)$ 为变量 $X_k$ 的邻居集合， $\backslash k$ 为除 $X_k$ 外其它变量的集合，那么 $(G, X)$ 就构成了一个马尔可夫随机场。

无向图的马尔可夫性：无向图中的马尔可夫性可以表示为：

$X_{k} \perp \mathbf{X}_{\backslash N(k), \backslash k} | \mathbf{X}_{N(k)}$

其中 $\mathbf{X}_{\backslash N(k), \backslash k}$ 表示除 $X_{N(k)}$ 和 $X_k$ 外的其它变量。

上图中由马尔可夫性质可以得到： $X_1\perp X_4|X_2,X_3$ 和 $X_2\perp X_3|X_1,X_4$ 。

1.4、无向图模型的概率分解

团：由于无向图模型并不提供一个变量的拓扑顺序，因此无法用链式法则对 $p(x)$ 进行逐一分解。无向图模型的联合概率一般以全连通子图为单位进行分解。无向图中的一个全连通子图，称为团（Clique），即团内的所有节点之间都连边。在所有团中，如果一个团不能被其它的团包含，这个团就是一个最大团（Maximal Clique）。

因子分解：无向图中的的联合概率可以分解为一系列定义在最大团上的非负函数的乘积形式。

Hammersley Clifford定理：如果一个分布 $p(x) > 0$ 满足无向图 $G$ 中的局部马尔可夫性质，当且仅当 $p(x)$ 可以表示为一系列定义在最大团上的非负函数的乘积，即：

$p(x)=\frac{1}{Z} \prod_{c\in C}\phi_c(x_c)$

上式也称为吉布斯分布。其中 $C$ 为 $G$ 中的最大团集合， $\phi_c(x_c)$ 是定义在团 $c$ 上的势能函数， $Z$ 是配分函数（Partition Function），用来将乘积归一化为概率形式。

$Z=\sum_{\mathbf{x} \in \mathcal{X}} \prod_{c \in \mathcal{C}} \phi_{c}\left(\mathbf{x}_{c}\right)$

其中 $\mathcal{X}$ 为随机向量 $X$ 的取值空间。

无向图模型与有向图模型的一个重要区别是有配分函数 $Z$ 。配分函数的计算复杂度是指数级的，因此在推断和参数学习时都需要重点考虑。

由于势能函数必须为正的，因此我们一般定义为：

$\phi_c(\mathbf{x_c})=\exp(-E_c(\mathbf{x_c}))$

其中 $E_c(\mathbf{x_c})$ 为能量函数。这里的负号是遵从物理上的习惯，即能量越低意味着概率越高。

因此无向图上定义的概率分布可以表示为：

$\begin{aligned} P(\mathbf{x}) &=\frac{1}{Z} \prod_{c \in \mathcal{C}} \exp \left(-E_{c}\left(\mathbf{x}_{c}\right)\right) \\ &=\frac{1}{Z} \exp \left(\sum_{c \in \mathcal{C}}-E_{c}\left(\mathbf{x}_{c}\right)\right) \\ \end{aligned}$

这种形式的分布又称为玻尔兹曼分布（Boltzmann Distribution）。任何一个无向图模型都可以用上式来表示其联合概率。

1.5、常见的无向图模型

1.5.1、对数线性模型

势能函数一般定义为：

$\phi_{c}\left(\mathbf{x}_{c} | \theta_{c}\right)=\exp \left(\theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}\right)\right)$

其中函数 $f_{c}\left(\mathbf{x}_{c}\right)$ 为定义在 $\mathbf{x}_c$ 上的特征向量， $\theta_c$ 为权重向量。这样联合概率 $p(x)$ 的对数形式为：

$\log p(\mathbf{x} ; \theta)=\sum_{c \in C} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}\right)-\log Z(\theta)$

其中 $θ$ 代表所有势能函数中的参数 $θ_c$ 。这种形式的无向图模型也称为对数线性模型或最大熵模型。

如果用对数线性模型来建模条件概率 $p(y|x)$ ，有：

$p(y | \mathbf{x} ; \theta)=\frac{1}{Z(\mathbf{x} ; \theta)} \exp \left(\theta^{\mathrm{T}} f(\mathbf{x}, y)\right)$

其中 $Z(\mathbf{x};\theta)=\sum_y \exp (\theta^{\mathrm{T}} f(\mathbf{x}, y))$ 。这种对数线性模型也称为条件最大熵模型或softmax回归模型。

1.5.2、条件随机场

条件随机场是一种直接建模条件概率的无向图模型。

和条件最大熵模型不同，条件随机场建模的条件概率 $p(y|x)$ 中， $y$ 一般为随机向量，因此需要对 $p(y|x)$ 进行因子分解。设条件随机场的最大团集合为 $C$ ，条件概率为：

$p(\mathbf{y} | \mathbf{x} ; \theta)=\frac{1}{Z(\mathbf{x} ; \theta)} \exp \left(\sum_{c \in \mathcal{C}} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}, \mathbf{y}_{c}\right)\right)$

其中 $Z(\mathbf{x};\theta)=\sum_y \exp(\sum_{c \in \mathcal{C}} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}, \mathbf{y}_{c}\right))$ 为归一化项。

一个最常用的条件随机场为图(b)中所示的链式结构，其条件概率为：

$p(\mathbf{y} | \mathbf{x} ; \theta)=\frac{ 1}{Z(\mathbf{x} ; \theta)} \exp \left(\sum_{t=1}^{T} \theta_{1}^{\mathrm{T}} f_{1}\left(\mathbf{x}, y_{t}\right)+\sum_{t=1}^{T-1} \theta_{2}^{\mathrm{T}} f_{2}\left(\mathbf{x}, y_{t}, y_{t+1}\right)\right)$

其中 $f1(\mathbf{x},y_t)$ 为状态特征，一般和位置 $t$ 相关， $f_2(\mathbf{x}, y_t,y_{t+1})$ 为转移特征，一般可以简化为 $f_2(y_t,y_{t+1})$ 并使用状态转移矩阵来表示。

1.6、有向图和无向图之间的转换

无向图模型可以表示有向图模型无法表示的一些依赖关系，比如循环依赖；但它不能表示有向图模型能够表示的某些关系，比如因果关系。

以图(a)中的有向图为例，其联合概率分布可以分解为：

$p(x) = p(x_1)p(x_2)p(x_3)p(x_4|x_1,x_2,x_3)$

其中 $p(x_4|x_1,x_2,x_3)$ 和四个变量都相关。如果要转换为无向图，需要将这四个变量都归属于一个团中。因此需要将 $x_4$ 的三个父节点之间都加上连边，如图(b)所示。这个过程称为道德化（Moralization）。转换后的无向图称为道德图（Moral Graph）。

在道德化的过程中来有向图的一些独立性会丢失，比如上面 $X_1\perp X_2\perp X_3|\varnothing$ 在道德图中不再成立。

2、推断

在图模型中，推断（Inference）是指在观测到部分变量 $\mathbf{e}=\{e_1,e_2,\dots,e_m \}$ 时，计算其它变量的某个子集 $\mathbf{q}=\{q_1,q_2,\dots,q_n \}$ 的后验概率 $p(\mathbf{q}|\mathbf{e})$ 。

假设一个图模型中，除了变量 $\mathbf{e},\mathbf{q}$ 外，其余变量表示为 $\mathbf{z}$ 。根据贝叶斯公式有：

$\begin{aligned} p(\mathbf{q} | \mathbf{e}) & = \frac{ p(\mathbf{q}, \mathbf{e})}{p(\mathbf{e})} \\ &=\frac{\sum_{\mathbf{z}} p(\mathbf{q}, \mathbf{e}, \mathbf{z})}{\sum_{\mathbf{q}, \mathbf{z}} p(\mathbf{q}, \mathbf{e}, \mathbf{z})} \\ \end{aligned}$

因此，图模型的推断问题可以转换为求任意一个变量子集的边际概率分布问题。

在图模型中用的推断方法可以分为精确推断和近似推断两类。

2.1、变量消除法

以上图为例，假设推断问题为计算后验概率 $p(x_1|x_4)$ ，需要计算两个边际概率 $p(x_1,x_4)$ 和 $p(x_4)$ 。

根据条件独立性假设，有：

$p(x_1,x_4)=\sum_{x_2,x_3}p(x_1)p(x_2|x_1)p(x_3|x_1)p(x_4|x_2,x_3)$

假设每个变量取 $K$ 个值，计算上面的边际分布需要 $K^2$ 次加法以及 $3K^2$ 次乘法。

根据乘法的分配律，边际概率 $p(x_1,x_4)$ 可以写为：

$p(x_1,x_4)=\sum_{x_3}p(x_3|x_1)\sum_{x_2}p(x_2|x_1)p(x_4|x_2,x_3)$

这样计算量可以减少到 $K^2+K$ 次加法和 $K^2+K+1$ 次乘法。

这种方法是利用动态规划的思想，每次消除一个变量，来减少计算边际分布的计算复杂度，称为变量消除法。

2.2、信念传播算法

信念传播（Belief Propagation,BP）算法，也称为和积（Sum-Product）算法或消息传递（Message Passing）算法，是将变量消除法中的和积（Sum-Product）操作看作是消息，并保存起来，这样可以节省大量的计算资源。

2.2.1、链式结构上的的信念传播算法

以上图所示的无向马尔可夫链为例，其联合概率 $p(x)$ 为：

$\begin{aligned} p(\mathbf{x}) &=\frac{1}{Z} \prod_{c \in \mathcal{C}} \phi_{c}\left(\mathbf{x}_{c}\right) \\ &=\frac{1}{Z} \prod_{t=1}^{T-1} \phi\left(x_{t}, x_{t+1}\right) \end{aligned}$

其中 $ϕ(x_t,x_{t+1})$ 是定义在团 $(x_t,x_{t+1})$ 的势能函数。

第 $t$ 个变量的边际概率 $p(x_t)$ 为：

$\begin{aligned} p\left(x_{t}\right) &=\sum_{x_{1}} \cdots \sum_{x_{t-1}} \sum_{x_{t+1}} \cdots \sum_{x_{T}} p(\mathbf{x}) \\ &=\frac{1}{Z} \sum_{x_{1}} \cdots \sum_{x_{t-1}} \sum_{x_{t+1}} \cdots \sum_{x_{T}} \prod_{t=1}^{T-1} \phi\left(x_{t}, x_{t+1}\right) \end{aligned}$

假设每个变量取 $K$ 个值，不考虑归一化项，计算上述边际分布需要 $K^{T−1}$ 次加法以及 $(T−1)K^{T−1}$ 次乘法。

根据乘法的分配律际概率 $p(x_t)$ 可以通过下面方式进行计算：

$\begin{aligned} p\left(x_{t}\right) &=\frac{1}{Z}\left(\sum_{x_{1}} \cdots \sum_{x_{t-1}} \prod_{j=1}^{t-1} \phi\left(x_{j}, x_{j+1}\right)\right) \cdot\left(\sum_{x_{t+1}} \cdots \sum_{x_{T}} \prod_{j=t}^{T-1} \phi\left(x_{j}, x_{j+1}\right)\right) \\ &=\frac{1}{Z}\left(\sum_{x_{t-1}} \phi\left(x_{t-1}, x_{t}\right) \cdots\left(\sum_{x_{2}} \phi\left(x_{2}, x_{3}\right)\left(\sum_{x_{1}} \phi\left(x_{1}, x_{2}\right)\right)\right)\right) \\ &\left(\sum_{x_{t+1}} \phi\left(x_{t}, x_{t+1}\right) \cdots\left(\sum_{x_{T-1}} \phi\left(x_{T-2}, x_{T-1}\right)\left(\sum_{x_{T}} \phi\left(x_{T-1}, x_{T}\right)\right)\right)\right) \\ &=\frac{1}{Z} \mu_{t-1, t}\left(x_{t}\right) \mu_{t+1, t}\left(x_{t}\right) \end{aligned}$

其中 $\mu_{t-1, t}(x_t)$ 定义为变量 $X_{t-1}$ 向变量 $X_t$ 传递的消息， $\mu_{t-1, t}(x_t)$ 是关于变量 $X_t$ 的函数，可以递归计算：

$\mu_{t-1, t}\left(x_{t}\right) \triangleq \sum_{x_{t-1}} \phi\left(x_{t-1}, x_{t}\right) \mu_{t-2, t-1}\left(x_{t-1}\right)$

$\mu_{t+1, t}(x_t)$ 为变量 $X_{t+1}$ 向变量 $X_t$ 传递的消息，定义为：

$\mu_{t+1, t}\left(x_{t}\right) \triangleq \sum_{x_{t+1}} \phi\left(x_{t}, x_{t+1}\right) \mu_{t+2, t+1}\left(x_{t+1}\right)$

边际概率 $p(x_t)$ 的计算复杂度减少为 $O(TK^2)$ 。如果要计算整个序列上所有变量的边际概率，不需要将消息传递的过程重复 $T$ 次，因为其中每两个相邻节点上的消息是相同的。

2.2.2、树结构上的信念传播算法

信念传播算法也可以推广到具有树结构的图模型上。如果一个有向图满足任意两个变量只有一条路径（忽略方向），且只有一个没有父节点的节点，那么这个有向图为树结构，其中唯一没有父节点的节点称为根节点。如果一个无向图满足任意两个变量只有一条路径，那么这个无向图也为树结构。在树结构的无向图中任意一个节点都可以作为根节点。

树结构图模型的信念传播过程为）从叶子节点到根节点依次计算并传递消息）从根节点开始到叶子节点，依次计算并传递消息）在每个节点上计算所有接收消息的乘积（如果是无向图还需要归一化），就得到了所有变量的边际概率。

3、近似推断

在实际应用中，精确推断一般用于结构比较简单的推断问题。当图模型的结构比较复杂时，精确推断的计算开销会比较大。此外，如果图模型中的变量是连续的，并且其积分函数没有闭式解时，也无法使用精确推断。因此，在很多情况下也常常采用近似的方法来进行推断。

采样法是通过模拟的方式来采集符合某个分布 $p(x)$ 的一些样本，并通过这些样本来估计和这个分布有关的运算，比如期望等。

下面介绍基于采样法的近似推断。

3.1、蒙特卡罗方法

蒙特卡罗方法的一个最简单的应用例子是计算圆周率 $π$ 。蒙特卡罗方法的基本思想可以归结为根据一个已知概率密度函数为 $p(x)$ 的分布来计算函数 $f (x)$ 的期望：

$\mathbb{E}[f(x)]=\int_{x} f(x) p(x) d x$

当 $p(x)$ 比较复杂时，很难用解析方法来计算这个期望。为计算 $E[f(x)]$ ，我们可通过数值方法来近似计算。首先从 $p(x)$ 中独立抽取 $N$ 个样本 $x^{(1)},x^{(2)},\dots,x^{(N)}$ ， $f(x)$ 的期望可以用这 $N$ 个样本的均值 $\hat{f}_N$ 来近似：

$\hat{f}_N=\frac{1}{N}(f(x^{(1)})+f(x^{(2)})+\dots+f(x^{(N)}))$

根据大数定律， $N$ 趋向于无穷大时，样本均值收敛于期望值：

$\hat{f}_{N} \stackrel{P}{\longrightarrow} \mathbb{E}_{p}[f(x)] \quad when \quad N\longrightarrow \infty$

这就是蒙特卡罗方法的理论依据。

蒙特卡罗方法的难点是如何进行随机采样，即如何让计算机生成满足概率密度函数 $p(x)$ 的样本。我们知道，计算机可以比较容易地随机生成一个在 $[0, 1]$ 区间上均布分布的样本 $ξ$ 。如果要随机生成服从某个非均匀分布的样本，就需要一些间接的采样方法。

如果一个分布的概率密度函数为 $p(x)$ ，其累积分布函数 $cdf(x)$ 为连续的严格增函数，且存在逆函数 $cdf^{−1}(y),y ∈ [0, 1]$ ，那么我们可以利用累积分布函数的逆函数来生成服从该随机分布的样本。假设 $ξ$ 是 $[0, 1]$ 区间上均匀分布的随机变量 $cdf^{−1}(ξ)$ 服从概率密度函数为 $p(x)$ 的分布。

但当 $p(x)$ 非常复杂，累积分布函数的逆函数难以计算，就难以直接对 p(x) 进行采样，往往需要使用一些间接的采样策略，比如拒绝采样、重要性采样、马尔可夫链蒙特卡罗采样等。这些方法一般是先根据一个比较容易采样的分布进行采样，然后通过一些策略来间接得到符合 $p(x)$ 分布的样本。

3.2、拒绝采样

拒绝采样，也叫接受-拒绝采样。假设原始分布 $p(x)$ 难以直接采样，我们可以引入一个容易采样的分布 $q(x)$ ，一般称为提议分布(Proposal Distribution），然后以某个标准来拒绝一部分的样本使得最终采集的样本服从分布 $p(x)$ 。

在拒绝采样中，已知未归一化的分布 $\hat{p}(x)$ ，我们需要构建一个提议分布 $q(x)$ 和一个常数 $k$ ，使得 $kq(x)$ 可以覆盖函数 $\hat{p}(x)$ ，即 $kq(x) ≥ \hat{p}(x),∀x$ 。如图所示。

对于每次抽取的样本 $\hat{x}$ ，计算接受概率（acceptance probability）：

$\alpha(\hat{x})=\frac{\hat{p}(\hat{x})}{kq(\hat{x})}$

并以概率 $\alpha(\hat{x})$ 来接收样本 $\hat{x}$ 。

拒绝采样的采样过程如下：

判断一个拒绝采样方法的好坏就是看其采样效率，即总体的接受率。如果函数 $kq(x)$ 远大于原始分布函数 $\hat{p}(x)$ ，拒绝率会比较高样，效率会非常不理想。要找到一个和 $\hat{p}(x)$ 比较接近的提议分布往往比较困难，特别是在高维空间中采样率会非常低，导致很难应用到实际问题中。

3.3、重要性采样

如果采样的目的是计算分布 $p(x)$ 下函数 $f(x)$ 的期望，那么实际上抽取的样本不需要严格服从分布 $p(x)$ 。也可以通过另一个分布，即提议分布 $q(x)$ ，直接采样并估计 $\mathbb{E}_p[f(x)]$ 。

函数 $f(x)$ 在分布$p(x)下的期望可以写为：

$\begin{aligned} \mathbb{E}_{p}[f(x)] &=\int_{x} f(x) p(x) d x \\ &=\int_{x} f(x) \frac{p(x)}{q(x)} q(x) d x \\ &=\int_{x} f(x) w(x) q(x) d x \\ &=\mathbb{E}_{q}[f(x) w(x)] \\ \end{aligned}$

其中 $w(x)$ 称为重要性权重。

重要性采样（Importance Sampling）是通过引入重要性权重分布将 $p(x)$ 下 $f(x)$ 的期望变为在分布 $q(x)$ 下 $f(x)w(x)$ 的期望，从而可以近似为：

$\hat{f}_{N}=\frac{1}{N}\left(f\left(x^{(1)}\right) w\left(x^{(1)}\right)+\cdots+f\left(x^{(N)}\right) w\left(x^{(N)}\right)\right)$

其中 $x^{(1)},x^{(2)},\dots,x^{(N)}$ 是从 $q(x)$ 中独立抽样出的样本点。

重要性采样也可以在只知道未归一化的分布 $\hat{p}(x)$ 的情况下计算函数 $f(x)$ 的期望：

$\begin{aligned} \mathbb{E}_{p}[f(x)] &= \int_{x} f(x) \frac{ \hat{p}(x)}{Z} d x \\ &=\frac{\int_{x} \hat{p}(x) f(x) d x}{\int_{x} \hat{p}(x) d x} \\ & \approx \frac{\sum_{n=1}^{N} f\left(x^{(n)}\right) \hat{w}\left(x^{(n)}\right)}{\sum_{n=1}^{N} \hat{w}\left(x^{(n)}\right)} \\ \end{aligned}$

其中 $\hat{w}(x)=\frac{\hat{p}(x)}{q(x)}$ ， $x^{(1)},x^{(2)},\dots,x^{(N)}$ 是从 $q(x)$ 中独立抽样出的样本点。

3.4、马尔可夫链蒙特卡罗方法

在高维空间中，拒绝采样和重要性采样的效率随空间维数的增加而指数降低。马尔可夫链蒙特卡罗方法（MCMC）是一种更好的采样方法以很容易地对高维变量进行采样。

MCMC方法也有很多不同的具体采样方法，但其核心思想是将采样过程看作是一个马尔可夫链：

$x_1,x_2,\dots,x_{t-1},x_t,x_{t+1},\dots$

第 $t + 1$ 次采样依赖于第 $t$ 次抽取的样本以及状态转移分布（即提议分布） $q(x|x_t)$ ，如果这个马尔可夫链的平稳分布为 $p(x)$ ，那么在状态平稳时抽取的样本就服从 $p(x)$ 的分布。

MCMC方法的关键是如何构造出平稳分布为 $p(x)$ 的马尔可夫链，并且该马尔可夫链的状态转移分布 $q(x|x^{'})$ 一般为比较容易采样的分布。

使用MCMC方法进行采样时需要注意两点：一是马尔可夫链需要经过一段时间的随机游走才能达到平稳状态，这段时间称为预烧期（Burn-in Period）。预烧期内的采样点并不服从分布 $p(x)$ ，需要丢弃；二是基于马尔可夫链抽取的相邻样本是高度相关的。而在机器学习中，我们一般需要抽取的样本是独立同分布的。为了使得抽取的样本之间独立，我们可以每间隔 $M$ 次随机游走，抽取一个样本。如果 $M$ 足够大则可以认为抽取的样本是独立的。

3.4.1、Metropolis-Hastings 算法

Metropolis-Hastings算法，简称MH算法，是一种应用广泛的MCMC方法。

假设马尔可夫链的状态转移分布（即提议分布 $q(x|x^{'})$ 为一个比较容易采样的分布，其平稳分布往往不是 $p(x)$ 。为此MH算法引入拒绝采样的思想来修正提议分布，使得最终采样的分布为 $p(x)$ 。

在MH算法中设第 $t$ 次采样样本为 $x_t$ ，首先根据提议分布 $q(x|x_t)$ 抽取一个样本 $\hat{x}$ ，并以概率 $A(\hat{x},x_t)$ 来接受 $\hat{x}$ 作为第 $t+1$ 次的采样样本 $x_{t+1}$ ：

$A(\hat{x},x_t)=\min(1,\frac{p(\hat{x})q(x_t|\hat{x})}{p(x_t)q(\hat{x}|x_t)})$

因为每次 $q(x|x_t)$ 随机生成一个样本 $\hat{x}$ ，并以 $A(\hat{x},x_t)$ 的概率接受，因此修正的马尔可夫链状态转移概率为：

$q^{'}(\hat{x}|x_t)=q(\hat{x}|x_t)A(\hat{x},x_t)$

该修正的马尔可夫链可以达到平稳状态，且平稳分布为 $p(x)$ 。

证明：根据马尔可夫链的细致平稳条件，有：

$\begin{aligned} p\left(\mathbf{x}_{t}\right) q^{\prime}\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right) &=p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right) A\left(\hat{\mathbf{x}}, \mathbf{x}_{t}\right) \\ &=p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right) \min \left(1, \frac{p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right)}{p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right)}\right) \\ &=\min \left(p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right), p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right)\right) \\ &=p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right) \min \left(\frac{p\left(\mathbf{x}_{t}\right) q\left(\hat{\mathbf{x}} | \mathbf{x}_{t}\right)}{p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right)}, 1\right) \\ &=p(\hat{\mathbf{x}}) q\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right) A\left(\mathbf{x}_{t}, \hat{\mathbf{x}}\right) \\ &=p(\hat{\mathbf{x}}) q^{\prime}\left(\mathbf{x}_{t} | \hat{\mathbf{x}}\right) \end{aligned}$

因此 $p(x)$ 是状态转移概率为 $q^{′}(\hat{x}|x_t)$ 的马尔可夫链的平稳分布。

3.4.2、Metropolis算法

如果MH算法中的提议分布是对称的，即 $q(\hat{x}|x_t) = q(x_t|\hat{x})$ ，第 $t + 1$ 次采样的接受率可以简化为：

$A(\hat{x},x_t)=\min(1,\frac{p(\hat{x})}{p(x_t)})$

这种MCMC方法称为Metropolis算法。

3.4.3、吉布斯采样

吉布斯采样是一种有效地对高维空间中的分布进行采样的MCMC方法，可以看作是Metropolis-Hastings算法的特例。

吉布斯采样使用全条件概率作为提议分布来依次对每个维度进行采样，并设置接受率为 $A = 1$ 。

对于一个 $M$ 维的随机向量 $X = [X_1,X_2,\dots,X_M]^T$ ，其第 $i$ 个变量 $X_i$ 的全条件概率为：

$\begin{aligned} p\left(x_{i} | \mathbf{x}_{i}\right) & \triangleq P\left(X_{i}=x_{i} | X_{\backslash i}=\mathbf{x}_{\backslash i}\right) \\ &=p\left(x_{i} | x_{1}, x_{2}, \cdots, x_{i-1}, x_{i+1}, \cdots, x_{M}\right) \end{aligned}$

其中 $\mathbf{x}_{\backslash i}=[x_{1}, x_{2}, \cdots, x_{i-1}, x_{i+1}, \cdots, x_{M}]^T$ 表示除 $X_i$ 外其他变量的取值。

吉布斯采样可以按照任意的顺序根据全条件分布依次对每个变量进行采样。假设从一个随机的初始化状态 $x^{(0)} = [x_1^{(0)} , x_2^{(0)} , · · · , x_M^{(0)}]^T$ 开始，按照下标顺序依次对 $M$ 个变量进行采样。

吉布斯采样的每单步采样也构成一个马尔可夫链。假设每个单步（采样维度为第 $i$ 维）的状态转移概率 $q(x|x^{′})$ 为：

$q\left(\mathbf{x} | \mathbf{x}^{\prime}\right)=\left\{\begin{array}{cc}{\frac{p(\mathbf{x})}{p\left(\mathbf{x}_{\backslash i}^{\prime}\right)}} & {\text { if } \mathbf{x}_{\backslash i}=\mathbf{x}_{\backslash i}^{\prime}} \\ {0} & {\text { otherwise }}\end{array}\right.$

其中边际分布 $p(\mathbf{x}_{\backslash i}^{'})=\sum_{x^{'}}p(x^{'})$ ，等式 $\mathbf{x}_{\backslash i}=\mathbf{x}_{\backslash i}^{\prime}$ 表示 $x_j = x_j^{'}, ∀j \neq i$ ，因此有 $p(\mathbf{x}_{\backslash i}^{'})=p(\mathbf{x}_{\backslash i})$ ，并可以得到：

$p\left(\mathbf{x}^{\prime}\right) q\left(\mathbf{x} | \mathbf{x}^{\prime}\right)=p\left(\mathbf{x}^{\prime}\right) \frac{p(\mathbf{x})}{p\left(\mathbf{x}_{\backslash i}^{\prime}\right)}=p(\mathbf{x}) \frac{p\left(\mathbf{x}^{\prime}\right)}{p\left(\mathbf{x}_{\backslash i}\right)}=p(\mathbf{x}) q\left(\mathbf{x}^{\prime} | \mathbf{x}\right)$

根据细致平稳条件状态转移概率 $q(x|x^{′})$ 的马尔可夫链的平稳分布为 $p(x)$ 。

4、学习

图模型的学习可以分为两部分：一是网络结构学习，即寻找最优的网络结构；二是网络参数估计，即已知网络结构，估计每个条件概率分布的参数。网络结构学习一般比较困难，一般是由领域专家来构建。这里只讨论在给定网络结构条件下的参数估计问题。

4.1、不含隐变量的参数估计

如果图模型中不包含隐变量，即所有变量都是可观测的，那么网络参数一般可以直接通过最大似然来进行估计。

有向图模型：在有向图模型中，所有变量 $x$ 的联合概率分布可以分解为每个随机变量 $x_k$ 的局部条件概率 $p(x_k|x_{π_k};θ_k)$ 的连乘形式，其中 $θ_k$ 为第 $k$ 个变量的局部条件概率的参数。

给定 $N$ 个训练样本 $D = \{x^{(n)}\}_{n=1}^N$ ，其对数似然函数为：

$\begin{aligned} \mathcal{L}(\mathcal{D} ; \theta) &=\frac{1}{N} \sum_{n=1}^{N} \log p\left(\mathbf{x}^{(n)} ; \theta\right) \\ &=\frac{1}{N} \sum_{n=1}^{N} \sum_{k=1}^{K} \log p\left(x_{k}^{(n)} | x_{\pi_{k}}^{(n)} ; \theta_{k}\right) \\ \end{aligned}$

其中 $θ_k$ 为模型中的所有参数。

因为所有变量都是可观测的，最大化对数似然 $L(D;θ))$ ，只需要分别地最大化每个变量的条件似然来估计其参数。

$\theta_{k}=\arg \max \sum_{n=1}^{N} \log p\left(x_{k}^{(n)} | x_{\pi_{k}}^{(n)} ; \theta_{k}\right)$

无向图模型：在无向图模型中，所有变量 $x$ 的联合概率分布可以分解为定义在最大团上的势能函数的连乘形式。以对数线性模型为例：

$p(\mathbf{x} ; \theta)=\frac{1}{Z(\theta)} \exp \left(\sum_{c \in \mathcal{C}} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}\right)\right)$

其中 $Z(\theta)=\sum_{\mathbf{x}} \exp \left(\sum_{c \in \mathcal{C}} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}\right)\right)$ 。

给定 $N$ 个训练样本 $D = \{x^{(n)}\}_{n=1}^N$ ，其对数似然函数为：

$\begin{aligned} \mathcal{L}(\mathcal{D} ; \theta) &=\frac{1}{N} \sum_{n=1}^{N} \log p\left(\mathbf{x}^{(n)} ; \theta\right) \\ &=\frac{1}{N} \sum_{n=1}^{N}\left(\sum_{c \in C} \theta_{c}^{\mathrm{T}} f_{c}\left(\mathbf{x}_{c}^{(n)}\right)\right)-\log Z(\theta) \\ \end{aligned}$

其中 $θ_c$ 为定义在团 $c$ 上的势能函数的参数。

可以看出，无向图模型的参数估计要比有向图更为复杂。在有向图中，每个局部条件概率的参数是独立的；而在无向图中，所有的参数都是相关的，无法分解。

因此，无向图的参数估计通常采用近似的方法。一是利用采样来近似计算这个期望；二是坐标上升法，即固定其它参数，来优化一个势能函数的参数。

4.2、含隐变量的参数估计

如果图模型中包含隐变量，即有部分变量是不可观测的，就需要用EM算法进行参数估计。

最后编辑于：2020.03.02 23:27:04

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 201,681评论 5赞 474
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,710评论 2赞 377
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 148,623评论 0赞 334
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,202评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,232评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,368评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,795评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,461评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,647评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,476评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,525评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,226评论 3赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,785评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,857评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,090评论 1赞 258
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,647评论 2赞 348
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,215评论 2赞 341

概率图模型

1、模型表示

1.1、有向图模型

1.2、常见的有向图模型

1.2.1、Sigmoid信念网络

1.2.2、朴素贝叶斯分类器

1.2.3、隐马尔科夫模型

1.3、无向图模型

1.4、无向图模型的概率分解

1.5、常见的无向图模型

1.5.1、对数线性模型

1.5.2、条件随机场

1.6、有向图和无向图之间的转换

2、推断

2.1、变量消除法

2.2、信念传播算法

2.2.1、链式结构上的的信念传播算法

2.2.2、树结构上的信念传播算法

3、近似推断

3.1、蒙特卡罗方法

3.2、拒绝采样

3.3、重要性采样

3.4、马尔可夫链蒙特卡罗方法

3.4.1、Metropolis-Hastings 算法

3.4.2、Metropolis算法

3.4.3、吉布斯采样

4、学习

4.1、不含隐变量的参数估计

4.2、含隐变量的参数估计

推荐阅读更多精彩内容