投稿日: SIGIR 論文紹介

Toward self-correcting search engines: using underperforming queries to improve search

Hassan, Ahmed
White, Ryen W.
Wang, Yi-Min
In Proc. of SIGIR 2013
http://dl.acm.org/citation.cfm?id=2484043

概要

検索エンジンでは一般にどのクエリに対しても同一のランキングアルゴリズムが使用される.そのため,クエリの種類によっては検索精度に差が生じる.この論文では,精度の悪いクエリの種類を自動的に推定して,かつその種類専用のランキングアルゴリズム(ranker)を使うことで全体的な検索精度の向上を目的としている.

全体の処理の流れ

まず,この研究ではあらゆるクエリは要素がバイナリ値の140次元のベクトルで表される.たとえば,1次元目はクエリが英語であれば1,2次元目は文字数が10以上であれば1,といったようなもの.そのため,クエリの種類としては2の140乗種類が存在するが,この研究ではその中でも頻出する種類だけを考慮する.
頻出する種類をSATグループとDSATグループに分割する.SATに属する種類のクエリは,そのクエリを用いた多くのユーザが検索を満足して終えたことを表している.そのため,ユーザが入力したクエリがSATに属する場合は,従来通りの検索アルゴリズムを使えば良い.一方,DSATに属する種類のクエリは,そのクエリを用いた多くのユーザが検索を不満足な状態で終えたことを表している.そのため,クエリの種類(ベクトル)ごとにlearning-to-rankを用いてその種類専用のランキングアルゴリズムを用意する.ユーザが入力したクエリがDSATに属する場合は,そのクエリの種類に対応するランキングアルゴリズムを使用する.

クエリの種類ごとのSAT・DSATの推定

まずは,DSATに該当するクエリを集める.1つの検索セッションの中で検索エンジンの切り替えが発生したクエリはユーザが検索結果に不満足であったクエリであることが多いということが過去の研究で示されているため,クエリログからそのようなクエリを集める.ただし,不満足である場合ばかりではないので,既存研究で提案された素性を用いて本当に不満足であったクエリとそうでないクエリを分類する.

本当に不満足であった各クエリをベクトルに変換し,FP-Growthというアルゴリズムを用いて不満足に頻出するベクトルを求める.しかし,たとえば英語のクエリでかつアメリカ国内で入力されたクエリがDSATで頻出するとわかった場合,
DSATならば(英語のクエリ,アメリカ国内で入力)は成り立つとしても,(英語のクエリ,アメリカ国内で入力)ならばDSATは成り立たない.そこで,両方向の確率が高いパターンをDSATとする必要がある.

そのために,クエリログからクリック数が閾値以上のクエリと最後に30秒以上ページが閲覧されたクエリは真にSATなクエリであるとして抽出し,DSATと同様に各クエリをベクトルに変換したのち,SATに頻出するベクトルを求める.A=(英語のクエリ,アメリカ国内で入力)としたときに
 DSAT correlation=\frac{P(A,DSAT)}{P(A)P(DSAT)}
が閾値以上のベクトルを真のDSATとする.


-SIGIR, 論文紹介

関連記事

What are you looking for? An eye-tracking study of information usage in Web search

Cutrell, Edward Guan, Zhiwei In Proc. of CHI2007 http://dl.acm.org/citation.cfm?id=1240690 概要 デスクトップ …

Modelling User Interest for Zero-query Ranking

Liu Yang, Qi Guo, Yang Song, Sha Meng, Milad Shokouhi, Kieran McDonald, and W. Bruce Croft In Proc. …

【論文紹介】The automated acquisition of suggestions from tweets

Dong, Li and Wei, Furu and Duan, Yajuan and Liu, Xiaohua and Zhou, Ming and Xu, Ke AAAI 2013 ACM, PD …

【論文紹介】Content-boosted matrix factorization for recommender systems: experiments with recipe recommendation

Forbes, Peter and Zhu, Mu RecSys 2011 ACM, PDF 概要 ユーザのアイテムに対するレーティングを予測する際に、アイテムの構成要素を考慮した、Matrix Fa …

【論文紹介】Anticipating Information Needs Based on Check-in Activity

Benetka, Jan R. and Balog, Krisztian and Nørvåg, Kjetil WSDM 2017 ACM, PDF 概要 ユーザがある場所(たとえばレストラン)から移 …