概率图模型

笔者对概率图模型一直充满兴趣，决定趁这个机会好好整理一下。内容主要包括贝叶斯网络、马尔可夫随机场，以及概率图上的推断和学习问题的常见算法。也是对之前学习的MCMC方法、EM算法等的一个综合性理解。

主要参考了 Stanford’CS228’ Probabilistic Graphical Models

以及 深度学习，邱锡鹏著

概率图模型表示

概率图模型用图结构表示变量之间的因果关系、相关关系。

图中的结点表示随机变量，图中的连边表示随机变量之间的关联性，根据边的方向，主要分为两种模型：

• 有向图模型（贝叶斯网络），用有向边表示变量之间的因果关系
• 无向图模型（马尔可夫随机场），用无向边表示变量之间的依赖关系

贝叶斯网络

贝叶斯网路更进一步是一个DAG（Directed Acyclic Graph），因为如果构成环路不符合因果关系的定义。

对于贝叶斯网络的局部结构，和相应的独立性和条件独立性，整理在下表中：

贝叶斯网络中，结点之间的因果关系可以用条件概率刻画, 也即用$P(X \vert Y)$反映边$Y \rightarrow X$之间的因果关系。

该条件概率可以有不同的表示方式:

• 确定的函数关系
• 数结构表示方法
• 表格表示方法

在贝叶斯网络中，联合概率可以简单地分解成条件概率的乘积。

马尔可夫随机场

在马尔可夫随机场中，仅知道结点之间的相关关系。

此时为了计算所有结点的联合概率，不能简单地像贝叶斯网络一样分解为条件概率的乘积。

此时需要用到Hammersley-Clifford 定理，将马尔可夫随机场的联合概率$p(x)$和势能函数$\phi$建立其联系:

Hammersley-Clifford 定理的证明稍显繁琐，此处暂略，但该定理可以进行直观理解。

$ p(x) = \frac{\prod_C \phi_C(x_C)}{Z},Z = \sum_{x \in X}\prod_C \phi_C(x_C)$, 其中$C$为图上的最大团，$Z$称为配分函数，用来归一化概率。

常见的对势能函数的表示方法是对数线性模型：

$\phi(x \vert \theta) = \exp(\theta^T f(x))$。其中$f(x)$为$x$上的特征向量。

此时对数联合概率可以写为，$\log p(x) = \theta^T f(x) - \log Z$

推断

经典的推断问题是，给定一个概率图，在观测到了部分变量的前提下，求未观测到的变量的条件概率。

推断问题对于实际应用，决策、推理等具有应用价值，也常常作为其他算法（如概率图上的学习算法）的一个子部分出现。

由于涉及积分，推断问题复杂度很高，除了精确推断算法，通常还会有近似推断算法。

变量消除法

变量消除法是最简单直接的精确推断方法。本质上就是直接计算，对于贝叶斯网络和马尔可夫随机场都是适用的。

该算法比较简单，因此这里不过多叙述。

信念传播

首先需要从因子图（factor graph，cluster graph）讲起，由于概率图的局部马尔可夫性，概率图上所有变量的联合概率可以分解为因子团的乘积（在贝叶斯网络中为条件概率，在马尔可夫随机场中为势能函数）。因子图是将每个因子团构成因子图上的结点，对于有联系的因子团（具有相同变量的因子团）之间连边。

信念传播算法是在因子团上面传播消息，结点$i$到结点$j$传递的消息为$\delta_{i \rightarrow j}$

边上的消息定义为双向消息的乘积，$\mu_{ij} = \delta_{i \rightarrow j} \delta_{j \rightarrow i}$

而结点上的信念度定义为其收到的所有消息以及其势能函数的乘积，$\beta_i = \phi_i \prod_{j \in N(i)} \delta_{j \rightarrow i} $

又由于$\frac{\prod_i \beta_i}{ \prod_{ij} \mu_{ij}} = \frac{\prod_i\phi_i \prod_{j \in N(i)} \delta_{j \rightarrow i}}{\prod_{ij} \delta_{i \rightarrow j} \delta_{j \rightarrow i}} = \prod_i \phi_i$

因此，传播后的信念度可以作为结点上的概率（无向图中需要除以配分函数)。

对于树结构的概率图，此时因子图和原概率图是等价的，信念传播得到的结果就是精确解。

而对于带有环路的概率图模型，仍然使用信念传播，将得到近似解，称为环路信念传播算法。

近似推断

近似推断通常是基于采样的算法，可以参见 蒙特卡罗方法与MCMC

这里补充关于蒙特卡罗方法的理解，本质上是依托于大数定律的方法。

根据大数定理，$\bar X \rightarrow E[X]$，对于示性函数应用大数定理，则有$\bar I(x=k) \rightarrow E[I(x=k)] = P(X=k)$

更进一步，蒙特卡罗方法的界，可以由著名的Hoeffding不等式给出。

学习

学习问题，是给定了概率图的观测数据之后，对其参数进行估计的任务。

学习问题，分为不含隐变量和含隐变量的估计，本文将从不含隐变量的情况开始，最后使用EM算法推广到含隐变量的情况。

贝叶斯网络的极大似然估计

由于贝叶斯网络中的因果关系本质上给定了条件概率。其极大似然估计是简单的，关于极大似然估计，可以参见 极大似然估计的性质

$p(x,y) = p(y) p(x \vert y), \log p(x,y) = \log p(y)+\log p(x \vert y)$

观察上式，最大化对数似然函数，只需先最大化$\log p(y)$ ，再最大化$ \log p(x \vert y)$即可。

马尔可夫随机场的梯度上升法

马尔可夫随机场的极大似然估计，通常采用梯度上升法寻找最大值。

考虑对数线性模型，$\phi(x) = \exp(\theta^T f(x))$

对其经验似然函数求导可以得到，

$E_{x \sim \tilde{p} }[f(x)] - \frac{\sum_x \exp(\theta^T f(x)) f(x)}{Z} = E_{x \sim \tilde{p} }[ f(x)] - E_{x \sim p }[f(x)]$

上式的含义是，对于马尔可夫随机场，其经验似然函数的最大值当且仅当其特征的经验分布和理论分布相同。

极大后验估计

极大后验估计基于贝叶斯统计的思想。

不同于非贝叶斯统计中，认为参数是固定的值，通过最大化似然函数来寻求最合适的参数。

贝叶斯统计认为，参数是存在先验分布的，所谓的参数估计问题无非是在给定观测数据的前提下，计算参数的后验分布。

$p(\theta \vert x) = \frac{p(x \vert \theta) p(\theta)}{p(x)}$，对于已知$p(x)$的前提，贝叶斯统计的任务是最大化后验估计: $p(x \vert \theta) p(\theta)$

此时的问题只在于寻找先验概率$p(\theta)$，最简单先验概率可以为β分布或者狄利克雷分布，关于迪利克雷分布和贝叶斯统计的关系，可以参考 知乎’狄利克雷分布和狄利克雷过程 . 而在贝叶斯网络中，可以考虑假设先验分布为多项分布等。

对于马尔可夫随机场，由于通常使用梯度上升法寻找最大值，此时可以考虑假设先验分布为高斯分布或者拉普拉斯分布，在这两个先验分布下，关于参数$\theta$的导数可以认为是无先验的情况下，加上了$L_2 \text{ or } L_1$正则项。关于高斯分布与拉普拉斯分布与正则化的关系，可以参见 博客园‘ L1和L2正则化。

含隐变量的估计：EM算法

对于含有隐变量的估计，通常使用EM算法。

在含隐变量的估计中，核心的问题是：

• 求参数$\theta$的极大似然估计需要隐变量$z$的观测情况，但$z$又是未知的
• 根据可观测的$x$推断不可观测的$z$,需要计算在给定参数$\theta$的前提下，计算条件概率$p(z \vert z)$， 但$\theta$却也是未知的。

EM算法利用引入一个额外的分布，迭代地进行上述两个相互依赖的问题，并且可以保证算法收敛。

对于EM算法详细而严谨的推导，可以参见 EM算法