隐马尔可夫模型中的Viterbi算法

隐马尔可夫模型中的 Viterbi算法 先用一句话来简单描述一下给出一个观测序列 o1,o2,o3 .，我们希望找到观测 序列背后的隐藏状态序列 s1, s2, s3, .；Viterbi以它的发明者名字命名，正是这样 一种由动态规划的方法来寻找出现概率最大的隐藏状态序列（被称为 Viterbi路 径）的算法。 这里需要抄一点有关隐马可夫序列（HMM，Hidden Markov Model）的书页来解 释一下观测序列和隐藏状态序列。 首先从最简单的离散 Markov过程入手，我们知道，Markov随机过程具有如下的 性质在任意时刻，从当前状态转移到下一个状态的概率与当前状态之前的那些 状态没有关系。所以，我们可以用一个状态转移概率矩阵来描述它。假设我们有 n个离散状态 S1, S2,Sn，我们可以构造一个矩阵 A，矩阵中的元素 aij表示从当 前状态 Si 下一时刻迁移到 Sj 状态的概率。 但是在很多情况下，Markov模型中的状态是我们观察不到的。例如，容器与彩球 的模型有若干个容器，每个容器中按已知比例放入各色的彩球（这样，选择了 容器后，我们可以用概率来预测取出各种彩球的可能性）；我们做这样的实验， 实验者从容器中取彩球先选择一个容器，再从中抓出某一个球，只给观察者 看球的颜色；这样，每次取取出的球的颜色是可以观测到的，即 o1, o2,，但是 每次选择哪个容器是不暴露给观察者的，容器的序列就组成了隐藏状态序列 S1, S2,Sn。这是一个典型的可以用 HMM 描述的实验。 HMM有几个重要的任务，其中之一就是期望通过观察序列来猜测背后最有可能 的隐藏序列。在上面的例子中，就是找到我们在实验中最有可能选择到的容器序 列。Viterbi正是用来解决这个问题的算法。HMM另外两个任务是a 给定一个 HMM，计算一个观测序列出现的可能性；b已知一个观测序列，HMM 参数不 定，如何优化这些参数使得观测序列的出现概率最大。解决前一个问题可以用与 Viberbi结构非常类似的 Forward算法来解决（实际上在下面合二为一），而后者 可以用 Baum-Welch/EM 算法来迭代逼近。 从 Wiki 上抄一个例子来说明 Viterbi算法。 假设你有一个朋友在外地，每天你可以通过电话来了解他每天的活动。他每天只 会做三种活动之一Walk, Shop, Clean。你的朋友从事哪一种活动的概率与当 地的气候有关，这里，我们只考虑两种天气Rainy, Sunny。我们知道，天气 与运动的关系如下 例如，在下雨天出去散步的可能性是 0.1。 而天气之前互相转换的关系如下，（从行到列） 例如，从今天是晴天而明天就开始下雨的可能性是 0.4 。 同时为了求解问题我们假设初始情况通话开始的第一天的天气有 0.6 的概率是 Rainy，有 0.4 概率是 Sunny。OK，现在的问题是，如果连续三天，你发现你的朋 友的活动是Walk-Shop-Clean；那么，如何判断你朋友那里这几天的天气是怎 样的 解决这个问题的 python 伪代码如下 def forward_viterbiy, X, sp, tp, ep T {} for state in X prob. V. path V. prob. T[state] sp[state], [state], sp[state] for output in y U {} for next_state in X total 0 argmax None valmax 0 for source_state in X prob, v_path, v_prob T[source_state] p ep[source_state][output] * tp[source_state][next_state] prob * p v_prob * p total prob if v_prob valmax argmax v_path [next_state] valmax v_prob U[next_state] total, argmax, valmax T U apply sum/max to the final states total 0 argmax None valmax 0 for state in X prob, v_path, v_prob T[state] total prob if v_prob valmax argmax v_path valmax v_prob return total, argmax, valmax 几点说明 1、算法对于每一个状态要记录一个三元组prob, v_path, v_prob，其中，prob 是从开始状态到当前状态所有路径（不仅仅 是最有可能的 viterbi 路径）的概率加 在一起的结果（作为算法附产品，它可以输出一个观察序列在给定 HMM 下总的 出现概率，即 forward 算法的输出），v_path是从开始状态一直到当前状态的 viterbi路径，v_prob则是该路径的概率。 2、算法开始，初始化 T （T是一个 Map，将每一种可能状态映射到上面所说的 三元组上） 3、三重循环，对每个一活动 y，考虑下一步每一个可能的状态 next_state，并重 新计算若从 T中的当前状 态 state跃迁到 next_state概率会有怎样的变化。跃迁主要考虑天气转移 （tp[source_state][next_state]）与该天气下从事某种活动 （ep[source_state][output]）的联合概率。所有下一步状态考虑完后，要从 T中找 出最优的选择 viterbi 路径即概率最大的 viterbi路径，即上面更新 Map U的 代码 U[next_state] total, argmax, valmax。 4、算法最后还要对 T中的各种情况总结，对 total 求和，选择其中一条作为最优 的 viterbi路径。 5、算法输出四个天气状态，这是因为，计算第三天的概率时，要考虑天气转变 到下一天的情况。 6、通过程序的输出可以帮助理解这一过程 observationWalk next_stateSunny stateSunny p0.36 triple0.144,Sunny-,0.144 stateRainy p0.03 triple0.018,Rainy-,0.018 Update U[Sunny]0.162,Sunny-Sunny-,0.144 next_stateRainy stateSunny p0.24 triple0.096,Sunny-,0.096 stateRainy p0.07 triple0.042,Rainy-,0.042 Update U[Rainy]0.138,Sunny-Rainy-,0.096 observati