隐马尔可夫模型

一、隐马尔可夫模型HMM

  1. 隐马尔可夫模型(Hidden Markov model,HMM)是可用于序列标注问题的统计学模型,描述了由隐马尔可夫链随机生成观察序列的过程,属于生成模型。

  2. 隐马尔可夫模型:隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观察而产生观察随机序列的过程。

    • 隐藏的马尔可夫链随机生成的状态的序列称作状态序列。
    • 每个状态生成一个观测,而由此产生的观测的随机序列称作观测序列。
    • 序列的每一个位置又可以看作是一个时刻。

1.1 基本概念

  1. 是所有可能的状态的集合, 是所有可能的观测的集合,其中 是可能的状态数量, 是可能的观测数量。

    • 是状态的取值空间, 是观测的取值空间 。
    • 每个观测值 可能是标量,也可能是一组标量构成的集合,因此这里用加粗的黑体表示。状态值的表示也类似。
  2. 是长度为 的状态序列, 是对应的观测序列。

    • 是一个随机变量,代表状态
    • 是一个随机变量,代表观测
  3. 为状态转移概率矩阵

    其中 ,表示在时刻 处于状态 的条件下,在时刻 时刻转移到状态 的概率。

  4. 为观测概率矩阵

    其中 ,表示在时刻 处于状态 的条件下生成观测 的概率。

  5. 是初始状态概率向量: 是时刻 时处于状态 的概率。

    根据定义有:

  6. 隐马尔可夫模型由初始状态概率向量 、状态转移概率矩阵 以及观测概率矩阵 决定。因此隐马尔可夫模型 可以用三元符号表示,即 : 。其中 称为隐马尔可夫模型的三要素:

    • 状态转移概率矩阵 和初始状态概率向量 确定了隐藏的马尔可夫链,生成不可观测的状态序列。
    • 观测概率矩阵 确定了如何从状态生成观测,与状态序列一起确定了如何产生观测序列。
  7. 从定义可知,隐马尔可夫模型做了两个基本假设:

    • 齐次性假设:即假设隐藏的马尔可夫链在任意时刻 的状态只依赖于它在前一时刻的状态,与其他时刻的状态和观测无关,也与时刻 无关,即:

    • 观测独立性假设,即假设任意时刻的观测值只依赖于该时刻的马尔可夫链的状态,与其他观测及状态无关,即:

      .

1.2 生成算法

  1. 隐马尔可夫模型可以用于标注问题:给定观测的序列,预测其对应的状态序列。 如:词性标注问题中,状态就是单词的词性,观测就是具体的单词。在这个问题中:

    • 状态序列:词性序列 。

    • 观察序列:单词序列 。

    • 生成方式:

      • 给定初始状态概率向量 ,随机生成第一个词性。
      • 根据前一个词性,利用状态转移概率矩阵 随机生成下一个词性。
      • 一旦生成词性序列,则根据每个词性,利用观测概率矩阵 生成对应位置的观察,得到观察序列。
  2. 一个长度为 的观测序列的 HMM 生成算法:

    • 输入:

      • 隐马尔可夫模型
      • 观测序列长度
    • 输出:观测序列

    • 算法步骤:

      • 按照初始状态分布 产生状态

      • ,开始迭代。迭代条件为: 。迭代步骤为:

        • 按照状态 的观测概率分布 生成
        • 按照状态 的状态转移概率分布 产生状态

二、 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. 一些期望值:

    • 在给定观测 的条件下,状态 出现的期望值为:

    • 在给定观测 的条件下,从状态 转移的期望值:

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