二、 HMM 基本问题

1. 隐马尔可夫模型的 3 个基本问题：

   • 概率计算问题：给定模型 和观测序列 ，计算观测序列 出现的概率 。即：评估模型 与观察序列 之间的匹配程度。

   • 学习问题：已知观测序列 ，估计模型 的参数，使得在该模型下观测序列概率 最大。即：用极大似然估计的方法估计参数。

   • 预测问题（也称为解码问题）：已知模型 和观测序列 ， 求对给定观测序列的条件概率 最大的状态序列 。即：给定观测序列，求最可能的对应的状态序列 。

     如：在语音识别任务中，观测值为语音信号，隐藏状态为文字。解码问题的目标就是：根据观测的语音信号来推断最有可能的文字序列。

2.1 概率计算问题

1. 给定隐马尔可夫模型 和观测序列 ，概率计算问题需要计算在模型 下观测序列 出现的概率 。

2. 最直接的方法是按照概率公式直接计算：通过列举所有可能的、长度为 的状态序列 ，求各个状态序列 与观测序列 的联合概率 ，然后对所有可能的状态序列求和，得到 。

   • 状态序列 的概率为：

     

   • 给定状态序列 ，观测序列 的条件概率为：

     

   • 和 同时出现的联合概率为：

     

   • 对所有可能的状态序列 求和，得到观测序列 的概率：

     

   • 上式的算法复杂度为 ，太复杂，实际应用中不太可行。

2.1.1 前向算法

1. 给定隐马尔可夫模型 ，定义前向概率：在时刻 时的观测序列为 ， 且时刻 时状态为 的概率为前向概率，记作：

2. 根据定义， 是在时刻 时观测到 ，且在时刻 处于状态 的前向概率。则有：

   • ：为在时刻 时观测到 ，且在时刻 处于状态 ，且在 时刻处在状态 的概率。

   • ：为在时刻 观测序列为 ，并且在时刻 时刻处于状态 的概率。

   • 考虑 ，则得到前向概率的地推公式：

     

     

3. 观测序列概率的前向算法：

   • 输入：

     • 隐马尔可夫模型
     • 观测序列

   • 输出： 观测序列概率

   • 算法步骤：

     • 计算初值： 。

       该初值是初始时刻的状态 和观测 的联合概率。

     • 递推：对于 ：

       

     • 终止： 。

       因为 表示在时刻 ，观测序列为 ，且状态为 的概率。对所有可能的 个状态 求和则得到 。

4. 前向算法是基于 状态序列的路径结构 递推计算 。

   • 其高效的关键是局部计算前向概率，然后利用路径结构将前向概率“递推”到全局。
   • 算法复杂度为 。

2.1.2 后向算法

1. 给定隐马尔可夫模型 ，定义后向概率：在时刻 的状态为 的条件下，从时刻 到 的观测序列为 的概率为后向概率，记作： 。

2. 在时刻 状态为 的条件下，从时刻 到 的观测序列为 的概率可以这样计算：

   • 考虑 时刻状态 经过 转移到 时刻的状态 。

     • 时刻状态为 的条件下，从时刻 到 的观测序列为观测序列为 的概率为 。
     • 时刻状态为 的条件下，从时刻 到 的观测序列为观测序列为 的概率为 。

   • 考虑所有可能的 ，则得到 的递推公式：

     

     

3. 观测序列概率的后向算法：

   • 输入：

     • 隐马尔可夫模型
     • 观测序列

   • 输出： 观测序列概率

   • 算法步骤：

     • 计算初值：

       对最终时刻的所有状态 ，规定 。

     • 递推：对 :

       

     • 终止：

       为在时刻 1， 状态为 的条件下，从时刻 2 到 的观测序列为 的概率。对所有的可能初始状态 （由 提供其概率）求和并考虑 即可得到观测序列为 的概率。

2.1.3 统一形式

1. 利用前向概率和后向概率的定义，可以将观测序列概率统一为：

   

   • 当 时，就是后向概率算法；当 时，就是前向概率算法。

   • 其意义为：在时刻 ：

     • 表示：已知时刻 时的观测序列为 、 且时刻 时状态为 的概率。
     • 表示：已知时刻 时的观测序列为 、 且时刻 时状态为 、且 时刻状态为 的概率。
     • 表示： 已知时刻 时的观测序列为 、 且时刻 时状态为 、且 时刻状态为 的概率。
     • 表示：已知观测序列为 、 且时刻 时状态为 、且 时刻状态为 的概率。
     • 对所有可能的状态 取值，即得到上式。

2. 根据前向算法有： 。则得到：

   

   由于 的形式不重要，因此有：

   

3. 给定模型 和观测序列 的条件下，在时刻 处于状态 的概率记作：

   • 根据定义：

     

   • 根据前向概率和后向概率的定义，有： ，则有：

     

4. 给定模型 和观测序列 ，在时刻 处于状态 且在 时刻处于状态 的概率记作：

   • 根据

     

   • 考虑到前向概率和后向概率的定义有： ，因此有：

     

5. 一些期望值：

   • 在给定观测 的条件下，状态 出现的期望值为： 。

   • 在给定观测 的条件下，从状态 转移的期望值： 。

     • 这里的转移，表示状态 可能转移到任何可能的状态。
     • 假若在时刻 的状态为 ，则此时不可能再转移，因为时间最大为 。
   • 在观测 的条件下，由状态 转移到状态 的期望值： 。

2.2 学习问题

1. 根据训练数据的不同，隐马尔可夫模型的学习方法也不同：

   • 训练数据包括观测序列和对应的状态序列：通过监督学习来学习隐马尔可夫模型。
   • 训练数据仅包括观测序列：通过非监督学习来学习隐马尔可夫模型。

2.2.1 监督学习

1. 假设数据集为 。其中：

   • 为 个观测序列； 为对应的 个状态序列。
   • 序列 ， 的长度为 ，其中数据集中 之间的序列长度可以不同。

2. 可以利用极大似然估计来估计隐马尔可夫模型的参数。

   • 转移概率 的估计：设样本中前一时刻处于状态 、且后一时刻处于状态 的频数为 ，则状态转移概率 的估计是：

     

   • 观测概率 的估计：设样本中状态为 并且观测为 的频数为 ，则状态为 并且观测为 的概率 的估计为：

     

   • 初始状态概率的估计：设样本中初始时刻（即： ）处于状态 的频数为 ，则初始状态概率 的估计为： 。

2.2.2 无监督学习

1. 监督学习需要使用人工标注的训练数据。由于人工标注往往代价很高，所以经常会利用无监督学习的方法。

   隐马尔可夫模型的无监督学习通常使用 Baum-Welch 算法求解。

2. 在隐马尔可夫模型的无监督学习中，数据集为 。其中：

   • 为 个观测序列。
   • 序列 的长度为 ，其中数据集中 之间的序列长度可以不同。

3. 将观测序列数据看作观测变量 ， 状态序列数据看作不可观测的隐变量 ，则隐马尔可夫模型事实上是一个含有隐变量的概率模型： 。其参数学习可以由 EM 算法实现。

   • E 步：求 Q 函数（其中 是参数的当前估计值）

     

     将 代入上式，有：

     

     • 在给定参数 时， 是已知的常数，记做 。
     • 在给定参数 时， 是 的函数，记做 。

     根据 得到：

     

     其中： 表示第 个序列的长度， 表示第 个观测序列的第 个位置。

   • M 步：求Q 函数的极大值：

     

     极大化参数在 Q 函数中单独的出现在3个项中，所以只需要对各项分别极大化。

     • ：

       

       将 代入，有：

       

       将 代入，即有：

       

       考虑到 ，以及 ， 则有：

       

       其物理意义为：统计在给定参数 ，已知 的条件下， 的出现的频率。它就是 的后验概率的估计值。

     • ：同样的处理有：

       

       得到：

       

       考虑到 ，则有：

       

       其物理意义为：统计在给定参数 ，已知 的条件下，统计当 的情况下 的出现的频率。它就是 的后验概率的估计值。

     • ：同样的处理有：

       

       得到：

       

       其中如果第 个序列 的第 个位置 ，则 。

       考虑到 ，则有：

       

       其物理意义为：统计在给定参数 ，已知 的条件下，统计当 的情况下 的出现的频率。它就是 的后验概率的估计值。

4. 令，其物理意义为：在序列 中，第 时刻的隐状态为 的后验概率。

   令 ，其物理意义为：在序列 中，第 时刻的隐状态为 、且第 时刻的隐状态为 的后验概率。

   则 M 步的估计值改写为：

   

   其中 为示性函数，其意义为：当 的第 时刻为 时，取值为 1；否则取值为 0 。

5. Baum-Welch算法：

   • 输入：观测数据

   • 输出：隐马尔可夫模型参数

   • 算法步骤：

     • 初始化：，选取 ，得到模型

     • 迭代，迭代停止条件为：模型参数收敛。迭代过程为：

       • 求使得 Q 函数取极大值的参数：

         

       • 判断模型是否收敛。如果不收敛，则 ，继续迭代。

     • 最终得到模型 。

2.3 预测问题

2.3.1 近似算法

1. 近似算法思想：在每个时刻 选择在该时刻最有可能出现的状态 ，从而得到一个状态序列 ，然后将它作为预测的结果。

2. 近似算法：给定隐马尔可夫模型 ，观测序列 ，在时刻 它处于状态 的概率为：

   

   在时刻 最可能的状态： 。

3. 近似算法的优点是：计算简单。

   近似算法的缺点是：不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际上不发生的部分。

   • 近似算法是局部最优（每个点最优），但是不是整体最优的。
   • 近似算法无法处理这种情况： 转移概率为 0 。因为近似算法没有考虑到状态之间的迁移。

2.3.2 维特比算法

1. 维特比算法用动态规划来求解隐马尔可夫模型预测问题。

   它用动态规划求解概率最大路径（最优路径），这时一条路径对应着一个状态序列。

2. 维特比算法思想：

   • 根据动态规划原理，最优路径具有这样的特性：如果最优路径在时刻 通过结点 ， 则这一路径从结点 到终点 的部分路径，对于从 到 的所有可能路径来说，也必须是最优的。

     

   • 只需要从时刻 开始，递推地计算从时刻 1 到时刻 且时刻 状态为 的各条部分路径的最大概率（以及取最大概率的状态）。于是在时刻 的最大概率即为最优路径的概率 ，最优路径的终结点 也同时得到。

   • 之后为了找出最优路径的各个结点，从终结点 开始，由后向前逐步求得结点 ，得到最优路径 。

3. 定义在时刻 状态为 的所有单个路径 中概率最大值为：

   

   它就是算法导论中《动态规划》一章提到的“最优子结构”

   则根据定义，得到变量 的递推公式：

   

4. 定义在时刻 状态为 的所有单个路径中概率最大的路径的第 个结点为：

   

   它就是最优路径中，最后一个结点（其实就是时刻 的 结点） 的前一个结点。

   

5. 维特比算法：

   • 输入：

     • 隐马尔可夫模型
     • 观测序列

   • 输出：最优路径

   • 算法步骤：

     • 初始化：因为第一个结点的之前没有结点 ，所以有：

       

     • 递推：对

       

     • 终止： 。

     • 最优路径回溯：对 ： 。

     • 最优路径 。