全部博文(330)
分类:
2012-01-04 11:06:03
文章来源:
这篇文章简单描述一下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。我们知道,天气与运动的关系如下:
Rainy | Sunny | |
Walk | 0.1 | 0.6 |
Shop | 0.4 | 0.3 |
Clean | 0.5 | 0.1 |
例如,在下雨天出去散步的可能性是0.1。
而天气之前互相转换的关系如下,(从行到列)
Rainy | Sunny | |
Rainy | 0.7 | 0.3 |
Sunny | 0.4 | 0.6 |
例如,从今天是晴天而明天就开始下雨的可能性是0.4 。
同时为了求解问题我们假设初始情况:通话开始的第一天的天气有0.6的概率是Rainy,有0.4概率是Sunny。OK,现在的问题是,如果连续 三天,你发现你的朋友的活动是:Walk->Shop->Clean;那么,如何判断你朋友那里这几天的天气是怎样的?
解决这个问题的python伪代码如下:
几点说明:
所以,最终的结果是,朋友那边这几天最可能的天气情况是Sunny->Rainy->Rainy->Rainy,它有 0.009408的概率出现。而我们算法的另一个附带的结论是,我们所观察到的朋友这几天的活动序列:Walk->Shop->Clean在 我们的隐马可夫模型之下出现的总概率是0.033612。
参考文献
附:c++主要代码片断