Upgrade to Pro — share decks privately, control downloads, hide ads and more …

IR Reading 2019秋 論文紹介 / IR Reading 2019Fall

Takuya Asano
October 27, 2019

IR Reading 2019秋 論文紹介 / IR Reading 2019Fall

IR Reading 2019秋 http://sigir.jp/post/irreading_2019fall/ で下記2本の論文を紹介しました。

1. Accelerated Query Processing Via Similarity Score Prediction (SIGIR 2019)
2. Fast Approximate Filtering of Search Results Sorted by Attribute (SIGIR 2019)

Takuya Asano

October 27, 2019
Tweet

More Decks by Takuya Asano

Other Decks in Research

Transcript

  1. "DDFMFSBUFE2VFSZ1SPDFTTJOH7JB 4JNJMBSJUZ4DPSF1SFEJDUJPO 4*(*3 w 63- w IUUQTEMBDNPSHDJUBUJPODGN JE w ݚڀͷ໨త

    w సஔΠϯσοΫεܕͷݕࡧΤϯδϯͰUPQLͷΫΤϦॲཧΛ
 ߴ଎Խ͢Δ͜ͱ w ํ๏ w ΫΤϦॲཧதͷಈతͳจॻͷࢬמΓ QSVOJOH ʹண໨͠ɺ
 ػցֶशΛԉ༻ͯ͠ΞϧΰϦζϜΛվળ
  2. ಈతࢬמΓʹΑΔΫΤϦॲཧ w ΫΤϦॲཧதʹɺͦΕ·Ͱʹॲཧͨ͠จॻͷUPQLͷείΞ Λܭࢉɾอ࣋͢Δʢ੨ઢʣ w ࠷ऴతʹ ʹऩଋ͢Δ w จॻͷείΞͷVQQFSCPVOEΛܭࢉ͢Δ w

    λʔϜ͝ͱͷ࠷େείΞ NBYTDPSF ΛΠϯσοΫεʹอଘ͓ͯ͘͠ͳͲ w VQQFSCPVOE͕ᮢ஋ ΑΓখ͍͞είΞͷจॻ͸҆શʹεΩοϓͰ͖Δ w ͜ͷํ๏͸ϩεϨεɺͭ·Γਖ਼֬ͳUPQLͷจॻ͕ಘΒΕΔ θ Θk θ
  3. طଘͷಈతࢬמΓΞϧΰϦζϜ w ޮ཰తͳΫΤϦॲཧͷํ๏ͱͯ͠.BY4DPSF 8"/%  #.8 CMPDLNBY8"/% ͕͋Δ w ͢΂ͯجຊతͳઓུ͸લड़ͷಈతࢬמΓͱಉ͡

    w 8"/%͸ݡ͍ΞϧΰϦζϜͰ.BY4DPSFΑΓͨ͘͞Μ εΩοϓͰ͖ΔΑ͏ʹ͍ͯ͠Δ w #.8 CMPDLNBY8"/% ͸8"/%ΛϒϩοΫԽ͠ɺ ֤ϒϩοΫʹ౷ܭ৘ใΛ΋ͭΑ͏ʹ͞Βʹվྑͨ͠΋ͷ
  4. 3FTFBSDI2VFTUJPOT w 32 w సஔΠϯσοΫεΛॲཧ࢝͠ΊΔલʹ ΛਪఆͰ͖Δ͔ʁ w 32 w ΋͠લ΋ͬͯ

    ΛਪఆͰ͖ΔͳΒɺͦͷࣄલ஌ࣝʹΑͬͯ
 Ͳͷఔ౓ΫΤϦॲཧΛ଎͘Ͱ͖Δ͔ʁ w 32 w ͷࣄલ஌ࣝΛ࢖ͬͯ.BY4DPSFɺ8"/%ɺ#.8ͷΑ͏ͳख๏ ΛվྑͰ͖Δ͔ʁ Θk (D, Q) Θk (D, Q) Θk (D, Q)
  5. w PWFSFTUJNBUFͨ͠ͱ͖ʹΑΓϖφϧςΟΛ༩͍͑ͨ w ֬཰Ϟσϧʹଛࣦؔ਺Λ૊Έ߹ΘͤΔ w ࠓճ͸PWFSFTUJNBUFͨ͠ͱ͖ͷଛࣦΛ ഒͱ ͢ΔΑ͏ͳઢܗͷଛࣦؔ਺ʢ੨ઢʣΛߟ͑Δ α ֬཰Ϟσϧϕʔεͷᮢ஋༧ଌ

    w .JOJNVN#BZFT3JTL .#3  w ༧ଌ෼෍ͷ্Ͱɺଛࣦͷظ଴஋͕࠷খͱ ͳΔΑ͏ͳ Λબ୒Ͱ͖Δ w ࠷దͳ ͸ ͷRVBOUJMFͱͳΔ ͜ͱ͕ূ໌͞Ε͍ͯΔ<> w ͨͱ͑͹ɺ ͷͱ͖RVBOUJMF ࢛෼Ґ఺ ͕࠷ద w Ϟσϧʹ͸#BZFTJBO-JOFBS3FHSFTTJPO #-3 Λ࢖ͬͨ w ղੳతʹʢดܗࣜͰʣղ͕ٻΊΒΕΔͷ Ͱߴ଎ʹܭࢉͰ͖Δ ̂ Θk ̂ Θk 1/(α + 1) α = 3 <>1'$ISJTUP⒎FSTFOBOE'9%JFCPME0QUJNBMQSFEJDUJPOVOEFSBTZNNFUSJDMPTT&DPOPNFUSJD5IFPSZ   r 
  6. ଛࣦϕʔεͷᮢ஋༧ଌ w ଛࣦؔ਺Λ࢖ͬͨػցֶशϞσϧ΋ߟ͑Δ w ༩͑ΒΕͨଛࣦؔ਺ʹରͯ͠௚઀ֶश w ଛࣦؔ਺ʹ͸ඇରশʹͨ͠)VCFSMPTTΛ࠾༻ w ඍ෼Մೳ w

    ϚϧνϨΠϠʔύʔηϓτϩϯ .-1  w .-1-
 ૚ʢӅΕ૚͕ʣͷ.-1 w .-1-
 ૚ʢӅΕ૚͕ʣͷ.-1 w ͍ͣΕ΋$16Ͱޮ཰తʹܭࢉՄೳ
  7. Ϟσϧͷֶश w Ϟσϧͷֶशʹ࢖ͬͨΫΤϦϩά w .JDSPTPGU2VFSZMPH w   ΫΤϦ w

    σʔληοτ w (PWສ݅ w $MVF8FC#ສ݅ w ֶशࡁΈϞσϧͷ༧ଌ଎౓ w NT .-1-  w NT .-1-  w NT #-3  w ͍ͣΕ΋NTҎ಺ͳͷͰे෼଎͍ ֶशʹ࢖ͬͨಛ௃ྔ
  8. 3FTFBSDI2VFTUJPOT w 32 w సஔΠϯσοΫεΛॲཧ࢝͠ΊΔલʹ ΛਪఆͰ͖Δ͔ʁ w ˠώʔϓͷᮢ஋͕༧ଌՄೳͰ͋Δ͜ͱΛࣔͨ͠ w 32

    w ΋͠લ΋ͬͯ ΛਪఆͰ͖ΔͳΒɺͦͷࣄલ஌ࣝʹΑͬͯ
 Ͳͷఔ౓ΫΤϦॲཧΛ଎͘Ͱ͖Δ͔ʁ w ˠಈతࢬמΓΞϧΰϦζϜͷ଎౓͕Ҏ্վળ͢Δ͜ͱΛࣔͨ͠ w 32 w ͷࣄલ஌ࣝΛ࢖ͬͯ.BY4DPSFɺ8"/%ɺ#.8ͷΑ͏ͳख๏ΛվྑͰ͖Δ͔ʁ w ˠ͢΂ͯͷख๏ͰΞϧΰϦζϜతͳվળ͕ՄೳͰ͋Δ͜ͱΛࣔͨ͠ Θk (D, Q) Θk (D, Q) Θk (D, Q)
  9. ײ૝ w ܾఆతͳํ๏ʢ Λ࢖͏ϕʔεϥΠϯʣͰ΋े෼Ͱ͸ʁ w 5BCMFΛΈΔͱɺϕʔεϥΠϯ͔Βͷࠩ͸ͦΕ΄Ͳେ͖͘ͳ͍ w "MHPSJUINͰଟগվળ͢Δͱ͸͍͑ɺࠩ෼͸͍͍ͤͥఔ౓ w ࢬמΓΞϧΰϦζϜͷࠩͷ΄͏͕େ͖͍

    w ࢓૊Έ͕γϯϓϧͳ ͷ΄͏͕औΓճ͠΍͍͢ʢػցֶश͍Βͳ͍͠ʣ w ΋ͬͱ͍͍ϞσϧΛ࡞ΕΔ༨஍͸͋Δ w ಛ௃ྔ΍ػցֶशΞϧΰϦζϜͷվળ͕Մೳ w ਅͷᮢ஋ʢΦϥΫϧʣʹ͚ۙͮ͹ͦΕͳΓʹ଎͘ͳΔ Qk Qk
  10. 'BTU"QQSPYJNBUF'JMUFSJOHPG4FBSDI 3FTVMUT4PSUFECZ"UUSJCVUF 4*(*3 w 63- w IUUQTEMBDNPSHDJUBUJPODGN JE w ໰୊ઃఆ

    w ଐੑʹΑΔιʔτॱΛकΓͳ͕Β%$(ͷΑ͏ͳϝτϦοΫΛ࠷దԽ͢Δ໰୊ w ͜ͷݚڀͷ੒Ռ w ߴ଎ʹ΄΅࠷దͳ݁ՌΛฦ͢ΞϧΰϦζϜΛఏҊ w ۙࣅʹΑΔΤϥʔ཰ͱ࠷ѱ࣌ؒܭࢉྔͷཧ࿦อূ͋Γ w ࣮ݧతʹ΋ߴ଎ੑͱΤϥʔ཰ͷόϥϯε͕Α͍͜ͱ͕ࣔ͞Εͨ
  11. ໰୊ઃఆ'JMUFSJOH!L w ௨ৗɺϢʔβ͕ݕࡧͰཉ͍͠ͷ͸ SFMFWBODFΛ࠷େԽͨ͠4&31 w 8FCݕࡧɺ4/4ɺετϦʔϛϯά αʔϏεɺ&$αΠτͳͲ w ଟ͘ͷαʔϏεͰ͸ɺଐੑʢ࣌ؒ΍Ձ֨ ͳͲʣʹΑΔιʔτʹରԠ͍ͯ͠Δ

    w ͨͱ͑͹"NB[POͰJQIPOFͷݕࡧ݁ ՌΛՁ֨ͷ͍҆ॱʹ͢ΔͱSFMFWBODFͷ
 ௿͍ΞΠςϜ্͕ʹདྷΔͨΊɺϢʔβମ ݧΛଛͳ͏ BNB[PODPKQͰՁ֨ͷ͍҆ॱͰJQIPOFΛݕࡧ
 ʢՈిˍΧϝϥΧςΰϦʣ
  12. ώϡʔϦεςΟΫεʹΑΔํ๏ w $VUP⒎015 w ͋Β͔͡ΊܾΊͨSFMFWBODFͷᮢ஋ͰϑΟϧλ͔ͯ͠Β015Ͱ͞ΒʹϑΟϧλ w ࠷ѱέʔεͰ͸Τϥʔ཰ʢਫ਼౓ʣͷอূ͕ͳ͍ w ᮢ஋ͷઃఆʹΑΔͨΊ w

    ࣌ؒܭࢉྔ͸վળͤͣ࠷ѱέʔεͰ  w 5PQL015 w UPQLͷϦετΛٻΊɺͦΕΛ͞Βʹ015ͰϑΟϧλ͢Δ w LݸະຬͷϦετʹ͢Δ͜ͱͰϝτϦοΫΛ࠷େԽͰ͖Δ͜ͱ΋͋ΔͨΊ w PQUJNBMʢۙࣅʹΑΔΤϥʔ཰͕ʣͰ͋Δ͜ͱ͕ূ໌Ͱ͖Δ w ࣌ؒܭࢉྔ͸࠷ѱͰ Θ(nk) Θ(n log k + k2)
  13. Џ'JMUFSJOH w $VUP⒎΍5PQLͳͲͷώϡʔϦεςΟΫεͰ͸Τϥʔ཰ΛίϯτϩʔϧͰ͖ͳ͍ w Џ'JMUFSJOH͸Τϥʔ཰ΛЏҎԼʹอূͨۙ͠ࣅղΛɺ
 ࣌ؒܭࢉྔ Ͱݟ͚ͭΔʢ ʣ w Џ'JMUFSJOH͸ҎԼͷεςοϓ͔ΒͳΔ

    w 3JHIUQSVOJOH w %JTDSFUJ[BUJPO w 5ISFTIPMEJOH w ֤ϑΣʔζͰى͜Γ͏Δ࠷ѱέʔεʹɺޙͷϑΣʔζͰରԠ͢Δ͜ͱͰ
 ܭࢉ࣌ؒΛ࡟͍ͬͯ͘ Θ(n + k2 log(1−ϵ) (ϵ/k)) 0 < ϵ < 1