algoritmo de adentro hacia afuera

En informática , el algoritmo de análisis sintáctico interno-externo permite 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 avance-retroceso 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 maximización de expectativas (un algoritmo de aprendizaje no supervisado).

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

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

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

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

Caso base:

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

Caso general:

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

${\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${\displaystyle \beta _{j}(p,q)}$es simplemente la suma de todas esas reglas posibles:

${\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)}$

Caso base:

${\displaystyle \alpha _{j}(1,n)={\begin{cases}1&{\mbox{si }}j=1\\0&{\mbox{en otro caso}}\end{cases}}}$

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

Caso general:

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

${\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.${\displaystyle N_{r}\rightarrow N_{s}N_{j}}$en la gramática. Entonces la contribución correcta de esa regla a la probabilidad externa${\displaystyle \alpha _{j}(p,q)}$es:

${\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${\displaystyle \alpha _{j}(p,q)}$es la suma de las contribuciones izquierda y derecha sobre todas esas reglas:

${\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)}$

• J. Baker (1979): Gramáticas entrenables para el reconocimiento del habla . En JJ Wolf y DH Klatt, editores, Documentos sobre comunicación del habla presentados en la 97.ª reunión de la Sociedad Acústica de América , páginas 547–550, Cambridge, MA, junio de 1979. MIT.
• Karim Lari , Steve J. Young (1990): La estimación de gramáticas estocásticas libres de 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 libres de 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 paréntesis . Actas de la 30.ª reunión anual de la Asociación de Lingüística Computacional, Asociación de Lingüística Computacional , 128-135.

• Algoritmo de adentro hacia afuera - Fei Xia
• El algoritmo de adentro hacia afuera - Michael Collins