Java中的维特比算法

Question

我正在学习 coursera NLP 课程，第一个编程任务是构建 Viterbi 解码器。我想我真的快要完成它了，但是有一些我似乎无法追踪的难以捉摸的错误。这是我的代码：

http://pastie.org/private/ksmbns3gjctedu1zxrehw

http://pastie.org/private/ssv6tc8dwnamn2qegdvww

到目前为止，我已经调试了与“教学”相关的函数，所以我可以说算法的参数正在被正确估计。特别感兴趣的是 viterbi() 和 findW() 方法。我正在使用的算法的定义可以在这里找到：http : //www.cs.columbia.edu/~mcollins/hmms-spring2013.pdf第 18 页。

我很难理解的一件事是，当 K = {1, 2} 时，我应该如何更新特殊情况的反向指针（在我的情况下，这是 0 和 1，因为我是零-索引我的数组）分别在这些情况下我使用的参数是 q({TAGSET} | *, *) 和 q ({TAGSET} | *, {TAGSET})。

提示而不是勺子喂的答案也将受到高度赞赏！

Answer 1

以下是一些建议：

1. 如果您对模型中如何发生转换有任何困惑，您应该绘制 HMM 晶格。例如，您可以将到第一个隐藏状态的转换视为源自单个起始隐藏状态，因此 k=0 的反向指针必须始终指向此起始状态。在您的代码中，您可能不应该循环遍历 k=0 的隐藏状态findW（这似乎是正确的），但您可能应该循环 k=1。

2. 通常，在 HMM 推理中相乘转移概率和发射概率会导致非常小的浮点值，这可能会导致数值错误。您应该添加对数概率而不是乘以概率。

3. 为了检查维特比或前向-后向实现，我通常还会编写一个强力方法并比较每个方法的输出。如果暴力算法和动态编程算法在短序列上匹配，那么就可以合理地衡量两者都是正确的。