630-0101 8916-5 Tel: 0743-72-5246 {taku-ku,matsu}@is.aist-nara.ac.jp , Support Vector Machine (SVM) 5540 : , Support Vector Machine Japanese Dependency Structure Analysis based on Support Vector Machine Taku Kudoh Yuji Matsumoto Graduate School of Infomation Science, Nara Institute Science and Technology 8916-5 Takayama-cho, Ikoma-shi Nara 630-0101 Japan Tel: +81-743-72-5246 {taku-ku,matsu}@is.aist-nara.ac.jp This paper describes an analysis method of Japanese dependency structure based on Support Vector Machine (SVM). Conventional parsing techniques based on Machine Learning framework, such as Decision Tree and Maximum Entropy Model, cannot analyze sentence precisely, since features in these models must be selected carefully and it is difficult to train combination of features.  On the other hand, it is well-known that SVM achieves high generalization performance even with high dimensional input data. Furthermore, by introducing the kernel principle, SVM can carry out the training in high-dimensional spaces with smaller computational cost independent of their dimensionality. We apply SVM to Japanese dependency structure identification problem. Experimental results on Kyoto University corpus show that our system performs 88.66% even with small training data (5540 sentences). Keywords : Parsing, Dependency Structure Analysis, Machine Learning, Support Vector Machine , 3 SVM 4 5
Support Vector Machine
2
2.1
Optimal Hyperplane
, 2 x i ∈ R n , y i ∈ {+1, −1} (x i , y i ), . . . , (x i , y i ) X i n i [10] (ME) [11] . Yi (x i = (f 1 , f 2 , . . . , f n ) ∈ R n ) i (-1) (1), , x i ∈ R n y ∈ {±1} f : R n → {±1} Euclid n , SVM , ( w · x ) + b = 0 w ∈ R n , b ∈ R ( (1) ) , Support  Vector Machine (SVM) [1] [7] Boosting [2] ) ( SVM 2 (w · x i ) + b ≥ 1 if (y, € 1) ( w · x i ) + b ≤ −1 if (y, E −1) (2) (3) , Kernel , C , SVM . , (1) X i d(w,b;x;) | w · x i + b | d(w,b;x;) = || w || (2) (3) min d(w,b;x;) min d(w,b;x;) + Xi;yi= | w · x i + b | | w · x i + b | min min + || w || || w || x i ,y i × i , y i = 1 2 (2),(3) ( i = 1, . . . , l ) Y i [(w · x i ) + b] ≥ 1 (4) (4) [3] [5] [12] [13]. , , Support Vector Machine (SVM) . 2 SVM || w || 1 ,

2.2
Soft Margin
Soft  Margin

, Lagrange Kernel X1,X2 , ||w||² (7) ,2, . C C , :歌x 1歌,Ф K (8)歌(8) if (y, € 1) (w · x i ) + b ≥   1 − ξ i if (y, E −1) (w · x i ) + b ≥ −1 + ξ i K , Φ

SVM
K Kernel b; Kernel Dbest , CYK , Radial Basis Function (RBF) (11) d 3.2 SVM SVM 2 2 (f ij , Yij ) = {(f 12 , Y12), (f 23 , Y23), 1< i < m B, {b1,b2,...,bm} D {Dep(1),Dep(2),...,Dep(m–1)} ,Dep(i) b; , , D . . . , (f tn –1 m , Ym –1 m ) } f ij = {f 1, . . , f n } ∈ R n  yij ∈ { } P(Dep(i) = j | f' ij) P(Dep(i)= j | f ′ i j ) = D (12) f'ij , Dbcst = argmax P(D|B) D ²tanh(x) = 1+exp( , SVM (9) bi 2 [8]. [8] . 3 3.1 2 1. 1 , 2. B . (12) 3. k 3.3 , 2 ,2, 。 4 4.1 , [9] , 1 9 (11) C' (Version 2.0) 1 6 1 (5540 ), ) .  Kernel (1246 , 1 ,私はこの本を持っている女性を探している。 , 1 . - ? , . 2 , [11] . , , , 2 , 1 。 , 4.2 2 2 (A) , (A) k = 5, Kernel , SVM [6]. , a . 2へ2

4.5
Kernel
Kernel 3032 k = 5 , d d = 1, 2, 3, 4 4 , d = 4 , d = 1 , 2 4.3 3 5540 2 4.4 1 1172 86.52% , SVM 100% 
 
 . kernel SVM 1:
4: (3032    , k = 5) 3 4.6 [8]
5: (4318    , d = 3) 5540 2/3 , 88.3% , ME 3-10 。 5 7 1 4.8 Kernel , , 5540 4.7 C [11], 7958 [8]   , 87.2% ME 4 AlphaServer 8400 (617Mhz) , 5540 7 21 , 4318 SVM 5 , Support Vector Machine (SVM) , 5540 , 88.66% , SVM 3 [2] Y. Freund and Schapire. Experiments with a new Boosting algoritm. In 13th International Confer- ence on Machine Learning , pp. 148+, 1996. [3] T. Joachims. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. In European Conference on Machine Learning (ECML), 1998. [4] T. Joachims. Making Large-Scale SVM Learn- ing Practical. In Advances in Kernel Methods - Support Vector Learning. MIT Press, 1999. [5] T. Joachims.  Transductive Inference for Text Classification using Support Vector Machines. In International Conference on Machine Learning (ICML), 1999. [6] J. Platt. Probabilistic Outputs for Support Vec- tor Machines and Comparisons to Regularized Likelihood Methods. In Advances in Large Mar- gin Classifiers. MIT Press, 1999. [7] V. Vapnik. Statistical Learning Theory. Wiley- Interscience, 1998. [8] Vol. 6, No. 3, pp. 59–73, 1999. [9] 3 , pp. 115–118, 1997. [10] , Vol. 39, No. 12, p. 3117, 1998. [11] , SVM . ME NL128-5, pp. 31–38, 1998. [12] . Support Vector Ma- , chine NL128-24, pp. 173–180, 1998. [13] . . Support Vector Machine , Vol. 41, No. 4, p. 1113, 2000. [1] C. Cortes and V. Vapnik. Support Vector Net- works. Machine Learning , Vol. 20, pp. 273–297, 1995.