`

隐马尔可夫模型中的Viterbi算法zz

阅读更多

 

这篇文章简单描述一下Viterbi算法——一年之前我听过它的名字,直到两周之前才花了一点时间研究了个皮毛,在这里做个简单检讨。先用一句话来简单描述一下:给出一个观测序列o1,o2,o3 …,我们希望找到观测序列背后的隐藏状态序列s1, s2, s3, …;Viterbi以它的发明者名字命名,正是这样一种由动态规划的方法来寻找出现概率最大的隐藏状态序列(被称为Viterbi路径)的算法。

这里需要抄一点有关隐马可夫序列(HMMHidden Markov Model)的书页来解释一下观测序列和隐藏状态序列。

首先从最简单的离散Markov过程入手,我们知道,Markov随机过程具有如下的性质:在任意时刻,从当前状态转移到下一个状态的概率与当前状态之前的那些状态没有关系。所以,我们可以用一个状态转移概率矩阵来描述它。假设我们有n个离散状态S1, S2,Sn,我们可以构造一个矩阵A,矩阵中的元素aij表示从当前状态Si下一时刻迁移到Sj状态的概率。

但是在很多情况下,Markov模型中的状态是我们观察不到的。例如,容器与彩球的模型:有若干个容器,每个容器中按已知比例放入各色的彩球(这样,选择了容器后,我们可以用概率来预测取出各种彩球的可能性);我们做这样的实验,实验者从容器中取彩球——先选择一个容器,再从中抓出某一个球,只给观察者看球的颜色;这样,每次取取出的球的颜色是可以观测到的,即o1, o2,…,但是每次选择哪个容器是不暴露给观察者的,容器的序列就组成了隐藏状态序列S1, S2,Sn。这是一个典型的可以用HMM描述的实验。

HMM有几个重要的任务,其中之一就是期望通过观察序列来猜测背后最有可能的隐藏序列。在上面的例子中,就是找到我们在实验中最有可能选择到的容器序列。Viterbi正是用来解决这个问题的算法。HMM另外两个任务是:a) 给定一个HMM,计算一个观测序列出现的可能性;b)已知一个观测序列,HMM参数不定,如何优化这些参数使得观测序列的出现概率最大。解决前一个问题可以用与Viberbi结构非常类似的Forward算法来解决(实际上在下面合二为一),而后者可以用Baum-Welch/EM算法来迭代逼近。

Wiki上抄一个例子来说明Viterbi算法。

假设你有一个朋友在外地,每天你可以通过电话来了解他每天的活动。他每天只会做三种活动之一——Walk, Shop, Clean。你的朋友从事哪一种活动的概率与当地的气候有关,这里,我们只考虑两种天气——Rainy, Sunny。我们知道,天气与运动的关系如下:

 

 

Rainy

Sunny

Walk

0.1

0.6

Shop

0.4

0.3

Clean

0.5

0.1

 

例如,在下雨天出去散步的可能性是0.1

而天气之前互相转换的关系如下,(从行到列)

 

 

Rainy

Sunny

Rainy

0.7

0.3

Sunny

0.4

0.6

 

例如,从今天是晴天而明天就开始下雨的可能性是0.4

同时为了求解问题我们假设初始情况:通话开始的第一天的天气有0.6的概率是Rainy,有0.4概率是SunnyOK,现在的问题是,如果连续三天,你发现你的朋友的活动是:Walk->Shop->Clean;那么,如何判断你朋友那里这几天的天气是怎样的?

解决这个问题的python伪代码如下:

def forward_viterbi(y, X, sp, tp, ep):

   T = {}

   for state in X:

       ##          prob.      V. path  V. prob.

       T[state] = (sp[state], [state], sp[state])

   for output in y:

       U = {}

       for next_state in X:

           total = 0

           argmax = None

           valmax = 0

           for source_state in X:

               (prob, v_path, v_prob) = T[source_state]

               p = ep[source_state][output] * tp[source_state][next_state]

               prob *= p

               v_prob *= p

               total += prob

               if v_prob > valmax:

                   argmax = v_path + [next_state]

                   valmax = v_prob

           U[next_state] = (total, argmax, valmax)

       T = U

   ## apply sum/max to the final states:

   total = 0

   argmax = None

   valmax = 0

   for state in X:

       (prob, v_path, v_prob) = T[state]

       total += prob

       if v_prob > valmax:

           argmax = v_path

           valmax = v_prob

   return (total, argmax, valmax)几点说明:

算法对于每一个状态要记录一个三元组:(prob, v_path, v_prob),其中,prob是从开始状态到当前状态所有路径(不仅仅

是最有可能的viterbi路径)的概率加在一起的结果(作为算法附产品,它可以输出一个观察序列在给定HMM下总的出现概率,即forward算法的输出),v_path是从开始状态一直到当前状态的viterbi路径,v_prob则是该路径的概率。

算法开始,初始化T T是一个Map,将每一种可能状态映射到上面所说的三元组上)  三重循环,对每个一活动y,考虑下一步每一个可能的状态next_state,并重新计算若从T中的当前状态state跃迁到next_state概率会有怎样的变化。跃迁主要考虑天气转移(tp[source_state][next_state])与该天气下从事某种活动(ep[source_state][output])的联合概率。所有下一步状态考虑完后,要从T中找出最优的选择viterbi路径——即概率最大的viterbi路径,即上面更新Map U的代码U[next_state] = (total, argmax, valmax)

算法最后还要对T中的各种情况总结,对total求和,选择其中一条作为最优的viterbi路径。

算法输出四个天气状态,这是因为,计算第三天的概率时,要考虑天气转变到下一天的情况。

通过程序的输出可以帮助理解这一过程:

observation=Walk

        next_state=Sunny

                state=Sunny

                        p=0.36

                        triple=(0.144,Sunny->,0.144)

                state=Rainy

                        p=0.03

                        triple=(0.018,Rainy->,0.018)

        Update U[Sunny]=(0.162,Sunny->Sunny->,0.144)

        next_state=Rainy

                state=Sunny

                        p=0.24

                        triple=(0.096,Sunny->,0.096)

                state=Rainy

                        p=0.07

                        triple=(0.042,Rainy->,0.042)

        Update U[Rainy]=(0.138,Sunny->Rainy->,0.096)

observation=Shop

        next_state=Sunny

                state=Sunny

                        p=0.18

                        triple=(0.02916,Sunny->Sunny->,0.02592)

                state=Rainy

                        p=0.12

                        triple=(0.01656,Sunny->Rainy->,0.01152)

        Update U[Sunny]=(0.04572,Sunny->Sunny->Sunny->,0.02592)

        next_state=Rainy

                state=Sunny

                        p=0.12

                        triple=(0.01944,Sunny->Sunny->,0.01728)

                state=Rainy

                        p=0.28

                        triple=(0.03864,Sunny->Rainy->,0.02688)

        Update U[Rainy]=(0.05808,Sunny->Rainy->Rainy->,0.02688)

observation=Clean

        next_state=Sunny

                state=Sunny

                        p=0.06

                        triple=(0.0027432,Sunny->Sunny->Sunny->,0.0015552)

                state=Rainy

                        p=0.15

                        triple=(0.008712,Sunny->Rainy->Rainy->,0.004032)

        Update U[Sunny]=(0.0114552,Sunny->Rainy->Rainy->Sunny->,0.004032)

        next_state=Rainy

                state=Sunny

                        p=0.04

                        triple=(0.0018288,Sunny->Sunny->Sunny->,0.0010368)

                state=Rainy

                        p=0.35

                        triple=(0.020328,Sunny->Rainy->Rainy->,0.009408)

        Update U[Rainy]=(0.0221568,Sunny->Rainy->Rainy->Rainy->,0.009408)

final triple=(0.033612,Sunny->Rainy->Rainy->Rainy->,0.009408)所以,最终的结果是,朋友那边这几天最可能的天气情况是Sunny->Rainy->Rainy->Rainy,它有0.009408的概率出现。而我们算法的另一个附带的结论是,我们所观察到的朋友这几天的活动序列:Walk->Shop->Clean在我们的隐马可夫模型之下出现的总概率是0.033612

 

参考文献

 http://www.ece.ucsb.edu/Faculty/Rabiner/ece259/Reprints/tutorial%20on%20hmm%20and%20applications.pdf 

http://en.wikipedia.org/wiki/Viterbi_algorithm 

http://googlechinablog.com/2006/04/blog-post_17.html

分享到:
评论

相关推荐

    隐马尔可夫模型的简介以及实例介绍以及三个主要算法

    隐马尔可夫模型的三个主要算法,即前向算法、后向算法和Viterbi算法,每种算法都有其独特的应用场景和计算目的。前向算法主要是用来计算在给定模型参数下,观察到特定观察序列的概率,这在评估模型的输出概率时非常...

    HMM隐马尔可夫模型用于中文分词

    隐马尔可夫模型(Hidden Markov Model,HMM)是一种统计模型,被广泛应用于模式识别、自然语言处理等领域。HMM的核心思想是通过一个可以观察的马尔可夫过程来描述一个隐含的状态序列,其中状态不可直接观察到,但每...

    隐马尔可夫模型的算法分析

    1. 详细讨论了隐马尔科夫模型的原理和算法,包括前向变量算法、后向变量算法、Viterbi算法和Baum-Welch算法。 2. 分析了隐马尔科夫模型的几个重要问题,包括计算观察序列概率、估计最优状态序列和训练模型参数。 3...

    隐马尔可夫模型前向算法matlab程序-forward algorithm.m

    隐马尔可夫模型前向算法matlab程序-forward algorithm.m 这个是隐马尔可夫模型前向算法程序,根据一个示例用matlab编写的,希望对大家有用。由于在线时间不够,所以图贴不上来,我只能以附件的形式发上来了。。。

    一种基于隐马尔可夫模型的人脸识别方法.pdf

    本文提出了一种基于隐马尔可夫模型的人脸识别方法,该方法利用人脸隐马尔可夫模型的结构特征和Viterbi算法的特点,对特征观察序列进行分割,并使用部分序列对所有隐马尔可夫模型递进地计算最大相似度,同时排除...

    隐马尔可夫模型源代码(matlab)

    在MATLAB的压缩包文件中,“隐马尔可夫模型源代码(matlab)”很可能包含了实现上述步骤的函数或脚本。这些源代码可能包括初始化模型的函数、Baum-Welch训练函数、Viterbi解码函数和Forward-Backward评估函数等。通过...

    对经典隐马尔可夫模型学习算法的改进.7z

    对经典隐马尔可夫模型学习算法的改进 改进了两个基本假设。

    隐马尔可夫模型及其在自然语言处理中的应用

    隐马尔可夫模型及其在自然语言处理中的应用

    HMM隐马尔可夫模型MATLAB实现

    隐马尔可夫模型(Hidden Markov Model,简称HMM)是概率统计领域中的一个重要模型,尤其在自然语言处理、语音识别、生物信息学等领域有着广泛的应用。在MATLAB环境中,我们可以利用其强大的数学计算能力和丰富的函数...

    连续型隐马尔可夫模型(HMM)参数迭代算法

    ### 连续型隐马尔可夫模型(HMM)参数迭代算法 #### 知识点解析 **一、隐马尔可夫模型(HMM)基础** 隐马尔可夫模型是一种统计模型,用于描述一个含有未知参数的马尔可夫过程。这种模型在自然语言处理、语音识别...

    10.2 基于隐马尔可夫模型(HMM)的孤立字语音识别_隐马尔可夫模型(HMM)的孤立字语音识别_

    在本主题中,我们将深入探讨基于隐马尔可夫模型(HMM)的孤立字语音识别方法,并结合MATLAB程序实现进行讲解。 隐马尔可夫模型(Hidden Markov Model, HMM)是概率统计模型,广泛应用于自然语言处理、生物信息学...

    对经典隐马尔可夫模型学习算法的改进

    ### 隐马尔可夫模型(HMM)学习算法的改进:理论与实践 #### 引言 隐马尔可夫模型(Hidden Markov Model, HMM)自诞生以来,在多个领域展现了其强大的应用潜力,尤其是在语言识别、生物信息学(如DNA序列比对、...

    第20章-隐马尔可夫模型

    隐马尔可夫模型(Hidden Markov Model, HMM)作为一种重要的概率图模型,在序列预测问题中扮演着核心角色。它能够有效地处理一系列数据点间的关系,并且尤其适用于语音识别、自然语言处理等领域的序列标注任务。 ##...

    一种基于隐马尔可夫模型的人脸识别方法_王志超

    总结,本文介绍了一种改进的基于隐马尔可夫模型的人脸识别方法,该方法通过特征观察序列的分割和优化的Viterbi算法实现识别效率的提升。这种创新技术对于应对人脸识别中的实时性和准确性需求有着重要的实践意义,为...

Global site tag (gtag.js) - Google Analytics