luria的个人博客分享 http://blog.sciencenet.cn/u/luria

博文

隐马尔科夫模型简介(三)

已有 303 次阅读 2019-7-15 20:33 |个人分类:Algorithm|系统分类:科研笔记| 马尔科夫, 稳马尔可夫, 隐马尔科夫, HMM, Hidden Markov Models

本篇继续讨论隐马尔科夫模型的第二个基本问题——解码问题

在讨论之前,还是欢迎我们的主角——隐马尔科夫模型(HMM)出场!

 

Problem 2. 解码问题 (Decoding Problem)

已知HMM模型λ=(A, B, π),以及观测序列O,求最可能的状态序列。之前的博文http://blog.sciencenet.cn/blog-2970729-1188964.html 中讨论的问题就属于这一类问题。

其实这个问题和之前讨论的评估问题(第一类问题)相比,已知的条件是一致的,只是所求不同。因此理论上也可以用枚举法,事实上,在第一篇隐马尔科夫模型简介博文中我们也这样做了。同样因为计算量比较大,所以枚举法并不可取。在此介绍一种目前主流的解决方案,叫做维特比算法(Viterbi Algorithm),算法演示如下:

Viterbi Algorithm.gif


Viterbi算法的思想是步步为营,每一步都是当前最佳的路。如果用气温和年轮的例子来说:

1. 首先写出第一年的情况

因为第一年观测到的是小年轮,于是δ1(H)表示第一年观测到小年轮的同时气温为高温的概率:

δ1(H) = 0.6×0.1=0.06

注:其中0.6表示初始为H的概率,0.1表示观测到小年轮而且为高温的概率。

同时,第一年观测到小年轮而且气温为低温的概率为:

δ1(C) = 0.4×0.7=0.28

δ1(C) >δ1(H),因此第一年为低温的可能性更大,所以下一步计算时不考虑第一年为高温的情况

2. 计算第二年的情况

第二年观测到的是中年轮(M),于是

δ2(H) =δ1(C)×0.4×0.4 = 0.0448

注:第一个0.4表示由低温转高温的概率,第二个0.4为观测为中年轮,且状态为高温的概率

同理,δ2(C) =δ1(C)×0.6×0.2 = 0.0336

δ2(H) >δ2(C),因此第二年为高温的可能性更大,所以下一步计算时不考虑第二年为低温的情况。

3. 计算第三年的情况

第三年观测为小年轮,计算方法同第二年,直接写出结果如下:

δ3(H) =δ2(H)×0.7×0.1 = 0.003136

δ3(C) =δ2(H)×0.3×0.7 = 0.009408

δ3(C) >δ3(H),因此第三年是低温的可能更高,所以下一步计算时不考虑第三年为高温的情况。

4. 计算第四年的情况

第四年观测为大年轮,计算方法同第二年,直接写出结果如下:

δ4(H) =δ3(C)×0.4×0.5 = 0.0018816

δ4(C) =δ3(C)×0.6×0.1 = 0.00056448

δ3(H) >δ3(C),因此第四年是高温的可能更高。综上,这四年最可能的状态是C-H-C-H,这一结果和第一篇隐马尔科夫简介博文(http://blog.sciencenet.cn/blog-2970729-1188964.html)中HMM算法得到的结果一致。但是通过计算过程来看,更加高效。

如果用数学公式表示,如下:

 

参考材料:

https://sens.tistory.com/m/320?category=501289

Guy Leonard Kouemou. History and Theoretical Basics of Hidden Markov Models

Mark Stamp. A Revealing Introduction to Hidden Markov Models

李航. 统计学习方法



http://blog.sciencenet.cn/blog-2970729-1189655.html

上一篇:隐马尔科夫模型简介(二)
下一篇:EM算法(期望最大化算法)简介

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-8-21 02:43

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部