概率图模型

2017-07-28

从联系上讲,隐马尔可夫模型(HMM),马尔可夫随机场(MRF)和条件随机场(CRF)都是概率图模型。但是,他们之间还是有一些差异的,一方面HMM是有向图模型(贝叶斯网),而MRF和CRF是无向图模型(马尔可夫网);另一方面HMM以及MRF都是生成式模型(Generative Model),CRF是判别式模型(Generative Model)。生成式模型和判别式模型区别在于,假定所关心的变量集合为$Y$,可观测变量集合为 $O$,其他变量的集合为$R$,生成式模型考虑联合分布$P(Y,R,O)$,判别式模型考虑条件分布$P(Y,R|O)$。

HMM

Markov Chain

马尔可夫链有两个很强的假设:

系统下一刻的状态仅由当前的状态决定,不依赖以往任何状态。
任意时刻的观测只依赖于该时刻的Markov Chain的状态,与其他观测及状态无关

下图为HMM的图结构:

这样我们就可以得到所有变量的联合概率分布为:
$$P(x_1,y_1,...,x_n,y_n)=P(y_1)P(x_1|y_1)\prod_{i=2}^nP(y_i|y_{i-1})P(x_i|y_i)$$

模型定义

HMM由初始状态概率分布,状态转移概率分布,以及输出观测概率分布决定。初始状态概率分布和状态转移概率分布确定了Hidden Markov Chain,生成了不可观测的状态序列。观测概率分布确定了一个生成规则用来从状态序列产生观测序列。

Viterbi algorithm

模型应用

HMM可用来进行标注,此时的状态就是标记。标注问题是给定观测序列来预测其对应的标记序列。

MRF

CRF

Linear-chain CRF

考虑一个标注问题,$X$为观测序列,$Y$为标记序列(状态序列)。状态序列的条件概率分布$P(Y|X)$构成了条件随机场。当:
$$P(Y_i|X,Y_1,...,Y_{i-1},Y_{i+1},...,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})$$
i=1,2,...,n(在i=1和n时只考虑单边)。
则称$P(Y|X)$为线性链条件随机场。
其参数化表示为:
$$P(y|x)=\frac{1}{Z(x)}exp\left(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,j}\mu_ls_l(y_i,x,i)\right)$$
其中,
$$Z(x)=\sum_yexp\left(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,j}\mu_ls_l(y_i,x,i)\right)$$
上面公式看起来有点复杂,其实一点一点揉碎了看还是很清晰的。这里$x$是当前随机变量$X$的取值,是一个已知了的观测序列;$y$是当前随机变量$Y$的取值,是一个可能的状态序列,我们需要计算的就是这个可能的状态序列在观测序列已知的条件下的概率;$t_k$和$s_l$是特征函数,$\lambda_k$和$\mu_l$是其分别对应的权值;$k$和$l$表示特征函数的组数;$Z(x)$是规范化因子。