八
12
六、维特比算法（Viterbi Algorithm）
寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states)
对于一个特殊的隐马尔科夫模型(HMM)及一个相应的观察序列，我们常常希望能找到生成此序列最可能的隐藏状态序列。
1.穷举搜索
我们使用下面这张网格图片来形象化的说明隐藏状态和观察状态之间的关系：
我们可以通过列出所有可能的隐藏状态序列并且计算对于每个组合相应的观察序列的概率来找到最可能的隐藏状态序列。最可能的隐藏状态序列是使下面这个概率最大的组合：
Pr（观察序列|隐藏状态的组合）
例如，对于网格中所显示的观察序列，最可能的隐藏状态序列是下面这些概率中最大概率所对应的那个隐藏状态序列：
Pr(dry,damp,soggy | sunny,sunny,sunny), Pr(dry,damp,soggy | sunny,sunny,cloudy), Pr(dry,damp,soggy | sunny,sunny,rainy), . . . . Pr(dry,damp,soggy | rainy,rainy,rainy)
这种方法是可行的，但是通过穷举计算每一个组合的概率找到最可能的序列是极为昂贵的。与前向算法类似，我们可以利用这些概率的时间不变性来降低计算复杂度。
2.使用递归降低复杂度
给定一个观察序列和一个隐马尔科夫模型（HMM），我们将考虑递归地寻找最有可能的隐藏状态序列。我们首先定义局部概率
,它是到达网格中的某个特殊的中间状态时的概率。然后，我们将介绍如何在t=1和t=n(>1)时计算这些局部概率。
这些局部概率与前向算法中所计算的局部概率是不同的，因为它们表示的是时刻t时到达某个状态最可能的路径的概率，而不是所有路径概率的总和。
2a.局部概率‘s和局部最佳途径
考虑下面这个网格，它显示的是天气状态及对于观察序列干燥，湿润及湿透的一阶状态转移情况：
对于网格中的每一个中间及终止状态，都有一个到达该状态的最可能路径。举例来说，在t=3时刻的3个状态中的每一个都有一个到达此状态的最可能路径，或许是这样的：
我们称这些路径局部最佳路径(partial best paths)。其中每个局部最佳路径都有一个相关联的概率，即局部概率或。与前向算法中的局部概率不同，是到达该状态（最可能）的一条路径的概率。
因而(i,t)是t时刻到达状态i的所有序列概率中最大的概率，而局部最佳路径是得到此最大概率的隐藏状态序列。对于每一个可能的i和t值来说，这一类概率（及局部路径）均存在。
特别地，在t=T时每一个状态都有一个局部概率和一个局部最佳路径。这样我们就可以通过选择此时刻包含最大局部概率的状态及其相应的局部最佳路径来确定全局最佳路径（最佳隐藏状态序列）。
未完待续：维特比算法2
本文翻译自：http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html
部分翻译参考：隐马尔科夫模型HMM自学
转载请注明出处“我爱自然语言处理”：blog.52nlp.org
本文链接地址：http://blog.52nlp.org/hmm-learn-best-practices-six-viterbi-algorithm-1
相关文章:
- HMM学习最佳范例五：前向算法1
- HMM学习最佳范例五：前向算法5
- HMM学习最佳范例六：维特比算法5
- HMM学习最佳范例六：维特比算法4
- HMM学习最佳范例六：维特比算法2
- HMM学习最佳范例六：维特比算法3
- wiki上一个比较好的HMM例子
- HMM学习最佳范例七：前向-后向算法1
- HMM学习最佳范例四：隐马尔科夫模型
- HMM学习最佳范例五：前向算法4
评论
21条回复 to “HMM学习最佳范例六：维特比算法1”
发表评论
订阅52nlp：
好像没有关于训练算法baum welch的
[回复]
admin 回复:
八月 14th, 2009 at 21:36
请耐心等待，后继我会继续写这个系列，可以先看看几篇关于HMM的经典论文：
An Introduction to Hidden Markov Models;
A tutorial on Hidden Markov Models and selected applications in speech recognition;
[回复]
谢谢您的工作！
[回复]
admin 回复:
八月 23rd, 2009 at 19:38
不用客气，欢迎常来！
[回复]
<>书中也有介绍HMM：
http://www.douban.com/subject/4114152/
希望对初学者有帮助。
[回复]
52nlp 回复:
一月 9th, 2010 at 19:22
谢谢！
[回复]
楼主很强大，谢谢您的工作……
[回复]
52nlp 回复:
一月 22nd, 2010 at 20:53
不客气，欢迎常来看看！
[回复]
“最可能的隐藏状态序列是使下面这个概率最大的组合：
Pr（观察序列|隐藏状态的组合）”
为什么不是“Pr（隐藏状态的组合|观察序列）”呢？
[回复]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐 藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]
[...] Viterbi algorithm 寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) [...]