Difference between revisions of "Inside Outside algorithm"
From Cohen Courses
Jump to navigationJump to searchm |
m |
||
| Line 10: | Line 10: | ||
The algorithm is a dynamic programming algorithm that is often used with chart parsers to estimate expected production counts. | The algorithm is a dynamic programming algorithm that is often used with chart parsers to estimate expected production counts. | ||
| + | |||
| + | The algorithm works by computing | ||
| + | |||
| + | The inside probability is defined as <math>\beta(A, i, j)=P(A\Rightarrow\hat{*} w_i...w_j|G, \mathbf{w})</math>, which is the probability of a nonterminal <math>A</math> generating the word sequence <math>w_i</math> to <math>w_j</math> | ||
=== Inside probabilities === | === Inside probabilities === | ||
| − | |||
| − | |||
=== Outside counts === | === Outside counts === | ||
Revision as of 11:37, 29 November 2011
This is a Method page for the Inside-outside algorithm.
Background
The inside-outside algorithm is a way of estimating probabilities in a PCFG. It is first introduced [| Baker, 1979]. The inside outside algorithm is in fact a generalization of the forward-backward algorithm (for hidden Markov models) to PCFGs.
It is often used as part of the EM algorithm for computing expectations.
Algorithm
The algorithm is a dynamic programming algorithm that is often used with chart parsers to estimate expected production counts.
The algorithm works by computing
The inside probability is defined as , which is the probability of a nonterminal generating the word sequence to
