HMM数学推导—Evaluation问题

作者: PrivateEye_zzy | 来源:发表于2022-01-21 17:12 被阅读0次

本章涉及到的知识点清单：

1、前向概率的定义

2、前向概率的递推关系推导

3、前向概率求解 $P(O|\lambda)$

4、Forward算法流程

5、后向概率的定义

6、后向概率的递推关系推导

7、后向概率求解 $P(O|\lambda)$

8、Backward算法流程

9、案例演示

10、Evaluation问题总结

一、前向概率的定义

前向概率的定义

为了解决Evaluation问题的高时间复杂度，我们引入一个前向概率 $\alpha_{t}(i)$ ，如上图所示， $\alpha_{t}(i)$ 表示 $1,2,...,t$ 时刻的观测 $o_{1},o_{2},...,o_{t}$ ，以及 $t$ 时刻的隐变量状态 $i_{t}=q_{i}$ ，在给定参数 ${\lambda }$ 下的联合概率，即

t时刻的前向概率

易知： $\alpha_{t}(i)$ 可以用 $T*N$ 的矩阵表示

二、前向概率的递推关系推导

通过前向概率的定义，可以推导出它的递推关系

由 $\alpha_{t}(i)$ 可得到 $\alpha_{t+1}(j)$ 的表达

t+1时刻的前向概率

将 $\alpha_{t+1}(j)$ 展开化简得：

前向概率递推关系

（PS：由于HMM中隐变量是离散序列，故 $\int \Rightarrow \sum$ ）

上述化简使用了观测独立假设和齐次Markov假设，可见 $\alpha_{t+1}(j)$ 和 $\alpha_{t}(i)$ 之间存在着具体的递推关系。且根据前向概率的定义，当处于初始时刻 $t=1$ 时，前向概率 $\alpha_{1}(i)$ 为：

初始时刻t=1的前向概率

则利用这个递推关系和 $\alpha_{1}(i)$ ，就可以从前向后分别求出 $\alpha_{2}(i)\rightarrow \alpha_{3}(i)\rightarrow ...\rightarrow \alpha_{T}(i)$

三、 $\alpha_{t}(i)$ 前向概率求解 $P(O|\lambda)$

回归Evaluation问题，很自然的引入隐变量 $i_{T}$ ，经过简单的化简得：

Evaluation问题计算

以上就是利用前向概率 $\alpha_{t}(i)$ 的定义和递推关系，逐步向前递推，最终计算出 $P(O|\lambda)$ ，即Forward算法，显然，其时间复杂度已经降低至

四、Forward算法流程

输入：模型参数 $\lambda$ ，观测序列 $O$

输出： $P(O|\lambda)$ 概率值

Step1：初始值赋值

Forward算法step1

Step2：递推计算

Forward算法step2

Step3：计算 $P(O|\lambda)$

Forward算法step3

五、后向概率的定义

受前向概率定义的启发，我们可以从另一个角度定义出后向概率

后向概率定义

如上图所示，我们引入后向概率 $\beta_{t}(i)$ ，表示 $t+1,t+2,...,T$ 时刻的观测 $o_{t+1},o_{t+2},...,o_{T}$ ，以及 $t$ 时刻的隐变量状态 $i_{t}=q_{i}$ ，在给定参数 $\lambda$ 下的联合概率，即

t时刻的后向概率

同理，易知 $\beta_{t}(i)$ 可以用 $T*N$ 的矩阵表示

六、后向概率的递推关系推导

通过后向概率的定义，可以推导出它的递推关系

由 $\beta_{t}(i)$ 可以得到 $\beta_{t+1}(j)$ 的表达式

t+1时刻的后向概率

将 $\beta_{t}(i)$ 展开化简得：

后向概率递推

上述蓝色部分的化简，利用了概率图D-Seperation中的head-to-tail，可见 $\beta_{t}(i)$ 与 $\beta_{t+1}(j)$ 之间存在着具体的递推关系。且根据后向概率定义，当处于末尾时刻 $t=T$ 时，后向概率 $\beta_{T}(i)$ 为：

末尾时刻t=T的后向概率

则利用这个递推关系和 $\beta_{T}(i)$ ，就可以从后往前分别求出 $\beta_{T-1}(i)\rightarrow \beta_{T-2}(i)\rightarrow ...\rightarrow \beta_{1}(i)$

七、 $\beta_{t}(i)$ 后向概率求解 $P(O|\lambda)$

同前向概率一样，回归Evaluation问题，很自然的引入隐变量 $i_{1}$ ，经过简单的化简得：

Evaluation问题计算

以上就是利用后向概率 $\beta_{t}(i)$ 的定义和递推关系，逐步向后递推，最终计算出 $P(O|\lambda)$ ，即Backward算法，显然，其时间复杂度依然已经降低至 $O(TN^{2})$

八、Backward算法流程

输入：模型参数 $\lambda$ ，观测序列 $O$

输出： $P(O|\lambda)$ 概率值

Step1：初始值赋值

Backward算法step1

Step2：递推计算

Backward算法step2

Step3：计算 $P(O|\lambda)$

Backward算法step3

九、案例演示

最后我们使用李航老师——《统计学方法》中的例子：

例：考虑盒子和球模型 $\lambda = (\pi,A,B)$ ，状态集合 $Q=\{1,2, 3 \}$ ，观测集合 $V=\{红,白 \}$

$A = \begin{bmatrix}0.5 & 0.2 & 0.3\\ 0.3& 0.5 & 0.2\\ 0.2 & 0.3 & 0.5 \end{bmatrix}$ ， $B = \begin{bmatrix}0.5 & 0.5\\ 0.4& 0.6\\ 0.7 & 0.3 \end{bmatrix}$ ， $\pi = (0.2,0.4,0.4)^{T}$

设观测序列长度 $T=3$ ，观测序列为： $O=(红,白,红)$ ，求： $P(O|\lambda)$

根据Forward算法理论，我们可以很方便的使用Python语言编程实现求解Evaluation问题

Forward算法

Forward算法计算出的 $P(O|\lambda)$

Forward算法

同理，Backward算法也很容易实现

Backward算法

Backward算法计算出的 $P(O|\lambda)$

Backward算法

十、Evaluation问题总结

（1）Forward和Backward两个算法利用HMM的两个假设：齐次Markov假设和观测独立假设，可以非常有效的简化概率推导

（2）利用Forward和Backward算法可将Evaluation问题的时间复杂度由 $O(N^{T})$ ，降低至 $O(TN^{2})$

（3）利用前向概率和后向概率的定义，对HMM后续的Learning问题的推导有着极大的帮助

案例代码参加：HMM数学推导—Evaluation问题

HMM数学推导—Evaluation问题

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读