Interleavingについて - tsubosakaの日記

情報検索において検索手法の結果を評価する方法の手法の一つにInterleavingという方法がある。最近その辺についてちょっと読んでいたのでまとめておく。

検索エンジンにおいては何らかのRanking Function(http://en.wikipedia.org/wiki/Ranking_function)を用いて、与えられたクエリに対する検索結果を並び替える。

例えば"餃子レシピ"というクエリでGoogleで今検索したところ

1. http://cookpad.com/recipe/316319 (☆ほっぺが落ちちゃう　餃子☆)
2. http://cookpad.com/category/836 (餃子・シュウマイレシピ 306品)
3. http://matome.naver.jp/odai/2133424266153597701 (絶品餃子！！肉汁がやばい究極のギョーザのレシピを厳選！#レシピ #ギョーザ)

みたいな順番ででる。このとき別の評価関数を使えば

1. http://cookpad.com/recipe/316319 (☆ほっぺが落ちちゃう　餃子☆)
2. http://matome.naver.jp/odai/2133424266153597701 (絶品餃子！！肉汁がやばい究極のギョーザのレシピを厳選！#レシピ #ギョーザ)
3. http://cookpad.com/category/836 (餃子・シュウマイレシピ 306品)

上のように並び替えられる可能性もある。

このときどちらがいい検索結果なのかを判定するという問題がでてくる。

一つは検索の品質についてのガイドラインをさだめ、人手によりプロの評価者が検索結果を評価するという方法がある。例えばGoogleでもガイドラインを公開している。

しかし人手による評価だとすべてのクエリに対応は難しく、またパーソナライズ検索のような個々人によって検索結果が変わるような場合対応するのが難しい。そのためオンラインで実際にテストを行って、よりクリックされる方を採用するという方法が一般的には行われる。(実際には人手による評価である程度チェックした後、オンラインでのテストが行われることが多い)

この時、一つの方法としてはA/Bテストがある。バケットごとに別々の評価関数で並び替えた結果を出して、バケットごとのCTRなどを計測してどちらがよいかを決定する。しかしこの場合だと新しいアルゴリズムを入れた時に結果が大きく変わってしまう可能性があり、場合によっては好ましくない。そのため二つの評価関数によって得られた二つのリストの結果を混ぜあわせて表示するInterleavingという手法がある。

手法について

手法についての以下の記述は文献[1]を参考にした。なお文献[1]はWSDM 2013のBest Paperとなっている。

Balanced Interleaving [4]

各リストの順位の高いものから取っていく。また同点の場合はどちらを先にとるかはランダムで決定する。
例えばリスト1の結果が(a,b,c)、リスト2の結果が(c,a,e)だった場合、リスト1から取っていく場合

まずリスト1の一番目のaをとる
次にリスト2の一番目のcをとる
最後にリスト1の二番目のbをとる
結果のリストは(a,c,b)となる

リスト2から取っていく場合

まずリスト2の一番目のcをとる
次にリスト1の一番目のaをとる
最後にリスト2の二番目のaはすでにとられてるのでリスト1の二番目のbをとる
結果のリストは(c,a,b)となる

しかし、この方法には問題があって例えばa,b,cランダムにどれかをクリックするユーザがいたとしたらどちらの結果においても(a,b)がクリックされるとリスト1がよいとみなされリスト1の結果のクリック数はリスト2のクリック数の2倍となる。このため次に挙げられるTeam Draftという方法がある。

Team Draft [3]

これはドラフトのように一回のとるときにコイン投げを行なって、勝ったほうが自分のリストの上にあるものをとっていくという手法である。リスト1の結果が(a,b,c)、リスト2の結果が(c,a,e)だった場合結果は4通りあり

まずリスト1の一番目のaをとる
次にリスト2の一番目のcをとる
最後にリスト1の二番目のbをとる
結果のリストは(a,c,b)となる

まずリスト1の一番目のaをとる
次にリスト2の一番目のcをとる
最後にリスト2の三番目のeをとる (aをは取られてるので)
結果のリストは(a,c,e)となる

リスト2から始める場合も同様にすると結果のリストは

(c,a,b)
(c,a,e)

となる。

しかしこの方法でも問題が発生して、例えばリスト1の結果が(a,b,A)、リスト2の結果が(b,A,a)でAの文章のみが良かった場合、リスト2の方がAを上位に持ってこれているが、Team Draftの結果だと

(a:1, b:2, A:1)
(a:1, b:2, A:2)
(b:2, a:1, A:1)
(b:2, a:1, A:2)

となっており、Aのみがクリックされるとどちらがよいかを結論付けることができない。

Probabilistic Interleving [2]

Team Draftとどうようコイントスをしてどちらのリストから優先するかを決めるが、ペアでとるのではなく一回一回コイントスを行う。このため極端な話、リスト1から全て持って来られることもありえる。また上からとってくるのではなくリストの中から確率的にどの文章をとるか決める(ただし上位のものが高い確率でとられるようにする)

上の二つのような問題は発生しないが、確率的にすべてのリストの組み合わせが発生しうるのでもとのリストの両方からかけ離れた結果が得られることがある。また文献[1]においては二つのリストの差がでるまでに多くのクエリで評価する必要があるという実験的結果が得られている。

Optimized Interleaving [1]

Interleavingに必要な要素を定式化して最適化問題としてInterleavingしたリストの表示確率を計算する手法。

確率的な方法となっているが、まず可能なリストとしてリストA,BがあったときにInterleavingしたリストLが必ずTeam Draftなどのように二つのリストの上からとってきたものになるような制約を入れる。すなわちA=(a_1,a_2),B=(b_1,b_2)だった場合可能なリストとしてはL=(a_1,a_2),(b_1,b_2),(a_1,b_1)の3通りとする。例えば(a_2,b_1)などは含まない。また各リストの出現確率をp_iとする。

そしてbalanced interleavingの例で出した、ランダムに文章をクリックするユーザに対しては期待値が0となるようなcredit functionを設定する(credit functionはLのi番目がクリックされたときにどっちのリストにどの程度配分するかを表す)。

この制約のもとで例えばsensitivityが最大になるように最適化問題を解く。sensitivityはi番目の文章がクリックされたらAが勝つ確率、Bが勝つ確率のエントロピーとかをつかってその期待値を計算する(たとえばどれがクリックされてもAが絶対勝つようなリストはエントロピーが0となる)

まとめ

オンラインテストにおいて二つのRanking functionを比較するためのInterleavingという手法について紹介した。
この方法はCIKM, WSDMとかで一本ぐらいは大体出てる気がするけど日本ではあまり知られてないので参考になると幸いです。

参考文献

[1] Optimized Interleving for online retrieval evaluation, WSDM 2013
[2] A probabilistic method for inferring preferences from clicks, CIKM 2011
[3] How does clickthrough data reflect retrieval quality?, CIKM 2008
[4] Evaluating retrieval performance using clickthrough data. Text Mining 2003