Japanese Dependency Parsing Using a Tournament Model

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 361–368 Manchester, August 2008 Japanese Dependency Parsing Using a Tournament Model Masakazu Iwatate and Masayuki Asahara and Yuji Matsumoto Nara Institute of Science and Technology, Japan 8916-5, Takayama, Ikoma, Nara, Japan, 630-0192 {masakazu-i, masayu-a, matsu}@is.naist.jp Abstract In Japanese dependency parsing, Kudo’s relative preference-based method (Kudo and Matsumoto, 2005) outperforms both deterministic and probabilistic CKY-based parsing methods. In Kudo’s method, for each dependent word (or chunk) a log- linear model estimates relative preference of all other candidate words (or chunks) for being as its head. This cannot be consid- ered in the deterministic parsing methods. We propose an algorithm based on a tour- nament model, in which the relative pref- erences are directly modeled by one-on- one games in a step-ladder tournament. In an evaluation experiment with Kyoto Text Corpus Version 4.0, the proposed method outperforms previous approaches, includ- ing the relative preference-based method. 1 Introduction The shared tasks of multi-lingual dependency pars- ing took place at CoNLL-2006 (Buchholz and Marsi, 2006) and CoNLL-2007 (Nivre et al., 2007). Many language-independent parsing al- gorithms were proposed there. The algorithms need to adapt to various dependency structure constraints according to target languages: projec- tive vs. non-projective, head-initial vs. head-final, and single-rooted vs. multi-rooted. Eisner (1996) proposed a CKY-like O(n3) algorithm. Yamada and Matsumoto (2003) proposed a shift-reduce- like O(n2) deterministic algorithm. Nivre et al. (2003; 2004) also proposed a shift-reduce-like c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. 人だ。 hito-da. (man .) 読まない yomanai (doesn’t read) 本を hon-wo (books) (a) “He is a man who doesn’t read books.” 読まない。 yomanai. (doesn’t read .) 本を hon-wo (books) 彼は kare-wa (He) (b) “He doesn’t read books.” 彼は kare-wa (He) Figure 1: Examples of Japanese sentences. O(n) deterministic algorithm for projective lan- guages. The model is enhanced for non-projective languages by Nivre and Nilsson (2005). McDon- ald et al. (2005) proposed a method based on search of maximum spanning trees employing the Chu-Liu-Edmonds algorithm (hereafter “CLE al- gorithm”) (Chu and Liu, 1965; Edmonds, 1967). Most Japanese dependency parsers are based on bunsetsu units, which are similar concept to En- glish base phrases. The constraints in Japanese dependency structure are stronger than those in other languages. Japanese dependency structures have the following constraints: head-final, single- head, single-rooted, connected, acyclic and projec- tive. Figure 1 shows examples of Japanese sen- tences and their dependency structures. Each box represents a bunsetsu. A dependency relation is represented by an edge from a dependent to its head. Though sentence (a) is similar to sentence (b), the syntactic structures of these two are differ- ent, especially because “kare-wa” directly depends on “yomanai” in (b) but not in (a). In dependency parsing of Japanese, determin- istic algorithms outperform probabilistic CKY methods. Kudo and Matsumoto (2002) applied the 361 cascaded chunking algorithm (hereafter “CC al- gorithm”) to Japanese dependency parsing. Ya- mada’s method (Yamada and Matsumoto, 2003) employed a similar algorithm. Sassano (2004) …

Content truncated to 500 words