八

26

HMM学习最佳范例六：维特比算法4

分类 隐马尔科夫模型 

六、维特比算法（Viterbi Algorithm）

维特比算法定义(Viterbi algorithm definition)


1、维特比算法的形式化定义
　　维特比算法可以形式化的概括为：
　　对于每一个i，i = 1，… ，n，令：
　　　　　6.2.1_a
　　——这一步是通过隐藏状态的初始概率和相应的观察概率之积计算了t=1时刻的局部概率。
　　对于t=2，…，T和i=1，…，n,令：
　　　　　6.2.1_b
　　——这样就确定了到达下一个状态的最可能路径，并对如何到达下一个状态做了记录。具体来说首先通过考察所有的转移概率与上一步获得的最大的局部概率之积，然后记录下其中最大的一个，同时也包含了上一步触发此概率的状态。
　　令：
　　　　　6.2.1_c
　　——这样就确定了系统完成时(t=T)最可能的隐藏状态。
　　对于t=T-1，…，1
　　令：
　　　　　6.2.1_d
　　——这样就可以按最可能的状态路径在整个网格回溯。回溯完成时，对于观察序列来说，序列i1 … iT就是生成此观察序列的最可能的隐藏状态序列。

　　2.计算单独的delta‘s和phi‘s
　　维特比算法中的局部概率delta‘s的计算与前向算法中的局部概率alpha‘s的很相似。下面这幅图表显示了delta‘s和phi‘s的计算细节，可以对比一下前向算法3中的计算局部概率alpha‘s的那幅图表：
　　example.viterbi
（注：本图及前向算法3中的相似图存在问题，具体请见前向算法3文后评论，非常感谢读者YaseenTA的指正）
　　唯一不同的是前向算法中计算局部概率alpha‘s时的求和符号（Sigma）在维特比算法中计算局部概率delta‘s时被替换为max——这一个重要的不同也说明了在维特比算法中我们选择的是到达当前状态的最可能路径，而不是总的概率。我们在维特比算法中维护了一个“反向指针”记录了到达当前状态的最佳路径，即在计算phi‘s时通过argmax运算符获得。

总结(Summary)

　　对于一个特定的隐马尔科夫模型，维特比算法被用来寻找生成一个观察序列的最可能的隐藏状态序列。我们利用概率的时间不变性，通过避免计算网格中每一条路径的概率来降低问题的复杂度。维特比算法对于每一个状态(t>1)都保存了一个反向指针(phi)，并在每一个状态中存储了一个局部概率(delta)。
　　局部概率delta是由反向指针指示的路径到达某个状态的概率。
　　当t=T时，维特比算法所到达的这些终止状态的局部概率delta‘s是按照最优（最可能）的路径到达该状态的概率。因此，选择其中最大的一个，并回溯找出所隐藏的状态路径，就是这个问题的最好答案。
　　关于维特比算法，需要着重强调的一点是它不是简单的对于某个给定的时间点选择最可能的隐藏状态，而是基于全局序列做决策——因此，如果在观察序列中有一个“非寻常”的事件发生，对于维特比算法的结果也影响不大。
　　这在语音处理中是特别有价值的，譬如当某个单词发音的一个中间音素出现失真或丢失的情况时，该单词也可以被识别出来。

未完待续：维特比算法5

本文翻译自：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-4

相关文章:

  1. HMM学习最佳范例六：维特比算法5
  2. HMM学习最佳范例六：维特比算法2
  3. HMM学习最佳范例六：维特比算法1
  4. HMM学习最佳范例六：维特比算法3
  5. HMM学习最佳范例七：前向-后向算法1
  6. HMM学习最佳范例四：隐马尔科夫模型
  7. HMM学习最佳范例五：前向算法4
  8. HMM学习最佳范例七：前向-后向算法2
  9. HMM学习最佳范例七：前向-后向算法4
  10. HMM学习最佳范例五：前向算法5

评论

5条回复 to “HMM学习最佳范例六：维特比算法4”

  1. zhuzi on 九月 16th, 2009 22:13

    ——这样就确定了系统完成时(t=T)最可能的隐藏状态。
    　　对于t=T-1，…，1
    　　令：
    　　　　6.2.1_d
    　　——这样就可以按最可能的状态路径在整个网格回溯。回溯完成时，对于观察序列来说，序列i1 … iT就是生成此观察序列的最可能的隐藏状态序列。
    这里面公式为什么是t+1，而不是t-1，回溯应该是减1吧，我可能没明白原理，请再详细说下，谢谢。

    [回复]

    admin 回复:
    九月 16th, 2009 at 23:37

    正因为是回溯，所以才是t+1,譬如当t=T-1时，
    t+1指的是T时刻，而t指的就是T-1时刻，这个公式就转换为：
    i(T-1) = phi(T)(iT)了。
    如果是t-1的话，就变成了从T-2到T-1时刻，不是回溯，而是从前向后的计算了。

    [回复]

  2. zhuzi on 九月 17th, 2009 08:18

    明白了，十分感谢。

    [回复]

  3. dongshidu on 三月 13th, 2010 06:51

    我觉
    δt(i)=max[δt-1(i)*aji]*bikt
    否则
    正向经过的路径可能与反向指针指向的路径不一致

    [回复]

    52nlp 回复:
    三月 14th, 2010 at 12:35

    感觉您这个公式有问题，
    δt(i)=max[δt-1(j)*aji]*bikt
    中j应视作一个变量，from 1 to N中的任何一个。

    [回复]

发表评论






订阅52nlp：

Add to Google Reader or Homepage



Switch to our mobile site