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

関連記事

TwitterRank: Finding Topic-sensitive Influential Twitterers

Weng, Jianshu Lim, Ee-Peng Jiang, Jing He, Qi In Proc. of WSDM 2010 http://dl.acm.org/citation.cfm?i …

Where you Instagram?: Associating Your Instagram Photos with Points of Interest

Li, Xutao and Pham, Tuan-Anh Nguyen and Cong, Gao and Yuan, Quan and Li, Xiao-Li and Krishnaswamy, S …

【論文紹介】How Much Novelty is Relevant?: It Depends on Your Curiosity

Zhao, Pengfei and Lee, Dik Lun In Proc. of SIGIR 2016 概要 心理学の分野では、対象物の刺激が強すぎても弱すぎても人は惹き付けられず、中程度のとき最 …

Spatio-Temporal Topic Modeling in Mobile Social Media for Location Recommendation

Bo, Hu and Mohsen, Jamali and Martin, Ester In Proc. of ICDM 2013 概要 チェックインサービス等でのユーザと場所と時刻を考慮したモデル化 …

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に対するレーティン …