隐马尔可夫HMM中Forward算法

引言

隐马尔可夫中第一个问题是评估问题，评估该观察序列发生的概率，forward算法就是减少重复运算，其实你动动手算多了，你也会发现应该这么做，你如果生在那个时代，这个算法就是你发现的哦。

问题描述

你在中国，你朋友F在美国，F的作息有walk, shop, clean，但这选择跟天气有关，我们又知道Rainy的概率比Sunny的概率大
这是初始概率

这是天气转移矩阵

这是在相应天气下发生相应事的概率分布
然后，F这三天是walk，walk，shop，求{walk，walk，shop}的概率是多少

问题分析

我们先用穷举法来，即

Sunny Sunny Sunny
Sunny Sunny Rainy
Sunny Rainy Sunny
Sunny Rainy Rainy
Rainy Sunny Sunny
Rainy Sunny Rainy
Rainy Rainy Sunny
Rainy Rainy Rainy

分别求出在各个情况下，{walk，walk，shop}的概率，然后求下和就是最后的结果，我举其中一例求下

容易发现，这个运算量会很大，时间复杂度会很高

因此我们采用forward算法，我们发现穷举法有大量的重复运算，把已经算过的利用起来就是forward算法的基本思想

这算法就是用这么一个矩阵表示出来的，你把剩下的填好了，你这算法也就学会了，我稍加分析

0.6*0.1：第一天walk且是Rainy的概率，等于P(第一天是rainy)*P(walk| rainy)

(0.6*0.1*0.7+0.4*0.6*0.4)*0.4：第一天walk第二天是shop且第二天是Rainy的概率，等于(P(第一天walk 且 Rainy) * P(第二天Rainy|第一天Rainy) + P(第一天walk 且 Sunny) * P(第二天Rainy|第一天Sunny)) * P(第二天shop| Rainy)，其实很好理解，因为你不知道第一天是什么天气，但你知道第一天是walk的

以此类推，你就会把这张表填完。

最后，把第三天那一行的数字加起来就是最终结果，至于为什么加起来，相信你应该知道。

附上python代码

View Code

 1 #state of the wether
 2 state = ('Rainy', 'Sunny')
 3 #observation
 4 obs = ('walk', 'shop', 'clean')
 5 #initializing probability
 6 in_p = {'Rainy': 0.6, 'Sunny': 0.4}
 7 #transition probability Matrix
 8 A = {'Rainy': {'Rainy': 0.7, 'Sunny':0.3}, 'Sunny': {'Rainy': 0.4, 'Sunny':0.6}}
 9 #emission probability Matrix
10 B = {'Rainy': {'walk': 0.1, 'shop': 0.4, 'clean': 0.5}, 'Sunny': {'walk': 0.6, 'shop': 0.3, 'clean': 0.1}}
11 #result dictionary
12 result = {}
13 #mark the everyday's probability
14 value = {}
15 i = 0
16 while i < len(obs):
17     j = 0
18     while j < len(state):
19         #if it's thr first day
20         if i == 0:
21             value[state[j]] = in_p[state[j]] * B[state[j]][obs[i]]
22         #get the answer based on the previous day
23         else:
24             sum = 0
25             for key in result[i - 1]:
26                 sum = sum + result[i - 1][key] * A[key][state[j]]
27             value[state[j]] = sum * B[state[j]][obs[i]]
28         j = j + 1
29     #note the copy()
30     result[i] = value.copy();
31     i = i + 1
32 #suming up the last day's probability
33 sum = 0
34 for key in value:
35     sum = sum + value[key]
36 print sum