最近interleavingという手法について勉強してました。 勉強するにあたって、資料を探していたらこちらのチュートリアルを拝見しました。
https://research.yandex.com/tutorials/online-evaluation/sigir-2019
また、日本語だとこちらの記事が非常にわかりやすかったです。
これらをベースに勉強してみたので、今回はそのメモです。
Absolute feedbackとRelative feedback
A/Bテスト
おそらく、システムの何らかの機能についてユーザーにとって価値があるか評価しようとした際に、最初に思いつくのはA/Bテストだと思います。
A/Bテストでは、ユーザーによるフィードバックは「ページがクリックされた回数」、「ユーザーのセッション数」、「セッションタイム」など、絶対的な数値で測定します。
ここで問題になるのは、ユーザーによって行動の傾向は様々であるという点です。 あるユーザーは大量にページをクリックするかもしれませんし、あるユーザーは検索クエリを頻繁に修正するかもしれません。 こうしたユーザーが介入群・対照群に含まれる場合には、測定の際のノイズを増やし、信頼区間を広げてしまいます。 結果として、こうしたノイズが含まれる結果によって誤った判断を下してしまったり、テスト自体を完了するのに大量のサンプル数が必要になってしまったりするわけです。
side-by-side
A/Bテストでは、機能の良し悪しを評価するために絶対指標を使用していたのが、ノイズを大きくさせている原因だと考えられます。 つまり、異なる機能を横に並べ同じユーザーに見せて、どちらが良いか比較評価してもらい、相対指標で考えれば特に問題はないわけです。
当然、この方法はオンラインテストでは実施はできず、オフラインでの評価にしか使用できません。 ただし、この相対指標（relative feedback）という考え方がポイントになってきます。
interleaving
interleavingは検索や推薦システム等のランキングを行うシステムについて、複数のアルゴリズムを効率的に評価する手法です。 インターリービング（交互に配置すること）は、文字通り複数のランキングの結果を交互に配置します。
イメージはこんな感じです。
これにより、2つのランキングが混ぜ込まれた1つのランキングができます。 この混ぜ込んだランキングをテストとしてユーザーに表示していきます。
混ぜ込まれたランキングの各アイテムには出所となるランキングがあるので、混ぜ合わせ前のランキングのうちどちらがよりユーザーに好まれたかを相対的に測定することができます。
interleavingの特徴としては、
- 標準的なインターフェイスでの比較が可能
- 膨大な数のユーザーを対象に実験が可能
- 限られた範囲にだけ使用可能（ランキング、スニペットのみ、UIの変更は不可)
- 実験の単位が結果ページとのやりとりだけなので、長期的な関与の効果を把握しづらい
- ランキングをクリックして実際に商品購入に至るまでを測定したい場合など、ランキングをクリックしたあとの行動はトラッキングしにくい
などがあります。
interleavingの種類
一口にInterleavingと言っても、代表的な手法でいくつかやり方があり、それらについて確認します。
Balanced Interleaving
Balanced Interleavingのアルゴリズムは下記のようになっています。
ざっくりいうと、
- 2つのランキングのうち、どちらから使用するか選ぶ
- 2つのランキングの対象を交互に選択する
- もとになるランキングの上位からアイテムを選ぶ
- すでに出力のランキングにアイテムが含まれていなければ、出力の末尾に追加
- すでに出力に含まれていた場合には、そのアイテムは飛ばす
- ほしいランキングの長さになるまで2−3を続ける
みたいな動作をします。 詳細はアルゴリズムをご確認ください。
interleavingされたランキングに対して、クリックされたアイテムが、もともとどちらのランキングによるものなのかに応じて大本のランキングにカウントしていき、その値が大きいほうが優れたランキングであるといった評価を行います。
Team Draft Interleaving
Team Draft Interleavingのアルゴリズムは下記のようになっています。
プロ野球のドラフト指名みたいなやり方を想像して貰えばイメージしやすいかと思います。 まず、どちらのランキングが先に指名するかをランダムで決め、その順番に従って各ランキングでまだ選ばれていない最上位のアイテムを出力のランキングに加えていく方式です。
こちらの評価はシンプルに、結合されたランキングでクリックされたアイテムの出所となっているランキングのカウントが大きいほうが優れたランキングであると判断します。
Probabilistic Interleaving
Probabilistic Interleavingは、2つのランキングから上位からアイテムを選択するのではなく、上位のほうが選択されやすいようにアイテムの選択確率を設定し、確率的にアイテムを選択する方法です。
各ランキングのアイテムは、順位の乗の逆数が選択されやすさとなっており、この確率分布に基づいてランダムにアイテムがサンプリングされていきます。
Optimized Interleaving
あんまり良くわかってないので、これは省略。
こちらの記事によれば、これを適用するための条件が2つあり、これに加えて確率に関する制約のある中で目的関数についての最適化問題を線形計画法で得らしいです。難しい… 覚えてたらいつか追記します。
実装してみる
最後にちょっとだけ実装して終わろうと思います。 インターリービング自体は下記のライブラリでかんたんに使用することができます。
これを使って実装してみたいと思います。 とは言ってもライブラリが非常に使いやすく、そんなに実装は難しくならないのでシュッと確認してみます。
※内部の挙動がわかるように、ちょっと改修して使用します。
Balanced Interleaving
挙動の確認のため、ちょっと書き換えてみます。
▶balanced.py
実行するスクリプトはこんな感じにしています。
import interleaving import numpy as np np.random.seed(seed=42) a = [1, 2, 3, 4, 5] # Ranking 1 b = [4, 3, 5, 1, 2] # Ranking 2 method = interleaving.Balanced([a, b]) # initialize an interleaving method ranking = method.interleave() # interleaving print("rankiing: " + str(ranking)) clicks = [0, 2] result = interleaving.Balanced.evaluate(ranking, [0, 2]) print("winner: " + str(result))
これで実行すると、こんな感じになります。
% python sample.py is_a_first : True from: a, add: 1 from: b, add: 4 from: a, add: 2 from: b, add: 3 from: b, add: 5 rankiing: [1, 4, 2, 3, 5] k: 1 h_a: 2 h_b: 0 winner: [(0, 1)]
上の例だと、先にランキングを構成するのはaという事になっています。 その後、
from: a, add: 1 from: b, add: 4 from: a, add: 2 from: b, add: 3 from: b, add: 5
という順番で選択されています。最後でbが連続しているのが特徴的で、aのランキングの3回目で選択候補になった3のアイテムはすでにランキングにいたのでスキップされた感じですね。
これを評価すると、ランキングaの方から2回クリックを受けたことになり、最終的なランキングの序列は a > bのような出力になっている次第ですね。
Team Draft Interleaving
▶team_draft.py
動作確認としてこちらのスクリプトを実行します。
import interleaving import numpy as np np.random.seed(seed=42) a = [1, 2, 3, 4, 5] # Ranking 1 b = [4, 3, 5, 1, 2] # Ranking 2 method = interleaving.TeamDraft([a, b]) # initialize an interleaving method ranking = method.interleave() # interleaving print("rankiing: " + str(ranking)) clicks = [0, 2] result = interleaving.TeamDraft.evaluate(ranking, [0, 2]) print("winner: " + str(result))
実行するとこんな感じです。
% python sample_teamdraft.py
selected_team: 0
{0: {1}, 1: set()}
selected_team: 1
{0: {1}, 1: {4}}
selected_team: 1
{0: {1}, 1: {3, 4}}
selected_team: 0
{0: {1, 2}, 1: {3, 4}}
selected_team: 0
{0: {1, 2, 5}, 1: {3, 4}}
rankiing: [1, 4, 3, 2, 5]
0: 1
1: 1
winner: []
ランキングaとbがランダムに選ばれて、それぞれの選択できる最上位のアイテムを取得します。 評価としては、どちらも1件ずつクリックされていて、同点で引き分けになっています。
Probabilistic Interleaving
▶probabilistic.py
動作確認に使用するスクリプトはこんな感じです。
import interleaving import numpy as np np.random.seed(seed=42) a = [1, 2, 3, 4, 5] # Ranking 1 b = [4, 3, 5, 1, 2] # Ranking 2 method = interleaving.Probabilistic([a, b]) # initialize an interleaving method ranking = method.interleave() # interleaving print("rankiing: " + str(ranking)) clicks = [0, 2] result = interleaving.Probabilistic.evaluate(ranking, [0, 2]) print("winner: " + str(result))
実行してみます。
% python sample_probabilistic.py ranker: 0 add: 3 ranker: 1 add: 4 ranker: 1 add: 5 ranker: 1 add: 1 ranker: 1 add: 2 rankiing: [3, 4, 5, 1, 2] winner: [(1, 0)]
初回でランキングaの方から先頭ではない'3'が選択されていることがわかります。 このように、必ずしもランキングの最上位からピックされるわけではないということがわかりました。
Optimized Interleaving
Optimized Interleavingは正直あんまりできてないので、とりあえず動作確認だけ。
動かすスクリプトはこんな感じ。 Optimized Interleavingだけ、関数の入力が異なるので、そこだけ注意して使ってみます。
import interleaving import numpy as np np.random.seed(seed=42) a = [1, 2, 3, 4, 5] # Ranking 1 b = [4, 3, 5, 1, 2] # Ranking 2 method =interleaving.Optimized([a, b], sample_num=len(a) + len(b), secure_sampling=True) ranking = method.interleave() # interleaving print("rankiing: " + str(ranking)) clicks = [0, 2] result = interleaving.Optimized.evaluate(ranking, clicks) print("winner: " + str(result))
実行するとこんな感じ。
% python sample_optimized.py /Users/tsuno/Programs/Python/interleaving/interleaving/optimized.py:133: OptimizeWarning: A_eq does not appear to be of full row rank. To improve performance, check the problem formulation for redundant equality constraints. res = linprog(sensitivity, # objective function rankiing: [1, 4, 3, 5, 2] winner: [(0, 1)]
きっと上手にinterleavingされてるんだと信じてます。 理解したらこの辺追記します。
参考文献
以下の文献を参考にさせていただきました。
感想
interleaving、メジャーどころは多分4種類だということで、とりあえず触りだけ勉強してみた次第です。 なんとなくのイメージだけですが、こういう基本的な内容は抑えておけてよかったなと思いました。
ランキング関係のオンラインテストを行う場合に、こういうやり方もあるんだということは把握できたので、ひとまず勉強になりました。
