3

I come from a computer science perspective and am trying to understand dependency parsing.

What is the formal (computational) model for dependency parsing? The computational model for constituency parsing is a CFG; anything that can be generated from the rules of the CFG (like NP -> (Det) N (PP)) is a valid sentence/parse. How is the set of valid sentences/parses in dependency parsing described?

It seems like dependency parses and constituency parses give different kinds of information and that in general a constituency parse gives more information than a dependency parse. Why is this the case? What are examples where a sentence where a dependency parse can correspond to multiple constituency parses, so has less information (or vice versa)?

References are also appreciated. Thanks!

Improve this question
5
  • For the theoretical part, i.e. what are dependency grammars vs. PSGs tell us about a sentence, this question might be of interest: linguistics.stackexchange.com/q/3420/13238
    – Natalie Clarius
    Commented Dec 1, 2016 at 20:01
  • I would also like to add that although a detailled phrase structure analysis (as done in theoretical linguistics) usually contains more information about a sentence's strcuture than a dependency parse, much of this information is completely irrelevant to the purpose of computational processing. For example, there is an ongoing dispute about whether constituents like the cat are to be analyzed as a DP or an NP, with different assumptions about their inner structure and x-bar-levels etc. Or how to deal with ditransitive verbs when you impose the principle of binary branching. ...
    – Natalie Clarius
    Commented Dec 1, 2016 at 20:13
  • ... Or what this operation sometimes called "affix hopping" is supposed to be when you don't wan't to give up the very far-reaching principle of movement happening only "upwards" a tree. A parser doesn't care about such theory-internal considerations: As long as everything is in the right place and can be meaningfully related to some other words it interacts with, the sentence is grammatical and that's fine. That's why dependency parsing is often much mor suited for NLP purposes - because you don't need to care about all the complications arising from an accurate constituent analysis.
    – Natalie Clarius
    Commented Dec 1, 2016 at 20:14
  • @lemontree I wouldn't say dependency parsing is more suited for NLP, dependency parsers implicitly employ constituent-based analysis anyway, it's just not explicit. On the other hand, constituent-based parsers typically produce - maybe as an unsolicited byproduct - dependency structures.
    – Atamiri
    Commented Dec 2, 2016 at 10:14
  • @Atamiri Sure, dependency and constituency based grammars are not completely distinct from each other; but I do think that full-fledged constituency grammars as found discussions about in theoretical syntax papers exhibit way more complexity in the syntactic details (or problems arising from being as accurate as possible) than an average dependency parse which contains solely the lexical items with labelled relations between them, and thus doesn't need to deal with problems like functional categories or phonetically empty elements, which I think makes the implementaiton a little easier.
    – Natalie Clarius
    Commented Dec 7, 2016 at 19:44

3 Answers 3

Reset to default
2

Dependency parsing is constraint solving. I recommend you have a look at XDG, which is the only formally precise dependency grammar approach I'm aware of.

Improve this answer
1

There are many actively researched aspects in the field of natural language parsing. Nearly all of this activity is on statistical parsers. Consequently, there is no "standard" computational model for dependency parsers -- there are many competing and collaborating methodologies.

The computational model for constituency parsing is a CFG...

That was the case a long time ago, but now, mostly used as a stepping stone in pedagogy. The problem with bare CFG is that it produces an explosion in the number of valid parses (according to CFG) of typical sentences, whereas a human can easily discard most of these parses as meaningless. To overcome this limitation, broad-coverage parsers are based on statistical models. CFG may still be the grammar of such parsers, but the term "computational model" encompasses a lot more now.

Since the field is vast, I'll point you to just one example of how a parser could work. Matthew Honnibal's blogpost, Parsing English in 500 Lines of Python, is one of the best I've come across.

Improve this answer
2
  • By computational model I meant describing what is syntactically allowed rather than semantically meaningful (ex. "Colorless green ideas sleep furiously" is grammatically correct). What model describes the (possibly large) set of grammatically correct parses for a dependency parser, whether or not they are semantically meaningful?
    – Holden Lee
    Commented Dec 1, 2016 at 15:13
  • @HoldenLee "describing what is syntactically allowed" --> No, that's gone with statistical models. Instead of being described, these rules (and their weights) are induced by creating statistical models based on training corpora. I won't elaborate on semantics, because that's a whole new can of worms, all I can say for now is that these statistical models induce a bit of semantics also.
    – prash ♦
    Commented Dec 1, 2016 at 16:05
0

If you google search on "dependency grammar vs constituency grammar", you'll get a number of discussions that may be relevant to your question. Personally, I have not managed to understand dependency grammarians' views about this. My impression has been that dependency grammar is a variety of CFG.

Improve this answer

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.