Online Learning of Approximate Dependency Parsing Algorithms

Online Learning of Approximate Dependency Parsing Algorithms Ryan McDonald Fernando Pereira Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 {ryantm,pereira}@cis.upenn.edu Abstract In this paper we extend the maximum spanning tree (MST) dependency parsing framework of McDonald et al. (2005c) to incorporate higher-order feature rep- resentations and allow dependency struc- tures with multiple parents per word. We show that those extensions can make the MST framework computationally in- tractable, but that the intractability can be circumvented with new approximate pars- ing algorithms. We conclude with ex- periments showing that discriminative on- line learning using those approximate al- gorithms achieves the best reported pars- ing accuracy for Czech and Danish. 1 Introduction Dependency representations of sentences (Hud- son, 1984; Me´lˇcuk, 1988) model head-dependent syntactic relations as edges in a directed graph. Figure 1 displays a dependency representation for the sentence John hit the ball with the bat. This sentence is an example of a projective (or nested) tree representation, in which all edges can be drawn in the plane with none crossing. Sometimes a non-projective representations are preferred, as in the sentence in Figure 2.1 In particular, for freer-word order languages, non-projectivity is a common phenomenon since the relative positional constraints on dependents is much less rigid. The dependency structures in Figures 1 and 2 satisfy the tree constraint: they are weakly connected graphs with a unique root node, and each non-root node has a exactly one parent. Though trees are 1Examples are drawn from McDonald et al. (2005c). more common, some formalisms allow for words to modify multiple parents (Hudson, 1984). Recently, McDonald et al. (2005c) have shown that treating dependency parsing as the search for the highest scoring maximum spanning tree (MST) in a graph yields efficient algorithms for both projective and non-projective trees. When combined with a discriminative online learning al- gorithm and a rich feature set, these models pro- vide state-of-the-art performance across multiple languages. However, the parsing algorithms re- quire that the score of a dependency tree factors as a sum of the scores of its edges. This first-order factorization is very restrictive since it only allows for features to be defined over single attachment decisions. Previous work has shown that condi- tioning on neighboring decisions can lead to sig- nificant improvements in accuracy (Yamada and Matsumoto, 2003; Charniak, 2000). In this paper we extend the MST parsing frame- work to incorporate higher-order feature represen- tations of bounded-size connected subgraphs. We also present an algorithm for acyclic dependency graphs, that is, dependency graphs in which a word may depend on multiple heads. In both cases parsing is in general intractable and we provide novel approximate algorithms to make these cases tractable. We evaluate these algorithms within an online learning framework, which has been shown to be robust with respect approximate in- ference, and describe experiments displaying that these new models lead to state-of-the-art accuracy for English and the best accuracy we know of for Czech and Danish. 2 Maximum Spanning Tree Parsing Dependency-tree …

Content truncated to 500 words