Décodage itératif de Viterbi

Le décodage itératif de Viterbi est un algorithme qui identifie la sous-séquence S d'une observation O = { o ₁ , ..., o _n } ayant la probabilité moyenne la plus élevée (c'est-à-dire la probabilité mise à l'échelle par la longueur de S ) d'être générée par un modèle de Markov caché M donné à m états. L'algorithme utilise un algorithme de Viterbi modifié comme étape interne.

La mesure de probabilité échelonnée a été proposée pour la première fois par John S. Bridle. Un algorithme précoce pour résoudre ce problème, la fenêtre glissante , a été proposé par Jay G. Wilpon et al., 1989, avec un coût constant T = mn ² /2.

Un algorithme plus rapide consiste en une itération d'appels à l' algorithme de Viterbi , réestimant un score de remplissage jusqu'à convergence.

Une version de base (non optimisée), trouvant la séquence s avec la plus petite distance normalisée à partir d'une sous-séquence de t est :

// l'entrée est placée dans l'observation s[1..n], modèle t[1..m], // et [[matrice de distance]] d[1..n,1..m] // les éléments restants dans les matrices sont uniquement destinés aux calculs internes (int, int, int) Distance de sous-correspondance moyenne (caractère s [0..(n+1)], caractère t [0..(m+1)], int d [1..n,0..(m+1)]) { // score, début de la sous-séquence, fin de la sous-séquence déclarer int e, B, E t'[0] := t'[m+1] := s'[0] := s'[n+1] := 'e' e := aléatoire() faire e' := e pour i := 1 à n faire d'[i,0] := d'[i,m+1] := e (e, B, E) := ViterbiDistance(s', t', d') e := e/(E-B+1) jusqu'à ce que (e == e') retour (e, B, E) } 

La procédure ViterbiDistance() renvoie le tuple ( e , B , E ), c'est-à-dire le score de Viterbi " e " pour la correspondance de t et les points d'entrée ( B ) et de sortie ( E ) sélectionnés. " B " et " E " doivent être enregistrés à l'aide d'une simple modification de Viterbi.

Une modification applicable aux tables CYK, proposée par Antoine Rozenknop, consiste à soustraire e de tous les éléments de la matrice initiale d .

• Silaghi, M., « Repérage de sous-séquences correspondant à un HMM à l'aide des critères de probabilité d'observation moyenne avec application au repérage de mots-clés », AAAI, 2005.
• Rozenknop, Antoine, et Silaghi, Marius ; "Algorithme de décodage de treillis selon le critère de coût moyen pour la reconnaissance de la parole", TALN 2001.

• Li, Huan-Bang ; Kohno, Ryuji (2006). Une structure de code efficace pour les modulations codées par blocs avec un algorithme de décodage itératif de Viterbi . 3e Symposium international sur les systèmes de communication sans fil. Valence, Espagne : IEEE. doi :10.1109/ISWCS.2006.4362391. ISBN 978-1-4244-0397-4.
• Wang, Qi ; Wei, Lei ; Kennedy, RA (janvier 2002). « Décodage Viterbi itératif, mise en forme en treillis et structure multiniveau pour TCM à parité concaténée à haut débit ». IEEE Transactions on Communications . 50 (1) : 48–55. doi : 10.1109/26.975743. ISSN 0090-6778.