Algoritmo de Viterbi

Algoritmo de Viterbi

El algoritmo de Viterbi es una programación dinámica algoritmo para encontrar la más probable secuencia de estados ocultos - llamada la trayectoria Viterbi - que resulta en una secuencia de eventos observados, especialmente en el contexto de fuentes de información de Markov y modelos ocultos de Markov .

Los términos "camino de Viterbi" y "algoritmo de Viterbi" se aplican también a relacionados con algoritmos de programación dinámica que descubrir la explicación más probable para una observación. Por ejemplo, en el análisis estadístico de un algoritmo de programación dinámica se puede utilizar para descubrir la cantidad más probable derivación independiente del contexto (análisis) de una cadena, que a veces se llama la "Viterbi analizar".

El algoritmo de Viterbi fue propuesto por Andrew Viterbi en 1967 como un algoritmo de decodificación de códigos convolucionales más ruidosos enlaces de comunicaciones digitales. [ 1 ] El algoritmo ha encontrado aplicación universal en la descodificación de los códigos convolucionales utilizados tanto en CDMA y GSM celular digital, dial-up módems , satélite, comunicaciones de espacio profundo, y 802,1 LAN inalámbrica. En la actualidad también se utiliza comúnmente en el reconocimiento de voz , identificación de palabras clave , la lingüística computacional y bioinformática . Por ejemplo, en voz a texto (reconocimiento de voz), la señal acústica se considera la secuencia observada de los acontecimientos, y una cadena de texto es considerado como la "causa oculta" de la señal acústica. El algoritmo de Viterbi encuentra la cadena de texto más probable dada la señal acústica.

Contenido

[ ocultar ]

• 1 Algoritmo

• 2 Pseudocódigo

• 3 Ejemplo

• 4 extensiones

• 5 Véase también

• 6 Notas

• 7 Referencias

• 8 Implementaciones

• 9 Enlaces externos

Algoritmo

Supongamos que se nos da un modelo oculto de Markov (HMM) con espacio de estados , las probabilidades iniciales de estar en estado de transición y las probabilidades de transición de un estado a otro . Digamos que observar salidas . La secuencia de estados más probable es que produce las observaciones está dado por las relaciones de recurrencia: [ 2 ]

Aquí es la probabilidad de la secuencia de estados más probable responsable de las primeras observaciones que tiene como su estado final. El camino Viterbi puede ser recuperada de nuevo por el ahorro de punteros que recordar qué estado se utilizó en la segunda ecuación. Que sea la función que devuelve el valor de utilizar para calcular si o si . Entonces:

Aquí estamos utilizando la definición estándar de arg max .

La complejidad de este algoritmo es .

Pseudocódigo

Aquí es necesario establecer alguna para el problema. Teniendo en cuenta la observación espacial , el espacio de estados , una secuencia de observaciones , la matriz de transición de un tamaño tal que las tiendas de la probabilidad de transición de transitar de un estado a otro , la matriz de emisiones de tamaño tal que almacena la probabilidad de observar de un estado , un conjunto de probabilidades iniciales de tamaño tal que la probabilidad de que almacena . Se dice que una ruta de acceso es una secuencia de estados que generan las observaciones .

En este problema de programación dinámica, la construcción de dos 2-dimensionales tablas de tamaño . Cada elemento de , , almacena la probabilidad de que el camino más probable hasta ahora con que genera . Cada elemento de , , tiendas de la trayectoria más probable hasta el momento para

Llenamos las entradas de dos mesas por orden creciente de .

, Y

ENTRADA: El espacio de observación ,

el espacio de estado ,

una secuencia de observaciones de tal manera que si el

observación en tiempo es ,

matriz de transición de tamaño tal que almacena la transición

probabilidad de transitar de un estado a otro ,

emisión de matriz de tamaño tales que la probabilidad de tiendas

observación de un estado ,

una matriz de probabilidades iniciales de tamaño tal que almacena la probabilidad

que

SALIDA: La secuencia oculta el estado más probable

A01 función VITERBI ( O , S , π , Y , A , B ): X

A02 para cada estado s i hacer

A03 T 1 [i, 1] ← pi i B i

A04 T 2 [i, 1] ← 0

A05 final de

A06 para i ← 2 , 3 , ..., T hacer

A07 para cada estado s j do

A08 T 1 [j, i] ←

A09 T 2 [j, i] ←

A10 final para

A11 final para

A12 z T ←

A13 x T ← s z T

A14 para i ← T , T-1 , ..., 2 do

A15 z i-1 ← T 2 [z i , i]

A16 x i-1 ← s z i-1

A17 final para

A18 retorno X

A19 fin de la función

Ejemplo

Considere la posibilidad

...