概率图模型

机器学习最重要的任务：根据已观察到的证据对感兴趣的未知变量进行估计和推测

概率模型（probabilistic model）提供了一种描述框架，将描述任务归结为计算变量的概率分布。

在概率模型中，利用已知变量推测未知变量的分布称为”推断“（inference），其核心是基于可观测的变量推测出未知变量的条件分布

生成式：计算联合分布 $P(Y,R,O)$
判别式：计算条件分布 $P(Y,R\vert O)$

其中Y为关心的变量集合，O为可观测变量集合，R为其他变量集合

直接利用概率求和规则消去变量R，时间和空间复杂度为指数级别 $O(2^{\vert Y\vert+\vert R\vert})$ ，需要一种工具简洁紧凑地表达变量间的关系————概率图模型

概率图模型（probabilistic graphical model）：表达变量相关关系的概率模型，一种描述框架

结点：随机变量（集合）
边：变量之间的依赖关系

分类：

有向图：贝叶斯网，表示变量之间的依赖关系
无向图：马尔可夫网，表示变量之间的相关关系

隐马尔可夫模型（动态贝叶斯网）

隐马尔可夫模型（Hidden Markov Model，HMM）组成

状态变量： ${y_1,\dots,y_n}$ ，假定是隐藏的、不可被观测的
- 取值范围为 $\mathcal{Y}$ ，有N个可能取值的离散空间
观测变量： ${x_1,\dots,x_n}$ ，第i个时刻的观测值集合
- 观测变量为离散型或连续型，取值范围为 $\mathcal{X}={o_1,\dots,o_M}$

t时刻的状态 $x_t$ 只依赖于 t-1 时刻的状态 $x_{t-1}$ ，和其他 n-2 个状态无关

马尔可夫链：系统下一个时刻状态仅由当前状态决定，不依赖于之前的任何状态

HMM的基本组成

\[P(x_1,y_1,\dots,x_n,y_n)=P(y_1)P(x_1\vert y_1) \prod\limits_{i=2}^n P(y_i\vert y_{i-1})P(x_i\vert y_i)\]

确定一个HMM需要三组参数 $\lambda=[A,B,\pi]$

状态转移概率：模型在各个状态间转换的概率
- 表示在时刻t，若状态为 $s_i$ ，下一个状态 $s_j$ 的概率

\[A=[a_{ij}]_{N\times N}\\ a_{ij}=p(y_{t+1}=s_j\vert y_t=s_i)\\ 1\le i,j\le N\]

输出观测概率：模型根据当前状态获得各个观测值的概率
- 在任意时刻t，若状态为 $s_i$ ，则在下一时刻状态为 $s_j$ 的概率

\[B=[b_{ij}]_{N\times N}\\ b_{ij}=p(x_t=o_j\vert y_t=s_i)\\ 1\le i\le N,1\le j\le M\]

初始状态概率：模型在初始时刻各个状态出现的概率

\[\pi=[\pi_1,\dots,\pi_n]\\ \pi=p(y_1=s_i)\\ 1\le i\le N\]

HMM的生成过程

通过指定状态空间 $\mathcal{Y}$ ，观测空间 $\mathcal{X}$ 和上述三组参数，就可以确定一个马尔可夫模型，给定 $\lambda=[A,B,\pi]$ ，按照如下过程生成观察序列

设置 t=1，并根据初始状态 $\pi$ 选择初始状态 $y_1$
根据状态 $y_t$ 和输出观测概率 B 选择观测变量取值 $x_t$
根据状态 $y_t$ 和状态转移矩阵 A 转移模型状态，确定 $y_{t+1}$
若 $t<n$ ，设置 t=t+1，并转到第二步，否则停止

HMM的基本问题

对于模型 $\lambda=[A,B,\pi]$ ，给定观测序列 $x={x_1,\dots,x_n}$

评估模型和观测序列之间的匹配程度：有效计算观测序列其产生的概率 $P(x\vert\lambda)$
根据观测序列”推测“隐藏的模型状态 $y={y_1,\dots,y_n}$
参数学习：如何调整模型参数 $\lambda=[A,B,\pi]$ 使得该序列出现的概率最大 $P(x\vert \lambda)$

具体应用

根据以往的观测序列 $x={x_1,\dots,x_n}$ 预测当前时刻最有可能的观测值 $x_n$
语音识别：根据观测的语音信号推测最有可能的状态序列
通过数据学习参数（训练模型）

马尔可夫随机场/条件随机场

马尔可夫随机场（Markov random field，MRF）：典型的马尔可夫网，无向图模型

结点表示变量，边表示依赖关系
有一组势函数（potential functions），也称为因子（factor），是定义在变量子集上的非负实函数，用于定义概率分布函数

分布形式化：使用基于 极大团 的势函数（因子）

对于图中结点的一个子集，如果其中所有结点为全连接，则该子集为一个 团（clique） 。如果一个团加入另外的任何结点都不再形成团，则该团称为 极大团（maximal clique）
每个结点至少出现在一个极大团中
多个变量之间的连续分布可基于团分解为多个因子的乘积

对于 n 个变量 $x={x_1,\dots,x_n}$ ，所有团构成的集合为 C ，与团 Q 对应的变量集合为 $x_Q$ ，则联合概率定义为

\[P(x)=\frac{1}{Z}\prod\limits_{Q\in C}\psi_Q(x_Q)\]

其中 $\psi_Q$ 是团 Q 对应的势函数，Z 为概率的规范化因子，实际中不需要精确计算。实际中变量、团的数量过多，会给计算带来负担，所以考虑 极大团

基于 极大团 的势函数：联合概率分布可以使用极大团定义，以上面的图模型为例

\[\begin{aligned} P(x)=&\frac{1}{Z}\psi_{12}({x_1,x_2})\psi_{13}({x_1,x_3})\\ &\psi_{24}({x_2,x_4})\psi_{35}({x_3,x_5})\psi_{256}({x_2,x_5,x_6}) \end{aligned}\]

马尔可夫随机场中的分离集

马尔可夫随机场中得到 “条件独立性”
若从结点集 A 中的结点到 B 中的结点都必须经过结点集 C 中的结点，则称 C 是 A 和 B 的分离集（separating set）

全局马尔可夫性（global Markov property）：给定分离集的条件下，两个变量子集条件独立
令 A、B、C 对应的变量集为 $x_A,x_B,x_C$ ，则 $x_A,x_B$ 在 $x_C$ 给定条件下独立，记为

\[x_A\perp x_B\mid x_C\]

图模型简化为

得到的图模型联合概率为

\[P(x_A,x_B,x_C)=\frac{1}{Z}\psi_{AC}(x_A,x_C)\psi_{CB}(x_C,x_B)\]

条件概率为

\[\begin{aligned} P(x_A,x_B\vert x_C)& =\frac{P(x_A,x_B,x_C)}{P(x_C)} =\frac{P(x_A,x_B,x_C)}{\sum_{x_A^{'}}\sum_{x_B^{'}}p(x_A^{'},x_B^{'},x_C)}\\ &=\frac{\frac{1}{Z}\psi_{AC}(x_A,x_C)\psi_{CB}(x_C,x_B)}{\sum_{x_A^{'}}\sum_{x_B^{'}}p(x_A^{'},x_B^{'},x_C)}\\ &=\frac{\psi_{AC}(x_A,x_C)}{\sum_{x_A^{'}}\psi_{AC}(x_A^{'},x_C)}\cdot\frac{\psi_{BC}(x_B,x_C)}{\sum_{x_B^{'}}\psi_{BC}(x_B^{'},x_C)} \end{aligned} \\ \begin{aligned} P(x_A\vert x_C)& =\frac{P(x_A,x_C)}{P(x_C)} =\frac{\sum_{x_B^{'}}P(x_A,x_B^{'},x_C)}{\sum_{x_A^{'}}\sum_{x_B^{'}}p(x_A^{'},x_B^{'},x_C)}\\ &=\frac{\sum_{x_B^{'}}\frac{1}{Z}\psi_{AC}(x_A,x_C)\psi_{CB}(x_C,x_B^{'})}{\sum_{x_A^{'}}\sum_{x_B^{'}}p(x_A^{'},x_B^{'},x_C)}\\ &=\frac{\psi_{AC}(x_A,x_C)}{\sum_{x_A^{'}}\psi_{AC}(x_A^{'},x_C)} \end{aligned}\]

验证得到

\[P(x_A,x_B\vert x_C)=P(x_A\vert x_C)P(x_B\vert x_C)\]

马尔可夫随机场中的条件独立性

由全局马尔可夫可以导出

局部马尔可夫性（local Markov property）：在给定邻接变量的情况下，一个变量条件独立与其他变量
- 令 V 为图的结点集， $n(v)$ 为结点 v 在图上的邻接结点， $n^{*}(v)=n(v)\cup {v}$ ，则有

\[x_v\perp x_{V\setminus n^{*}(v)}\mid x_{n(v)}\]

成对马尔可夫性（pairwise Markov property）：在给定所有其他变量的情况下，两个非邻接的变量条件独立
- 令 V 为图的结点集，V 为边集，对图中两个结点 u、v，若 $\langle u,v \rangle\notin E$ ，则有

\[x_u\perp x_v\mid x_{V\setminus\langle u,v\rangle}\]

马尔可夫随机场中的势函数

势函数的作用：定量刻画变量集中变量的相关关系，非负函数，且在所偏好的变量取值上有较大的函数值

对于上图，假定变量均为二值变量，则可以定义势函数

\[\psi_{AC}(x_A,x_C)= \left\{ \begin{aligned} 1.5\text{ , if }x_A=x_C\\ 0.1\text{ , otherwise} \end{aligned} \right.\\ \psi_{BC}(x_B,x_C)= \left\{ \begin{aligned} 0.2\text{ , if }x_B=x_C\\ 1.3\text{ , otherwise} \end{aligned} \right.\]

说明模型偏好 A 和 C 有相同的取值，B 和 C 有不同的取值，换言之，A 和 C 正相关， B 和 C 负相关。所以按照上述偏好的变量值指派将有较高的联合概率

为了满足非负性，指数函数通常被用来定义势函数

\[\psi_Q(x_Q)=e^{-H_Q(x_Q)}\\ H_Q(x_Q)=\sum\limits_{u,v\in Q,u\ne v}\alpha_{uv}x_u x_v +\sum\limits_{v\in Q}\beta_v x_v\]

其中参数 $\alpha_{uv},\beta_{v}$ 分别考虑结点对关系、单结点

条件随机场 CRF

条件随机场（conditional random field，CRF）是 判别式 的无向图模型（可看作给定观测值的 MRF），条件随机场对多个变量给定相应的 观测值 后的条件概率建模

令 $x={x_1,\dots,x_n}$ 为观测序列， $y={y_1,\dots,y_n}$ 为对应的标记序列，CRF 的目标是构建条件概率模型 $P(y\vert x)$

标记变量 y 可以是结构型变量，它各个分量之间具有某种相关性。

自然语言处理的词性标注任务中，观测数据为语句（单词序列），标记为相应的词性序列，具有线性序列结构
在语法分析任务中，输出标记是语法树，具有树形结构

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

\[P(y_v\vert x,y_{V\setminus \{v\}})=P(y_v\vert x,y_{n(v)})\]

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

CRF 使用势函数和图结构的团来定义 $P(y\vert x)$

本章节仅考虑链式条件随机场（chain-structed CRF），如下图所示

包含两种关于标记变量的团：

相邻的标记变量，即 ${y_{i-1},y_i}$
单个标记变量 ${y_i}$

条件概率可被定义为

\[p(y\vert x)=\frac{1}{Z}\exp(\sum\limits_{j}\sum\limits_{i=1}^{n-1}\lambda_{j}t_{j}(y_{i+1},y_{i},x,i) +\sum\limits_{k}\sum\limits_{i=1}^{n-1}\mu_{k}s_{k}(y_i,x,i))\]

$t_{j}(y_{i+1},x,i)$ 是定义在观测序列的两个相邻标记未知上的转移特征函数（transition feature function），用于刻画相邻标记变量之间的相关关系以及观测序列对它们的影响
$s_{k}(y_i,x,i)$ 是定义在观测序列的标记位置 i 上的状态特征函数（status feature function），用于刻画观测序列对标记变量的影响
$\lambda_j,\mu_k$ 为参数， Z 为规范化因子

CRF 特征函数举例

特征函数 通常是实值函数，以刻画数据的一些 可能成立或者期望成立 的经验特性，以词性标注任务为例

采用特征函数

\[t_j(y_{i+1},y_i,x,i)= \left\{ \begin{aligned} &1 \text{ , if } y_{i+1}=[P] \text{ } y_i=[V] \text{ and }x_i=\text{"knock"}\\ &0 \text{ , otherwise} \end{aligned} \right.\]

表示当第 i 个观测值 $x_i$ 为单词“knock”时，相应的标记 $y_i,y_{i+1}$ 可能分别为 $[V],[P]$

MRF 和 CRF 的对比

MRF 使用团上的势函数定义概率，对联合概率建模

\[\begin{aligned} P(x)=&\frac{1}{Z}\psi_{12}({x_1,x_2})\psi_{13}({x_1,x_3})\\ &\psi_{24}({x_2,x_4})\psi_{35}({x_3,x_5})\psi_{256}({x_2,x_5,x_6}) \end{aligned}\]

CRF 使用团上的势函数定义概率，有观测变量，对条件概率建模

\[p(y\vert x)=\frac{1}{Z}\exp(\sum\limits_{j}\sum\limits_{i=1}^{n-1}\lambda_{j}t_{j}(y_{i+1},y_{i},x,i) +\sum\limits_{k}\sum\limits_{i=1}^{n-1}\mu_{k}s_{k}(y_i,x,i))\]

学习与推断

基于概率图模型定义的分布，能对目标变量的 边际分布 （marginal distribution）或某些可观测变量为条件的 条件分布 进行推断

对概率图模型，还需确定具体分布的参数，称为 参数估计或学习问题 ，通常使用极大似然估计或后验概率估计求解。若将参数当作待推测的变量，则参数估计过程和推断十分相似。

假设图模型所对应的变量集 $x={x_1,\dots,x_n}$ 能分为 $x_E,x_F$ 两个不相交的变量集，推断问题的目标就是计算边际概率 $p(x_F)$ 或者条件概率 $p(x_F\vert x_E)$ ，同时，由条件概率定义得到

\[p(x_F\vert x_E)=\frac{p(x_F,x_E)}{p(x_E)} =\frac{p(x_F,x_E)}{\sum_F p(x_F,x_E)}\]

其中，联合概率 $p(x_F,x_E)$ 可基于图模型获得，关键是如何高效计算边际分布 $p(x_E)$

概率图模型的推断可以分为两类

精确推断方法
近似推断方法

精准推断

精确推断实质上是一种 动态规划 算法，利用图模型所描述的条件独立性来削减计算目标概率值所需要的计算量。变量消去是最直观的精确推断方法，是构建其他精确推断算法的基础

以计算边缘概率 $p(x_5)$ 为例

\[\begin{aligned} p(x_5) &=\sum\limits_{x_4}\sum\limits_{x_3}\sum\limits_{x_4} \sum\limits_{x_1}p(x_1)p(x_2\vert x_1)p(x_3\vert x_2) p(x_4\vert x_3)p(x_5\vert x_3)\\ &=\sum\limits_{x_3}p(x_5\vert x_3)\sum\limits_{x_4} p(x_4\vert x_3)\sum\limits_{x_2}p(x_3\vert x_2) \sum\limits_{x_1}p(x_1)p(x_2\vert x_1) \end{aligned}\]

令 $m_{12}(x_2)=\sum\limits_{x_1}p(x_1)p(x_2\vert x_1)$

$m_{ij}$ 是求加过程的中间结果，是关于 $x_j$ 的函数，下标 i 表示此项对 $x_i$ 求加，下标 j 表示此项还剩余的其他变量，

同理有 $m_{23}(x_3)=\sum\limits_{x_2}p(x_3\vert x_2)m_{12}(x_2)$

\[\begin{aligned} p(x_5) &=\sum\limits_{x_3}p(x_5\vert x_3)m_{23}(x_3) \sum\limits_{x_4}p(x_4\vert x_3)\\ &=\sum\limits_{x_3}p(x_5\vert x_3)m_{23}(x_3)m_{43}(x_3)\\ &=m_{35}(x_5) \end{aligned}\]

变量消去法实质上利用了 乘法对加法的分配律，将对多个变量的积求和问题转化为对部分变量交替进行求积和求和的问题。每次的求积和求和运算被限制在局部，从而限制了计算

信念传播

计算 多个边际分布 ，重复使用变量消去法会造成大量的冗余计算。利用信念传播（belief propagation）方法避免冗余计算

信念传播算法中，一个结点仅在接收到来自其他所有结点的消息后才能向另外一个结点发送消息，且结点的边际分布正比于它所接收的消息的乘积

\[p(x_i)\propto \prod\limits_{k\in n(i)}m_{ki}(x_i)\]

结点 $x_3$ 要向 $x_5$ 发送消息，必须先收到来自结点 $x_2,x_4$ 的消息，且传递到 $x_5$ 的消息 $x_{35}(x_5)$ 恰为概率 $P(x_5)$

若图中没有环，则信念传播算法经过两个步骤即可完成所有消息传递，进而能够计算所有变量上的边际分布

指定一个结点，从所有叶节点开始向根结点传递消息，知道根结点接收到所有邻接结点的消息
从根结点开始向叶节点传递消息，知道所有叶节点均收到消息

近似推断

精确推断方法需要很大的计算开销，在现实应用中近似推断更为常用。可分为两大类：

采样法（sampling）：通过使用随机化方法完成近似，如 MCMC 采样
变分推断（variational inference）：使用确定性近似完成推断

采样法

很多任务中，直接计算或者逼近期望比推断概率分布更容易。采样法基于这个思路，假定目标是计算函数 $f(x)$ 在概率密度函数 $p(x)$ 下的期望：

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

则可根据 $p(x)$ 抽取一组样本 ${x_1,\dots,x_N}$ ,然后计算 $f(x)$ 在样本上的均值

\[\hat{f}=\frac{1}{N}\sum\limits_{i=1}^N f(x_i)\]

如果样本独立，基于大数定律这种通过大量取样的方法就能获得较高的近似精度，问题的关键变成如何取样，即从图模型所描述的概率分布中获取样本。

马克可夫链蒙特卡洛（Markov chain Monte Carlo，MCMC）：图模型中最常用的采样技术

给定连续变量 $x\in X$ 的概率密度函数 $p(x)$ ，x 在区间 A 中的概率为：

\[P(A)=\int_A p(x)dx\]

若有函数 $f:X\mapsto\mathbb{R}$ ，可计算 $f(x)$ 的期望：

\[p(f)=\mathbb{E}_p [f(x)]=\int_x f(x)p(x)dx\]

若 x 为高维变量且服从一个复杂分布，积分操作困难。MCMC 先构造出服从 p 分布的独立同分布随机变量 $x_1,\dots,x_N$ ，再得到无偏估计：

\[\hat{p}(f)=\frac{1}{N}\sum\limits_{i=1}^{N}f(x_i)\]

判断马尔可夫链的平稳态：

假定马尔可夫链 T 的状态转移概率为 $T(x^{‘}\vert x)$ ，t 时刻状态的分布为 $p(x^t)$ ，则某个时刻马尔可夫链满足平稳条件：

\[p(x^t)T(x^{t-1}\vert x^t)=p(x^{t-1})T(x^{t}\vert x^{t-1})\]

$p(x)$ 是该马尔可夫链的平稳分布，满足该条件时，已收敛到平稳状态

综上，MCMC算法流程

构造马尔可夫链，使其收敛到平稳分布等于待估参数的后验分布
通过该马尔可夫链产生样本
使用样本进行估计

变分推断

对数似然：

\[\ln p(x\vert\Theta)=\sum\limits_{i=1}^N\ln \{\sum\limits_{z}p(x_i,z\vert\Theta)\}\]

使用 EM 算法最大化对数似然

E步：t 时刻的参数 $\Theta^t$ 对 $p(z\vert x,\Theta^t)$ 推断，并计算联合似然函数 $p(x,z\vert \Theta^t)$
M步：基于E步结果最大化寻优

\[\begin{aligned} \Theta^{t+1} &=\mathop{\arg\max}\limits_{\Theta}\mathcal{Q}(\Theta;\Theta^t)\\ &=\mathop{\arg\max}\limits_{\Theta}\sum\limits_z p(z\vert x,\Theta^t)\ln p(x,z\vert\Theta) \end{aligned}\]

机器学习——概率图模型