CC-BY Fabian M. Suchanek Dependency Parsing 38
•  Dependency grammars •  Convington’s algorithm •  Summary Overview 2
Dependency grammars 3 det obj subj Honest grandness needs no praise  .     ADJ              N                 V        DET     N mod
Def: Dependency grammar A 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 Noun 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 A 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 Noun Verb Verb Det Noun subj obj det Adj Noun mod det obj subj Honest grandness needs no praise  .     ADJ              N                 V        DET     N mod Noun dependent head
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 Exists in natural language in the form of •  cross‐serial dependencies (Swiss German) •  Scrambling (also in high German)
•  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 Similar: “The old man the boat” “The complex houses married soldiers.”
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 25 Dependency parsing works very well in practice. Dependency grammars and context‐free grammars are strongly equivalent, as shown by H. Gaifman in 1965. 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.
Dependency Parsing in Python 26 import spacy py_text = "spacy dependency parser in python" py_nlp = spacy.load ("en_core_web_sm") py_doc = py_nlp (py_text) for token in py_doc:          # token.py_text: the word # token.dep_: the type of dependency # token.head: the head of the token.py_text, # token.children: the children of the token [Spacy.io documentation]
•  Dependency grammars •  Convington’s algorithm •  Summary Overview 27 >dep pattern
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 ->Formal-grammars ->Knowledge-representation
References 29 Michael Covington: “A Fundamental Algorithm for Dependency Parsing”, ACM Southeast 2001 Joakim Nivre: “An Efficient Algorithm for Projective Dependency Parsing”, IWPT 2003