Experiments with a Higher-Order Projective Dependency Parser

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 957–961, Prague, June 2007. c⃝2007 Association for Computational Linguistics Experiments with a Higher-Order Projective Dependency Parser Xavier Carreras Massachusetts Institute of Technology (MIT) Computer Science and Artificial Intelligence Laboratory (CSAIL) 32 Vassar St., Cambridge, MA 02139 carreras@csail.mit.edu Abstract We present experiments with a dependency parsing model defined on rich factors. Our model represents dependency trees with fac- tors that include three types of relations be- tween the tokens of a dependency and their children. We extend the projective pars- ing algorithm of Eisner (1996) for our case, and train models using the averaged percep- tron. Our experiments show that consider- ing higher-order information yields signifi- cant improvements in parsing accuracy, but comes at a high cost in terms of both time and memory consumption. In the multi- lingual exercise of the CoNLL-2007 shared task (Nivre et al., 2007), our system obtains the best accuracy for English, and the second best accuracies for Basque and Czech. 1 Introduction Structured prediction problems usually involve models that work with factored representations of structures. The information included in the factors determines the type of features that the model can exploit. However, richer representations translate into higher complexity of the inference algorithms associated with the model. In dependency parsing, the basic first-order model is defined by a decomposition of a tree into head- modifier dependencies. Previous work extended this basic model to include second-order relations—i.e. dependencies that are adjacent to the main depen- dency of the factor. Specifically, these approaches considered sibling relations of the modifier token (Eisner, 1996; McDonald and Pereira, 2006). In this paper we extend the parsing model with other types of second-order relations. In particular, we incorpo- rate relations between the head and modifier tokens and the children of the modifier. One paradigmatic case where the relations we consider are relevant is PP-attachment. For example, in “They sold 1,210 cars in the U.S.”, the ambigu- ity problem is to determine whether the preposition “in” (which governs “the U.S.”) is modifying “sold” or “cars”, the former being correct in this case. It is generally accepted that to solve the attachment deci- sion it is necessary to look at the head noun within the prepositional phrase (i.e., “U.S.” in the exam- ple), which has a grand-parental relation with the two candidate tokens that the phrase may attach— see e.g. (Ratnaparkhi et al., 1994). Other ambigu- ities in language may also require consideration of grand-parental relations in the dependency structure. We present experiments with higher-order models trained with averaged perceptron. The second-order relations that we incorporate in the model yield sig- nificant improvements in accuracy. However, the in- ference algorithms for our factorization are very ex- pensive in terms of time and memory consumption, and become impractical when dealing with many la- bels or long sentences. 2 Higher-Order Projective Models A dependency parser receives a sentence x of n to- kens, and outputs a labeled dependency tree y. In the tree, a labeled …

Content truncated to 500 words