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 de una clínica en un pueblo primitivo. La gente del pueblo tiene una propiedad muy agradable que son saludables o tiene fiebre. Ellos sólo pueden decir si tienen fiebre pidiendo un médico en la clínica. El médico sabio hace un diagnóstico de la fiebre por pedir a los pacientes cómo se sienten. Los aldeanos sólo responden que parece normal, mareos, o frío.

Supongamos que un paciente acude a la clínica cada día y le dice al médico cómo se siente. El médico cree que el estado de salud de este paciente funciona como una discreta cadena de Marko . Hay dos estados, "sano" y "Fever", pero el médico no puede observar directamente, es decir, que se oculta de él. En cada día, hay una cierta posibilidad de que el paciente informe al médico que tiene uno de los siguientes sentimientos, dependiendo de su estado de salud: "normal", "frío", o "mareado". Esas son las observaciones .Todo el sistema es la de un modelo oculto de Markov (HMM).

El médico sabe condición de los aldeanos de salud general, y lo que los pacientes se quejan de síntomas con o sin fiebre, en promedio. En otras palabras, los parámetros del HMM son conocidos. Se pueden representar de la siguiente manera en el lenguaje de programación Python :

estados = ( 'Saludable' , 'Fever' )

observaciones = ( 'normal' , 'frío' ,

...