Algoritmo interior-exterior - Inside–outside algorithm

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 interna es la probabilidad total de generar palabras , dada la raíz no terminal y una gramática : ${\ 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 : ${\ 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 comenzando con un subárbol enraizado 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 interior es solo 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)}$

Calcular probabilidades externas

Caso base:

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

Aquí está el símbolo de inicio . ${\ 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)}$

Ahora suponga 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 estas 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

• 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 interior-exterior . 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 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 de adentro hacia afuera - Fei Xia
• El algoritmo de adentro hacia afuera - Michael Collins