数学之美梳理（三）隐马尔可夫模型

隐马尔可夫模型是一个并不复杂的数学模型，到现在为止，他一直被认为是解决大多数自然语言处理问题最快速，有效的方法。它成功地解决了复杂地语音识别，机器翻译等问题。

通信模型

通信的本质就是一个编解码和传输的过程。但是自然语言处理前期的努力都集中在语法，语义和知识表述上，离通信的原理越走越远，这样离答案也越来越远。

当自然语言处理的问题回归到通信系统地解码问题时，许多难题就迎刃而解了。

按照雅各布森提出的通信6要素，一个典型的通信系统包括：发送者，信道，接收者，信息，上下文和编码。

假设$s_1, s_2, s_3, \ldots$ 表示发送者发出的信号，$o_1, o_2, o_3, \ldots$ 表示接收者收到的信号。那么通信中的解码就是根据接受的信号还原出发送的信号。

在某些领域，这个逻辑比较清晰，比如发送者用高电平表示1，低电平表示0，接收者再按照这个规则还原就好。

但如果放到语音识别，机器翻译等领域，这个逻辑就没这么直接了，因为它的规则并不是完备和收敛的，试图通过找到语音中的规则，又会走回研究语法的老路。

那么在语音识别领域，我们如何理解通信模型的应用呢？

我们不妨换一个角度，所谓的语音识别，就是听着去猜测说话者要表达的意思。这其实就像通信中，接收端根据收到的信号去分析，理解，还原发送端传过来的信息。根据声学信号来推测说话者的意思，就是语音识别。如果接收端是一台计算机，那么就要做语音的自动识别。

那么我们应该怎么做呢？只需要从所有的源信息中找到最可能产生出观测信号的那一个信息就好。

用概率的语言来说，就是在已知$o_1, o_2, o_3, \ldots$ 的情况下，求得令概率$P(s_1, s_2, s_3, \ldots | o_1, o_2, o_3, \ldots)$ 达到最大值的那个信息串，即

$$s_1, s_2, s_3,\ldots = ArgMax_{all s_1, s_2, s_3, \ldots} P(s_1, s_2, s_3, \ldots | o_1, o_2, o_3, \ldots)$$

上面的概率不容易直接求出来，不过可以间接地计算它，利用贝叶斯公式可以把上述公式等价变换成：

$$\frac{P(o_1,o_2,o_3,\ldots | s_1, s_2, s_3 \ldots) \cdot P(s_1, s_2, s_3, \ldots)}{P(o_1,o_2,o_3,\ldots)}$$

其中$P(o_1,o_2,o_3,\ldots | s_1, s_2, s_3 \ldots)$ 表示信息$s_1, s_2, s_3 \ldots$ 在传输后变成$o_1,o_2,o_3,\ldots$ 的可能性，而$P(s_1, s_2, s_3 \ldots)$ 表示$s_1, s_2, s_3 \ldots$ 本身是一个在接收端合乎情理的信号的可能性，最后$P(s_1, s_2, s_3, \ldots)$ 表示在发送端产生信息$s_1, s_2, s_3, \ldots$ 的可能性。

贝叶斯定理（英语：Bayes’ theorem）是概率论中的一个定理，描述在已知一些条件下，某事件的发生概率。比如，如果已知某种健康问题与寿命有关，使用贝叶斯定理则可以通过得知某人年龄，来更加准确地计算出某人有某种健康问题的概率。

通常，事件A在事件B已发生的条件下发生的概率，与事件B在事件A已发生的条件下发生的概率是不一样的。然而，这两者是有确定的关系的，贝叶斯定理就是这种关系的陈述。贝叶斯公式的一个用途，即透过已知的三个概率而推出第四个概率。贝叶斯定理跟随机变量的条件概率以及边际概率分布有关。

作为一个普遍的原理，贝叶斯定理对于所有概率的解释是有效的。这一定理的主要应用为贝叶斯推断，是推论统计学中的一种推断法。这一定理名称来自于托马斯·贝叶斯。

用公式来表示贝叶斯原理：

$P(A | B) = \frac{P (B | A) \cdot P(A)}{P(B)}$

在贝叶斯定理中，每个名词都有约定俗成的名称：

1. P(A | B) 是已知B发生后，A发生的条件概率，也称作A的事后概率
2. P(A)是A的先验概率（或边缘概率），不考虑任何B的因素
3. P(B | A) 是已知A发生后，B发生的条件概率，也称作B的后验概率
4. P(B)是B的先验概率（或边缘概率）

按这些术语，贝叶斯定理可表述为：

后验概率 = (似然性*先验概率)/标准化常量。也就是说，后验概率与先验概率和相似度的乘积成正比。

大家读到这里可能也许会问，这不是把问题变得更复杂了，因为公式越写越长了。但其实这里有一些地方可以简化。

首先，一旦$o_1,o_2,o_3, \ldots$ 一旦产生，就不会改变了，所以$P(o_1,o_2,o_3,\ldots)$ 是一个可以忽略的常数，因为我们只是想比较大小。

目前我们的公式变成了

$$P(o_1,o_2,o_3,\ldots | s_1, s_2, s_3 \ldots) \cdot P(s_1, s_2, s_3, \ldots)$$

当然，这里还有两项，虽然还是比一开始的公式的只有一项复杂，但是这个公式完全可以用隐马尔可夫模型来估计。

隐马尔可夫模型

马尔可夫性质

马尔可夫链（英语：Markov chain），又称离散时间马尔可夫链（discrete-time Markov chain，缩写为DTMC[1]），因俄国数学家安德烈·马尔可夫得名，为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。马尔科夫链作为实际过程的统计模型具有许多应用。

马尔可夫链

马尔可夫链（Markov chain），又称离散时间马尔可夫链（discrete-time Markov chain），因俄国数学家安德烈·马尔可夫得名，为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。马尔科夫链作为实际过程的统计模型具有许多应用。

在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变到另一个状态，也可以保持当前状态。状态的改变叫做转移，与不同的状态改变相关的概率叫做转移概率。随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在图形中的点，每一步可以移动到任何一个相邻的点，在这里移动到每一个点的概率都是相同的（无论之前漫步路径是如何的）。

上面的介绍中包含了马尔可夫链的三要素：

1. 状态空间，即每一步状态的所有可选值
2. 无记忆性（马尔可夫性质）
3. 转移矩阵

假设状态序列为

$$x_{t-2}, x_{t-1},x_t,x_{t+1},x_{t+2}\ldots$$

由马尔科夫链定义可知，

时刻Xt+1 的状态只与Xt 有关，用数学公式来描述就是：

$$P(x_{t+1} | \ldots x_{t-2},x_{t-1},x_{t}) = P(x_{t+1} | x_t)$$

举个例子，我们每天的早餐吃什么有两个选择，分别为A和B，如果我们今天早上吃了A，那么第二天早上继续吃A的概率是0.4，吃B的概率是0.6，而如果我们今天早上吃的是B，那么第二天早上吃A和B的概率都是0.5.

在这个例子中，状态空间就是 {A，B}，无记忆性就是说，明天吃什么只与今天有关，而转移矩阵如下：

$$\qquad \qquad A(今) B（今）\\ \begin{matrix} A（明） \\ B（明） \end{matrix} \begin{bmatrix} 0.4 & 0.5 \\ 0.6 & 0.5 \end{bmatrix}$$

假设我们第一天吃的是A，那么我们的初始状态就是:

$$\begin{bmatrix} 1 \\ 0 \end{bmatrix}$$

那么第二天吃A和B的概率分别为：

$$\begin{bmatrix} 0.4 & 0.5 \\ 0.6 & 0.5 \end{bmatrix} \times \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0.4 \\ 0.6 \end{bmatrix}$$

这个转移矩阵可以无限被左乘下去，如果最后的结果趋于稳定，那就说明这个马尔科夫链具有稳态，不过并不是所有的马尔可夫链都有稳态，也并不一定只有一个稳态。

隐马尔可夫模型

我们把马尔科夫链想象成一个状态机，它随机地选择一个状态作为初始状态，随后按照上述规则随机选择后续状态。这样运行一段时间后产生了一个状态序列$s_1,s_2,s_3,\ldots,s_T$ 。看到这个序列，我们不难数出某个状态$m_i$ 出现的次数$t(m_i)$，以及从$m_i$ 转移到$m_{j}$ 的次数$t(m_i, m_{j})$ ，从而估计出从$m_i$ 转移到$m_j$ 的概率$\frac{t(m_i, m_j)}{t(m_i)}$

隐马尔科夫模型是马尔可夫链的一个扩展：任意时刻t的状态是不可见的，所以观察者没法通过观察得到一个状态序列$s_1,s_2,s_3, \ldots, s_T$ 来推测转移概率等参数，但是隐马尔可夫模型在每个时刻t都会输出一个符号$o_t$ ，而且$o_t$ 跟$s_t$ 且只与$s_t$ 有关，这个被称为独立输出假设。

所谓的隐马尔可夫模型，相比于马尔可夫链，“隐”的是马尔可夫链的直接的输出s，但是我们知道的是与s相关的o。放到我们一开始的通信模型中，就是说，我们并不知道发送者发出的信号，但是我们知道接收者收到的信号。

基于马尔可夫假设和独立输出假设，我们可以计算出某个特定状态序列$s_1, s_2, s_3, \ldots$ 产出输出符号$o_1, o_2, o_3, \ldots$ 概率。

$$公式2：\\ P(s_1,s_2,s_3,\ldots,o_1,o_2,o_3,\ldots) = \prod_t P(s_t|s_{t-1}) \cdot P(o_t | s_t)$$

这个公式和我们前面简化后的公式就非常像了，我们再看一下之前的公式，我们称其为

$$公式1：\\ P(o_1,o_2,o_3,\ldots | s_1, s_2, s_3 \ldots) \cdot P(s_1, s_2, s_3, \ldots)$$

此时，我们就可以将原本的公式1替换成公式2了

$$P(o_1,o_2,o_3,\ldots | s_1, s_2, s_3 \ldots) = \prod_t P(s_t|s_{t-1}) \\ P(s_1, s_2, s_3, \ldots) = \prod_t P(o_t | s_t)$$

如此一来，通信的解码问题就可以用隐马尔可夫模型来解决了，而很多自然语言处理问题和通信的解码问题是等价的，因此它们完全可以由隐马尔可夫模型来解决。

$P(s_1,s_2,s_3,\ldots,o_1,o_2,o_3,\ldots)$ 指的是发送端出现$s_1,s_2,s_3,\ldots$ 并且 接收端出现$o_1,o_2,o_3,\ldots$ 的概率

$P(o_1,o_2,o_3,\ldots | s_1, s_2, s_3 \ldots)$ 指的是发送端出现$s_1,s_2,s_3,\ldots$ 的时候 接收端出现$o_1,o_2,o_3,\ldots$ 的概率，基于独立输出假设，它就等于$\prod_t P(o_t | s_t)$

$P(s_1, s_2, s_3, \ldots)$ 指的是发送端出现$s_1,s_2,s_3,\ldots$ 的概况，基于马尔可夫假设，他就等于$\prod_t P(s_t|s_{t-1})$

所以我们一开始的公式1$P(o_1,o_2,o_3,\ldots | s_1, s_2, s_3 \ldots) \cdot P(s_1, s_2, s_3, \ldots) = \prod_t P(o_t | s_t) \cdot \prod_t P(s_t|s_{t-1})$

至于如何找出上面式子的最大值，进而找出要被识别的句子$s_1,s_2,s_3,\ldots$，可以用维特比算法。

隐马尔可夫模型使用

围绕隐马尔可夫模型有三个基本问题：

1. 给定一个模型，如何计算某个特定的输出序列的概率
2. 给定一个模型和某个特定的输出序列，如何找出最可能产生这个输出的状态序列
3. 给定足够量的观测数据，如何估计隐马尔可夫模型的参数

第一个问题可以用Forward-Backward算法，第二个问题可以用维特比算法解决，第三个问题就是模型训练问题。

Forward-Backward算法

HMM模型的问题一是，给定一个模型，如何计算某个特定的输出序列的概率，用公式来表达，就是我们已知模型的参数$\lambda = (A,B,C)$，其中A是隐藏状态的概率转移矩阵，B是隐藏状态生成观测状态的生成概率矩阵，C是隐藏状态的初始概率分布，同时我们也知道了$O = {o_1,o_2,o_3,\ldots}$，现在我们要求观测序列O在模型$\lambda$ 下出现的概率$P(O | \lambda)$。

乍一看，这个问题很简单。因为我们知道所有的隐藏状态之间的转移概率和所有从隐藏状态到观测状态生成概率，那么我们是可以暴力求解的。

我们之前已经能够根据转化后的公式1，即$P(s_1, s_2, s_3,\ldots,o_1,o_2,o_3,\ldots) = P(o_1,o_2,o_3,\ldots | s_1, s_2, s_3 \ldots) \cdot P(s_1, s_2, s_3, \ldots) = \prod_t P(o_t | s_t) \cdot \prod_t P(s_t|s_{t-1})$ 求出序列$s_1, s_2, s_3,\ldots,o_1,o_2,o_3,\ldots$ 的联合概率

那么我们想要求出观测序列O在模型$\lambda$ 下出现的概率$P(O | \lambda)$，就是求$P(o_1,o_2,o_3,\ldots)$，我们只需要把所有的O的联合概率加起来就好，即：

$$P(o_1,o_2,o_3,\ldots) = \sum_{s_1,s_2,s_3,\ldots}P(s_1, s_2, s_3,\ldots,o_1,o_2,o_3,\ldots)$$

虽然上述方法有效，但是如果我们的隐藏状态数N(即s的可能取值，也就是我们之前说的状态空间的大小)非常多的那就麻烦了，此时我们预测状态有$N^T$ 种组合，算法的时间复杂度是$O(TN^T)$ 阶的。因此对于一些隐藏状态数极少的模型，我们可以用暴力求解法来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。

前向后向算法就是来帮助我们在较低的时间复杂度情况下求解这个问题的。

前向后向算法是前向算法和后向算法的统称，这两个算法都可以用来求HMM观测序列的概率。我们先来看看前向算法是如何求解这个问题的。

前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。

在前向算法中，通过定义“前向概率”来定义动态规划的这个局部状态。什么是前向概率呢, 其实定义很简单：定义时刻t时隐藏状态$s_t$ 为$q_i$, 观测状态的序列为$o_1,o_2,o_3,\ldots$ 的概率为前向概率，记为:

$$\alpha_t(i) = P(o_1,o_2,o_3,\ldots,o_t, s_t=q_i|\lambda)$$

既然是动态规划，我们就要递推了，现在假设我们找到了t时刻的各个隐藏状态的前向概率，现在我们要递推出t+1时刻各个隐藏状态的前向概率。

1. 我们可以基于时刻t的各个隐藏状态的前向概率，再乘以对应的状态转移概率，即$\alpha(j) \cdot a_{ji}$ 就是在时刻t观测到$o_1,o_2,o_3,\ldots,o_t$ 并且时刻t的隐藏状态为$q_j$ ，时刻t+1的隐藏状态为$q_i$ 的概率
2. 对时刻t所有的隐藏状态的前向概率求和，即$\sum_{j=1}^N \alpha_t(j)a_{ji}$ 就是在时刻t观测到$o_1,o_2,o_3,\ldots,o_t$ 并且时刻t+1的隐藏状态为$q_i$ 的概率。
3. 再进一步，由于观测状态$O_{t+1}$ 只依赖t+1时刻的隐藏状态$q_i$，那么我们再乘上生成概率就可以得到时刻t+1观测到$o_1,o_2,o_3,\ldots,o_{t+1}$，并且t+1时刻隐藏概率为$q_i$ 的概率，而这个概率就是t+1时刻的前向概率。即$[\sum_{j=1}^N \alpha_t(j)a_{ji}]\cdot b_t(o_{t+1})$，这里的前向概率$\alpha_t(i)$ 就是我们之前讨论的$P(o_1,o_2,o_3,\ldots | s_1, s_2, s_3 \ldots)$ 而$b_t(o_{t+1})$ 就是我们的生成概率$\prod_t P(o_t | s_t)$

维特比算法

维特比算法是一个特殊但是应用最广的动态规划算法。利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图，篱笆网络（Lattice）的有向图的最短路径问题而提出的。

它之所以重要，是因为凡是使用隐马尔可夫模型的问题，都可以用它来解码，包括数字通信，语音识别，机器翻译，拼音转汉字，分词等。

我们用输入法的拼音转汉字来说明：

假定用户输入的拼音是$y_1,y_2,\ldots,y_N$，对应的汉字是$x_1,x_2,\ldots,x_N$ 那么根据通信模型：

$$x_1,x_2,\ldots,x_N = ArgMax_{x \sub X} P(x_1,x_2,\ldots,x_N | y_1,y_2,\ldots,y_N)$$

根据隐马尔可夫模型，它又可以继续等于：

$$x_1,x_2,\ldots,x_N = ArgMax_{x \sub X} P(x_1,x_2,\ldots,x_N | y_1,y_2,\ldots,y_N) \\ = ArgMax_{x \sub X} \prod_{i=1}^N P(y_i | x_i) \cdot P(x_i | x_{i-1})$$

输入的$y_1,y_2,\ldots,y_N$ 为可见序列，而产生他们的隐含序列是$x_1,x_2,\ldots,x_N$。

这是一个相对简单的隐马尔可夫模型，没有状态跳跃，也没有状态自环。$P(x_i | x_{i-1})$ 是状态转移概率，$P(y_i | x_i)$ 是生成概率。

现在这个马尔可夫链的每个状态的输出是固定的，但是每个状态的值是可以改变的。比如拼音“zhong”可以是“中”，“种”等多个字。 我们抽象一点说，用符号$x_{ij}$ 来表示状态$x_i$ 的第j个可能的值。如果把每个状态按照不同的值展开，就得到了一个篱笆网络。

维特比算法可以概括为以下三点：

1. 如果概率最大的路径P（或者说最短路径）经过某个点，比如$x_{22}$ ，那么这条路径上从起始点S到$x_{22}$ 的这一段子路径Q一定是S到$x_{22}$ 之间的最短路径，否则，就可用另一条最短路径R来取代Q，这显然是矛盾的。
2. 从S到E的路径必定经过i时刻的某个状态，假定第i时刻有k个状态，那么如果记录了从S到第i个状态所有k个节点的最短路径，最终的最短路径必定经过其中一条。这样，在任何时刻，只需要考虑非常有限的候选路径即可
3. 结合上述两点，假定当我们从状态i到i+1，从状态S到i上各个节点的最短路径已经找到，并且记录在这些节点上，那么在计算从起点S到第i+1状态的某个节点的最短路径时，只要考虑从S到前一个状态i所有k个节点的最短路径，以及从这k个节点到$x_{x+1, j}$ 的距离即可。

这个动态规划的起始状态，即从S出发，到$x_1$ 的各个节点，不妨假定有$n_1$ 个，计算出S到他们的距离$d_{S,x_{1i}}$ 就是S到他们各自最短的距离，

这个动态规划的状态转移公式为：

$$d(S,x_{2i}) = min[d(S,x_{1j}) + d(x_{1j},x_{2i})]$$

模型训练问题

在利用隐马尔可夫模型解决实际问题中，需要事先知道从前一个状态$s_{t-1}$ 进入当前状态$s_t$ 的概率$P(s_t | s_{t-1})$，也称为转移概率，和每个状态$s_t$ 产生相应输出符号$o_t$ 的概率$P(o_t | s_t)$ 也称为生成概率。这些概率被称为隐马尔可夫模型的参数，而计算或者估计这些参数的过程称为模型的训练。

我们从条件概率的定义出发，知道：

$$P(o_t | s_t) = \frac{P(o_t,s_t)}{P(s_t)} \qquad 公式3 \\ P(s_t | s_{t-1}) = \frac{P(s_{t-1},s_t)}{P(s_{t-1})} \qquad 公式4$$

对于公式3的状态输出概率，如果有足够多的人工标记的数据，知道经过$s_t$ 有多少次$t_(s_t)$ ，每次经过这个状态时，分别产生的输出$o_t$ 是什么，而且分别有多少次$t(o_t, s_t)$ 就可以用两者的比值

$$P(o_t | s_t) = \frac{t(o_t, s_t)}{t(s_t)}$$

直接估算出模型的参数。因为数据是人工标注的，因此这种方法被称为有监督的训练方法

对于公式4的转移概率，其实和之前博客提到的统计语言模型的条件概率完全相同，因此可以按照统计语言模型的训练方法：

$$P(s_t | s_{t-1}) = \frac{t(s_{t-1},s_t)}{t(s_{t-1})}$$

有监督的训练的前提是需要大量人工标注的数据，很遗憾的是，很多应用做不到这件事。

因此训练隐马尔可夫模型更实用的方式是仅仅通过大量观测到信号$o_1,o_2,o_3,\ldots$ 就能推算模型参数的$P(s_t | s_{t-1})$ 和$P(o_t | s_t)$ 的方法，这种方法被称为无监督的训练方法，主要使用的是鲍姆——韦尔奇算法。

两个不同的隐马尔可夫模型可以产生相同的输出信号，因此仅仅是通过观察到的输出信号来倒推它的隐马尔可夫模型，可能会得到很多合适的模型，但是总有一个模型$M_{\theta_2}$ 比$M_{\theta_1}$ 更有可能产生观测到的输出，其中$\theta_2$ 比$\theta_1$ 是隐马尔可夫模型的参数。鲍姆——韦尔奇算法就是用来寻找这个最可能的模型。

鲍姆——韦尔奇算法的思路是这样的：

1. 首先找到一组能够产生输出序列O的模型参数（显然它们一定存在，因为转移概率P和生成概率Q均为均匀分布时，模型可以产生任何输出，包括我们观察到的输出）
2. 现在有了这样一个初始模型，我们记为$M_{\theta_0}$ 。需要在此基础上找到一个更好的模型。假定我们解决了隐马尔科夫模型第一个和第二个问题，不但可以算出这个模型产生O的概率$P(O | M_{\theta_0})$ ，而且能够找到这个模型产生O的所有可能的路径以及这些路径的概率。这些路径，实际上记录了每个状态经历了多少次，到达了哪些状态，输出了那些符号，因此可以将它们看作“标注的训练数据”。并且根据公式3和4计算出一组新的模型参数$\theta_1$，从$M_{\theta_0}$ 到$M_{\theta_1}$ 的过程称为一次迭代。可以证明：$P(O | M_{\theta_1}) > P(O | M_{\theta_0})$
3. 接下来，我们从$M_{\theta_1}$ 出发，可以找到一个更好的模型，然后不断重复这个过程，直到模型的质量不再有明显的提高。

鲍姆——韦尔奇算法的每一次迭代都是不断地估计新模型的参数，使得输出的概率达到最大化，因此这个过程被称为期望最大化（Expectation-Maximization）过程，简称EM过程。

EM过程保证算法一定可以收敛到一个局部最优点，但不保证是全局最优点，因此在一些应用中，它的效果比有监督的学习效果差，但如果目标函数是凸函数，只有一个最优点，这种情况下，EM过程可以找到最佳。