隠しマルコフモデルのためのパラレルフォワード - バックワードアルゴリズム

Question

サイドプロジェクトとして、NVidiaグラフィックスカードに隠れマルコフモデルを実装して、素早く多くのコアを使用できるようにします。

私はフォワード - バックワードアルゴリズムを見ていて、そこには何ができるのだろうと思っていましたか？たとえば、アルゴリズムの前方部分を見ると、行列乗算は分割して並列に実行できますが、前のステップに依存するアルゴリズムの反復部分はどのようにも並列化できますか？ここに適用できる数学的なトリックがありますか？

おかげで、

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は、再帰的なステップを並列化できないことを指摘していますが、これらの著者は、ForwardおよびViterbiアルゴリズムを一連の行列乗算および減算に減らす巧妙な方法を考え出しています。