Difference between revisions of "Inside Outside algorithm"
From Cohen Courses
Jump to navigationJump to searchm |
m |
||
| Line 9: | Line 9: | ||
== Algorithm == | == Algorithm == | ||
| − | === Inside | + | The algorithm is a dynamic programming algorithm that is often used with chart parsers to estimate expected production counts. |
| + | |||
| + | === Inside probabilities === | ||
| + | |||
| + | The inside probability is defined as <math>\beta(A, i, j)=P(A\rightarrow w_i...w_j|G, \mathbf{w})</math>. | ||
=== Outside counts === | === Outside counts === | ||
Revision as of 11:35, 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.
Inside probabilities
The inside probability is defined as .
