投稿日: SIGIR 論文紹介

Time-sensitive query auto-completion

Shokouhi, Milad
Radinsky, Kira
In Proc. of SIGIR 2012
http://dl.acm.org/citation.cfm?id=2348364

概要

従来のクエリの自動補完では,過去の一定期間における各クエリの出現頻度にのみ基づいて候補を選んでいる.
しかし,例えば10月に「ha」と入力されたら,「harry potter」よりも「halloween」を上位に提示したほうが良いように,時期によって補完する内容を変えることを目的としている.

手法

時刻tにおけるクエリqの候補としての良さを次式で表す.
 w(q|t)=\frac{\hat{y}_{t}(q)}{\sum_{i \in Q}\hat{y}_{t}(i)}
Qはクエリログ中の全クエリである.

まず,最もシンプルな方法として,時刻tにおけるクエリの出現頻度を,それ以前の出現頻度も考慮してスムージングを行う方法がある.
 \overline{y}_{t}=\lambda y_{t} + (1-\lambda)\overline{y}_{t-1}
この場合,時刻t+1における予測値は\hat{y}_{t+1} = \overline{y}_{t}となる.

次に,この手法を拡張し,クエリの流行度合い(F_{t})も考慮するようにする.
 \overline{y}_{t}=\lambda_{1} y_{t} + (1-\lambda_{1})(\overline{y}_{t-1} + F_{t-1})
 F_{t}=\lambda_{2} (\overline{y}_{t}-\overline{y}_{t-1}) + (1-\lambda_{2})F_{t-1}
このとき,t+1における予測値は\hat{y}_{t+1}=\overline{y}_{t}+F_{t}となる.

さらに,この手法を拡張し,クエリの周期性(S_{t})も考慮するようにする.
 \overline{y}_{t}=\lambda_{1} (y_{t}-S_{t-\tau}) + (1-\lambda_{1})(\overline{y}_{t-1} + F_{t-1})
 F_{t}=\lambda_{2} (\overline{y}_{t}-\overline{y}_{t-1}) + (1-\lambda_{2})F_{t-1}
 S_{t}=\lambda_{3} (y_{t}-\overline{y}_{t}) + (1-\lambda_{3})S_{t-\tau}
\tauが周期を表す.このとき,t+1における予測値は\hat{y}_{t+1}=(\overline{y}_{t}+F_{t})S_{t+1-\tau}となる.

実験

実験では,クエリの出現頻度の予測の精度と,ランキングの精度を評価.
比較手法としては,過去k日間またはkヶ月間(k=1,3,6,12)のクエリの出現頻度に基づいて将来のクエリの出現頻度を予測する手法と,過去のすべてのクエリの出現頻度に基づく手法を使用.
クエリのデータとしてBingのクエリログを使用.

クエリの出現頻度の予測の実験では,1日毎のクエリの出現頻度の予測では提案手法の方が良かったが,1ヶ月毎の予測では過去1日のデータを使ったベースライン手法の方が良い結果となった.提案手法で1ヶ月毎の予測精度が良くなかったのは,クエリの出現頻度を1ヶ月単位で見てしまうと,月によって差のあるクエリがそれほど多く無かったためである.提案手法では,決まった曜日に開催されるレース(「nascar」)や1月に開催される「australian open」といったクエリは上手く出現頻度を予測できていたが,例えばドラマが終了したために急にそのドラマに関するクエリが増えたときに対応できないなどという問題もある.

補完クエリのランキングの精度では,ベースライン手法よりも提案手法のほうが有効であることが示せ,提案手法では例えば「when to plant」に対して「when to plant tulips」と「when to plant tomatoes」のどちらを上位に提示すべきかを時期によって上手く考慮できていた.


-SIGIR, 論文紹介
-

関連記事

Addressing people’s information needs directly in a web search result page

Chilton, Lydia B. Teevan, Jaime In Proc. of WWW 2011 http://dl.acm.org/citation.cfm?id=1963413 概要 最近 …

Personalized Models of Search Satisfaction

Ahmed Hassan Ryen W. White In Proc. of CIKM 2013 概要 ユーザが検索セッションに対して満足したか,不満足だったかを知ることは検索エンジンの質を高めるうえ …

Experiments with a Venue-Centric Model for Personalisedand Time-Aware Venue Suggestion

Deveaud, Romain and Albakour, M-Dyaa and Macdonald, Craig and Ounis, Iadh In Proc. of CIKM 2015 概要 ユ …

Analyzing and evaluating query reformulation strategies in web search logs

Huang, Jeff Efthimiadis, Efthimis N. In Proc. of CIKM2009 http://dl.acm.org/citation.cfm?id=1645966 …

Your neighbors affect your ratings: on geographical neighborhood influence to rating prediction

Hu, Longke and Sun, Aixin and Liu, Yong In Proc. of SIGIR 2014 概要 店sの周辺の店の情報を利用することで、ユーザuのsに対するレーティン …