Debugging a Parser (Part 1)

I've been trying to implement a synchronous parser for a long time. I thought that I had it working during the spring, but three months later I can't reproduce the results. The simplest thing to see if the synchronous parser in Joshua is working seems to be this:

1. With a given SCFG, translate a set of sentences.
2. Try to parse the resulting source--target sentence pairs.

Presumably, since the target sentences were generated by the SCFG, the parser should be able to recognize all the sentences pairs that are produced.
However, when I came back to the parser this week, I was not able to complete the two-step process. Here's a tail of the log file that Joshua produced during the parsing run:

FEATURE: OOV penalty (weight -100.000)

NgramStateComputer: stateID=0; ngramOrder=5

Grammar sorting took: 3 seconds.

Model loading took 83 seconds

Memory used 14559.2 MB

oracle file is null

Parsing sentence pair #0 [thread 9]

فرانس کی تجویز کی حمایت ||| france supported the proposal

FOREIGN: ``فرانس کی تجویز کی حمایت''

ENGLISH: ``france supported the proposal''

And it doesn't go any further than that. I started the run around midnight, and 9 hours later, even the first sentence -- a very short one -- hasn't yet been processed.

One possibility is that the parser needs more memory that I've given it, and that the process is painfully thrashing in its tiny JVM. Looking at the flags to qsub, and to the JVM, we see that the process was given 80 GB. That ought to be enough to handle this short sentence, at least. There is no way that the parse chart can be that big.

Or can it? Of course, in order to know for sure whether a sentence pair can be recognized by an SCFG, we need to turn off all pruning during the chart expansion step. This slows thing down significantly, and makes the chart pretty big. But an 80-gig chart for a six-word input sentence? How could there be so many chart items?

And that's when I realized it: looking at my translation grammar, I found this curious abstract rule:

[X] ||| [X,1] ||| [X,1] ||| -0.00000 -0.00000

Here's the problem! We can apply this rule over and over again, adding more and more items to the chart, without ever making any progress in filling the chart. After a quick grep -v to remove the rule -- well, that didn't fix the problem. I added one more logging statement to confirm that, yes, it's during chart expansion that the parser hangs.

Now, in the parser, we're using the two-pass algorithm of Dyer (2010). There are three steps:

1. Parse the source-language sentence exhaustively, using the source side of the SCFG. This results in a hypergraph representing all parses of the source sentence.
2. Intersect this hypergraph (or rather, the context-free language it represents) with a regular language that only contains the target sentence.
3. Use the resulting CFG to parse the target sentence.

In this case, we're not even making it past step 1. But the thing to note is that step 1 is exactly the same as the chart expansion that happens when using Joshua to do machine translation. The only difference is the use of exhaustive pruning (that is, no pruning) as opposed to the standard cube pruning.

Using exhaustive pruning is slow, but not that slow. So I think there are two possibilities:

1. There's a bug somewhere in the pruning code that only shows up when no pruning is used. I rate this as rather unlikely.
2. More likely, there's a problem in the model somewhere (like the unary rule I already removed) that lets us generate a hypergraph of unbounded size, and since no pruning is being used, we go on forever trying to fill the chart.

The third possibility is that working without pruning really is that slow.

Dyer, Chris. Two monolingual parses are better than one (synchronous parse). 2010. In Proc. of NAACL.