投稿日: WSDM 論文紹介

Efficient multiple-click models in web search

Guo, Fan
Liu, Chao
Wang, Yi Min
In Proc. of WSDM2009

概要

クリックモデルに関するこれまでの研究では、ユーザはクエリを入力して1度検索結果をクリックしたら検索を終えるというモデルであったが、この論文ではクエリを入力して複数回検索結果をクリックするモデルを提案している。提案モデルはindependent click model(ICM)とdependent click model(DCM)の2つ。

クリックモデルの精度検証方法

ユーザuが入力したクエリqと、qに対する上位10件の検索結果と、各検索結果をuがクリックしたか否かのデータが与えられる。クリックモデルでは、あるユーザの検索行動をいかに忠実にシミュレートできるかを検証することが目的であり、あるユーザのある検索行動が起きる確率を計算している。ユーザの行動データを複数のモデルに与えたときに、最も高い確率を計算したモデルが最も良いモデルと言える。

ICM

ユーザが1回だけ検索結果をクリックすることを想定したcascade modelと呼ばれる既存のモデルを複数回クリックに拡張したもの。クエリqを入力したユーザはi番目の文書d_{i}を確率r_{d_{i}}でクリックするという行動を1位から10位まで繰り返す。d_{i}より上位の文書をクリックしたかどうかはd_{i}をクリックするかどうかに影響しないので「independent」なモデル。r_{d_{i}}qに関する検索ログ中で、d_{i}がクリックされた回数/d_{i}が表示された回数によって求める。

DCM

d_{i}を確率r_{d_{i}}でクリックしたユーザは、確率\lambda_{i}d_{i+1}に進み、1-\lambda_{i}の確率で検索を止めるというモデル。d_{i}より上位の文書をクリックしたかどうかがd_{i}をクリックするかどうかに影響するので「dependent」なモデル。\lambda_{i}は以下で求める。
1-\frac{\sharp\:{\rm query\:sessions\:when\:last\:clicked\:position}=i}{\sharp\:{\rm query\:sessions\:when\:position}\:i\:{\rm is\:clicked}}

実験

Bingの検索ログから約11万件のクエリに対する約400万セッションを取得して訓練データとテストデータに分類。訓練データを用いてr_{d_{i}}\lambda_{i}を求める。
実験の結果、入力される頻度が高いクエリに対してはDCMの方が良い結果であった。また、First Clickの推定精度に関しては2つのモデル間で大きな差は無かったが、Last Clickの推定精度はDCMの方がICMよりも高かった。


-WSDM, 論文紹介

関連記事

Can social features help learning to rank youtube videos?

Chelaru, Sergiu Viorel Orellana-Rodriguez, Claudia Altingovde, Ismail Sengor In Proc. of WISE 2012 概 …

Exploring and exploiting user search behavior on mobile and tablet devices to improve search relevance

Song, Yang Ma, Hao Wang, Hongning Wang, Kuansan In Proc. of WWW 2013 http://dl.acm.org/citation.cfm? …

An Eye Tracking Study of the Effect of Target Rank on Web Search

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

Who Will You “@”?

Gong, Yeyun and Zhang, Qi and Sun, Xuyang and Huang, Xuanjing In Proc. of CIKM 2015 概要 Twitterではリプライ …

Mining long-term search history to improve search accuracy

Tan, Bin Shen, Xuehua Zhai, ChengXiang In Proc. of KDD2006 http://dl.acm.org/citation.cfm?id=1150493 …