Multilingual Deterministic Dependency Parsing Framework using Modified Finite Newton Method Support Vector Machines

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 1175–1181, Prague, June 2007. c⃝2007 Association for Computational Linguistics Multilingual Deterministic Dependency Parsing Framework using Modi- fied Finite Newton Method Support Vector Machines Yu-Chieh Wu Jie-Chi Yang Yue-Shi Lee Dept. of Computer Science and In- formation Engineering Graduate Institute of Network Learning Technology Dept. of Computer Science and Information Engineering National Central University National Central University Ming Chuan University Taoyuan, Taiwan Taoyuan, Taiwan Taoyuan, Taiwan bcbb@db.csie.ncu.edu.tw yang@cl.ncu.edu.tw lees@mcu.edu.tw Abstract In this paper, we present a three-step mul- tilingual dependency parser based on a deterministic shift-reduce parsing algo- rithm. Different from last year, we sepa- rate the root-parsing strategy as sequential labeling task and try to link the neighbor word dependences via a near neighbor parsing. The outputs of the root and neighbor parsers were encoded as features for the shift-reduce parser. In addition, the learners we used for the two parsers and the shift-reduce parser are quite different (conditional random fields and the modi- fied finite-Newton method support vector machines). We found that our method could benefit from the two-preprocessing stages. To speed up training, in this year, we employ the MFN-SVM (modified fi- nite-Newton method support vector ma- chines) which can be learned in linear time. The experimental results show that our method achieved the middle rank over the 23 teams. We expect that our method could be further improved via well-tuned parameter validations for different lan- guages. 1 Introduction The target of dependency parsing is to automatically recognize the head-modifier relationships between words in natural language sentences. Usually, a dependency parser can construct a similar grammar tree with the dependency graph. In this year, CoNLL-2007 shared task (Nivre et al., 2007) focuses on multilingual dependency parsing based on ten different languages (Hajic et al., 2004; Aduriz et al., 2003; Martí et al., 2007; Chen et al., 2003; Böhmova et al., 2003; Marcus et al., 1993; Johansson and Nugues, 2007; Prokopidis et al., 2005; Czendes et al., 2005; Montemagni et al., 2003; Oflazer et al., 2003) and domain adaptation for English (Marcus et al., 1993; Johansson and Nugues, 2007; Kulick et al., 2004; MacWhinney, 2000; Brown, 1973) without taking the language- specific knowledge into consideration. The ultimate goal of them is to design ideal multilingual and domain portable dependency parsing systems. To accomplish the multilingual and domain ad- aptation tasks, we present a three-pass parsing model based on a shift-reducing algorithm (Ya- mada and Matsumoto, 2003; Chang et al., 2006), namely, neighbor parsing, root relation parsing, and shift-reduce parsing. Our method favors exam- ining the “un-parsed” tokens, which incrementally shrink. At the beginning, the parsing direction is mainly determined by the amount of un-parsed tokens in the sentence with either forward or backward parse. In this step, the projective parsing method can be used to evaluate most of the non- projective Treebank datasets. Once the direction is determined, the pseudo-projectivize transformation algorithm (Nivre and Nilsson, 2005) converts most non-projective training data into projective and decodes the parsed text …

Content truncated to 500 words