The Exploration of Deterministic and Efficient Dependency Parsing

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 241–245, New York City, June 2006. c⃝2006 Association for Computational Linguistics The Exploration of Deterministic and Efficient Dependency Parsing Yu-Chieh Wu Yue-Shi Lee Jie-Chi Yang Dept. of Computer Science and Information Engineering Dept. of Computer Science and Information Engineering Graduate Institute of Net- work Learning Technology National Central University Ming Chuan University National Central University Taoyuan, Taiwan Taoyuan, Taiwan Taoyuan, Taiwan bcbb@db.csie.ncu.edu.tw lees@mcu.edu.tw yang@cl.ncu.edu.tw Abstract In this paper, we propose a three-step multilingual dependency parser, which generalizes an efficient parsing algorithm at first phase, a root parser and post- processor at the second and third stages. The main focus of our work is to provide an efficient parser that is practical to use with combining only lexical and part-of- speech features toward language inde- pendent parsing. The experimental results show that our method outperforms Malt- parser in 13 languages. We expect that such an efficient model is applicable for most languages. 1 Introduction The target of dependency parsing is to automati- cally recognize the head-modifier relationships between words in natural language sentences. Usu- ally, a dependency parser can construct a similar grammar tree with the dependency graph. In this year, CoNLL-X shared task (Buchholz et al., 2006) focuses on multilingual dependency parsing with- out taking the language-specific knowledge into account. The ultimate goal of this task is to design an ideal multilingual portable dependency parsing system. To accomplish the shared task, we present a very light-weight and efficient parsing model to the 13 distinct treebanks (Haji� et al., 2004; Simov et al., 2005; Simov and Osenova, 2003; Chen et al., 2003; Böhmová et al., 2003; Kromann 2003; van der Beek et al., 2002; Brants et al., 2002; Kawata and Bartels, 2000; Afonso et al., 2002; Džeroski et al., 2006; Civit and Martí 2002; Nivre et al., 2005; Oflazer et al., 2003; Atalay et al., 2003) with a three-step process, Nivre’s algorithm (Nivre, 2003), root parser, and post-processing. Our method is quite different from the conventional three-pass processing, which usually exhaustively processes the whole dataset three times, while our method favors examining the “un-parsed” tokens, which incrementally shrink. At the beginning, we slightly modify the original parsing algorithm (proposed by (Nivre, 2003)) to construct the initial dependency graph. A root parser is then used to recognize root words, which were not parsed during the previous step. At the third phase, the post-processor (which is another learner) recognizes the still un-parsed words. However, in this paper, we aim to build a multilingual portable parsing model without em- ploying deep language-specific knowledge, such as lemmatization, morphologic analyzer etc. Instead, we only make use of surface lexical and part-of- speech (POS) information. Combining these shal- low features, our parser achieves a satisfactory re- sult for most languages, especially Japanese. In the remainder of this paper, Section 2 describes the proposed parsing model, and Section 3 lists the experimental settings and results. Section 4 pre- sents the discussion and analysis of our parser …

Content truncated to 500 words