NLP——HMM模型与计算实例

因为个人时间的关系，从这学期入学开始，我们换一种新的更新方式。开始主要以专题文章为主，系列文章为辅。在专题文章中，我们不会具体写出每一个内容的来龙去脉，但是我们依然会注重文章中的细节和文字的打磨。希望新的形式也能够让大家喜欢。

这一部分摘自我这学期在电子工程与计算机（Electrical Engineering and Computer Science, EECS）所修的自然语言处理（Natural Language Processing, NLP）的课程的课堂笔记。所关注的内容是自然语言处理中的隐马尔可夫模型（Hidden Markov Model，HMM）。

那么我们开始吧。

隐马尔可夫模型的前身：马尔可夫模型

如果你是统计系的出身，那么你应该修过随机过程这一门课。随机过程的一开始我们就有提到过马尔可夫链这么一个概念。具体可以看一下这一篇文章：

随机过程（1）——引入，有限状态马尔科夫链，状态转移，常返与瞬时状态本节

但为了与下面的隐马尔可夫模型相对应，我们这里可能要稍微修改一下我们的标记。

我们会给出这么一些记号

时间：

t = {1, 2, ldots, T}

状态：

Q = {1, 2, ldots, N}

，代表有

个状态事件：

O = {o_1, o_2, ldots, o_N}

，代表每个状态对应的观测（observation）初始概率：

pi_j = P(q_1 = j)

转移概率矩阵：

a_{ij} = P(q_t = j mid q_{t - 1} = i), 1 le i,j le N

如果用人话来描述这一串记号的话，大体意思就是：在一条马尔可夫链中，一个状态经过一个时间之后，会转移到另外一个状态。且在一开始，每一个状态有一个初始概率，并且状态的概率转移服从转移概率矩阵。

这里我们给出一张图作为例子。

在这张图中，我们可以给出它的初始概率和转移概率矩阵。

{pi} = begin{bmatrix}0.5 \ 0.2 \ 0.3end{bmatrix}

mathbf A = begin{bmatrix}0.6 & 0.2 & 0.2 \ 0.5 & 0.3 & 0.2 \ 0.4 & 0.1 & 0.5end{bmatrix}

以矩阵左上角的那个元素

0.6

为例，这就代表，从事件

到事件

的转移概率为

0.6

。也就是说，如果站在现在的位置来看，事件是

，那么下一个时间点事件依然是

的概率就是

0.6

。当然"事件是

"可以有很多种解读，例如原文中，指的就是股票的涨跌。

因为本文重点关注的是HMM模型和它的计算举例，因此关于马尔可夫模型相关的内容，我们不多赘述。感兴趣的朋友可以阅读上面贴的那些文章。

隐马尔可夫模型引入

很多人可能第一反应就是隐马尔可夫模型（HMM）到底“隐”在了哪里。为了解释这一点，我们直接给出HMM的一些记号。

时间：

t = {1, 2, ldots, T}

状态：

Q = {1, 2, ldots, N}

，代表有

个状态事件：

O = {1, 2, ldots, M}

，代表每个状态对应的观测（observation）初始概率：

pi_j = P(q_1 = j)

转移概率矩阵：

a_{ij} = P(q_t = j mid q_{t - 1} = i), 1 le i,j le N

观测概率矩阵：

b_j(k) = P(o_t = k mid q_t = j), 1 le k le M

这里有两个变动，一个是状态的含义变了，一个就是最后的观测概率矩阵（Observation Probabilities，也有的地方会把它叫作Emission Probabilities）。在这里我们要强调的点是，在隐马尔可夫模型中，事件和状态是不同的意思（对比上面的马尔可夫模型，其实事件和状态是一个意思）。换句话说，对于隐马尔可夫模型，每一个事件下可能会对应一个状态的发生概率，而且根据事件值的不同，对应的状态的发生概率就会不同。但是事实上，在隐马尔可夫模型中，我们关心的是事件的具体观测值，但是状态的具体值是未知的。状态会通过观测概率矩阵影响事件，但是同一个时间点的事件与状态的概率才能互相影响（条件独立），并且我们无法追踪状态的具体观测值。这就是“隐”的含义。

听起来还是有点抽象的，我们之后会给一个具体的例子。之后的计算我们也会使用这个例子。

隐马尔可夫模型的三大类问题

隐马尔可夫模型有三大类问题。但在这里我们只介绍两个，因为最后一个是需要使用EM算法的，但是在NLP的背景下暂时还用不上，所以我们这里就不多提了。

评判问题

关于评判（Evaluation）问题，一般定义为如下

Definition 1: Evaluation 给定观测序列

O = (o_1o_2ldots o_r)

和模型

Phi = (A, B, pi)

，如何高效计算

P(O | Phi)

？

这里相当于是说，在给定这个模型的情况下，得到对应观测的条件概率为多少。

对于这个问题，一个考虑是通过全概率公式，把

的信息引入进来。所以我们可以把公式写成

P(O | Phi) = sum_{Q}P(O, Q|Phi) = sum_Q P(Q |Phi) P(O | Q, Phi)

第二步这么写自然是使用的条件概率公式，同样也是因为我们有转移概率矩阵和观测概率矩阵，因此后面的值就都可以计算了。具体的公式写在下面

P(O | Q, Phi) = b_{q_1}(o_1)b_{q_2}(o_2)ldots b_{q_T}(o_T)

P(Q | Phi) = pi_{q_1} a_{q_1q_2}ldots a_{q_{T - 1}q_T}

这里的

a, b

对应的分别是转移概率矩阵和观测概率矩阵的元素。一个是每一步的观测概率的乘积，一个是不断地状态转移而得到的概率的乘积（当然这个也是因为有马尔可夫性，不过如果不需要学随机过程，这个结论就直接记忆就好）。

有了这个公式，我们的计算就不困难了，但是要注意的是我们考虑的是高效的算法。而这个题中，一个转移状态序列

{q_1, ldots, q_T}

的取值有非常多的可能。每一个状态可以取

个值，然后一共有

个状态，这样对应的取法就有

O(N^T)

个。这不是一个多项式时间复杂度，所以并不是一个合适的计算方式。因此我们需要引入其它的方法。

这个方法就是向前法（Forward Algorithm）。具体的计算方法如下

计算

alpha_1(i) = pi_i b_i (o_1), 1 le i le N

计算

alpha_{i 1 }(j) = [sum_{i = 1}^N alpha_t (i) a_{ij}]b_j(o_{t 1}), 1 le t le T - 1, 1 le j le N

计算

P(O | Phi) = sum_{i = 1}^N alpha_T(i)

第一点和第三点其实不难理解。第一点就是简单的状态向事件的转移，第三点则是全概率公式。一个序列的最终概率，当然等于不同状态下，这个事件发生的概率和。就像天气是晴天，有可能是气压低情况下的天气是晴天，有可能是气压高情况下的，这些概率都要加上。

但是第二点是怎么推导出来的呢？这很明显是根据上一个时间点的结果所计算出来的。具体可以写出这样的公式。

alpha_{t 1}(i) = P(o_1, o_2, ldots, o_{t 1}, q_{t 1} = i)

= sum_{j = 1}^N P(o_1, o_2, ldots, o_{t 1}, q_t = j, q_{t 1} = i)

=sum_{j = 1}^N P(o_{t 1}, q_{t 1} = i | o_1, o_2 ,ldots, o_t, q_t = j)P(o_1, o_2, ldots, o_t , q_t = j)

= sum_{j = 1}^N P(o_{t 1}|q_{t 1} = i) P(q_{t 1} = i | q_t = j) alpha_t(j) = sum_{j = 1}^Nb_i(o_{t 1})a_{ji}alpha_t (j)

最后一个式子其实就是最终的结果。这个推导过程还是有几步跳步的，我们希望读者自己理解这个过程每一步都用了什么样的信息。另外要注意的是，因为这里所有的状态都未知，所以所有的

o_i

都是没有赋值的。注意区分标记。

有了计算结果之后，我们还可以得到下面这两个结果。

P(o_1o_2ldots o_T) = sum_{i = 1}^N alpha_T(i)

P(q_T = i | o_1o_2 ldots o_T) = frac {alpha_T(i)}{sum_{i = 1}^N alpha_T(i)}

第一个式子其实也就是

P(O | Phi)

。

Example 1: 考虑如下一个天气预报模型，计算序列

{s, r, r, s, r}

发生的概率。

通过这张图我们可以知道，这里状态之间有一个转移概率矩阵和一个初始概率

mathbf A = begin{bmatrix} 0.3, 0.4, 0.3 \ 0.4, 0.5, 0.1 \ 0.4, 0.1, 0.5end{bmatrix}

pi = begin{bmatrix}0.5 \ 0.2 \ 0.3end{bmatrix}

其中状态顺序为

[M, H, L]

，分别对应的是median, high, low。这里指的就是大气压。

另外，我们也给出这个题的观测概率矩阵

mathbf b = begin{bmatrix}0.5 & 0.75 & 0.25 \ 0.5 & 0.25 & 0.75end{bmatrix}

其中事件顺序为

{s, r}

，其中

表示sun，

表示rain。比方说左上角的

0.5

，含义就是“在气压为median的情况下，天气为sun的概率为

0.5

”。所以可以看出来，这里我们的状态就是大气压的级别，而事件就是是否下雨，具体状态是观测不到的，但是有对应的状态与事件之间的条件概率。

要解决这一道题，自然的点还是要考虑这个序列所对应的

alpha

。首先我们考虑

t = 1

的情况。这个时候，计算公式就是

alpha_1 (M) = 0.5 times 0.5 = 0.25

alpha_1(H) = 0.2 times 0.75 = 0.15

alpha_1 (L) = 0.3 times 0.25 = 0.075

注意这里乘的系数

[0.5, 0.75, 0.25]

就是事件在

情况下的概率，因为我们第一个事件是

。

下面开始计算

t = 2

，这里可以得到结果是

alpha_2(M) = (0.25 times 0.3 0.15 times 0.4 0.075 times 0.4) times 0.5 = 0.0825

alpha_2(H) = (0.25 times 0.4 0.15 times 0.5 0.075 times 0.1) times 0.25 = 0.0456

alpha_2(L) = (0.25 times 0.3 0.15 times 0.1 0.075 times 0.5) times 0.75 = 0.0956

事实上这里可以把括号里的部分写成一个矩阵相乘的形式。

alpha_2 = A^Talpha_1

然后再与之后的向量

[0.5, 0.25, 0.75]

做一个按位相乘（简单来说就是按照

[a_1, a_2] otimes [b_1, b_2] = [a_1b_1, a_2b_2]

的规则来相乘）。注意这个向量对应的其实是事件为

的情况，因为序列的第二个元素是

。

类似的，可以计算出

t = 3, 4, 5

的情况。这里就直接给出结果了。

alpha_3 = begin{bmatrix}0.0406, 0.0163, 0.0578end{bmatrix}

alpha_4 = begin{bmatrix}0.0209, 0.0226, 0.0107end{bmatrix}

alpha_5 = begin{bmatrix}0.0098, 0.0052, 0.0104end{bmatrix}

其中状态的顺序是

[M, H, L]

。当然，对于

alpha_5

我们直接把向量求和，就可以得到最终的答案

0.0254

。

解码问题

解码问题（Decoding）的概念是这样的

Definition 2: Decoding 给定观测序列

O = (o_1o_2ldots o_r)

和模型

Phi = (A, B, pi)

，如何选取

Q = (q_1, q_2, ldots, q_T)

，可以使得

P(Q, O| Phi)

最大化。

如果写的具体一点，这个问题就是

v_t(i) = max_{q_1, q_2, ldots, q_{t - 1}} P(q_1q_2ldots q_{t-1}, q_t = i, o_1o_2ldots o_t|Phi)

也就是固定了最后一步为

之后的计算公式。

这就是在寻找一个最大可能的观测序列所对应的隐藏状态。至于为什么要叫解码问题，这个我们留到后面再解释。

计算这个

的方法一般是维特比（Viterbi）算法。具体的计算步骤是这样的。

计算

v_1(i) = pi_i b_i (o_1)

计算

v_t(j) = (max_i v_{t - 1}(i) a_{ij})b_j (o_t)

换句话说，这也是一个逐步迭代的过程。当然了，在介绍例子之前，我们还是先介绍一下，为什么是这个计算公式。事实上，通过

v_2(i)

的计算我们就能够看出端倪。

v_2(i) = max_{q_1}P(q_1 = k, q_2 = i, o_1o_2 | Phi)

= max_{q_1}(v_1(k) P(q_2 = i| q_1 = k, o_1, Phi) P(o_2 | q_2 = i, q_1 = k, o_1, Phi))

= max_{q_1}(v_1(k) P(q_2 = i| q_1 = k, Phi) P(o_2 | q_2 = i, o_1, Phi))

= max_{k}v_1(k) a_{ki}b_i(o_2)

注意倒数第二行使用了之前提到的隐马尔可夫模型的条件独立性。

其实我们可以看出来的一点是，这个计算公式其实和之前没有本质的差别。无非就是把求和换成了取最值。但是要注意的是，这里因为每一个值都要取最大值，所以我们不能够使用上面那种矩阵计算的方式。

好的，我们举个例子。

Example 2: 考虑相同的天气预报模型，计算事件序列

{s, r, r, s, r}

对应的概率最大的状态序列

。

我们计算一下，首先很容易我们有

v_1(M) = 0.5 times 0.5 = 0.25

v_1(H) = 0.2 times 0.75 = 0.15

v_1(L) = 0.3 times 0.25 = 0.075

这里的向量为什么是

[0.5, 0.75, 0.25]

，你只要看懂上一个题就明白了。

然后我们考虑

t = 2

的情况，这个时候对应的结果是

v_2(M) = max(0.25 times 0.3 , 0.15 times 0.4, 0.075 times 0.4) times 0.5 = 0.0375

v_2(H) = max(0.25 times 0.4, 0.15 times 0.5, 0.075 times 0.1) times 0.25 = 0.0250

v_2(L) = max(0.25 times 0.3, 0.15 times 0.1, 0.075 times 0.5) times 0.75 = 0.0563

这个数和上面的求和对应的数相同。

类似的，可以求出

t = 3, 4, 5

的情况，这就对应为

v_3 = begin{bmatrix}0.0113, 0.0038, 0.0211end{bmatrix}

v_4 = [0.0042, 0.0034, 0.0026]

v_5 = [0.0007, 0.0004, 0.0010]

所以可以看出来，实际上对应的概率最高的五个状态为

[M, L, L, L, L]

，这分别对应了求解出来的

v_i

中数值最高的那个维度对应的状态。

最后来简单计算一下时间复杂度，在这个时间复杂度上，每一个时间和状态下，都会对应一个计算

max_i v_{t - 1}(i) a_{ij}b_j(o_t)

，它的时间复杂度为

O(N)

。枚举时间和状态再相乘，就可以得到最终的结果为

O(N^2T)

。这里的

就是时间步数。

学习问题

学习（Learning）问题是隐马尔可夫模型要解决的第三类问题，我们会介绍它的概念，但在这里我们不介绍具体的方法。

Definition 3: Learning 如何调整

Phi = (A, B, pi)

，使得

P(O | Phi)

可以被最大化。

HMM在NLP中的应用

在NLP中，HMM也有它自己的一个应用，这个就是HMM标签器（tagger）。简单介绍一下它的背景，就是在自然语言处理中，有的时候词语的词性会造成非常大的影响，因此我们需要对每一个词语的词性做一个预测。比方说同一个英语单词可能是名词也可能是动词，那么知道具体词性的话很明显就会对词语的预测提供很大的帮助。

这里具体来说的话，我们希望给定一个序列

W = {w_1, w_2, ldots, w_n}

，我们希望预测出最好的

T = t_1, t_2, ldots, t_n

，这里每一个

t_i

对应的就是预测的

w_i

的词性。换句话说，就是希望计算

argmax_{t_1, ldots, t_n} P(t_1, ldots, t_n mid w_1, ldots, w_n)

利用贝叶斯公式，我们有

P(t_1, ldots, t_n mid w_1, ldots, w_n) = frac {P(w_1 ,ldots, w_n | t_1, ldots, t_n ) P(t_1 ,ldots, t_n)}{P(w_1, ldots ,w_n)}

那么因为分母是与

t_i

无关的，所以可以不管。所以实际上只需关心分子。但是如果要使用上面的隐马尔可夫模型，我们必然是需要一些假设的。具体来说就是

P(w_1, ldots, w_n mid t_1,ldots,t_n) simeq prod_{i = 1}^n P(w_i mid t_i)

P(t_1, ldots, t_n) simeq prod_{ i =1}^n P(t_i mid t_{i- 1})

第一个就是隐马尔可夫模型中的条件独立假设，第二个其实是NLP中的n-gram假设。简单来说，就是预测词语的时候，究竟使用某一个词语前面的几个位置。比方说如果是bigram，那么相当于使用句子的连续两个词作为训练数据，也就是只考虑相邻一个词的影响。当然了，你也可以考虑trigram等等，但是对应的训练数据量就会成指数的上升。

为了不那么抽象，我们举个例子。

Example 3: 考虑下面两个句子

Secretariat/NNP is/VBZ expected/VBN to/TO race/? tomorrow
People/NNS continue/VBP to/TO inquire/VB the/DT reason/NN for/IN the/DT race/? for outer space

问单词race更有可能是名词（NN）还是动词（VB）？

这里的大写字母（诸如NNP，VBZ）都是词性。

这里使用的是bigram的假设，因此我们可以把问题简化成计算

P(VB|TO)P(race|VB)

P(NN|TO)P(race|NN)

这里因为我们只考虑给一个词标记词性，所以不存在乘积符号。而计算这两个值其实就对应了两部分的内容，第一部分是词性与词性之间的转移概率矩阵，这个可以通过Penn Treebank数据库来计算出来。第二部分要从数据中学习到，本质上是观测概率矩阵。

最后简单提一下时间复杂度。我们之前计算过时间复杂度为

O(N^2 T)

，但是如果

很大的话，说明每一层的状态很多。这个情况下，如果选取所有的状态也不一定能得到想要的结果，因此常见的方案就是使用Beam Search，简单来说就是每一次只考虑一部分可能的结果，而直接对其他的结果进行剪枝。具体可以看下图。

好的，关于这一部分内容，我们就说这么多。

小结

本节主要介绍了隐马尔可夫模型的具体应用，理解和计算实例，并简单的介绍了一个它在NLP中的一个应用例子。虽然当今情况下它已经不如深度学习那么高效，但是这依然是一个非常重要和值得学习的机器学习算法，也是概率图模型的基础了属于是。

NLP服务

0 人点赞

NLP——HMM模型与计算实例

目录

隐马尔可夫模型的前身：马尔可夫模型

隐马尔可夫模型引入

隐马尔可夫模型的三大类问题

评判问题

解码问题

学习问题

HMM在NLP中的应用

小结