Dependency Parsing as Head Selection

Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 665–676, Valencia, Spain, April 3-7, 2017. c⃝2017 Association for Computational Linguistics Dependency Parsing as Head Selection Xingxing Zhang, Jianpeng Cheng and Mirella Lapata Institute for Language, Cognition and Computation School of Informatics, University of Edinburgh 10 Crichton Street, Edinburgh EH8 9AB {x.zhang,jianpeng.cheng}@ed.ac.uk, mlap@inf.ed.ac.uk Abstract Conventional graph-based dependency parsers guarantee a tree structure both during training and inference. Instead, we formalize dependency parsing as the prob- lem of independently selecting the head of each word in a sentence. Our model which we call DENSE (as shorthand for Dependency Neural Selection) produces a distribution over possible heads for each word using features obtained from a bidirectional recurrent neural network. Without enforcing structural constraints during training, DENSE generates (at inference time) trees for the overwhelm- ing majority of sentences, while non-tree outputs can be adjusted with a maximum spanning tree algorithm. We evaluate DENSE on four languages (English, Chi- nese, Czech, and German) with varying degrees of non-projectivity. Despite the simplicity of the approach, our parsers are on par with the state of the art.1 1 Introduction Dependency parsing plays an important role in many natural language applications, such as re- lation extraction (Fundel et al., 2007), machine translation (Carreras and Collins, 2009), language modeling (Chelba et al., 1997; Zhang et al., 2016) and ontology construction (Snow et al., 2005). De- pendency parsers represent syntactic information as a set of head-dependent relational arcs, typi- cally constrained to form a tree. Practically all models proposed for dependency parsing in recent years can be described as graph-based (McDon- 1Our code is available at http://github.com/ XingxingZhang/dense_parser. ald et al., 2005a) or transition-based (Yamada and Matsumoto, 2003; Nivre et al., 2006b). Graph-based dependency parsers are typically arc-factored, where the score of a tree is defined as the sum of the scores of all its arcs. An arc is scored with a set of local features and a lin- ear model, the parameters of which can be effec- tively learned with online algorithms (Crammer and Singer, 2001; Crammer and Singer, 2003; Fre- und and Schapire, 1999; Collins, 2002). In or- der to efficiently find the best scoring tree during training and decoding, various maximization algo- rithms have been developed (Eisner, 1996; Eisner, 2000; McDonald et al., 2005b). In general, graph- based methods are optimized globally, using fea- tures of single arcs in order to make the learn- ing and inference tractable. Transition-based algo- rithms factorize a tree into a set of parsing actions. At each transition state, the parser scores a candi- date action conditioned on the state of the transi- tion system and the parsing history, and greedily selects the highest-scoring action to execute. This score is typically obtained with a classifier based on non-local features defined over a rich history of parsing decisions (Yamada and Matsumoto, 2003; Zhang and Nivre, 2011). Regardless of the algorithm used, most well-known dependency parsers, such as the MST-Parser (McDonald et …

Content truncated to 500 words