【隱馬爾可夫模型】隱馬爾可夫模型的觀測序列概率計算算法及例題詳解

【隱馬爾可夫模型】用前向算法計算觀測序列概率P（O｜λ）???????

【隱馬爾可夫模型】用后向算法計算觀測序列概率P（O｜λ）

隱馬爾可夫模型是關于時序的概率模型，描述由一個隱藏的馬爾可夫鏈隨機生成不可觀測的狀志的序列，再由各個狀態隨機生成一個觀測而產生觀測的序列的過程。模型本身屬于生成模型，表示狀態序列和觀測序列的聯合分布，但是狀態序列是隱藏不可觀測的。

觀測序列概率的計算需要有效的算法支撐。

模型 $\lambda=(A,B,\pi)$ ，A為狀態轉移概率矩陣，B為觀測概率矩陣，π 為初始狀態概率向量

直接計算法

直接計算法主要用于闡釋思路，概念上可行但計算上不可行（計算量過大）

思路：

1、列舉所有可能的長度為 $T$ 的狀態序列 $I=(i_1,i_2,...,i_T)$

2、求各個狀態序列 $I$ 與觀測序列 $O=(o_1,o_2,\cdots,o_T)$ 的聯合概率 $P(O,I|\lambda)$

3、對所有可能的狀態序列求和，得到 $P(O|\lambda).$

輸入：隱馬爾可夫模型 $\lambda=(A,B,\pi)$ 和觀測序列 $O=(o_1,o_2,\cdots,o_T)$

輸出：貫徹序列 $O$ 出現的概率,

1）狀態序列 $I=(i_1,i_2,\cdots,i_T)$ 的概率

$P(I\mid\lambda)=\pi_{i_{1}}a_{i_{1}i_{2}}a_{i_{2}i_{3}}\cdots a_{i_{T-1}i_{T}}$

2）對固定的狀態序列 $I=(i_1,i_2,\cdots,i_T)$ , 觀測序列 $O=(o_1,o_2,\cdots,o_T)$ 的概率

$P(O\mid I,\lambda)=b_{i_{1}}(o_{1})b_{i_{2}}(o_{2})\cdotp\cdotp\cdotp b_{i_{T}}(o_{T})$

3） $O$ 和 $I$ 同時出現的聯合概率

$\begin{aligned} P(O,I|\lambda)& =P(O|I,\lambda)P(I|\lambda)=\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)\cdots a_{i_{T-1}i_T}b_{i_T}(o_T) \end{aligned}$

4）對所有可能的狀態序列 $I$ 求和，得到觀測序列 $O$ 的概率

$\begin{aligned} P(O|\lambda)& =\sum_{I}P(O\mid I,\lambda)P(I\mid\lambda) =\sum_{i_{1},i_{2},\cdots,i_{T}}\pi_{i_{1}}b_{i_{1}}(o_{1})a_{i_{2}}b_{i_{2}}(o_{2})\cdots a_{i_{r-1}i_{T}}b_{i_{T}}(o_{T}) \end{aligned}$

實際操作中，步驟四的計算量很大，是 $O(TN^T)$ 階的

前向算法

前向概率：?給定隱馬爾可夫模型 $\lambda=(A,B,\pi)$ ，定義到時刻t 部分觀測序列為 $o_1,o_2,\cdots,o_t$ 且狀態為 $q_i$ ?的概率為前向概率，記作 $\alpha_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i|\lambda)$

輸入：隱馬爾可夫模型 $\lambda=(A,B,\pi)$ 和觀測序列 $O=(o_1,o_2,\cdots,o_t)$

輸出：觀測序列 $O$ 出現的概率 $P(O|\lambda)$

1）初值， $\alpha_1(i)=\pi_ib_i(o_1),\quad i=1,2,\cdots,N$

2）遞推，對 $t=1,2,\cdots,T-1,$

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

3）終止?

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

計算量 $O(TN^2)$ 階

例：盒子和球模型 $\lambda=(A,B,\pi)$ ，狀態集合 $Q=\{1,2,3\}$ ，觀測集合 $V=\{Red,White\}$

$\left.A=\left[\begin{array}{ccc}0.5&0.2&0.3\\0.3&0.5&0.2\\0.2&0.3&0.5\end{array}\right.\right],\quad B=\left[\begin{array}{ccc}0.5&0.5\\0.4&0.6\\0.7&0.3\end{array}\right],\quad\pi=\left[\begin{array}{c}0.2\\0.4\\0.4\end{array}\right]$

$T=3,O=(\text{Red,White,Red})$ ,用前向算法求 $P(O|\lambda)$

解答：

1）初值?

$\begin{aligned}\alpha_1(1)&=\pi_1b_1(o_1)=0.10\\\alpha_1(2)&=\pi_2b_2(o_1)=0.16\\\alpha_1(3)&=\pi_3b_3(o_1)=0.28\end{aligned}$

A為狀態轉移概率矩陣，B為觀測概率矩陣，π 為初始狀態概率向量，O為觀測序列

$a_{ij}$ ?——A的i行j列， $b_i(o_j)$ ——B的i行 $o_j$ 列

例如 $o_1$ 對應Red，對應觀測集合V的第一列，對應觀測概率矩陣B的第一列

2）遞推

$\begin{aligned} \alpha_{2}(1)& =\left[\sum_{i=1}^{3}\alpha_{1}(i)a_{i1}\right]b_{1}(o_{2})=0.154\times0.5=0.077 \\ \alpha_{2}(2)& =\left[\sum_{i=1}^3\alpha_1(i)a_{i2}\right]b_2(o_2)=0.184\times0.6=0.1104 \\ \alpha_{2}(3)& =\left[\sum_{i=1}^3\alpha_1(i)a_{i3}\right]b_3(o_2)=0.202\times0.3=0.0606\\ \\ \alpha_{3}(1)& =\left[\sum_{i=1}^3\alpha_2(i)a_{i1}\right]b_1(o_3)=0.04187 & \\ \alpha_{3}(2)& =\left[\sum_{i=1}^3\alpha_2(i)a_{i2}\right]b_2(o_3)=0.03551 \\ \alpha_{3}\left(3\right)& =\left[\sum_{i=1}^3\alpha_2(i)a_{i3}\right]b_3(o_3)=0.05284 \end{aligned}$

$b_i(o_j)$ B的i行 $o_j$ 列， $b_1(o_3)$ 就是對應B的第一行第一列的元素

3）終止

$P(O|\lambda)=\sum_{i=1}^3\alpha_3(i)=0.13022$

遞推至T=3，對前向概率求和得到 $P(O|\lambda)$

后向算法

后向概率：?給定隱馬爾可夫模型 $\lambda=(A,B,\pi)$ ，定義到時刻t 狀態為 $q_i$ ?的條件下，從t+1到T的部分觀測序列為 $o_{t+1},o_{t+2},\cdots,o_T$ 的概率為后向概率，記作

$\beta_t(i)=P(o_{t+1},o_{t+2},\cdots,o_T|i_t=q_i,\lambda)$

輸入：隱馬爾可夫模型 $\lambda=(A,B,\pi)$ 和觀測序列 $O=(o_{t+1},o_{t+2},\cdots,o_T)$

輸出：觀測序列 $O$ 出現的概率 $P(O|\lambda)$

1）初值， $\beta_T(i)=1,\quad i=1,2,\cdots,N$

2）遞推，對 $t=T-1,T-2,\cdots,1$

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

3）終止?

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

計算量 $O(TN^2)$ 階

例：盒子和球模型 $\lambda=(A,B,\pi)$ ，

$T=4,O=(\text{Red,White,Red,White})$ ,用后向算法求 $P(O|\lambda)$

解答：

1）初值?

$\mathrm{\beta}_4\left(\mathrm{i}\right)=1\quad\mathrm{~i}=1,2,3$

A為狀態轉移概率矩陣，B為觀測概率矩陣，π 為初始狀態概率向量，O為觀測序列

從T=4向下遞推，一般設后向概率初值為1

2）遞推

遞推至 $\beta _1$ 終止

$\begin{aligned} \beta_3\left(1\right)& =\sum_{\mathrm{j}=1}^3\mathrm{a}_{1\mathrm{j}}\mathrm{b}_{\mathrm{j}}\left(\mathrm{O}_{4}\right)\beta_{4}\left(\mathrm{j}\right)=0.25+0.12+0.09=0.46 \\ \beta_{3}\left(2\right)& \mathrm{=\sum_{j=1}^3a_{2j}b_{j}\left(O_{4}\right)\beta_{4}\left(j\right)=0.15+0.3+0.06=0.51} \\ \beta_{3}\left(3\right)& =\sum_{\mathrm{j}=1}^3\mathrm{a}_{3\mathrm{j}}\mathrm{b}_{\mathrm{j}}\left(\mathrm{O}_{4}\right)\mathrm{\beta}_{4}\left(\mathrm{j}\right)=0.1+0.18+0.15=0.43 \\ \end{aligned}$

$\begin{aligned}\beta_2\left(1\right)&=\sum_{\mathrm{j}=1}^3\mathrm{a}_{1\mathrm{j}}\mathrm{b}_{\mathrm{j}}\left(\mathrm{O}_3\right)\beta_3\left(\mathrm{j}\right)=0.25*0.46+0.08*0.51+0.21*0.43=0.2461\\\beta_2\left(2\right)&=\sum_{\mathrm{j}=1}^3\mathrm{a}_{2\mathrm{j}}\mathrm{b}_{\mathrm{j}}\left(\mathrm{O}_3\right)\beta_3\left(\mathrm{j}\right)=0.15*0.46+0.2*0.51+0.14*0.43=0.2312\\\beta_2\left(3\right)&=\sum_{\mathrm{j}=1}^3\mathrm{a}_{3\mathrm{j}}\mathrm{b}_{\mathrm{j}}\left(\mathrm{O}_3\right)\beta_3\left(\mathrm{j}\right)=0.1*0.46+0.12*0.51+0.35*0.43=0.2577\end{aligned}$

$\begin{aligned}&\mathrm{\beta_1\left(1\right)=\sum_{j=1}^3a_{1j}b_j\left(O_2\right)\beta_2\left(j\right)=0.25*0.2461+0.12*0.2312+0.09*0.2577=0.112462}\\&\mathrm{\beta_1\left(2\right)=\sum_{j=1}^3a_{2j}b_j\left(O_2\right)\beta_2\left(j\right)=0.15*0.2461+0.3*0.2312+0.06*0.2577=0.121737}\\&\mathrm{\beta_1\left(3\right)=\sum_{j=1}^3a_{3j}b_j\left(O_2\right)\beta_2\left(j\right)=0.1*0.2461+0.18*0.2312+0.15*0.2577=0.104881}\end{aligned}$

$a_{ij}$ ?——A的i行j列， $b_i(o_j)$ ——B的i行 $o_j$ 列

$b_i(o_j)$ B的i行 $o_j$ 列， $b_1(o_3)$ 就是對應B的第一行第一列的元素

3）終止

$\mathrm{P}\left(\mathrm{O}|\lambda)\right.=\sum_{i=1}^3\pi_\mathrm{i}b_\mathrm{i}\left(\mathrm{O}_1\right)\beta_1\left(\mathrm{i}\right)=0.0600908$

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/214192.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/214192.shtml
英文地址，請注明出處：http://en.pswp.cn/news/214192.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！