skeiji.final.dvi

Size: px

Start display at page:

Download "skeiji.final.dvi"

いぶきこやぎ
7 years ago
Views:

1 HTML HTML 1) HTML HTML 2) df idf 3) 4) : World Wide Web Automatic acquisition of hyponymy relations from HTML documents This paper describes an automatic acquisition method for hyponymy relations. Hyponymy relations play a crucial role in various natural language processing systems, and there have been many attempts to automatically acquire the relations from largescale corpora. Most of the existing acquisition methods rely on particular linguistic patterns, such as juxtapositions, which specify hyponymy relations. Our method, however, does not use such linguistic patterns. We try to acquire hyponymy relations from four different types of clues. The first is repetitions of HTML tags found in usual HTML documents on the WWW. The second is statistical measures such as df and idf, which are popular in IR literatures. The third is verb-noun cooccurrences found in normal corpora. The fourth is heuristic rules obtained through our experiments on a development set. KeyWords: Knowledge acquisition, Hypernym, Hyponym, Statistical Natural Language Processing, World Wide Web 1 hyponymy relation synonymy relation part-whole relation, School of Information Science, Japan Advanced Institute of Science and Technology 1

Most of the existing acquisition methods rely on particular linguistic patterns, such as juxtapositions, which specify hyponymy relations. Our method, however, does not use such linguistic patterns.

2 Vol. 1 No. 1 Jan. 1 WWW HTML Miller (Miller, Beckwith, Fellbaum, Gross, and Miller 1990) A B (hypernym) B A hyponym B is a (kind of) A 1 B A hyponym(a B) hyponym( ) hyponym( ) hyponym( ) (Mandala, Tokunaga, and Tanaka 1998). QA (Fleischman, Hovy, and Echihabi 2003) WWW HTML 1) 2) 3) HTML HTML lexico syntactic pattern HTML df idf 1 A concept represented by a lexical item L 0 is said to be a hyponym of the consepct represented by a lexical item L 1 if native speakers of English accept sentences consutructed from the frame An L 0 is a (kind of ) L 1. 2

hyponym( ) hyponym( ) hyponym( ) (Mandala, Tokunaga, and Tanaka 1998).

3 HTML 4 WWW 87 HTML 9 2,000 2,000 14,000, 3.6 % % 5% % 10 % 1, % (Hearst 1992; Caraballo 1999; 2001; Morin and Jacquemin 2003; Fleischman et al. 2003;,, 2003) Hearst such as such NP as {NP, }* {(or and)} NP Hearst such as... works by such authors as Herrick, Goldsmith, and Shakespeare. such as hyponym( author Herrick ) hyponym( author Goldsmith ) hyponym( author Shakespeare ). ( 2001) ( 2003) , % 3

2003;,, 2003) Hearst such as such NP as {NP, }* {(or and)} NP Hearst such as.

4 Vol. 1 No. 1 Jan. 1 1 A B A B A B * A, B A B A B * A B * A B A B A B * A B * X ( 2001) % 85% % 81.3% HTML ( 2003) 4

5 HTML DVD-RW PC 1 HTML HTML 2 df idf WWW HTML 1 1 HTML 1 2 {DVD RW } { } 1 1 HTML 2 df idf WWW 5

6 Vol. 1 No. 1 Jan DVD RW WWW. DVD RW DVD RW DVD RW ( 1) 1 WWW HTML HTML 3 3 HTML <A> <FONT> <TD> <B> 6

7 HTML <UL> <LI> </LI> <UL> <LI>DVD-RW</LI> <LI> </LI> <LI> </LI> <LI> </LI> </UL> <LI>PC </LI> <UL> <LI> </LI> <LI> </LI> <LI> </LI> </UL> </UL> (a) (UL 1 LI 1 ) (UL 1 UL 2 LI 1 DVD RW) (UL 1 UL 2 LI 2 ) (UL 1 UL 2 LI 3 ) (UL 1 UL 2 LI 4 ) (UL 1 LI 3 PC ) (UL 1 UL 4 LI 1 ) (UL 1 UL 4 LI 2 ) (UL 1 UL 4 LI 3 ) (c) (UL LI ) (UL UL LI DVD RW) (UL UL LI ) (UL UL LI ) (UL UL LI ) (UL LI PC ) (UL UL LI ) (UL UL LI ) (UL UL LI ) (b) (UL 1 LI ) (UL 1 UL 2 LI DVD RW) (UL 1 UL 2 LI ) (UL 1 UL 2 LI ) (UL 1 UL 2 LI ) (UL 1 LI PC ) (UL 1 UL 4 LI ) (UL 1 UL 4 LI ) (UL 1 UL 4 LI ) (d) 2 HTML 1 HTML HTML 3 1 <OPTION> <LI> <STRONG> 7

(c) (UL LI ) (UL UL LI DVD RW) (UL UL LI ) (UL UL LI ) (UL UL LI ) (UL LI PC ) (UL UL LI ) (UL UL LI ) (UL UL LI ) (b) (UL 1 LI ) (UL 1 UL 2 LI DVD RW) (UL

8 Vol. 1 No. 1 Jan. 1 2(a) HTML 4 HTML HTML HTML 2(a) <LI> </LI> <UL> </UL> (UL LI ) 2(a) HTML 2(b) HTML 2(b) {DVD RW } { PC } 2 PC 2(c) N 2(c) N =1 2(d) {DVD RW } { } { PC } N =1 4 1 HTML 8

9 HTML 3.3 df idf ( 2) 1 HTML df idf HTML HTML C G C LD(C) LD(C) 5 N 2 h(c) h(c) =argmax n N {df (n, LD(C)) idf(n, G)} idf(n, G) = log G df (n, G) df(n, D) D n G G 3 DVD RW df (n, LD(C)) idf(n, G) 5 B 9

1 2 1 C G C LD(C) LD(C) 5 N 2 h(c) h(c) =argmax n N {df

10 Vol. 1 No. 1 Jan. 1 df(n, D) D n tf(n, D) tf(n, D) tf idf tf(n, LD(C)) idf(n, G) df (n, LD(C)) idf(n, G) ( 3) 2 { h(c 1 ),C 1, h(c 2 ),C 2,, h(c m ),C m } C 1,,C m 1 h(c i ) 2 C i 3 3 h(c i ) C i 2 df idf h(c i ),C i 3 4 k m k DVD RW 3 10

11 HTML 3 C p v f hypo (C, p, v) {p 1,,p l } {v 1,,v m } hypov(c) = f hypo (C, p 1,v 1 ),f hypo (C, p 2,v 1 ),,f hypo (C, p l 1,v m ),f hypo (C, p l,v m ) h(c) hyperv(h(c)) = f(h(c),p 1,v 1 ),f(h(c),p 2,v 1 ),,f(h(c),p l 1,v m ),f(h(c),p l,v m ) f(n, p, v) 33 6 (,,, 2000) 7 n p v WWW 2 Lin(Lin 1998) Lee(Lee 1999) Jaccard (Salton and Lesk 1968) C h(c) sim(c, h(c)) = hypov(c) hyperv(h(c)) hypov(c) hyperv(h(c)) Lin Lee ; 3.01GB 7 ( 2000). 11

l,v m ) f(n, p, v) 33 6 (,,, 2000) 7 n p v 500 0 WWW 2 Lin(Lin 1998) Lee(Lee 1999) Jaccard (Salton and Lesk 1968) C

12 Vol. 1 No. 1 Jan m { h(c i ),C i } m i=1 sim(c i,h(c i )) df (h(c i ),LD(C i )) idf(h(c i ),G) 2 df idf 1 2 k ( 4) WWW

13 HTML 3 3 (part-whole relation) HTML WWW HTML ( 1.26GB ) HTML JUMAN( 1999) HTML ( 0.89GB ) HTML 13

14 Vol. 1 No. 1 Jan. 1 2 ID 10397,,, 16653,,,,,,,, 21561,,,,,, DDI,,,,,, 30288,,,,,,, 35645,,, 51462,,,, 53147,,, NTT,,,,,,, 58174,,,, 59502,,,, 69064,,,,,, HTML Tidy 8 HTML XML ,000 4,000 2,000 13, goo HTML JUMAN ( 2000) j

51462,,,, 53147,,, 56681 NTT,,,,,,, 58174,,,, 59502,,,, 69064,,,,,, HTML Tidy 8 HTML XML

15 HTML Proposed Method (Step 4) Step 3 Step 2 Step 2 (tf) accuracy [%] # of hypernym hyponym pairs 3 j j C k, k=1 j k=1 correct(c k,h(c k )) j k=1 C k j 1 j 200 C k C k correct(c k,h(c k )) h(c k ) C k sim(c, h(c)) df (h(c),ld(c)) idf(h(c),g) 2 df (h(c),ld(c)) idf(h(c),g) ,800(= 2, ) 3 Step 4 15

k=1 C k j 1 j 200 C k C k correct(c k,h(c k )) h(c k ) C k 2 3 4 3 2 3 4 3 4 sim(c, h(c)) df

16 Vol. 1 No. 1 Jan % % 5% % 10% % sim(c, h(c)) df (h(c),ld(c)) idf(h(c),g) df (n, LD(C)) idf(n, G) tf(n, LD(C)) idf(n, G) 3 Step 2(tf) tf(n, LD(C)) idf(n, G) df (n, LD(C)) idf(n, G) tf(n, LD(C)) idf(n, G) df (n, LD(C)) idf(n, G) Step X Rule X X X % %

3 2 df (n, LD(C)) idf(n, G) tf(n, LD(C)) idf(n, G) 3 Step 2(tf) tf(n, LD(C)) idf(n, G)

17 HTML 3 Step2 Step4 Step4 Step4 Step3 Step *, *, *, *, *, JavaScript* 23 *, *, *, *, *, *, *, *, *, 16 *, *, *, 42 *, *, *, *, *, *, * *, *, *, *, 21 *, *, *, *, *, *, *, *, *, 53 *, *, *, 29 *, *, *, *, *, *, * 68 *, *, *, *, *, 47 *, *, *, 112 *,, * *, *, *, 69 *, *, *, *, *, *, *, *, * 78 *, *, *, *, *, *, *, *, ,,,,, *, *, *, *, *, * *,,, * *, *, *, *, *, *, *, * *,, *, * *, *, *, *, * ,,,, 324,,,, 150,,,,,,, 343, 172,,,,,,,,, 391 +,, *, *, 10 +,,,,,,,,, * +. 17

69 *, *, *, *, *, *, 169 + *, *, * 78 *, *, *, *, *, *, *, *, 196 81,,,,, 200 82 *, *, *, *, *, * 201 86 *,,, * 207 106 *, *, *, *, *,

18 Vol. 1 No. 1 Jan Proposed Method -Step 3 -Step 4 -Rule 1 -Rule 2 -Rule 3 accuracy [%] # of hypernym hyponym pairs accuracy [%] Proposed Method 20 Re-ranking of top 2 hypernym candidates Re-ranking of top 3 hypernym candidates Re-ranking of top 4 hypernym candidates Re-ranking of top 5 hypernym candidates # of hypernym hyponym pairs % hyponym(, ) k sim(c, h(c)) df (h(c),ld(c)) idf(h(c),g) 5 18

hypernym hyponym pairs 4 100 80 accuracy [%] 60 40 Proposed Method 20 Re-ranking of top 2 hypernym candidates Re-ranking of

19 HTML sim(c, h(c)) df (h(c),ld(c)) idf(h(c),g) head-final 1 2 HTML 2 HTML 2 1 HTML 3 ( 2001) ( 2003)

20 Vol. 1 No. 1 Jan. 1 4 A B A B.*.* A B.*.* A B.*.* A B.*.* A B.* ( ).* A B A B.* (, )?.* A, B.* ( ).* ( ) 3 2 HTML sim(c, h(c)) df (h(c),ld(c)) idf(h(c),g) 4 20

* ( ) 3 2 HTML 3 1 100 4 1 2 3 4 4 1 2 3 4 1 2 3 6 1

21 HTML Proposed Method Alternative 1 Alternative 2 Alternative 3 Alternative 4 accuracy [%] # of hypernym hyponym pairs df (n, LD(C)) idf(n, G) HTML HTML 2 30 % HTML 30 % 21

22 Vol. 1 No. 1 Jan. 1 3 WWW HTML 6 WWW HTML HTML HTML df idf % 22

23 HTML 1 3 DVD RW, ( 15 (A) , ) ( ).. Caraballo, S. A. (1999). Automatic construction of a hypernym-labeled noun hierarchy from text. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics, pp Fleischman, M., Hovy, E., and Echihabi, A. (2003). Offline Strategies for Online Question Answering: Answering Questions Before They Are Asked. In Proceedings of the 41th Annual Meeting of the Association for Computational Linguistics, pp Hearst, M. A. (1992). Automatic acquistition of hyponyms from large text corpora. In Proceedings of the 14th International Conference on Computational Linguistics, pp Lee, L. (1999). Measures of Distributional Similarity. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, pp Lin, D. (1998). Automatic Retrieval and Clustering of Similar Words. In Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, pp Mandala, R., Tokunaga, T., and Tanaka, H. (1998). The Use of WordNet in Information Retrieval. In Proceedings of the COLING ACL workshop on Usage of Wordnet in Natural Language Processing, pp Miller, G. A., Beckwith, R., Fellbaum, C., Gross, D., and Miller, K. J. (1990). Introduction to WordNet: An on-line lexical database. In Journal of Lexicography, pp Morin, E. and Jacquemin, C. (2003). Automatic acquisition and expansion of hypernym links. In Computer and the Humanities forthcoming. 23

24 Vol. 1 No. 1 Jan. 1 Salton, G. and Lesk, M. E. (1968). Computer evaluation of indexing and text processing. Journal of the ACM, 15 (1), Yoshida, M., Torisawa, K., and Tsujii, J. (2001). A method to integrate tables of the World Wide Web. In Proceedings of the International Workshop on Web Document Analysis, pp ,, (2003) NL-157, pp (2001).. Master s thesis,. (2001).., 8 (4), (1999). JUMAN version (2000). 3 4., 7 (5), : HTML : , ). ( ) ( ) ( ) A

25 HTML $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $. $,$ $ $ , *.*.*.*.*.*.*.* 7 HTML 3.2 HTML (Yoshida, Torisawa, and Tsujii 2001) A B AB O HTML HTML 1 25

26 Vol. 1 No. 1 Jan HTML B

27 HTML 27

1 1 tf-idf tf-idf i

14 A Method of Article Retrieval Utilizing Characteristics in Newspaper Articles 1055104 2003 1 31 1 1 tf-idf tf-idf i Abstract A Method of Article Retrieval Utilizing Characteristics in Newspaper Articles