隐马尔可夫模型的预测

【概述】

对于隐马尔可夫模型的预测问题，即：已知模型 $\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^{\ast }$，从而得到一个状态序列 $I^{\ast }=(i_1^{\ast },i_2^{\ast },\cdots ,i_T^{\ast })$，将其作为预测结果

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

$${\gamma }_t(i)=\frac{{\alpha }_t(i){\beta }_t(i)}{\sum _{j=1}^N{\alpha }_t(j){\beta }_t(j)}$$

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

$$i_t^{\ast }=\arg \underset{1\le i\le N}{max}{y}_t(i),t=1,2,\cdots ,T$$

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

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

【Viterbi 算法】

基本思想

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

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

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

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

算法流程

首先给出两个变量的定义

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

$${\delta }_t(i)=\underset{i_1,i_2,\cdots ,i_{t-1}}{max}P(i_t=i,i_{t-1},\cdots ,i_1,o_t,\cdots ,o_1|\lambda ),i=1,2,\cdots ,N$$

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

$$\begin{array}{rl}{\delta }_{t+1}(i)& =\underset{i_1,i_2,\cdots ,i_t}{max}P(i_{t+1}=i,i_t,\cdots ,i_1,o_{t+1},\cdots ,o_1|\lambda )\\ & =[\underset{1\le j\le N}{max}{\delta }_t(j)a_{ji}]\cdot b_i(o_{t+1})\\ & i=1,2,\cdots ,N;t=1,2,\cdots ,T-1\end{array}$$

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

$${\mathrm{\Psi }}_t(i)=\arg \underset{1\le j\le N}{max}{\delta }_{t-1}(j)a_{ji}i=1,2,\cdots ,N$$

---

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

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

算法步骤：

Step 1：算法初始化

$$\begin{array}{rlr}{\delta }_1(i)& ={\pi }_i{b}_i(o_1),& i=1,2,\cdots ,N\\ {\mathrm{\Psi }}_1(i)& =0,& i=1,2,\cdots ,N\end{array}$$

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

$$\begin{array}{rlr}{\delta }_t(i)& =[\underset{1\le j\le N}{max}{\delta }_{t-1}(j)a_{ji}]\cdot b_i(o_{t+1}),& i=1,2,\cdots ,N\\ {\mathrm{\Psi }}_t(i)& =\arg \underset{1\le j\le N}{max}{\delta }_{t-1}(j)a_{ji}& i=1,2,\cdots ,N\end{array}$$

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

$$\begin{array}{rl}{P}^{\ast }& =\underset{1\le i\le N}{max}{\delta }_T(i)\\ i_T^{\ast }& =\arg \underset{1\le i\le N}{max}{\delta }_T(i)\end{array}$$

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

$$i_t^{\ast }={\mathrm{\Psi }}_{t+1}(i_{t+1}^{\ast })$$

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