HMM与序列标注 Algorithm

隐马尔可夫模型（Hidden Markov Model，HMM）是一种统计模型，它用来描述一个含有隐含未知参数(隐状态)的马尔可夫过程。其难点是从可观察的参数中(显状态)确定该过程的隐含参数(隐状态)，然后利用这些参数来作进一步的分析。
举一个经典的例子：一个东京的朋友每天根据天气{下雨，天晴}决定当天的活动{公园散步,购物,清理房间}中的一种，我每天只能在twitter上看到她发的推特，我前天公园散步、昨天购物、今天清理房间了！”，那么我可以根据她发的推特推断东京这三天的天气。在这个例子里，显状态是活动，隐状态是天气。
HMM怎么描述：
任何一个HMM都可以通过下列五元组来描述：

:param obs:观测序列 :param states:隐状态 :param start_p:初始概率（隐状态） :param trans_p:转移概率（隐状态） :param emit_p: 发射概率（隐状态表现为显状态的概率）

上面的例子可以用如下的HMM来描述：

states = ('Rainy', 'Sunny') #隐状态 observations = ('walk', 'shop', 'clean') #观测 start_probability = {'Rainy': 0.6, 'Sunny': 0.4} #初始概率 transition_probability = { 'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3}, 'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6}, } #转换概率 emission_probability = { 'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5}, 'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},} #发射概率

其中隐状态之间的转移概率：

文章图片

根据出现的活动求解最可能的天气：
1、定义V[时间][今天天气] = 概率，注意今天天气指的是，前几天的天气都确定下来了（概率最大）今天天气是X的概率，这里的概率通过转换概率计算得出。
2、因为第一天我的朋友去散步了，所以第一天下雨的概率V[第一天][下雨] = 初始概率[下雨] * 发射概率[下雨][散步] = 0.6 * 0.1 = 0.06，同理可得V[第一天][天晴] = 0.24 。从直觉上来看，因为第一天朋友出门了，她一般喜欢在天晴的时候散步，所以第一天天晴的概率比较大，数字与直觉统一了。
3、从第二天开始，对于每种天气Y，都有前一天天气是X的概率 * X转移到Y的概率 * Y天气下朋友进行这天这种活动的概率。因为前一天天气X有两种可能，所以Y的概率有两个，选取其中较大一个作为V[第二天][天气Y]的概率，同时将今天的天气加入到结果序列中
4、比较V[最后一天][下雨]和[最后一天][天晴]的概率，找出较大的哪一个对应的序列，就是最终结果。
通常，我们会面对一个较大的序列和较大规模的数据，这时候使用上面的方法每一种可能的序列都计算一次的话，代价是相当大的。这时候，就需要使用一种动态规划算法：Viterbi算法，来解码这个序列了。

HMM模型在NLP方向上得到了较为深入的应用，特别是序列标注方面，其中分词、词性标注、命名实体识别都属于这一类。
由于中文分词是中文NLP中即基础又相较与英文比较特殊的一个问题，下面以中文分词为例来介绍HMM在NLP的序列标注中的应用。
中文分词是将中文自然语言文本划分成词语序列，目前主流方法为序列标注，即用BMES这个四个标签去标注句子中的每一个字(B是词首，M是词中，E是词尾，S是单字词)。
如下面这段话：
小明硕士毕业于中国科学院计算所
采用BMES标签来标注的话：

文章图片

分词结果即为：
小明硕士毕业于中国科学院计算所
那这个问题套用HMM来建模的话，”小明硕士毕业于中国科学院计算所
”这句话的每个字都看做一个HMM模型中的显状态，” BEBEBMEBEBMEBME”则看作一个隐状态序列。
相比于上面估算天气的这个例子，我们似乎还缺几个参数：

start_probability transition_probability emission_probability

【HMM与序列标注】没错，这些参数我们现在还是不知道的。那怎么办呢，这个时候就需要去人工标注一些语料来训练出这几个参数了。有一些公开的语料库可供我们来使用，比如人民日报中文分词语料库，其标注形式为：

文章图片

一共三列，第一列是字第二列是词性第三列是BMES标签，下面就使用这个预料来训练

start_probability transition_probability emission_probability

这三个参数，说是训练，其实主要还是对已标注的数据进行统计。我根据人民日报语料库训练得到的参数如下：

文章图片

现在我们已知了

observations start_probability transition_probability emission_probability

这些参数，剩下的就是调用Viterbi算法来估算隐状态序列states了。Viterbi算法的实现可以参考这个github。如观测状态"小明硕士毕业于中国科学院计算所",估算得到的隐状态即为"BEBEBMEBEBMEBME"，这样子差不多中文分词即完成一大部分了，后续还可以基于HMM模型来估测各个观测状态的词性。

至此，使用HMM模型来进行中文序列标注的一个基本思想和过程差不多也介绍完毕了。当然，像HMM、CRF这些来进行序列标注的方案已经做的非常成熟了，目前学术界开始尝试使用RNN来解决序列标注的问题。