dependency or constituency treebank?

Question

Most Treebank conversion which I found in the web are from constituency treebank to dependency treebank, I wonder why there is little works in the opposite direction?

Does it mean that nowadays dependency parsing is more promising and "the state of art" in the field of NLP? if yes why?

Answer 1

There is a rather simple answer to this question. This answer is that conversion from dependency to constituency is not really possible, at least not in the way imagined. Dependency structures are usually flatter than the corresponding constituency structures. What this means is that when one translates from dependency to constituency, the result is a rather flat constituency structure. Most constituency grammars assume more layered structures than dependency-based systems can acknowledge.

If a constituency structure is entirely headed, then it can always be easily translated to the corresponding dependency structure, and the resulting dependency structure will be considered valid by most people who do dependency parsing. The opposite does not hold, however. If a dependency structure is translated to the corresponding constituency structure, the resulting constituency structure will be flatter than most people who do constituency parsing want to assume.

To restate the point in other terms, it is possible to automatically translate layered constituency structures to rather flat dependency structures, but translating rather flat dependency structures to layered constituency structures is impossible.

Finally, I cannot confidently answer the last part of the question, since I am not working in NLP. However, my limited exposure to trends in NLP suggests that the answer is yes, i.e. dependency parsing is indeed the "state of the art" in the field of NLP. From what I understand, dependency parsing is now preferred in many NLP circles because it is in general simpler and faster.

Answer 2

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

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.