HMMで上位k個のビタビパスを見つけるアルゴリズムを作成する必要があります（通常のビタビアルゴリズムを使用して最適なパスを見つけます）。
状態Nで終わる上位K個のパスを含む状態NごとにサイズkのリストV_t、Nを保存する必要があると思いますが、そのリストを追跡する方法がわかりません。ありがとう
7875 次
2 に答える
19
これは注意して解決できます。うーんのトレリス構造を見ると最もわかりやすいです。
この例では、非表示の状態は00、01、10、11であり、これら4つのセットをSとして示します。観測値は表示されていませんが、0、1であると想定しています。
正しい遷移行列があると仮定します。
transition[4][4]
放出確率：
emissions[4][2]
そして初期確率：
p[2]
したがって、すべての列は非表示の状態を表します。Viterbiの目標は、観測値が与えられた場合に最も可能性の高い非表示の状態シーケンスを計算することです。ここで、alpha（i、t）=時間tでの観測値がo_t（o_tは1）である時間tで、隠れた状態シーケンスが状態i（iは00、01、10、11のいずれか）にある最大の確率とします。 0、1）の。最初の観測をo_1と表記します。次のように効率的に計算できます。
alpha(i, 1) = p[i] * emissions[i][o_1]
alpha(i, t) = emissions[i][o_t] * max_{k in states} (alpha(k, t-1) * transition[k][i])
最適なパスを見つけるために、alpha（i、t）ステップで、上記のmax関数を最大化した状態へのポインターを逆方向に保持します。最後に、すべてのalpha（i、T）と状態のiを調べて、どれが最大であるかを見つけ、それをたどって最も可能性の高い状態シーケンスを取得します。
次に、これを拡張して上位のkパスを格納する必要があります。現在、各alpha（i、t）には、1つの親のみが格納されています。ただし、上位k個の先行タスクを保存したとします。したがって、各alpha（i、t）は、最も可能性の高い値と遷移元のノードだけでなく、遷移元の上位k個のノードとそれらの値のソートされた順序のリストにも対応します。
これは、maxを実行する代わりに、1つの先行ノードのみを取得するという点で簡単に実行でき、上位k個の先行ノードを取得してそれらを格納します。基本ケースの場合、先行ノードがないため、alpha（i、1）はまだ単一の値です。任意の列（たとえばt）に到達し、その列のノード（i）で終わる上位k個のパスを見つけたい場合は、上位k個の先行パスとそれらから取得する上位パスを見つける必要があります。
これは、次の問題があるかのようです。サイズ4 x kの行列mです。ここで、行は先行する状態を表し、m[state]はそこで終了するパスの上位k個の確率を表します。したがって、mの各行は最大から最小にソートされ、問題は次のようになります。
Best_K_Values(t, i) = Top K over all i,preceding_state,k (emissions[i][o_t] * m[preceding_state][k] * transition[preceding_state][i])
これは気が遠くなるように見えますが、理解するのに少し時間がかかります。一般にO（4 log k）またはO（numStates log k）のヒープを使用して、ソートされた行列の問題から上位kを解くことができます。
ソートされた行列のこのわずかな変化K番目の最小要素を参照してください。この場合、列はソートされていませんが、そこにある考え方は引き続き適用されます。
まだ読んでいる場合は、このメソッドの全体的な複雑さはO（（numStates log k）* numStates * t）= O（numStates ^ 2 * t * log k）であることに注意してください（これは正しい複雑さだと思います）。
これを理解するのは難しいかもしれませんが、質問がある場合、または私が何か間違ったことをした場合はお知らせください。
于 2013-03-16T20:26:24.110 に答える
3
これについては実際に広範な文献があります。少し掘り下げましたが、これを見つけました。
アプリケーションを使用したビタビ復号アルゴリズムのリスト
http://www.ensc.sfu.ca/people/faculty/cavers/ENSC805/readings/42comm02-seshadri.pdf
于 2014-12-22T04:08:03.457 に答える