Iterativ Viterbi-avkodning

Iterativ Viterbi-avkodning är en algoritm som upptäcker undersekvensen S av en observation O = { o ₁ , ..., o _n } som har den högsta genomsnittliga sannolikheten (dvs. sannolikheten skalad med längden på S ) att genereras av en given dold Markov modell M med m tillstånd. Algoritmen använder en modifierad Viterbi-algoritm som ett internt steg.

Det skalade sannolikhetsmåttet föreslogs först av John S. Bridle. En tidig algoritm för att lösa detta problem, glidande fönster , föreslogs av Jay G. Wilpon et al., 1989, med konstant kostnad T = mn ² /2.

En snabbare algoritm består av en iteration av anrop till Viterbi-algoritmen , som omskattar ett utfyllnadspoäng tills konvergens.

Algoritmen

En grundläggande (icke-optimerad) version, att hitta sekvensen s med det minsta normaliserade avståndet från någon undersekvens av t är:

// input placeras i observation s[1..n], mall t[1..m], // och [[avståndsmatris]] d[1..n,1..m] // återstående element i matriser är endast för interna beräkningar (int, int, int) AverageSubmatchDistance(char s[0..(n+1)], char t[0..(m+1)], int d[1..n,0 ..(m+1)]) { // poäng, sekvensstart, sekvensslut deklarera int e, B, E t'[0] := t'[m+1] := s'[0] := s '[n+1] := 'e' e := random() gör e' := e för i := 1 till n gör d'[i,0] := d'[i,m+1] : = e (e, B, E) := ViterbiDistance(s', t', d') e := e/(E-B+1) tills (e == e') returnerar (e, B, E) }

Proceduren ViterbiDistance() returnerar tupeln ( e , B , E ), dvs. Viterbi-poängen " e " för matchningen av t och de valda ingångs- ( B ) och utgångspunkterna ( E ) från den. " B " och " E " måste spelas in med en enkel modifiering av Viterbi.

En modifiering som kan tillämpas på CYK-tabeller, föreslagen av Antoine Rozenknop, består i att subtrahera e från alla element i den initiala matrisen d .

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

Vidare läsning

•   Li, Huan-Bang; Kohno, Ryuji (2006). En effektiv kodstruktur av blockkodade moduleringar med iterativ Viterbi-avkodningsalgoritm . Tredje internationella symposiet om trådlösa kommunikationssystem. Valencia, Spanien: IEEE. doi : 10.1109/ISWCS.2006.4362391 . ISBN 978-1-4244-0397-4 .
•   Wang, Qi; Wei, Lei; Kennedy, RA (januari 2002). "Iterativ Viterbi-avkodning, spaljéformning och flernivåstruktur för höghastighetsparitetskonkatenerad TCM". IEEE-transaktioner på kommunikation . 50 (1): 48–55. doi : 10.1109/26.975743 . ISSN 0090-6778 .