一、MEMM和HMM的比较

\( \require{AMScd} \)
\[ \text{HMM} \\
\begin{CD}
q_1 @>>> q_2 @. \cdots @. q_{t-1} @>>> q_t \\
@VVV @VVV @. @VVV @VVV \\
o_1 @. o_2 @. @. o_{t-1} @. o_t
\end{CD} \\
p(Q,O)=\prod^T_{t=1}p(q_t|q_{t-1})p(o_t|q_t) \\
\quad \\
\quad \\
\text{MEMM} \\
\begin{CD}
q_1 @>>> q_2 @. \cdots @. q_{t-1} @>>> q_t \\
@AAA @AAA @. @AAA @AAA \\
o_1 @. o_2 @. @. o_{t-1} @. o_t
\end{CD} \\
p(Q|O) = \prod^T_{t=1} p(q_t | q_{t-1}, o_t) \]

1. MEMM是判别模型。

在HMM中，观测序列由隐藏状态序列生成，在序列标注任务中寻找以最大概率生成指定观测序列的隐藏状态序列,\(HMM-viterbi\)计算观测序列和隐藏序列的最大联合概率。\( \lambda \) 是模型参数。

\[ Q = \arg\max_{Q} P(Q,O | \lambda) \]

而MEMM作为判别模型直接给出目标状态序列。

\[ Q = \arg\max_{Q} P(Q | O, \lambda) \]

2. 可定义更复杂的特征

在 \( HMM-Viterbi \) 查找序列标注时当前隐藏状态和上个隐藏状态相关，假定各观测状态之间互相独立, 观测状态是生成目标，并不便于定义更多特征条件。

\[ \delta_t(j) = \max_i \delta_{t-1}(i)a_{ij} \cdot b_j(o_t) \]

在MEMM中并不要求各观测状态独立，可使用特征函数对条件\( o_t \)定义更复杂的分类特征，e.g. 大小写、上下文字符)。

\[ \delta_t(j) = \max_i \delta_{t-1}(i) P(q_t=S_j | q_{t-1} = S_i, o_t) \]

3. MEMM的\( viterbi \)算法

与\( HMM-viterbi \) 类似，定义两个函数用于保存每个步骤的最大概率和最佳前驱状态。然后从前向后递归，最后回朔状态序列。但这里和HMM不同的是改联合概率定义为条件概率。

\[ \begin{align}
\delta_t(i) & = \max_{q_1 q_2 \cdots q_{t-1}} P(q_1 q_2 \cdots q_{t-1},q_t=S_i | O_1 O_2 \cdots O_t) \\
\psi_t(i) & = \arg\max_{q_1 q_2 \cdots q_{t-1}} P(q_1 q_2 \cdots q_{t-1},q_t=S_i | O_1 O_2 \cdots O_t)
\end{align} \]

1. 第一步
   此时 \( q_0 = {\emptyset} \)，这里理解为，没有上一个隐藏状态本身就表示一种特殊状态（序列开始状态）
   \[ \begin{align}
   \delta_1(i) & = P(q_t=S_i | q_0={\emptyset}, O_1) \\
   \psi_1(i) & = {\emptyset}
   \end{align} \]
2. 递归
   \[ \begin{align}
   \delta_t(j) & = \max_i \delta_{t-1}(i)P(q_t=S_j | q_{t-1}=S_i, O_t) \\
   \psi_t(j) & = \arg\max_i \delta_{t-1}(i)P(q_t=S_j | q_{t-1}=S_i, O_t)
   \end{align} \]
3. 结束
   后续计算和回朔和HMM相同，不再叙述。

在 \( P(q_t=S_j | q_{t-1}=S_i, O_t) \) 中，工程实现时，实际传递的其实是
\( P(q_t=S_j | q_{t-1}=S_i, O, t) \) ，原因是特征函数可能需要判断 \( t \) 时刻的上下文作为特征。作为最大熵马尔可夫模型介绍，本文不考虑使用其他的概率计算方法。

五、参考资料
[1] https://en.wikipedia.org/wiki/Maximum-entropy_Markov_model
[2] McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000)
[3] Ethem Alpaydın: Introduction to Machine Learning Third Edition 15 Hidden Markov Models
[4] Daphne Koller, Nir Friedman; Probabilistic Graphical Models – Principles and Techniques
[5] 李航; 统计学习方法
[6] peghoty; http://blog.csdn.net/itplus/article/details/26550369