向前算法解决隐马尔可夫模型似然度问题

1向前算法原理描述向前算法解决：问题1（似然度问题）：给一个HMMλ=（A,B）和一个观察序列O，确定...

1 向前算法原理描述

向前算法解决：问题1（似然度问题）：给一个HMM λ=（A,B） 和一个观察序列O，确定观察序列的似然度问题 P=(O|λ) 。



对于马尔可夫链，表面观察和实际隐藏是相同的，只需要标记吃冰淇淋数目“3 1 3”的状态，把加权（弧上）的对应概率相乘即可。而隐马尔可夫模型就不是那么简单了，因为状态是隐藏的，我们并不知道隐藏的状态序列是什么？

简化下问题：假如我们知道天气热冷状况，并且知道小明吃冰淇淋的数量，我们去观察序列似然度。如：对于给定的隐藏状态序列“hot hot cold”我们来计算观察序列“3 1 3”的输出似然度。

如何进行计算？首先，隐马尔可夫模型中，每个隐藏状态只产生一个单独的观察即一一映射，隐藏状态序列与观察序列长度相同，即：给定这种一对一的映射以及马尔可夫假设，对于一个特定隐藏状态序列 
以及一个观察序列 
观察序列的似然度为：



故从隐藏状态“hot hot cold”到所吃冰淇淋观察序列“3 1 3”的向前概率为：

P(3 1 3|hot hot cold)=P(3|hot)*P(1|hot)*P(3|cold)=0.4*0.2*0.1=0.008

实际上，隐藏状态序列“hot hot cold”是我们的假设，并不知道隐藏状态序列，我们要考虑所有可能的天气序列，如此一来，我们将计算所有可能的联合概率，计算将会变得特别复杂。

我们来计算天气序列Q生产一个特定的冰淇淋事件序列O的联合概率：



如果隐藏序列只有一个是“hot hot cold”，那么我们的冰淇淋观察“3 1 3”和一个可能的隐藏状态“hot hot cold”的联合概率为：

P(313|hothotcold)=P(hot|start)*P(hot|hot)*P(hot|cold)*P(3|hot)*P(1|hot)*P(3|cold)=0.8*0.7*0.30.4*0.2*0.1=0.001344

P(3 1 3)= P(313| cold cold cold)+ P(313| cold cold hot) + P(313| hot hot cold ) + P(313| cold hot cold) + P(313|hot cold cold) + P(313| hot hot hot) + P(313| hot cold hot) + P(313| cold hot hot)

对于具有N个隐藏状态和T个观察序列，将会有 
个可能隐藏序列，在实际中T往往很大，比如文本处理中可能有数万几十万个词汇，计算量将是指数上升。在隐含马尔可夫模型中有种向前的算法有效代替这种指数增长的复杂算法，大大降低了复杂度。实验证明向前算法的复杂度是 
。

2 向前算法的实例解析

向前算法是一种动态规划算法，当得到观察序列的概率时候，它使用一个表来存储中间值。向前算法也使用对于生成观察序列的所有可能的隐藏状态的路径上的概率求和的方法计算观察概率。在向前算法中横向表示观察序列，纵向表示状态序列。

下图是对于给定的隐藏状态序列“hot hot cold”计算观察序列“3 13 ”的似然度的向前网格的例子。其中：

1

2

3

4

5

横向：时间上的观察序列，纵向：空间上的状态序列

方框：观察状态         圆框：隐藏状态

续框：不合法转移       实线上值：加权概率

每个单元
表示对于给定的自动机λ，在前面t个观察之后，在状态j的概率： 
，其中 
表示第t个状态是状态j的概率。如：
表示状态1即数3时，q1的概率。



上面公式的3个因素：



向前网格如下：



在时间1和状态1的向前概率：



（从状态cold开始吃3根冰淇淋的似然度0.02）

在时间1和状态2的向前概率：



（从状态hot始吃3根冰淇淋的似然度0.32）

在时间2和状态1的向前概率：



（从开始到cold再到cold以及从开始到hot再到cold的天气状态，吃冰淇淋3 1 的观察似然度0.54）

在时间2和状态2的向前概率：



（从开始到cold再到hot以及从开始到hot再到hot的天气状态，吃冰淇淋3 1 的观察似然度0.0464）

用同样方法，我们可以计算时间步3和状态步1的向前概率以及时间步3和状态步2的概率等等，以此类推，直到结束。显而易见，使用向前算法来计算观察似然度可以表示局部观察似然度。这种局部观察似然度比使用联合概率表示的全局观察似然度更有用。

3 向前算法定义

向前算法的递归定义：

4  参考文献

【1】统计自然语言处理基础  Christopher.Manning等 著    宛春法等 译

【2】自然语言处理简明教程  冯志伟 著

【3】数学之美  吴军 著

【4】Viterbi算法分析文章  王亚强

http://www.cnblogs.com/baiboy/p/hmm3.html

作者：白宁超

    关注 SOTON数据分析