引言

隐马尔可夫中第一个问题是评估问题，评估该观察序列发生的概率，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}的概率，然后求下和就是最后的结果，我举其中一例求下

P(walk，walk，shop|Sunny，Sunny，Sunny) = P(Sunny) * P(walk| Sunny) * P(Sunny |Sunny) * P(walk| Sunny) * P(Sunny |Sunny) * P(shop| Sunny)

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

因此我们采用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代码

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 Matrix10 B = {
    'Rainy': {
    'walk': 0.1, 'shop': 0.4, 'clean': 0.5}, 'Sunny': {
    'walk': 0.6, 'shop': 0.3, 'clean': 0.1}}11 #result dictionary12 result = {}13 #mark the everyday's probability14 value = {}15 i = 016 while i < len(obs):17     j = 018     while j < len(state):19         #if it's thr first day20         if i == 0:21             value[state[j]] = in_p[state[j]] * B[state[j]][obs[i]]22         #get the answer based on the previous day23         else:24             sum = 025             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 + 129     #note the copy()30     result[i] = value.copy();31     i = i + 132 #suming up the last day's probability33 sum = 034 for key in value:35     sum = sum + value[key]36 print sum