¿Cuál es la diferencia entre los algoritmos de avance-retroceso y Viterbi?

Quiero saber cuáles son las diferencias entre el algoritmo de avance y retroceso y el algoritmo de Viterbi para inferencia en modelos ocultos de Markov (HMM).

Un poco de historia primero tal vez aclara un poco las cosas.

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 un modelo particular produzca una secuencia particular de símbolos?
   • Para la evaluación utilizamos dos algoritmos: el algoritmo de avance o el algoritmo de retroceso (NO los confunda con el algoritmo de avance y retroceso).

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 capacitación responde a la pregunta: dada la estructura del modelo y un conjunto de secuencias, encuentre el modelo que mejor se adapte 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 confunda con la decodificación de Viterbi)
     3. Baum Welch = algoritmo de avance-retroceso

Para resumir, utiliza el algoritmo de Viterbi para el problema de decodificación y Baum Welch / Forward-backward 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 de avance con el algoritmo de avance
2. Calcular 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 nuevos parámetros del modelo (probabilidades de inicio, probabilidades de transición, probabilidades de emisión)
5. Calcule la nueva probabilidad de registro del modelo
6. Deténgase cuando el cambio en la probabilidad de registro sea menor que un umbral determinado o cuando se pase 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 orientarlo en la dirección correcta.

Adelante-Atrás da probabilidad marginal para cada estado individual , Viterbi da probabilidad de la secuencia más probable de estados . Por ejemplo, si su tarea de HMM es predecir el clima soleado y lluvioso para cada día, adelante hacia atrás le diría la probabilidad de que esté "soleado" para cada día, Viterbi le daría la secuencia más probable de días soleados / lluviosos, y el probabilidad de esta secuencia.

Encuentro que estas dos diapositivas siguientes de {2} son realmente buenas para ubicar los algoritmos de Viterbi hacia adelante y hacia atrás entre todos los otros algoritmos típicos utilizados con HMM:

Notas:

• $x$ es la emisión observada, son los parámetros del HMM.$\pi$
• ruta = una secuencia de emisiones
• decodificación = inferencia
• aprendizaje = entrenamiento = estimación de parámetros
• Algunos documentos (p. Ej., {1}) afirman que Baum-Welch es lo mismo que el algoritmo de avance-retroceso, pero estoy de acuerdo con Masterfool y Wikipedia: Baum-Welch es un algoritmo de maximización de expectativas que utiliza el algoritmo de avance-retroceso. Las dos ilustraciones también distinguen a Baum-Welch del algoritmo de avance-retroceso.

Referencias

• {1} Lember, Jüri y Alexey Koloydenko. "El entrenamiento ajustado de Viterbi 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, utilizado para entrenar los parámetros de un HMM. Se utiliza el algoritmo de avance-retroceso durante cada iteración. El algoritmo hacia adelante y hacia atrás realmente es solo una combinación de los algoritmos hacia adelante y hacia atrás: un pase hacia adelante, un paso hacia atrás. Por sí solo, el algoritmo hacia adelante y hacia atrás 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 tuvo una respuesta precisa. Añadiría un ejemplo para contar las diferencias entre los algoritmos de avance-retroceso y Viterbi.

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

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

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

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

Aquí hay un Rcó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))