19

For example, Cer, Daniel M., et al. "Parsing to Stanford Dependencies: Trade-offs between Speed and Accuracy." LREC. 2010. :

enter image description here

Why is dependency parsing so much faster than constituency parsing?

1
  • 1
    I haven't worked with all the parsers listed here, but I have worked with a few. From what I have seen, the difference usually comes down to the difference in the implementation's programming language.
    – prash
    Mar 31, 2014 at 8:20

5 Answers 5

12

Parsing speed obviously depends on a lot of factors, but in this case I would say that algorithmic complexity is the most important. The transition-based dependency parsers (all except MSTParser and RelEx) use greedy decoding and achieve linear complexity (or quadratic in the case of the Covington algorithm). This should be compared to the constituency-based parsers, which are all based on CKY-style dynamic programming, which is O(n^5) for lexicalized models. MSTParser is somewhere in between. It uses dynamic programming, but thanks to the Eisner style split-head representation it runs in O(n^3) time. The more constrained nature of the dependency parsing problem, mentioned in several comments, also plays a role in that it tends to give tighter "grammar constants" (fewer cases to consider in each derivation step), and it also facilitates the use of split-head representations to reduce complexity.

8
  • What is a "split-head" representation? Does that mean that a given word can have two heads? That's what Word Grammar does, but I think most dependency grammars assume that all structures are rooted, meaning that a given word can have only one head. Apr 1, 2014 at 15:59
  • @TimOsborne Ref. cs.jhu.edu/~jason/papers/eisner+satta.acl99.pdf
    – prash
    Apr 1, 2014 at 16:59
  • @prash, I've taken a look at that paper. That sucker is dense. I cannot begin to penetrate it. How about a brief explanation in normal English. What does "split head representation" mean in this context. One other comment, most of what I see in the paper looks more like constituency than dependency, e.g. c-command and the like. Apr 1, 2014 at 17:45
  • 2
    In CKY-style parsing you combine smaller trees into bigger trees and the root of a tree can be anywhere in the span. So you need to keep track of five indices: the start, mid and end points of the two trees being combined, and the position of the two roots. With a split head representation, you instead combine half trees (a head word together with its left or right half subtree), so you only need to keep track of the start, mid and end points + a boolean variable indicating whether the head is at the left or right periphery of the half tree. This is how you get from O(n^5) to O(n^3). Apr 2, 2014 at 7:04
  • 2
    The price to pay for the improvement in complexity with split-head representations is that you cannot use features that combine information from the left and right half-tree. This is why split-head parsers are more prone to make the error of attaching two subjects to the same verb, one on each side. Apr 2, 2014 at 7:05
9

Michael Collins gives a nice explanation in his MOOC on NLP, summarized in this slide:

enter image description here

In short:

  • with the usual CKY algorithm in PCFG parsing, which is based on dynamic programming and yields a constituency-based tree, you have a time complexity of O(n^3 * G^3) as the dynamic programming algorithm is also looking for which non-terminal to choose (hence G^3).
  • in dependency parsing, the dynamic programming algorithm (e.g. (Covington 2001) that jlawler cited) doesn't have to choose any non-terminal, so the time complexity is simply O(n^3)

Since G (the number of non-terminals in the grammar) is in the order of 50, if your O(n^3) takes 10 seconds to run (in the dependency parsing case), it will take almost 10 minutes if it becomes O(n^3 * G^3) (in the constituency parsing case).


References:

  • (Covington 2001) Covington, Michael A. "A fundamental algorithm for dependency parsing." Proceedings of the 39th annual ACM southeast conference. 2001.
  • For a nice overview of dependency parsing algorithms: Kübler, Sandra, Ryan McDonald, and Joakim Nivre. "Dependency parsing." Synthesis Lectures on Human Language Technologies 1.1 (2009): 1-127.
1
  • 1
    This compares two specific algorithms (CKY and Eisner), which are rarely implemented as-is. As an example, all parsers on Cer's list (Berkeley only to some extent) use pruning to mitigate the G^3 factor. Jun 25, 2017 at 9:19
8

I asked Michael Covington, whose name is on one of the faster parsers, and he replies:

I don't know the inner workings of any of these parsers (not even the one with my name on it, which was implemented by Joakim Nivre). Choice of programming language may have a lot to do with it.

Another factor is that with dependency parsing, the search space can be considerably smaller because you're only linking together nodes that already exist, not creating an unknown number of new ones. The person to ask is Joakim Nivre. Here's the paper that, in some sense, started the ball rolling: http://www.ai.uga.edu/mc/dgpacmcorr.pdf

1
  • That dependency parsing is much faster than constituency parsing makes sense to me due to the inherent minimalism of dependency. Mar 31, 2014 at 17:18
5

There are several factors at play:

  • The implementation language: C/C++ is faster than Java is faster than Python
  • The algorithm: Most of the constituent parsers, as well as MSTParser, use a dynamic programming approach with O(N^3) time consumption. The ones with "Nivre" in the name use a stepwise deterministic approach with O(N) time consumption. The "Covington" algorithm has O(N^2) time consumption
  • The classification algorithm: "Nivre Eager Feature Interact" uses a classification algorithm that is more expensive than the normal linear classifier used by most others
  • Finally, there is something called the "Grammar constant" - In constituent parsing, you have labels on the phrases, and deciding on which labels are appropriate depends on the label set.

There are constituent parsers that implement an O(N) algorithm similar to that used by most dependency parsers:

The Stanford SRParser is about 30x as fast as the "Stanford" parser from the table, with better accuracy. It is still slower than the dependency parsers, presumably because of the "grammar constant" - it is reasonable to expect a constituent parser to be 2-3x slower when using a roughly comparable algorithm.

The table above does not use a "roughly comparable algorithm", so it is more of an apples-to-oranges comparison based on the most popular software implementations that people use.

1

I have no experience building parsers, but I would guess that Dependency parsing is faster because the trees that need to be built are simpler. If you know a given word's part of speech, you have to answer just one more question: which other word in the sentence is its parent? In CG parsing, you need to know which other word or words in the sentence are in the same constituent, and what kind of constituent is it?

The programming language can play a role as well, but it is also possible that we now have such specialized programming languages that a given language can do only one kind of tree or the other. In that case, I expect the languages that can do only DG trees to be simpler than the ones that can do only CG trees.

2
  • 1
    You are using "CG" as an abbreviation for "constituency grammar", right? I've also seen "CG" used for "cognitive grammar" and "categorial grammar". Apr 1, 2014 at 15:44
  • And 'construction grammar' :P Nov 21, 2016 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.