¿Cuál es la diferencia entre los algoritmos forward-backward y Viterbi?

Primero, un poco de antecedentes, tal vez aclare las cosas un poco.

Cuando se habla de HMM (modelos ocultos de Markov), generalmente hay 3 problemas a considerar:

1. Problema de evaluación

   • El problema de evaluación responde a la pregunta: ¿cuál es la probabilidad de que una secuencia particular de símbolos sea producida por un modelo en particular?
   • Para la evaluación usamos dos algoritmos: el algoritmo hacia adelante o el algoritmo hacia atrás (NO los confunda con el algoritmo hacia adelante-hacia atrás).

2. Problema de decodificación

   • El problema de decodificación responde a la pregunta: Dada una secuencia de símbolos (sus observaciones) y un modelo, ¿cuál es la secuencia de estados más probable que produjo la secuencia?
   • Para decodificar usamos el algoritmo de Viterbi .

3. Problema de entrenamiento

   • El problema de entrenamiento responde a la pregunta: Dada una estructura de modelo y un conjunto de secuencias, encuentre el modelo que mejor se ajuste a los datos .
   • Para este problema podemos usar los siguientes 3 algoritmos:
     1. MLE (estimación de máxima verosimilitud)
     2. Entrenamiento de Viterbi (NO confundir con decodificación de Viterbi)
     3. Baum Welch = algoritmo de avance-retroceso

Para resumir, utiliza el algoritmo de Viterbi para problema de decodificación y Baum Welch / Adelante-atrás cuando entrena su modelo en un conjunto de secuencias.

Baum Welch funciona de la siguiente manera.

Para cada secuencia en el conjunto de secuencias de entrenamiento.

1. Calcule las probabilidades hacia adelante con el algoritmo hacia adelante
2. Calcule las probabilidades hacia atrás con el algoritmo hacia atrás
3. Calcule las contribuciones de la secuencia actual a las transiciones del modelo, calcule las contribuciones de la secuencia actual a las probabilidades de emisión del modelo.
4. Calcule los parámetros del nuevo modelo (probabilidades de inicio, probabilidades de transición, probabilidades de emisión )
5. Calcule el nueva probabilidad de registro del modelo
6. Deténgase cuando el cambio en la probabilidad de registro es menor que un umbral dado o cuando se pasa un número máximo de iteraciones.

Si necesita una descripción completa de las ecuaciones para la decodificación de Viterbi y el algoritmo de entrenamiento hágamelo saber y puedo indicarle la dirección correcta.

Comentarios

• Hola . Si guardamos la ruta, durante la evaluación usando el algoritmo de reenvío, ¿hace que el uso del algoritmo de Viterbi en la decodificación sea redundante?

Encuentro que estas dos diapositivas siguientes de {2} son realmente buenas para situar el avance -Algoritmos hacia atrás y Viterbi entre todos los demás algoritmos típicos utilizados con HMM:

Notas :

• $ x $ son las emisiones observadas, $ \ pi $ son los parámetros del HMM.
• ruta = una secuencia de emisiones
• decodificación = inferencia
• aprendizaje = entrenamiento = estimación de parámetros
• Algunos artículos (p. ej., {1}) afirman que Baum – Welch es lo mismo que el algoritmo hacia adelante-hacia atrás, pero Estoy de acuerdo ee con Masterfool y Wikipedia: Baum – Welch es un algoritmo de maximización de expectativas que utiliza el algoritmo hacia adelante y hacia atrás. Las dos ilustraciones también distinguen a Baum – Welch del algoritmo de avance-retroceso.

Referencias:

• {1} Lember, Jüri y Alexey Koloydenko. «El entrenamiento Viterbi ajustado para modelos ocultos de Markov». Bernoulli 14, no. 1 (2008): 180-206.
• {2} 6.047 / 6.878 Biología Computacional: Genomas, Redes, Evolución (Otoño de 2012) Conferencia 07 – HMMs II (2012-09-29) http://stellar.mit.edu/S/course/6/fa12/6.047/courseMaterial/topics/topic2/lectureNotes/Lecture07_HMMsIIb_6up/Lecture07_HMMsIIb_6up.pdf (Manolis Kellis):

La respuesta de Morat es falsa en un punto: Baum -Welch es un algoritmo de maximización de expectativas, que se utiliza para entrenar los parámetros de un HMM. utiliza el algoritmo de avance y retroceso durante cada iteración. El algoritmo de avance y retroceso en realidad es solo una combinación de los algoritmos de avance y retroceso: un pase hacia adelante, un pase hacia atrás. Por sí solo, el algoritmo de avance-retroceso no se usa para entrenar los parámetros de un HMM, sino solo para suavizar: calcular las probabilidades marginales de una secuencia de estados.

https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm

https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

@Yaroslav Bulatov tenía una respuesta precisa. Agregaría un ejemplo para decirle a diferencias entre los algoritmos de avance-retroceso y de Viterbi.

Supongamos que tenemos este HMM (de la página de Wikipedia HMM). Tenga en cuenta que el modelo ya está proporcionado, por lo que aquí no hay aprendizaje de la tarea de datos.

Suponga que nuestros datos son una secuencia de longitud 4. (Walk, Shop, Walk, Clean). Dos algoritmos darán cosas diferentes.

• El algoritmo hacia adelante y hacia atrás dará la probabi lidad de cada estado oculto . Aquí hay un ejemplo. Tenga en cuenta que cada columna de la tabla suma $ 1 $.

• El algoritmo de Viterbi proporcionará la secuencia más probable de estados ocultos . Aquí hay un ejemplo. Tenga en cuenta que también existe una probabilidad asociada con esta secuencia de estado oculta. Esta secuencia tiene un problema máximo. sobre todas las demás secuencias (p. ej., $ 2 ^ 4 = 16 $ secuencias de todas las Sunny a todas las Rainy).

Aquí hay algunos R código para la demostración

library(HMM) # in education setting, # hidden state: Rainy and Sunny # observation: Walk, Shop, Clean # state transition P <- as.matrix(rbind(c(0.7,0.3), c(0.4,0.6))) # emission prob R <- as.matrix(rbind(c(0.1, 0.4, 0.5), c(0.6,0.3, 0.1))) hmm = initHMM(States=c("Rainy","Sunny"), Symbols=c("Walk","Shop", "Clean"), startProbs=c(0.6,0.4), transProbs=P, emissionProbs=R) hmm obs=c("Walk","Shop","Walk", "Clean") print(posterior(hmm,obs)) print(viterbi(hmm, obs))