Inside–outside algorithm

From Quire, the open reference·Parameter estimation method for probabilistic context-free grammars·2 min read

Redirected from Inside-outside algorithm

For parsing algorithms in computer science, the inside–outside algorithm is a way of re-estimating production probabilities in a probabilistic context-free grammar. It was introduced by James K. Baker in 1979 as a generalization of the forward–backward algorithm for parameter estimation on hidden Markov models to stochastic context-free grammars. It is used to compute expectations, for example as part of the expectation–maximization algorithm (an unsupervised learning algorithm).

Inside and outside probabilities#edit

The inside probability ${\displaystyle \beta _{j}(p,q)}$ is the total probability of generating words ${\displaystyle w_{p}\cdots w_{q$ , given the root nonterminal ${\displaystyle N^{j$ and a grammar ${\displaystyle G}$ :^[1]

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

The outside probability ${\displaystyle \alpha _{j}(p,q)}$ is the total probability of beginning with the start symbol ${\displaystyle N^{1$ and generating the nonterminal ${\displaystyle N_{pq}^{j$ and all the words outside ${\displaystyle w_{p}\cdots w_{q$ , given a grammar ${\displaystyle G}$ :^[1]

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

Computing inside probabilities#edit

Base Case:

{{mathimg|50815e2b99d693623179f2bb4a1d6b5254db8697|width=23.324ex|height=3.343ex|va=-1.005ex|alt={\displaystyle \beta _{j}(p,p)=P(w_{p}|N^{j},G)}}}

General case:

Suppose there is a rule ${\displaystyle N_{j}\rightarrow N_{r}N_{s$ in the grammar, then the probability of generating ${\displaystyle w_{p}\cdots w_{q$ starting with a subtree rooted at ${\displaystyle N_{j$ is:

{{mathimg|3c96025defc36194aaa1e5db53665512a6a10308|width=39.992ex|height=7.676ex|va=-3.338ex|alt={\displaystyle \sum _{k=p}^{k=q-1}P(N_{j}\rightarrow N_{r}N_{s})\beta _{r}(p,k)\beta _{s}(k+1,q)}}}

The inside probability ${\displaystyle \beta _{j}(p,q)}$ is just the sum over all such possible rules:

{{mathimg|bbbbf3f985ecea0504eaff28fd6fa90c059ded2a|width=55.439ex|height=7.676ex|va=-3.338ex|alt={\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)}}}

Computing outside probabilities#edit

Base Case:

{{mathimg|effbf8129bc86183569a1c03b4e95d9f69dba68c|width=26.453ex|height=6.176ex|va=-2.505ex|alt={\displaystyle \alpha _{j}(1,n)={\begin{cases}1&{\mbox{if j=1\\0&{\mbox{otherwise\end{cases}}

Here the start symbol is ${\displaystyle N_{1$ .

General case:

Suppose there is a rule ${\displaystyle N_{r}\rightarrow N_{j}N_{s$ in the grammar that generates ${\displaystyle N_{j$ . Then the left contribution of that rule to the outside probability ${\displaystyle \alpha _{j}(p,q)}$ is:

{{mathimg|be508988cbfb17783dc55a53400d11eacab2eaa1|width=40.164ex|height=7.676ex|va=-3.338ex|alt={\displaystyle \sum _{k=q+1}^{k=n}P(N_{r}\rightarrow N_{j}N_{s})\alpha _{r}(p,k)\beta _{s}(q+1,k)}}}

Now suppose there is a rule ${\displaystyle N_{r}\rightarrow N_{s}N_{j$ in the grammar. Then the right contribution of that rule to the outside probability ${\displaystyle \alpha _{j}(p,q)}$ is:

{{mathimg|b7521bb33bbd2bab1164475b7f4066d9c5fb3c16|width=40.235ex|height=7.343ex|va=-3.005ex|alt={\displaystyle \sum _{k=1}^{k=p-1}P(N_{r}\rightarrow N_{s}N_{j})\alpha _{r}(k,q)\beta _{s}(k,p-1)}}}

The outside probability ${\displaystyle \alpha _{j}(p,q)}$ is the sum of the left and right contributions over all such rules:

{{mathimg|4d3bad2e9b9902012c9628c865da419305cdcd45|width=103.898ex|height=7.676ex|va=-3.338ex|alt={\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&}}

References#edit

^ a b Manning, Christopher D.; Hinrich Schütze (1999). Foundations of Statistical Natural Language Processing. Cambridge, MA, USA: MIT Press. pp. 388–402. ISBN 0-262-13360-1.

J. Baker (1979): Trainable grammars for speech recognition. In J. J. Wolf and D. H. Klatt, editors, Speech communication papers presented at the 97th meeting of the Acoustical Society of America, pages 547–550, Cambridge, MA, June 1979. MIT.
Karim Lari, Steve J. Young (1990): The estimation of stochastic context-free grammars using the inside–outside algorithm. Computer Speech and Language, 4:35–56.
Karim Lari, Steve J. Young (1991): Applications of stochastic context-free grammars using the Inside–Outside algorithm. Computer Speech and Language, 5:237–257.
Fernando Pereira, Yves Schabes (1992): Inside–outside reestimation from partially bracketed corpora. Proceedings of the 30th annual meeting on Association for Computational Linguistics, Association for Computational Linguistics, 128–135.

External links#edit

Categories Parsing algorithms

This article is mirrored from “Inside–outside algorithm” on English Wikipedia, revision 1143544206, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1143544206 · just now