i †す630-0192 E-mail: †{taku-ku,matsu}@is.aist-nara.ac.jp 8916-5 , Support Vector Machine . Kernel Kernel , Kernel Power Set Kernel , Kernel 30-280 Support Vector Machine, Kernel , Power Set Kernel, Data Mining Power Set Kernel for Feature Combination: Data Mining approach for its fast classifiers Taku KUDO † and Yuji MATSUMOTO† † Graduate School of Information Science,Nara Institute of Science and Technology 8916-5, Takayama-Cho, Ikoma-shi Nara, 630-0192 Japan E-mail: †{taku-ku,matsu}@is.aist-nara.ac.jp Abstract The kernel method (e.g., Support Vector Machines) attracts a great deal of atten- tion recently. The merit of the kernel method is that the effective feature combination , which has been manually selected in the previous approaches, is implicitly expanded without loss of generality and computational cost. However, the kernel-based approach is usually too slow to classify large-scale test data. In this paper, we fist formulate a Power Set Kernel which gives a dot product of two sets. Then, we extend the Basket Mining algorithm to convert a kernel-based classifier into a simple and fast linear classifier. Experimental results on Japanese Word Segmentation and Japanese Dependency Parsing show that our new classifier is about 30-280 times faster than the standard kernel-based classifier. Key words   Support Vector Machines, Kernel Method, Power Set Kernel, Data Mining 1. [9],
, Support  Vector  Machine [13] Kernel , SVM , Kernel .  Kernel SVM SVM φ(x) · φ(x') , RH , SVM , Kernel , ) . Kernel , Power Set Kernel Kernel Kernel . .         , Power Set Kernel , Kernel PSKI, PSKE 2 , , , Kernel , PSKI 3-12  , PSKE 30-280 2.   Kernel Method (x1,y1),...,(xL,yL)      x i ∈ R N , yi ∈ {+1,−1} . SVM , Yシ   , . , SVM +1 , -1 y j α j φ ( x j ) · φ ( x ) + b y = sgr (1) N ≪ H ) αέ, b ∈ R, 0 ≤ α j ≤ C 2 , R H , H    , N . Kernel SVM (1)        , , φ(x j ) · φ(x) , α , RH K(x 1 , x 2 ) = φ(x 1 ) · φ(x 2 ) .  Kernel Kernel (1) y j α j K (x j , x) + b ) (2) (2) , SVM , Kernel ". Kernel String  Kernel [10], Tree  Kernel [3], [6], Deffusion  Kernel [7] 3. Power Set Kernel x    , . F = {1,2,...,N} , X j (j = {1,2,...,L})    , F (X j ∈ F).        ,      X j   , x j = {x j1,x j2,...,x jN } ( 2 x z ε = 0). i ∈ X j      , x j i = 1, . Kernel φ , R N RH ( SVM Kernel Kernel , Power Set Kernel (PSK) 2 dition) Kernel (Mercer's con-や1 1 ( ) 1    Power Set   P(X)      , X 1  P(X) = {¢, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} 2    Power Set Kernel K(X,Y) X, Y Kernel K(X,Y) Power Set Kernel
rび. , Cr PSK , Kernel 2      X = {a,b,c}, Y = {a,b,d} c 0 = 1, c 1 = 2, c 2 = 4, c 3 = 1 K(X,Y) = 1 · 1 + 2 · 2 + 4 · 1 + 1 · 0 = 9 3.1   Power Set Kernel 1     d K(X,Y) = |X ∩ Y| d    , Power Set Kernel       . |X ∩ Y | q , K(X,Y) = g(|X ∩ Y |)   , Power Set Kernel . 2  K(X,Y) = g(|X ∩ Y |)    ,
4    Quasi-RBF Kernel X,Y            , RBF Kernel ( α ∈ R + ） , K(X,Y) = exp(−α(|X|² + |Y|² − 2|X ∩ Y|)) function  PSKI_classify(X) r = 0 # foreach i ∈ 'X foreach j ∈ h(i) rj = rj + 1 end end result = b # foreach j ∈ (1 .. L ) result += y j α j · g(r j ) end return sgn(result) 1 PSKI = exp(−a|X|²)exp(−s|Y|²)exp(2a|X ∩ Y|) |X| = |Y| = N(      ) ( , RBF Kernel   ,         2 ) , PSK                    , RBF Kernel    , c, = exp(−αN 2 ) ∑ { , (2s) † τ(l,r) 4.   Power Set Kernel 2 g    ,
L O(|X| · L) 4.1   PSKI (Inverted Representation) X i ∈ X , (1) PSKI h(i)   ,          i (  | h ( i ) | ). PSKI   , B 4.2   PSKE (Expanded Representation) 4. 2. 1 PSK Cr
w(s)= y j α 3 c | s | I ( s ∈ P ( X j )) { = 1
0 1 ,      (6)
(6) . PSKE , O(|P(X)|) L . S | w(s)| s     , , 4.2.2 PSKE w = {w(s1), w(s2), . . . , w(s1p(f)[)} . 2 Kernel C|s|/Cmax . CmaxYjQj X j , CmazYjQj 2 2 Kernel w' w w 3 w = {w(s1),w(s2),...,w(s(|P(F)|} σneg < w(s) < σpos (σneg < 0, σpos > 0) , w(s) = 0 .       , w' . w w' , 0 (σ neg, σ pos) . w 4. (y1α1,x1),...,(ylαl,xl), , w(s) ≥ CO, C1, . . . w(s) ≥ σ neg w(s) Kernel w n , d , cr = 0 (r > d) , d F  , Fd Kernel , ) ori [1] (5) (4) ), d kernel , d Cr PSKE , Cr ,  Cr Cmaz (= max({c1,c2,...,cn})) , Cmaz s . 2 ", kernel [4].             , 3 4 。 −∞ − ∞ ( y s ＜ 0) ( y 5 > 0), Opos Tneg 。 Opos, Oneg (bias) σ(> 0) Opos, Oneg Tpos = σ oneg =一σ Opos s    , s Ω = {{s,w(s)} . TRIE w(s) . TRIE PSKE (7) TRIE 4 (6) . w(s) . Double-Array [2], [8] ξ(= {1,2,3,4})
(JWS), (JDP) [12], [15], [16] kernel , 3 RBF Kernel , , , PrefixSpan [11] (97.94%→97.83%) . 1 , , XEON 2.4GHz 4.0Gbyte Memory 6. Linux , C++ . ,      , Power Set Kernel 5.2 0.1 2,3   , PSKI       PSKE σ 0.0001 s. | Ω | . PSKI   , JWS      1.7    (0.85 → 0.49), JDP 12     (0.28 → 0.022), ） JWP . JDP     , B (|h(i)| Set Kernel PSKE 2
, PSKI 3-12  , PSKE       30-280 Kernel (Tree Kernel, String Kernel) PSKE  , JWP      280    (σ = 0.005, 0.85 /   → 0.0033  / ), JDP     30   (σ = 0.0005, 0.28   /   → 0.0097   /   )
5.3 , PSKE              , PSKB , JWS , JWD 232     (JWD)/826     (JWP)     ,  e . , [Ω]
x = {x1,x2,...,xN}, y = {y1,y2,...,yN} (  1, xj,yj  , 0 , .
. JWD σ=0.0005 , σ=0.005, JDP , ,        , . 5 , 1 6  T(d,r) =
x j ∈ {0,1} , r      (r = {0,1,...,d}) , (x1y1x2y2 --x1yr)
1 5.1 5. 2
Rakesh Agrawal and Ramakrishnan Srikant. [1] Fast algorithms for mining association rules. In Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo, editors, Proc. 20th Int. Conf. Very Large Data Bases, VLDB, pp. 487–499. Mor- gan Kaufmann, 12–15  1994. Junichi Aoe.  An efficient digital search algo- [2] rithm by using a double-array structure. IEEE Transactions on Software Engineering , Vol. 15, No. 9, 1989. Michael Collins and Nigel Duffy.  Convolution [3] kernels for natural language. In NIPS, 2001. Hideki Isozaki and Hideto Kazawa. Effi- [4] cient support vector classifiers for named entity recognition. In Proceedings of COLING-2002 , 2002. Thorsten Joachims. Text categorization with [5] support vector machines: learning with many relevant features. In Proceedings of ECML-98, 10th European Conference on Machine Learn- ing, No. 1398, pp. 137–142, Chemnitz, DE, 1998. Springer Verlag, Heidelberg, DE. Hisashi Kashima and Teruo Koyanagi. Svm [6] kernels for semi-structured data. In Proc. 19th Int. Conf. Machine Learning , 2002. Diffu- Risi Imre Kondor and Jon Lafferty. [7] sion kernels on graphs and other discrete in- put spaces. In Proc. 19th Int. Conf. Machine Learning , 2002. [8] Taku Kudo.  Darts:  Double-ARray  Trie  Sys- tem. Taku Kudo and Yuji Matsumoto.  Chunking [9] with support vector machines. In Proceedings of the Second Meeting of the NAACL , 2001. Huma Lodhi, Craig Saunders, John Shawe- [10] Taylor, Nello Cristianini, and Chris Watkins. Text classification using string kernels. Journal of Machine Learning Research , Vol. 2, , 2002. [11]  Jian Pei, Jiawei Han, and et al.  Prefixspan: Mining sequential patterns by prefix-projected growth. In Proc. of International Conference of Data Engineering, pp. 215–224, 2001. [12] Manabu Sassano.  An empirical study of ac- tive learning with support vector machines for japanese word segmentation. In Proceedings of the Second Meeting of the ACL , pp. 505–512, 2002. [13] Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer, 1995. . Support vector ma- [14] . chine , Vol. 43, No. 1, pp. 44–53, 2002. [15]
No. 6, pp. 1834–1842, 2002.