Decodificación de Viterbi

Posición en la rutaMódulo 2 de 3 · Tema 2 de 4

2.2 Decodificación de Viterbi

—Puntuación del lab— / 100XP total—Racha—

La historia única más probable

El algoritmo forward suma todos los caminos ocultos para decir cuán probables son los datos. A menudo queremos otra cosa: la mejor historia única, la secuencia de estados que explica los datos con la mayor probabilidad. La decodificación de Viterbi la halla. La idea es el algoritmo forward con un cambio: en vez de sumar sobre los estados previos, tomar el mejor. Se guarda una puntuación $\delta_t(j)$ , la probabilidad del mejor camino que termina en el estado $j$ el día $t$ , y se recuerda qué estado previo la dio, el puntero hacia atrás.

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

Tras el último día, elija el estado con mayor $\delta_T$ y recorra hacia atrás los punteros $\psi$ para leer todo el camino. Dos puntos prácticos. Primero, trabaje con logs: los productos de muchas probabilidades se acercan a cero, pero los logs los convierten en sumas y, como el log es creciente, el mejor camino es el mismo. Segundo, el mejor camino no es lo mismo que elegir el estado más probable cada día por separado. El camino puede venir forzado por lo que viene después, como muestra el ejemplo.

Pequeño, Grande, Grande otra vezDía 1:

\delta_1=(0{,}54,\ 0{,}12)

. Día 2 (grande): Tranquilo viene mejor de Tranquilo,

0{,}54\cdot0{,}9\cdot0{,}1=0{,}0486

. Tormentoso viene mejor de Tormentoso,

0{,}12\cdot0{,}8\cdot0{,}7=0{,}0672

, no de Tranquilo (

0{,}54\cdot0{,}1\cdot0{,}7=0{,}0378

). Día 3: Tormentoso viene de Tormentoso,

0{,}0672\cdot0{,}8\cdot0{,}7=0{,}0376

, y Tranquilo solo

0{,}0044

. El mejor camino es Tormentoso, Tormentoso, Tormentoso con probabilidad

0{,}0376

. Sin embargo, el primer día solo parecía tranquilo con probabilidad

0{,}82

. Los movimientos grandes posteriores arrastran toda la historia hacia Tormentoso. Este camino es

1{,}78

veces más probable que Tranquilo, Tormentoso, Tormentoso (

0{,}0212

Viterbi reemplaza la suma del algoritmo forward por un máximo y guarda punteros hacia atrás.
El mejor camino puede diferir del estado más probable de cada día tomado por separado.
Use logs: las sumas de logs evitan el desbordamiento por defecto y conservan el mismo mejor camino.

Lab: qué se califica

Una puntuación de Viterbi el día dos15 pts
La probabilidad del mejor camino15 pts
El log del mejor camino10 pts
Frente a otro camino10 pts
El primer estado del mejor camino15 pts
Los pasos de Viterbi10 pts
Emparejar el vocabulario10 pts
Por qué usar logs15 pts

0/ 8 respondidos

1Respuesta numérica15 ptsSin responder

Con $\delta_1=(0{,}54,\ 0{,}12)$ y un movimiento grande el día 2, ¿cuánto vale $\delta_2(S)=\max(0{,}54\cdot0{,}1,\ 0{,}12\cdot0{,}8)\cdot0{,}7$ ? Dé cuatro decimales.

d =

aceptado: ± 0.0003

2Respuesta numérica15 ptsSin responder

Con $\delta_2=(0{,}0486,\ 0{,}0672)$ y un movimiento grande el día 3, ¿cuánto vale $\delta_3(S)=\max(0{,}0486\cdot0{,}1,\ 0{,}0672\cdot0{,}8)\cdot0{,}7$ , la probabilidad del mejor camino? Dé cuatro decimales.

d =

aceptado: ± 0.0003

3Respuesta numérica10 ptsSin responder

¿Cuál es el logaritmo natural de la probabilidad $0{,}0376$ del mejor camino? Dé dos decimales.

l =

aceptado: ± 0.02

4Respuesta numérica10 ptsSin responder

¿Cuántas veces es más probable el mejor camino (probabilidad $0{,}0376$ ) que el camino Tranquilo, Tormentoso, Tormentoso (probabilidad $0{,}0212$ )? Dé dos decimales.

r =

aceptado: ± 0.02

5Elección15 ptsSin responder

El primer día muestra un movimiento pequeño, lo que hace Tranquilo probable al 82 % por sí solo. ¿Cuál es el primer estado del mejor camino para Pequeño, Grande, Grande?

6Ordenar los pasos10 ptsSin responder

Ponga en orden los pasos de la decodificación de Viterbi.

Arrastra para reordenar, o enfoca un elemento, pulsa Espacio para levantarlo, las flechas para moverlo y Espacio para soltarlo.

1Tras el último día, elegir el estado de mayor puntuación
2Empezar con delta igual a la probabilidad inicial por la primera emisión
3Recorrer los punteros hacia atrás para leer el camino
4Para cada día y estado, conservar el mejor predecesor y recordarlo

7Emparejar10 ptsSin responder

Empareje cada término con su significado.

Elige la pareja de cada elemento de la izquierda.

\delta_t(j)

\psi_t(j)

Algoritmo forward

Algoritmo de Viterbi

8Explicar con palabras15 ptsSin responder

En una o dos frases, explique por qué la decodificación de Viterbi suele escribirse con logs de las probabilidades y por qué eso no cambia el mejor camino.

Se califica por:Los productos de muchas probabilidades se acercan a ceroLos logs convierten productos en sumas y el log es creciente, así que el mejor camino es el mismo0 / 400 caracteres

Modo matemáticasEntrada por teclado o LaTeXEjercicio 1 de 8 · Ctrl ⏎ para comprobar

Decodificación de Viterbi

Posición en la rutaMódulo 2 de 3 · Tema 2 de 4

2.2 Decodificación de Viterbi

—Puntuación del lab— / 100XP total—Racha—

La historia única más probable

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

Pequeño, Grande, Grande otra vezDía 1:

\delta_1=(0{,}54,\ 0{,}12)

. Día 2 (grande): Tranquilo viene mejor de Tranquilo,

0{,}54\cdot0{,}9\cdot0{,}1=0{,}0486

. Tormentoso viene mejor de Tormentoso,

0{,}12\cdot0{,}8\cdot0{,}7=0{,}0672

, no de Tranquilo (

0{,}54\cdot0{,}1\cdot0{,}7=0{,}0378

). Día 3: Tormentoso viene de Tormentoso,

0{,}0672\cdot0{,}8\cdot0{,}7=0{,}0376

, y Tranquilo solo

0{,}0044

. El mejor camino es Tormentoso, Tormentoso, Tormentoso con probabilidad

0{,}0376

. Sin embargo, el primer día solo parecía tranquilo con probabilidad

0{,}82

. Los movimientos grandes posteriores arrastran toda la historia hacia Tormentoso. Este camino es

1{,}78

veces más probable que Tranquilo, Tormentoso, Tormentoso (

0{,}0212

Viterbi reemplaza la suma del algoritmo forward por un máximo y guarda punteros hacia atrás.
El mejor camino puede diferir del estado más probable de cada día tomado por separado.
Use logs: las sumas de logs evitan el desbordamiento por defecto y conservan el mismo mejor camino.

Lab: qué se califica

Una puntuación de Viterbi el día dos15 pts
La probabilidad del mejor camino15 pts
El log del mejor camino10 pts
Frente a otro camino10 pts
El primer estado del mejor camino15 pts
Los pasos de Viterbi10 pts
Emparejar el vocabulario10 pts
Por qué usar logs15 pts

0/ 8 respondidos

1Respuesta numérica15 ptsSin responder

Con $\delta_1=(0{,}54,\ 0{,}12)$ y un movimiento grande el día 2, ¿cuánto vale $\delta_2(S)=\max(0{,}54\cdot0{,}1,\ 0{,}12\cdot0{,}8)\cdot0{,}7$ ? Dé cuatro decimales.

d =

aceptado: ± 0.0003

2Respuesta numérica15 ptsSin responder

d =

aceptado: ± 0.0003

3Respuesta numérica10 ptsSin responder

¿Cuál es el logaritmo natural de la probabilidad $0{,}0376$ del mejor camino? Dé dos decimales.

l =

aceptado: ± 0.02

4Respuesta numérica10 ptsSin responder

¿Cuántas veces es más probable el mejor camino (probabilidad $0{,}0376$ ) que el camino Tranquilo, Tormentoso, Tormentoso (probabilidad $0{,}0212$ )? Dé dos decimales.

r =

aceptado: ± 0.02

5Elección15 ptsSin responder

El primer día muestra un movimiento pequeño, lo que hace Tranquilo probable al 82 % por sí solo. ¿Cuál es el primer estado del mejor camino para Pequeño, Grande, Grande?

6Ordenar los pasos10 ptsSin responder

Ponga en orden los pasos de la decodificación de Viterbi.

Arrastra para reordenar, o enfoca un elemento, pulsa Espacio para levantarlo, las flechas para moverlo y Espacio para soltarlo.

1Tras el último día, elegir el estado de mayor puntuación
2Empezar con delta igual a la probabilidad inicial por la primera emisión
3Recorrer los punteros hacia atrás para leer el camino
4Para cada día y estado, conservar el mejor predecesor y recordarlo

7Emparejar10 ptsSin responder

Empareje cada término con su significado.

Elige la pareja de cada elemento de la izquierda.

\delta_t(j)

\psi_t(j)

Algoritmo forward

Algoritmo de Viterbi

8Explicar con palabras15 ptsSin responder

En una o dos frases, explique por qué la decodificación de Viterbi suele escribirse con logs de las probabilidades y por qué eso no cambia el mejor camino.

Se califica por:Los productos de muchas probabilidades se acercan a ceroLos logs convierten productos en sumas y el log es creciente, así que el mejor camino es el mismo0 / 400 caracteres

Modo matemáticasEntrada por teclado o LaTeXEjercicio 1 de 8 · Ctrl ⏎ para comprobar

Decodificación de Viterbi

La historia única más probable

Lab: qué se califica

Inicia sesión para ejecutar tu código.

Decodificación de Viterbi

La historia única más probable

Lab: qué se califica

Inicia sesión para ejecutar tu código.