HMM数学推导—Evaluation问题

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

HMM数学推导—Evaluation问题
HMM数学推导—开篇
2020-03-05 数学之美
机器学习（四）支持向量机
03-隐马可夫模型（HMM）二
Beam Search
2021-03-25
2019-01-25
04 隐马尔可夫模型 - HMM的三个问题 - 预测问题 - V
03 隐马尔可夫模型 - HMM的三个问题 - 学习问题 - B

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

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问题
本章涉及到的知识点清单：1、前向概率的定义2、前向概率的递推关系推导3、前向概率求解4、Forward算法流程5、...
HMM数学推导—开篇
本章涉及到的知识点清单：1、HMM定义2、变量定义3、两个假设4、三个基本问题5、极大似然优化失效一、HMM定义...
2020-03-05 数学之美
今天从吴军老师的《数学之美》的 HMM 模型，看到b站up主讲 EM 算法，重温了二话不说就是一顿推导的美妙感觉。...
机器学习（四）支持向量机
支持向量机的数学推导较复杂，本篇文章不对支持向量机的数学原理进行推导。仅仅从支持向量机要解决的问题出发，大致推导支...
03-隐马可夫模型（HMM）二
1、HMM问题一：求观测序列问题（直接计算）首先我们回顾下HMM模型的问题一。这个问题是这样的。我们已知HMM模...
Beam Search
Beam Search 数学推导：
2021-03-25
两个个简单的思考在学习数学的过程中总是刻意的回避推导类的问题其他的还好一到推导类的问题就犯困大...
2019-01-25
写出 svm 原始问题转换至其对偶问题的数学推导过程： 1 导包： from sklearn import svm...
04 隐马尔可夫模型 - HMM的三个问题 - 预测问题 - V
03 隐马尔可夫模型 - HMM的三个问题 - 学习问题八、HMM的三个问题 - 预测问题问题：在观测序列已...
03 隐马尔可夫模型 - HMM的三个问题 - 学习问题 - B
02 隐马尔可夫模型 - HMM的三个问题 - 概率计算问题七、HMM的三个问题 - 学习问题若训练数据包含观...