next up previous
Next: Reverse completion Up: Rule probability estimation Previous: Computing expected production counts

Computing outer probabilities

The outer probabilities are computed by tracing the complete paths from the final state to the start state, in a single backward pass over the Earley chart. Only completion and scanning steps need to be traced back. Reverse scanning leaves outer probabilities unchanged, so the only operation of concern is reverse completion.

We describe reverse transitions using the same notation as for their forward counterparts, annotating each state with its outer and inner probabilities.




Andreas Stolcke
Sat Jun 29 21:49:02 PDT 1996