HMM隐马尔可夫模型评估观察序列概率

2023-12-20 21:23:35

隐马尔可夫模型

定义

隐马尔科夫模型(Hidden Markov Model, HMM)是建模序列数据的图模型

在HMM模型存在隐藏状态 $\{\dots,x(t-1),x(t),x(t+1),\dots\}$ ，以及观测状态 $\{\dots,y(t-1),y(t),y(t+1),\dots\}$

设 $Q$ 为所有隐藏状态的集合， $V$ 为所有观测状态的集合，即
$Q=\{q_1,q_2,\ldots,q_N\},V=\{v_1,v_2,\ldots v_M\}$
设存在长度为 $T$ 的序列，其中 $I$ 对应的状态序列， $Q$ 是对应的观察序列
$I=\{i_1,i_2,\ldots,i_T\},O=\{o_1,o_2,\ldots o_T\}\quad i_t\in Q,o_t\in V$
其中HMM满足齐次马尔科夫链假设，即即任意时刻的隐藏状态只依赖于它前一个隐藏状态，一般来说, 给定状态 $q_t$ ，对于时刻 $s < t$ 和 $t < u$ ，则 $q_s$ 与 $q_u$ 相互独立。同时满足观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，即给定状态 $q_t$ ，对于输出状态 $v_s$ 与 $v_u$ 也相互独立

定义在 $t$ 时刻隐藏状态为 $i_t=q_j$ 到 $t + 1$ 时刻隐藏状态为 $i_{t+1}=q_i$ 的转移概率为 $a_{ij}$ ，即
$a_{ij}=P(i_{t+1}=q_j|i_t=q_i)$
同时 $a_{ij}$ 可以组成马尔科夫链的状态转移矩阵 $A$
$A=\begin{bmatrix}a_{ij}\end{bmatrix}_{N\times N}$
定义在 $t$ 时刻隐藏状态为 $i_t=q_j$ 观测到 $o_{t+1}=v_k$ 的概率为 $b_j(k)$ ，即
$b_j(k)=P(o_t=v_k|i_t=q_j)$
同时 $b_j(k)$ 可以组成马尔科夫链的观测概率矩阵 $B$
$B=\left[b_j(k)\right]_{N\times M}$
并定义在 $t = 1$ 时刻的隐藏状态概率分布 $\Pi$
$\Pi=\left[\pi(i)\right]_N\text{其中 }\pi(i)=P(i_1=q_i)$
可知一个HMM模型可以由隐藏状态初始概率分布 $\Pi$ , 状态转移概率矩阵 $A$ 和观测状态概率矩阵 $B$ 决定。 $\Pi,A$ 决定状态序列， $B$ 决定观测序列。因此，HMM模型可以由一个三元组 $\lambda$ 表示如下： $\lambda=(A,B,\Pi)$

直接计算

当给定模型HMM模型 $\lambda=(A,B,\Pi)$ 和观测序列 $O=\{o_1,o_2,\ldots o_T\}$ ，求观测序列 $O$ 在HMM中出现的概率 $P(O|\lambda)$

计算 $I=\{i_1,i_2,\ldots,i_T\}$ 出现的概率
$P(I|\lambda)=\pi_{i_1}a_{i_1i_2}a_{i_2i_3}\cdots a_{i_{T-1}i_T}$
其中观测序列 $O=\{o_1,o_2,\ldots o_T\}$ 在 $I=\{i_1,i_2,\ldots,i_T\}$ 情况下出现的概率
$P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2).\ldots b_{i_T}(o_T)$
根据联合概率公式可得
$P(O,I|\lambda)=P(I|\lambda)P(O|I,\lambda)=\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)\ldots a_{i_{T-1}i_T}b_{i_T}(o_T)$
然后计算边缘概率
$P(O|\lambda)=\sum_{I}P(O,I|\lambda)=\sum_{i_1,i_2,..,i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1,i_2}b_{i_2}(o_2)\ldots a_{i_{T-1} i_T}b_{i_T}(o_T)$
虽然直接计算方法有效，但是如果隐藏状态数 $N$ 非常多，此时预测状态有 $N^T$ 种组合，算法的时间复杂度是 $O(TN^T)$ 阶的。因此对于一些隐藏状态数极少的模型，我们可以直接计算来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。

前向计算

前向概率：时刻 $t$ 部分观测序列为 $O=\{o_1,o_2,\ldots o_t\}$ ，且隐藏状态为 $q_i$ 的概率为
$\alpha_{t}(i)=P(o_{1},o_{2},\ldots o_{t},i_{t}=q_{i}|\lambda)$
可得时刻 $t$ 部分观测序列为 $O=\{o_1,o_2,\ldots o_t\}$ ，隐藏状态为 $q_j$ 且 $t + 1$ 时刻隐藏状态为 $q_i$ 的概率为 $\alpha_{t}(j)a_{ji}$ ，可推出时刻 $t$ 部分观测序列为 $O=\{o_1,o_2,\ldots o_t\}$ ，且 $t + 1$ 时刻隐藏状态为 $q_i$ 的概率为 $\sum_{j=1}^{N}\alpha_{t}(j)a_{ji}$ ，若 $t + 1$ 时刻的观测状态为 $o_{t+1}$ ，则可以得到 $t + 1$ 时刻观测序列为 $O=\{o_1,o_2,\ldots o_{t+1}\}$ 且 $t + 1$ 时刻隐藏状态为 $q_i$ 的概率为：
$\alpha_{t+1}\left(i\right)=\left[\sum_{j=1}^{N}\alpha_{t}(j)a_{ji}\right]b_{i}\left(o_{t+1}\right.)$
由此得到了从前向概率的递推表达式

算法描述

输入：HMM模型 $\lambda=(A,B,\Pi)$ ,观测序列 $O=(o_1,o_2,\ldots o_T)$
输出：观测序列概率 $P(O|\lambda)$ 。

初值

$\begin{aligned}\alpha_1(i)=\pi_ib_i(o_1),\quad i=1,2,\cdots,N\end{aligned}$

递推对 $t=1,2,\cdots,T-1$

$\alpha_{t+1}\left(i\right)=\left[\sum_{j=1}^{N}\alpha_{t}(j)a_{ji}\right]b_{i}\left(o_{t+1}\right.),\quad i=1,2,\dots,N$

终止

$P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)$

算法时间复杂度是 $O(TN^2)$

后向计算

后向概率：时刻 $t + 1$ 到最后时刻 $T$ 的部分观测序列为 $\{o_{t+1},o_{t+2},\ldots o_T\}$ ，且时刻 $t$ 的隐藏状态为 $q_i$ 的概率为
$\beta_{t}(i)=P(o_{t+1},o_{t+2},\ldots o_T|i_{t}=q_{i},\lambda)$
可得 $t + 2$ 到最后时刻 $T$ 观测状态为 $\{o_{t+2},o_{t+3},\ldots{o}_T\}$ ， $t$ 时刻隐藏状态为 $q_i$ ， $t + 1$ 时刻隐藏状态为 $q_j$ 的概率为 $a_{ij}\beta_{t+1}(j)$ ，当 $t + 1$ 时刻观测到的状态 $o_{t+1}$ ，此时概率为 $a_{ij}b_j(o_{t+1})\beta_{t+1}(j)$ ，可得时刻 $t$ 到最后时刻 $T$ 的部分观测序列为 $\{o_{t+1},o_{t+2},\ldots o_T\}$ ，且时刻 $t$ 的隐藏状态为 $q_i$ 的概率为
$\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j)$
算法描述

输入：HMM模型 $\lambda=(A,B,\Pi)$ ,观测序列 $O=(o_1,o_2,\ldots o_T)$
输出：观测序列概率 $P(O|\lambda)$

初始化时刻 $T$ 的各个隐藏状态后向概率：

$\beta_T(i)=1,\:i=1,2,\ldots N$

递推时刻 $T-1,T-2,\ldots1$ 时刻的后向概率：

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

计算最终结果：

$P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)$