Transcription

1 2012 STUDIES ON RANKING DOCUMENTS WITH QUERY-INTENT SENSITIVITY 11R3129 Shota HATAKENAKA

2 PageRank PageRank PageRank Topic Sensitive PageRank

3 Rocchio

4 1 1.1,,,,, Web, Wiki, blog, twitters,, (query),, (term-matching) (term frequency), (inverse document frequency), TF*IDF,,,,,,,,,,.,,,,,. 3

5 1.2, ,,, Web (theme) (authoritative) (distributive),, Web PageRank [1] ,, Web PageRank HITS,??,,, Topic Sensitive PageRank 10 4 Topic Sensitive PageRank [2] 4

6 1.1: 1.2.3?? Bhattacharyya.[3] 1.2:

7 , Rocchio 5 3 Rocchio [4] PageRank , : 3 (DEIM ), PageRank 2., : Ranking Documents using Similarity-based PageRanks, IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PacRim), PageRank 6

8 3., : PageRank, 4 (DEIM ), 2012., 2, 4., : Ranking Documents with Query and Topic Sensitivity, 7th International Conference on Digital Information Management (ICDIM ), 2012., 2, 5., : Query and Topic Sensitive PageRank for General Documents, 14th IEEE International Symposium on Web Systems Evolution (WSE), 2012., 2, 6.,, :, 11 FIT, 2012.,,, Bhattacharyya.,Bhattacharyya,. 7.,, : Ranking Documents with Query-Topic Sensitivity, International Workshop on Web Information Retrieval Support Systems in IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology(WIRSS), , 7

9 . 8.,, :, 5 (DEIM ), Web 8

10 2 PageRank 2.1,,, Web, Wiki, blog, twitters,, (query),, (term-matching) (term frequency) (inverse document frequency) TF*IDF,, ( ) 9

11 , Web (theme) (authoritative) (distributive),,,,,,,,,,, Web PageRank HITS, Web PageRank d d =< v 1,..., v n > i = 1,..., n w i v i 2 TF*IDF q d i 10

12 cos(d i q) cos(d i q) cos(d i, q) = d i q d i q q d 1, d 2 d n PageRank PageRank Web Web Web PageRank Web PageRank A B PageRank 11

13 P i PageRank P R i P j PageRank P R j P R i = P j B Pi P R j P R j B Pi P i P R j P j PageRank 1 n PageRank H 1 n t t = t+1 H H 2 PageRank H Web Web PageRank 1 Web Web 2 Web Web 2 H H H = (1 d)h + d N N Web d Web Web PageRank Web PageRank Web 12

14 d i d j cos(d i, d j ) = d i d j d i d j 0 PageRank 2 d 0 d 1 d n N ( ) d 1 d 0 r 01 r 01 = 1 N r 01 d 1 d n d 0 d 0 d 1 d n d 1 d 0 rw 01 rw 01 = w 01 ni=1 w 0i w 01 d 0 d 1 d 0 d PageRank 2 1/N N M M = (1 d)m + d d 0.15 M PageRank 13

15 A B B C A C ( ) PageRank PageRank r 1 r 2 10 Sim(r 1, r 2 ) = (A B) k A B r 1 r 2 k PageRank PageRank PageRank 2 3 PageRank

16 (PageRank) Web PageRank 2.5 Web 15

17 2.1: PageRank Top10 PR

18 2.2: TOP : k Sim (PageRank, )

19 3 PageRank, 2, 3.1,,,,, Web, Wiki, blog, twitters,,, (query),, (term-matching) (term frequency), (inverse document frequency), TF*IDF,,,,,,,,,, ( ),, 18

20 ,,, (Topic Driftting), Web PageRank HITS,,,, Web PageRank

21 2 3.3 d d =< v 1,..., v n > i = 1,..., n w i v i 2 TF*IDF q d i cos(d i q) cos(d i q) cos(d i, q) = d i q d i q q d 1, d 2 d n 3.4 PageRank PageRank PageRank PageRank A B PageRank 20

22 d i PageRank P R i d j PageRank P R j P R i = d j B di P R j P R j B di d i P R j d j PageRank 1 n PageRank H 1 n t t = t+1 H H 2 PageRank H Web PageRank H H H = (1 d)h + d N N Web d Topic Sensitive PageRank Topic Sensitive PageRank [7] Web ODP ODP PageRank 2 PageRank ODP c j PageRank d PageRank rank jd q PageRank c j q P (c j q ) P (c j q ) = P (c j) P (q c j ) P (q ) P (c j ) P (q c j ) 21

23 s qd s qd = n P (c j q ) rank jd j ODP [?] PageRank 2 d i t j T ji T ji = d i t j d i t j t j t j s j t j s j d i d j w ij w ij = d i d j d i d j 0 22

24 PageRank 2 d 0 d 1 d n N ( ) d 1 d 0 r 01 r 01 = 1 N r 01 d 1 d n d 0 d 0 d 1 d n d 1 d 0 r 01 r 01 = w 01 ni=1 w 0i d 0 d PageRank PageRank 2 1/N N t j M M = (1 d)m + d d PageRank 0.15 M PageRank s j PageRank PageRank s j d i PageRank P R ji P R ji = s j nk=1 s k P R ji s j d i PageRank P R ji 23

25 3.5.3 t j t j q m s j Q mj s j w j Q jm = q m w j q m w j Q jm q m d i n v mi = T ji P R ji Q jm j=1 q m d i v mi PageRank [?]

26 8 ( ) PageRank Topic Sensitive PageRank Topic Sensitive PageRank PageRank 2 ODP 8 PageRank : TSPR MYPR TSPR MYPR ,3,5 3,4, Topic Sensitive PageRank

27 10 4 Topic Sensitive PageRank 4 2 Topic Sensitive PageRank Topic Sensitive PageRank Topic Sensitive PageRank Topic Sensitive PageRank Topic Sensitive PageRank Topic Sensitive PageRank Topic Sensitive PageRank Topic Sensitive PageRank

28 3.2: (TSPR) 4.56E E E-08 0 (MYPR) (TSPR) E E-08 (MYPR) Topic Sensitive PageRank 1 Topic Sensitive PageRank ODP Web

29 3.3: Topic Sensitive PageRank PageRank ( ) : PageRank * ( ) : Topic Sensitive PageRank PageRank ( )

30 3.6: PageRank * ( ) : TD

31 3.8: TD

32 4 4.1 Blog twitter 31

33 4.2 ( ) ( ) Bhattacharyya [6] Bhattacharyya Bhattacharyya 1 L = m u=1 P u Q u p q m u=1 P u = m u=1 Q u = 1 blog twitter Bhattacharyya Bhattacharyya 2 d q = N n=1 tf i Bha i N q d d q tf i d i Bha q i q i Bhattacharyya N d q q q Bhattacharyya q Bhattacharyya 0 Bhattacharyya 32

34 q Bhattacharyya q Bhattacharyya Bhattacharyya Bhattacharyya q q Bhattacharyya Bhattacharyya 0 Bhattacharyya Bhattacharyya q q d , ,000 6, Bhattacharyya 4.1 Bhattacharyya 4.2 Bhattacharyya ID

35 4.1: Bhattacharyya Bhattacharyya ID : Bhattacharyya ( ) Bhattacharyya ID Bhattacharyya 4.3 Bhattacharyya Bhattacharyya Bhattacharyya 34

36 4.3: Bhattacharyya ( ) Bhattacharyya ID Bhattacharyya Bhattacharyya Bhattacharyya 4.6 Bhattacharyya Bhattacharyya 35

37 4.4: 5 ID: : : : : : 28 36

38 5 5.1 Blog twitter,,,, ( ) ( ) 37

39 3 Rocchio 5.2 Rocchio d d =< v 1,..., v n > i = 1,..., n w i v i 2 TF*IDF q d i cos(d i q) cos(d i q) 38

40 cos(d i, q) = d i q d i q q d 1, d 2 d n Rocchio [15] q D r D n TF*IDF q q q = q + D R d i D R d i D N d j D N d j D R D N Bhattacharyya [?] Bhattacharyya Bha = m u=1 P u Q u (0 Bha 1) p q ( m u=1 P u = m u=1 Q u = 1) blog twitter 39

41 Bhattacharyya Bhattacharyya q q i BC iq 1 BC iq = Bha iq log( ) CO iq Bha iq q i Bhattacharyya CO iq q i 2 Bha CO Bha Bha Bha CO iq CO iq = c a + b c a i b q c i q q q BC dr N BC iq,n+1 = BC iq,n (1 + w i,d + N + w i,d N ) BC i,n n q i N N + n w i,d + w i,d i i n+1 j dr j,n+1 Nn=1 tf i,j BC iq,n+1 dr j,n+1 = N tf i,j j i N j j CO j CO j = Nn=1 tf i,j CO iq N 40

42 q i BC iq 2. N BC i,n , ,000 6, Rocchio 3 =1.0 =0.8 =

43 Rocchio 3 top10 R) Rocchio Rocchio Rocchio 5 ( ), 1, 4 5 Rocchio

44 5.1: Rocchio FB[0] FB[1] FB[2] FB[3] R) R) R) R) ( ) R) ( ) ( ) ( )

45 5.2: Rocchio SMAP SMAP , 44

46 5.3: ??NY, , ASEM ASEM

47 5.4: Rocchio ?? PT ?? , 18 PT

48 5.5: ?? , NHK

49 5.6: ?? ,

50 6,. Web,,,,,,,,, 49

51 50

52 [1] Hatakenaka, S. and Miura, T.: Ranking Documents using Similarity-based Page- Ranks, IEEE Pacific Rim Conference on Communications, Computers and Signal Processing(PacRim), [2] Hatakenaka, S. and Miura, T.: Query and Topic Sensitive PageRank for General Documents, 14th IEEE International Symposium on Web Systems Evolution(WSE), [3] :, 11 FIT, [4] :, 5 (DEIM), [5] S. Brin and L. Page The anatomy of a large scale hypertextual Web search engine. ComputerNetworks and ISDN Systems, 30, , [6] Oren. Kurland and Lillian Lee PageRank without hyperlinks: Structural reranking using links induced by language models. Proceedings of the 28th annual international ACM SIGIR, [7] T. H. Haveliwala Topic-sensitive PageRank. Proceedings of the 11th international conference on World Wide Web, [8] Amy N. Langville, Carl D. Meyer,,, Google PageRank 2009 [9] J. Kleinberg Bursty and hierarchical structure in streams. Proc. 8th SIGKDD,2002, [10] Masaya Murata, Hiroyuki Toda, Yumiko Matsuura and Ryoji Kataoka, A Query Expansion Method Using Access Concentration Sites in Search Result Proceedings of the DataBase and Web symposium,

53 [11] Hang Cui, Ji-RongWen, Jian-Yun Nie andwei-yingma, Probabilistic Query Expansion Using Quer Logs Proceedingsof the 11th international conference on World Wide Web 2002, [12] Georges E. Dupret and Benjamin Piwowarski. A user browsing model to predict search engine click data from past observations ACM SIGIR , [13] KMamoru Komachi, Shimpei Makimoto, Kei Uchiumi, and Manabu Sassano. Learning semanticcategories from clickthrough logs ACLIJCNLP , [14] Qingshan LIU and Dimitris N METAXAS Unifying Subspace and Distance Metric Learning with Bhattacharyya Coefficient for Image Classification Lecture Notes in Computer Science 2009 Volume 5416/ , [15] Rocchio, J.J Relevance fssdback in information retrieval. The SMART Retrieval Systems, pp , Prentice-Hall,