【西瓜书】第十四章概率图模型

本文是周志华老师《机器学习》第十四章概率图模型的学习笔记及部分习题答案。

概率模型是将学习任务归结为计算变量的概率分布的模型。在该模型中，利用已知的变量推测位置变量的分布称为推断。

假定关心的标量为$Y$，可观测变量集合为$O$，其他变量为$R$，那么就可以将模型分为两种：

生成式考虑联合分布$P(Y, R, O)$
判别式考虑条件分布$P(Y, R|O)$

给定观测变量，推断就是由上述分布去推测条件概率分布$P(Y|O)$

由于直接求解该模型的复杂度是指数级别的，因此我们需要有一套能够简洁紧凑表达变量关系的工具，其中的代表就是概率图模型。它利用图作为标识，用节点来表示随机变量，边来表示随机变量之间的关系，概率图主要分为两类：

贝叶斯网，使用有向无环图(常用于变量间存在显式因果关系的情况）
马尔科夫网，使用无向图（常用于变量之间存在相关性但没有明显因果性）

隐马尔可夫模型

隐马尔可夫模型（Hidden Markov Model， HMM）是最简单的动态贝叶斯网。其中的变量分为两组，第一组是状态变量$y_i \in \mathcal{Y}$表示第i时刻的系统，通常被设定为隐变量，即不可观测的。第二组是观测变量$x_i \in \mathcal{X}$表示i时刻的观测值。

状态变量$y_i$的取值范围被称为状态空间，通常是有$N$个取值的离散空间。

如下图所示，HMM中的依赖关系有两种：

观测变量的取值仅依赖于同一时刻的状态变量。
当前时刻的状态变量仅依赖于前一时刻的状态变量。即所谓的马尔可夫性质（在DP里叫无后效性）。

根据这种依赖关系，所有变量的联合概率分布就是：

$P \left( x _ { 1 } , y _ { 1 } , \ldots , x _ { n } , y _ { n } \right) = P \left( y _ { 1 } \right) P \left( x _ { 1 } | y _ { 1 } \right) \prod _ { i = 2 } ^ { n } P \left( y _ { i } | y _ { i - 1 } \right) P \left( x _ { i } | y _ { i } \right)$

确定了结构信息后，HMM还需要以下三组参数：

状态转移概率，模型在各个状态之间转移的概率，记作$A$

$a _ { i j } = P \left( y _ { t + 1 } = s _ { j } | y _ { t } = s _ { i } \right)$

输出观测概率，即由状态导出观测的概率分布，记作$B$
$b _ { i j } = P \left( x _ { t } = o _ { j } | y _ { t } = s _ { i } \right)$
初始状态概率，模型初始时个状态的概率，记作$\pi$

$\pi _ { i } = P \left( y _ { 1 } = s _ { i } \right)$

那么一个HMM可以通过状态空间$\mathcal{Y}$, 观测空间$\mathcal{X}$和参数$\lambda = [A,B, \pi]$来确定，并按照一些过程产生观测序列：

$t=1$时，按照初始状态概率$\pi$选择初始状态$y_1$
由当前状态和输出观测概率$B$选择观测变量$x$
由当前状态和状态转移矩阵$A$确定下一状态
若$t\lt n $，则$t+=1$，并转到第2步，否则停止

在应用中，人们会关注三个问题：

给定模型参数，如何计算其产生的观测序列的概率的概率$P(X|\lambda)$。
给定模型和观测序列，如何找到与该观测序列最匹配的状态序列，即由观测序列推断状态序列。
给定观测序列，如何调整模型参数，使得$P(x|\lambda)$最大

由于HMM的条件独立性，这三个问题都可以高效求解。

马尔科夫随机场

马尔科夫随机场（Markov Random Field， MRF）是一种典型的马尔可夫网络。

首先来介绍MRF中两个重要的概念：

MRF其中有一组势函数(potential function)，又称因子(factor)，它是定义在变量子集上的非负实函数，用于定义概率分布函数。
对MRF中节点的自己，若其中任意两个节点之间都有边连接，则称该子集为团(clique)，当团中加入任意一个节点都不能构成团，则称其为极大团。

有了团的概念，MRF中变量的联合概率分布能基于团分解为多个因子的乘积。当然，在变量个数较多时，团的数目会显著增加，所以我们往往基于极大团来定义联合概率，所有极大团组合集合为$C^*$，则：

$P ( \mathbf { x } ) = \frac { 1 } { Z ^ { * } } \prod _ { Q \in \mathcal { C } ^ { * } } \psi _ { Q } \left( \mathbf { x } _ { Q } \right)$

其中$Z^*$为规范化因子。那么，如下图的一个MRF的联合概率分布就可以定义为：

$P ( \mathbf { x } ) = \frac { 1 } { Z } \psi _ { 12 } \left( x _ { 1 } , x _ { 2 } \right) \psi _ { 13 } \left( x _ { 1 } , x _ { 3 } \right) \psi _ { 24 } \left( x _ { 2 } , x _ { 4 } \right) \psi _ { 35 } \left( x _ { 3 } , x _ { 5 } \right) \psi _ { 256 } \left( x _ { 2 } , x _ { 5 } , x _ { 6 } \right)$

在MRF中，如果从结点集A到结点集B的路径都要经过结点集C，则成结点集A，B被C分离，C称作分离集（如下图）：

那么对于MRF就有全局马尔可夫性质(global Markov property)：给定两个变量子集的分离集，则这两个变量子集条件独立。记作：

$\mathbf { x } _ { A } \perp \mathbf { x } _ { B } \left| \mathbf { x } _ { C }\right.$

接着由该性质可以推出两个有用的推论：

局部马尔可夫性（local Markov property）：给定某变量的邻接变量，则该变量独立于其他变量
成对马尔可夫性（pairwise Markov property）：给定所有其他变量，两个非邻接变量条件独立

MRF中的势函数是用来刻画变量之间的相互关系，为了满足其非负性，势函数被定义为指数函数：

$\psi _ { Q } \left( \mathbf { x } _ { Q } \right) = e ^ { - H _ { Q } \left( \mathbf { x } _ { Q } \right) }$

其中，常有：

$H _ { Q } \left( \mathbf { x } _ { Q } \right) = \sum _ { u , v \in Q , u \neq v } \alpha _ { u v } x _ { u } x _ { v } + \sum _ { v \in Q } \beta _ { v } x _ { v }$

其中$\alpha, \beta$均是参数，函数$H_Q$中两项分别考虑的是单个节点和成对节点。

条件随机场

条件随机场（Conditional Random Field， CRF）是一种判别式模型，和前面生成式的MRF不同，它对条件分布进行建模。它可以看作给定观测值的MRF。

CRF的目标是构建条件概率模型$P(y|x)$,标记变量$y$可以是分量之间具有某种相关性的结构型变量（例如词性标注中的序列结构，语法分析中的树形结构）。

我们用$G=(V,E)$来表示图，并设图中节点和标记变量一一对应，$y_v$表示和节点$v$对应的标记变量，$n(v)$表示节点$v$的邻接节点，若图中变量满足马尔科夫性

$P \left( y _ { v } | \mathbf { x } , \mathbf { y } _ { V \backslash \{ v \} } \right) = P \left( y _ { v } | \mathbf { x } , \mathbf { y } _ { n ( v ) } \right)$

则$(y,x)$构成一个CRF。

现实应用中，常用的是下图所示的链式结构，即链式条件随机场，我们就此展开讨论。

CRF也利用势函数和团来定义联合概率：

$P ( \mathbf { y } | \mathbf { x } ) = \frac { 1 } { Z } \exp \left( \sum _ { j } \sum _ { i = 1 } ^ { n - 1 } \lambda _ { j } t _ { j } \left( y _ { i + 1 } , y _ { i } , \mathbf { x } , i \right) + \sum _ { k } \sum _ { i = 1 } ^ { n } \mu _ { k } s _ { k } \left( y _ { i } , \mathbf { x } , i \right) \right)$

其中$t_j(y_{i+1}, y_i,x,i)$是定义在观测序列的两个相邻标记位置上的转移特征函数，用于刻画相邻标记变量之间的相关关系以及观测序列对其的影响；$s_k(y_i, x,i)$是定义在观测序列的标记位置i上的状态特征函数，用于刻画观测序列对标记变量的影响。

定义好合适的两个特征函数后，就可以使用条件随机场了。

CRF和MRF形式上非常像，区别在于一个处理的是条件概率一个处理的是联合概率。

学习和推断

概率模型图中的推断是指由联合概率分布去推算边际分布或者条件分布。
学习则是指确定概率图模型中具体分布的参数。

在贝叶斯学派看来，参数和变量都看作随机变量，因此参数估计和变量推断可以统一起来（当然频率学派不这么看），那么接下来我们就主要讨论概率图的推断方法。

我们将模型的变量集分为两个不相交的变量集$XE$和$XF$，推断问题的目标就是计算边际概率$P(X_F)$或者条件概率$P(X_F|X_E)$：

$P \left( \mathbf { x } _ { F } | \mathbf { x } _ { E } \right) = \frac { P \left( \mathbf { x } _ { E } , \mathbf { x } _ { F } \right) } { P \left( \mathbf { x } _ { E } \right) } = \frac { P \left( \mathbf { x } _ { E } , \mathbf { x } _ { F } \right) } { \sum _ { \mathbf { x } _ { F } } P \left( \mathbf { x } _ { E } , \mathbf { x } _ { F } \right) }$ $P \left( \mathbf { x } _ { E } \right) = \sum _ { \mathbf { x } _ { F } } P \left( \mathbf { x } _ { E } , \mathbf { x } _ { F } \right)$

大致上，推断方法可以分为两类，一类是精确推断，一类是近似推断。前者复杂度较高，不适合数据太大时应用，后者则希望在较低的复杂度下获得原问题的近似解。

下面介绍两种精确推断方法：变量消去和信念传播。

变量消去

变量消去是最直观的精确推断算法，其主要思想是通过独立性将计算目标进行分解，然后利用乘法对加法的分配律，将多个变量积的求和问题，转换为对部分变量交替求和求积的问题。由于每次求和/求积都限制在局部，因此仅和部分变量有关。

以下面的过程为例：

$\begin{aligned} P \left( x _ { 5 } \right) & = \sum _ { x _ { 3 } } P \left( x _ { 5 } | x _ { 3 } \right) \sum _ { x _ { 4 } } P \left( x _ { 4 } | x _ { 3 } \right) m _ { 23 } \left( x _ { 3 } \right) \\ & = \sum _ { x _ { 3 } } P \left( x _ { 5 } | x _ { 3 } \right) m _ { 23 } \left( x _ { 3 } \right) \sum _ { x _ { 4 } } P \left( x _ { 4 } | x _ { 3 } \right) \\ & = \sum _ { x _ { 3 } } P \left( x _ { 5 } | x _ { 3 } \right) m _ { 23 } \left( x _ { 3 } \right) m _ { 43 } \left( x _ { 3 } \right) \\ & = m _ { 35 } \left( x _ { 5 } \right) \end{aligned}$

其中$m$是计算的中间过程。

但是变量消去会有大量的冗余计算（这取决于变量消去的顺序，但是最优顺序的求解是NP难的）。

信念传播

信念传播算法是将变量消去中的求和操作看作一个消息传递过程，从而较好的解决了求多个边际分布时候的重复计算问题。也就是说，对于一步变量消去来说，其操作为：

$m _ { i j } \left( x _ { j } \right) = \sum _ { x _ { i } } \psi \left( x _ { i } , x _ { j } \right) \prod _ { k \in n ( i ) \backslash j } m _ { k i } \left( x _ { i } \right)$

该式消去了变量$xi$，在信念传播算法中该操作被视为从$x_i$传递一个$m{ij}(x_j)$信息到$x_j$。那么，和变量消去一样的，每次消息传递仅在局部进行。每个节点在收到其他所有节点的消息后开始向另一个节点发送消息，且节点的边际分布正比与它所接受的消息的乘积：

$P \left( x _ { i } \right) \propto \prod _ { k \in n ( i ) } m _ { k i } \left( x _ { i } \right)$

整个信念传播算法分为两步：

指定根节点，从所有叶子节点开始向根节点传递消息，直到根节点收到消息。
根节点开始向叶子节点传播消息，直到所有叶子节点收到消息。

近似推断

由于精确推断需要很大的计算开销，因此实际中应用更多的是近似推断方法。该方法可以分为两类，一类是采样，使用随机化方法完成近似；一类是变分推断，使用确定性近似完成近似推断。

MCMC采样

在很多任务中，我们计算概率分布的目的是希望由此计算出期望，那么当直接计算或者逼近该期望比推断概率分布更容易时，我们就不妨直接去计算期望。

假设我们需要计算函数$f$在概率密度函数$p$下的期望：

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

我们可以用样本均值来逼近：

$\hat { f } = \frac { 1 } { N } \sum _ { i = 1 } ^ { N } f \left( x _ { i } \right)$$。其关键是如何采样来在尽量少的样本数中获得尽量高的近似度。概率图模型中最常用的方法是马尔可夫蒙特卡洛方法（MCMC）.其关键在于，构造出一个平稳分布为$p$的马尔科夫链，此时当马尔科夫链运行时间够长，则产出的样本近似服从于$p$。令马尔可夫链的状态转移概率为$T$， $t$时刻分布为$p(x^t)$，则当： $$p \left( \mathbf { x } ^ { t } \right) T \left( \mathbf { x } ^ { t - 1 } | \mathbf { x } ^ { t } \right) = p \left( \mathbf { x } ^ { t - 1 } \right) T \left( \mathbf { x } ^ { t } | \mathbf { x } ^ { t - 1 } \right)$

时该马尔可夫链达到平稳状态，$p(x)$是其平稳分布。

也就是说MCMC先构造一条马尔可夫链，使其收敛到的平稳分布恰为待估计参数的后验分布，然后通过这条马尔可夫链来产生符合后验分布的样本，并基于这些样本来进行估计。这里马尔可夫链的转移概率的构造至关重要，不同的构造方法也产生不同的MCMC方法。

M-H算法

Metropolis-Hastings算法是MCMC的重要代表，它基于拒绝采样来逼近平稳分布。

其基本过程是：

基于当前状态的分布进行采样，选出候选样本$x^*$
基于均匀分布采样出阈值$u$
若阈值$u\le A(x^*|x^{t-1})$，则接受该采样结果，否则拒绝该结果。
回到步骤1，直到采样结束

这里那么状态转移概率写成先验转移概率$Q$和接受概率$A$的乘积$Q(x|x^{t-1]})A(x|x^{t-1})$，则平稳状态时：

$p \left( \mathbf { x } ^ { t - 1 } \right) Q \left( \mathbf { x } ^ { * } | \mathbf { x } ^ { t - 1 } \right) A \left( \mathbf { x } ^ { * } | \mathbf { x } ^ { t - 1 } \right) = p \left( \mathbf { x } ^ { * } \right) Q \left( \mathbf { x } ^ { t - 1 } | \mathbf { x } ^ { * } \right) A \left( \mathbf { x } ^ { t - 1 } | \mathbf { x } ^ { * } \right)$

具体算法描述如下：

其中接受率设置为：

$A \left( \mathbf { x } ^ { * } | \mathbf { x } ^ { t - 1 } \right) = \min \left( 1 , \frac { p \left( \mathbf { x } ^ { * } \right) Q \left( \mathbf { x } ^ { t - 1 } | \mathbf { x } ^ { * } \right) } { p \left( \mathbf { x } ^ { t - 1 } \right) Q \left( \mathbf { x } ^ { * } | \mathbf { x } ^ { t - 1 } \right) } \right)$

吉布斯采样可以被看作MH算法的特例，它也采用马尔可夫链来获取样本，其区别在于：没有拒绝采样；每次只更新变量的一个分量。

变分推断

变分推断通过已知简单分布来逼近复杂分布，并通过限制近似分布的类型得到一种局部最优但具有确定解的近似后验分布。

假设某个概率图中所有可观察变量$x$的联合分布为：

$p ( \mathbf { x } | \Theta ) = \prod _ { i = 1 } ^ { N } \sum _ { \mathbf { z } } p \left( x _ { i } , \mathbf { z } | \Theta \right)$

则似然函数为：

$\ln p ( \mathbf { x } | \Theta ) = \sum _ { i = 1 } ^ { N } \ln \left\{ \sum _ { \mathbf { z } } p \left( x _ { i } , \mathbf { z } | \Theta \right) \right\}$

其中$\Theta$为$x,z$服从的分布参数，那么整个学习任务就是由观测变量来估计隐变量$p(z|x,\Theta)$和参数$\Theta$.
这个模式似乎很常见哦，其实就可以对似然函数使用EM算法：

E-step 固定参数，计算似然函数
M-step 最大化对数联合似然函数在当前分布下的期望，来更新参数

参数更新如下：

$\begin{aligned} \Theta ^ { t + 1 } & = \underset { \Theta } { \arg \max } \mathcal { Q } \left( \Theta ; \Theta ^ { t } \right) \\ & = \underset { \Theta } { \arg \max } \sum _ { \mathbf { z } } p ( \mathbf { z } | \mathbf { x } , \Theta ^ { t } ) \ln p ( \mathbf { x } , \mathbf { z } | \Theta ) \end{aligned}$

但是，在实际任务中，E步往往因为z模型复杂而难以进行，此时可以借助变分推断。
首先假设多变量$z$可以拆解为一系列相互独立的多变量$z_i$，分别服从于分布$q_i$，然后对于这些$q_i$假设它们分布相对简单。

通过恰当分割独立变量子集并选择其服从的分布，我们可对隐变量做高效推断，这种方法是通过联合近似函数$\ln p(x,z)$在$z_j$之外的隐变量分布上求期望得到的，因此又称为平均场(mean field)算法。

当然，实践中以下两点往往严重限制了变分推断的发挥：

隐变量的分割方式
变量子集的分布假设

主题模型

主题模型（topic model）是一种生成式有向图模型，主要用于离散型数据，其中典型代表是隐迪利克雷分配模型（Latent Dirichlet Allocation, LDA）。

其中的几个基本概念：词（word）是待处理数据的基本离散单元；文档（document）是待处理的数据对象，它用词袋模型（bag-of-words）来表示，其中的词在文档中是不计顺序的；主题是一个概念，表现为一系列相关词及其它们在该概念下出现的概率。

那么按照LDA主题模型，一篇文档$d$是这么生成的：

根据参数为$\alpha$的迪利克雷分布随机采样一个话题分布$\Theta_t$。
按照以下步骤生成文档中的$N$个词：
- 根据$\Thetat$进行话题指派，得到文档$t$中词$n$的话题$z{t,n}$
- 根据指派的话题所对应的词频分布$\beta_k$随机采样生成词。

用盘式标记的话，LDA的变量关系就如下：

其中文档的词频$w{t,n}$是唯一的观测变量，它依赖于对这个词进行的话题指派$z{t,n}$，以及话题对应的词频$\betak$；同时，话题指派$z{t,n}$依赖于话题分布$\Theta_t$，$\Theta_t$依赖于迪利克雷分布的参数$\alpha$，而话题词频则依赖于参数$\eta$。$K$是话题个数，$T$是文档篇数，$N$是词典中词个数。

那么LDA模型的联合概率分布就是：

$\begin{aligned} p ( \mathbf { W } , \mathbf { z } , \boldsymbol { \beta } , \Theta | \boldsymbol { \alpha } , \boldsymbol { \eta } ) & = \\ & \prod _ { t = 1 } ^ { T } p \left( \Theta _ { t } | \boldsymbol { \alpha } \right) \prod _ { i = 1 } ^ { K } p \left( \boldsymbol { \beta } _ { k } | \boldsymbol { \eta } \right) \left( \prod _ { n = 1 } ^ { N } P \left( w _ { t , n } | z _ { t , n } , \boldsymbol { \beta } _ { \boldsymbol { k } } \right) P \left( z _ { t , n } | \Theta _ { t } \right) \right) \end{aligned}$

其中话题词频$p(beta_k|eta)$和话题分布分布服从迪利克雷分布。那么$\alpha$和$\eta$就是模型中待确定的参数。

给定训练数据，LDA的参数可以用极大似然法来估计，但是实践中往往采用变分法来求近似解。

当模型已知时（$\alpha,\beta$确定），推断文档的话题结构可以用下式进行：

$p ( \mathbf { z } , \boldsymbol { \beta } , \Theta | \mathbf { W } , \boldsymbol { \alpha } , \boldsymbol { \eta } ) = \frac { p ( \mathbf { W } , \mathbf { z } , \boldsymbol { \beta } , \Theta | \boldsymbol { \alpha } , \boldsymbol { \eta } ) } { p ( \mathbf { W } | \boldsymbol { \alpha } , \boldsymbol { \eta } ) }$

但是实际中往往该式难以求解，因此常用吉布斯采样或者变分法来推断。