Iterativní Viterbiho dekódování - Iterative Viterbi decoding

Iterativní Viterbiho dekódování je algoritmus který spatří posloupnost S pozorování Ó = {Ó1, ..., Ón} s nejvyšší průměrnou pravděpodobností (tj. pravděpodobnost se stupnicí o délku S) generování daným skrytý Markovův model M s m státy. Algoritmus používá upravený Viterbiho algoritmus jako vnitřní krok.

Měřítko měřítka pravděpodobnosti bylo poprvé navrženo uživatelem John S. Bridle. Časný algoritmus k vyřešení tohoto problému, Posuvné okno, navrhl Jay G. Wilpon et al., 1989, se stálými náklady T = mn2/2.

Rychlejší algoritmus se skládá z iterace volání do Viterbiho algoritmus, přehodnocení skóre výplně až do konvergence.

Algoritmus

Základní (neoptimalizovaná) verze, hledání sekvence s s nejmenší normalizovanou vzdáleností od nějaké posloupnosti t je:

// vstup je umístěn do pozorování s [1..n], šablona t [1..m], // a [[matice vzdálenosti]] d [1..n, 1..m] // zbývající prvky v matice jsou pouze pro interní výpočty (int, int, int) AverageSubmatchDistance (char s [0 .. (n + 1)], char t [0 .. (m + 1)], int d [1..n, 0 .. (m + 1)]) {// skóre, začátek subsekvence, konec subsekvence deklarovat int e, B, E t '[0]: = t' [m + 1]: = s '[0]: = s '[n + 1]: =' e 'e: = random () do e': = e pro i: = 1 až n do d '[i, 0]: = d' [i, m + 1]: = e (e, B, E): = ViterbiDistance (s ', t', d ') e: = e / (E-B + 1) do (e == e') návrat (e, B, E) }

Procedura ViterbiDistance () vrací n-tici (E, B, E), tj. skóre Viterbi “E"na zápas t a vybraná položka (B) a výstup (E) body z toho. "B" a "E„musí být zaznamenány pomocí jednoduché úpravy Viterbi.

Modifikace, kterou lze použít na tabulky CYK, kterou navrhl Antoine Rozenknop, spočívá v odečtení E ze všech prvků počáteční matice d.

Reference

  • Silaghi, M., „Spotting Subsequences matching a HMM using the Average Observation Probability Criteria with application to Keyword Spotting", AAAI, 2005.
  • Rozenknop, Antoine a Silaghi, Marius; „Algorithme de décodage de treillis selon le critère de coût moyen pour la reconnaissance de la parole“, TALN 2001.

Další čtení

  • Li, Huan-Bang; Kohno, Ryuji (2006). Efektivní struktura kódu blokově kódovaných modulací s iteračním Viterbiho dekódovacím algoritmem. 3. mezinárodní symposium o bezdrátových komunikačních systémech. Valencie, Španělsko: IEEE. doi:10.1109 / ISWCS.2006.4362391. ISBN  978-1-4244-0397-4.
  • Wang, Qi; Wei, Lei; Kennedy, R.A. (Leden 2002). „Iterativní Viterbiho dekódování, tvarování mřížoviny a víceúrovňová struktura pro vysokorychlostní TCM zřetězené TCM“. Transakce IEEE na komunikaci. 50 (1): 48–55. doi:10.1109/26.975743. ISSN  0090-6778.