Japanese Dependency Structure Analysis Based on Support Vector Machines

Japanese Dependency Structure Analysis Based on Support Vector Machines Taku Kudo and Yuji Matsumoto Graduate School of Information Science, Nara Institute of Science and Technology {taku-ku, matsu}@is, aist-nara, ac. jp ..... ..-" r Abstract This paper presents a method of Japanese dependency structure analysis based on Sup-- port Vector Machines (SVMs). Conventional parsing techniques based on Machine Learn- ing framework, such as Decision Trees and Maximum Entropy Models, have difficulty in selecting useful features as well as find- ing appropriate combination of selected fea- tures. On the other hand, it is well-known that SVMs achieve high generalization per- formance even with input data of very high dimensional feature space. Furthermore, by introducing the Kernel principle, SVMs can carry out the training in high-dimensional • spaces with a smaller computational cost in- dependent of their dimensionality. We apply SVMs to Japanese dependency structure iden- tification problem. Experimental results on Kyoto University corpus show that our sys- tem achieves the accuracy of 89.09% even with small training data (7958 sentences). 1 Introduction Dependency structure analysis has been rec- ognized as a basic technique in Japanese sentence analysis, and a number of stud- ies have been proposed for years. Japanese dependency structure is usually defined in terms of the relationship between phrasal units called 'bunsetsu' segments (hereafter "chunks~). Generally, dependency structure analysis consists of two steps. In the first step, dependency matrix is constructed, in which each element corresponds to a pair of chunks and represents the probability of a de- pendency relation between them. The second step is to find the optimal combination of de- pendencies to form the entire sentence. In previous approaches, these probabilites of dependencies axe given by manually con- structed rules. However, rule-based ap- proaches have problems in coverage and con- sistency, since there are a number of features that affect the accuracy of the final results, and these features usually relate to one an- other. On the other hand, as large-scale tagged corpora have become available these days, a number of statistical parsing techniques which estimate the dependency probabilities using such tagged corpora have been devel- oped(Collins, 1996; Fujio and Matsumoto, 1998). These approaches have overcome the systems based on the rule-based approaches. Decision Trees(Haruno et al., 1998) and Max- imum Entropy models(Ratnaparkhi, 1997; Uchimoto et al., 1999; Charniak, 2000) have been applied to dependency or syntactic struc- ture analysis. However, these models require an appropriate feature selection in order to achieve a high performance. In addition, ac- quisition of an efficient combination of fea- tures is difficult in these models. In recent years, new statistical learning techniques such as Support Vector Machines (SVMs) (Cortes and Vapnik, 1995; Vap- nik, 1998) and Boosting(Freund and Schapire, 1996) are proposed. These techniques take a strategy that maximize the margin between critical examples and the separating hyper- plane. In particular, compared with other conventional statistical learning algorithms, SVMs achieve high generalization even with training data of a very high dimension. Fur- thermore, by optimizing the Kernel function, SVMs can handle …

Content truncated to 500 words