Log-Linear Models of Non-Projective Trees, k-best MST Parsing and Tree-Ranking

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 962–966, Prague, June 2007. c⃝2007 Association for Computational Linguistics Log-linear Models of Non-projective Trees, k-best MST Parsing and Tree-ranking Keith Hall1 and Jiˇr´ı Havelka2 and David A. Smith1 1Center for Language and Speech Processing Johns Hopkins University Baltimore, MD USA keith hall@jhu.edu dasmith@cs.jhu.edu 2Institute of Formal and Applied Linguistics Charles University Prague, Czech Republic havelka@ufal.mff.cuni.cz Abstract We present our system used in the CoNLL 2007 shared task on multilingual parsing. The system is composed of three compo- nents: a k-best maximum spanning tree (MST) parser, a tree labeler, and a reranker that orders the k-best labeled trees. We present two techniques for training the MST parser: tree-normalized and graph- normalized conditional training. The tree- based reranking model allows us to explic- itly model global syntactic phenomena. We describe the reranker features which include non-projective edge attributes. We provide an analysis of the errors made by our system and suggest changes to the models and fea- tures that might rectify the current system. 1 Introduction Reranking the output of a k-best parser has been shown to improve upon the best results of a state- of-the-art constituency parser (Charniak and John- son, 2005). This is primarily due to the ability to incorporate complex structural features that cannot be modeled under a CFG. Recent work shows that k-best maximum spanning tree (MST) parsing and reranking is also viable (Hall, 2007). In the current work, we explore the k-best MST parsing paradigm along with a tree-based reranker. A system using the parsing techniques presented in this paper was entered in the CoNLL 2007 shared task competi- tion (Nivre et al., 2007). This task evaluated pars- ing performance on 10 languages: Arabic, Basque, Catalan, Chinese, Czech, English, Greek, Hungar- ian, Italian, and Turkish using data originating from a wide variety of dependency treebanks, and trans- formations of constituency-based treebanks (Hajiˇc et al., 2004; Aduriz et al., 2003; Mart´ı et al., 2007; Chen et al., 2003; B¨ohmov´a et al., 2003; Marcus et al., 1993; Johansson and Nugues, 2007; Prokopidis et al., 2005; Csendes et al., 2005; Montemagni et al., 2003; Oflazer et al., 2003). We show that oracle parse accuracy1 of the out- put of our k-best parser is generally higher than the best reported results. We also present the results of a reranker based on a rich set of structural fea- tures, including features explicitly targeted at mod- eling non-projective configurations. Labeling of the dependency edges is accomplished by an edge la- beler based on the same feature set as used in train- ing the k-best MST parser. 2 Parser Description Our parser is composed of three components: a k- best MST parser, a tree-labeler, and a tree-reranker. Log-linear models are used for each of the com- ponents independently. In this section we give an overview of the models, the training techniques, and the decoders. 2.1 MST Parsing, Reranking, and Labeling The connection between the maximum spanning tree problem and dependency parsing stems from …

Content truncated to 500 words