DEIM Forum 2018 C (1) (2), Web [3] 1. Shen [7] SNS T

Size: px

Start display at page:

Download "DEIM Forum 2018 C (1) (2), Web [3] 1. Shen [7] SNS T"

てるえいざわ
4 years ago
Views:

1 DEIM Forum 2018 C s.nagaki@kde.cs.tsukuba.ac.jp, kitagawa@cs.tsukuba.ac.jp (1) (2), Web [3] 1. Shen [7] SNS Twitter 1 Twitter [1 3] 2 2 NY the big apple Apple Apple inc. Wikipedia 2 DBpedia 3 Question Answering [4] [5,6] Mention Detection: 2 Candidate Selection: 3 Linking Decision: unlinkable [[NIL]] [[]] Candidate Selection Linking Decision Linking Decision [7] Wikipedia

2 sparrow [[Sparrow Records]] [[Sparrow]] [[Matt Sparrow]] [[Pirates of the Caribbean]] sparrow[[jack Sparrow]] [[Pirates of the Caribbean]] 2 Entity Recency FULLlinking LIGHT-linking 2 FULL-linking Entity Recency LIGHT-linking FULL-linking Entity Recency 1 Producer-Consumer FULL-linking FULL-linking Entity Recency LIGHT-linking 1: Producer-Consumer FULL-linking FULL-linking Entity Recency LIGHT-linking 3... Linking Decision : URI 2 : 3 :

3 d d M(d) := {m i} n(d) i=1 d KB E(d) := {(m i, e(m i)) m i M(d)}, s.t. e(m) KB {NIL}. e(m i) m i NIL n(d) d 4 : d i t i T D := {(t i, d i )} N i=0 5 : T D = {(t j, d j )} N j=0 d j M(d i ) := {m i } n(d) i=1 T D KB T E(T D) T E(T D) T E(T D) := {(t j, E(d j )} N j=1, s.t. E(d j ) := {(m i, e(m i )) m i M(d j )}, s.t. e(m) KB {[[NIL]]}. e(m i ) m i [[NIL]] 1. (1)Mention Detection, (2)Candidate Selection, (3)Linking Decision 3 d KB 6 : Mention Detection d M(d) = {m i } n(d) i=0 7 : Candidate Selection Mention Detection M(d) CSL(M(d)) = {CS(m) m M(d)} CS(m) m M(d) e CS(m) s.t. e KB. 8 : Linking Decision Candidate Selection CSL d E(d) := {(m i, e(m i)) m i M(d)}, s.t. e(m) KB {[[NIL]]}. e(m i) m i [[NIL]] Candidate Selection [7] Wikipedia 9 : D m i D(m i) := {(e ij, p(e ij m i))} n i j=0 eij mi p(e ij m i) m e Candidate Selection. 10 : Candidate Selection Mention Detection M(d) D CSL (M(d) D) := {CS(m) m M(d)}, s.t. e CS(m), e D(m).. ( 5) Candidate Selection( 10) m CS(m) Producer-Consumer 1 FULL-linking: Entity Recency 2 LIGHT-linking: FULL-linking Entity Recency 3. 2 Entity Recency [8] m e Entity Recency Entity Recency 11 : τ t τ t t 12 : Entity Recency

4 t T D t d m e Entity Recency ER(e m, T) = D T e e i D(m) DT e i ( e i D(m) DT e i = 0) p(e m) (otherwise) D T e e T D T e d p(e m) D m e T e e Entity Recency 1 Entity Recency T m e score(e, m, T) =(1 + rank(e, m) ) (1 λ) p(e m) size(d(m)) rank(e, m) λ ER(e m, T). size(d(m)) size(d(m)) m p(e m) m e rank(e, m) m p(e m) e rank(e, m) λ e D(m) DT e ER(e m) ER(e m) λ λ = e D(m) DT e D T α + e D(m) DT e α D T D T e 3. 3 (1) (2) 1 Producer-Consumer FULL-linking 1 d j (1 ) M j m i K , Algorithm 1: FULL-linking Input: (t j, d j ), D, K 1 τ Output: E(dj) := (mi, e(mi)) mi M(dj) 1 M(d j ) MentionDetection(d j ) 2 CSL(M(d j )) [ ] 3 for m i M(d j ) do 4 CS(m i ) CandidatesSelection(m i, t j, D, K 1 ) 5 CSL(M(d j )).push(cs(m i )) 6 end 7 E(d j ) LinkingDecision(M j, CSL(M(d j ))) 8 D UpdateDB(E(d j ), t j, τ, D) 9 return E(d j ) Algorithm 2: LIGHT-linking Input: (t j, d j ), D, K 2 Output: E(dj) := (mi, e(mi)) mi M(dj) 1 M(d j ) MentionDetection(d j ) 2 CSL(M(d j )) [ ] 3 for m i M(d j ) do 4 CS(m i ) CandidatesSelectionW ither(m i, t j, D, tau, D, K 2 ) 5 CSL(M(d j )).push(cs(m i )) 6 end 7 E(d j ) LinkingDecision(M j, CSL(M(d j ))) 8 return E(d j ) t j Entity Recency 8 Entity Recency Entity Recency T e D T e LIGHT-linking 2 1 M j m i 3 6 Entity Recency m j t j T j e 1 score(e, m, T j ) K 2 4. : : : Linking Decision Linking Decision Ubuntu 14.04LTS, Intel R Xeon R E v2 CPU, 128GB

5 1: 63, / 997, / 4.53 / 2: washington black trump moonlight dakota epn bolt patrick kennedy RAM PC Python gensim 4, TextBlob 5 C++ gcc 4.9 OpenMP New York Times Wikipedia Portal:Current events Portal:Current events 1 Portal:Current events Wikipedia Twitter API (GET statuses/sample) Wikipedia Wikipedia 11 4,923, events 9 overview/get statuse sample 10 NYTimes Archive API 11 pages articles en.xml.bz Mention Detection New York Times API 12 Portal:Current events Python Text Blob Linking Decision 3 Voting [9] Iterative Substitution (Itr-Sub) [10] Pair-Linking [11] a ) Word embedding Phan [11] Wikipedia cos Wikipedia Annotated-WikiExtractor 13 Word2vec [12] Python gensim b ) 5. 1 Wikipedia Wikipedia 12 api.json#/readme 13

6 Processing time (ms) Top 30 Top 3 Proposed Voting ItrSub PairLinking Processing time (ms) Top 30 Top 3 Proposed Voting ItrSub PairLinking (a) (b) 2: x y 30 Voting ItrSub (a) PairLinking Voting ItrSub (b) PairLinking 3: x y 3 Shen [7] a ) 8,805,246 2,126, τ 2 α τ Hua [8] 3 α 05. FULL-linking K 1 30 LIGHT-linking K 2 3 FULL-linking LIGHT-linking FULL-linking 24 LIGHT-linking d acc doc (d) := {mi M(d) e(mi) == trueentity} M(d) K 1 (= 30) K 2 (= 3) x y x y 3 Entity Recency

7 Voting ItrSub (a) PairLinking Voting ItrSub (b) PairLinking 4: x y 3 Entity Recency α 4 x y Linking Decision 3 Entity Recency FULL-linking r Entity Recency α FULL-linking LIGHT-linking 5 FULL-linking Entity Recency FULL-linking LIGHT-linking Linking Decision FULL-linking LIGHT-linking FULL-linking LIGHT-linking Voting ItrSub PairLinking 0 Voting ItrSub PairLinking (a) (b) 5: x y FULL-linking Candidate Selection Wikipedia [7,13] m e p(e m) Spitkovsky [14] Web 14 K [15,16] [17] [9, 18] 14

8 5. 2 Twitter Hua [8] (1) (2) (3) Fang [19] 6. (1) (2)(1) Linking Decision Linking Decision Entity Recency α Entity Recency NICT [1] M. Mathioudakis and N. Koudas. Twittermonitor: Trend detection over the twitter stream. In SIGMOD 10, pp , [2] C. Zhang, G. Zhou, Q. Yuan, H. Zhuang, Y. Zheng, L. Kaplan, S. Wang, and J. Han. Geoburst: Real-time local event detection in geo-tagged tweet streams. In SIGIR 16, pp , [3] A. Schulz, B. Schmidt, and T. Strufe. Small-scale incident detection based on microposts. In HT 15, pp. 3 12, [4] F. Hasibi, K. Balog, and S. E. Bratsberg. Exploiting entity linking in queries for entity retrieval. In ICTIR 16, pp , [5] P. Kapanipathi, P. Jain, C. Venkatramani, and A. P. Sheth. User interests identification on twitter using a hierarchical knowledge base. In ESWC 14, pp , [6] G. Li, J. Hu, J. Feng, and K. L. Tan. Effective location identification from microblogs. In ICDE 14, pp , [7] W. Shen, J. Wang, and J. Han. Entity linking with a knowledge base: Issues, techniques, and solutions. IEEE Transactions on Knowledge and Data Engineering, Vol. 27, No. 2, pp , [8] W. Hua, K. Zheng, and X. Zhou. Microblog entity linking with social temporal context. In Proc. the 2015 ACM SIG- MOD International Conference on Management of Data, pp , [9] P. Ferragina and U. Scaiella. Fast and accurate annotation of short texts with wikipedia pages. IEEE Software, Vol. 1, No. 29, pp , [10] W. Shen, J. Wang, P. Luo, and M. Wang. LIEGE: : link entities in web lists with knowledge base. In KDD 12, pp , [11] M. C. Phan, A. Sun, Y. Tay, J. Han, and C. Li. Neupl: Attention-based semantic matching and pair-linking for entity disambiguation. In CIKM 17, pp , [12] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems 26, pp , [13] S. Cucerzan. Large-scale named entity disambiguation based on wikipedia data. In EMNLP-CoNLL 07, pp , [14] V. I Spitkovsky and A. X Chang. A cross-lingual dictionary for english wikipedia concepts. In LREC 12, pp , [15] Z. Guo and D. Barbosa. Robust entity linking via random walks. In CIKM 14, pp , [16] E. O. Ganea, M. Ganea, A. Lucchi, C. Eickhoff, and T. Hofmann. Probabilistic bag-of-hyperlinks model for entity linking. In WWW 16, pp , [17] A. Pappu, R. Blanco, Y. Mehdad, A. Stent, and K. Thadani. Lightweight multilingual entity extraction and linking. In WSDM 17, pp , [18] F. Hasibi, K. Balog, and S. E. Bratsberg. Entity linking in queries: Tasks and evaluation. In ICTIR 15, pp , [19] Y. Fang and M. Chang. Entity linking on microblogs with spatial and temporal signals. Transactions of the Association for Computational Linguistics, Vol. 2, pp , 2014.

DEIM Forum 2019 D3-5 Web Yahoo! JAPAN Q&A Web Web

DEIM Forum 2019 D3-5 Web Yahoo! JAPAN Q&A Web Web DEIM Forum 2019 D3-5 Web 565 0871 1 5 Yahoo! JAPAN 102 8282 1 3 E-mail: {nakamura.tatsuya,hara}@ist.osaka-u.ac.jp, sufujita@yahoo-corp.jp Q&A Web Web Q&A Web Web 1 Web Web Web [2], [3], [10] Web Web [8],