第十四章：隐 Markov 模型

HMM 概述

Markov 链也就是加权自动机。HMM 增加了要求：

• HMM 有一个观察符号的集合 O，这个集合中的符号不是从状态集合 Q 中的字母抽取的
• HMM 中观察似然度函数 B 的值不只限于 1 或 0，概率 bi(ot) 可以取 0-1 之间的任何值

HMM 要求的参数如下：

• 状态序列：Q = (q1, q2, …, qn)
• 观察序列：O = (o1, o2, …, on)
• 转换概率：A = (a01, a02, …, ann)
• 观察似然度：B = bi(ot)，表示从状态 i 生成观察值 ot 的概率
• 初始状态概率分布：π，πi 是 HMM 在状态 i 开始时的概率
• 接收状态：合法的接收状态集合

需要求解的是 A B π，因此一般使用 λ = {A, B, π} 来定义一个 HMM 模型，模型对外表现出来的是观察序列，状态序列不能直接观察到，被称为 “隐变量”。

三个基本问题：

• 评估问题：给定观察序列 O 和模型 λ，如何计算由该模型产生该观察序列的概率 P(O|λ)
• 解码问题：给定观察序列 O 和模型 λ，如何获取在某种意义下最优的状态序列 Q，一般使用 Viterbi 算法
• 训练问题：如何选择或调整模型参数 λ，使得在该模型下产生观察序列 O 的概率 P(O|λ) 最大

HMM 在语音识别中的应用

口语理解分为自动语音识别（ASR）和自动语音理解（ASU），这里重点关注 “大词汇量连续语音识别” 这个领域：

• 大词汇量：5000-60000 个单词的词汇
• 连续：所有单词自然地、一块说出来

可以把语音识别系统看作一个噪声信道模型，建立噪声信道模型需要解决两个问题：

• 为了挑选出与噪声输入匹配的最佳的句子，需要对 “最佳匹配” 有一个完全的度量
• 所有英语句子的集合非常大，需要一个有效的算法使得只搜索那些有机会与输入匹配的句子
  • Viterbi 或动态规划解码算法
  • A* 或栈解码算法

语音识别的概率噪声信道模型总体结构目标如下：“对于给定的某个声学输入 O，在语言 L 的所有句子中，寻找一个最可能的句子。”

• 可以把 O 看成音片串，把句子看成单词串
• 单词通常根据正词法定义，比如 oak 和 oaks 不同，can 和 can’t 相同

$$\hat{W} = \arg \max_{W \in L} P(W|O) = \arg \max_{W \in L} P(O|W) P(W)$$

• 假定输入序列是音子序列，而不是声学观察序列
• 向前算法对于给定音子序列的观察，能够产生出对于给定单词的这些音子的观察概率，是 HMM 的特殊情况；进一步扩充就可以对给定的一个句子计算出音子序列的概率。
• Viterbi 和 A* 解码算法能同时计算观察序列的似然度并给出最可能的句子。

语音识别系统可以分为三个阶段：

• 信号处理阶段：又叫特征抽取阶段，语音的声学波形切分为音片框架（通常是10，15 或 20 毫秒），把音片框架转换成声谱特征，声谱特征要给出不同频率信号的能量大小的信息。
• 音子阶段：又叫亚词阶段，尝试识别单个语音，输出概率。
• 解码阶段：利用单词发音词典和语言模型（概率语法）采用解码算法发现对于给定音子集合具有最大概率的单词序列。难点在于协同发音和快速发音导致的单词边界模糊。

Viterbi 的 “动态规划恒定” 假定如果对于全部观察序列，最终的最佳路径恰好通过了状态 qi，那么这条最佳路径必定是在此之前包括状态 qi 在内的所有路径中最佳的路径。目的是用一种简单的办法分解最佳路径概率的计算，简单地假定在时刻 t 的每一条最佳路径就是在时刻 t-1 终结的每一条路径的最佳扩充。换言之，对于在状态 j 和时刻 t 结尾的最佳路径，viterbi[t,j] 就是从时刻 t-1 到时刻 t 前面每种可能路径的一切可能的扩充的最大值：

$$viterbi[t,j] = max_i(viterbi[t-1, i]a_{ij}) b_j(o_t)$$

有三个关键的办法可以充实简化的 Viterbi 算法：

• 实际输入的不是音子，而是声谱特征或声学特征矢量，因此给定状态 i，观察值 Ot 的观察似然读 bi(t) 不是简单的 01，而是概率估计
• HMM 状态不是简单的音子，而是次音子（音子被分解成：开始、中间和最后部分三个状态）
• 在每一个时间步对低概率的路径进行修剪，而不让它延伸到下一个状态列。通常使用 ”beam search“ 实现：对于每一个状态列（时间步），维护一个比较短的表，只记录路径概率处于最可能单词路径的某一百分比（beam search 宽度）之内的高概率单词。当向下一个时间步转移时，只有从这些单词的转移才能够向前延伸。

Viterbi 算法有两个限制：

• 不计算具有最大概率的单词序列，而计算与这样的单词序列近似的、对于给定的输入具有最大概率的状态序列（音子序列或次音子序列），有时候概率最大的音子序列并不对应于概率最大的单词序列。假设单词序列包含一个具有很多发音的单词，通过这个单词发音路径的概率（所有发音概率和为 1）就小于只有一个发音单词的概率，具有多个发音的单词就会被忽略。
• 不能应用于所有可能的语言模型，原因是 ”动态规划恒定“ 假设只能采用二元语法。三元语法中一个单词的概率由前面两个单词决定，因此一个句子的最佳三元语法概率的路径就可能会通过没有包括在该单词的最佳路径中的某个单词。

两类解决办法：

• 第一类：修改算法，返回多个潜在语段，再使用其他复杂语言模型，重新给多个输出排序。如 1990 年，Schwartz 和 Chow 提出的 ”N-最佳 Viterbi 算法“，对于给定的语音输入，可以返回 N 个最佳句子。比如假定使用二元语法，返回 N 个概率最高的句子，再使用三元语法给每个句子指派一个新语言模型的先验概率。先验概率与每个句子的声学似然度结合，生成每个句子的后验概率，然后重新给句子打分排序。
• 第一类还有一种方法也是用 N-最佳，但返回的不是句子表，而是一个 ”单词格“。单词格是单词的有向图，单词之间用单词格连接后就可以对大量句子进行紧致的编码，格中每个单词使用它们的观察似然度扩充。
• 第二类：使用 A* 解码算法
  • Viterbi 计算通过 HMM 的最佳路径的似然度；向前算法计算通过 HMM 所有路径的总和的似然度。
  • A* 解码依靠完全的向前算法，而不依靠近似值。它也允许使用任何语言模型。
  • A* 解码是对于 ”格“（数学概念，不是语法格）和 ”树“ 的一种最佳优先搜索。
  • A* 解码算法需要找出从根到概率最大的叶子之间的路径（单词序列），而该路径的概率可以由语言模型的先验概率和它与声学数据匹配的似然度的乘积确定。具体过程可参见 P650 的例子。
  • 快速匹配：一种试探性方法，用于筛选下面可能的单词的数目，通常需要计算出前面概率的近似值。很多都基于 ”树结构词表“，该表中存储着所有单词的发音，存储的方式要使得在向前方推进计算概率的时候，可以与相同音子开头的单词共享，做到前后勾连。
  • A* 评估函数：为了解决路径越长概率越小的问题。f*(p) = g(p) + h*(p)，f*(p) 是从部分路径 p 开始的最佳完全路径（完全句子）的估计分数
    • g(p) 是从语段的起点到部分路径的终点的分数
    • h*(p) 是从部分路径延伸到语段终点的最佳分数的估计

小结

• HMM 概述

  • 一般使用 λ = {A, B, π} 来定义一个 HMM 模型，模型对外表现出来的是观察序列，状态序列不能直接观察到，被称为 “隐变量”。三个基本问题：
  • 评估问题：给定观察序列 O 和模型 λ，如何计算由该模型产生该观察序列的概率 P(O|λ)
  • 解码问题：给定观察序列 O 和模型 λ，如何获取在某种意义下最优的状态序列 Q，一般使用 Viterbi 算法
  • 训练问题：如何选择或调整模型参数 λ，使得在该模型下产生观察序列 O 的概率 P(O|λ) 最大

• HMM 在语音识别中的应用

  • 可以把语音识别系统看作一个噪声信道模型，建立噪声信道模型需要解决两个问题：
    • 为了挑选出与噪声输入匹配的最佳的句子，需要对 “最佳匹配” 有一个完全的度量
    • 所有英语句子的集合非常大，需要一个有效的算法使得只搜索那些有机会与输入匹配的句子
  • 语音识别的概率噪声信道模型总体结构目标如下：“对于给定的某个声学输入 O（音子序列），在语言 L 的所有句子中，寻找一个最可能的句子。”
  • 语音识别系统可以分为三个阶段：
    • 信号处理阶段：声学波形切分为音片框架，音片框架转换成声谱特征
    • 音子阶段：尝试识别单个语音，输出概率
    • 解码阶段：利用单词发音词典和语言模型采用解码算法发现对于给定音子集合具有最大概率的单词序列
  • 解码使用的 Viterbi 的 “动态规划恒定” 假定如果对于全部观察序列，最终的最佳路径恰好通过了状态 qi，那么这条最佳路径必定是在此之前包括状态 qi 在内的所有路径中最佳的路径。
  • 有三个关键的办法可以充实简化的 Viterbi 算法：
    • 实际输入的不是音子，而是声谱特征或声学特征矢量
    • HMM 状态不是简单的音子，而是次音子
    • 使用 ”beam search“ 在每一个时间步对低概率的路径进行修剪，不让它延伸到下一个状态列
  • Viterbi 算法有两个限制：
    • 它不计算具有最大概率的单词序列，而计算音子或次音子序列，有时候概率最大的音子序列并不对应于概率最大的单词序列
    • 不能应用于所有可能的语言模型，原因是 ”动态规划恒定“ 假设只能采用二元语法
  • 两类解决办法：
    • 第一类：修改算法，返回多个潜在语段，再使用其他复杂语言模型，重新给多个输出排序，如 1990 年，Schwartz 和 Chow 提出的 ”N-最佳 Viterbi 算法“。第一类还有一种方法也是用 N-最佳，但返回的不是句子表，而是一个 ”单词格“。
    • 第二类：使用 A* 解码算法。A* 解码依靠完全的向前算法，而不依靠近似值。它也允许使用任何语言模型。A* 解码算法需要找出从根到概率最大的叶子之间的路径（单词序列），而该路径的概率可以由语言模型的先验概率和它与声学数据匹配的似然度的乘积确定。

本章主要介绍了 HMM 在语音识别中的应用，其实 HMM 在 NLP 中的应用领域非常多，可以算是最重要的模型之一。里面涉及到的几种算法也比较经典，比如 Viterbi、beam search、A* 等。更多关于 HMM 的扩展资料可以查看：HMM Tutorial