隐马尔可夫模型

1. 通信系统

2. 各种“马尔可夫”们

2.1 马尔可夫假设

2.2 马尔可夫链

2.3 隐马尔可夫模型

2.3.1 将隐马尔可夫模型应用于解码问题

2.3.2 如何训练隐马尔可夫模型

2.3.2.1 有监督的训练

2.3.2.2 无监督的训练

1. 通信系统

通信的本质就是一个【编码+传输+解码】的过程。典型的通信系统具有六大要素：发送者（信息源）、信道、接收者、信息、上下文、编解码。这六大要素关系如下所示：

其中 $s_1, s_2, s_3...$ 表示发送者发出的原始信息， $o_1, o_2, o_3, ...$ 表示将 $s_1, s_2, s_3...$ 编码后的信息，接收者则要用特定的解码方式将 $o_1, o_2, o_3, ...$ 还原成 $s_1, s_2, s_3...$ 。上面这个通信系统表示的过程本质上就是自然语言处理的过程。

那如何才能成功解码呢？将 $o_1, o_2, o_3, ...$ 解码成 $s_1, s_2, s_3...$ 的过程，其实就是寻找能让这个条件概率 $P(s_1, s_2, s_3, ... | o_1, o_2, o_3, ...)$ 达到最大值的 $s_1, s_2, s_3...$ 。用数学公式表达这个意思如下所示：

我们利用贝叶斯公式将这个条件概率展开，得：

其中， $P(o_1, o_2, o_3, ...)$ 表示接收端收到 $o_1, o_2, o_3, ...$ 的概率，这在真实场景中是一个可以被忽略的常数项（因为一旦需要启动解码 $o_1, o_2, o_3, ...$ 的工作，就证明这个编码信息已经存在了，完全消除不确定性了）。 $P(s_1, s_2, s_3...)$ 表示 $s_1, s_2, s_3...$ 是一段合乎情理的有意义的话的概率。

因为 $P(o_1, o_2, o_3, ...)$ 是一个常数，因此后续我们只要考虑分子的大小就行：

那如何估计上面的概率值呢？这个时候，就得请出隐马尔可夫模型（Hidden Markov Model）了。

2. 各种“马尔可夫”们

首先声明下，“隐马尔可夫模型”并非是19世纪俄罗斯数学家马尔可夫（Andrey Markov）提出的，而是由美国数学家鲍姆(LeonardE.Baum)等人在20世纪六七十年代提出的。之所以被称为“隐马尔可夫模型”，是因为这个模型是基于马尔可夫假设提出的。

2.1 马尔可夫假设

马尔可夫假设，听起来感觉高大上，但其实它描述了一个非常直观的概念。想象一下，我们要预测明天的天气“是晴还是雨”。马尔可夫假设就是说，明天的天气只与今天的天气有关，而与前天及以前的天气无关。

用更专业的语言来说，马尔可夫假设认为在给定时间段内，一个系统的未来状态只取决于它的当前状态，而与它过去的状态无关。这就像是在一个迷宫中，你只需要知道你现在在哪里，就可以推测出下一步应该往哪里走，而不需要关心你之前是怎么走到这里的。可以用下面的数学公式来表示马尔可夫假设：

即当前的状态 $s_t$ 的出现概率只与前一个状态 $s_{t-1}$ 直接相关，而与更早的状态无关。

2.2 马尔可夫链

马尔可夫链，简单来说，就是一系列遵循马尔可夫假设的随机事件或状态。这些事件或状态按照时间顺序排列，形成一个链条。在这个链条中，每个事件或状态的发生概率只取决于前一个事件或状态。作者举了如下一个简单的马尔可夫链：

其中 $s_1=m_1,s_2= m_2, s_3=m_3, s_4=m_4$ 分别表示4种不同的状态，每条带有箭头的有向线段表示一种状态转变，线段上的数字表示转移概率。比如状态 $m_2$ 后面有两条转化路径，一条是转化到状态 $m_4$ ，概率为0.4；另一条是转化到状态 $m_3$ ，概率为0.6。

2.3 隐马尔可夫模型

有些情况下，上面的状态 $s_1=m_1,s_2= m_2, s_3=m_3, s_4=m_4$ 并不能直接观察到，能看到的则是与这些状态息息相关的信号 $o_1, o_2, o_3, ...$ 。为了简化问题，统计学家们提出了“独立输出假设”，指在每个时刻 $t$ ，模型会输出一个符号 $o_t$ ，而且 $o_t$ 跟 $s_t$ 相关且仅跟 $s_t$ 相关。如下图所示，作者展示了一个简单的隐马尔可夫模型：

简而言之，可以将【隐马尔可夫模型】看做是【马尔可夫假设】+【独立输出假设】结合的产物。

2.3.1 将隐马尔可夫模型应用于解码问题

请注意，上图中表示的隐马尔可夫模型，本质上能够表达一种映射关系（即原文 $s_1, s_2, s_3, ...$ 与其编码后的 $o_1, o_2, o_3, ...$ 的映射关系），正因为这个特性，隐马尔可夫模型可被用于通信的解码问题，即我们可以计算出信息源发出某个特定的消息序列 $s_1, s_2, s_3, ...$ 产生出特定的符号序列 $o_1, o_2, o_3, ...$ 的概率，其数学公式的表达形式如下：

其中：

大家是不是觉得眼熟？是的，上面的公式正是通信系统的解码过程中的目标函数，目的就是找到使 $P(s_1, s_2, s_3, ... , o_1, o_2, o_3, ...)$ 值最大时对应的原文句子 $s_1, s_2, s_3, ...$ 。隐马尔可夫模型给我们提供了一个简单易行的估计 $P(s_1, s_2, s_3, ... , o_1, o_2, o_3, ...)$ 值的方法，但至于如何能快速找到最大的 $P$ 值，就得利用维特比算法(Viterbi Algorithm)了，这里面的细节我们会在后面的读书笔记中介绍。

2.3.2 如何训练隐马尔可夫模型

作者提出，围绕隐马尔可夫模型有三个基本问题：

1）如何计算给定模型下特定输出序列 $o_1, o_2, o_3, ...$ 的概率？
2）如何找到给定模型和特定输出序列下最可能的状态序列 $s_1, s_2, s_3, ...$ ？
3）如何利用大量观测数据来估计隐马尔可夫模型的参数？

问题一最简单，这通常通过前向算法（Forward Algorithm）或后向算法（Backward Algorithm）来计算，就类似于初中求解概率值的问题。

问题二就用前面的提到的维特比算法进行求解，这个后续章节会介绍。

问题三就涉及到如何训练隐马尔可夫模型的问题了。通常，隐马尔可夫模型的参数主要有两个：

1）转移概率：从前一个状态 $s_{t-1}$ 转移到下一个状态 $s_t$ 的概率，即 $P(s_t|s_{t-1})$ 。

2）生成概率：每个状态 $s_t$ 产生输出符号 $o_t$ 的概率，即 $P(o_t|s_t)$ 。

现在参数明确了，接下来的问题就是如何去估计这两个参数。

2.3.2.1 有监督的训练

将 $P(s_t|s_{t-1})$ 和 $P(o_t|s_t)$ 用贝叶斯公式展开，得：

如果我们有足够多的人工标注数据，就能数出状态 $s_t$ 出现的次数 $\#s_t$ ，再统计出状态 $s_t$ 输出符号 $o_t$ 的次数 $\#(s_t, o_t)$ ，最后相除，即可估算出上面参数之一的生成概率 $P(o_t|s_t)$ 的值：

至于转移概率 $P(s_t|s_{t-1})$ 的估算，对前面几章读书笔记还有印象的同学应该能反应过来，这个其实表示的就是统计语言模型。因此，基于训练语料库，可以用下面的公式进行估计：

尽管有监督的训练方法因其直接性而易于理解，但其核心挑战在于高质量的人工标注数据的稀缺性。并非所有现实问题都能轻松找到相应的人工标注数据。为了应对这一挑战，科学家们提出了无监督的训练方法，旨在无需人工标注的情况下从数据中学习模式。

2.3.2.2 无监督的训练

隐马尔可夫模型最常用的无监督训练算法当属鲍姆-韦尔奇算法（Baum-WelchAlgorithm），它通过迭代方法估计模型参数，使得观测序列 $o_1, o_2, o_3, ...$ 的概率最大化。该算法是一种期望最大化（Expectation-Maximization, EM）算法的实现。它的基本思想是通过迭代来估计模型参数，每次迭代都包括一个E步（Expectation Step）和一个M步（Maximization Step）。

1）初始化：首先，随机设定模型的初始参数，包括状态转移概率、符号生成概率等，得到初始化模型 $M_{\theta_0}$ 。
2）E步骤：接着，初始化模型 $M_{\theta_0}$ ，找到这个模型产生观测序列 $o_1, o_2, o_3, ...$ 的所有可能的隐藏状态路径 $s_1, s_2, s_3, ...$ 以及这些路径的概率。这些可能的路径，实际上记录了每个隐藏状态经历了多少次，到达了哪些其他的隐藏状态，对应输出了哪些符号，因此可以将它们看做是“标注的训练数据”。
3）M步骤：然后，根据E步骤中得到的所谓“标注的训练数据”，模仿上一节监督训练里的方式，计算新的转移概率和生成概率，进而得到新模型 $M_{\theta_1}$ ，以使得模型生成观测序列的总概率增加。可以数学证明：