Viterbi parses

 

Both the definition of Viterbi parse, and its computation are straightforward generalizations of the corresponding notion for Hidden Markov Models [Rabiner and Juang1986], where one computes the Viterbi path (state sequence) through an HMM. Precisely the same approach can be used in the Earley parser, using the fact that each derivation corresponds to a path.

The standard computational technique for Viterbi parses is applicable here. Wherever the original parsing procedure sums probabilities that correspond to alternative derivations of a grammatical entity, the summation is replaced by a maximization. Thus, during the forward pass each state must keep track of the maximal path probability leading to it, as well as the predecessor states associated with that maximum probability path. Once the final state is reached, the maximum probability parse can be recovered by tracing back the path of ``best'' predecessor states.

The following modifications to the probabilistic Earley parser implement the forward phase of the Viterbi computation.

• Each state computes an additional probability, its Viterbi probability v.
• Viterbi probabilities are propagated in the same way as inner probabilities, except that during completion the summation is replaced by maximization: is the maximum of all products that contribute to the completed state . The same-position predecessor associated with the maximum is recorded as the Viterbi path predecessor of (the other predecessor state can be inferred).
• The completion step uses the original recursion without the collapsing of unit production loops. Loops are simply avoided, since they can only lower a path's probability. The collapsing of unit-production completions has to be avoided to maintain a continuous chain of predecessors for later backtracing and parse construction.
• The prediction step does not need to be modified for the Viterbi computation.

Once the final state is reached, a recursive procedure can recover the parse tree associated with the Viterbi parse. This procedure takes an Earley state as input and produces the Viterbi parse for the substring between k and i as output. (If the input state is not complete ( ), the result will be a partial parse tree with children missing from the root node.)

Viterbi-parse( ):

1. If , return a parse tree with root labeled X and no children.
2. Otherwise, if ends in a terminal a, let , and call this procedure recursively to obtain the parse tree

   

   Adjoin a leaf node labeled a as the right-most child to the root of T and return T.

3. Otherwise, if ends in a nonterminal Y, let . Find the Viterbi predecessor state for the current state. Call this procedure recursively to compute

   

   as well as

   

   Adjoin T' to T as the right-most child at the root, and return T.