Online Evaluation Methods for the Causal Effect of Recommendations
著者: masahiro sato
機関: independent researcher, Japan
なぜ選んだか
インターリービング気になっていたのでちょうど勉強できるなと思ったため
前回の facebook A/B テスト論文で因果推論ちょっとだけわかってきたので、継続して調べようと思った
割と行間をエスパーで埋めているので、論文にない説明も挟んでます。気になる部分ぜひご指摘くださいmm
まとめ
この論文では新しいインターリーブ手法を提案している
Causal balanced Interleaving (CBI) - 因果的均衡インターリービング?
「因果効果(causal effect)」の観点でモデルを比較する
検証でこの手法は不偏(unbiased)かつ A/B テストより効率が優れていることを示した
オンライン実験をシミュレートし、既存ランキングモデルをいくつか比較した
※ あくまでインターリービング手法なので、推薦手法は提案していない
いままでも因果効果による推薦モデル自体はあったものの、オフライン評価に閉じていた
模擬オンライン実験による評価手法を開発することで、これらをシミュレーションし比較した
既存研究との違い
v.s. A/B テスト
効率的
v.s. 既存インターリーブ手法
因果効果を考慮したインターリーブ手法は提案手法が初めてと主張
既存手法はランキングが「ユーザーのクエリや嗜好をどれだけ正確に反映しているか」が評価基準だが、提案手法では「その推薦によってどの程度インタラクションに影響が起きるか」の因果効果の観点に基づいている
イントロ:推薦とその因果効果
推薦は、ユーザーの行動に影響を与えるような処置のひとつ。
e.g.) 推薦によって、ユーザーのアイテムへのアクション(購入・閲覧)が増加するなどの影響がある
このような、ある処置のもたらす効果のことを処置効果 treatment effect (または因果効果 causal effect) という。
(因果効果があるからこそ推薦をやっているともいえる
因果効果は、あるアイテム・ユーザーについて、ユーザーに アイテムの推薦をした世界 と 推薦をしなかった世界 を考えたとき、「推薦をしたそのことによってユーザーがアイテムにアクションを起こした」という影響値のことを指す。
推薦はユーザー行動への予測精度が高ければよいかというとそうではなく、予測精度と因果効果との間に乖離がある場合もある(著者別論文) なので、「履歴から予測した、インタラクションの起きそうな優等生アイテムを推薦する」のではなく、「因果効果の高い(推薦したそのことによってインタラクションされる期待値が高まる)アイテムを推薦する」、という推薦手法が提案されている。(セレンディピティの文脈に近そう
イントロ:モデル比較
推薦モデルの性能を比較して最適なものを選択するためには、オンライン実験を行うのが一般的(実際にサービスに推薦の処置を適用し、ユーザーのアイテムに対する行動ログを用いて分析をする)。
因果効果は、その定義からして単体のアイテム・ユーザーについて直接観測できるものではない。ある地点で、ユーザーが推薦を受けた世界と受けていない世界の観測をして同時に比較することはできない。
なので、推薦を受ける・受けないそれぞれのユーザーを大量に用意してその二群を比較する検定(いわゆる A/B テスト)によって、統計的に因果効果を推論することしかできない。
(すごく雑にいうと、二群として平均的に同質な集団を集めれば、同一人物による推薦された世界のデータと推薦されていない世界のデータの両方が集まった、のと近い扱いができるってことだと思っている
推論モデル同士の比較をする際も同じく、推薦モデル A による推薦を受けるユーザーと、推薦モデル B による推薦を受けるユーザー間で A/B テストをする。
A/B テストより低コスト・効率的に推薦モデル間の比較を行う手法としてインターリービングが知られている。双方の推薦モデルから生成されたリストを融合することで単一のリストにし、そのフィードバックを用いてモデル間の比較を行う。
インターリービングの手法は、2つのランキング(推薦リスト)の混ぜ方であるので、それぞれ対応した名前が付いている。
理論
基本定義
$ \mathcal{U}: ユーザー集合
$ \mathcal{I}: アイテム集合
$ Y_{ui} \in \{0,1 \}: ユーザー $ u \in \mathcal{U} とアイテム $ i \in \mathcal{I} のインタラクション
推薦の概念を導入する
$ Z_{ui} \in \{0,1 \}: ユーザー $ u \in \mathcal{U} とアイテム $ i \in \mathcal{I} の推薦の有無
$ Y_{ui}^T: 推薦された($ Z_{ui}=1)ユーザー $ u \in \mathcal{U} とアイテム $ i \in \mathcal{I} のインタラクション
$ Y_{ui}^C: 推薦されていない($ Z_{ui}=0)ユーザー $ u \in \mathcal{U} とアイテム $ i \in \mathcal{I} のインタラクション
$ \tau_{ui} = Y_{ui}^T - Y_{ui}^C \in \{-1,0,1 \}: ユーザー $ u \in \mathcal{U} がアイテム $ i \in \mathcal{I} を推薦されたことによる因果効果(これを見たい)
観測されるアウトカムは
$ Y_{ui} = Z_{ui}Y_{ui}^T + (1-Z_{ui})Y_{ui}^C
どちらともを同時に得ることはできないため、原理的に因果効果 $ \tau_{ui} を計算することはできない
平均的な因果効果
$ L_u^A: モデル$ Aがユーザー$ uに生成する推薦リスト
$ \tau_A = \mathbb{E}[\tau_{ui}|i\in L_u^A, u\in\mathcal{U}] : モデル$ Aの平均因果効果
モデルの評価
平均因果効果において$ \tau_A > \tau_B ならば、推薦モデル$ Aを$ Bより優れている、とみなす
平均因果効果を比較するためには、原理的には
$ \tau_{L_u^A} = \frac{1}{n}\sum_{i\in L_u^A}\tau_{ui}, \quad \tau_{L_u^B}=\frac{1}{n}\sum_{i\in L_u^B}\tau_{ui}
この二つを算出したいが、因果効果$ \tau_{ui}は直接観測したアウトカムから推定できないのだった。
リスト$ L_u^A,L_u^Bのアイテムが潜在アウトカムとは独立にインターリーブリスト$ L_uにランダムに割り当てられていたとすると、それはランダム化比較試験(RCT)と見做せる。リスト$ L_u^Aの因果効果$ \tau_{L_u^A}は、インターリーブリストと元々のリストのどちらにもあるアイテムによるアウトカム平均値と、インターリーブリストには含まれなかったアイテムのアウトカム平均の差として推定できる。
$ \left( \hat{\tau}_{L_u^A} \right)_{\text{RCT}} = \frac{1}{|L_u^A|\cap L_u} \sum_{i\in L_u^A \cap L_u}Y_{ui} - \frac{1}{|L_u^A\backslash L_u|}\sum_{i\in L_u^A \backslash L_u} Y_{ui}
素朴なアイデア: Equal Probability Interleaving
ランダム割り当てをするなら、2つのリストに存在するアイテム集合$ L_u^A\cup L_u^Bから等確率で$ n個のアイテムを選択することが考えられる。
このランダム割り当てから上式で算出するアウトカム平均を EPI による RCT (EPI-RCT) と呼び、提案手法と比較する
より一般的な因果効果推定式
アイテムをユーザーに推薦するかどうか、というのはモデルの特徴量$ X_{ui}に対する予測に依存している。そのため、この特徴量が因果推論における共変量(バイアス要因)となる。
仮に、上記 RCT で述べた「リスト$ L_u^A,L_u^Bのアイテムが潜在アウトカムとは独立にインターリーブリスト$ L_uにランダムに割り当てられていたとすると」という前提が崩れており、「特徴量(共変量)$ X_{ui}によって推薦に偏りがあるため、インターリーブリストの割り当てとアウトカムに相関が生じる」とすると、そのバイアスを除去する必要がある
リストに含まれる(推薦される処置を受ける)確率を次のように定義する(傾向スコア)
$ p_{ui} = \mathbb{E}[Z_{ui}=1 | X_{ui}]
この確率を試行によって推定するのが ↓ で提案する Algorithm 1 の一部のねらい(ロジスティック回帰?
GitHub コードに calc_propensity あるが読めておらず:
仮定1: 共変量$ X_{ui}はアウトカム$ Y_{ui}^T,Y_{ui}^Cと$ Z_{ui}のすべての交絡を含んでいる
条件付き独立と等価: $ (Y_{ui}^T,Y_{ui}^C)\perp Z_{ui}|X_{ui}
訳注:$ X_{ui}の下で条件付き独立: 共変量 $ X_{ui}が同じアイテムとユーザーなら、推薦の確率は同じになる
推薦モデルのインターリービングでは$ Z_{ui}に影響を与える共変量(特徴量)がわかっているためこちらは満たされるはず
仮定2: アイテムの割り当ては決定論的でない
この二つの仮定を合わせて strongly ignorable treatment assignment という
このような仮定のもと、IPS weighting(逆傾向スコア重み付け)を用いてセレクションバイアスを除いた不偏推定量を構築できる
モデル$ Aがあるユーザーに生成した推薦リストの平均因果効果:
$ \left( \hat{\tau}_{L_u^A} \right)_{\text{IPS}} = \frac{1}{n}\sum_{i\in L_u^A \cap L_u} \frac{Y_{ui}}{p_{ui}} - \frac{1}{n}\sum_{i\in L_u^A \backslash L_u} \frac{Y_{ui}}{1-p_{ui}} \\= \frac{1}{n}\sum_{i\in L_u^A}\left( \frac{Z_{ui}Y_{ui}}{p_{ui}} - \frac{(1-Z_{ui})Y_{ui}}{1-p_{ui}} \right)
ユーザー・アイテムの組について、推薦されるかどうかの傾向$ p_{ui}とアウトカムの間に正の相関があるとする。推薦されやすいものは良い成果を出すアイテムで、推薦されにくいアイテムは結果が悪いもの、という関係になり、観測結果から得られた期待値はそれぞれ真の期待値から乖離してしまう。
推薦されているものから期待値を出すと下駄を履いた大きめの数値が出るし、推薦されていないものの期待値は過小評価された小さめの数値が出る
この推定量はバイアスをもたず、
$ \mathbb{E}\left[ \frac{Z_{ui}Y_{ui}}{p_{ui}} - \frac{(1-Z_{ui})Y_{ui}}{1-p_{ui}} \bigg\vert X_{ui} \right] = \mathbb{E} \left[ \frac{Z_{ui}Y_{ui}^T}{p_{ui}} - \frac{(1-Z_{ui}Y_{ui}^C)}{1-p_{ui}} \bigg\vert X_{ui} \right] \\ = \frac{\mathbb{E}[Z_{ui}|X_{ui}]Y_{ui}^T}{p_{ui}} - \frac{\mathbb{E}[(1-Z_{ui})|X_{ui}]Y_{ui}^C}{1-p_{ui}} \\ = \frac{p_{ui}Y_{ui}^T}{p_{ui}} - \frac{(1-p_{ui})Y_{ui}^C}{1-p_{ui}} = \tau_{ui}
期待値から真の因果効果を推定することができる。
(一行目右への変形が strongly ignorable treatment assignment 利用
提案アルゴリズム: Causal Balanced Interleaving
因果効果に対するインターリーブでのアイテム選択はランダム化されている必要がある
推薦とアウトカム$ Yとの間に交絡によるバイアスがかかる可能性があるため
https://gyazo.com/59c7828bb2af68991e42c45aab87821e
入力: 比較したい推薦リスト$ L_u^A, L_u^B
出力: インターリーブによって生成されるリスト $ L_u
$ A,Bどちらから取るかはランダムに始め、その後は交互にそれぞれのリストからまだ追加されていない要素を一つずつランダムに選びリストに足していく。サイズが入力リストと同じ$ nになった地点で終了
EPI と異なるのは、$ A,B交互にアイテムを選択する点:アイテムが元々どちらに所属していたかが偏らない
アイテムがリストのどちらにも含まれていると、より高い確率で選ばれる
リストの和の濃度に依存し、要素内のアイテムが少ないほど各アイテムは選ばれる確率が高い
Algorithm 1 を十分な回数繰り返し、共変量の組み合わせごとに$ Z_{ui}を記録すると、傾向を数値計算できる
ランダム化で交絡を除去、IPSW で選択バイアスを除去している
実験
研究課題
1. 平均的な因果効果の真の差について、どの方法が有効な推定値を得られるのか?
2. 提案するインターリーブ法 CBI は、A/B テストよりも効率的か?(実験ユーザー数が少ないか)
データセット
Dunnhumby: 小売っぽい
MovieLens-1M: 映画レビューサイト
すべてのユーザーとアイテムのペアについて、潜在的なアウトカム$ Y_{ui}^Tと$ Y_{ui}^Cの両方を含む半合成(semi-synthetic)データセットを用意
テストデータはオンライン評価のシミュレーションに使用
トレーニングデータは以下のモデル学習に使用
CUBN: アウトカム類似度 (-O) と治療類似度 (-T) による因果効果を考慮したユーザーベース近傍法
ULRMF/ULBPR: アップリフトベースのポイントワイズとペアワイズ学習法
BPR: ベイズパーソナライズランキング法
UBN: ユーザーベース近傍法
学習済みモデルの平均因果効果$ \overline{\tau_{L_u^{\text{model}}}}と平均処置アウトカム$ \overline{Y^T_{L_u^{\text{model}}}}
https://gyazo.com/ef601be9aeabfaa27c6155e1224d7604
平均因果効果の高い(ユーザーに影響を与えている)モデルが必ずしも平均的な処置アウトカムを高くしている訳ではない。
つまり、推薦アイテムの成果だけを評価すると、因果効果の弱いアイテムを推薦する可能性がある。
シミュレーション
ランダムにユーザーを選択し、比較するモデルを用いてリスト$ L_u^A,L_u^Bを生成
A/B テスト手法については、モデル$ A, Bが別々に推薦をするようにグループ分割$ \mathcal{S}_A, \mathcal{S}_Bをした
インターリーブ法については、EPI, CBI それぞれの方法に則ってインターリーブされた推薦リストを生成する
「推薦をする」とは、$ Z_{ui}=1にすること
ユーザーアウトカム$ Y_{ui}の「観測」とは、$ Y_{ui}=Z_{ui}Y_{ui}^T + (1-Z_{ui})Y_{ui}^Cの計算をすること
観測したアウトカムを用いて、モデル間の平均的な因果効果の差を推定する
↑を 1 万回繰り返し、各オンライン評価手法による推定差分を記録した
推薦リストのサイズは$ n=10
結果と議論
AB-total: A/B テストですべてのアイテムについてユーザーインタラクションを評価
AB-list: A/B テストで推薦リスト上のアイテムのみについてユーザーインタラクションを評価
EPI-RCT: インターリーブでリストの和から等確率でアイテムを選択する
CBI-RCT: Algorithm 1 による因果的均衡インターリーブで RCT 推定式を評価(傾向スコアによる補正なし)
CBI-IPS: Algorithm 1 によるインターリーブで IPSW による不偏推定量を評価(最推し)
評価方法の妥当性
比較したモデルの因果効果の差の推定値(10,000回のシミュレーション実行の平均値±標準偏差)。太字の結果は、真の値が平均推定値の95%信頼区間内にあることを示す。
https://gyazo.com/29d3a8441022392ee0d74b10a9addba7
EPI-RCT と CBI-IPS で得られた平均値は真の差に近い値であった.
AB-total による平均値も Dunnhumby では真の値に近いが、ML-1M では若干乖離している。
AB-list では、表1に示すように、真の値とは大きく異なるが、治療成績の差 $ \overline{Y^T_{L_u^{\text{model}}}} に近い推定値が得られることが多い。
AB-list は $ \tau_{ui} ではなく $ Y_{ui}^T を評価するため、予想されることである。
さらに,CBI-RCT の推定値もほとんどの場合,真の差から乖離している。
これは,インターリーブにおける推薦確率の不均一性によって引き起こされるバイアスに起因する
逆に、CBI-IPS はこのバイアスをうまく除去し、真の値を中心とした推定値を得ることができている
※ CUBN-O & UBN,ULBPR & UBN の比較では,CBI-RCT と CBI-IPS の結果は同じであった。これらの比較では$ L_u^Aと$ L_u^Bの重複がなく、傾向$ p_{ui}も一定であった。したがって、バイアスがなく IPS は不要であり、CBI-RCT と CBI-IPS は同等
インターリーブ手法の効率性
↑で有効と判断したAB-total、EPI-RCT、CBI-IPS の効率性を比較した
{10, 14, 20, 30, 50, 70, 100, 140, 200, 300, 500, 700, 1000, 1400, 2000} の様々なサイズのユーザーサブセットを用意し、それぞれでシミュレーション
誤判定率(推定差分の符号が真実と逆である場合)を評価
ユーザー数への依存性:ユーザ数に応じた誤判定率の推移
https://gyazo.com/4b2463f280221d73c11c4b9b43d67dd4
CBI-IPS と EPI-RCT の誤判定比率は,利用者数の増加とともに,AB-total の誤判定比率よりも急速に減少することがわかる
Dunnhumby データセットでは,AB-total は CBI-IPS と EPI-RCT と同じ誤判定率を達成するために 30 倍程度のユーザ数を必要とする
ML-1M データセットでは,AB-total は実験範囲の部分集合サイズにおいて,同じ誤答率に達しなかった
これらの結果は,提案するインターリーブ手法の優れた効率性を示している
表2に示す標準偏差の小ささから予想されるように,CBI-IPS は EPI-RCT よりもわずかに効率が良い傾向がある
このインターリーブ手法では、比較したリストから選択されるアイテムの数がバランスされているためと考えられる
まとめ
推薦モデルを因果効果の観点から比較するインターリーブ手法を初めて提案
バイアスのないモデル比較のためのインターリーブ手法:
等確率でアイテムを選択して RCT として推定する CBI-RCT
そのあと傾向スコアを用いて重み付けする CBI-IPS
オンライン実験のシミュレーションにより次を示した:
本手法と A/B テストはバイアスがない
本手法は A/B テストより大幅に効率的
将来的に:
マルチリービングに拡張予定
実際の推薦サービスでのオンライン実験
感想
文脈を埋めるのが非常に大変だった
EPI, CBI しか見てないが既存の何かしらのインターリービング手法との比較はやらなくてよかったのだろうか
実システム上でこの推薦はインターリービングやれる・やれないなどあるのだろうか
リランキングするときにパラメータ調整する:マルチリービング使える
:memo: 分散を抑える