Dependency Parsing Based on Dynamic Local Optimization

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 211–215, New York City, June 2006. c⃝2006 Association for Computational Linguistics Dependency Parsing Based on Dynamic Local Optimization Ting Liu Jinshan Ma Huijia Zhu Sheng Li Information Retrieval Lab Harbin Institute of Technology Harbin, 150001, China {tliu,mjs,hjzhu,ls}@ir.hit.edu.cn Abstract This paper presents a deterministic pars- ing algorithm for projective dependency grammar. In a bottom-up way the al- gorithm finds the local optimum dynam- ically. A constraint procedure is made to use more structure information. The algorithm parses sentences in linear time and labeling is integrated with the parsing. This parser achieves 63.29% labeled at- tachment score on the average in CoNLL- X Shared Task. 1 Introduction Recently, dependency grammar has gained renewed attention in the parsing community. Good results have been achieved in some dependency parsers (Yamada and Matsumoto, 2003; Nivre et al., 2004). With the availability of many dependency treebanks (van der Beek et al., 2002; Hajiˇc et al., 2004; B¨ohmov´a et al., 2003; Kromann, 2003; Dˇzeroski et al., 2006) and more other treebanks which can be converted to dependency annotation (Brants et al., 2002; Nilsson et al., 2005; Chen et al., 2003; Kawata and Bartels, 2000), multi-lingual dependency pars- ing is proposed in CoNLL shared task (Buchholz et al., 2006). Many previous works focus on unlabeled parsing, in which exhaustive methods are often used (Eis- ner, 1996). Their global searching performs well in the unlabeled dependency parsing. But with the increase of parameters, efficiency has to be consid- ered in labeled dependency parsing. Thus determin- istic parsing was proposed as a robust and efficient method in recent years. Such method breaks the construction of dependency tree into a series of ac- tions. A classifier is often used to choose the most probable action to assemble the dependency tree. (Yamada and Matsumoto, 2003) defined three ac- tions and used a SVM classifier to choose one of them in a bottom-up way. The algorithm in (Nivre et al., 2004) is a blend of bottom-up and top-down processing. Its classifier is trained by memory-based learning. Deterministic parsing derives an analysis without redundancy or backtracking, and linear time can be achieved. But when searching the local optimum in the order of left-to-right, some wrong reduce may prevent next analysis with more possibility. (Jin et al., 2005) used a two-phase shift-reduce to decrease such errors, and improved the accuracy of long dis- tance dependencies. In this paper a deterministic parsing based on dy- namic local optimization is proposed. According to the probabilities of dependency arcs, the algorithm dynamically finds the one with the highest probabil- ities instead of dealing with the sentence in order. A procedure of constraint which can integrate more structure information is made to check the rational- ity of the reduce. Finally our results and error anal- ysis are presented. 2 Dependency Probabilities An example of Chinese dependency tree is showed in Figure1. The tree can be represented as a directed graph with nodes representing word tokens and arcs …

Content truncated to 500 words