Fabian M. Suchanek Dependency Parsing 31
Grammars help with structure Alizée is the mother of the little Annily.  is the mother of 2 PN PN V DET N PREP DET ADJ NP NP NP NP PP VP  S S -> NP VP NP -> N VP -> V NP -> DET ADJ N see Wikipedia/Phrase Structure Grammar try it out
Grammars help with structure Alizée is the mother of the little Annily.  is the mother of 3 PN PN V DET N PREP DET ADJ NP NP NP NP PP VP  S This is just a modifier of the noun!
Grammars help with structure Alizée is the mother of the little Annily.  is the mother of 4 PN PN V DET N PREP NP NP NP NP PP VP  S If we remove the modifiers, we match the pattern.
Grammars help with structure Alizée, who has a beautiful voice, is the mother of Annily. 5 PN PN V DET  is the mother of  N PREP NP NP NP NP PP VP  S PN DET ADJ NP SUB VP  V COMP The grammar identifies a sub‐ordinate phrase.
Grammars help with structure Alizée, who has a beautiful voice, is the mother of Annily. 6 PN PN V DET  is the mother of  N PREP NP NP NP NP PP VP  S If we remove the sub-ordinate phrase, the pattern matches.
Elvis          sings   a         song. In IE, one often uses dependency grammars. Dependency grammars 7 PN Verb Det Noun det obj subj
Def: Dependency grammar dependency grammar  is a set of rules of the form where X and Y are POS tags, L is a label. 8 X Y L Noun Verb Verb PN Det Noun subj obj det [ Joakim Nivre ] There are variants, where X and Y are words, or rules have more edges or no label. Dependency grammars and constituency grammars are strongly equivalent, as shown by H. Gaifman in 1965. or X Y L dependent head PN Verb Det Noun det obj subj Elvis          sings   a         song.
Dependency graph dependency graph  of a sentence is a connected acyclic graph whose nodes are the words and whose edges are given by the grammar, such that • Every word has at most one head • There generally is a verb without a head 9 Noun Verb Verb PN Det Noun subj obj det dependent head PN Verb Det Noun det obj subj Elvis          sings   a         song.
Examples: Dependency graph Try it out! 10 I shot an elephant in my pyjamas. subj obj nmod pmod news Economic had little effect on markets subj obj nmod pmod adj adj
Projection A dependency graph is  projective  if no arcs cross.  We consider only projective dependency graphs here. 11 He says  sentences  are rare  that are non-projective subj cop subj comp subj comp cop >convington
Covington’s Algorithm • Parse the sentence left to right   • Try to link every word to every previous word as permitted     by the grammar, going backwards in the sentence,     allowing only one head per word. 12 The Adj Noun Det Noun Verb Verb det cop subj song is great Det Noun Verb Adj
Covington’s Algorithm • Parse the sentence left to right   • Try to link every word to every previous word as permitted     by the grammar, going backwards in the sentence,     allowing only one head per word. 13 The Adj Noun Det Noun Verb Verb det cop subj song is great Det Noun Verb Adj
det Covington’s Algorithm • Parse the sentence left to right   • Try to link every word to every previous word as permitted     by the grammar, going backwards in the sentence,     allowing only one head per word. 14 The Adj Noun Det Noun Verb Verb det cop subj song is great Det Noun Verb Adj
Covington’s Algorithm • Parse the sentence left to right   • Try to link every word to every previous word as permitted     by the grammar, going backwards in the sentence,     allowing only one head per word. 15 The Adj Noun Det Noun Verb Verb det cop subj song is great Det Noun Verb Adj det
subj det Covington’s Algorithm • Parse the sentence left to right   • Try to link every word to every previous word as permitted     by the grammar, going backwards in the sentence,     allowing only one head per word. 16 The Adj Noun Det Noun Verb Verb det cop subj song is great Det Noun Verb Adj
subj det Covington’s Algorithm • Parse the sentence left to right   • Try to link every word to every previous word as permitted     by the grammar, going backwards in the sentence,     allowing only one head per word. 17 The Adj Noun Det Noun Verb Verb det cop subj song is great Det Noun Verb Adj
cop subj det Covington’s Algorithm • Parse the sentence left to right   • Try to link every word to every previous word as permitted     by the grammar, going backwards in the sentence,     allowing only one head per word. 18 The Adj Noun Det Noun Verb Verb det cop subj song is great Det Noun Verb Adj
Task: Covington's Algorithm Apply Convington's algorithm to 19 Not every idea by Coyote was brilliant. ADJ det V N subj DET V cop N neg N NEG PN PREP pobj N prep PREP PREP N PN V ADJ NEG DET
Runtime of Covington’s Algorithm • Parse the sentence left to right   • Try to link every word to every     previous word as permitted by grammar 20 PREP N PN NEG DET Not every idea by Coyote was brilliant. V ADJ
• Parse the sentence left to right   • Try to link every word to every     previous word as permitted by grammar 21 PREP N PN NEG DET Not every idea by Coyote was brilliant. V ADJ Runtime of Covington’s Algorithm
Complexity of Covington’s Algo 22 ? det det pobj loc The horse raced past the barn fell subj
Complexity of Covington’s Algo 23 det det pobj loc The horse raced past the barn fell subj subj
Complexity of Covington’s Algo 24 The horse raced past the barn fell loc subj det det pobj attr
Complexity of Covington’s Algo Parse left to right, connect every word to every possible preceding word (with constant access to the grammar):  With backtracking:  25 The horse raced past the barn fell loc subj det det pobj attr
Parsing When lexical ambiguity and agreement are present, parsing is NP-complete. 26 Barton et al: Computational Complexity and Natural Language.
Parsing The worst case does not occur, i.e., people do not actually utter sentences that put any reasonable parsing algorithm into a worst-case situation. 27 Covington: A Fundamental Algorithm for Dependency Parsing When lexical ambiguity and agreement are present, parsing is NP-complete. Barton et al: Computational Complexity and Natural Language.
Parsing 28 Dependency parsing works very well in practice. The worst case does not occur, i.e., people do not actually utter sentences that put any reasonable parsing algorithm into a worst-case situation. Covington: A Fundamental Algorithm for Dependency Parsing When lexical ambiguity and agreement are present, parsing is NP-complete. Barton et al: Computational Complexity and Natural Language.
Def: Dependency Patterns dependency pattern  is a chain graph whose nodes are words or X or Y. A dependency pattern   matches a dependency graph  , if there is   a substitution   for X and Y such that  . 29 RR Coyote eats tasty a subj obj eats X Y obj subj
Def: Dependency Patterns dependency pattern  is a chain graph whose nodes are words or X or Y. A dependency pattern   matches a dependency graph  , if there is   a substitution   for X and Y such that  . 30 eats X Y obj subj obj subj eats RR a tasty Coyote, who is hungry,
... but not all problems are solved 31 Coyote dreams that Coyote eats a roadrunner. eats X Y obj subj obj subj ->ie-by-reasoning ->semantic-web
References 32 ->ie-by-reasoning ->semantic-web ->security Michael Covington: A Fundamental Algorithm for Dependency Parsing ”, ACM Southeast 2001 Joakim Nivre: An Efficient Algorithm for Projective Dependency Parsing ”, IWPT 2003