投稿日: CIKM 論文紹介

How fresh do you want your search results?

Shiwen Cheng
Anastasios Arvanitis
Vagelis Hristidis
In Proc. of CIKM 2013

概要

検索結果中の情報の鮮度に着目した研究はこれまでにも多数行われてきた.既存研究で対象としていたクエリは,ニュースに関するものか,「MLB ワールドシリーズ」のように定期的に高頻度で入力されるものを対象としていた.さらに,Web上でクエリを含む文書数の増加や,入力されるクエリ数の増加から,入力されたクエリが鮮度を必要とするか否かを判定していた.
この研究では,「credit card overdraft fees」や「celebrity gossips」のようなクエリを対象とする.これらのクエリも,関連のある新しい情報が必要とされるが,前述したようなクエリを含む文書数の増加や,入力されるクエリ数の増加からはそのことを推定するのは難しい.そこで,一定期間ごとのクエリの検索結果を比較し,頻繁に検索結果が変化するクエリは情報の鮮度が重要であると考え,検索結果をリランキングする.

手法

クエリQに対する一定期間ごとの検索結果を比較し,頻繁に検索結果が変化するクエリは情報の鮮度が重要であるという考えに基づき,まず各期間の語の分布を求め,期間ごとの分布の差をKLダイバージェンスを用いて求める.
 TDC(Q)=\frac{1}{n-1}\sum_{i=1}^{n-1}KL \left( LM(T_{i}), LM(T_{i+1}) \right)
T_{i}が1つの期間を表し,例えば2013年10月,などに相当する.TDC(Q)が大きいクエリほど情報の鮮度が重要となる.

クエリQに対する文書dのスコアは次式により求められる.
 Score(d,Q)=BM25(d,Q) \cdot \lambda_{Q}e^{\lambda_{Q} \cdot \Delta_{t_{d}}}
 \lambda_{Q} = \alpha \cdot \left( 1-e^{-TDC(Q)} \right)
\Delta_{t_{d}}dがWeb上に現れてから現在までの経過時間である.情報の鮮度が重要なクエリの場合,クエリと関連が高く,最近出現した文書ほどスコアが高くなる.

TDCとクエリの鮮度の相関

119個のクエリに対して,10名の学生と110名のAmazon Mechanical Turkのユーザがクエリに要求される鮮度を判定した.判定は「no time preference」,「up to 2 years old」,「up to 6 months old」,「up to 1 month old」,「up to 1 week old」の5つの中から1つ選択する.1つのクエリに対する評価者の平均値をそのクエリに要求される鮮度の正解値とする.
鮮度が重要でないと判定されたクエリの例としては「public speaking tips」や「interview thank you letter」が,鮮度が重要と判定されたクエリの例としては「California lottery results」や「NBA scores」などがあげられる.

TDCを計算する際は,T_{i}の期間を2007年から2011年は1年,2012年は最初の半年とし,それぞれの期間中にWeb上に現れた文書を対象として,クエリの検索結果の上位400件を集め,その中での語の分布を求める.より具体的には,TDCは次式で求められる.
 TDC(Q)=\frac{1}{5}\sum_{i=2007}^{2011}KL \left( LM(T_{i}), LM(T_{i+1}) \right)

正解値とTDCの相関を求めると,-0.427と高い相関が得られた.T_{i}を1週間,1ヶ月,半年と変えて相関を求めたが,1年としたときが最も相関が高かった.
また,Web上でクエリを含む文書数の増加具合や,入力されるクエリ数の増加具合と正解値の相関を求めたが,提案手法より低い値であった.

検索結果のリランキング

提案手法の他に4つの比較手法を用意する.提案手法を含めた5手法で各クエリに対する検索結果上位5件をプールし,各文書の適合度をAmazon Mechanical Turkにより評価し,手法ごとのnDCGを求める.
クエリの鮮度や文書が生成されてからの時間を考慮しない比較手法と比べて,提案手法のほうが良い結果が得られた.
また,クエリの鮮度の正解値を0-6ヶ月,6-24ヶ月,24ヶ月以上の3グループに分けてnDCGを求めたところ,0-6ヶ月のクエリが最もベースラインに比べて提案手法が検索結果を改善できていた.
時間や鮮度を考慮しない手法でも提案手法と同程度精度の高いクエリがあったが,この理由としては,最近になるほど生成される文書の量が増え,その分通常の検索アルゴリズムでクエリに高い精度で適合する文書が含まれる確率が高くなっているからだと推定される.


-CIKM, 論文紹介
-

関連記事

Tagging Your Tweets: A Probabilistic Modeling of Hashtag Annotation in Twitter

Ma, Zongyang Sun, Aixin Yuan, Quan Cong, Gao In Proc. of CIKM2014 http://dl.acm.org/citation.cfm?id= …

Predicting web searcher satisfaction with existing community-based answers

Liu, Qiaoling Agichtein, Eugene Dror, Gideon Gabrilovich, Evgeniy Maarek, Yoelle Pelleg, Dan Szpekto …

Cooooooooooooooollllllllllllll!!!!!!!!!!!!!! using word lengthening to detect sentiment in microblogs

Brody, Samuel Diakopoulos, Nicholas In Proc. of EMNLP2011 http://dl.acm.org/citation.cfm?id=2145498 …

Music on YouTube: User engagement with traditional, user-appropriated and derivative videos

Liikkanen, Lassi A. and Salovaara, Antti In Computers in Human Behavior, vol. 50 概要 YouTubeの音楽動画を対象に …

Supporting Complex Search Tasks

Ahmed Hassan Awadallah Ryen W. White Patrick Pantel Susan T. Dumais Yi-Min Wang In Proc. of CIKM2014 …