维特比算法

维特比算法（英语：Viterbi algorithm）是一种动态规划算法。

算法用途

用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。

举例

想象一个乡村诊所。

村民有着非常理想化的特性，要么健康要么发烧。

他们只有问诊所的医生的才能知道是否发烧。

聪明的医生通过询问病人的感觉诊断他们是否发烧。

村民只回答他们感觉正常、头晕或冷。

假设一个病人每天来到诊所并告诉医生他的感觉。

医生相信病人的健康状况如同一个离散马尔可夫链。

病人的状态有两种“健康”和“发烧”，但医生不能直接观察到，这意味着状态对他是“隐含”的。

每天病人会告诉医生自己有以下几种由他的健康状态决定的感觉的一种：正常、冷或头晕。这些是观察结果。

整个系统为一个隐马尔可夫模型(HMM)。

医生知道村民的总体健康状况，还知道发烧和没发烧的病人通常会抱怨什么症状。

用Python代码表示为：

states = ('健康', '发热') # 状态的样本空间
observations = ('正常', '发冷', '发晕') # 观测的样本空间
start_probability = {'健康': 0.6, '发热': 0.4} # 起始个状态概率
transition_probability = { # 状态转移概率
  '健康': {'健康': 0.7, '发热': 0.3},
  '发热': {'健康': 0.4, '发热': 0.6},
}
emission_probability = { # 状态->观测的发散概率
  '健康': {'正常': 0.5, '发冷': 0.4, '发晕': 0.1},
  '发热': {'正常': 0.1, '发冷': 0.3, '发晕': 0.6},
}

假设一个村民三天内，描述自己 ‘发冷’、’发晕’、 ‘发晕’，医生需要判断村民究竟是否健康

obs = ('发冷', '发晕', '发晕')

计算状态矩阵

其实这个问题是一个动态规划问题，写起来也并不难。

• 第一层的状态为
  初始健康概率(0.6) 健康时发冷的概率(0.4)
  初始发热概率(0.4) 发热时发冷的概率(0.3)

result_m = [{}]
for s in states:
    result_m[0][s] = (start_probability[s]*emission_probability[s][obs[0]],None)

第一层为

{'健康': (0.24, None), '发热': (0.12, None)}

余下层

for t in range(1,len(obs)):
    result_m.append({})
    for s in states:
        result_m[t][s] =  \
            max([(result_m[t-1][s0][0]*transition_probability[s0][s] \
                 *emission_probability[s][obs[t]],s0) for s0 in states])

• 对于每一个t时刻状态s,获取t-1时刻每个状态s0的p
• 结合由s0转化为s的转移概率和s状态至obs的发散概率
• 计算t时刻s状态的最大概率，并记录该概率的来源状态s0

输出大概如下：

[{'健康': (0.24, None), '发热': (0.12, None)},
 {'健康': (0.0168, '健康'), '发热': (0.043199999999999995, '发热')},
 {'健康': (0.0017280000000000002, '发热'), '发热': (0.015551999999999996, '发热')}]

结论：

健康->发热->发热

正常情况下时间复杂度为 $O(n^2)$，不过谷歌优化到了$O(n)$，简直不是人呐。。。