概率图模型：HMM，MEMM，CRF

HMM（Hidden Markov Moel）是一个有向图模型，为简化求解多随机变量的联合概率分布，做了两个假设：齐次马尔科夫假设和观测独立假设。这两个假设都具有局限性。MEMM（Maximum Entropy Markov Model）舍弃了HMM的观测独立假设，使用了所有上下文的观测值。因此具有更强的表达能力。同时使用最大熵模型对条件概率建模。每个条件概率在局部进行了归一化，这又带来了“label bias”问题。CRF去除了HMM的另一个假设“齐次马尔科夫假设”，使用全局归一化计算联合概率，避免了局部归一化带来的“label bias”的问题。

1 HMM

隐马尔科夫做的两个假设：

齐次马尔科夫假设：当前隐状态的值只受前一隐状态的影响。
观测独立假设：当前的观测值，只与当前时刻的隐状态有关，与其他时刻的隐状态和其他观测变量无关。

概率图模型：HMM，MEMM，CRF

这两个假设都是有局限性的。例如再做词性标注时，当前的词性不仅与当前词有关，与观测的上下文都是有关系的（观测独立假设不合理）。于是引入了最大熵马尔科夫模型（MEMM）。它去除了HMM的观测独立假设，每一时刻的隐状态考虑了整个观测序列，因此表达能力更强。

2 MEMM

MEMM是判别式模型，每一时刻是给定所有观测序列X和上一时刻隐状态下的条件概率分布。并且使用最大熵模型对条件概率建模，所以叫做最大熵马尔科夫模型。MEMM的联合概率分布计算方式：
$p(o_1o_2..o_n|x_1x_2...x_n)=\prod_{i=1}^np(o_i|o_{i-1},x_1x_2...x_n)$
概率图模型：HMM，MEMM，CRF

其中 $p(o_i|o_{i-1},x_1x_2...x_n)$ 会在局部进行归一化，即枚举可能oi的条件概率后求和计算概率。如下：
$p(o_i|o_{i-1},x_1x_2...x_n)=\frac{exp(F(o_i,o_{i-1},x_1x_2...x_n))}{\sum_{o_i}exp(F(o_i,o_{i-1},x_1x_2...x_n))}$
局部归一化会带来“label bias”问题。概率在候选值较多时候分散出去，更少时更加集中，导致选择最优路径时，模型偏向选择候选取值较少的。

3 CRF

CRF在MEMM的基础上进一步去除了HMM的齐次马尔科夫假设。对概率进行全局归一化，从而避免了局部归一化带来的“label bias”问题。

为什么去除齐次马尔科夫假设可避免局部归一化。类似于语言模型对一句话概率建模。为简化问题，也做了马尔科夫假设。二元语言模型就是做了一阶马尔科夫假设。
$p(y_1y_2...y_n|X)\simeq p(y_1|X)p(y_2|y_1,X)...p(y_n|y_{n-1},X)\tag{1}$
正是因为做了马尔科夫假设，将联合概率简化成了每个时刻只依赖上一时刻的条件概率。而这个条件概率计算需要局部归一化。去除马尔科夫假设也就不需要对每一时刻的条件概率建模了。

概率图模型：HMM，MEMM，CRF

联合概率计算：
$p(o_i|o_{i-1},x_1x_2...x_n)=\frac{1}{Z(x_1x_2...x_n)}\prod_{i=1}^nexp(F(o_i,o_{i-1},x_1x_2...x_n))$
可以看到是在全局进行了归一化。

4 演进过程与对比

HMM,MEMM,CRF的演进用下图来解释。

概率图模型：HMM，MEMM，CRF

对比：

	建模对象	图类型	学习算法	预测算法	存在问题
HMM	联合概率，生成式模型	有向图	1.极大似然估计 2.Baum-Welch(前向-后向)	viterbi	强假设导致的局限性
MEMM	条件概率，判别式模型	有向图	1.极大似然估计2.梯度下降3.牛顿迭代	viterbi	label bias
CRF	条件概率，判别式模型	无向图	1.极大似然估计2.梯度下降	viterbi	考虑的信息多，模型复杂。全局归一化的归一化因子可能性过多（指数级别），计算困难

概率计算公式和训练过程不易放入表格，下面对比

HMM：

概率计算与训练过程：

为便于理解，把上面的概率图都复制下来了

概率图模型：HMM，MEMM，CRF

概率计算：
$\mathop{max}p(o_1o_2...o_n|x_1x_2...x_n)\simeq p(o_1)p(x_1|o1)\prod_{i=2}^np(o_i|o_{i-1})p(x_i|o_i)$
训练过程：

HMM的训练过程就是估计模型参数 $\pi,A,B$ 的过程，一般用极大似然估计或者Baum-Welch（前向后向）。

MEMM:

概率图模型：HMM，MEMM，CRF
概率计算：
$p(o_1o_2...o_n|x_1x_2...x_n)\simeq\prod_{i=1}^mp(o_i|o_{i-1},x_1x_2...x_n)$
每个条件概率都用最大熵模型建模，即：
$p(o_1o_2...o_n|x_1x_2...x_n)\simeq\prod_{i=1}^mp(o_i|o_{i-1},x_1x_2...x_n)\\=\prod_{i=1}^m\frac{\mathop{exp}F(o_i,o_{i-1},x_1x_2...x_n)}{\sum_{o_i}\mathop{exp}F(o_i,o_{i-1},x_1x_2...x_n)}$
训练过程：

1.预先定义一系列特征函数。

2.模型参数是各特征函数的系数（参见最大熵模型）。由训练确定模型参数，从而得到确定的模型。

3.用特定的模型对联合概率计算。概率最大的隐状态序列作为输出

CRF

概率图模型：HMM，MEMM，CRF
$p(o_1o_2...o_n|x_1x_2...x_n)=\frac{exp\sum_{i=1}F(o_1,o_2,x_1x_2...x_n)}{\sum_{o_1o_2o_n}exp\sum_{i=1}F(o_1,o_2,x_1x_2...x_n}\\=\frac{1}{Z(X)}exp\sum_{i=1}F(o_1,o_2,x_1x_2...x_n)$
训练过程：

1.预先定义一系列特征函数。

2.模型参数是各特征函数的系数（参见最大熵模型）。由训练确定模型参数，从而得到确定的模型。

3.用特定的模型对联合概率计算。概率最大的隐状态序列作为输出

CRF训练过程基本与MEMM一致，都是预先定义特征函数。只是MEMM在计算概率时局部归一化，CRF全局归一化。

概率图模型：HMM，MEMM，CRF

1 HMM

2 MEMM

3 CRF

4 演进过程与对比

相关推荐