[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Algoritmo de Viterbi : que es, definición y significado, descargar videos y fotos.

  ıllı Algoritmo de Viterbi : que es, definición y significado, descargar videos y fotos.  

El algoritmo de Viterbi deja hallar las secuencias de estados más probable en un Modelo escondo de Márkov (MOM), S=(q1,q2,…,qT)undefined, desde una observación O=(o1,o2,…,oT)undefined, esto es, consigue la secuencia inmejorable que mejor explica la secuencia de observaciones.

Consideremos la variable dt(i)undefined que se define como:

dt(i)=maxq1,q2,…,qt-1P(q1,q2,…,qt=i,o1,o2,…,ot|µ)undefined

dt(i)undefined es la probabilidad del mejor camino hasta el estado iundefined habiendo visto las tundefined primeras observaciones. Esta función se calcula para todos y cada uno de los estados y también momentos de tiempo.

dt+1(j)=bj(ot+1)undefined

Puesto que la meta es conseguir las secuencia de estados más probable, va a ser preciso guardar el razonamiento que hace máxima la ecuación precedente en todos y cada momento de tiempo tundefined y para cada estado jundefined y para esto empleamos la variable ft(j)undefined.

A continuación se especifica el proceso completo usando las funciones dundefined y fundefined.

Inicialización

d1(i)=pibi(o1)undefined

donde 1=i=Nundefined

dt+1(j)=bj(ot+1)undefined,

donde:

t=1,2,…,T-1undefined, 1=j=Nundefined

ft+1(j)=arg?max1=i=Ndt(i)aijundefined,

donde:

t=1,2,…,T-1undefined, 1=j=Nundefined

qT*=arg?max1=i=NdT(i)undefined

Reconstrucción de la secuencia de estados más probable

qt*=ft+1(qt+1*)undefined,

donde:

t=T-1,T-2,…,1undefined

Algunos de los cálculos del algoritmo de Viterbi recuerdan a los del algoritmo forward preciso para calcular eficazmente la probabilidad de una secuencia de observables. Una de las diferencias es la integración de la función arg?maxundefined (en vez de sumar las probabilidades) para calcular la secuencia de estados más probable.

Ejemplo de secuencia de estados más probable

La figura muestra un caso de secuencia de estados más probable en un Modelo Escondo de Márkov de cinco estados dada una secuencia de observaciones de longitud cinco.

Muy utilizado para reconocimiento de voz, biología molecular, fonemas, palabras, codificadores entre otros muchos. A cada secuencia de estados le toca una secuencia de etiquetas (o bien labels) de clasificación, esto es, palabras, caracteres, fonemas, sufijos. Dada una secuencia observada, se deduce la más probable secuencia de estados.

Desambiguación léxica categorial

Una de las aplicaciones del algoritmo de Viterbi es en el área de procesamiento del lenguaje natural, más en concreto en el proceso de desambiguación léxica categorial.

En este caso en particular, los elementos de un Modelo Escondo de Márkov serían los siguientes:

• El conjunto Qundefined de estados sería el conjunto de posibles etiquetas (categorías gramaticales) para las palabras.
  
• El conjunto Vundefined de observables en todos y cada uno de ellos de los estados corresponde con el conjunto de palabras diferentes.
  
• El conjunto Aundefined de probabilidades de transiciones entre estados sería la probabilidad de que una determinada categoría categorial prosiga a otra. Por servirnos de un ejemplo, la probabilidad de que la categoría nombre vaya tras la categoría determinante.
  
• El conjunto Bundefined de probabilidades de las observaciones correspondería con la probabilidad de pertenencia de una palabra (un perceptible) a una determinada categoría. Por servirnos de un ejemplo, la probabilidad de que la palabra casa sea verbo, que va a ser menor que la probabilidad de que esta palabra tenga la categoría gramatical nombre.

La figura siguiente muestra un caso de etiquetado gramatical para la oración "Coto privado de caza"

En él, los observables son la secuencia de palabras de la oración. Se puede observar para cada palabra se contempla solo un conjunto limitado de posibles categorías gramaticales (caza puede ser o bien nombre o bien verbo). Este es dado a que la probabilidad de pertenencia de ciertas palabras a una categoría gramatical es nula (como la probabilidad de que la palabra caza sea adverbio). Esto facilita enormemente los cálculos en el modelo.

  ELIGE TU TEMA DE INTERÉS: 

---

Internet y Tecnologias

• Anterior
• Siguiente