Inside-outside algorithm

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 a variant of the Expectation-maximization algorithm, in which the basic assumption is that a "good" grammar is one that makes sentences in the training corpus likely to occur.

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]

References

* 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.
* Christopher D. Manning, Heinrich Shütze (1999): Foundations of statistical natural language processing.