偶看新闻痔疮应该吃什么食物:隐马尔科夫模型HMM自学 （5-2）Viterbi Algorithm
来源：百度文库 编辑：偶看新闻 时间：2024/06/12 20:50:02
隐马尔科夫模型HMM自学 （5-2）Viterbi Algorithm
书接前文，viterbi算法已经基本成形......
崔晓源 翻译
一般化上一篇最后得到的公式我们可以把概率的求解写成：
2d. 反向指针, 
‘s
考虑下面trellis
现在我们可以得到到达每一个中间或者终点状态的概率最大的路径。但是我们需要采取一些方法来记录这条路径。这就需要在每个状态记录得到该状态最优路径的前一状态。记为：
这样argmax操作符就会选择使得括号中式子最大的索引j。
如果有人问，为什么没有乘以混淆矩阵中的观察概率因子。这是因为我们关心的是在到达当前状态的最优路径中，前一状态的信息，而与他对应的观察状态无关。
2e. viterbi算法的两个优点
1）与Forward算法一样，它极大的降低了计算复杂度
2）viterbi会根据输入的观察序列，“自左向右”的根据上下文给出最优的理解。由于viterbi会在给出最终选择前考虑所有的观察序列因素，这样就避免了由于突然的噪声使得决策原理正确答案。这种情况在真实的数据中经常出现。
==================================================
下面给出viterbi算法完整的定义1. Formal definition of algorithm
The algorithm may be summarised formally as:
For each i,, i = 1, ... , n, let :
- this intialises the probability calculations by taking the product of the intitial hidden state probabilities with the associated observation probabilities.
For t = 2, ..., T, and i = 1, ... , n let :
- thus determining the most probable route to the next state, and remembering how to get there. This is done by considering all products of transition probabilities with the maximal probabilities already derived for the preceding step. The largest such is remembered, together with what provoked it.
Let :
- thus determining which state at system completion (t=T) is the most probable.
For t = T - 1, ..., 1
Let :
- thus backtracking through the trellis, following the most probable route. On completion, the sequence i1 ... iT will hold the most probable sequence of hidden states for the observation sequence in hand.
==================================================
我们还用天气的例子来说明如何计算状态CLOUDY的部分概率，注意它与Forward算法的区别 还是那句话：怎么样？看到这里豁然开朗了吧。要是还不明白，我就.....................还有办法，看个动画效果：http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s3_pg3.html参数定义：http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s3_pg4.htmlhttp://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s3_pg5.html别忘了，viterbi算法的目的是根据给定的观察状态序列找出最有可能的隐含状态序列，别忘了viterbi算法不会被中间的噪音所干扰。