algorithm - 前方後方アルゴリズムとビタビ アルゴリズムの違いは何ですか?

Question

n-gram モデルのフォワード-バックワード アルゴリズムと隠れマルコフ モデル (HMM) のビタビ アルゴリズムの違いは何ですか?

これら 2 つのアルゴリズムの実装を確認したところ、トランザクションの確率が異なる確率モデルから来ていることがわかりました。

これら2つのアルゴリズムに違いはありますか?

Answer 1

Forward-Backward アルゴリズムは、前方ステップと後方ステップを組み合わせて、特定の時間に各状態にある確率を取得します。したがって、すべての時間ステップに対してこれを行うと、各時点で個々に最も可能性の高い状態のシーケンスを得ることができます (ただし、各ステップで個々の状態を考慮p(q_i -> q_j)=0し、遷移モデルの確率が発生する可能性があるため、有効なシーケンスであるとは限りません)。 、 言い換えると：

、 どこ

一方、ビタビ アルゴリズムは、異なる最適性基準を最大化することにより、観測シーケンスが与えられた場合に最も可能性の高い状態シーケンスを見つけます。

詳細な説明については、このよく知られた論文を参照することをお勧めします (問題 #2 を参照)。

LAWRENCE R. RABINER、隠れマルコフ モデルに関するチュートリアルと音声認識における選択されたアプリケーション

Answer 2

簡潔に言えば：

Forward-Backwardは、ある特定の時点で最も可能性の高いトークンが何であるかを予測する場合にのみ使用されます。考えられるすべてのシーケンスを考慮に入れ、それらを平均して、その時点で最も可能性の高いトークンを見つけます。したがって、返されるシーケンスは真のシーケンスではなく、考えられるすべてのシーケンスを考慮した場合に最も可能性の高いトークンのコレクションになります。

Viterbiは、最も可能性の高い一連のイベントを見つけるために使用されます。これにより、すべてのシーケンスが調べられ、最も可能性の高いシーケンスが選択されます。

Answer 3

Rabiner の論文の262 ～ 264 ページを見てみると、すべてが明らかになるはずです。あなたの質問に対するこの論文からの直接引用された回答は次のとおりです。

「...ビタビ アルゴリズムは、(バックトラッキング ステップを除いて) 実装において、前方後方アルゴリズムの前方計算 (式 19-21) に似ていることに注意してください。主な違いは、(式 33a (式 20) の合計手順の代わりに使用されます。