Fabian M. Suchanek Dependency Parsing 38
•   Dependency grammars •   Convington’s algorithm •   Summary Overview 2
In IE, one often uses dependency grammars. Dependency grammars 3 det obj subj Honest grandness needs no praise  .     ADJ              N                 V        DET     N mod
Def: Dependency grammar dependency grammar  is a set of rules of the form where X and Y are POS tags, L is a label. 4 X Y L Noun Verb Verb PN Det Noun subj obj det or X Y L dependent head [ Joakim Nivre ] There are variants, where X and Y are words, or rules have more edges or no label. Adj Noun mod det obj subj Honest grandness needs no praise  .     ADJ              N                 V        DET     N mod
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 5 dependent head Noun Verb Verb PN Det Noun subj obj det Adj Noun mod det obj subj Honest grandness needs no praise  .     ADJ              N                 V        DET     N mod
Examples: Dependency graph Try it out! 6 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. 7 He says  sentences  are rare  that are non-projective subj cop subj comp subj comp cop >convington
•   Dependency grammars •   Convington’s algorithm •   Summary Overview 8
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. 9 You should chew before you swallow. PRON   AUX      V         ADP   PRON      V PRON AUX V ADP V V V V subj aux advcl mark
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. 10 V V V V subj aux advcl mark You should chew before you swallow. PRON   AUX      V         ADP   PRON      V PRON AUX V ADP
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. 11 V V V V subj aux advcl mark You should chew before you swallow. PRON   AUX      V         ADP   PRON      V PRON AUX V ADP
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 V V V V subj aux advcl mark subj aux You should chew before you swallow. PRON   AUX      V         ADP   PRON      V PRON AUX V ADP
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 V V V V subj aux advcl mark subj aux You should chew before you swallow. PRON   AUX      V         ADP   PRON      V PRON AUX V ADP
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 V V V V subj aux advcl mark subj aux You should chew before you swallow. PRON   AUX      V         ADP   PRON      V PRON AUX V ADP
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 V V V V subj aux advcl mark subj aux advcl mark subj You should chew before you swallow. PRON   AUX      V         ADP   PRON      V PRON AUX V ADP
Task: Covington’s Algorithm 16 Over himself, over his own body and mind, the individual is sovereign. PRP         N           PRP   PP   ADJ      N       CONJ     N       DET           N            V       ADJ N V ADJ V N N CONJ N N det subj cop pmod pobj conj cc mod mod DET N V PRP PRP N N PP ADJ John Stuart Mill
Runtime of Covington’s Algorithm •  Parse the sentence left to right     •  Try to link every word to every         previous word as permitted by grammar 17 Over himself, over his own body and mind, the individual is sovereign. PRP         N           PRP   PP   ADJ      N       CONJ     N       DET           N            V       ADJ
18 Runtime of Covington’s Algorithm •  Parse the sentence left to right     •  Try to link every word to every         previous word as permitted by grammar Key advantage of dependency parsing (and Convington’s algorithm): It can process a sentence incrementally. Over himself, over his own body and mind, the individual is sovereign. PRP         N           PRP   PP   ADJ      N       CONJ     N       DET           N            V       ADJ
Complexity of Covington’s Algo 19 ? The horse raced past the barn fell loc subj det det pobj
Complexity of Covington’s Algo 20 The horse raced past the barn fell loc subj det pobj det subj
Complexity of Covington’s Algo 21 The horse raced past the barn fell loc subj det pobj attr det
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:  22 The horse raced past the barn fell loc subj det pobj attr det
Parsing When lexical ambiguity and agreement are present, parsing is NP-complete. 23 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. 24 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 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. 25 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. Dependency parsing works very well in practice. Dependency grammars and context‐free grammars are strongly equivalent, as shown by H. Gaifman in 1965. ->Formal-grammars
•   Dependency grammars •   Convington’s algorithm •   Summary Overview 26
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  . 27 The flesh is often willing if the spirit is weak. subj cop is X Y cop subj Dependency patterns are robust to surface variations such as noun modifiers or subordinate phrases.
Summary: Dependency Parsing Dependency parsing is a standard way of extracting the syntactic structure of a sentence. •  Dependency grammars are equivalent to phrase structure grammars •  Using dependency patterns in information extraction can help in     dealing with surface variations in sentences 28 The flesh is often willing if the spirit is weak. subj cop is X Y cop subj
References 29 Michael Covington: A Fundamental Algorithm for Dependency Parsing ”, ACM Southeast 2001 Joakim Nivre: An Efficient Algorithm for Projective Dependency Parsing ”, IWPT 2003 ->Semantic-web