隐马尔科夫链与维特比算法
马尔科夫链
明天的天气怎么样？明天的股市怎么样？用户下一个输入的单词会是什么？这些问题都是一个随机过程的问题（就是「随机过程随机过」的那个随机过程）。
对随机过程的研究要比随机变量复杂得多，在任何一个时刻 t，对应的状态 st 都是随机的，而我们要研究不同时刻的状态之间的相关性就变得非常复杂。比如今天的最高气温可能和之前几天的最高气温都是相关的，这让模型的建立变得复杂。马尔科夫为了简化问题，提出了一种假设，即
随机过程中每个状态的概率分布只和其前一个状态有关。
注意，我们不能否认前天的天气和今天天气的相关性。马尔科夫链并不是直接否认前一时刻的状态与后一时刻状态之间的相关性，而是说明了在当前时刻状态已知的前提下，下一时刻的状态只与当前时刻有关，而和之前的时刻无关。
隐马尔科夫模型(HMM) 马尔科夫模型极大得简化了随机过程的研究，但是在现实问题中，我们常常无法直接获得随机过程中各个时刻的状态。比如语音识别，当你听到“li hai”，可能是在说「厉害」，也可能是在说「里海」。听到的“li hai”是观测到的现象，而背后的信息才是我们要研究的随机过程的状态。这就是隐马尔科夫模型
任意时刻 t 的状态 st 是不可见的，观测者不能直接观察状态序列来推测状态转移模型的参数。但是隐马尔科夫模型在每个时刻都会输出 ot,而且 ot 仅和 st 相关（独立输出假设）。
状态转移矩阵 与 发射矩阵
如果 HMM 模型的状态是离散的，而观察状态也是离散的，我们就可以得到两个关键的矩阵。一个是状态转移矩阵，其表示模型在不同状态间跳转的概率。比如状态为「不感冒」和「感冒」，则[[0.7, 0.3], [0.4, 0.6]]表示
如果昨天不感冒，则今天 70%不感冒，30%感冒
如果昨天感冒了，则今天 40%不感冒，60%感冒
另一个矩阵叫做发射矩阵，其表示在不同的状态下产生不同观测值的概率，比如
如果不感冒，则有 50%的概率表现正常，有 40%概率觉得冷，有 10%的概率感觉头晕
如果感冒了，则有 10%的概率表现正常，有 30%概率觉得冷，有 60%概率觉得头晕
除此之外，我们还有一些先验知识。比如人有 60%的概率处于健康状态，有 40%的概率处于感冒状态。
请问，假设我第一天感觉正常，第二天感觉有点冷，第三天感觉有点 dizzy，我这三天最可能的状态分别是什么呢？
维特比算法
这个问题可以被建模为图遍历的问题。也就是从第一天开始一直到今天，状态流转的路径中可能性最大的路径。而没过一层的可能性都有「状态数的平方」那么多，所以整个图求解也是复杂度非常高的。
而维特比算法就是解决这个问题的一种动态规划算法。其核心思想在于
到达今天各个状态的最大概率，是由到达昨天的各个状态的最大概率，与今天的观测情况决定的。
比如今天感觉有点冷吧，如果昨天身体好的很，那么今天很可能并没有感冒，但是如果昨天就感冒了，那今天感冒的概率就很大。
那么在感觉冷的情况下今天感冒的概率是多少呢？
- 我们要知道昨天感冒的概率，昨天感冒且今天感冒的转移概率
- 我们要知道昨天没感冒的概率，昨天没感冒且今天感冒的转移概率
- 我们要知道感冒导致感觉冷的概率
P(今天感冒) = 常数 * max(P(昨天感冒)*P(今天感冒|昨天感冒)*P(觉得冷|感冒),
P(昨天没感冒)*P(今天感冒|昨天没感冒)\*P(觉得冷|感冒))
同样我们也可以算出今天没有感冒的概率。通过动态规划，我们可以算出整个随机过程的 path 下最可能的状态转移路径。
(小知识：维特比算法的发明人安德鲁维特比在 1985 年创立了高通公司。)
实战
class Viterbi:
def __init__(self, start_p, trans_p, emission_p):
self.start_p = start_p
self.trans_p = trans_p
self.emission_p = emission_p
self.state_count = len(start_p)
self.ob_count = len(self.emission_p[0])
self.round = 0
self.path = {}
self.V_last = []
self.obs = []
def next(self, ob):
self.obs.append(ob)
if self.round == 0:
self.V_last = [self.start_p[i] * self.emission_p[i][ob] for i in range(self.state_count) ]
self.path = [[i] for i in range(self.state_count)]
else:
newPath = []
newV_last = []
for y in range(self.state_count):
(prob, state) = max([(self.V_last[y0] * self.trans_p[y0][y] * self.emission_p[y][ob], y0)
for y0 in range(self.state_count)])
newV_last.append(prob)
newPath.append(self.path[state] + [y])
self.V_last = newV_last
self.path = newPath
self.round += 1
viterbi = Viterbi(
[0.6, 0.4],
[[0.7, 0.3], [0.4, 0.6]],
[[0.5, 0.4, 0.1], [0.1, 0.3, 0.6]])
viterbi.next(0)
viterbi.next(1)
viterbi.next(2)
第一天正常，第二天感觉冷，第三天感觉头晕，其最可能的 path 为 “健康->健康->感冒”。