反復ビタビ復号

反復ビタビ復号化は、m 個の状態を持つ特定の隠れマルコフモデルM によって生成される平均確率が最も高い観測値O = { o 1 _、 ...、o _n }の部分列Sを見つけるアルゴリズムです(つまり、 Sの長さでスケールされた確率) 。このアルゴリズムは、内部ステップとして 修正ビタビアルゴリズムを使用します。

スケールされた確率測度は、John S. Bridle によって初めて提案されました。この問題を解決するための初期のアルゴリズムであるスライディング ウィンドウは、Jay G. Wilpon らによって 1989 年に提案され、一定のコストT = mn ² /2 でした。

より高速なアルゴリズムは、 Viterbi アルゴリズムの呼び出しを繰り返し、収束するまでフィラー スコアを再推定するものです。

基本的な（最適化されていない）バージョンでは、 tのサブシーケンスからの正規化された距離が最小のシーケンスs を見つけます。

// 入力は観測s[1..n]、テンプレートt[1..m]に配置されます。
// および [[距離行列]] d[1..n,1..m]
// 行列の残りの要素は内部計算専用です
(int, int, int) 平均サブマッチ距離(char s[0..(n+1)], char t[0..(m+1)], int d[1..n,0..(m+1)]) {
    // スコア、サブシーケンスの開始、サブシーケンスの終了
    int e, B, E を宣言する
    t'[0] := t'[m+1] := s'[0] := s'[n+1] := 'e'

    e := ランダム()
    する
        e' := e
	i := 1 から n まで、d'[i,0] := d'[i,m+1] := e を実行する。
	(e, B, E) := ViterbiDistance(s', t', d')
        e := e/(E-B+1)
    (e == e') まで

    戻り値 (e, B, E)
}

ViterbiDistance() プロシージャは、タプル ( e、B、E )、つまり、 tとそこから選択されたエントリ ( B ) および終了 ( E ) ポイントとの一致に対するViterbi スコア「e 」を返します。「 B」と「E」は、Viterbi に簡単な変更を加えて記録する必要があります。

Antoine Rozenknop によって提案された CYK テーブルに適用できる変更は、初期行列dのすべての要素からe を減算することです。

• Silaghi, M.、「平均観測確率基準を使用した HMM に一致するサブシーケンスのスポッティングとキーワード スポッティングへの応用」、AAAI、2005 年。
• ローゼンノック、アントワーヌ、シラーギ、マリウス。 「保護観察のための監視アルゴリズムのアルゴリズム」、TALN 2001。

• Li, Huan-Bang; Kohno, Ryuji (2006).反復ビタビ復号アルゴリズムによるブロック符号化変調の効率的なコード構造。第3回ワイヤレス通信システム国際シンポジウム。スペイン、バレンシア：IEEE。doi ： 10.1109/ ISWCS.2006.4362391。ISBN 978-1-4244-0397-4。
• Wang, Qi; Wei, Lei; Kennedy, RA (2002 年 1 月)。「高速パリティ連結 TCM の反復 Viterbi 復号、トレリス シェーピング、およびマルチレベル構造」。IEEE Transactions on Communications。50 (1): 48–55。doi : 10.1109 /26.975743。ISSN 0090-6778  。