La decodificación iterativa de Viterbi es un algoritmo que detecta la subsecuencia S de una observación O = { o 1 , ..., o n } que tiene la probabilidad promedio más alta (es decir, la probabilidad escalada por la longitud de S ) de ser generada por un objeto oculto dado. Modelo M de Markov con estados m . 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, ventana deslizante , fue propuesta por Jay G. Wilpon et al., 1989, con el coste constante T = mn 2 /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.
El algoritmo
Una versión básica (no optimizada), encontrar la secuencia s con la distancia normalizada más pequeña de 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) AverageSubmatchDistance (char s [0 .. (n + 1)], char t [0 .. (m + 1)], int d [1..n, 0 .. (m + 1 )]) { // puntuación, inicio de subsecuencia, final de subsecuencia declare int e, B, E t '[0]: = t' [m + 1]: = s '[0]: = s' [n + 1]: = 'e' e: = aleatorio () hacer e ': = epara i: = 1 an do d '[i, 0]: = d' [i, m + 1]: = e(e, B, E): = ViterbiDistance (s ', t', d ') e: = e / (E-B + 1) hasta (e == e ') volver (e, B, E)}
El procedimiento ViterbiDistance () devuelve la tupla ( e , B , E ), es decir, la puntuación de Viterbi " e " para la coincidencia de ty los puntos de entrada ( B ) y salida ( E ) seleccionados. " B " y " E " deben registrarse mediante una simple modificación 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 .
Referencias
- Silaghi, M., "Detección de subsecuencias que coinciden con un HMM utilizando los criterios de probabilidad de observación promedio con aplicación a la detección de palabras clave", AAAI, 2005.
- Rozenknop, Antoine y Silaghi, Marius; "Algorithme de décodage de treillis selon le critère de coût moyen pour la reconnaissance de la parole", TALN 2001.
Otras lecturas
- Li, Huan-Bang; Kohno, Ryuji (2006). Una estructura de código eficiente de modulaciones codificadas en bloques con algoritmo de decodificación iterativo de Viterbi . 3er Simposio Internacional de Sistemas de Comunicación Inalámbricos. 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 por paridad de alta velocidad". Transacciones IEEE sobre comunicaciones . 50 (1): 48–55. doi : 10.1109 / 26.975743 . ISSN 0090-6778 .