《统计学习方法》隐马尔可夫模型部分读书笔记

0. 引入

我们举一个例子，如果我们想要预测股市的走向。如果使用朴素贝叶斯算法，则需要有一个强假设“各特征为独立分布”，但显然，每一日的股票走向是相互影响的。因此，如果用一句通俗易懂的文字描述隐马尔可夫模型，就是该模型会（仅）参考前一次的分布对下一步的分布进行预测。

查看源图像


2. 隐马尔可夫模型

2.1 名词介绍

我们将事物的变化抽象为状态的变化，对应观测值的变化。同一事物所有可能的状态的集合记作 Q；所有可能的观测值的集合记作 V。结合时间维度，我们将事物随时间变化的状态序列集合记为 I；将事物随时间变化的观测序列集合记为 O。

同时定义了状态转移矩阵 A(N*N)，反映了从迁移状态 $i_1$ 转变到下一状态 $i_2$ 的概率。N 为状态类别的数量。其中 $a_{1j}$ 表示 $a_{1j}=P(i_2=q_j|i_1=q_1)$，即上一状态为 $q_1$ 且当前状态为 $q_j$ 时的概率，即表格的第一行为当前状态，第一列为上次状态。

$i_2=q_1$ $i_2=q_2$ … $i_2=q_N$
$i_1=q_1$ $a_{11}$ $a_{12}$ $a_{1j}$
$i_1=q_2$
…
$i_1=q_N$

也定义了观测概率矩阵 B(N*M)，反映了从状态 $i_1$ 到观测结果 $o_1$ 的对应关系。N 为状态类别的数量，M 为观测数1。

$o_1=v_1$ $o_1=v_2$ … $o_1=v_m$
$i_1=q_1$ $a_{11}$ $a_{12}$ $a_{1j}$
$i_1=q_2$
…
$i_1=q_N$

定义了初始状态概率向量（因为在第一个时刻并没有前一状态）：

$\pi = \begin{bmatrix} \pi_1\\ \pi_2\\ … \\ \pi_N \end{bmatrix}=\begin{bmatrix} P(i_1=q_1)\\ P(i_1=q_2) \\ … \\ P(i_1=q_N) \end{bmatrix} $

2.2 隐马尔可夫模型

我们画出隐马尔可夫模型的示意图：

image-20210608120327255

可以发现隐马尔可夫链由状态变量链和观测变量链组成，而状态变量链的递推受约束于状态转移矩阵 A；每一个观测变量受约束于其对应的状态变量，因而受约束于观测概率矩阵 B。因此隐马尔可夫模型可以用 $\lambda=(A,B,\pi)$ 来表示。

2.3 隐马尔可夫的两个基本假设

  • 齐次马尔可夫性假设：假设隐马尔可夫链在任意时刻 t 的状态只能依赖于前一时刻的状态，与其他时刻的状态及观测无关，也与时间 t 无关。
  • 观测独立性假设：假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测和状态无关。

3. 隐马尔可夫的三个基本问题

3.1 概率计算问题

概率计算问题解决的是给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,…,o_T)$，计算在模型 $\lambda$ 下观测序列 O 出现的概率 $P(O|\lambda)$。

3.1.1 直接计算法

通过列举所有可能的状态序列列表 I，求各个状态序列 I 与观测序列 O 的联合概率 。

image-20210608154301221

但是这个方法的计算量很大，时间复杂度为 $O(TN^T)$。

3.1.2 前向算法

我们定义前向概率：给定隐马尔可夫模型 $\lambda$，定义时刻 t 观测序列为 $o_1,o_2,…,o_t$ 且状态为 $q_i$ 的概率为前向概率，记作 $\alpha_t(i)=P(o_1,o_2,…,o_t,i_t=q_i|\lambda)$

算法（观测序列概率的前向算法）：

输入：隐马尔可夫模型 $\lambda$，观测序列 O；

输出：观测序列概率 $P(O|\lambda)$

  1. 初值：$\alpha_1(i)=\pi_ib_i(o_1)$

  2. 递推：对 $t=1,2,…,T-1$

    $\alpha_{t+1}(i)=[\sum_{j=1}^N\alpha_t(j)a_{ji}]b_i(o_{t+1})$

  3. 终值：$P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)$

image-20210608170544099

时间复杂度为 $O(N^2T)$

3.1.3 后向算法

我们定义后向概率：给定隐马尔可夫模型 $\lambda$，定义在时刻 t 状态为 $q_i$ 的条件下，从 t+1 到 T 的部分观测序列为 $o_{t+1},o_{t+2},…,o_T$ 的概率，记作 $\beta_t(i)=P(o_{t+1},o_{t+2},..,o_T|i_t=q,\lambda)$

算法（观测序列概率的后向算法）：

输入：隐马尔可夫模型 $\lambda$，观测序列 O；

输出：观测序列概率 $P(O|\lambda)$

  1. 初值：$\beta_T(i)=1$

  2. 对 $t=T-1,T-2,…,1$

    $\beta_t(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j)$

  3. 终值：$P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)$

image-20210628111835743

3.2 学习问题

学习问题是已知观测序列 $O=(o_1,o_2,…,o_T)$，估计模型 $\lambda=(A,B,\pi)$ 参数，使得在模型下观测序列概率 $P(O|\lambda)$ 最大，即用极大似然估计的方法估计参数。

3.2.1 监督学习方法

此处的训练数据为观测序列和对应的状态序列，即 ${(O_1,I_1),(O_2,I_2),…,(O_S,I_S)}$ 。可以使用极大似然估计方法来估计隐马尔可夫模型的参数。

  1. 转移概率 $a_{ij}$ 的估计

    image-20210628114128973

  2. 观测概率 $b_j(k)$ 的估计

    image-20210628114749674

  3. 初始状态概率 $\pi_i$ 的估计 $\hat \pi_i$ 为 S 个样本中初始状态为 $q_i$ 的频率

3.2.2 无监督学习方法（Baum-Welch）

由于监督学习需要使用标注的训练数据，而人工标注训练数据往往代价很高，有时会利用无监督学习的方法。

不难发现，隐马尔可夫模型是一个含有隐变量的概率模型 $P(O|\lambda)=\sum_{I}P(O|I,\lambda)P(I|\lambda)$，他的参数学习可以使用 EM 算法实现。（我们的目标是学习隐马尔可夫模型 $\lambda=(A,B,\pi)$ 的参数，状态序列数据 I 为不可观测的隐数据）

  1. 确定完全数据的对数似然函数 $log P(O,I|\lambda)$

  2. EM 算法的 E 步：求 Q 函数 $Q(\lambda, \overline{\lambda})$

    image-20210630093439226

  3. EM 算法的 M 步：极大化 Q 函数，求模型参数 $A,B,\pi$

    依次求偏导并令其结果为 0，求解参数。

3.3 预测问题

预测问题也称解码问题，已知模型 $\lambda=(A,B,\pi)$ 参数和观测序列 $O=(o_1,o_2,…,o_T)$，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I=(i_1,i_2,…,i_T)$。即给定观测序列，求最有可能的对应的状态序列。

  • 维比特算法

    维比特算法即用动态规划求概率最大路径（最优路径）。（一条路径对应一个状态序列）

    image-20210630095130731

    首先导入两个变量 $\delta$ 和 $\phi$。

    • 定义在时刻 t 状态为 i 的所有单个路径 $(i_1,i_2,…,i_t)$ 中概率最大值为 $\delta_t(i)=max_{i_1,i_2,…,i_{t-1}}P(i_t=i,i_{t-1},…,i_1,o_t,…,o_1|\lambda)$。

      由此可以得到变量 $\delta$ 的递推公式：

      $\delta_{t+1}(i)=max_{i_1,i_2,…,i_t}P(i_{t+1}=i,i_t,…,i_1,o_{t+1},…,o_1|\lambda)$

      $=max_{1\leq j\leq N}[\delta_t(j)a_{ji}]b_i(o_{t+1})$

    • 定义在时刻 t 状态为 i 的所有单个路径 $(i_1,i_2,…,i_{t-1},i)$ 中概率最大的路径的第 t-1 个节点为 $\phi_t(i)=arg \ max_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}]$

    输入：模型 $\lambda=(A,B,\pi)$ 和观测 $O=(o_1,o_2,…,o_T)$

    输出：最优路径 $I=(i_1,i_2,…,i_T)$

    1. 初始化：

      $\delta_1(i)=\pi_ib_i(o_1)$，$i=1,2,…,N$

      $\phi_1(i)=0$，$i=1,2,…,N$

    2. 递推。对 $t=2,3,…,T_j$

      在时刻 t 所有状态为 i 的所有路径中概率最大值：$\delta_1(i)=max_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}]b_i(o_t)$，$i=1,2,…,N$

      用于存最优路径：$\phi_t(i)=arg \ max_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}]$，$i=1,2,…,N$

    3. 终止

      $P^*=max_{1\leq j\leq N}\ \delta_{T}(i)$

    4. 最优路径回溯。

      对 $t=T-1,T-2,…,1$，$i_t=\phi_{t+1}(i_{t+1})$


4. 总结

隐马尔可夫可以理解为朴素贝叶斯的一个改进，去除了强假设“各特征为独立分布”，（仅）参考前一次的分布对下一步的分布进行预测。

  • 我们可以通过直接概率计算（时间复杂度大），或是前向、后向方法计算在模型 $\lambda$ 下观测序列 O 出现的概率 $P(O|\lambda)$。

  • 然后通过上一步得到的观测序列 O，用于学习模型参数的训练数据。可分为监督学习（使用极大似然估计）和无监督学习（使用 EM 算法）。

  • 最后是使用训练好的模型进行预测。一般使用维比特算法（用动态规划求概率最大路径）。最终得到概率最大的路径（即每一个时间节点下的估计值）