隐马尔可夫模型的预测

【概述】

对于隐马尔可夫模型的预测问题，即：已知模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\cdots,o_T)$，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I=(i_1,i_2,\cdots,i_T)$

有两种预测算法：

• 近似算法：计算简单，但由于预测的状态序列可能有实际不发生的部分，故不能保证预测的状态序列整体是最有可能的状态序列
• Viterbi 算法：计算较为复杂，本质是用动态规划求概率最大路径，一条路径对应一条状态

【近似算法】

近似算法的思想是：在每个 $t$ 时刻，选择在该时刻最有可能出现的状态 $i_t^{*}$，从而得到一个状态序列 $I^{*}=(i_1^{*},i_2^{*},\cdots,i_T^{*})$，将其作为预测结果

对于给定的隐马尔可夫模型 $\lambda=(A,B,\pi)$ 和观测序列 $O$，在时刻 $t$ 处于状态 $q_i$ 的概率 $\gamma_t(i)$ 是：

$$\gamma_t(i) = \frac{\alpha_t(i)\beta_t(i)}{\sum\limits_{j=1}^N \alpha_t(j)\beta_t(j)}$$

在每一时刻 $t$，最有可能的状态 $i_t^{*}$ 是：

$$i_t^{*} = \arg \max_{1\leq i\leq N} y_t(i),\quad t=1,2,\cdots,T$$

从而得到状态序列 $I^{*}=(i_1^{*},i_2^{*},\cdots,i_T^{*})$

对于上述方法得到的状态序列，可能存在转移概率 $a_{ij}=0$ 的相邻状态

【Viterbi 算法】

基本思想

Viterbi 算法的基本思想是动态规划，根据动态规划的原理，最优路径具有这样的特性：如果最优路径在时刻 $t$ 通过结点 $i_t^{*}$，那么这一路径是从结点 $i_t^{*}$ 到终点 $i_T^{*}$ 的部分路径，而且对于从 $i_t^{*}$ 到 $i_T^{*}$ 的所有可能的部分路径来说，必须是最优的

因为假如不是这样，那么从 $i_t^{*}$ 到 $i_T^{*}$ 就有另一条更好的部分路径存在，如果把它和从 $i_1^{*}$ 到达 $i_t^{*}$ 的部分路径连接起来，就会形成一条比原来的路径更优的路径，这是矛盾的

依据这一原理，只需从 $t=1$ 时刻开始，递推地计算在 $t$ 时刻状态为 $i$ 的各条部分路径的最大概率，直至得到 $t=T$ 时刻状态为 $i$ 的各条路径的最大概率，时刻 $t=T$ 的最大概率即为最优路径的概率 $P^{*}$，最优路径的终结点 $i_T^{*}$ 也可同时得到

之后，为了找出最优路径的各个结点，从终结点 $i_T^{*}$ 开始，由后向前逐步求得结点 $i_{T-1}^{*},i_{T-2}^{*},\cdots,i_1^{*}$，得到最优路径 $I^{*}=(i_1^{*},i_2^{*},\cdots,i_T^{*})$

算法流程

首先给出两个变量的定义

定义在时刻 $t$ 状态为 $i$ 的所有单个路径 $(i_1,i_2,\cdots,i_t)$ 中概率最大值为：

$$\delta_t(i) = \max_{i_1,i_2,\cdots,i_{t-1}} P(i_t=i,i_{t-1},\cdots,i_1,o_t,\cdots,o_1|\lambda),\quad i=1,2,\cdots,N$$

根据定义，可得 $\delta$ 的递推公式：

$$\begin{align*} \delta_{t+1}(i) &= \max_{i_1,i_2,\cdots,i_{t}} P(i_{t+1}=i,i_{t},\cdots,i_1,o_{t+1},\cdots,o_1|\lambda) \\ &= [\max_{1\leq j\leq N} \delta_t(j)a_{ji}] \cdot b_i(o_{t+1}) \\ &i=1,2,\cdots,N;t=1,2,\cdots,T-1 \end{align*}$$

定义在时刻 $t$ 状态为 $i$ 的所有单个路径 $(i_1,i_2,\cdots,i_{t-1},i)$ 中概率最大的路径的第 $t-1$ 个结点为：

$$\Psi_t(i) = \arg \max_{1\leq j\leq N} \delta_{t-1}(j)a_{ji} \quad i=1,2,\cdots,N$$

---

输入：隐马尔可夫模型 $\lambda=(A,B,\pi)$，观测序列 $O=(o_1,o_2,\cdots,o_T)$

输出：最优路径 $I^{*}=(i_1^{*},i_2^{*},\cdots,i_T^{*})$

算法步骤：

Step 1：算法初始化

$$\begin{align*} \delta_1(i) &= \pi_i b_i(o_1),&i=1,2,\cdots,N \\ \Psi_1(i) &= 0,&i=1,2,\cdots,N \\ \end{align*}$$

Step 2：对 $t=2,3,\cdots,T$ 递推

$$\begin{align*} \delta_t(i) &= [\max_{1\leq j\leq N} \delta_{t-1}(j)a_{ji}] \cdot b_i(o_{t+1}), & i=1,2,\cdots,N \\ \Psi_t(i) &= \arg \max_{1\leq j\leq N} \delta_{t-1}(j)a_{ji} & i=1,2,\cdots,N \end{align*}$$

Step 3：计算最优路径的概率 $P^{*}$ 与终结点 $i_T^{*}$

$$\begin{align*} P^{*} &= \max_{1\leq i\leq N} \delta_T(i) \\ i_T^{*} &= \arg \max_{1\leq i\leq N} \delta_T(i) \end{align*}$$

Step 4：最优路径回溯，对 $t=T-1,T-2,\cdots,1$

$$i_t^{*} = \Psi_{t+1}(i_{t+1}^{*})$$

求得最优路径 $I^{*}=(i_1^{*},i_2^{*},\cdots,i_T^{*})$