隐马尔科夫模型(HMM)详解(共8页).docx

《隐马尔科夫模型(HMM)详解(共8页).docx》由会员分享，可在线阅读，更多相关《隐马尔科夫模型(HMM)详解(共8页).docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上马尔科夫过程马尔科夫过程可以看做是一个自动机，以一定的概率在各个状态之间跳转。考虑一个系统，在每个时刻都可能处于N个状态中的一个，N个状态集合是 S1,S2,S3,.SN。我们现在用q1,q2,q3,qn来表示系统在t=1,2,3,n时刻下的状态。在t=1时，系统所在的状态q取决于一个初始概率分布PI，PI(SN)表示t=1时系统状态为SN的概率。马尔科夫模型有两个假设：1.系统在时刻t的状态只与时刻t-1处的状态相关；（也称为无后效性）2.状态转移概率与时间无关；（也称为齐次性或时齐性）第一条具体可以用如下公式表示：P(qt=Sj|qt-1=Si,qt-2=Sk,)

2、= P(qt=Sj|qt-1=Si)其中，t为大于1的任意数值，Sk为任意状态第二个假设则可以用如下公式表示：P(qt=Sj|qt-1=Si)= P(qk=Sj|qk-1=Si)其中，k为任意时刻。下图是一个马尔科夫过程的样例图：可以把状态转移概率用矩阵A表示，矩阵的行列长度均为状态数目，aij表示P(Si|Si-1)。隐马尔科夫过程与马尔科夫相比，隐马尔科夫模型则是双重随机过程，不仅状态转移之间是个随机事件，状态和输出之间也是一个随机过程，如下图所示：此图是从别处找来的，可能符号与我之前描述马尔科夫时不同，相信大家也能理解。该图分为上下两行，上面那行就是一个马尔科夫转移过程，下面这一行则是输

3、出，即我们可以观察到的值，现在，我们将上面那行的马尔科夫转移过程中的状态称为隐藏状态，下面的观察到的值称为观察状态，观察状态的集合表示为 O=O1,O2,O3,OM。相应的，隐马尔科夫也比马尔科夫多了一个假设，即输出仅与当前状态有关，可以用如下公式表示：P(O1,O2,Ot|S1,S2,St)=P(O1|S1)*P(O2|S2)*.*P(Ot|St)其中，O1,O2,Ot为从时刻1到时刻t的观测状态序列，S1,S2,St则为隐藏状态序列。另外，该假设又称为输出独立性假设。举个例子举个常见的例子来引出下文，同时方便大家理解！比如我在不同天气状态下去做一些事情的概率不同，天气状态集合为下雨，阴天，

4、晴天，事情集合为宅着，自习，游玩。假如我们已经有了转移概率和输出概率，即P(天气A|天气B)和P(事情a|天气A)的概率都已知道，那么则有几个问题要问（注意，假设一天我那几件事情中的一件），1.假如一周内的天气变化是 下雨-晴天-阴天-下雨-阴天-晴天-阴天，那么我这一周 自习-宅着-游玩-自习-游玩-宅着-自习的概率是多大？2.假如我这一周做事序列是 自习-宅着-游玩-自习-游玩-宅着-自习，不知道天气状态的情况下这个做事序列的概率是多大？3.假如一周内的天气变化是 下雨-晴天-阴天-下雨-阴天-晴天-阴天，那我们这一周最有可能的做事序列是什么？4.假如我这一周做事序列是 自习-宅着-游玩-

5、自习-游玩-宅着-自习，那么这一周的天气变化序列最有可能是什么？对于第一个问题，我想大家应该都能很快知道怎么算。（啥？不知道，答案在本文最后）隐马模型基本要素及基本三问题综上所述，我们可以得到隐马尔科夫的基本要素，即一个五元组S,N,A,B,PI；S：隐藏状态集合；N：观察状态集合；A：隐藏状态间的转移概率矩阵；B：输出矩阵（即隐藏状态到输出状态的概率）；PI：初始概率分布（隐藏状态的初始概率分布）；其中，A、B、PI称为隐马尔科夫的参数，用X表示。由上述问题可以引出隐马尔科夫的三个基本问题的其中两个，下文中为了简便，将隐马尔科夫模型简称为HMM(Hiden Markov Model)。HMM

6、的三个基本问题是：1. 给定模型（五元组），求某个观察序列O的概率（样例问题2）（即已知模型参数，计算某一特定输出序列的概率.通常使用解决.）2.给定模型和观察序列O，求可能性最大的隐藏状态序列（样例问题4）。（即已知模型参数，寻找最可能的能产生某一特定输出序列的隐含状态的序列.通常使用Viterbi算法解决.）3.对于给定的观察序列O，调整HMM的参数，使观察序列出现的概率最大。（即已知输出序列，寻找最可能的状态转移以及输出概率.通常使用Baum-Welch算法以及Reversed Viterbi算法解决.）前向算法对于第一个基本问题，计算公式为：即对于观察序列O，我们需要找出所有可能的隐藏

7、状态序列S，计算出在给定模型下S输出为O的概率（就是样例问题一啊），然后计算概率之和。直观上看，假如序列O的长度为T，模型的隐藏状态集合大小为N，那么一共有NT个可能的隐藏状态序列，计算复杂度极高O(NT)，暴力算法太慢了。解决方案就是动态规划（Dynamic Programming）。假设观察序列为O1,O2,O3,.,Ot. 在时刻i（1i=t）时，定义C为产生序列O1,O2,Oi且Si=Sk的概率：其中，Sk为任意一个隐藏状态值。则C(i+1,Sr)的计算公式为：其中，Sr为任意一个隐藏状态值。A为转移概率。B为隐藏状态到观察状态的概率。为了便于理解，还是看图：C(3,下雨)考虑了t=1

8、和t=2的所有组合情况，同时也是C(4,下雨|阴天|晴天)的子问题。C(3,阴天)和C(3,晴天)也是如此计算，而C(i+1,Sr)计算公式则可以表示成：由图知：C(4,阴天)=C(3,下雨)*A(下雨,阴天)+C(3,阴天)*A(阴天,阴天)+C(3,晴天)*A(晴天,阴天)*B(阴天,自习)。通过图片，大家应该能直观的理解该算法了，该算法又称为前向算法，那还有后向算法？是的，后向算法就是这个算法倒过来嘛，也是动态规划，这里就不赘述了，有兴趣的看参考文献。另外，这里没有讲解如何初始化概率，也可以去参考文献里查证。维特比算法现在，HMM的第一个基本问题解决了，下面开始解决第二个问题，第二个问题

9、又称为解码问题，同样的，暴力算法是计算所有可能性的概率，然后找出拥有最大概率值的隐藏状态序列。与问题一的暴力解决方案类似，复杂度为O(NT)。那应该用什么方案呢？毫无疑问，还是动态规划啊！假设观察序列为O1,O2,O3,.,Ot. 在时刻i（1i=2时，节点中保存着一些小节点，这些小节点的数目即为上一个状态的状态数目，小节点的值意义为到达该时刻状态为Sr且前一时刻状态为Sk时能够产生状态序列的最大概率。比如背景为绿色的小节点的值的意义为时刻3为下雨，时刻2为下雨时去自习-宅着-游玩的最大概率。（注意，节点表示时刻i时某个状态，小节点表示节点中保存的前一状态的节点，比如绿色的那个节点）。对于时刻i（i2），每个小节点的概率为那么对于时刻i+1,小节点的概率为：然后，从时刻t中寻找最大的小节点回溯即可。样例问题一答案上面样例问题中第一问的答案是:概率：P=P(下雨)*P(晴天|下雨)*P(阴天|晴天)*P(自习|下雨)*P(宅着|晴天)*P(自习|阴天) 注：其中，第一项P(下雨)为初始概率分布（还记得马尔科夫的t=1时刻的概率分布么？）。参考文献：一种非时齐的隐马尔科夫模型及其在音字转换中的应用统计语言模型的研究与应用统计和规则相结合的语言模型的中文输入法中的应用基于Markov链的整句输入算法研究与实现参考文献及本文pdf下载地址：专心-专注-专业