Descodificación iterativa de Viterbi

La decodificación iterativa de Viterbi es un algoritmo que detecta la subsecuencia S de una observación O = { o ₁ , ..., o _n } que tiene la mayor probabilidad promedio (es decir, probabilidad escalada por la longitud de S ) de ser generada por un modelo oculto de Markov M con m estados. El algoritmo utiliza un algoritmo de Viterbi modificado como paso interno.

La medida de probabilidad escalada fue propuesta por primera vez por John S. Bridle. Un algoritmo temprano para resolver este problema, la ventana deslizante , fue propuesto por Jay G. Wilpon et al., 1989, con un costo constante T = mn ² /2.

Un algoritmo más rápido consiste en una iteración de llamadas al algoritmo de Viterbi , reestimando una puntuación de relleno hasta la convergencia.

Una versión básica (no optimizada), que encuentra la secuencia s con la menor distancia normalizada desde alguna subsecuencia de t, es:

// la entrada se coloca en la observación s[1..n], plantilla t[1..m],
// y [[matriz de distancias]] d[1..n,1..m]
// Los elementos restantes en las matrices son únicamente para cálculos internos.
(int, int, int) DistanciaSubcoincidenciaPromedio(char s[0..(n+1)], char t[0..(m+1)], int d[1..n,0..(m+1)]) {
    // puntuación, inicio de subsecuencia, fin de subsecuencia
    declarar int e, B, E
    t'[0] := t'[m+1] := s'[0] := s'[n+1] := 'e'

    e := aleatorio()
    hacer
        y' := y
	para i := 1 a n hacer d'[i,0] := d'[i,m+1] := e
	(e, B, E) := ViterbiDistancia(s', t', d')
        e := e/(E-B+1)
    hasta (e == e')

    devolver (e, B, E)
}

El procedimiento ViterbiDistance() devuelve la tupla ( e , B , E ), es decir, la puntuación de Viterbi " e " para la coincidencia de t y los puntos de entrada ( B ) y salida ( E ) seleccionados de ella. " B " y " E " deben registrarse utilizando una modificación simple de Viterbi.

Una modificación que se puede aplicar a las tablas CYK, propuesta por Antoine Rozenknop, consiste en restar e de todos los elementos de la matriz inicial d .

• Silaghi, M., "Detección de subsecuencias que coinciden con un HMM utilizando el criterio de probabilidad de observación promedio con aplicación a la detección de palabras clave", AAAI, 2005.
• Rozenknop, Antoine y Silaghi, Marius; "Algoritmo de décodage de treillis según le critère de coût moyen pour la reconnaissance de la parole", TALN 2001.

• Li, Huan-Bang; Kohno, Ryuji (2006). Una estructura de código eficiente de modulaciones codificadas por bloques con un algoritmo de decodificación iterativo de Viterbi . Tercer Simposio Internacional sobre Sistemas de Comunicación Inalámbrica. Valencia, España: IEEE. doi :10.1109/ISWCS.2006.4362391. ISBN . 978-1-4244-0397-4.
• Wang, Qi; Wei, Lei; Kennedy, RA (enero de 2002). "Decodificación iterativa de Viterbi, modelado de enrejado y estructura multinivel para TCM concatenado con paridad de alta velocidad". IEEE Transactions on Communications . 50 (1): 48– 55. doi :10.1109/26.975743. ISSN  0090-6778.