¿Qué es una explicación intuitiva del algoritmo de Viterbi?

Answer 1

No sé cuán intuitivo alguien encontrará esta explicación, pero aquí va. Un algoritmo de Viterbi encuentra el código Viterbi * más probable válido de una señal recibida ruidosa. Un algoritmo de Viterbi analiza el estado actual recibido de la señal y la serie de estados anteriores para decidir cuál es el valor verdadero más probable del estado actual.

Un ejemplo simplista y no riguroso podría ayudar.
Digamos que tenemos un codificador que solo genera la secuencia: 1-> 3-> 5
Recibimos la señal 1-> 2-> 5
La probabilidad de 1-> 2 es cero, ¡Uh-Oh!
Pero espere, la probabilidad de 1-> 3 es del 100%, por lo que detectamos y corregimos el código recibido a 1-> 3
El último paso es fácil. 3-> 5 es una transición válida, por lo que aceptamos que es cierto

* El “código de Viterbi” parece estar fuera de moda en estos días y sigue el término más general “código de convolución”.

Referencias
La entrada de Wikipedia para el Algoritmo de Viterbi es bastante sencilla e incluso incluye algunos códigos de muestra de Java: http://en.wikipedia.org/wiki/Vit…

El libro InformationTheory and Reliable Communication de Robert G. Gallager proporciona un tratamiento sólido de los códigos de convolución en las páginas 258-273 (ADVERTENCIA: este es uno de los textos de referencia más duros que he encontrado, más de 500 páginas de pared a pared ecuaciones y pruebas de nivel de posgrado)

Answer 2

Como respuesta intuitiva, considérelo como un crucigrama:

Tienes algunas letras en las que confías mucho, algunas de las que no estás muy seguro, así que las escribes con lápiz (‘partes blandas’ o similares son descripciones de esa confianza), y conoces una ‘regla’ para ayudar a tus decisiones y para corregir errores (en crucigramas, es decir, las palabras deben ser inglesas; en códigos convolucionales es el polinomio)

p.ej
tienes cama
Confías mucho en la D, la E en absoluto: puede ser una A, así que la has escrito con lápiz

entonces obtienes ‘L’ como la siguiente letra y estás muy seguro de eso

Entonces BEDL

hmm … parece extraño …

luego una ‘Y’ – nuevamente con alta confianza

Cama?

y ahora decides que BEDLY no es una palabra …
Pero la E podría ser una A, que da MALO, que es una palabra

Entonces aceptas eso y sigues adelante.

(Tal vez sea TRISTE, tal vez lo corrija más tarde o tal vez sea un error irrecuperable)

Viterbi rastrea la confianza de los bits recibidos y de la secuencia general (métricas de ruta)

Por supuesto, los crucigramas son 2D: puede usar palabras hacia abajo para verificar y viceversa). Ese refinamiento es (parte de) lo que le da códigos Turbo que son más importantes y utilizados en sistemas más modernos.

Answer 3

El algoritmo de Viterbi se utiliza para encontrar la secuencia de estado oculta más probable en una secuencia observable, cuando la probabilidad de una secuencia no observable puede descomponerse en un producto de probabilidades. En teoría, para una secuencia de N palabras con K posibles etiquetas, podríamos calcular todas las probabilidades de todas las secuencias posibles de K ^ N, y encontrar el máximo, pero tendríamos un tiempo de ejecución exponencial en la longitud de la lista. Lo que el algoritmo de Viterbi aprovecha es que la única operación para encontrar estas probabilidades es la multiplicación. Por lo tanto, para todos los caminos que terminan en una categoría específica (por ejemplo, V), el camino con mayor probabilidad que termina en V se unirá por encima de todos los otros caminos que terminan en V para todas las expansiones futuras de V. Dicho de otra manera, tome dos caminos posibles DN y VN, digamos con probabilidades de ejecución 0.9 y 0.1, respectivamente, como análisis para las dos primeras palabras de la secuencia de fichas “el hombre comió la lasaña”. Ninguna secuencia posible de mejores etiquetas (digamos VDN) puede hacer que DVVDN sea más probable que NVVD N. Dado que solo nos preocupamos por la secuencia de etiquetas más probable, con Viterbi, solo necesitamos mantener K posibles análisis con totales acumulados en cada paso, porque sabemos que el análisis final más probable de K será mayor que todas las demás rutas, incluso las rutas que no calculamos explícitamente. El resultado es un algoritmo optimizado con N * (K ^ 2) en lugar de K ^ N tiempo de ejecución.