20

n-gram 模型上的 Forward-backward 算法和隐马尔可夫模型(HMM)上的 Viterbi 算法有什么区别?

当我回顾这两种算法的实现时,我唯一发现的是交易概率来自不同的概率模型。

这两种算法有区别吗?

4

3 回答 3

19

Forward-Backward 算法结合了前向步骤和后向步骤来获得在特定时间处于每个状态的概率。因此,对所有时间步执行此操作可以为我们提供每次最可能的状态序列(尽管不能保证是有效序列,因为它考虑了每一步的单个状态,并且可能发生p(q_i -> q_j)=0转换模型中的概率) , 换句话说:

等式 1, 在哪里等式2

另一方面,维特比算法通过最大化不同的最优性标准来找到给定观察序列的最可能的状态序列:

等式 3

我建议您参考这篇著名的论文以获得详细解释(参见问题 #2):

LAWRENCE R. RABINER,隐马尔可夫模型教程和语音识别中的选定应用

于 2009-12-14T04:57:58.977 回答
6

简而言之:

如果只想预测某个特定时间最可能的标记是什么,则使用 Forward-Backward。它将考虑每个可能的序列并对它们进行平均以找到当时最可能的令牌。因此,当您考虑所有可能的序列时,您将返回的序列将不是真正的序列,而是最可能的标记的集合。

Viterbi 用于查找最可能的事件序列。这将查看每个序列并简单地选择最有可能的序列。

于 2013-02-07T06:28:22.787 回答
0

看看Rabiner 论文的第 262 - 264 页,一切都会变得清晰。这是一个直接引用的答案——来自这篇论文——你的问题:

“......应该注意的是,Viterbi 算法在实现上与前向-后向算法的前向计算(方程 19-21)相似(除了回溯步骤)。主要区别在于(方程 33a)中的最大化) 超过先前的状态,用于代替(等式 20)中的求和过程。”

于 2013-07-10T10:26:10.257 回答