Algoritmo interior-exterior

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

Para analizar algoritmos en informática , el algoritmo interno-externo 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 hacia 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 maximización de expectativas (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 inicial 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)}$

Calcular 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 a partir de 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 las 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)}$

Calcular 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 hay 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)}$

Supongamos ahora que hay 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, artículos sobre comunicación del habla 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 estocásticas libres de contexto utilizando el algoritmo interior-exterior. Habla y lenguaje informático , 4:35–56.
• Karim Lari, Steve J. Young (1991): Aplicaciones de gramáticas estocásticas libres de contexto utilizando el algoritmo Inside-Outside. Habla y lenguaje informático , 5:237–257.
• Fernando Pereira, Yves Schabes (1992): Reestimación interior-exterior a partir 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.

enlaces externos

• Algoritmo interior-exterior - Fei Xia
• El algoritmo interior-exterior - Michael Collins