反復ビタビ復号法は、観測値O = { o 1 , ..., o n } の部分列Sのうち、 m個の状態を持つ隠れマルコフモデルMによって生成される確率（つまり、 Sの長さでスケールされた確率）が最も高いものを見つけるアルゴリズムです。このアルゴリズムは、修正ビタビアルゴリズムを内部ステップとして 用います。
スケール化確率測度は、ジョン・S・ブライドルによって初めて提案されました。この問題を解くための初期のアルゴリズムであるスライディングウィンドウは、ジェイ・G・ウィルポンらによって1989年に提案され、定数コストT = mn 2 /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のための反復ビタビ復号法、トレリスシェーピング、およびマルチレベル構造」. IEEE Transactions on Communications . 50 (1): 48– 55. doi :10.1109/26.975743. ISSN 0090-6778.
