En informática , el algoritmo interior-exterior es una forma de volver a estimar las probabilidades de producción en una gramática probabilística libre de contexto . Fue introducido por James K. Baker en 1979 como una generalización del algoritmo hacia adelante-hacia atrás para la estimación de parámetros en modelos de Markov ocultos a gramáticas estocásticas libres de contexto . Se utiliza para calcular expectativas, por ejemplo, como parte del algoritmo de maximización de expectativas (un algoritmo de aprendizaje no supervisado).
Probabilidades internas y externas
La probabilidad interior es la probabilidad total de generar palabras , dada la raíz no terminal y una gramática : [1]
La probabilidad exterior es la probabilidad total de comenzar con el símbolo de inicio y generando lo no terminal y todas las palabras afuera , dada una gramática : [1]
Calcular probabilidades internas
Caso base:
Caso general:
Supongamos que hay una regla en la gramática, entonces la probabilidad de generar comenzando con un subárbol enraizado en es:
La probabilidad interior es solo la suma de todas esas reglas posibles:
Calcular probabilidades externas
Caso base:
Aquí el símbolo de inicio es .
Caso general:
Supongamos que hay una regla en la gramática que genera . Entonces la contribución izquierda de esa regla a la probabilidad exterior es:
Ahora suponga que hay una regla en la gramática. Entonces, la contribución correcta de esa regla a la probabilidad externa es:
La probabilidad exterior es la suma de las contribuciones izquierda y derecha sobre todas estas reglas:
Referencias
- ↑ a b Manning, Christopher D .; Hinrich Schütze (1999). Fundamentos del procesamiento estadístico del lenguaje natural . Cambridge, MA, EE.UU .: MIT Press. págs. 388 –402. ISBN 0-262-13360-1.
- J. Baker (1979): Gramáticas entrenables para el reconocimiento de voz . En JJ Wolf y DH Klatt, editores, Speech communication papers presentados en la 97ª reunión de la Acoustical Society of America , páginas 547–550, Cambridge, MA, junio de 1979. MIT.
- Karim Lari , Steve J. Young (1990): La estimación de gramáticas libres de contexto estocásticas utilizando el algoritmo de adentro hacia afuera . Habla y lenguaje informático , 4: 35–56.
- Karim Lari , Steve J. Young (1991): Aplicaciones de gramáticas libres de contexto estocásticas utilizando el algoritmo Inside-Outside . Habla y lenguaje por computadora , 5: 237–257.
- Fernando Pereira, Yves Schabes (1992): Reestimación interior-exterior de corpus parcialmente entre corchetes . Actas de la 30ª reunión anual de la Asociación de Lingüística Computacional, Asociación de Lingüística Computacional , 128-135.