Linear-Time Dependency Analysis for Japanese

Linear-Time Dependency Analysis for Japanese Manabu Sassano Fujitsu Laboratories, Ltd. 4-1-1, Kamikodanaka, Nakahara-ku, Kawasaki 211-8588, Japan sassano@jp.fujitsu.com Abstract We present a novel algorithm for Japanese dependency analysis. The algorithm allows us to analyze dependency structures of a sentence in linear-time while keeping a state-of-the-art accuracy. In this paper, we show a formal description of the algorithm and discuss it theoretically with respect to time complexity. In addition, we eval- uate its efficiency and performance empirically against the Kyoto University Corpus. The proposed algorithm with improved models for dependency yields the best ac- curacy in the previously published results on the Kyoto University Corpus. 1 Introduction Efficiency in parsing as well as accuracy is one of very important issues in natural languages process- ing. Although we often focus much on parsing ac- curacy, studies of its efficiency are also important, especially for practical NLP applications. Improv- ing efficiency without loss of accuracy is a really big challenge. The main purpose of this study is to propose an efficient algorithm to analyze dependency structures of head final languages such as Japanese and to prove its efficiency both theoretically and empiri- cally. In this paper, we present a novel efficient al- gorithm for Japanese dependency analysis. The al- gorithm allows us to analyze dependency structures of a sentence in linear-time while keeping a state- of-the-art accuracy. We show a formal description of the algorithm and discuss it theoretically with respect to time complexity. In addition to this, we evaluate its efficiency and performance empir- ically against the Kyoto University Corpus (Kuro- hashi and Nagao, 1998), which is a parsed corpus of news paper articles in Japanese. The remainder of the paper is organized as fol- lows. Section 2 describes the syntactic characteris- tics of Japanese and the typical sentence processing of Japanese. In Section 3 previous work of depen- dency analysis of Japanese as well as of English is briefly reviewed. After these introductory sections, our proposed algorithm is described in Section 4. Next, improved models for estimating dependency of two syntactic chunks called bunsetsus are pro- posed in Section 5. Section 6 describes experimen- tal results and discussion. Finally, in Section 7 we conclude this paper by summarizing our contribu- tions and pointing out some future directions. 2 Parsing Japanese 2.1 Syntactic Properties of Japanese The Japanese language is basically an SOV lan- guage. Word order is relatively free. In English the syntactic function of each word is represented with word order, while in Japanese postpositions repre- sent the syntactic function of each word. For ex- ample, one or more postpositions following a noun play a similar role to declension of nouns in Ger- man, which indicates a grammatical case. Based on such properties, a bunsetsu1 was de- vised and has been used to analyze syntactically a sentence in Japanese. A bunsetsu consists of one or more content words followed by zero or more function words. By defining a bunsetsu like that, we can analyze a sentence in a similar way that …

Content truncated to 500 words