资源描述：
《隐马尔可夫模型中的Viterbi算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、隐马尔可夫模型中的Viterbi算法先用一句话来简单描述一下：给出一个观测序列o1,o2,o3...，我们希望找到观测序列背后的隐藏状态序列s1,s2,s3,...；Viterbi以它的发明者名字命名，正是这样一种由动态规划的方法来寻找出现概率最大的隐藏状态序列（被称为Viterbi路径）的算法。这里需要抄一点有关隐马可夫序列（HMM，HiddenMarkovModel）的书页来解释一下观测序列和隐藏状态序列。首先从最简单的离散Markov过程入手，我们知道，Markov随机过程具有如下的性质：在任意时刻，从当前状态转移到下一个状态的概率与当前状态之前的那些状态没有关系。所以，我
2、们可以用一个状态转移概率矩阵来描述它。假设我们有n个离散状态S1,S2,…Sn，我们可以构造一个矩阵A，矩阵中的元素aij表示从当前状态Si下一时刻迁移到Sj状态的概率。但是在很多情况下，Markov模型中的状态是我们观察不到的。例如，容器与彩球的模型：有若干个容器，每个容器中按已知比例放入各色的彩球（这样，选择了容器后，我们可以用概率来预测取出各种彩球的可能性）；我们做这样的实验，实验者从容器中取彩球——先选择一个容器，再从中抓出某一个球，只给观察者看球的颜色；这样，每次取取出的球的颜色是可以观测到的，即o1,o2,…，但是每次选择哪个容器是不暴露给观察者的，容器的序列就组成了
3、隐藏状态序列S1,S2,…Sn。这是一个典型的可以用HMM描述的实验。HMM有几个重要的任务，其中之一就是期望通过观察序列来猜测背后最有可能的隐藏序列。在上面的例子中，就是找到我们在实验中最有可能选择到的容器序列。Viterbi正是用来解决这个问题的算法。HMM另外两个任务是：a)给定一个HMM，计算一个观测序列出现的可能性；b)已知一个观测序列，HMM参数不定，如何优化这些参数使得观测序列的出现概率最大。解决前一个问题可以用与Viberbi结构非常类似的Forward算法来解决（实际上在下面合二为一），而后者可以用Baum-Welch/EM算法来迭代逼近。从Wiki上抄一个例子
4、来说明Viterbi算法。假设你有一个朋友在外地，每天你可以通过电话来了解他每天的活动。他每天只会做三种活动之一——Walk,Shop,Clean。你的朋友从事哪一种活动的概率与当地的气候有关，这里，我们只考虑两种天气——Rainy,Sunny。我们知道，天气与运动的关系如下：RainySunnyWalk0.10.6Shop0.40.3Clean0.50.1例如，在下雨天出去散步的可能性是0.1。而天气之前互相转换的关系如下，（从行到列）RainySunnyRainy0.70.3Sunny0.40.6例如，从今天是晴天而明天就开始下雨的可能性是0.4。同时为了求解问题我们假设初始
5、情况：通话开始的第一天的天气有0.6的概率是Rainy，有0.4概率是Sunny。OK，现在的问题是，如果连续三天，你发现你的朋友的活动是：Walk->Shop->Clean；那么，如何判断你朋友那里这几天的天气是怎样的？解决这个问题的python伪代码如下：defforward_viterbi(y,X,sp,tp,ep):T={}forstateinX:##prob.V.pathV.prob.T[state]=(sp[state],[state],sp[state])foroutputiny:U={}fornext_stateinX:total=0argmax=Nonevalm
6、ax=0forsource_stateinX:(prob,v_path,v_prob)=T[source_state]p=ep[source_state][output]*tp[source_state][next_state]prob*=pv_prob*=ptotal+=probifv_prob>valmax:argmax=v_path+[next_state]valmax=v_probU[next_state]=(total,argmax,valmax)T=U##applysum/maxtothefinalstates:total=0argmax=Nonevalmax=0fo
7、rstateinX:(prob,v_path,v_prob)=T[state]total+=probifv_prob>valmax:argmax=v_pathvalmax=v_probreturn(total,argmax,valmax)几点说明：1、算法对于每一个状态要记录一个三元组：(prob,v_path,v_prob)，其中，prob是从开始状态到当前状态所有路径（不仅仅是最有可能的viterbi路径）的概率加在一起的结果（作为算法附产品，它可以输出一个观察序列在给定HM
