Shihanmax's blog
概率图模型
概率图模型总览
定义1 概率图模型 概率图模型是由图表示的概率分布，假设有联合概率分布$P(Y)$，$Y \in \mathcal{Y}$是一组随机变量，由图$G=(V,E)$表示概率分布$P(Y)$，节点$v\in V$表示一个随机变量$Y_v$，边$e \in E$表示随机变量之间的概率依赖关系。下图是常见概率图模型的分类：
从图中看出，贝叶斯网络都是有向的，而马尔科夫网络都是无向的，本文重点回顾一下常用的隐马尔可夫模型（HMM）和条件随机场（CRF）。隐马尔可夫模型属于动态贝叶斯网络的一种，而条件随机场则是一种马尔科夫网络。
HMM
有向图模型适合于描述节点间具有单向依赖的场景，无向图模型的节点间是互相依赖的，没有方向性。二者的区别在于整个图的联合概率的表示：
对于有向图，则概率可以表示为：
\[P(x_{1}, \cdots, x_{n})=P(x_{1}) \cdot P(x_{2} \mid x_{1}) \cdot P(x_{3} \mid x_{2}) \cdot P(x_{4} \mid x_{2}) \cdot P(x_{5} \mid x_{3}, x_{4})\]
隐马尔可夫模型是一种有向图模型，它是关于时序的概率模型，描述一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测，进而组成一个观测序列的过程。其中不可观测的状态随机序列，称为状态序列（state sequence）；由状态序列生成的随机序列，称为观测序列（observation sequence）。
定义2 隐马尔可夫模型（Hidden Markov Models, HMM）
定义状态集合$Q={q_1,q_2,…,q_N}$；观测集合$V={v_1,v_2,…,v_M}$，其中$N$是所有的状态个数，$M$是所有可能的观测数。
定义$I$为长度为$T$的状态序列：$I=(i_1,i_2,…,i_T)$，$O$为对应的观测序列：$O=(o_1,o_2,…,o_T)$。
定义$A$为状态转移矩阵：
\[A=[ a_{ ij } ]_{N\times N}\]其中$a_{ij}$表示在$t$时刻状态为$q_i$时，$t+1$时刻转移到状态$q_j$的概率。
定义$B$为观测概率矩阵：$B=[b_j(k)]_{N\times M}$，其中$b_j(k)$表示在$t$时刻由状态$q_j$生成观测$v_k$的概率。
定义$\pi$为初始状态概率向量：$\pi = (\pi_i)$，其中$\pi_i$表示在$t=1$时刻处于状态$q_i$的概率。
隐马尔可夫模型$\lambda$可由其参数集${ A,B,\pi }$表示：$\lambda={A,B,\pi}$。
由上述定义可知，HMM引入了两个假设：
（1）齐次马尔科夫假设：任意时刻$t$的状态只依赖其前一时刻的状态，与其他时刻、观测无关，与$t$也无关。
（2）观测独立假设：任意时刻的观测仅依赖于当前时刻的马尔可夫链的状态，与其他状态、观测均无关。
隐马尔可夫模型有三个基本问题：
（1）概率计算问题。给定$\lambda={A,B,\pi}$和观测序列$O$，计算概率$P(O\mid \lambda)$
使用前向-后向算法递推计算。
（2）参数学习问题。已知观测序列$O$，估计模型的参数$\lambda={A,B,\pi}$
采用极大似然估计的方法来进行参数估计，实践中，使用Baum-Welch算法（EM算法在HMM上的实现）
（3）预测问题（解码问题）。已知模型$\lambda={A,B,\pi}$和观测序列$O$，求给定观测序列时最有可能的状态序列$I$
采用维特比算法求解最优路径（最优状态序列）。
CRF
首先介绍概率无向图模型，设有联合概率分布$P(Y)$，由无向图$G=(V,E)$表示，如果联合概率分布$P(Y)$满足成对、局部或全局马尔可夫性，则称此联合概率分布为概率无向图模型（probabilistic undirected graphical model），或称马尔可夫随机场（Markov random field, MRF）。
对于概率无向图，可以将整个网络划分为若干个最大团，原图的联合概率可以描述为若干个团的联合概率之积（由Hammersly-Clifford $^1$定理保证）：
\[P(Y)=\frac{1}{Z(x)} \prod_{c} \Psi_{c}(Y_{c})\]其中，$Z(x)$是归一化项$Z=\sum_{Y} \prod_{C} \Psi_{C}(Y_{C})$，$\psi_{C}(Y_C)$是最大团$C$所包含的随机变量的联合概率，这个函数称为势函数（为了保证概率非负，势函数必须是非负的）。
以下图为例，其联合概率分布可以描述为：
\[P(Y)=\frac{1}{Z(x)}(\Psi_{1}(X_{1}, X_{3}, X_{4}) \cdot \Psi_{2}(X_{2}, X_{3}, X_{4}))\]
定义3 马尔可夫随机场
假设有随机变量$X$，$Y$，$P(Y\mid X)$是给定随机变量$X$的条件下，随机变量$Y$的马尔可夫随机场。
定义4 条件随机场
一般地，设$X$和$Y$是随机变量，$P(Y \mid X)$是在给定$X$的条件下，$Y$的概率分布。若随机变量$Y$构成一个由无向图$G=(V,E)$表示的马尔可夫随机场，即：$P(Y_{v} \mid X, Y_{w}, w \neq v )=P(Y_{v} \mid X, Y_{w}, w \sim v )$对任意节点v成立，则称条件概率分布$P(Y \mid X)$为条件随机场（conditional random field），其中 $w \sim v$表示在图$G$中所有与节点$v$有边连接的节点$w$，$w \neq v$表示节点$v$以外的所有节点，$Y_*$表示节点$*$对应的随机变量。
定义5 线性链条件随机场
设$X$和$Y$均为线性链表示的随机变量序列，若在给定$X$的条件下，随机变量$Y$的条件概率分布$P(Y\mid X)$构成条件随机场，且满足马尔可夫性：
\[P(Y_{i} \mid X, Y_{1}, \cdots, Y_{i-1}, Y_{i+1}, \cdots, Y_{n})=P(Y_{i} \mid X, Y_{i-1}, Y_{i+1})\]其中$i=1,2,…,n$，则称$P(Y\mid X)$为线性链条件随机场。在标注问题中，$X$表示输入观测，$Y$表示标记序列。
设$\theta= { \theta_{k} } \in \Re^{K}$为参数向量，
\[\mathcal{T}= \{ t_{k} (y, y', \mathbf{x}_{t} ) \}_{k=1}^{K}\] \[\mathcal{S}= \{s_{l} (y, \mathbf{x}_{t} ) \}_{l=1}^{L}\]分别为定义在边上和定义在节点上的实值特征函数集合，则线性链条件随机场的条件概率有如下形式：
\[P(y \mid x)=\frac{1}{Z(x)} \exp (\sum_{i, k} \lambda_{k} t_{k}(y_{i-1}, y_{i}, x, i)+\sum_{i, l} \mu_{l} s_{l}(y_{i}, x, i))\]其中，$Z(x)$为归一化项：$Z(x)=\sum_{y} \exp (\sum_{l, k} \lambda_{k} t_{k}(y_{i-1}, y_{i}, x, i)+\sum_{i, l} \mu_{l} s_{l}(y_{i}, x, i))$
在上式中，$t_k$依赖当前位置的标记和前一个位置的标记、以及当前位置的观测；$s_l$依赖当前位置的观测和当前位置的标记，$\lambda_k$和$\mu_l$分别为两种特征函数的权重，也即CRF中需要学习的参数，将整个序列中所有的节点及每个节点对应的所有的特征函数值加权求和并归一化之后，便可得到当前标记序列的概率分数。
与隐马尔可夫模型类似，线性链条件随机场也有三个基本问题：
（1）概率计算：给定条件随机场$P(Y\mid X)$，输入序列$x$和标记序列$y$，求条件概率$P(Y_i=y_i\mid x)$，$P(Y_{i-1}=y_{i-1},Y_i=y_i\mid x)$及相应的数学期望问题，采用前向后向算法。
（2）参数估计（学习算法）：从有标注数据中学习条件随机场模型的参数，即每一个特征函数的权重$\theta$
（3）模型推断：在已知条件随机场参数$\theta$时，给定观测序列$X$，求解最有可能的标记序列$Y$，使用维特比算法。
常见的“两种”CRF
在序列标注实践中，我们经常接触到两种结构看似不同的CRF：
“标准”CRF 第一种以CRF++为代表，CRF++是一个CRF求解工具包，其使用方式与上述标准CRF的建模流程相同，我们这里暂且称其为“标准CRF”，其训练和测试流程如下：
训练阶段：首先需要定义一批特征模板，根据模板，生成一些特征函数，然后使用SGD、BFGS等优化算法求得最优的特征函数的权重；
测试阶段：在最优的特征函数权重上，使用维特比算法等求解最优标记序列。
RNN+CRF中的CRF 第二种CRF一般出现在RNN+CRF序列标注模型中，在这类模型中，加入CRF模块的目的是，希望能够通过加入CRF模块，引入标签之间的一阶马尔可夫依赖，使得在模型训练中，避免出现非正常标签转移的情况。
此种CRF模块，接收一个$S \times L$的发射矩阵，其中$S$为序列长度，$L$为标签个数，模块内部包含三个矩阵：
- 标签起始概率：标记每个标签出现在序列开头的概率，$1\times L$
- 标签结束概率：标记每个标签出现在序列结尾的概率，$1\times L$
- 标签转移概率：标记标签之间的转移概率，$L \times L$
这三个概率矩阵即是CRF模块需要训练的参数。
这个模块具有如下能力：
- 给定发射矩阵（emission），计算该发射矩阵在当前概率矩阵分布下的路径分数（训练时，最大化该分数能够起到同时训练RNN+CRF参数的目的）
- 给定发射矩阵（emission），求解对应的最优解码路径
在原始的RNN序列标注模型中，每个RNN时间步上的输出，通过投影到标签空间后，直接通过softmax等方式求得最优的标签，加入CRF模块之后，相当于通过三个概率矩阵对序列标签路径进行约束，同时，这种约束也能在训练中影响下层RNN的参数训练。在测试阶段，三个概率矩阵在训练数据上调整至最优，RNN输出的发射矩阵通过CRF进行维特比解码。
这里RNN后层接的并非完整的CRF，因为它不需要特征模板，也不接受离散特征，从结构上看，它其实更像一个HMM，拥有概率转移矩阵和初始概率矩阵（但区别在于，它的观测集不是离散的）。这里能够称为CRF的原因是，在“标准CRF”建模中，存在两类特征函数：
- 边函数（定义在边上，描述$t$时间步上观测与当前标签、上一时间步标签之间的关系），负责计算转移分数
- 点函数（定义在节点上，描述$t$时间步上观测与标签的关系），负责计算状态分数
“标准CRF”需要手动抽取序列的特征，在RNN+CRF中，RNN起到了对序列抽取特征的作用，可以将RNN理解为一组点函数的集合，其输出的发射矩阵即是$L$种标签的状态分数分布；而边函数则需要CRF模块通过概率矩阵的形式进行建模，所以CRF模块中的概率矩阵只是定义边函数的一种“特征”而已。
回顾上文，CRF的条件概率建模为：
\[P(y \mid x)=\frac{1}{Z(x)} \exp (\sum_{i, k} \lambda_{k} t_{k}(y_{i-1}, y_{i}, x, i)+\sum_{i, l} \mu_{l} s_{l}(y_{i}, x, i))\]在RNN+CRF中，认为RNN模型作为一组点特征抽取器（$s_l$）的建模能力是足够强大的，这种情况下，我们甚至可以忽略边特征函数中观测$x$对标签$y_i$的影响，这时边特征函数重写为$t_{k}(y_{i-1}, y_{i}, i)$，这一步简化带来的好处是，在进行边特征函数建模时，其状态空间则是一个有限的参数矩阵（对应CRF模块中的起始、终止、转移概率矩阵）。
另外，RNN的每个时间步的信息是相对独立的，而后接一层CRF状态控制则能够对全局的输出标签作出最优决策。RNN接上CRF模块，相当于将$S$个$L$分类问题转化为一个$L^S$分类问题，也即，我们要从$L^S$条路径中选择一条最优路径。
待续
后续，会继续讨论其他形式的概率图模型，及相关概念间的区别和联系，如最大熵隐马尔可夫模型（MEMM）、High-order CRFs和simi-CRFs，NB（朴素贝叶斯模型）和HMM、LR和CRF、HMM和CRF、随机过程与马尔可夫过程等。