最大熵马尔可夫模型（MEMM）及其三个基本问题

最大熵马尔可夫模型的定义

最大熵马尔可夫模型（Maximum-entropy Markov model，MEMM）由Andrew McCallum，Dayne Freitag和Fernando Pereira三人于2000年提出^[1]。它结合了隐马尔可夫模型（HMM）和最大熵模型（MEM），被广泛应用于处理序列标注问题。文献[1]认为在HMM中主要存在以下两个问题：

无法用特征对观测序列参数化：在很多序列标注任务中，尤其当不能枚举所有观测序列时，通常需要用大量的特征来刻画观测序列。比如在文本中识别一个未见过的公司名字时，通常需要用到很多特征信息，如大写字母、结尾词、词性、格式、在文本中的位置等；
判别式模型比生成式模型更适合处理序列标注问题：HMM多被用在处理序列标注问题，序列标注问题的目标是求出状态相对于观测的条件概率$P(state|observation)$，而HMM是对状态和观测的联合概率$P(state,observation)$进行建模的生成式模型，相对于直接对$P(state|observation)$进行建模的判别式模型来说，显然判别式模型更适合处理序列标注问题。

为了解决以上两个问题，MEMM在HMM的基础上做了如下改进：

采用判别式模型：不对状态和观测的联合概率$P(state,observation)$进行建模，而是直接对状态相对于观测的条件概率$P(state|observation)$进行建模；
采用最大熵模型进行建模：对当前时刻的状态取值的概率用最大熵模型进行建模，因此能够实现用特征对观测序列参数化；

MEMM的具体定义如下：

设$V$是所有可能的观测的集合，$Q$是所有可能的状态的集合：

$V=\{v_1,v_2,...,v_M\},Q=\{q_1,q_2,...,q_N\}$

其中，$N$是可能的状态数，$M$是可能的观测数。
$O$是长度为$T$的观测序列，$I$是对应的状态序列：

$O=(o_1,o_2,...,o_T),I=(i_1,i_2,...,i_T)$

在已知观测序列$O$的条件下，状态序列为$I$的概率为

$\begin{aligned} P(I|O)&=P(i_1,i_2,...,i_T|O)\\ &=P(i_1|O)\prod_{t=2}^TP(i_t|i_{t-1},O)\\ &=P(i_1|O)\prod_{t=2}^T\cfrac{\exp\left(\sum_{k=1}^K w_kf_k(i_t,i_{t-1},O)\right)}{\sum\limits_{i_t}\exp\left(\sum_{k=1}^K w_kf_k(i_t,i_{t-1},O)\right)}\\ &=P(i_1|O)\prod_{t=2}^T\cfrac{1}{Z(i_{t-1},O)}\exp\left(\sum_{k=1}^K w_kf_k(i_t,i_{t-1},O)\right)\\ \end{aligned}$

其中，$Z(i_{t-1},O)=\sum\limits_{i_t}\exp\left(\sum_{k=1}^K w_kf_k(i_t,i_{t-1},O)\right),f_k(i_t,i_{t-1},O),w_k$分别对应于最大熵模型中的归一化因子，特征函数和特征函数的权重。若在$i_1$前添加一个恒为常量0的状态$i_0=0$，则上式可化简为

$\begin{aligned} P(I|O)&=P(i_0=0,i_1,i_2,...,i_T|O)\\ &=\prod_{t=1}^TP(i_t|i_{t-1},O)\\ &=\prod_{t=1}^T\cfrac{1}{Z(i_{t-1},O)}\exp\left(\sum_{k=1}^K w_kf_k(i_t,i_{t-1},O)\right)\\ \end{aligned}$

最大熵马尔可夫模型的三个基本问题

概率计算问题：在给定模型参数$w_k(k=1,2,…,K)$、观测序列$O=(o_1,o_2,…,o_T)$和状态序列$I=(i_1,i_2,…,i_T)$的条件下，计算条件概率$P(I|O)$；
学习问题：在给定观测序列$O=(o_1,o_2,…,o_T)$和状态序列$I=(i_1,i_2,…,i_T)$的条件下，估计模型参数$w_k(k=1,2,…,K)$，使得条件概率$P(I|O)$达到最大；
预测问题：也称为解码问题，已知模型参数$w_k(k=1,2,…,K)$和观测序列$O=(o_1,o_2,…,o_T)$，求条件概率$P(I\vert O)$达到最大的状态序列$I=(i_1,i_2,…,i_T)$，即给定观测序列，求最有可能的对应状态序列。

概率计算问题

由于MEMM属于判别式模型，而对于判别式模型来说，给定了模型参数$w_k(k=1,2,…,K)$和观测序列$O=(o_1,o_2,…,o_T)$，直接套用模型的定义即可计算出条件概率$P(I|O)$。

学习问题

既有观测序列$O=(o_1,o_2,…,o_T)$也有状态序列$I=(i_1,i_2,…,i_T)$时：此时MEMM类似于最大熵模型，所以能用于估计最大熵模型参数的策略和算法均可用于MEMM；
只有观测序列$O=(o_1,o_2,…,o_T)$而没有状态序列$I=(i_1,i_2,…,i_T)$时：此时MEMM是一个含有隐变量的模型，对于含有隐变量的模型，则可以使用EM算法对其进行参数估计。

预测问题

HMM中用于解决预测问题的维特比（Viterbi）算法在MEMM中同样适用，具体算法如下：
定义在时刻$t$状态为$q_i$的所有单个路径$(i_1,i_2,…,i_t)$中概率最大值为

$\delta_t(i)=\max\limits_{i_1,i_2,..,i_{t-1}}P(i_1,...,i_{t-1},i_t=q_i|O),\quad i=1,2,...,N$

由此定义可推得

$\begin{aligned} \delta_1(i)&=P(i_1=q_i|i_0=0,O) \\ \delta_2(i)&=\max\limits_{1\leq j\leq N}[\delta_1(j)\cdot P(i_2=q_i|i_1=q_j,O)] \\ \delta_3(i)&=\max\limits_{1\leq j\leq N}[\delta_2(j)\cdot P(i_3=q_i|i_2=q_j,O)] \\ \end{aligned}$

依次此类推可得如下递推公式

$\delta_{t}(i)=\max\limits_{1\leq j\leq N}[\delta_{t-1}(j)\cdot P(i_t=q_i|i_{t-1}=q_j,O)]$

同样再定义在时刻$t$状态为$q_i$的所有单个路径$(i_1,i_2,…,i_t)$中概率最大的路径的第$t-1$个结点为

$\psi_t(i)=\arg\max\limits_{1\leq j\leq N}[\delta_{t-1}(j)\cdot P(i_t=q_i|i_{t-1}=q_j,O)]$

因此，取$i_T^*=\arg\max\limits_{i}[\delta_T(i)]$，则$i_{T-1}^*=\psi_T(i_T^*),i_{T-2}^*=\psi_{T-1}(i_{T-1}^*),…,i_1^*=\psi_2(i_2^*)$。由于MEMM模型本身的问题，用维特比算法求出来的最优序列$I^*=(i_1^*,i_2^*,…,i_T^*)$并不是真正意义上的最优状态序列，下面举例说明：
假设已知的观测序列为$O=(o_1,o_2,o_3,o_4)$，所有可能的状态的集合为$Q=\{1,2,3,4,5\}$，各个时刻之间的状态转移概率如下图所示

由维特比算法易算得最优状态序列$I^*=(1,1,1,1)$，但是结合解码问题的实际情形可知，显然状态序列$\tilde{I}=(1,2,2,2)$相对来说比$I^*$更加合理，因为$\tilde{I}$每个时刻之间的状态转移都比$I^*$更加自信，例如从时刻1到时刻2，$I^*$是选择转移到自己最不自信的下一个状态（0.4 < 0.6），而$\tilde{I}$则是选择转移到自己最自信的那个状态（0.6 > 0.4），同理可知，在时刻2到时刻3和时刻3到时刻4时都是同样的情形。因此，$I^*$一定不是真正意义上的最优状态序列，此即为MEMM的标注偏置问题（The Label Bias Problem）^[2]。导致标注偏置的主要原因是MEMM对各个时刻的状态取值的概率$P(i_t|i_{t-1},o_t)$进行了局部归一化，也即

$\begin{aligned} \sum_{i_t}P(i_t|i_{t-1},O)&=\sum_{i_t}\cfrac{1}{Z(i_{t-1},O)}\exp\left(\sum_{k=1}^K w_kf_k(i_t,i_{t-1},O)\right) \\ &=\sum_{i_t}\cfrac{1}{\sum\limits_{i_t}\exp\left(\sum_{k=1}^K w_kf_k(i_t,i_{t-1},O)\right)}\exp\left(\sum_{k=1}^K w_kf_k(i_t,i_{t-1},O)\right) \\ &=1 \end{aligned}$

所以对于那些可转移状态少的状态来说，它转移到下一个状态的概率通常都会比那些可转移状态多的状态转到下一个状态的概率要高。比如上图中的状态1可以转移到状态1/2，状态2可以转移到状态1/2/3/4/5，那么状态1可转移的状态就比状态2可转移的状态要少，所以从状态1转移到状态1/2的单个概率通常都会比从状态2转移到状态1/2/3/4/5的单个概率要高。显然这是不符合实际情形的，因为我们并不要求每个状态的可转移状态个数相等，所以对于每个状态来说，只要它们是以同等自信程度转移到下一个状态，那么它们的转移概率就应该相等。比如上图中的时刻3到时刻4时，状态1转移到状态1/2的自信程度相等（0.5=0.5），同样状态2转移到状态1/2/3/4/5的自信程度也相等（0.2=0.2=0.2=0.2=0.2），那么它们的转移概率理应都是相等的，显然进行局部归一化后它们的转移概率是不相等的，所以只需取消局部归一化或者换成全局归一化即可解决标注偏置问题。

参考文献

[1] Mccallum A, Freitag D, Pereira F. Maximum Entropy Markov Models for Information Extraction and Segmentation[J]. Icml, 2000.
[2] Lafferty J, Mccallum A, Pereira F C N. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data[J]. Proceedings of Icml, 2001.