最大熵马尔可夫模型

Posted on

最大熵马尔可夫模型

最大熵模型是在已知经验分布的基础上求解有关特征函数\(f(\pmb{x},y)\)的最优的\(P(y|\pmb{x})\)概率分布，但它的随机变量\(y\)有相互独立性假设，所以不能很好地描述\(\pmb{x}_i, y_{i-1}\)和\(y_i\)的关系，而HMM又有观测独立性假设不能自由的选取特征。所以希望找到一个能同时服从马尔可夫性假设和服从最大熵假设的模型解决序列标注的问题。

1. 模型形式

最大熵马尔可夫模型（Maximum Entropy Markov Model，MEMM）：在给定的观察状态和前一状态的条件下，出现当前状态的概率。

对比隐马尔可夫模型HMM：
HMM模型包括状态序列\(I\)和观测序列\(O\)，状态转移概率矩阵\(A\)，观测概率矩阵\(B\)，初始概率向量\(\pi\)。HMM依赖于已知数据的概率分布，从历史经验中决定现实决策，但实际能训练的数据是少量且稀疏的，无法枚举所有的数据分布情况，所以需要在数据稀疏的条件下估计未知变量的条件概率。

最大熵马尔可夫模型MEMM：
MEMM用一个\(P(i_j | i_{j-1}, o_j)\)来替代HMM中的两个条件概率分布，即两个概率矩阵。\(P(o_j | o_{j-1}, i_j)\)表示从先前状态和当前观测值的条件下得到当前状态的概率，即根据前一状态和当前观测预测当前状态，每个分布函数\(P_{i_{j-1}}(i_j | o_j)\)都是一个服从最大熵的指数模型。

\[P_{i_{j-1}}(i_j | o_j) = \frac{1}{Z_{\bar{\lambda}}(o_j, i_{j-1})} \exp \left( \sum_q^m \lambda_a f_a (o_j, i_j) \right), \quad j=1,2,\cdots,T\]

左边为HMM模型，右边为MEMM模型，其中\(y\)表示状态，\(x\)表示观测。

  • HMM双状态转移条件概率的输出独立性假设，在训练过程中通过统计\(i_j, i_{j-1}, o_j\)的条件概率\(P(i_j| i_{j-1}), P(o_j|i_j)\)，在解码中通过联合概率反向递推\(P(i_j | i_{j-1}, o_j)\)；
  • MEMM限定条件求最优条件概率分布，在训练过程中收敛一组有关特征函数\(f_a(o_j,i_j)\)的参数向量\(\pmb{\lambda}\)，以及有关\(o_j\)和\(i_{j-1}\)的正则化因子，在解码过程中直接求得条件概率\(P(i_j | i_{j-1}, o_j)\)。

2. 优势和局限

  1. HMM因为其严格的观测独立性假设，对于具有多个相互作用的观测状态组合以及中场范围的元素依赖的数据环境识别特征的能力有限，而最大熵模型特征选择灵活，且不需要额外的独立性假设或内在约束；
  2. HMM是生成模型，学习的是联合概率，必须列举所有的观察序列的可能值，而MEMM可以在不完整信息下推导出未知数据；
  3. MEMM的本质是有向概率图模型，每个特征组合\(P(i_j, i_{j-1}, o_j)\)之间独立且做局部归一，可能存在标记偏置（label bias）的问题。

3. 标记偏置问题

MEMM只能达到局部最优解，而不能达到全局最优解，因此MEMM虽然解决了HMM输出独立性假设的问题，但却存在标记偏置问题。

改进：条件随机场