ビタビアルゴリズムは次のとおりです。
コメント
- アルゴリズムの説明（こことここ）はあなたの質問に答えますか、それとも探していますか他の何かのために？どのアルゴリズムをいつ使用するか疑問に思っていますか？それぞれのメリットについてのディスカッションをお探しですか？
回答
最初に少し背景を説明すると、問題が解決する可能性があります。少し。
HMM（隠れマルコフモデル）について話すとき、考慮すべき一般的に3つの問題があります：
-
評価の問題
- 評価の問題は、特定のシンボルのシーケンスが特定のモデルによって生成される確率はどれくらいかという質問に答えます。
- 評価には、フォワードアルゴリズムまたはバックワードアルゴリズムの2つのアルゴリズムを使用します（フォワードバックワードアルゴリズムと混同しないでください）。
-
デコードの問題
- デコードの問題が次の質問に答えます。一連のシンボル（観測値）とモデルが与えられた場合、そのシーケンスを生成した最も可能性の高い状態のシーケンスは何ですか。
- デコードには、ビタビアルゴリズムを使用します。
-
トレーニングの問題
- トレーニングの問題は質問に答えます：モデル構造とシーケンスのセットが与えられたら、データに最適なモデルを見つけます。
- この問題では、次の3つのアルゴリズムを使用できます。
- MLE（最大尤度推定）
- ビタビトレーニング（ビタビデコードと混同しないでください）
- Baum Welch =前方後方アルゴリズム
要約すると、ビタビアルゴリズムを使用して一連のシーケンスでモデルをトレーニングする場合のデコードの問題とバウムウェルチ/前方後方。
バウムウェルチは次のように機能します。
シーケンスのトレーニングセット内の各シーケンスについて。
- フォワードアルゴリズムを使用してフォワード確率を計算します
- バックワードアルゴリズムを使用して後方確率を計算します
- モデルの遷移に対する現在のシーケンスの寄与を計算し、モデルの放出確率に対する現在のシーケンスの寄与を計算します。
- 新しいモデルパラメータ（開始確率、遷移確率、放出確率）を計算します。 ）
- を計算しますモデルの新しい対数尤度
- 対数尤度の変化が指定されたしきい値よりも小さい場合、または最大反復回数を超えた場合に停止します。
必要な場合ビタビ復号とトレーニングアルゴリズムの方程式の完全な説明を教えていただければ、正しい方向に向けることができます。
コメント
- こんにちは。パスを保存すると、フォワードアルゴリズムを使用した評価中に、冗長なデコードにビタビアルゴリズムが使用されますか？
回答
Forward-Backwardは、各個々の状態の周辺確率を示し、Viterbiは、最も可能性の高い一連の状態の確率を示します。たとえば、HMMタスクが毎日の晴れと雨の天気を予測することである場合、Forward Backwardは毎日の「晴れ」の確率を示し、Viterbiは晴れ/雨の日の最も可能性の高いシーケンスを示します。このシーケンスの確率。
回答
{2}の次の2つのスライドは、前方に配置するのに非常に適していると思います。 -HMMで使用される他のすべての一般的なアルゴリズムの中でも特に後方アルゴリズムとビタビアルゴリズム：
注：
- $ x $は観測された放出、$ \ pi $はHMMのパラメーターです。
- path =一連の放出
- デコード=推論
- 学習=トレーニング=パラメーター推定
- 一部の論文（たとえば、{1}）は、バウムウェルチは前方後方アルゴリズムと同じであると主張していますが、私はMasterfoolとWikipediaを使用したee：Baum–Welchは、前方後方アルゴリズムを使用する期待値最大化アルゴリズムです。 2つの図は、バウムウェルチアルゴリズムと前方後方アルゴリズムも区別しています。
参照：
- {1} Lember、Jüri、Alexeyコロイデンコ。 「隠れマルコフモデルの調整済みビタビトレーニング。」ベルヌーイ14、いいえ。 1（2008）：180-206。
- {2} 6.047 / 6。878計算生物学：ゲノム、ネットワーク、進化（2012年秋）レクチャー07-HMM II（2012-09-29） http://stellar.mit.edu/S/course/6/fa12/6.047/courseMaterial/topics/topic2/lectureNotes/Lecture07_HMMsIIb_6up/Lecture07_HMMsIIb_6up.pdf （Manolis Kellis）：
回答
Moratの回答は1つの点で誤りです：バウム-ウェルチは期待値最大化アルゴリズムであり、HMMのパラメーターをトレーニングするために使用されます。各反復中に前方後方アルゴリズムを使用します。フォワードバックワードアルゴリズムは、実際にはフォワードアルゴリズムとバックワードアルゴリズムの単なる組み合わせです。1つのフォワードパス、1つのバックワードパスです。前方後方アルゴリズムは、それ自体では、HMMのパラメーターのトレーニングには使用されませんが、平滑化、つまり一連の状態の周辺尤度の計算にのみ使用されます。
https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm
回答
@Yaroslav Bulatovが正確な回答をしました。その一例を追加して、フォワードバックワードアルゴリズムとビテルビアルゴリズムの違い。
このHMMがあるとします（Wikipedia HMMページから）。注：モデルはすでに指定されているため、ここではデータタスクからの学習はありません。
データが長さ4のシーケンスであるとします。(Walk, Shop, Walk, Clean)。2つのアルゴリズムで異なる結果が得られます。
- 前方後方アルゴリズムは、確率を与えます各隠し状態のlity 。これが例です。表の各列の合計は$ 1 $になることに注意してください。
- ビタビアルゴリズムは、最も可能性の高い非表示状態のシーケンスを提供します。これが例です。この隠れた状態のシーケンスに関連する確率もあることに注意してください。このシーケンスには最大の確率があります。他のすべてのシーケンス（たとえば、すべての
SunnyからすべてのRainyまでの$ 2 ^ 4 = 16 $シーケンス）。
ここにいくつかありますRデモのコード
library(HMM) # in education setting, # hidden state: Rainy and Sunny # observation: Walk, Shop, Clean # state transition P <- as.matrix(rbind(c(0.7,0.3), c(0.4,0.6))) # emission prob R <- as.matrix(rbind(c(0.1, 0.4, 0.5), c(0.6,0.3, 0.1))) hmm = initHMM(States=c("Rainy","Sunny"), Symbols=c("Walk","Shop", "Clean"), startProbs=c(0.6,0.4), transProbs=P, emissionProbs=R) hmm obs=c("Walk","Shop","Walk", "Clean") print(posterior(hmm,obs)) print(viterbi(hmm, obs))