隱馬爾可夫模型的並行前後向算法

Question

作爲一個側面項目，我想爲我的NVidia顯卡實現隱馬爾可夫模型，這樣我就可以快速執行並使用多個內核。

我正在查看Forward-Backward算法，並想知道我能在這裏做什麼並行？例如，如果您查看算法的前向部分，可以將矩陣乘法劃分爲並行執行，但是可以將依賴於上一步的算法的迭代部分以任何方式並行化？在這裏可以應用某種數學技巧嗎？

感謝，

MJ

http://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm#Example

Answer 1

你在你的評估正確 - 你可以並行化矩陣乘法（即跨州），但你不能並行遞歸步驟。我剛剛在我的HMM和GPU上做了一篇博客文章。看看這裏：

http://sgmustadio.wordpress.com/2012/02/27/hidden-markov-models-in-cuda-gpu/

Answer 2

如果你仍然在這個項目上工作，你可能想看看HMMlib和parredHMMlib。

sgmustadio指出你不能並行遞歸步驟是正確的，但似乎這些作者提出了一種聰明的方法來將正向和維特比算法減少爲一系列矩陣乘法和縮減。