View source for Complexity of constraint satisfaction

{{context|date=June 2012}}
In [[computer science]], the '''inside–outside algorithm''' is a way of re-estimating production probabilities in a [[probabilistic context-free grammar]]. It was introduced [[James K. Baker]] in 1979 as a generalization of the [[forward–backward algorithm]] for parameter estimation on [[hidden Markov model]]s to [[stochastic context-free grammar]]s. It is used to compute expectations, for example as part of the [[expectation–maximization algorithm]] (an unsupervised learning algorithm).

==Inside and outside probabilities==
The inside probability <math>\beta_j(p,q)</math> is the total probability of generating words <math>w_p \cdots w_q</math>, given the root nonterminal <math>N^j</math> and a grammar <math>G</math>:<ref name="manning-schuetze1999">{{cite book |first=Christopher D. | last=Manning | coauthor=Hinrich Schütze |title=Foundations of Statistical Natural Language Processing |publisher=MIT Press | location=Cambridge, MA, USA | year=1999 |isbn=0-262-13360-1 | pages=388–402}}</ref>
:<math>\beta_j(p,q) = P(w_{pq}|N^j_{pq}, G)</math>

The outside probability <math>\alpha_j(p,q)</math> is the total probability of beginning with the start symbol <math>N^1</math> and generating the nonterminal <math>N^j_{pq}</math> and all the words outside <math>w_p \cdots w_q</math>, given a grammar <math>G</math>:<ref name="manning-schuetze1999"/>
:<math>\alpha_j(p,q) = P(w_{1(p-1)}, N^j_{pq}, w_{(q+1)m}|G)</math>

==References==
{{Reflist}}
* 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==
* [http://www.cog.brown.edu/~mj/Software.htm An implementation of the algorithm by Mark Johnson]
* [http://faculty.washington.edu/fxia/courses/LING572/inside-outside.ppt Inside-outside algorithm - Fei Xia]
* [http://www.cs.columbia.edu/~mcollins/io.pdf The Inside-Outside Algorithm - Michael Collins]

{{DEFAULTSORT:Inside-outside algorithm}}
[[Category:Parsing algorithms]]


{{algorithm-stub}}