引言

文章根据udacity自然语言处理进行整理，提供给初学者进行参考。主要围绕隐马尔可夫的基本实现原理和维特比算法进行介绍。

相关参考学习视频：

udacity--自然语言处理（PS：国外导师视频课程，中文字幕。课程简洁易懂、生动形象。具有项目实战、导师项目审核特色。比较推荐入门。点击此处可获得课程优惠券）

1. 概述

在自然语言中，一个句子通常是由多个词组成、包含形容词、名词、动词等等。如下面的这个句子：Mary had a little lamb 。如何找出每个词对应的词性是问题的重点。这里将探讨如何使用隐马尔可夫模型进行词性标注。

隐马尔可夫模型还用于语音识别和语音生成、机器翻译、生物信息学基因识别和计算机视觉人类手势识别，等等。

2. 隐马尔可夫模型

介绍马尔可夫模型的基本原理。

假设标记句子 “Jane will spot Will ” 的方式是名词、情态动词、动词、名词。

需要计算两种概率，一是转移概率，即名词后面是情态动词、情态动词后面是动词、动词后面是名词的概率；另一种是发射概率，即 N 名词是Jane、情态动词是 will 等等的概率。如下图

发射概率的计算

如下图的一些句子，可以看作是语料。每个句子做了标注。

发射概率的计算，如果单词是n(名词) ，那该单词是 Mary 或 Jane 的概率。为此，可先创建一个这样的表格，如下图所示。N、M、V 分别表示词性。其中 Mary 在语料句子中作为 N 出现了 4次。

之后将每列除以条目之和，获得这些数字。如此就计算出了相应的发射概率。注意单词可以重复出现，例如 will 即是名词又是情态动词。

转移概率的计算

首先需要给每个句子添加一个开始和结束的标签。当然这些标签也可以作为词性。现在创建计数表，计算每个词性出现的次数。如下图的 3 ，表示名词N 后面出现的情态动词 M 的次数为 3 次。

为了计算概率，需要将每行中的条目除以行中条目的和。如下图情态动词动词M之后是名词N的概率为 1/4； M情态动词之后是动词V的概率为 3/4 。这个就是转移概率。

最后一步就是将转移概率和发射概率合并。形成马尔可夫模型。如下图所示

根据上图的马尔可夫模型。来看具体的实现原理。从 <S> 开始， <S> 到 N 的概率为 ，即转移概率为 3/4 。当 Jane 为 N 名词时概率为 2/9 ，即发射概率 2/9 。

再从 N 转移到 M 的，转移概率为1/3 ，生成 Will 的发射概率为 3/4 。然后再到 V ，最后后到 <E> 结束。如此计算，便得到了一条句子的所有概率。

之后将所有概率进行相乘。得到了这个句子的概率为 0.0003858 。这个值可能比较小，但考虑到可以生成大量长度不等的句子，该值已经很大了。

通常做法是从所有可能的词性组合中选择生成概率最高的句子。如在下面的两个句子中，生成的句子一样，但词性不同 ，导致概率也不一样。选择最大概率的组合作为最终的句子。

路径裁剪

如果从所有可能的词性组合中选择生成概率最高的句子。假如有这样的一个句子： Jane will spot Will  和 对应的三种词性 N、M、V。找出所有可能的词性组合。这里得到的词性组合就等于 3 的4次方，即 81 种。这呈现一种指数计算，如果句子越长，那句子组合数量也将越大。最终是需要找到概率最大的路径，如果有 81 种路径组合，意味着需要计算 81 次。这会影响计算效率到此需要使用 维特比算法来减少计算量。

在使用维特比算法之前，先进行裁剪。我们计算概率是将所有的发射概率和转移概率相乘，但如果路径中有0 值，则可不用计算，因为 0 乘以任何数都为 0 。 如下图中的概率值：

（备注： 下图中仅对 Jane will spot Will 做了发射概率的标示，即 Jane 是 N 名词的概率为 2/9 。对照发射概率表为 2/9 。）

到此删除发射概率和转移概率中只要有 0 出现的路径。现在可得到如下图的模型。到此裁剪后的路径为 4 条。

将4条路径上的概率相乘，得到的结果进行比较。可得到概率最大的路径，也就是最后需要的路径。

维特比算法

在上面使用路径裁剪的方式，将 81 种词性组合路径删减为 4 种。还有一种算法，只查看两个路径并合并他们。

如下图，在 N 这个点上。有两种路径可以到达。可分别计算两种路径的概率，可发现左边的路径比右边的路径概率小很多。因此将忽略左边的路径，而采用右边的路径。这是维特比算法的基本思想。

来看维特比算法的具体实现。再利用上图中使用的  Jane will spot Will 句子和 N、M、V 词性。

根据发射概率表和转移概率表。从 <S> 到 N 的转移概率为 3/4 。 对应的 Jane 是 N 的概率为 2/9 。同样的 <S> 到 M 的转移概率为 1/4 ，Jane 是 N 的概率为 0 。<S> 到 V 的转移概率为 0 ，Jane 是 V 的概率为 0 。

因此生成节点的概率是 发射概率 * 转移概率。即 <S> 到 N 的转移概率和 Jane 是N的发射概率 ：  (3/4) * (2/9) = 1/6 。同理计算  <S> 到 M 的转移概率和 Jane 是M的发射概率分别为 0 。

再转到下个单词 will ，有三个路径指向 N、即转移概率分别是 1/9、1/4 和 1。同时 will 是 N 的发射概率为 1/9 。如此再计算三个路径上概率值，保留最大的概率值。似乎 1/6 * 1/9 * 1/9 是最大值。

同样的方式计算M和V，并保留最大的概率值。重复的方式进行，知道句子末尾。如此可得到如下的结果，忽略0的路径

如何找到最佳路径，可从后往前追踪。即 <E> -> N -> V -> M -> M -> N -> <S> 这便是最佳路径。

3. 相关文献

语音和语言处理图书的隐马尔可夫模型和词性标注。

4. 项目实现

在 notebook 中，使用 Pomegranate 库构建隐马尔可夫模型，并使用通用标签集进行词性标注。在使用更大型的标签集对实际文本语料库进行标注时，隐马尔可夫模型的准确率达到了 96% 以上。隐马尔可夫模型还用于语音识别和语音生成、机器翻译、生物信息学基因识别和计算机视觉人类手势识别，等等。

项目可访问此 github ，使用 jupyter notebook 打开。