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

関連記事

Semantic Annotation of Mobility Data using Social Media

Wu, Fei and Li, Zhenhui and Lee, Wang-Chien and Wang, Hongjian and Huang, Zhuojie In Proc. of WWW 20 …

On a Topic Model for Sentences

Balikas, Georgios and Amini, Massih-Reza and Clausel, Marianne In Proc. of SIGIR 2016 概要 通常のLDAでは文書ご …

Time-critical search

Mishra, Nina and White, Ryen W. and Ieong, Samuel and Horvitz, Eric In Proc. of SIGIR 2014 概要 一緒にいる人 …

Placing Videos on a Semantic Hierarchy for Search Result Navigation

Tan, Song Jiang, Yu-Gang Ngo, Chong-Wah ACM TOMM 2014 http://dl.acm.org/citation.cfm?id=2578394 概要 「 …

Spatial influence vs. community influence: modeling the global spread of social media

Kamath, Krishna Y. Caverlee, James Cheng, Zhiyuan Sui, Daniel Z. In Proc. of CIKM 2012 http://dl.acm …