Procesamiento del Lenguaje Natural para Recuperación de Información

El algoritmo de Viterbi

El algoritmo de Viterbi fue inicialmente desarrollado para encontrar, dada una secuencia de símbolos, la serie de transiciones más probable entre los estados de una cadena de Markov necesaria para producir dicha secuencia. Este problema es el equivalente markoviano al análisis sintáctico en una gramática regular estocástica y nos sirve como herramienta de desambigüación.

    El algoritmo de Viterbi es un caso particular del algoritmo de Programación Dinámica utilizado para encontrar un camino extremal en un grafo multietapa. Al igual que en el caso del análisis sintáctico para gramáticas regulares no deterministas, se recurre a un trellis, pero en este caso se define la función peso, no el dominio de los booleanos, sino en el intervalo [0..1], puesto que ahora representa la probabilidad de una regla o transición:

y se sustituyen respectivamente las funciones "extremiza" por "max" y [circlemultiply] por el producto:

Al final del proceso C(n,|Q|) nos proporciona la probabilidad (de máxima verosimilitud) de que la cadena analizada pertenezca al lenguaje de la gramática.

Referencias:

Conferencia ISWC2003
Semantica web

Descargas:

Fecha ultima actualizacion: 05 de Abril de 2.007