はじめに
2つのシステムの性能やデザインを比較したいときには、A/Bテストを行うことがあります。UIの変更など、比較すべきシステムが多くないような場合で、かつ、たくさんのページビューがあるようなサービスを運用している場合にはA/Bテストでも良いかも知れません。しかし、比較すべきシステムが複数ある場合や、あまりページビューがない場合、A/Bテストで有意な結果を得るためには長い時間がかかってしまうことが知られています。
そこで注目を集めているのが、近年提案されたインターリービング（Interleaving（日：交互配置））という手法です。検索や推薦システム等のランキングを行うシステムにのみ適用が可能ですが、実験的にA/Bテストよりも10~100倍効率的であるということが知られています。この記事では最近の論文によって報告されているインターリービングの性能について、また、各種インターリービング手法とPythonモジュールinterleavingを使った実践方法について解説します。
なお、著者はNTCIR-13 OpenLiveQという、質問検索システムの性能をコンペ形式で競うイベントを運営しております。このイベントでは、実際に参加者の方が作成した質問検索システム（検索キーワードを入力して質問のランキングを返すシステム）の性能を、Yahoo!知恵袋上でのインターリービングによって評価する予定です。インターリービングの技術に興味を持たれた方、検索システムの構築に興味がある方、技術力を世に示したい方は是非ご参加を検討いただければ幸いです。
要約
- 概要：Joachimsにより初のインターリービング手法が提案された(Joachims 2002a, 2003)。代表的なインターリービング手法には、Balanced interleaving（均衡交互配置） (Joachims 2002a, Joachims 2003)、Team draft interleaving（チームドラフト交互配置） (Radlinski et al. 2008)、Probabilistic interleaving（確率的交互配置） (Hofmann et al. 2011)、Optimized interleaving（最適化交互配置） (Radlinski and Craswell 2013)がある。
- 性能：(Chapelle et al. 2012)のアメリカのYahoo!検索における実験、および、(Schuth et al. 2015a)の検索エンジンにおける実験から、**「インターリービングはA/Bテストより100倍効率的な場合があり、おおよその場合、10~100倍効率的で、A/Bテストより効率的でない場合は少ない」**といえる。
- 手法
- Balanced interleavingは「2つのランキングから交互に検索結果を最上位から順に選択し1つのランキングを生成する」インターリービング手法である。
- Team draft interleavingは「2つの検索結果を選ぶごとに先攻・後攻をランダムで決めながら、両ランキングから1つずつ、まだ用いられていない検索結果を上位から順に選択していく」インターリービング手法である。
- Probabilistic interleavingは「できるだけ各ランキング中の検索結果の順序を保持しつつも、相対的に低い確率で任意の順序での検索結果選択を許容する」インターリービング手法である。
- Optimized interlavingは「いくつかの制約のもと、生成されるランキングの感度の期待値を最大にするようなランキング提示確率を用いる」インターリービング手法である。
- Multileavingは3つ以上のランキング間の優劣を決定するための方法である。
- 実践：interleavingで上記のインターリービングを実践することができる。
インターリービングの概要
インターリービングが初めて論文として発表されたのは、おそらく、(Joachims 2002a)または(Joachims 2003)ではないかと思います（同著者のRanking SVM 論文(Joachims 2002b)の実験でこれを利用）。これらの論文中ではまだインターリービングという言葉は登場していませんでした。アイデアはシンプルで、**「2つのランキングから交互に検索結果を最上位から順に選択し1つのランキングを生成してユーザに提示する」**というものでした。以下に例を示します：
| 順位 | ランキングA | ランキングB |
|---|---|---|
| 1 | 001 | 004 |
| 2 | 002 | 005 |
| 3 | 003 | 006 |
ここでは、ランキングAとランキングBのどちらが良いのかを決めることを目的としており、001や002などは検索結果のIDを表すものとします。
どちらのランキングから先に検索結果を選択していくかによって、生成される結合ランキングが異なってきます。そのため、この2つのランキングから長さ3の結合ランキングは以下の2種類が生成されます：
| 順位 | 結合ランキング1 | 結合ランキング2 |
|---|---|---|
| 1 | 001 | 004 |
| 2 | 004 | 001 |
| 3 | 002 | 005 |
最初にランキングAから検索結果を選択していく場合には、ランキングAから検索結果001、ランキングBから検索結果004、最後にランキングAから検索結果002を選択して、最終的に001, 004, 002という結合ランキング1が生成されます。一方、最初にランキングBから検索結果を選択していく場合には、ランキングBから検索結果004、ランキングAから検索結果001、最後にランキングBから検索結果005を選択して、最終的に004, 001, 005という結合ランキング2が生成されます。詳しい手法については後述します。
あとは、これらの結合ランキングをユーザに対して提示し、どの検索結果がクリックされたのかを観察します。直感的には、多くのクリックがされた検索結果を含むランキングがより優れているということになります。例えば、上記結合ランキング1, 2をそれぞれ100人に提示し、150人が検索結果004のみをクリック、50人が検索結果001のみをクリックしたのであれば、ランキングBが優れているという結論を導くことができます。
その後の論文(Radlinski et al. 2008)では、このような手法に対し下記のようにInterleavingという名称が与えられました：
Joachims [12, 13] proposed a method for interleaving the rankings from a pair of retrieval functions so that clicks provide a blind preference judgment.
なお、最初の論文(Joachims 2002a, Joachims 2003)で提案された手法はBalanced interleavingと名付けられ、現在では以下の4種類が代表的なインターリービング手法となっています：
- Balanced interleaving（均衡交互配置） (Joachims 2002a, Joachims 2003)
- Team draft interleaving（チームドラフト交互配置） (Radlinski et al. 2008)
- Probabilistic interleaving（確率的交互配置） (Hofmann et al. 2011)
- Optimized interleaving（最適化交互配置） (Radlinski and Craswell 2013)
インターリービングがA/Bテストよりも優れていると考えられる点について、(Radlinski et al. 2008)は、「絶対評価」と「一対比較評価」について論じ、味や音のような感覚的なものの評価では「絶対評価」は難しく、「一対比較評価」がよく用いられることを挙げ、ランキングの評価においても「一対比較評価」が効果的であると主張しています。A/Bテストは、同じユーザが2つのランキングを比較しているわけではないので、「一対比較評価」ではありません。一方、インターリービングは同じユーザが2つのランキングを暗に比較することになるので、「一対比較評価」であると言えます。
例えば、非常に性能がよく似たランキングをA/Bテストで評価する場合と、インターリービングで評価する場合を考えます。極端なことを考えれば、A/Bテストの場合、最上位の結果がどちらも同等に良ければ、どちらのクリックスルーレートも変わらないでしょう。一方で、インターリービングによる評価は、ユーザに対して暗に選択を行わせることになるため（例えば、ランキングAの最上位から得られた1件目をクリックするか、ランキングBの最上位から得られた2件目をクリックするか）、差が生じやすくなります。
次の節では、実際に行われた大規模な実験の結果を紹介し、上記の直感が正しいのか、また、インターリービングが本当にA/Bテストより10~100倍効率的なのかについて解説します。
インターリービングの性能
ここでは「インターリービングはA/Bテストより10~100倍効率的」の根拠を示します。以下の説明からわかる通り、より正確には**「インターリービングはA/Bテストより100倍効率的な場合があり、おおよその場合、10~100倍効率的で、A/Bテストより効率的でない場合は少ない」**です。また、ここで「効率的である」とは、有意性検定に関わるある条件を満たすために必要なランキングの提示回数が少ないことを意味します。
(Chapelle et al. 2012)の7節では、アメリカのYahoo!検索エンジン上で行われたA/Bテストとインターリービングの比較を行い、4つのランキングの比較を行った場合、そのうち3ペアについては100倍以上、2ペアについては10倍以上効率化され、1ペアについては悪化したと報告しています。より詳細なデータを論文中より引用します：
(Chapelle et al. 2012)より引用
| B - A | C - A | D - A | C - B | D - B | D - C |
|---|---|---|---|---|---|
| 379.1 | 193.1 | 17.8 | 270.7 | 18.9 | 0.69 |
各列X-YはランキングXとランキングYの比較を表し、数値は(A/Bテストによって統計的有意な差が検出できる最小の表示回数)/(インターリービングによって統計的有意な差が検出できる最小の表示回数)を表しています。そのため、この数値が100以上であれば100倍以上効率的（ランキングの表示回数を1/100節約できる）であると言えます。
ランキングAは実験時のYahoo!のランキング、その他は改良版であり、ランキングCとDはパラメータが違うだけで同じ方法を使っています。事前のオフライン評価（nDCG@5）では、D, C, B, Aの順でnDCGが高く、DとCの相対的な差が非常に小さいことがわかっています。そのため、ランキングの差が極めて小さい場合以外は、インターリービングの方がA/Bテストよりも効率的である可能性があります。
ちなみに、優劣を誤って判断する確率を0.05よりも小さくしたい場合には、「B - A」、「C - A」、「C - B」のそれぞれに対して、インターリービングなら$10^5$, $10^4$, $10^4$回の提示が必要になり、A/Bテストなら$10^6$回でも不十分であることも報告されています。
(Schuth et al. 2015a)では、38ランキングペアに対して30億回の提示を行いChapelleらと似たような結果を報告しています（論文中では明記されていないがおそらくMicrosoft Bing上での実験）：
(Schuth et al. 2015a)より引用
We see that on average across the set of 38 experiments, 80% power with AB experiments is obtained with between $10^7$ and $10^8$ observations (queries). On the other hand, the same power is obtained with between $10^5$ and $10^6$ observations with TDI.
要約すると、80%の検出力を達成するためには、A/Bテストでは$10^7$ 〜 $10^8$回、インターリービングでは$10^5$ 〜 $10^6$回ほどランキングを提示する必要がある、と述べています。また、平均した場合には100倍ほどの差があることが、同論文のFigure 1から読み取ることができます。ちなみに、ここではインターリービングの一手法である、Team draft interleaving（引用中のTDI）が利用されています。こちらの結果からも、インターリービングはA/Bテストよりもかなり効率的であることが示唆されています。
Web検索のランキングに偏った話であり、A/Bテストよりも効率的ある場合の条件はまだはっきりしてはいませんが、以上の2つの論文の実験結果から、**「インターリービングはA/Bテストより10~100倍効率的」**と言っても良いのではないかと思います。
インターリービングの手法
最初のBalanced interleavingの提案に始まり、様々なインターリービング手法がこれまで提案されてきました。その中でも代表的な4種類の方法を以下で説明します。なお、これらの手法はすべてinterleavingで実装されています。
以下の説明では、2つのランキングA, B（検索結果IDのリスト）のインターリービングを目的とし、生成されるランキング（結合ランキング）をLとしてこれがk個の検索結果を含むものとします。擬似コードはPythonで書かれているものとします。
Balanced interleaving (Joachims 2002a, 2003)
(Joachims 2002a, 2003)で提案されたインターリービング手法は、後にBalanced interleavingと名付けられました。
Balanced interleavingは以下のように行われます：
L = [] # 生成されるランキング
k_A, k_B = 0, 0 # 各ランクキング中で参照している順位を表すポインタ
is_A_first = random_bit() # TrueかFalseをランダムで返す。最初にどちらのランキングの検索結果を利用するか決める。
while len(L) < k and k_A < len(A) and k_B < len(B):
if k_A < k_B or (k_A == k_B and is_A_first):
if not A[k_A] in L:
L.append(A[k_A]) # A[k_A]がすでにLに含まれていなければ末尾に追加
k_A += 1
else:
if not B[k_B] in L:
L.append(B[k_B]) # B[k_B]がすでにLに含まれていなければ末尾に追加
k_B += 1
- ランキングAとBのどちらから先に検索結果を選ぶのかを決める(
is_A_first) - 一方のランキングからそのポインタ(
k_Aork_B)が指す検索結果を選び、それがLに含まれていなければ末尾に追加する - ポインタに1を加算する
- もう一方のランキングに対して、2-3と同様のことを行う
- 2に戻る
Balanced interleavingの例を以下に示します：
| 順位 | ランキングA | ランキングB |
|---|---|---|
| 1 | 001 | 002 |
| 2 | 002 | 003 |
| 3 | 003 | 004 |
例えば、長さ3の結合ランキングを生成する場合、ランキングAを最初に選択した場合(is_A_first == True)には、下記の結合ランキング1に、ランキングBを最初に選択した場合には下記の結合ランキング2が生成されることになります：
| 順位 | 結合ランキング1 | 結合ランキング2 |
|---|---|---|
| 1 | 001 | 002 |
| 2 | 002 | 001 |
| 3 | 003 | 003 |
結合ランキング1は、ランキングAを最初に選択→ランキングAから検索結果001を選択・追加→ランキングBから検索結果002を選択・追加→ランキングAから検索結果002を選択、追加しない→ランキングBから検索結果003を選択・追加、のように生成されます。
一方、結合ランキング2は、ランキングBを最初に選択→ランキングBから検索結果002を選択・追加→ランキングAから検索結果001を選択・追加→ランキングBから検索結果003を選択・追加、のように生成されます。
あるユーザに結合ランキングを提示したときに、クリックされた検索結果の順位を記録し、これをC=[c1, c2, ...]とし、最も低い順位をc_max (C中の最大値)とします。このとき、以下のscore_Aとscore_Bの大小関係からランキングAとBのどちらが優れているかを判断することができます：
lowest = L[c_max] # クリックされた検索結果のうち最も下位にある検索結果
# A.index(x)はA中にxが含まれればそのインデックス、含まれなければlen(A)を返すものとする
l = min([A.index(lowest), B.index(lowest)]) # lowestのAおよびB中での順位のうち上位の方
score_A = len([c for c in C if c in A[:l+1]) # ランキングAのl位までの検索結果のうち、クリックされたものの数
score_B = len([c for c in C if c in B[:l+1]) # ランキングBのl位までの検索結果のうち、クリックされたものの数
ここでは、もしランキングAとBを別々に提示していたら何件クリックされていたのかをscore_Aとscore_Bで近似しています。
まず、各ランキングの何位までをユーザが閲覧するのかを推定し、これをlとしています。このlは「L中でクリックされた検索結果のうち最も下位にある検索結果」のAおよびB中での順位のうち、順位が高い方であると仮定しています。例えば、結合ランキングで検索結果001と002がクリックされた場合、検索結果002のAとBでの順位のうち高い方、つまり、「ランキングB中の検索結果002の順位」をlとして設定します。
あとは、ランキングAとBのl位までの検索結果中で何件の検索結果が結合ランキングにおいてクリックされたのかを数え、これらをそれぞれscore_A、score_Bとしています。結合ランキングを何度もユーザに提示し、score_A > score_B、score_A < score_B、score_A == score_Bであった回数を数えることで、ランキングAとBの優劣を決定することができます。
ただし、Balanced interleavingでは、ランキングAとBが類似する場合、ユーザがランダムに検索結果をクリックしても、どちらか一方が優れているという結果が得られることがあると指摘されています。例えば、上記の結合ランキング1および2では、1つの検索結果のみをクリックした場合、ランキングAとBの優劣は以下のようになります。
| クリックされた順位 | 結合ランキング1 | 結合ランキング2 |
|---|---|---|
| 1 | A > B | A < B |
| 2 | A < B | A > B |
| 3 | A < B | A < B |
もし、全てのユーザが一様な確率で1つの検索結果をクリックすれば、ランキングBの方がAよりも優れているという結論が得られてしまいます。このランダムクリックに対するバイアスがBalanced interleavingの欠点であるとされ、下記で述べるような別のインターリービング手法が提案されてきました。
Team draft interleaving (Radlinski et al. 2008)
(Radlinski et al. 2008)で提案されたTeam draft interleavingはBalanced interleavingよりも簡潔で、性能的にも優れていることが示されています。Team draft interleavingは、しばしば、**「2つのチームを作る際に、まず両チームのキャプテンを決め、キャプテンが互いに自分が欲しい選手を交互に選んでいくことで自チームを構成する」**様に例えられます。
Team draft interleavingのアルゴリズムは以下の通りです：
L = [] # 生成されるランキング
team_A, team_B = [], [] # 各ランクキングから選ばれた検索結果
while len(L) < k and len(set(A)-set(L)) > 0 and len(set(B)-set(L)) > 0:
is_A_first = random_bit() # TrueかFalseをランダムで返す
if len(team_A) < len(team_B) or (len(team_A) == len(team_B) and is_A_first):
r = [r for r in A if not r in L][0] # Lに含まれていないAの検索結果のうち、最上位の検索結果
L.append(r)
team_A.append(r)
else:
r = [r for r in B if not r in L][0] # Lに含まれていないBの検索結果のうち、最上位の検索結果
L.append(r)
team_B.append(r)
- ランキングAとBのどちらから先に検索結果を選ぶのかを決める(
is_A_first) - 一方のランキングから
Lに含まれていない検索結果のうち最上位のものを選びLの末尾に追加する - そのランキングの「チーム」(
team_Aorteam_B)に2で追加された検索結果を追加する - もう一方のランキングに対して、2-3と同様のことを行う
- 1に戻る
Balanced interleavingと異なり、検索結果は1度に、両ランキングから1つずつ、計2つずつ選ばれ、どちらのランキングから先に選ぶかはその都度ランダムで決定されます。
Balanced interleavingで用いたランキングAとBの例の場合、Team draft interleavingでも全く同じ結合ランキングが得られます（ただし、チーム割当まで考慮すると、Balanced interleavingとは異なり、4種類のランキングが生成される（後述））。
一方、以下の例では、Balanced interleavingとTeam draft interleavingでは異なる結合ランキングが得られます：
| 順位 | ランキングA | ランキングB |
|---|---|---|
| 1 | 001 | 004 |
| 2 | 002 | 005 |
| 3 | 003 | 006 |
Balanced interleavingの場合（長さ3）
| 順位 |結合ランキング1 | 結合ランキング2 |
|--:|:-:|:-:|:-:|:-:|
|1| 001 | 004 |
|2| 004 | 001 |
|3| 002 | 005 |
Team draft interleavingの場合（長さ3）（括弧中の記号はどちらのランキングから選ばれたのかを表す）
| 順位 | 結合ランキング1 | 結合ランキング2 | 結合ランキング3 | 結合ランキング4 |
|---|---|---|---|---|
| 1 | 001 (A) | 001 (A) | 004 (B) | 004 (B) |
| 2 | 004 (B) | 004 (B) | 001 (A) | 001 (A) |
| 3 | 002 (A) | 005 (B) | 002 (A) | 005 (B) |
Team draft interleavingの結合ランキング1は、ランキングAを最初に選択→ランキングAから検索結果001を選択・追加→ランキングBから検索結果004を選択・追加→ランキングAを最初に選択→ランキングAから検索結果002を選択・追加、のように生成されます。
結合ランキング3は、ランキングBを最初に選択→ランキングBから検索結果004を選択・追加→ランキングAから検索結果001を選択・追加→ランキングAを最初に選択→ランキングAから検索結果002を選択・追加、のように生成されます。
このように、検索結果を2個追加するごとに、どちらが先に検索結果を選ぶか（先攻・後攻）が入れ替わることがあります。
Team draft interleavingにおいて、ランキングの優劣の決定は非常にシンプルです。Balanced interleavingのように、各ランキングに対してあるスコアを決めてこれを比較することになりますが、これは「結合ランキングL中でクリックされた検索結果のうち、チームに所属する検索結果(team_A or team_B)の数」となります。
しかしながら、やはり、Team draft interleavingにも問題があります。Balanced interleavingで用いたランキングAとBの例から、チーム割当の違いまで考慮した場合には、以下の4種類の結合ランキング（長さ3）が得られます：
比較対象のランキング
| 順位 | ランキングA | ランキングB |
|---|---|---|
| 1 | 001 | 002 |
| 2 | 002 | 003 |
| 3 | 003 | 004 |
結合ランキング
（括弧中の記号はどちらのランキングから選ばれたのかを表す）
| 順位 | 結合ランキング1 | 結合ランキング2 | 結合ランキング3 | 結合ランキング4 |
|---|---|---|---|---|
| 1 | 001 (A) | 001 (A) | 002 (B) | 002 (B) |
| 2 | 002 (B) | 002 (B) | 001 (A) | 001 (A) |
| 3 | 003 (A) | 003 (B) | 003 (A) | 003 (B) |
例えば、ここで検索結果003だけがクリックに値するような内容であり、他の検索結果はまったくクリックされないような状況を考えます。このとき、ランキングBの方が明らかに良いランキングである（検索結果003をランキングAの場合よりもより上位に順位付けている）のにも関わらず、期待値的にはランキングAもBも同等に良いという結果が得られてしまうことになります。これは、4種類の結合ランキングはすべて同じ確率で生成され、検索結果003のみがクリックされる場合、結合ランキング1, 3でAが、結合ランキング2, 4でBが良いと判断されるためです。そのため、Balanced interleavingで起こってしまったようなランダムクリックに対するバイアスの問題ではなく、**感度が低い (Low sensitivity)（ランキングの善し悪しに差があるにも関わらず区別できない）**という問題がTeam draft interleavingにはあります。
Probabilistic interleaving (Hofmann et al. 2011)
Balanced interleavingとTeam draft interleavingの問題点を指摘しつつ、新たな手法の提案を行ったのが(Hofmann et al. 2011)です。Probabilistic interleavingでは、できるだけ各ランキング中の検索結果の順序を保持しつつも、相対的に低い確率で任意の順序での検索結果選択を許容する、というのが基本的なアイデアとなります。
Team draft interleavingでは、まだ結合ランキングに追加されていない検索結果のうち、最上位のものを決定的に選択していました。これに対して、Probabilistic interleavingでは以下の順位のみに依存する確率で検索結果を確率的に選択します：
$P_R(d) \propto 1/r_R(d)^{\tau}$
ここで、$P_R(d)$はランキング$R$中の検索結果$d$が選択される確率であり、$r_R(d)$はランキング$R$中での検索結果$d$の順位、$\tau$はパラメータであり論文中では$\tau=3$が用いられています。
上記の式が意味することは、ランキング中$r$位の検索結果は$r$の$\tau$乗に反比例する確率で選択されるということです。$\tau=3$のとき、1位の検索結果は1、2位の検索結果は1/8、3位の検索結果は1/27というように、順位が下がるにつれて急激に確率が下がるようになっています。
検索結果の選択は、非復元抽出によって行われ、また、既に結合ランキングに含まれる検索結果集合も除外されます。そのため、結合ランキング中のある時点において選択可能な検索結果集合を$D=R \cap L$（ランキング$R$と結合ランキング$L$を集合と見なしたときの積集合）としたとき、ランキング$R$中で検索結果$d$が選択される確率は厳密には以下のようになります：
$P_R(d) = \frac{1/r_R(d)^{\tau}}{\sum_{d' \in D}1/r_R(d')^{\tau}}$
Probabilistic interleavingのアルゴリズムは以下のようになります：
def probabilistic_selection(R, L, tau=3.0):
'''
検索結果選択確率
R: ランキングを表すlist
L: 結合ランキングを表すlist
tau: パラメータ（デフォルト：3.0）
'''
result = []
prob_sum = 0.0
for i, d in enumerate(R):
p = 1.0 / (i+1) ** tau if not d in L else 0.0
prob_sum += p
result.append(p)
result = [p / prob_sum for p in result]
return result
L = [] # 生成されるランキング
team_A, team_B = [], [] # 各ランクキングから選ばれた検索結果
while len(L) < k and len(set(A)-set(L)) > 0 and len(set(B)-set(L)) > 0:
is_A_selected = random_bit() # TrueかFalseをランダムで返す
selected_ranking = A if is_A_selected else B # ランキングを選択
selected_team = team_A if is_A_selected else team_B # チームを選択
probs = probabilistic_selection(selected_ranking, L)
r = multinomial_sampling(selected_ranking, probs) # multinomial_sampling(R, probs)はR[i]を確率probs[i]で選択
L.append(r)
selected_team.append(r)
- ランキングAとBのどちらから検索結果を選ぶのかを決める(
is_A_selected) - 一方のランキングから
Lに含まれていない検索結果のうち、確率$P_R(d)$で検索結果$d$を選択しLの末尾に追加する - そのランキングの「チーム」(
team_Aorteam_B)に2で追加された検索結果を追加する - 1に戻る
結合ランキングがユーザに提示されクリックが行われたとき、ランキングの優劣の決定はTeam draft interleavingと同じように行うことができます。論文中の4.3節では、ある結合ランキングを生成しうるすべてのチーム割当を考慮した、より洗練された手法が提案されていますがここでは割愛します。
Probabilistic interleavingでは、Balanced interleavingで起こっていたようなランダムクリックに対するバイアスや、Team draft interleavingで問題となっていた低い感度の問題を解消することができると言われています。前者の問題が起こらない理由として、結合ランキングに用いられる両ランキングの検索結果数の期待値は同じ（ランダムにクリックされても同等の性能であると評価される）であることが挙げられています。また、後者の問題が起こらない理由を説明するために、Team draft interleavingで問題があった例題へProbabilistic interleavingを適用してみます：
（チームの割当を考慮すると全48通りあるが、スペースを節約するためにチーム割当の違いはここでは無視している）
| 順位 | 結合ランキング1 | 結合ランキング2 | 結合ランキング3 | 結合ランキング4 | 結合ランキング5 | 結合ランキング6 | 合計 |
|---|---|---|---|---|---|---|---|
| 1 | 001 | 001 | 002 | 002 | 003 | 003 | |
| 2 | 002 | 003 | 001 | 003 | 001 | 002 | |
| 3 | 003 | 002 | 003 | 001 | 002 | 001 | |
| 確率 | 0.185 | 0.025 | 0.144 | 0.188 | 0.025 | 0.029 | 0.595 |
ここで、「確率」とは「検索結果003のみがクリックされたときに、Bが勝つ結合ランキングが生成される確率」を表します（後に計算例を示します）。この合計値が0.5よりも大きいため、期待値的にはランキングBが期待通り優れていると判断されることになり、Team draft interleavingの低い感度の問題が解決されていることがわかります。もちろん、この例だけではProbabilistic interleavingの感度が高いことを示したことにはなりませんが、少なくともTeam draft interleavingで起こる問題はProbabilistic interleavingでは起こらないことになります。
もう少し「検索結果003のみがクリックされたときに、Bが勝つ結合ランキングが生成される確率」を詳しく解説してみます。
例えば、結合ランキング1「001, 002, 003」が生成されたとき、考えられるチーム割当は以下の1.1 ~ 1.8の8通りになります。
（括弧中の記号はどちらのランキングから選ばれたのかを表す）
| 順位 | 1.1 | 1.2 | 1.3 | 1.4 | 1.5 | 1.6 | 1.7 | 1.8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 001 (A) | 001 (A) | 001 (A) | 001 (A) | 001 (B) | 001 (B) | 001 (B) | 001 (B) |
| 2 | 002 (A) | 002 (A) | 002 (B) | 002 (B) | 002 (A) | 002 (A) | 002 (B) | 002 (B) |
| 3 | 003 (A) | 003 (B) | 003 (A) | 003 (B) | 003 (A) | 003 (B) | 003 (A) | 003 (B) |
| 生成確率 | 0.083 | 0.083 | 0.096 | 0.096 | 0.003 | 0.003 | 0.004 | 0.004 |
上記の「生成確率」は、例えば、1.1の場合、0.5*1/(1+1/8+1/27) * 0.5*1/8/(1/8+1/27) * 0.5と計算することができます。これは、まずランキングAを選ぶ確率が0.5で、このうち1位の001を選ぶ確率が1/(1+1/8+1/27)、次にランキングAを選ぶ確率が0.5で、002と003のうち2位の002を選ぶ確率が1/8/(1/8+1/27)、最後にランキングAを選ぶ確率も0.5で、検索結果は003だけしか残っていないので、無条件にこれを選ぶことになります。これらのチーム割当のうち、検索結果003のみがクリックされた場合にランキングBが優れていると判断されるのは、1.2, 1.4, 1.6, 1.8の4種類となります。これらの確率を足し合わせたものが、「検索結果003のみがクリックされたときに、Bが勝つ結合ランキングが生成される確率」となります。すなわち、結合ランキング1の場合、0.185となります。
Optimized interleaving (Radlinski and Craswell 2013)
Team draft interleavingでは、ランダムクリックに対するバイアスの問題は解決され、一方、その低い感度が問題とされていました。Optimized interleavingでは、いくつかの制約の下、この感度の期待値を最適化（最大化）するような結合ランキングを優先的に提示するインターリービング手法となっています。
(Radlinski and Craswell 2013)では、以下のような制約を結合ランキングは満たす必要があると主張しました。
制約1
**結合ランキングは元となるランキングと大きく異なってはならない。**つまり、どちらかのランキングか、その中間的なランキングでなくてはならない。より厳密には、結合ランキングの任意の順位までの検索結果は、各ランキングのある順位$i$, $j$までの検索結果の和集合でなくてはならない：
$\forall k \geq 0, \exists i, j \geq 0, L_{1:k}=A_{1:i} \cup B_{1:j}$
ここで、あるランキング$R$の$R_{1:k}$は、1位から$k$位までの検索結果集合としています（ただし、$k=0$のとき、$R_{1:k}$は空集合とする）。
この条件が満たされるとき、結合ランキングは（元となる両ランキングに重複がなければ）、元となるランキングの検索結果の順序を保持することになります。つまり、どちらかのランキングで検索結果$d$が$d'$よりも上位に順位付けされている場合、結合ランキングでも検索結果$d$が$d'$よりも上位に順位付けされていることになります。
制約2
結合ランキングに対してランダムなクリックを行った場合、両ランキングのいずれかが優れているという結論を導いてはならない。
この制約を詳しく説明するためには、結合ランキング$L_i$の提示確率$p_i$、および、結合ランキング$L_i$の$j$番目の検索結果がクリックされた時にランキングAが得られるクレジット（得点）$\delta_j(L_i)$を導入する必要があります。
Optimized interleavingでは、制約1を満たすような全ての結合ランキングを提示する可能性があり、それぞれの結合ランキングには提示確率が与えられています。ユーザに結合ランキングを提示する際には、この提示確率に従って結合ランキングを選択することになります。Optimized interleavingでは、この提示確率を変数として、感度を最大化するような提示確率を決定します。
また、Optimized interleavingでは、与えられた2つのランキングの優劣を決定するためにクレジット関数を用います。クレジットが正であれば、ランキングAが優れている、クレジットが負であればランキングBが優れている、0であれば優劣がつかないということを意味します。結合ランキング$L_i$の$j$番目の検索結果がクリックされた時にランキングAが得られるクレジットは、関数$\delta_j(L_i)$によって決定され、以下の条件を満たす任意の関数を設定可能です：
$r_A(l_{i, j}) < r_B(l_{i, j}) \Rightarrow \delta_j(L_i) > 0$
$r_A(l_{i, j}) > r_B(l_{i, j}) \Rightarrow \delta_j(L_i) < 0$
ただし、$r_R(d)$はランキング$R$中での検索結果$d$の順位（$d$が含まれてない時は、$|R|+1$とする）、$l_{i,j}$は結合ランキング$L_i$の$j$番目の検索結果です。つまり、上記の式は、もしクリックされた検索結果のランキングA中の順位がランキングBよりも上であれば、クレジットは必ず正でなくてはならず、ランキングB中の順位がランキングAよりも上であれば、クレジットは負でなくてはならない、ということを意味します。
論文中では、以下のような関数を例としてあげています：
$\delta_j(L_i)=r_B(l_{i, j})-r_A(l_{i, j})$（両ランキングにおける順位の差）
$\delta_j(L_i)=1/r_A(l_{i, j})-1/r_B(l_{i, j})$（両ランキングにおける順位の逆数の差）
さて、ここで本題に戻って、**「結合ランキングに対してランダムなクリックを行った場合、両ランキングのいずれかが優れているという結論を導いてはならない」**という制約を定式化します。より厳密には、ある任意の$m\geq1$と$\eta \geq 1$に対して、結合ランキング中の上位$m$件中で$\eta$回のランダムクリックが行われた場合のクレジットの期待値は0でなくてはならない、と解釈できます。すなわち、制約2は以下のように表現することができます：
$\forall m, \eta \geq1, E[\sum_{j \in C_{m, \eta}}\delta_j(L_i)] = \sum_{L_i, C_{m, \eta}} P(L_i, C_{m, \eta}) \sum_{j \in C_{m, \eta}} \delta_j(L_i) = 0$
ここでは、結合ランキング$L_i$とクリックされた順位の集合$C_{m, \eta}$（ただし、このクリックは上位$m$件中で$\eta$回行われたものとする）が確率変数であり、$P(L_i, C_{m, \eta})$は結合ランキング$L_i$が提示され、かつ、順位$j \in C_{m, \eta}$へのクリックがユーザから得られる確率を表します。また、$\sum_{j \in C_{m, \eta}}\delta_j(L_i)$がクリック$C_{m, \eta}$が得られたときのクレジットの合計値を表し、これの期待値が0であることが制約となります。
この制約は更に簡略することが可能で、上位$m$件中へのクリックが結合ランキングに関わらずランダムであること、つまり、結合ランキングの提示確率と独立であること（$P(L_i, C_{m, \eta})=P(L_i)P(C_{m, \eta})$）、および、ある順位の検索結果が確率$1/m$でクリックされることを利用します：
$\forall m, \eta \geq1, E[\sum_{j \in C_{m, \eta}}\delta_j(L_i)] = \sum_{L_i} P(L_i) \sum_{C_{m, \eta}} P(C_{m, \eta}) \sum_{j \in C_{m, \eta}} \delta_j(L_i) = 0$
ここで、$\sum_{C_{m, \eta}}P(C_{m, \eta}) \sum_{j \in C_{m, \eta}} \delta_j(L_i)$は$C_{m, \eta}$を確率変数とした$\sum_{j \in C_{m, \eta}} \delta_j(L_i)$の期待値と解釈でき、$\eta=1$の場合の期待値$\frac{1}{m} \sum^m_{j = 1} \delta_j(L_i)$の$\eta$倍となります。そのため、より簡略化された制約式は、以下のようになります：
$\forall m, \eta \geq1, E[\sum_{j \in C_{m, \eta}}\delta_j(L_i)] = \sum_{L_i} P(L_i) \frac{\eta}{m} \sum^m_{j = 1} \delta_j(L_i) = 0$
さらに、$p_i \equiv P(L_i)$、$m$と$\eta$は定数であるため、最終的な制約式は以下の通りです：
$\forall m \geq 1, \sum_{L_i} p_i \sum^m_{j = 1} \delta_j(L_i) = 0$
感度（目的関数）
最適化問題の目的関数は感度の期待値となります。感度として、ある結合ランキング上でどちらのランキングが優れていると判断されるかの確率のエントロピーが提案されています。これを説明するために、ある結合ランキング$L_i$において、順位に依存する1回のランダムクリックでランキングAが優れていると判断される確率$P(A|L_i)$、ランキングBが優れていると判断される確率$P(B|L_i)$、さらに、優劣がつかない確率$P(T|L_i)$を導入します：
$P(A|L_i)=\sum_{j, \delta_j(L_i)>0} P(l_{i, j})$（$\delta_j(L_i)>0$であるような検索結果のいずれかがクリックされる確率）
$P(B|L_i)=\sum_{j, \delta_j(L_i)<0} P(l_{i, j})$（$\delta_j(L_i)<0$であるような検索結果のいずれかがクリックされる確率）
$P(T|L_i)=\sum_{j, \delta_j(L_i)=0} P(l_{i, j})$（$\delta_j(L_i)=0$であるような検索結果のいずれかがクリックされる確率）
論文中ではこの順位に依存したランダムクリックが順位の逆数に比例することを仮定しています（$P(l_{i, j}) \propto 1/j$、つまり、$P(l_{i, j}) = \frac{1/j}{\sum^{|L_i|}_{j'=1}1/j'}$）．
ここで、「ある結合ランキング上で優劣がつくとわかったときにどちらのランキングが優れていると判断されるかの確率のエントロピー」は、以下のように定義することができます：
$h(L_i) = - \sum_{R \in { A, B } } \frac{P(R|L_i)}{P(A|L_i)+P(B|L_i)}\log_2\frac{P(R|L_i)}{P(A|L_i)+P(B|L_i)}$
もし、優劣がつかない場合、このエントロピーが0であると定義すれば、優劣がつくかつかないかという2値の確率上のエントロピーの期待値は以下のようになり、これが感度として用いられることになります：
$f(L_i) = P(T|L_i) \times 0 + (1-P(T|L_i))h(L_i) = (1-P(T|L_i))h(L_i)$
ここで定義された感度は、順位に依存した1度のランダムクリックで優劣がつかない確率$P(T|L_i)$が高ければ低く、また、ランキングAとBの優劣がつく確率が同程度（エントロピーが高い）であれば高くなります。例えば、$P(T|L_i)=0$、$P(A|L_i) = P(B|L_i)=0.5$のとき最大値1をとります（いずれをクリックしても優劣がつき、かつ、一方のランキングが優れていると判断される確率が等しい）。
提示確率の最適化において最大化されるべき目的関数は、感度$f(L_i)$の期待値とし以下のようになります：
$\sum_{L_i} p_i f(L_i)$
最適化問題
上記の$L_i$に対する制約（制約1）、$p_i$に対する制約（制約2）、および、確率としての制約、さらに、最大化すべき目的関数をまとめると最適化問題は以下のようになります：
$\max_{p_i} \sum_{L_i \in \mathcal{L}} p_i f(L_i)$
subject to
$\forall L_i \in \mathcal{L}, k \geq 0, \exists i, j \geq 0, L_{i, 1:k}=A_{1:i} \cup B_{1:j}$
$0 \leq p_i \leq 1$
$\sum_{L_i \in \mathcal{L}}p_i = 1$
$\forall m \geq 1, \sum_{L_i \in \mathcal{L}} p_i \sum^m_{j = 1} \delta_j(L_i) = 0$
これは線形計画問題であり、一般的なソルバで解くことができますが、常に解が存在するかは示されていません。
最後に、Optimized interleavingの簡単な例を示します。以下の2つのランキングを考えます：
| 順位 | ランキングA | ランキングB |
|---|---|---|
| 1 | 001 | 002 |
| 2 | 002 | 003 |
この場合、制約1によって許容される長さ2の結合ランキングは以下の3種類です：
| 順位 | 結合ランキング1 ($L_1$) | 結合ランキング2 ($L_2$) | 結合ランキング3 ($L_3$) |
|---|---|---|---|
| 1 | 001 | 002 | 002 |
| 2 | 002 | 003 | 001 |
これらの提示確率$p_1, p_2, p_3$を求める最適化問題は以下の通りです：
$\max_{p_i} p_1f(L_1) + p_2f(L_2) + p_3f(L_3)$
subject to
$0 \leq p_1 \leq 1, 0 \leq p_2 \leq 1, 0 \leq p_3 \leq 1$
$p_1 + p_2 + p_3 = 1$
$p_1 \delta_1(L_1) + p_2 \delta_1(L_2) + p_3 \delta_1(L_3) = 0$
$p_1 (\delta_1(L_1) + \delta_2(L_1)) + p_2 (\delta_1(L_2) + \delta_2(L_2)) + p_3 (\delta_1(L_3) + \delta_2(L_3)) = 0$
ただし、感度は$f(L_1) = 0.918 $、$f(L_2) = 0 $、$f(L_3) = 0.918 $であり、$\delta_j(L_i)=1/r_A(l_{i, j})-1/r_B(l_{i, j})$を用いたときクレジットは$\delta_1(L_1)=1/1-1/3=2/3$、$\delta_1(L_2)=1/2-1/1=-1/2$、$\delta_1(L_3)=1/3-1/2=-1/6$、$\delta_2(L_1)=1/2-1/1=-1/2$、$\delta_2(L_2)=1/2-1/1=-1/2$、$\delta_2(L_3)=1/1-1/3=2/3$、となります。$f(L_2) = 0 $であるのは、$L_2$のいずれをクリックしても必ずランキングBが優れていると判断されるためです。
この線形計画問題の解は以下のようになります：
| 順位 | 結合ランキング1 ($L_1$) | 結合ランキング2 ($L_2$) | 結合ランキング3 ($L_3$) |
|---|---|---|---|
| 1 | 001 | 002 | 002 |
| 2 | 002 | 003 | 001 |
| $p_i$ | 0.429 | 0.200 | 0.371 |
直感的には、感度が低い$L_2$の利用をできるだけ避けつつも、制約を満たすために$p_2=0$とするわけにはいかないので上記のような結果になっています。
Multileaving (Schuth et al. 2014, 2015b)
ここまでは、2つのランキングのインターリービング手法を解説しましたが、複数のランキングに対するインターリービング手法も提案されています。これを**マルチリービング（Multileaving）**呼びます。(Schuth et al. 2014)では、Team draft interleavingとOptimized interleavingに対するマルチリービングが提案され、(Schuth et al. 2015b)では、Probabilistic interleavingに対するマルチリービングが提案されています。特に、Optimized interleavingとProbabilistic interleavingの実装は、インターリービングとマルチリービングで細部が異なるため注意が必要です。
インターリービングでも複数のランキングをペアごとに比較することは可能ですが、マルチリービングはこれよりも効率的であると、シミュレーションによる実験では示されています(Schuth et al. 2014)。しかし、まだ実際のデータに対する報告は行われていないため、どれほど効率化がされるかはまだ明らかではありません。
インターリービングの実践
最後に、Pythonモジュールinterleavingを用いて実際にインターリービングを行ってみます。ここでは、2つのランキングを対象としたTeam draft interleavingを用いることにします。
interleavingのREADME.mdに従ってインストールをしてみます：
pip install git+https://github.com/mpkato/interleaving.git
インストールで失敗する場合は、おおよそ、numpyまたはscipyへの依存関係が原因だと思いますので、別途これらをインストールしてから試してみると良いと思います。
interleavingのREADME.mdに書かれているUsageを再現してみます：
>>> import interleaving as il
>>> a = [1, 2, 3, 4, 5] # ランキングA
>>> b = [4, 3, 5, 1, 2] # ランキングB
>>> method = il.TeamDraft([a, b]) # Team draft interleavingを利用
>>> ranking = method.interleave() # 1つの結合ランキングを生成
>>> ranking # 生成された結合ランキング
[1, 4, 2, 3, 5]
>>> ranking.teams # チーム割当
{0: {1, 2}, 1: {3, 4, 5}}
ここで生成されたランキングは、ランキングAから1、Bから4、Aから2、Bから3、Bから5の順に検索結果が選択され生成されています。
次に、各種クリックに対して、どちらが優れていると判断されるかを確認します：
>>> clicks = [0, 2] # 1位(1)、3位(2)をクリック
>>> il.TeamDraft.evaluate(ranking, clicks)
[(0, 1)] # ランキングBよりランキングAが優れている
>>> clicks = [1, 3] # 2位(4)、4位(3)をクリック
>>> il.TeamDraft.evaluate(ranking, clicks)
[(1, 0)] # ランキングAよりランキングBが優れている
>>> clicks = [0, 1] # 1位(1)、2位(4)をクリック
>>> il.TeamDraft.evaluate(ranking, clicks)
[] # どちらが優れているとは言えない
このように、TeamDraft.evaluateによって、あるクリックからどちらのランキングを優れているかを知ることができます。出力される結果は与えられたランキングのインデックスのペアのlistであり、(i, j)が含まれているとき、インデックスiのランキングがインデックスjのランキングより優れていると判断されたことを意味します。
TeamDraft以外にも、以下のインターリービングが実装されており、TeamDraftと同じように使うことができます：
BalancedProbabilisticOptimized
また、Balanced以外は3つ以上のランキングを受け取り、マルチリービングを行うことができます：
>>> import interleaving as il
>>> a = [1, 2, 3] # ランキングA
>>> b = [4, 5, 6] # ランキングB
>>> c = [7, 8, 9] # ランキングC
>>> method = il.TeamDraft([a, b, c]) # Team draft multileaving
>>> ranking = method.interleave()
>>> ranking # 生成された結合ランキング
[1, 4, 7]
まとめ
この記事では、ランキングをA/Bテストで比較するようなケースに対する代替手段として、インターリービングという最新の手法について説明しました。A/Bテストよりも仕組みが複雑にはなりますが、より少数の試行でランキングの比較が可能であるため、使わない手はないのではないかと思います。
書き切れていない内容として、Probabilistic interleavingにおけるランキングの優劣判定方法、マルチリービングの詳細、各手法の性能比較がありますが、これらは加筆、もしくは、別記事にて言及したいと思います。
最後に、interleavingについては、まだまだ試作の段階であり、実際にこれを用いたインターリービングを実環境で行うに際して多くの改良を入れる予定です。ぜひwatchして最新版をフォローください。
参考文献
- (Joachims 2002a) Joachims. Unbiased evaluation of retrieval quality using clickthrough data. Technical report, Cornell University, Department of Computer Science, 2002. http://www.joachims.org.
- (Joachims 2002b) Joachims. Optimizing Search Engines using Clickthrough Data. KDD 2002.
- (Joachims 2003) Joachims. Evaluating retrieval performance using clickthrough data. Text Mining 2003.
- (Radlinski et al. 2008) Radlinski, Kurup, and Joachims. How Does Clickthrough Data Reflect Retrieval Quality? CIKM 2008.
- (Hofmann et al. 2011) Hofmann, Whiteson, and de Rijke. "A probabilistic method for inferring preferences from clicks." CIKM 2011.
- (Radlinski and Craswell 2013) Radlinski and Craswell. "Optimized Interleaving for Online Retrieval Evaluation." WSDM 2013.
- (Chapelle et al. 2012) Chapelle, Joachims, Radlinski, and Yue. "Large-scale Validation and Analysis of Interleaved Search Evaluation." ACM TOIS 30.1 (2012): 6.
- (Schuth et al. 2015a) Schuth, Hofmann, and Radlinski. "Predicting Search Satisfaction Metrics with Interleaved Comparisons." SIGIR 2015.
- (Schuth et al. 2014) Schuth, Sietsma, Whiteson, Lefortier, and de Rijke. "Multileaved Comparisons for Fast Online Evaluation." CIKM 2014.
- (Schuth et al. 2015b) "Probabilistic Multileave for Online Retrieval Evaluation." SIGIR 2015.