投稿日: 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, 論文紹介
-

関連記事

Learning from the Past: Answering New Questions with Past Answers

A. Shtok, G. Dror, Y. Maarek, and I. Szpektor In Proc. of WWW 2012 http://dl.acm.org/citation.cfm?id …

Identifying task-based sessions in search engine query logs

Lucchese, Claudio Orlando, Salvatore Perego, Raffaele Silvestri, Fabrizio Tolomei, Gabriele In Proc. …

【論文紹介】Bartering Books to Beers: A Recommender System for Exchange Platforms

Rappaz, Jérémie and Vladarean, Maria-Luiza and McAuley, Julian and Catasta, Michele WSDM 2017 ACM, P …

Are Web User Comments Useful for Search?

Wai Gen Yee Andrew Yates Shizhu Liu Ophir Frieder In Proc. of LSDS-IR Workshop 2009 概要 YouTubeの動画を検索 …

Deciphering Mobile Search Patterns: A Study of Yahoo! Mobile Search Queries

Yi, Jeonghee Maghoul, Farzin Pedersen, Jan In Proc. of WWW2008 http://dl.acm.org/citation.cfm?id=136 …