引言

上一节介绍了隐马尔可夫模型(Hidden Markov Model,HMM)向最大熵马尔可夫模型(Maximum Entropy Markov Model,MEMM)的演化过程。本节将针对MEMM模型的缺陷，并介绍 条件随机场(Condition Random Field,CRF)。

回顾：最大熵马尔可夫模型

最大熵马尔可夫模型的 观测状态$\mathcal{O}$ 可分为全局影响(Global)和局部影响(Local)两种：

• 全局影响意味着 将所有观测变量$o_1,\cdots ,o_T$视为一个结点。对应概率图描述如下：
  
  对应建模对象$\mathcal{P}(\mathcal{I}\mid \mathcal{O};\lambda )$表示如下：
  $$\mathcal{P}(\mathcal{I}\mid \mathcal{O};\lambda )=\mathcal{P}(i_1\mid \mathcal{O};\lambda )\cdot \prod _{t=2}^T\mathcal{P}(i_t\mid i_{t-1},\mathcal{O};\lambda )$$
• 局部影响意味着 各时刻的观测变量$o_t$与对应时刻的隐变量$i_t$进行关联，但各时刻的观测变量独立性被打破。对应概率图描述如下：
  
  对应建模对象$\mathcal{P}(\mathcal{I}\mid \mathcal{O};\lambda )$表示如下：
  $$\begin{array}{rl}\mathcal{P}(\mathcal{I}\mid \mathcal{O};\lambda )& =\mathcal{P}(i_1,\cdots ,i_T\mid o_1,\cdots ,o_T;\lambda )\\ & =\mathcal{P}(i_1\mid o_1;\lambda )\cdot \prod _{t=2}^T\mathcal{P}(i_t\mid i_{t-1},o_t;\lambda )\end{array}$$

最大熵马尔可夫模型的优点

和隐马尔可夫模型相比，最大熵马尔可夫模型的优点体现在两个方面：

• 最大熵马尔可夫模型是 概率判别模型，在解码任务(Decoding)中，相比于隐马尔可夫模型，使用更少的计算量对最优隐状态序列进行求解：
  $$\begin{array}{rl}\hat{\mathcal{I}}& =\underset{\mathcal{I}}{\mathrm{argmax}}\mathcal{P}(\mathcal{I}\mid \mathcal{O};\lambda )\\ & =\underset{i_1}{\mathrm{argmax}}\mathcal{P}(i_1\mid \mathcal{O};\lambda )\cdot \prod _{t=2}^T\underset{i_t}{\mathrm{argmax}}\mathcal{P}(i_t\mid i_{t-1},\mathcal{O};\lambda )\end{array}$$
  相比之下，马尔可夫模型使用维特比算法(Viterbi)使用联合概率分布的迭代方式求解最优状态序列：
  $$\begin{array}{rl}{\delta }_t(k)& =\underset{i_1,\cdots ,i_{t-1}}{\max }\mathcal{P}(o_1,\cdots ,o_t,i_1,\cdots ,i_{t-1},i_t=q_k;\lambda )\\ {\delta }_{t+1}(j)& =\underset{i_1,\cdots ,i_t}{\max }\mathcal{P}(o_1,\cdots ,o_{t+1},i_1,\cdots ,i_t,i_{t+1}=q_j;\lambda )\\ {\delta }_{t+1}(j)& ={\delta }_t(k)\cdot a_{kj}\cdot b_j(o_{t+1})\end{array}$$
  但是，含隐变量联合概率分布的计算代价要明显高于条件概率的计算。
• 最大熵马尔可夫模型打破了观测独立性假设，它使得观测变量间存在关联关系，相比观测独立性假设在序列标注任务(解码任务)中更加合理。

最大熵马尔可夫模型的缺陷

MEMM的缺陷是：造成标注偏置问题(Label Bias Problem)的出现。

标注偏置问题

如果使用一句话描述该问题：在状态转移的过程中，条件概率分布的熵值越低，那么状态转移过程越忽视观测变量。

本来是通过观测变量的差异性 来描述隐变量的条件概率结果；但如果熵值过低，导致观测变量的差异性几乎没有对条件概率结果产生影响，最终使状态转移结果与给定观测结果不匹配。

标注偏置问题示例

假设存在如下词语数据集：
D = { ′ r o b ′ , ′ r o b ′ , ′ r o b ′ , ′ r i b ′ } \mathcal D = \{'rob','rob','rob','rib'\} D={′rob′,′rob′,′rob′,′rib′}

• 正常情况下，学习过程中 概率图结构表示如下：
  这个MEMM概率图结构并不严谨，详细见下面红字。
  
  在学习过程(Learning)中，从初始状态$i_1$经过第一次观测进行状态转移，最终得到状态$i_2$。状态$i_2$的条件概率结果表示如下：
  由于四个单词的‘首字母’均相同，均为$r$。因此，无论是哪个样本，第一次观测的结果均是同一结果。
  $$\mathcal{P}(i_2\mid i_1,o_2=r)=\frac{4}{4}=1$$
  以此类推，在状态$i_2$的条件下，经过第二次观测，状态转移至$i_3,i_4$的条件概率结果分别表示如下：
  四个样本在第二次观测中，$o$占了三个，$i$占了一个，根据概率的频率定义，其状态转移的条件概率取决于当前时刻观测变量出现的频率。
  $$\begin{array}{r}\mathcal{P}(i_3\mid i_2,o_3=i)=\frac{1}{4}\\ \mathcal{P}(i_4\mid i_2,o_4=o)=\frac{3}{4}\end{array}$$
  最终的第三次观测，所有样本点的观测结果均是$b$。因此有：
  $$\mathcal{P}(i_5\mid i_3,o_5=b)=\mathcal{P}(i_5\mid i_4,o_5=b)=1$$
  上述状态转移过程中，条件概率结果与观测变量的差异性之间存在密切关系。在解码任务(Decoding)中，假设给定 观测序列：$rib$，对应的$\mathcal{P}(\mathcal{I}\mid \mathcal{O};\lambda )$表示如下：
  真正的开始是从$i_2$,而$i_3,i_4$并不是两个独立的隐变量，而是同一个隐变量在不同概率下的转移结果。这里为了表述方便，将其分成两个部分。但在公式表达中需要将其合并。
  $\mathcal{P}(i_4\mid i_2,o_4=i)=0$恒成立。因为$o_4$选择不了$i$。
  $$\begin{array}{rl}\hat{\mathcal{I}}& =\underset{\mathcal{I}}{\mathrm{argmax}}\mathcal{P}(\mathcal{I}\mid \mathcal{O}=rib;\lambda )\\ & =\underset{\mathcal{I}}{\mathrm{argmax}}\mathcal{P}(i_2,i_3,i_4,i_5\mid \mathcal{O}=rib)\\ & =\underset{i_2}{\mathrm{argmax}}\mathcal{P}(i_2\mid i_1,o_2=r)\cdot \underset{i_3,i_4}{\mathrm{argmax}}\left[\mathcal{P}(i_3\mid i_2,o_3=i),\mathcal{P}(i_4\mid i_2,o_4=i)\right]\cdot \underset{i_5}{\mathrm{argmax}}\left[\mathcal{P}(i_5\mid i_3,o_5=b),\mathcal{P}(i_5\mid i_4,o_5=b)\right]\\ & =\mathcal{P}(i_2\mid i_1,o_2)\cdot \mathcal{P}(i_3\mid i_2,o_3)\cdot \mathcal{P}(i_5\mid i_3,o_5)\end{array}$$
  至此，找到最优路径 I ^ = { i 1 , i 2 , i 3 , i 5 } \hat {\mathcal I} = \{i_1,i_2,i_3,i_5\} I^={i1​,i2​,i3​,i5​}
• 基于相同的数据集合，学习过程将概率图结构修改成如下形式：
  
  该图和上图正常情况之间的区别在于：该图是从路径的角度进行划分，而上图是从时刻的角度进行划分。
  在学习过程中，初始状态$i_0$在第一次观测后进行状态转移，分别转移至$i_1,i_2$的条件概率表示如下：
  不同于正常情况，此时$i_0$存在两条路径，虽然观测结果全部是$r$,但从路径的角度观察，存在$\frac{3}{4}$概率是样本$rob$中的$r$,而仅有$\frac{1}{4}$概率是样本$rib$中的$r$。
  $$\begin{array}{r}\mathcal{P}(i_2\mid i_0,o_2=r)=\frac{3}{4}\\ \mathcal{P}(i_1\mid i_0,o_1=r)=\frac{1}{4}\end{array}$$
  核心步骤：无论是$i_1$还是$i_2$，它均只存在唯一一条路径，$i_1\to i_3,i_2\to i_4$，没有其他选择。这样会导致在该时刻的观测变量无论是什么，都不影响其唯一路径的选择。也就是说，此时的观测变量并不对状态转移过程产生影响：
  在路径被确定的条件下，$i_1$的概率分布(出度)只有一种选择。
  $$\begin{gathered} \mathcal{P}(i_3\mid i_1,o_3=i)=\mathcal{P}(i_3\mid i_1)=1 \\ \mathcal{P}(i_4\mid i_2,o_4=o)=\mathcal{P}(i_4\mid i_2)=1 \end{gathered}$$
  同理，后续结点由于路径的确定同样也被确定，对应结果如下：
  相比于上一步骤的影响差了很多，因为无论哪条路径，其最后的观测结果都是$b$
  $$\begin{gathered} \mathcal{P}(i_5\mid i_3,o_5=b)=\mathcal{P}(i_5\mid i_3)=1 \\ \mathcal{P}(i_5\mid i_4,o_5=b)=\mathcal{P}(i_5\mid i_4)=1 \end{gathered}$$
  如果此时给定观测序列：$rib$，再次观察最优路径：
  $$\begin{array}{rl}\hat{\mathcal{I}}& =\underset{\mathcal{I}}{\mathrm{argmax}}\mathcal{P}(\mathcal{I}\mid \mathcal{O}=rib;\lambda )\\ & =\underset{\mathcal{I}}{\mathrm{argmax}}\left[\mathcal{P}(i_2\mid i_0,o_2=r)\cdot \mathcal{P}(i_4\mid i_2,o_4=o)\cdot \mathcal{P}(i_5\mid i_4,o_5=b)\right],\\ & \left[\mathcal{P}(i_1\mid i_0,o_1=r)\cdot \mathcal{P}(i_3\mid i_1,o_3=i)\cdot \mathcal{P}(i_5\mid i_3,o_5=b)\right]\\ & =\mathcal{P}(i_2\mid i_0,o_2=r)\cdot \mathcal{P}(i_4\mid i_2,o_4=o)\cdot \mathcal{P}(i_5\mid i_4,o_5=b)\end{array}$$
  最优路径 I ^ = { i 0 , i 2 , i 4 , i 5 } \hat {\mathcal I}= \{i_0,i_2,i_4,i_5\} I^={i0​,i2​,i4​,i5​}，但这个最优路径描述的观测序列是 $rob$，与给定序列不符合。

从熵的角度观察观测变量存在差异性的部分：

• 正常情况下：
  $$\frac{3}{4}\log \frac{4}{3}+\frac{1}{4}\log 4\approx 0.5623$$
• 标注偏置现象：
  $$0\log 0+1\log 1=0.0$$

标注偏置现象使得观测变量存在差异的部分熵更小，在最大熵思想一节中熵值小意味着概率分布相差较大，距离“等可能”的效果越远，此时状态转移过程概率分布可能已经内定给概率结果大的隐状态，而当前时刻的观测值作用很小，甚至没有作用。

下一节将介绍条件随机场。

相关参考：
机器学习-条件随机场（3）-MEMM VS CRF