Global Learning of Labeled Dependency Trees

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 1156–1160, Prague, June 2007. c⃝2007 Association for Computational Linguistics Global Learning of Labelled Dependency Trees Michael Schiehlen Kristina Spranger Institute for Computational Linguistics University of Stuttgart D-70174 Stuttgart Michael.Schiehlen@ims.uni-stuttgart.de Kristina.Spranger@ims.uni-stuttgart.de Abstract In the paper we describe a dependency parser that uses exact search and global learning (Crammer et al., 2006) to produce labelled dependency trees. Our system inte- grates the task of learning tree structure and learning labels in one step, using the same set of features for both tasks. During la- bel prediction, the system automatically se- lects for each feature an appropriate level of smoothing. We report on several exper- iments that we conducted with our system. In the shared task evaluation, it scored better than average. 1 Introduction Dependency parsing is a topic that has engendered increasing interest in recent years. One promis- ing approach is based on exact search and struc- tural learning (McDonald et al., 2005; McDonald and Pereira, 2006). In this work we also pursue this approach. Our system makes no provisions for non-projective edges. In contrast to previous work, we aim to learn labelled dependency trees at one fell swoop. This is done by maintaining several copies of feature vectors that capture the features’ impact on predicting different dependency relations (deprels). In order to preserve the strength of Mc- Donald et al. (2005)’s approach in terms of unla- belled attachment score, we add feature vectors for generalizations over deprels. We also employ vari- ous reversible transformations to reach treebank for- mats that better match our feature representation and that reduce the complexity of the learning task. The paper first presents the methodology used, goes on to describing experiments and results and finally con- cludes. 2 Methodology 2.1 Parsing Algorithm In our approach, we adopt Eisner (1996)’s bottom- up chart-parsing algorithm in McDonald et al. (2005)’s formulation, which finds the best pro- jective dependency tree for an input string �� ���� � � . We assume that every possible head– dependent pair  � is described by a feature vec- tor  with associated weights   . Eisner’s algo- rithm achieves optimal tree packing by storing par- tial structures in two matrices and . First the diagonals of the matrices are initiated with 0; then all other cells are filled according to eqs. (1) and (2) and their symmetric variants.   �  ! "   � #%$'& (*) �+ (*,   (.-/( 0 �  -   (1)   � #%$'& (*)  ,( +1  (.-/(  (2) root � #2$'& (*) � + ( +  � (3-/(  - 54 ( 674 ( This algorithm only accommodates features for sin- gle links in the dependency graph. We also investi- gated an extension, McDonald and Pereira (2006)’s second-order model, where more of the parsing his- tory is taken into account, viz. the last dependent 8 assigned to a head  . In the extended …

Content truncated to 500 words