引子

在Transformer架构流行之前，自然语言的处理，尤其是NER（命名实体识别）等任务，通常是利用传统的序列模型处理的，比如隐马尔可夫模型、条件随机场等。实际上，这些模型的假设通常是——模型的未来状态只与当前状态有关。这类模型的发展以HMM（隐马尔可夫模型）为起始，经过MEMM（最大熵马尔可夫模型），到CRF（条件随机场）为止。这些模型在现在已经很少使用了，不过依然有着意义。本篇就来探讨一下HMM和MEMM这两个模型。CRF放在新一期讲。

马尔可夫假设

假设我们有一系列的随机状态发生的概率$P(X_t=x_k)$，其中$t$表示不同的时刻，$X_t=x_k$表示$t$时刻的随机变量取值为$x_k$，那么马尔可夫假设就是这样一个式子：
$$
P(X_t=x_k|X_1=x_{k1}, X_2=x_{k2},\cdots,X_{t-1}=x_{kt-1})=P(X_t=x_k|X_{t-1}=x_{kt-1})
$$
用语言解释，就是，下一时刻的随机状态的取值，只与当前时刻有关。

基础设定

我们还是回到自然语言这个设定上来，很多时候，我们需要对序列做标注任务，比如词性的标注、分词。这次我们就用分词任务来说明。

这次就用B和I两类字符做分词。所谓B就是一个词的开始（Beginning），也就是提示要分割的地方，在标注B的字符前面分割，而I就是表示“处在一个词的内部”（Intermediate），也就是这个字符前面无需分割，举个例子，对于“我爱吃薯片”这句话来说，如果这五个字符分别被标注为BBIBI，那么最后的切分方式就是“/我/爱吃/薯片”。

HMM：隐马尔可夫模型

分词显然是在一句话内生效的，那么我们可以把每个字符设为$C_i$，每个字符的分割方式设为$S_i$，其中，$i$表示在序列的位置（index），那么一个句子的分割方式的概率就是$P(S_1S_2\cdots S_n)$，这很好理解。如果我们认定马尔可夫假设，并且认定每个字符的分割方式与和当前字符有关，而当前字符的概率与前一个字符有关，那么我们由浅入深，先考虑前两个字符分割方式与整个句子的联合概率：
$$
P(S_1S_2C_1C_2)=P(C_1)P(S_1|C_1)P(C_2|C_1)P(S_2|C_2)
$$
前三个字符：
$$
P(S_1S_2S_3C_1C_2C_3)=P(S_1|C_1)P(C_2|C_1)P(S_2|C_2)P(C_3|C_2)P(S_3|C_3)
$$
不难看出，每多考虑一个字符，就会增加两项——$P(C_{t}|C_{t-1})$和$P(S_t|C_t)$，这两项分别是在前一个字符的影响下，当前字符的概率；以及在当前字符的影响下，当前字符的分割方式概率。那么我们就可以建模成这样一个网络：

其中，我们称字符之间的概率为转移概率，而字符到切割方式的概率为发射概率。当然，之所以HMM是“隐”马尔可夫模型，就表明，实际中，$C$不一定就是字符，可能是一些隐信息。

总而言之，HMM依靠两个极其强的假设：

当前字符的出现只与前一个字符有关。
当前字符的分割方式只与当前字符有关。

MEMM：最大熵马尔可夫模型

通过HMM不难看出，“当前字符的分割方式只与当前字符有关“这一假设未免过于强了，举例来说，”我是南京市长“和”这是南京市长江大桥“两句中，”长“字的切割方式是与上下文有关联的，所以，一个字符的分割方式不仅与当前字符有关，也与之前的字符或者标注方式有关。MEMM就是为了解决这个问题的，MEMM对条件概率进行建模：
$$
P(S_1S_2\cdots S_n|C_1C_2\cdots C_n)=\prod P(S_t|S_{t-1},C_t)
$$
如式子所示，概率的计算考虑到了序列的前一个元素的分割方式对于当前字符的分割方式影响，这个模型的结构实际上是这样的：

当然，到这里可能会有一个疑问：为什么要求”当前字符的概率“而非”当前字符生成的概率“？我们往下看。

累乘的每一项的计算方法是：
$$
P(S_t|S_{t-1},C_t)=\frac{\exp{\sum_{i} \lambda_if_i(C_t,S_t)}}{Z(S_{t-1}, C_{t})}
$$
其中，$f_i$是自设置的特征函数，数量可以自行确定，而$\lambda_i$则是参数，可以理解为权重。分母则是一个归一化的因子，因为概率的取值为$[0,1]$，所以需要一个归一化项，确保和为1。这个公式是来源于最大熵原理的，所以该模型也叫做MEMM。