隐马尔科夫模型详解

《隐马尔科夫模型详解》由会员分享，可在线阅读，更多相关《隐马尔科夫模型详解（11页珍藏版）》请在金锄头文库上搜索。

1、马尔科夫过程马尔科夫过程可以看做是一个自动机，以一定的概率在各个状态之间跳转。考虑一个系统，在每个时刻都可能处于N个状态中的一个，N个状态集合 是S1,S2,S3,.SN。我们如今用 叽弘凡来表示系统在t=l,2,3,.n时刻下的 状态。在t=1时，系统所在的状态q取决于一个初始概率分布PI, PI(SN)表示t=1 时系统状态为SN的概率。马尔科夫模型有两个假设：1. 系统在时刻t的状态只与时刻t-1处的状态相关；也称为无后效性2. 状态转移概率与时间无关；也称为齐次性或时齐性第一条详细可以用如下公式表示：P(qt=Sj|qt-1=Siqt-2=Sk，)=P(qt=Sj|qt-1=Si)其中

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

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

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

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

6、。HMM的三个根本问题是：1给定模型(五元组，求某个观察序列O的概率(样例问题2即模型参数，计算某一特定输出序列的概率.通常使用forward算法解 决2. 给定模型和观察序列O,求可能性最大的隐藏状态序列(样例问题4。 即模型参数，寻找最可能的能产生某一特定输出序列的隐含状态的序 列.通常使用Viterbi算法解决.3. 对于给定的观察序列O,调整HMM的参数，使观察序列出现的概率 最大。即输出序列，寻找最可能的状态转移以及输出概率通常使用 Baum-Welch 算法以及 Reversed Viterbi 算法解决.前向算法对于第一个根本问题，计算公式为：p(oix)=艺 p(of sm =

7、工 咔ss即对于观察序列0,我们需要找出所有可能的隐藏状态序列S,计算出在给 定模型下S输出为0的概率就是样例问题一啊，然后计算概率之和。直观上看，假设序列0的长度为T，模型的隐藏状态集合大小为N，那么一 共有Nt个可能的隐藏状态序列，计算复杂度极高0(Nt)，暴力算法太慢了。解决方案就是动态规划Dynamic Programming。假设观察序列为O,O2,O3,.,Ot.在时刻i1viv=t时，定义C为产生序列 0,02,0）且Si=Sk的概率：其中，Sk为任意一个隐藏状态值。 那么C（i+1,Sr）的计算公式为：Nc（i + lfSr） = 2k=l宅若自习f雨下雨4.门习其中，Sr为任

8、意一个隐藏状态值。A为转移概率。B为隐藏状态到观察状态 的概率。为了便于理解，还是看图：下雨宅曲下雨F雨阴黄阳黃乂kkn /jC（3,下雨）考虑了 t=1和t=2的所有组合情况，同时也是C（4,下雨阴天晴天） 的子问题。C（3,阴天）和C（3,晴天）也是如此计算，而C（i+l,Sr）计算公式那么可以 表示成：下雨由图知：C（4,阴天）=C（3,下雨）*A（下雨，阴天）+C（3,阴天）*A（阴天，阴天）+C（3, 晴天）*A（晴天，阴天）*B （阴天，自习）。通过图片，大家应该能直观的理解该算法了，该算法又称为前向算法，那还 有后向算法？是的，后向算法就是这个算法倒过来嘛，也是动态规划，这里就不

9、 赘述了，有兴趣的看参考文献。另外，这里没有讲解如何初始化概率，也可以去 参考文献里查证。维特比算法如今，HMM的第一个根本问题解决了，下面开场解决第二个问题，第二个 问题又称为解码问题，同样的，暴力算法是计算所有可能性的概率，然后找出拥 有最大概率值的隐藏状态序列。与问题一的暴力解决方案类似，复杂度为O（Nt）。那应该用什么方案呢？毫无疑问，还是动态规划啊！假设观察序列为0,02,03,.,Ot.在时刻ilviv=t时，定义D为观察 0,02,0）且Si=Sk时产生该观察序列的最大概率：DCtSfe） = max 01,02,=几其中，S1,S2,.S（i-1）,在此时也已经可以得到，因为它

10、们是子问题啊。D（i += max.C（if * &童鞋们有么有看到该公式和上面的前向算法的差异？一个是对子问题求和， 一个是对子问题求最大值啊。当然，对于本问题来说，因为需要求出的是使得观察序列概率最大的隐藏状 态的序列，而不是最大概率，所以，在算法计算过程中，还需要记录前一个隐藏 状态的值。比方C（4，阴天）的最大值是有子问题C（3,下雨）得来的，那么需要在C（4, 阴天）这个节点记录前置状态为下雨。由于本算法和前向算法只是计算公式的不同，所以参考图是一样的，本算法 还可以参考上面算法的图；同样的，解释中没有提到初始化,可以去看参考文献。本算法又称为维特比算法，维特比是人名，这个老先生在上

11、世纪70年代创 造的该算法，但在现代人看来没什么神秘，可见问题在解决后可能会很简单，所 以不管是生活上还是学术上都不要畏惧，勇于战而后知战之易矣。相信理解了前向算法和维特比算法后，大家对样例问题2和样例问题4都能 解决了吧，对于样例问题3,其实跟维特比算法差不多，只不过是在观察状态的 空间中寻找最优解。对于根本问题三，本人还没有理解的太透彻，这里就不献丑了。应用说了这么多，HMM到底有什么应用呢？HMM 开场是在信息论中应用的，后来才被应用到自然语言处理还有其他 图像识别等各个方面。下面举两个例子说明他的应用，一个是输入法的整句解码, 一个是语音识别。有图为证：输入法把拼音看做是观察状态，需要

12、得到的汉字为隐藏状态，这样，输入法 的整句解码就变成了维特比解码，其转移概率即是二元语言模型，其输出概率即 是多音字对应不同拼音的概率。将上图中的拼音换成语音，就成了语音识别问题，转移概率仍然是二元语言 模型，其输出概率那么是语音模型，即语音和汉字的对应模型。扩展尽管HMM模型解决问题的效果已经很好了，但在学术上，精益求精，总的 想着方法使它变得更好。于是出现了针对HMM的各种扩展，这里介绍两种吧。一种是对三大假设的时齐性进展扩展，即假设状态转移概率与时间有关。这 在输入法中也有实际意义的，比方作为主语的ta他，它，她与名词ta塔 和动词ta踏，蹋等出现的位置一般是不一样的，主语一般出如今句首

13、或各种 从句的开场端；比方，我们会说他是谁，而极少说“塔是谁不排除有个别 奇葩的人的名字只有一个塔字，这样，我们在考虑tashishui这个拼音串时， 第一个字ta考虑他，它，她的概率会大一些，塔字的概率就会小一些。在这个方面，参考文献中的论文? 一种非时齐性的隐马尔科夫模型在音字转 换中的应用？中提到了一种实现方法，统计语言模型时，使用词语在句子中的位 置作为位置统计出词语的平均位置。在音字转换的语言模型的使用时，使用拼音 所对应的词语位置与平均位置的一个函数作为权重重新估计语言模型的概率。公 式如下：耳3U眩）=/凡“石）*畑烝“弘匚其中Pml(w1Iw2)是最大似然估计的转移概率，f(.

14、)那么为权重函数。另外一种扩展HMM的方法那么是对无后效性假设进展扩展，原来只假设某 状态只与前一状态有关，以致于只能使用语言模型中的二元模型，如今那么假设 某状态与前两个甚至更多个状态有关，这样就能使用高元语言模型了。如今我们 考虑只与前两个有关，那么这是虽然使用了三元模型，但是维特比算法的计算就 会出现问题，因为如今t时刻的状态的概率不仅要考虑t-1时刻的状态，还要考 虑t-2时刻的状态。用来解决维特比算法在三元模型下的问题也成为二阶HMM问题的方法 是：合并前后两个状态将二阶HMM问题转换成一阶HMM问题。合并二阶HMM下雨下枠姑犬对于合并二阶HMM来说，可以看下列图:11 族I丽Ia.

15、宅若*3.游旳i；为了简便起见，我把隐藏状态改为两个，下雨和晴天。由图可以看到，当t=2 时，节点中保存着一些小节点，这些小节点的数目即为上一个状态的状态数目， 小节点的值意义为到达该时刻状态为Sr且前一时刻状态为Sk时可以产生状态序 列的最大概率。比方背景为绿色的小节点的值的意义为时刻3为下雨，时刻2 为下雨时去自习-宅着-玩耍的最大概率。注意，节点表示时刻i时某个状态， 小节点表示节点中保存的前一状态的节点，比方绿色的那个节点。对于时刻i G2，每个小节点的概率为那么对于时刻i+1，小节点的概率为：D(i 十= maxD (t f) * 氏如丄然后，从时刻t中寻找最大的小节点回溯即可。样例问题一答案上面样例问题中第一问的答案是：概率：P=P（下雨）*P（晴天下雨）*.*P（阴天|晴天）*P（自习下雨）*P（宅着晴 天）*.