Layer-Based Dependency Parsing

Layer-Based Dependency Parsing* Ping Jian and Chengqing Zong Institute of Automation, Chinese Academy of Sciences No. 95 Zhongguancun East Road, Beijing, 100190, China {pjian, cqzong}@nlpr.ia.ac.cn Abstract. In this paper, a layer-based projective dependency parsing approach is presented. This novel approach works layer by layer from the bottom up. Inside the layer the dependency graphs are searched exhaustively while between the layers the parser state transfers deterministically. Taking the dependency layer as the parsing unit, the proposed parser has a lower computational complexity than graph-based models which search for a whole dependency graph and alleviates the error propagation that transition-based models suffer from to some extent. Furthermore, our parser adopts the sequence labeling models to find the optimal sub-graph of the layer which demonstrates that the sequence labeling techniques are also competent for hierarchical structure analysis tasks. Experimental results indicate that the proposed approach offers desirable accuracies and especially a fast parsing speed. Keywords: dependency parsing, dependency layer, sequence labeling * The research work has been partially funded by the Natural Science Foundation of China under grant No.60736014, 60723005 and 90820303, the National Key Technology R&D Program under grant No. 2006BAH03B02, the Hi-Tech Research and Development Program (863 Program) of China under grant No. 2006AA010108-4, and also supported by the China-Singapore Institute of Digital Media as well. Copyright 2009 by Ping Jian and Chengqing Zong 1 Introduction Graph-based models (McDonald et al., 2005; McDonald and Pereira, 2006) and transition- based models (Yamada and Matsumoto, 2003; Nivre and Scholz, 2004) are two dominant paradigms in the dependency parsing community. McDonald and Nivre (2007) have made elaborate analyses about the very different theoretical properties of these two kinds of models and the corresponding experimental behaviors. Generally, graph-based approaches learn a model for scoring possible dependency graphs of an input sentence and apply exhaustive search algorithms to find the one that maximizes the score. The unit graph-based models calculate is the whole sentence (the whole dependency graph) both in training and inference procedures, which results in a cubic computational complexity (in projective case). By contrast, transition-based approaches train a classifier to greedily choose the best parsing action under the current parser state. They make decisions at a configuration which is usually composed by a couple of focus tokens and the parsing contexts. Therefore, these two kinds of dependency parsing methods represent the two extremes when they seek the best dependency structure of the input sentence. In this paper, we adopt a moderate structural granularity to calculate the parser: a dependency layer. The dependency layer we mean here is a set of tokens whose dependency depth (the depth of the dependency tree) is at most one. Inside the layer the dependency graphs can be searched exhaustively while between the layers the parser state transfers deterministically. On one hand, this design will decrease the computational cost for searching the whole tree like graph-based models do; on the other hand, it may alleviate the error propagation resulting from the complete no “search” outside the parsing configuration in …

Content truncated to 500 words