LINGUIST List 14.659

Fri Mar 7 2003

Disc: New: Proof of Correctness in Best-First Parsing

Editor for this issue: Karen Milligan <karenlinguistlist.org>

Directory

1. Liang Huang, Proof of Correctness in Best-First Parsing

In Best-First (or Uniform-cost) search, we should ensure that items
are popped (from the priority-queue) in a non-increasing order of
merit (probability as for parsing).

But for probabilistic Earley parsing (Stolcke, 1995), actually this
monotonical order is broken by the ''prediction step'': (i, j, A ->
alpha .B beta, p) --> (j, j, B -> .gamma, prob(B->.gamma)

here the probability of the rule B->.gamma may be higher than
p. That's just like using Dijkstra to a graph containing negative
edges (but of course no negative cycles).

Do you know anybody having proved the correctness of this algorithm?
Or do you have any other derivation that ensures monotonicity?

One possible solution is to change the ''predication step'' into:

 (i, j, A -> alpha .B beta, p) --> (j, j, B -> .gamma, p *
prob(B->.gamma). In this way, no negative edges. But it is not
elegant at all. One should remember the p for each predicted state.

I'd appreciate it very much if you could discuss this issue with me.

Thanks,
Liang Huang (Bill)
Shanghai Jiao Tong University