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

関連記事

【論文紹介】Matrix factorization techniques for context aware recommendation

Baltrunas, Linas and Ludwig, Bernd and Ricci, Francesco RecSys 2011 Link 概要 コンテキストによるバイアスを考慮したレーティング …

How fresh do you want your search results?

Shiwen Cheng Anastasios Arvanitis Vagelis Hristidis In Proc. of CIKM 2013 概要 検索結果中の情報の鮮度に着目した研究はこれまで …

【論文紹介】What Makes a Link Successful on Wikipedia?

Dimitrov, Dimitar and Singer, Philipp and Lemmerich, Florian and Strohmaier, Markus In Proc. of WWW …

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 …

Personalized Models of Search Satisfaction

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