机器学习笔记第十四章概率图模型

14.1 隐马尔可夫模型

概率模型提供一种描述框架，将学习任务转化为计算变量的概率分布，利用已知变量来推测未知变量的分布为“推测”。假定关心的变量集合为 $Y$ ，可观测变量集合为 $O$ ，其他变量集合为 $R$ ，生成式模型联合分布 $P(Y,R,O)$ ，判别式模型考虑条件分布 $P(Y,R|O)$ ，给定一组观测变量值，推断就是从上述两个分布得到条件概率分布 $P(Y|O)$ 。

概率图模型是一类用图来表达变量关系的概率模型，最常见的是用一个结点表示一个或一组随机变量，边表示变量间的概率相关关系，即“变量关系图”。根据边的性质不同，分为有向无环图（也叫有向图模型或贝叶斯网）和无向图（也叫无向图模型或马尔可夫图）。

隐马尔可夫模型是结构最简单的动态贝叶斯网，主要应用于时序数据建模，在语音识别、自然语言处理等方面广泛应用。如图14.1所示，状态变量 $\left \{ y_{1},y_{2},...,y_{n} \right \}$ ，其中 $y_{i}\in \gamma$ 表示第i时刻系统状态，状态变量一般是隐藏的、不可被观测的，也称隐变量。观测变量 $\left \{ x_{1},x_{2},...,x_{n} \right \}$ ，其中 $x_{i}\in \chi$ 表示第i时刻的观测值。系统通常在多个状态 $\left \{ s_{1},s_{2},...,s_{N} \right \}$ 之间转换，故 $\gamma$ 一般有N个可能取值的离散空间，观测变量 $x_{i}$ 仅考虑离散型，并且假定其取值范围 $\chi$ 为 $\left \{ o_{1},o_{2},...,o_{M} \right \}$ 。

“马尔可夫链”就是系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态。基于这种依赖关系，所有变量的联合概率分布为

$P(x_{1},y_{1},...,x_{n},y_{n})=P(y_{1})P(x_{1}|y_{1})\prod_{i=2}^{n}P(y_{i}|y_{i-1})P(x_{i}|y_{i}).$

此外，隐马尔可夫模型还要一下三组参数：

         $\bullet$ 状态转移概率：模型在各状态间转换的概率记为矩阵 $A=[a_{ij}]_{N\times N}$ ，其中

$a_{ij}=P(y_{t+1}=s_{j}|y_{t}=s_{i}),$    $1\leqslant i,j\leqslant N,$

表示在任意时刻t，若状态为 $s_{i}$ ，则下一刻状态为 $s_{j}$ 的概率。

         $\bullet$ 输出观测概率：模型根据状态获得各个观测值的概率，通常记为矩阵 $B=[b_{ij}]_{N\times M}$ ，其中

$b_{ij}=P(x_{t}=o_{j}|y_{t}=s_{i}),$    $1\leqslant i\leqslant N,1\leqslant j\leqslant M$

表示在任意时刻t，若状态为 $s_{i}$ ，则观测值 $o_{j}$ 被获取的概率。

         $\bullet$ 初始状态概率：模型在初始时刻各状态出现的概率，通常记为 $\pi =(\pi _{1},\pi _{2},...,\pi _{N})$ ，其中

$\pi _{i}=P(y_{1}=s_{i}),$    $1\leqslant i\leqslant N$

表示模型的初始状态为 $s_{i}$ 的概率。

通过 $\gamma$ 、 $\chi$ 和三组参数能够确定一个隐马尔可夫模型，通常用参数 $\lambda =[A,B,\pi ]$ 来指代。给定 $\lambda$ ，可以下过程产生观测序列 $\left \{ x_{1},x_{2},...,x_{n} \right \}$ ：

(1)设置 $t=1$ ，并根据初始状态概率 $\pi$ 确定 $y_{1}$ ；

(2)根据 $y_{t}$ 和 $B$ 选择观测变量取值 $x_{t}$ ；

(3)根据 $y_{t}$ 和 $A$ 转移模型状态，即确定 $y_{t+1}$ ；

(4)若 $t< n$ ，设置 $t=t+1$ ，并转到第(2)步，否则停止。

14.2 马尔可夫随机场

马尔可夫随机场是著名无向图模型，其有一组势函数，也叫因子，这是定义在变量子集上的非负实函数，主要用于定义概率分布函数。如图14.2所示，若其中任意两结点间都有边连接，则称该结点子集为一个“团”，如果一个团中加入另外任何一个结点都不再形成团，则该团为“极大团”。

对于n个变量 $x=\left \{ x_{1},x_{2},...,x_{n} \right \}$ ，所有极大团构成的集合为 $C^{*}$ ，与团 $Q\in C^{*}$ 对应的变量集合记为 $x_{Q}$ ，则联合概率 $P(x)$ 定义为

$P(x)=\frac{1}{Z^{*}}\prod_{Q\in C^{*}}^{} \psi _{Q}(x_{Q}),$

其中 $Z^{*}=\sum_{x}^{}\prod_{Q\in C^{*}}^{}\psi _{Q}(x_{Q})$ 规范化因子，以确保 $P(x)$ 是被正确定义的概率。

如图14.3所示，如果从结点集A中的结点到B中的结点都必须经过结点集C中的结点，则称结点集A和B被结点集C分离，C称为“分离集”。全局马尔可夫性是指给定两个变量子集的分离集，则这两个变量子集条件独立。也就是说，若令A，B和C对应的变量集分别为 $x_{A},x_{B}$ 和 $x_{C}$ ，则 $x_{A}$ 和 $x_{B}$ 在给定 $x_{C}$ 的条件下独立，记为 $x_{A}\perp x_{B}|x_{C}$ 。

由全局马尔可夫性可得如下推论

$\bullet$ 局部马尔可夫性：给定某变量的邻接变量，则该变量条件独立于其他变量，形式化地说，令V为图的结点集， $n(v)$ 为结点v在图上的邻接结点， $n^{*}(v)=n(v)\cup \left \{ v \right \}$ ，有 $x_{v}\perp x_{V/n^{*}(v)}|x_{n(v)}$ 。

$\bullet$ 成对马尔可夫性：给定所有其他变量，两个非邻接变量条件独立。

为满足非负性，指数函数常被用于定义势函数，即

$\psi _{Q}(x_{Q})=e^{-H_{Q}(x_{Q})}.$

$H_{Q}(x_{Q})$ 是一个定义在变量 $x_{Q}$ 上的实值函数，常见形式为

$H_{Q}(x_{Q})=\sum_{u,v\in Q,u\neq v}\alpha _{uv}x_{u}x_{v}+\sum_{v\in Q}\beta _{v}x_{v},$

其中 $\alpha _{uv}$ 和 $\beta _{v}$ 是参数。上式中的第一项考虑每一对结点的关系，第二项仅考虑单节点。

14.3 条件随机场

条件随机场是一种判别式无向图模型，对条件分布进行建模。条件随机场试图对多个变量在给定观测值后的条件概率进行建模。具体来说，令 $x=\left \{ x_{1},x_{2},...,x_{n} \right \}$ 为观测序列，标记序列为 $y=\left \{ y_{1},y_{2},...,y_{n} \right \}$ ，那么条件随机场的目标是构建条件概率模型 $P(y|x)$ 。特别注意，y可以是结构型变量，即其分量之间具有某种相关性。

令 $G=\left \langle V,E \right \rangle$ 表示结点与标记变量y中元素一一对应的无向图， $y_{v}$ 表示与结点 $v$ 对应的标记变量， $n(v)$ 表示结点 $v$ 的邻接结点，若图G的每个变量 $y_{v}$ 都满足马尔可夫性，即

$P(y_{v}|x,y_{V/\left \{ v \right \}})=P(y_{v}|x,y_{n(v)})$ ，

则 $(x,y)$ 构成一个条件随机场。

在条件随机场中，条件概率为

$P(y|x)=\frac{1}{Z}exp(\sum_{j}\sum_{i=1}^{n-1}\lambda _{j}t_{j}(y_{i+1},y_{i},x,i)+\sum_{k}\sum_{i=1}^{n}\mu _{k}s_{k}(y_{i},x,i)),$

其中 $t_{j}(y_{i+1},y_{i},x,i)$ 是定义在观测序列的两个相邻标记位置上的转移特征函数， $s_{k}(y_{i},x,i)$ 是定义在观测序列的标记位置i上的状态特征函数。

14.4 学习与推断

边际分布是指对无关变量求和或积分后得到结果，给定参数 $\Theta$ 求解某个变量x的分布，就变成对联合分布中其他无关变量进行积分的过程，这称为“边际化”。

假设图模型对应的变量集 $x=\left \{ x_{1},x_{2},...,x_{N} \right \}$ 能分为 $x_{E}$ 和 $x_{F}$ 两个不相交的变量集，计算边际概率 $P(x_{F})$ 或条件概率 $P(x_{F}|x_{E})$ 。

$P(x_{F}|x_{E})=\frac{P(x_{E},x_{F})}{P(x_{E})}=\frac{P(x_{E},x_{F})}{\sum_{x_{F}}P(x_{E},x_{F})},$

其中联合概率 $P(x_{E},x_{F})$ 可基于概率图模型获得，故

$P(x_{E})=\sum_{x_{F}}P(x_{E},x_{F}).$

概率图模型的推断方法分为两类，即精确推方法和近似推断方法，接下来介绍两种有代表性的精确推断方法。

14.4.1 变量消去

精确推断是一类动态规划算法，利用图模型所描述的条件独立性来削减计算目标概率值所需的计算量。变量消去是构建其他精确推断算法的基础。如图14.7(a)所示

假定计算编辑概率 $P(x_{5})$ ，为此，只需加法消去变量 $\left \{ x_{1},x_{2},x_{3},x_{4} \right \}$ ，即

$P(x_{5})=\sum_{x_{4}}\sum_{x_{3}}\sum_{x_{2}}\sum_{x_{1}}P(x_{1},x_{2},x_{3},x_{4})$

$=\sum_{x_{4}}\sum_{x_{3}}\sum_{x_{2}}\sum_{x_{1}}P(x_{1})P(x_{2}|x_{1})P(x_{3}|x_{2})P(x_{4}|x_{3})P(x_{5}|x_{4})$

14.4.2 信念传播

变量消去法通过求和操作

$m_{ij}(x_{j})=\sum_{x_{i}}\psi (x_{i},x_{j})\prod_{k\in n(i)/j}m_{ki}(x_{i})$

消去变量 $x_{i}$ ，其中 $n(i)$ 表示结点 $x_{i}$ 的邻接结点。在信念传播算法中，该操作可看作从 $x_{i}$ 向 $x_{j}$ 传递了一个消息 $m_{ij}(x_{j})$ 。一个结点只有在接收到来自其他所有结点的消息后才能向另一个结点发消息，且结点的边际分布正比于它所接收的消息的乘积，即

$P(x_{i})\infty \prod_{k\in n(i)}m_{ki}(x_{i}).$

14.5 近似推断

14.5.1 MCMC采样

在许多任务中，我们关心某些概率分布并不是因为对这些概率分布本身感兴趣，而是要基于它们计算某些期望，并且进一步基于期望做决策。如果直接计算或逼近这个期望比推断概率分布更容易，则直接操作无疑将使推断问题更为高效。

假定目标是计算函数 $f(x)$ 在概率密度函数p(x)下的期望

$E_{p}[f]=\int f(x)p(x)dx,$

则可根据 $p(x)$ 抽取一组样本 $\left \{ x_{1},x_{2},...,x_{N} \right \}$ ，然后计算 $f(x)$ 在这些样本上的均值

$\tilde{f}=\frac{1}{N}\sum_{i=1}^{N}f(x_{i}),$

以此来近似目标期望 $E_{p}[f]$ 。概率图模型中最常用的采样技术是马尔可夫链蒙特卡罗方法，给定连续变量 $x\in X$ 的概率密度函数p(x)，x 在区间A中的概率可计算为

$P(A)=\int_{A}^{}p(x)dx.$

若有函数 $f:X\rightarrow R$ ，则可计算 $f(x)$ 的期望

$p(f)=E_{p}[f(X)]=\int_{x}f(x)p(x)dx.$

MCMC先构造出服从p分布的独立同分布随机变量 $x_{1},x_{2},...,x_{N}$ ，再得到上式的无偏估计

$\tilde{p}(f)=\frac{1}{N}\sum_{i=1}^{N}f(x_{i}).$

如果马尔可夫链运行时间足够长，则此时产出的样本x近似服从于分布p。假定平稳马尔可夫链T的状态转移概率（即从状态x转移到状态x'的概率）为 $T(x'|x)$ ，t时刻状态的分布为 $p(x^{t})$ ，则马尔可夫链满足平稳条件

$p(x^{t})T(x^{t-1}|x^{t})=p(x^{t-1})T(x^{t}|x^{t-1}),$

MCMC方法先构造一条马尔可夫链，使其收敛至平稳分布恰为待估计参数的后验分布，然后通过该马尔可夫链产生符合其后验分布的样本，并且基于这些样本来进行估计。

Metropolis-Hastings (简称 MH) 算法是 MCMC 的重要代表，它基于"拒绝采样"来逼近平稳分布 p，其算法如图14.9所示。

若 $x^{*}$ 最终收敛到平稳收态，则根据上式有

$p(x^{t-1})Q(x^{*}|x^{t-1})A(x^{*}|x^{t-1})=p(x^{*})Q(x^{t-1}|x^{*})A(x^{t-1}|x^{*}),$

于是，为了达到平稳状态，只需将接受率设置为

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

以下是用python实现的MH算法

import numpy as np
import matplotlib.pyplot as pltdef target_distribution(x):"""目标分布（需要进行采样的分布），这里以标准正态分布为例:param x: 输入值:return: 概率密度函数值"""return np.exp(-0.5 * x ** 2) / np.sqrt(2 * np.pi)def proposal_distribution(x, scale=1.0):"""提议分布（用于生成候选样本），这里以标准正态分布为例:param x: 当前值:param scale: 提议分布的标准差:return: 新的提议值"""return x + scale * np.random.randn()def metropolis_hastings(iterations, initial_value, proposal_scale):"""Metropolis-Hastings 算法:param iterations: 迭代次数:param initial_value: 初始值:param proposal_scale: 提议分布的标准差:return: 生成的样本"""samples = np.zeros(iterations)current_value = initial_valuefor i in range(iterations):proposed_value = proposal_distribution(current_value, proposal_scale)# 计算接受率acceptance_ratio = min(1, target_distribution(proposed_value) / target_distribution(current_value))# 接受或拒绝提议if np.random.rand() < acceptance_ratio:current_value = proposed_valuesamples[i] = current_valuereturn samples# 示例参数
iterations = 10000
initial_value = 0
proposal_scale = 1.0# 执行 Metropolis-Hastings 算法
samples = metropolis_hastings(iterations, initial_value, proposal_scale)# 可视化结果
plt.figure(figsize=(10, 6))
plt.hist(samples, bins=50, density=True, alpha=0.6, color='g', label='Samples')
x = np.linspace(-4, 4, 100)
plt.plot(x, target_distribution(x), 'r', label='Target Distribution')
plt.title('Metropolis-Hastings Sampling')
plt.xlabel('Value')
plt.ylabel('Density')
plt.legend()
plt.show()

我们希望从中采样的分布。示例中使用的是标准正态分布（均值为0，方差为1）；生成候选样本的分布。示例中使用的是标准正态分布，方差由 scale 参数决定；通过在提议分布中生成候选样本，并根据接受率决定是否接受这些样本来生成新的样本；使用 Matplotlib 绘制生成的样本的直方图，并与目标分布的理论密度函数进行比较。下图是代码运行的结果

14.5.2 变分推断

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

盘式记法如图所示，图14.10(a)表示N个变量 $\left \{ x_{1},x_{2},...,x_{N} \right \}$ 均依赖于其他变量z，图(b)中。相互独立、由相同机制生成的多个变量被放在一个方框(盘)内，并在方框中标出类似变量重复出现的个数N；方框可以嵌套。

图b中观察到的变量x的联合分布的概率密度函数是

$p(x|\Theta )=\prod_{i=1}^{N}\sum_{z}p(x_{i},z|\Theta ),$

所对应的对数似然函数为

$lnp(x|\Theta )=\sum_{i=1}^{N}ln\left \{ \sum_{z}p(x_{i},z|\Theta ) \right \},$

其中 $x=\left \{ x_{1},x_{2},...,x_{N} \right \}$ ， $\Theta$ 是x与z服从的分布参数。

概率模型的参数估计通常以最大化对数似然函数为手段。上式可使用EM算法，根据t时刻的参数 $\Theta ^{t}$ 对 $p(z|x,\Theta ^{t})$ 进行推断，并计算联合似然函数 $p(x,z|\Theta )$ ,进行最大化寻优，即对关于变量 $\Theta$ 的函数 $\wp(\Theta ;\Theta ^{t})$ 进行最大化从而求取