Algoritmo de dentro a fuera

Método de estimación de parámetros para gramáticas probabilísticas independientes del contexto

En el caso de los algoritmos de análisis sintáctico en informática , el algoritmo de dentro a fuera es una forma de reestimar 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 de adelante hacia atrás para la estimación de parámetros en modelos ocultos de Markov a gramáticas estocásticas libres de contexto . Se utiliza para calcular expectativas, por ejemplo, como parte del algoritmo de expectativa-maximización (un algoritmo de aprendizaje no supervisado).

Probabilidades internas y externas

La probabilidad interna es la probabilidad total de generar palabras , dada la raíz no terminal y una gramática : ^[1] ${\displaystyle \beta _{j}(p,q)}$ ${\displaystyle w_{p}\cdots w_{q}}$ ${\displaystyle N^{j}}$ ${\displaystyle G}$

${\displaystyle \beta _{j}(p,q)=P(w_{pq}|N_{pq}^{j},G)}$

La probabilidad externa es la probabilidad total de comenzar con el símbolo de inicio y generar el no terminal y todas las palabras externas , dada una gramática : ^[1] ${\displaystyle \alpha _{j}(p,q)}$ ${\displaystyle N^{1}}$ ${\displaystyle N_{pq}^{j}}$ ${\displaystyle w_{p}\cdots w_{q}}$ ${\displaystyle G}$

${\displaystyle \alpha _{j}(p,q)=P(w_{1(p-1)},N_{pq}^{j},w_{(q+1)m}|G)}$

Calculando probabilidades internas

Caso base:

${\displaystyle \beta _{j}(p,p)=P(w_{p}|N^{j},G)}$

Caso general:

Supongamos que hay una regla en la gramática, entonces la probabilidad de generar comenzando con un subárbol con raíz en es: ${\displaystyle N_{j}\rightarrow N_{r}N_{s}}$ ${\displaystyle w_{p}\cdots w_{q}}$ ${\displaystyle N_{j}}$

${\displaystyle \sum _{k=p}^{k=q-1}P(N_{j}\rightarrow N_{r}N_{s})\beta _{r}(p,k)\beta _{s}(k+1,q)}$

La probabilidad interna es simplemente la suma de todas esas reglas posibles: ${\displaystyle \beta _{j}(p,q)}$

${\displaystyle \beta _{j}(p,q)=\sum _{N_{r},N_{s}}\sum _{k=p}^{k=q-1}P(N_{j}\rightarrow N_{r}N_{s})\beta _{r}(p,k)\beta _{s}(k+1,q)}$

Calculando probabilidades externas

Caso base:

${\displaystyle \alpha _{j}(1,n)={\begin{cases}1&{\mbox{if }}j=1\\0&{\mbox{otherwise}}\end{cases}}}$

Aquí el símbolo de inicio es . ${\displaystyle N_{1}}$

Caso general:

Supongamos que existe una regla en la gramática que genera . Entonces, la contribución izquierda de esa regla a la probabilidad externa es: ${\displaystyle N_{r}\rightarrow N_{j}N_{s}}$ ${\displaystyle N_{j}}$ ${\displaystyle \alpha _{j}(p,q)}$

${\displaystyle \sum _{k=q+1}^{k=n}P(N_{r}\rightarrow N_{j}N_{s})\alpha _{r}(p,k)\beta _{s}(q+1,k)}$

Ahora supongamos que existe una regla en la gramática. Entonces, la contribución correcta de esa regla a la probabilidad externa es: ${\displaystyle N_{r}\rightarrow N_{s}N_{j}}$ ${\displaystyle \alpha _{j}(p,q)}$

${\displaystyle \sum _{k=1}^{k=p-1}P(N_{r}\rightarrow N_{s}N_{j})\alpha _{r}(k,q)\beta _{s}(k,p-1)}$

La probabilidad externa es la suma de las contribuciones izquierda y derecha sobre todas esas reglas: ${\displaystyle \alpha _{j}(p,q)}$

${\displaystyle \alpha _{j}(p,q)=\sum _{N_{r},N_{s}}\sum _{k=q+1}^{k=n}P(N_{r}\rightarrow N_{j}N_{s})\alpha _{r}(p,k)\beta _{s}(q+1,k)+\sum _{N_{r},N_{s}}\sum _{k=1}^{k=p-1}P(N_{r}\rightarrow N_{s}N_{j})\alpha _{r}(k,q)\beta _{s}(k,p-1)}$

Referencias

1. 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 presented at the 97th meeting of the 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 estocásticas independientes del contexto utilizando el algoritmo interior-exterior. Computer Speech and Language , 4:35–56.
• Karim Lari, Steve J. Young (1991): Aplicaciones de gramáticas estocásticas independientes del contexto utilizando el algoritmo Inside–Outside. Computer Speech and Language , 5:237–257.
• Fernando Pereira, Yves Schabes (1992): Reestimación interna-externa a partir de corpus parcialmente entre corchetes. Actas de la 30.ª reunión anual de la Asociación de Lingüística Computacional, Association for Computational Linguistics , 128–135.

Enlaces externos

• Algoritmo de dentro a fuera - Fei Xia
• El algoritmo de dentro a fuera - Michael Collins