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

博文

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

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

本文接上篇继续讨论隐马尔科夫模型,上篇详见:

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

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

本篇主要探讨隐马尔科夫模型三个基本问题中的第一个问题,后续还会接着讨论另外的两个,敬请关注

3. 隐马尔科夫模型的三个基本问题

Problem 1. 评估问题 (Evaluation Problem)

给定模型λ= (A, B, π),以及观测链O,求解此模型出现观测链O的概率P(O|λ)? (注:用上篇中年轮与气温的例子来说,已知状态转移矩阵A,观测矩阵B,以及初始状态分布π,求特定的观测链,例如S-M-S-L这种年轮排列,出现的概率)

 

方案1. 枚举法

为了解决这个问题,我们最开始可能想到的是简单粗暴的枚举法(概率法):列举出所有可能的状态链(例如H-H-H-HH-H-H-CH-H-C-H …),对应出现S-M-S-L这种年轮排列的概率,再把所有的概率相加,自然就可以得到在P(O|λ)

如果按照数学公式来计算,思路如下:

先定义状态链X = (X0, X1, X2, …, XT-1)

(1)只看HMM图中虚线上半部分,相当于给定模型λ,求状态链X的概率,很显然

(2)只看HMM图中虚线下半部分,相当于在给定了状态链X和模型λ,求观测链O的概率。很显然

(3) 按联合概率的定义有

当然,这个公式也可以推导出来,具体如下:

(4)再按概率公式展开P(O|λ),即

也即,

这种算法虽然直观,但是计算量非常大,是O(TNT)。在概念上可行,但是计算不上可行。

 

方案2. 前向算法(Forward Algorithm)

既然叫做隐马尔科夫链,作为一条链我们就可以用链的方式来算。链的特征是当前的状态仅与上一个状态有关。

Q1:还是用年轮与气温的例子来说,如何计算第四年观测到大年轮(L)的概率?

A1:它是以下两部分之和:其一是第四年气温为高温(H),观测为大年轮(L)的概率,其二是第四年气温为低温(C),观测为大年轮(L)的概率。

Q2:这时有人要问了,第四年气温为低温(C)的概率是多少?

A2:它是以下两部分之和:其一是第三年气温为H的概率乘以气温由高温(H)转低温(C)的概率,其二是第三年气温为低温(C)的概率乘以气温由低温(C)转低温(C)的概率。

Q3:紧接着问,第三年气温为高温(H)的概率是多少?

A3:这是第三年观测为小年轮(S),气温为H的概率!

Q4:那么第三年观测为小年轮(S)的概率又是多少?

A4:很好,回头看看第一问Q1,这个问题又回来了!相当于整个计算递归(轮回)了一遍。

用图来说明如下:

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

先定义前向概率αt(i),它表示到时刻t时,观测序列为o1, o2, o3, …,ot且状态为qi的概率,记作:

思路采用的是递归(从最后一个状态到第一个状态),但是计算的时候反过(从最一个状态到最后一个状态)

1. 计算初始的前向概率α0(i)

2. 联系t-1时刻的前向概率αt-1(j)t时刻的前向概率αt(i)

注:它由两部分组成,红色框中的部分表明t-1时刻各个状态对应的前向概率与其状态转移概率之积再求和,前面t-1的事就搞定了;蓝色框内的是当前时刻(t时刻) Ot这种观测值的第i个状态的概率

3. 当运行到最后一个前向概率时,所有的计算都完成了,即获取到P(O|λ),具体的式子如下:

直接概率法的复杂度是O(TNT),而前向算法的复杂度是O(N2T),当T较大时可以大大节省计算开销。


参考材料:

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-1189654.html

上一篇:隐马尔科夫模型简介(一)
下一篇:隐马尔科夫模型简介(三)

0

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

数据加载中...

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

GMT+8, 2019-11-12 13:40

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部