3350 Table 1 1 Examples of top similar words by the proposed method. 1 Fig. 1 An example of context profiles. c(w i,f ) p(f w i) w i f Pointwise Mutua

Size: px

Start display at page:

Download "3350 Table 1 1 Examples of top similar words by the proposed method. 1 Fig. 1 An example of context profiles. c(w i,f ) p(f w i) w i f Pointwise Mutua"

たけなりながおか
5 years ago
Views:

1 Vol. 52 No (Dec. 2011) 1 1 2, 3, Dirichlet Bhattacharyya A Bayesian Similarity Measure for Large-scale Calculation of Distributional Similarities Jun ichi Kazama, 1 Stijn De Saeger, 1 Kow Kuroda, 2 Masai Murata 5 and Kentaro Torisawa 1 Existing word similarity measures are not robust to data sparseness since they rely only on the point estimation of words context profiles obtained from a limited amount of data. This paper proposes a Bayesian method for robust distributional word similarities. The method uses a distribution of context profiles obtained by Bayesian estimation and taes the expectation of a base similarity measure under that distribution. When the context profiles are multinomial distributions, the priors are Dirichlet, and the base measure is the Bhattacharyya coefficient, we can derive an analytical form that allows efficient calculation. For the tas of word similarity estimation for a large-scale vocabulary in Japanese, we show that the proposed measure gives better accuracies than other well-nown similarity measures ) 28) 26) 12) 7) 10),13),17) sim(w 1,w 2)=g(v(w 1),v(w 2)). (1) v(w i) w i w i g 2 1 f w i v (w i) 1 National Institute of Information and Communications Technology 2 Kyoto Institute of Technology 3 Kyoto University 4 Comprehensive Research Organization, Waseda University 5 Graduate School of Engineering, Tottori University 3349 c 2011 Information Processing Society of Japan

2 3350 Table 1 1 Examples of top similar words by the proposed method. 1 Fig. 1 An example of context profiles. c(w i,f ) p(f w i) w i f Pointwise Mutual Information; PMI 1 1 g Jaccard Jensen-Shannon g v(w i) 1 v(w i) p(f w 1) p(f w 2) w 1 w 2 w 0 sim(w 0,w 1) >sim(w 0,w 2) 100 regularization 2) 4) 18),24) v(w i) p(v(w i)) sim b (w 1,w 2)=E[sim(w 1,w 2)] {p(v(w1 )),p(v(w 2 ))} (2) = E[g(v(w 1),v(w 2))] {p(v(w1 )),p(v(w 2 ))}. p(v(w i)) (2)

3 3351 Bhattacharyya 1) (2) 1 Web 100 Bhattacharyya Jensen- Shannon 2 Bhattacharyya 3 Bhattacharyya D φ p(d φ) φ =argmax φ p(d φ) w i f p(f w i) p(f w i)=c(w i,f )/ c(w i,f ). (3) D φ p(φ D) p(φ D) = p(d φ)p(φ). (4) p(d) p(φ) φ φ φ =1 K 1 w i φ = p(f w i) Dir(φ α) Dir(φ α) = Γ( K =1 α ) K =1 Γ(α ) K =1 φ α 1. (5) Γ( ) α = {α } α > 0 p(φ D) p(φ D) =Dir(φ {α + c()}). (6) c() D p(f w i) c() =c(w i,f ) 2.2 Bhattacharyya Jensen-Shannon JS 6),9) JS JS(p 1 p 2)= 1 2 (KL(p1 pavg)+kl(p2 pavg)). p avg = p 1+p 2 p 2 1 p 2 KL( ) Kullbac-Leibler KL K KL(p 1 p 2)= p 1 log p 1. (7) p 2 =1 JS KL 2 JS (2) KL(p 1 p 2) p 1 p 2 0

4 Bhattacharyya 1) BC K BC(p 1,p 2)= p1 p 2. (8) =1 BC JS BC JS 3. BC (2) 2 Dir(p 1 α) Dir(p 2 β) BC b (p 1,p 2)=E[BC(p 1,p 2)] {Dir(p1 α ),Dir(p 2 β )} = Dir(p 1 α)dir(p 2 β)bc(p 1,p 2)dp 1dp 2. (9) BC b (p 1,p 2)= Γ(α 0)Γ(β 0) Γ(α )Γ(β ) K =1 Γ(α + 1 )Γ(β ) 2. (10) Γ(α )Γ(β ) α 0 = α β 0 = β (6) Dir(p 1 {α + c(w 1,f )}) Dir(p 1 {β + c(w 2,f )}) 2 α α + c(w 1,f ) β β + c(w 2,f ) α β c(w i,f ) 1 p(v(w i)) v(w i) BC b (w 1,w 2)= Γ(α 0 + a 0)Γ(β 0 + b 0) K Γ(α 0+a 0+ 1 )Γ(β0+b0+ 1 ) 2 2 =1 Γ(α + c(w 1,f )+ 1 2 )Γ(β + c(w 2,f )+ 1 2 ) Γ(α + c(w 1,f ))Γ(β + c(w 2,f )) α 0 = α β 0 = β a 0 = c(w1,f ) b 0 = c(w2,f ) Bhattacharyya BC b α = α α = β w 1 w 2 BC b w 0 w 1 w 2 K =2 c(w 0,f 1)=10 c(w 0,f 2)=20 c(w 1,f 1)=1 c(w 1,f 1)=2 c(w 2,f 1) = 100 c(w 2,f 2) = (1/3, 2/3) α =1.0 BC b BC b (w 0,w 1)= BC b (w 0,w 2)= BC b (w 0,w 1) < BC b (w 0,w 2) w 0 1 BC b (w 0,w 0)= sim(w i,w i) BC b (w i,w i) 1 sim b (w i,w i)=e[sim(w i,w i)] {p(v(wi ))} =1 4. (11) (11) 170 (11)

5 3353 log lnγ(x) log GNU Scientific Library GSL log GSL log Lanczos (11) c(w i,f ) c(w i,f ) > 0 c(w i,f ) log c(w i,f )=0 1 1, 2 w i (A) A[w i]=lnγ(α 0 + a 0) lnγ(α 0 + a ) 2 (B) B[w i][] =lnγ(α + c(w i,f )+ 1 ) lnγ(α 2 + c(w i,f )) c(w i,f ) > 0 (C) C[w i][] = exp(2(lnγ(α + 1 ) lnγ(α 2 )))) + exp(lnγ(α + c(w i,f )+ 1 ) 2 lnγ(α + c(w i,f )) + lnγ(α + 1 ) lnγ(α 2 )) c(w i,f ) > 0 (D) D[] = exp(2(lnγ(α + 1 ) lnγ(α 2 ))). BC b (w 1,w 2) c(w i,f ) D[] V c(w1,f ) c(w 2,f ) 3 c(w 1,f ) > 0 c(w 2,f )=0 (C) V c(w 1,f ) > 0 c(w 2,f ) > 0 V = V D[]+exp(B[w 1][]+ B[w 2][]) V (A) exp(a[w 1]+A[w 2]+ ln(v )) BC b 100 c(w i,f ) 14),20),21) w i c(w i,f ) L 4 c(w i,f ) M 1 N 16CPU 100 L = M =1,600 N = Jensen-Shannon 57 BC b 100 Jensen-Shannon 26 GB BC b 34 GB (11) 1 w 1 w 2 2 (C) (D) exp exp L

6 ) {,, } {, } {, } {, } T MP@T Mean Average Precision; MAP P@T T AP P@T = 1 T δ(w i ans), T AP = 1 R i=1 N δ(w i ans)p@i. i=1 δ(w i ans) w i 1 0 N R MP@T MAP ),15) Web 23) 1 n w r (n, w, r ) w, r n f (,, ) n w (,, ) n 1 n 2 (n 1, n 2, ) (n, w, r,c) Web 4.7 3,100 2,200 f A B EDR V3.0 5) 304, , A B A B A B C Murata 19) 12, {a, b, c} 2 {a, d, e} a 1 2 a a 1 {b, c} 2 {d, e} {b, c, d, e}

7 A 115 3,740 B 65 3,675 C 1,700 8, Bhattacharyya BC b JS p(f w 1) p(f w 2) Jensen-Shannon 7),9) PMI-cos PMI (w i,f )=log p(w i,f ) p(w i )p(f ) wi f PMI 20),21), 1 Cls-JS Hagiwara 11) Kazama 14) p(w i,f )= p(wi c)p(f c c)p(c) EM p(c w 1) p(c w 2) Jensen- Shannon EM EM s1 s2 2 s1+s2 Kazama 14) s1 s2 2, EM EM 1 Cls-BC Jensen-Shannon Bhattacharyya 1 Pantel 21) PMI BC p(f w 1) p(f w 2) Bhattacharyya 1) BC b BC a p(f w 1) p(f w 2) Bhattacharyya p(f w i) c(w i,f ) α 0 α 1 (11) BC a c(w i,f ) log(c(w i,f )) ),25) Web 14),25) 500 BC b BC a α A MAP MP BC b BC a 2 X log α Y MAP 2 MP α MAP MP MAP α MP α = BC b BC MAP 6.6% MP@1 14.7% BC a BC BC b 2 Cls-JS Cls-BC 2 {α } α = α

8 3356 Measure 2 A Table 2 Performance on siblings (Set A). JS PMI-cos Cls-JS (s1) Cls-JS (s2) Cls-JS (s1+s2) Cls-BC (s1) Cls-BC (s2) Cls-BC (s1+s2) BC BC b (0.0002) BC b (0.0016) BC b (0.0032) BC a (0.0016) BC a (0.0362) BC a (0.1) without log(c(w i,f )) + 1 modification JS PMI-cos BC BC Cls-BC JS PMI-cos Cls-JS Bhattacharyya 2 PMI-cos JS BC 1 A α B 3 A α = B α 1 A 2 MAP α BC Bayes BC b Absolute Discounting BC a MP Fig. 2 (Upper) Tuning of α for MAP. The dashed horizontal line indicates the score of BC. Bayes corresponds to BC b and Absolute Discounting to BC a. (Bottom) Corresponding MPs. C 4 A B Cls-JS Cls-BC BC b BC MP@1 7.5% MAP MAP MP ,700

9 B Table 3 Performance on siblings (Set B). Table 4 4 C Performance on closed-sets (Set C). Measure JS PMI-cos Cls-JS (s1+s2) Cls-BC (s1+s2) BC BC b (0.0002) BC b (0.0016) BC b (0.0032) BC a (0.0016) BC a (0.0362) BC a (0.01) MAP L = M =3,600 N =2,000 MAP MP C Cls-JS Cls-BC EM 15) 100 2,000 24CPU GB 1CPU BC b BC MP@20 MP@20 MP@ Measure JS PMI-cos Cls-JS (s1) Cls-JS (s2) Cls-JS (s1+s2) Cls-BC (s1) Cls-BC (s2) Cls-BC (s1+s2) BC BC b (0.0004) BC b (0.0008) BC b (0.0016) BC b (0.0032) L = M =3,200 and N =2,000 JS PMI-cos Cls-JS (s1+s2) BC BC b (0.0004) BC b (0.0008) BC b (0.0016) BC b (0.0032) MP@20 Table 5 The numbers of improved, unchanged, and degraded words in terms of MP@20 for each evaluation set. # improved # unchanged # degraded Set A 755 2, Set B 643 2, Set C 3,153 3,962 1, BC b BC MP@20 BC b 40,000

10 L M Table 7 Effect of L and M in approximation. L(= M) ,600 3,200 6, , , , , , , MAP BC b (0.0016) BC MP@20 40,000 A B C 0 ID Fig. 3 Averaged Differences of MP@20 between BC b (0.0016) and BC within each 40,000-word ran range (Left: Set A. Middle: Set B. Right: Set C). 6 (A) (B) (C) 0 Table 6 Statistics on word rans. (A): Avg. word rans of answers. (B): Avg. word rans of system outputs. (C): Avg. word rans of correct system outputs. Set A Set C (A) 238,483 (A) 255,248 (B) (C) (B)/(C) (B) (C) (B)/(C) Cls-JS (s1+s2) 282, , , , JS 183, , , , BC 162,758 98, , , BC b (0.0016) 55,915 54, , , BC BC b BC BC JS JS Cls-JS Cls-JS 6 (B) 6 (A) (B) 6 (C) 6 (B)/(C) Cls-JS JS BC BC b BC b 4 L M L = M =1,600 L = M A BC b 7 w i f L M L = M =1,600 20%

11 Bhattacharyya Kneser-Ney 16) 18),24) p(f w i) { p(f w i)= c(w i,f ) Γ(α0 +a a 0 p(f w 0 )Γ(α +c(w i,f )+ i)= ) Γ(α 0 +a )Γ(α +c(w i,f ))} Bhattacharyya ),24) α = α α 6.3 Bhattacharyya Jensen-Shannon 1 α PMI 2 μ(w1,f )μ(w 2,f ) p 1 p 2 Bhattacharyya μ(w i,f ) p i μ(w 1,f ) μ(w 2,f ) BC b BC b BC d (p 1,p 2)= K =1 pd 1 p d 2 d >0 BCb d (w 1,w 2)= Γ(α 0 + a 0)Γ(β 0 + b 0) K Γ(α 0 + a 0 + d)γ(β 0 + b 0 + d) =1 Γ(α + c(w 1,f )+d)γ(β + c(w 2,f )+d). Γ(α + c(w 1,f ))Γ(β + c(w 2,f )) Rauber 22) Bhattacharyya Γ(α0)Γ(β 0) BC(Dir(φ α), Dir(φ β)) = Γ(α ) Γ(β ) Γ((α + β )/2) K (α + β )). (12) BC b (6) (12) (12) Tsuda 27) x X h H z =(x, h) K z(z, z ) h K(z, z )= p(h x)p(h x )K z(z, z ) (13) h H h H Tsuda x h HMM Γ( 1 2

12 Bhattacharyya Bhattacharyya Jensen-Shannon PMI Bhattacharyya 1) Bhattacharyya, A.: On a measure of divergence between two statistical populations defined by their probability distributions, Bull. Calcutta Math. Soc., Vol.49, pp (1943). 2) Chen, S.F. and Goodman, J.: An empirical study of smoothing techniques for language modeling (1998). TR-10-98, Computer Science Group, Harvard University. 3) Chen, S.F. and Rosenfeld, R.: A Survey of Smoothing Techniques for ME Models, IEEE Trans. Speech and Audio Processing, Vol.8, No.1, pp (2000). 4) Cortes, C. and Vapni, V.: Support Vector Networs, Machine Learning, Vol.20, pp (1995). 5) CRL: EDR Electronic Dictionary Version 2.0 Technical GUIDE (2002). Communications Research Laboratory (CRL). 6) Dagan, I., Lee, L. and Pereira, F.: Similarity-based Methods for Word Sense Disambiguation, Proc. ACL 97 (1997). 7) Dagan, I., Lee, L. and Pereira, F.: Similarity-Based Models of Word Cooccurrence Probabilities, Machine Learning, Vol.34, No.1-3, pp (1999). 8) Dagan, I., Marcus, S. and Marovitch, S.: Contextual Word Similarity and Estimation from Sparse Data, Computer, Speech and Language, Vol.9, pp (1995). 9) Dagan, I., Pereira, F. and Lee, L.: Similarity-based Estimation of Word Cooccurrence Probabilities, Proc. ACL 94 (1994). 10) Grefenstette, G.: Explorations In Automatic Thesaurus Discovery, KluwerAcademic Publishers (1994). 11) Hagiwara, M., Ogawa, Y. and Toyama, K.: PLSI Utilization for Automatic Thesaurus Construction, Proc. IJCNLP 2005 (2005). 12) Harris, Z.: Distributional Structure, Word, pp (1954). 13) Hindle, D.: NOUN CLASSIFICATION FROM PREDICATE-ARGUMENT STRUCTURES, Proc. ACL-90, pp (1990). 14) Kazama, J., De Saeger, S., Torisawa, K. and Murata, M.: Generating a large-scale analogy list using a probabilistic clustering based on noun-verb dependency profiles, Proc. 15th Annual Meeting of The Association for Natural Language Processing (in Japanese) (2009). 15) Kazama, J. and Torisawa, K.: Inducing Gazetteers for Named Entity Recognition by Large-scale Clustering of Dependency Relations, Proc. ACL-08: HLT (2008). 16) Kneser, R. and Ney, H.: Improved bacing-off for m-gram language modeling, Proc. ICASSP95 (1995). 17) Lin, D.: Automatic retrieval and clustering of similar words, Proc. COLING/ACL- 98, pp (1998). 18) Mochihashi, D., Yamada, T. and Ueda, N.: Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language Modeling, Proc. ACL-IJCNLP 2009, pp (2009). 19) Murata, M., Ma, Q., Shirado, T. and Isahara, H.: Database for Evaluating Extracted Terms and Tool for Visualizing the Terms, Proc. LREC 2004 Worshop: Computational and Computer-Assisted Terminology, pp.6 9 (2004). 20) Pantel, P., Crestan, E., Borovsy, A., Popescu, A.-M. and Vyas, V.: Web-Scale Distributional Similarity and Entity Set Expansion, Proc. EMNLP 2009, pp (2009). 21) Pantel, P. and Lin, D.: Discovering Word Senses from Text, Proc. 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp (2002). 22) Rauber, T.W., Braun, T. and Berns, K.: Probabilistic distance measures of the Dirichlet and Beta distributions, Pattern Recognition, Vol.41, pp (2008). 23) Shinzato, K., Shibata, T., Kawahara, D., Hashimoto, C. and Kurohashi, S.: Tsubai: An open search engine infrastructure for developing new information access, Proc. IJCNLP 2008 (2008). 24) Teh, Y.W.: A Hierarchical Bayesian Language Model Based On Pitman-Yor Processes, Proc. COLING-ACL 2006, pp (2006). 25) Terada, A., Yoshida, M. and Naagawa, H.: A Tool for Constructing a Synonym Dictionary using Context Information, IPSJ SIG Technical Report (in Japanese), pp (2004). 26) Tsuchida, M., De Saeger, S., Torisawa, K., Murata, M., Kazama, J., Kuroda, K. and Ohwada, H.: Large Scale Similarity-based Relation Expansion, Proc. IUCS

3361 2010 (2010). 27) Tsuda, K., Kin, T. and Asai, K.: Marginalized ernels for biological sequences, Bioinfomatics, Vol.18, No.suppl 1, pp.s268 S275 (2002). 28) Yamada, I., Torisawa, K., Kazama, J.

6 BCb d φ α 1 dφ = Γ(α ) = Z(α) 1. (14) Γ(α 0) BCb d (p 1,p 2) BCb d (p 1,p 2)= Dir(φ 1 α)dir(φ 2 β) φ d 1φ d 2 dφ 1 dφ 2 = Z(α)Z(β) l φ α l 1 1l m φ βm 1 2m φ d 1φ d 2 dφ 1 dφ 2.

13 (2010). 27) Tsuda, K., Kin, T. and Asai, K.: Marginalized ernels for biological sequences, Bioinfomatics, Vol.18, No.suppl 1, pp.s268 S275 (2002). 28) Yamada, I., Torisawa, K., Kazama, J., Kuroda, K., Murata, M., De Saeger, S., Bond, F. and Sumida, A.: Hypernym Discovery Based on Distributional Similarity and Hierarchical Structures, Proc. EMNLP 2009 (2009). 6 BCb d φ α 1 dφ = Γ(α ) = Z(α) 1. (14) Γ(α 0) BCb d (p 1,p 2) BCb d (p 1,p 2)= Dir(φ 1 α)dir(φ 2 β) φ d 1φ d 2 dφ 1 dφ 2 = Z(α)Z(β) l φ α l 1 1l m φ βm 1 2m φ d 1φ d 2 dφ 1 dφ 2. } {{ } A (14) A A = φ α l 1 dφ2 m = m φ βm 1 2m φ βm 1 2m [ φ d 2 φ d 2 Γ(α + d) l = Γ(α l) Γ(α 0 + d) φ α +d 1 1 l 1l dφ 1 Γ(α + d) ] Γ(α l l) dφ 2 Γ(α 0 + d) φ β +d 1 2 m φ βm 1 2m dφ2 Γ(α + d) = Γ(α l l) Γ(β + d) Γ(βm) m Γ(α 0 + d) Γ(β 0 + d) Γ(αl ) Γ(β m) Γ(α + d) Γ(β + d) =. Γ(α 0 + d)γ(β 0 + d) Γ(α ) Γ(β ) BC d b (p 1,p 2)= Γ(α 0)Γ(β 0) Γ(α 0 + d)γ(β 0 + d) K =1 Γ(α + d)γ(β + d). Γ(α )Γ(β ) ( ) ( ) NICT MASTAR

14 3362 MASTAR FIT2005 ACL ACL

21 Pitman-Yor Pitman- Yor [7] n -gram W w n-gram G Pitman-Yor P Y (d, θ, G 0 ) (1) G P Y (d, θ, G 0 ) (1) Pitman-Yor d, θ, G 0 d 0 d 1 θ Pitman-Yor G

21 Pitman-Yor Pitman- Yor [7] n -gram W w n-gram G Pitman-Yor P Y (d, θ, G 0 ) (1) G P Y (d, θ, G 0 ) (1) Pitman-Yor d, θ, G 0 d 0 d 1 θ Pitman-Yor G ol2013-nl-214 No6 1,a) 2,b) n-gram 1 M [1] (TG: Tree ubstitution Grammar) [2], [3] TG TG 1 2 a) ohno@ilabdoshishaacjp b) khatano@maildoshishaacjp [4], [5] [6] 2 Pitman-Yor 3 Pitman-Yor 1 21 Pitman-Yor