[syllogism]

The Stanford parser is particularly slow --- it's in java, and it's written for research more than anything. The C&C CCG parser runs at about 60-80 sentences a second, although it gives either CCG constituents or dependencies -- so the output may take some interpretation.

Shift-reduce dependency parsers are linear time, and are giving state-of-the-art results. My parser's currently a pain in the ass to install, as it hasn't really been released yet, but it does hundreds of sentences a second. Accuracy is state-of-the-art -- 92-93% depending on the beam width and the evaluation set (Stanford or MALT dependencies).

https://github.com/syllog1sm/redshift/ . You'll want the develop branch. It's GPL licensed.

It's implemented in Cython (i.e., almost all the code is Cython --- I'm not using it just for the speed critical bits), which would make it easy to work with if you're using Python. But, as I said...I don't claim it's currently fit for human consumption.

A C++ implementation of the same algorithm is here: http://www.sutd.edu.sg/yuezhang.aspx . Note his papers too -- he did some of the important work on this line of research.

The last few years of work in shift-reduce dependency parsing have been a bit of a break-through in parsing, imo.

[bravura]

The Stanford parser is particularly slow --- it's in java, and it's written for research more than anything.

The choice of language is not what causes the slowness of the Stanford parser. It's the choice of search strategy, which trades-off speed for accuracy.

Shift-reduce dependency parsers are linear time, and are giving state-of-the-art results.

No, this is incorrect.

The choice of parsing logic (shift-reduce, dependency) and the search strategy (greedy, sometimes erroneously called "deterministic") are orthogonal. It's the greedy search strategy that leads to linear time performance.

The choice of logic determines the lower-bound (best-case) on parsing complexity. If you do exhaustive search for the exact solution of a shift-reduce dependency parser, it is worst-case exponential. In practice, you don't do exact search, and by using a beam search approximation you can get observed linear-time performance.

[edit: You can read my thesis if you are not familiar with what a parsing logic is.]

I am not aware of state-of-the-art results from greedy shift-reduce parsers. Do you mind sharing?

[syllogism]

> The choice of language is not what causes the slowness of the Stanford parser. It's the choice of search strategy, which trades-off speed for accuracy.

Even amongst chart parsers it's not a very quick implementation.

> The choice of parsing logic (shift-reduce, dependency) and the search strategy (greedy, sometimes erroneously called "deterministic") are orthogonal. It's the greedy search strategy that leads to linear time performance.

They're really only conceptually orthogonal, because in practice once you choose shift-reduce you're always going to choose greedy/deterministic/whatever search. I'm not aware of any shift-reduce/transition-based parsing results that don't use 1-best or beam search.

> I am not aware of state-of-the-art results from greedy shift-reduce parsers. Do you mind sharing?

Zhang and Nivre (2011) http://www.sutd.edu.sg/cmsresource/faculty/yuezhang/acl11j.p... 93.5 UAS on Stanford basic dependencies. This is the best published result on the dataset, and the best published dependency parsing result for English.

Probably the parser is still worse than the C&J reranking parser, when 200 parses are supplied to the reranker. But I'd be very surprised if it wasn't better than the Stanford parser, and probably also the Berkeley parser.

[microtonal]

Accuracy is state-of-the-art -- 92-93% depending on the beam width and the evaluation set (Stanford or MALT dependencies).

I assume that this is for English? A former colleague of mine compared two statistical dependency parsers (Malt and MST) to a rule-based dependency parser with a maxent disambiguation model, for Dutch. The rule-based system outperforms the statistical dependency parsers by a wide margin, both in-domain and out-of-domain:

http://dl.acm.org/citation.cfm?id=1870171

Nonetheless, I find work on statistical dependency parsing to be very exiting, since it is fast and requires far less human effort :).

https://github.com/syllog1sm/redshift/ . You'll want the develop branch. It's GPL licensed.

Very nice work!

[syllogism]

Yes, for English. There's a standard multi-lingual evaluation for statistical dependency parsers (the CoNLL 2007 data), but none for constituency parsers.

I had a look at that paper, but didn't read it carefully. All I can really say is that there's a real evaluation problem between rule-based and statistical parsers. Rule-based parsers recover richer representations, but tend to have lower coverage over arbitrary data --- they normally can't guarantee that a parse is returned; they may deem the sentence ungrammatical.

In that paper, the parsers were evaluated on "home ground" for the rule-based parser, as they used the treebank created for it. Having worked on the CCG formalism through my PhD, I can say that even small differences in annotation scheme can make a big difference in which parsers come out ahead.

[microtonal]

Rule-based parsers recover richer representations, but tend to have lower coverage over arbitrary data

This parser usually has a coverage around ~95-97%. In one experiment we also parsed Flemish (which uses some constructions that wouldn't be considered grammatical in Dutch) and obtained a coverage of ~94%.

It also has a robustness component that attempts to provide an analysis for as many constituents as possible if no fully spanning parse can be found.

Having worked on the CCG formalism through my PhD, I can say that even small differences in annotation scheme can make a big difference in which parsers come out ahead.

Certainly. But you are not mentioning the other elephant in the room: Dutch is a free word order language and also permits very liberal ordering in the middle field. The rule-based grammar may benefit from the detailed constraints in the lexical attribute-value structures.

[syllogism]

> Certainly. But you are not mentioning the other elephant in the room: Dutch is a free word order language and also permits very liberal ordering in the middle field. The rule-based grammar may benefit from the detailed constraints in the lexical attribute-value structures.

Mostly I didn't want to stick my neck out :p. It's easy to say something untrue about a language you don't know and haven't worked with.

I'd also be reluctant to assume which mechanisms were making a difference, because it's so hard to guess what cases are frequent and not easily inferred by a statistical model. One thing we can know is that the transition based parsers are best at producing projective dependency trees. The various techniques for non-projective shift-reduce parsing aren't very good.

Don't get me wrong --- I totally think the suggestion you offered makes sense, and it's a likely explanation. It's just that this stuff all very tricky.