next up previous
Next: Reverse completion (transitive) Up: Computing outer probabilities Previous: Computing outer probabilities

Reverse completion

displaymath8799

for all pairs of states tex2html_wrap_inline8657 and tex2html_wrap_inline8157 in the chart. Then

eqnarray6393

The inner probability tex2html_wrap_inline7697 is not used.

Rationale. Relative to tex2html_wrap_inline8755 , tex2html_wrap_inline8809 is missing the probability of expanding Y, which is filled in from tex2html_wrap_inline8187 . The probability of the surrounding of Y ( tex2html_wrap_inline8817 ) is the probability of the surrounding of X ( tex2html_wrap_inline8755 ), plus the choice of the rule of production for X and the expansion of the partial LHS tex2html_wrap_inline7757 , which are together given by tex2html_wrap_inline8161 .

Note that the computation makes use of the inner probabilities computed in the forward pass. The particular way in which tex2html_wrap_inline7697 and tex2html_wrap_inline8755 were defined turns out to be convenient here, as no reference to the production probabilities themselves needs to be made in the computation.

As in the forward pass, simple reverse completion would not terminate in the presence of cyclic unit productions. A version that collapses all such chains of productions is given below.



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