HMM数学推导—Evaluation问题

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

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问题

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,080评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,422评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,630评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,554评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,662评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,856评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,014评论 3赞 408
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,752评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,212评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,541评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,687评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,347评论 4赞 331
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,973评论 3赞 315
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,777评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,006评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,406评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,576评论 2赞 349

HMM数学推导—Evaluation问题

推荐阅读更多精彩内容