バンディットと因果推論

バンディットと  因果推論  Shota Yasui  @CFML勉強会 #1   

自己紹介  名前：安井翔太（３１）職業：Economic Research Scientist 経歴： 2011年立教大学経済学部卒業 2013年
Norwegian School of Economics MSc in Economics 2013年 Cyberagent 入社（総合職, 微妙な分析の量産） 2015年アドテク部門へ異動（専門職, MLの応用） 2017年 AILabへ異動（研究職, ML + CI回りの応用） 2 @housecat442 

今日の前談  そもそものバンディットの話  3

考えるお題  あるユーザーに対してどちらの広告テンプレートを見せるべきか？    4 slot_1 slot_2 slot_3 slot_1 slot _2
template_id: 26 template_id: 75

Adaptiveな実験としてのバンディット  あるユーザーに対してどちらの広告テンプレートを見せるべきか？  →クリックがより起きそうな方を都度選ぶべき  （クリックを増やしたいなら  5 slot_1 slot_2 slot_3 slot_1 slot
_2 template_id: 26 template_id: 75

Thompson Sampling MAB  6 model for 26 model for 75
ベータ分布  α：5  β：35  ベータ分布  α：3  β：12  0.2 0.4 sampling  sampling  arg max slot_1 slot _2 template_id: 75 clickされたらα=α+1   clickされなければβ=β+1   と更新する 

Adaptiveな実験としてのバンディット  あるユーザーに対してどちらの広告テンプレートを見せるべきか？  →クリックがより起きそうな方を選ぶべき（クリックを増やしたいなら  →機械学習で予測して、予測値が大き方を選べば良いのでは？  7 slot_1 slot_2 slot_3 slot_1 slot
_2 template_id: 26 template_id: 75

Thompson Sampling Contextual Bandit  8 model for 26 model for
75 特徴量xから予測する(ex. logistic regression   y = f(x)  特徴量xから予測する   y = g(x)  0.2 0.4 sampling  sampling  arg max slot_1 slot _2 template_id: 75 yを観測したらgを更新  都度更新ではなく1日１回のケースも  男性には26だけど女性には75が良いといった傾向が汲み取れる 

Thompson Sampling Contextual Bandit  9 model for 26 model for
75 特徴量xから予測する   y = f(x)  特徴量xから予測する   y = g(x)  0.2 0.4 sampling  sampling  arg max slot_1 slot _2 template_id: 75 yを観測したらgを更新  都度更新ではなく1日１回のケースも  Policy  男性には26だけど女性には75が良いといった傾向が汲み取れる 

今日の前談  バンディット=累積因果効果最大化  10

商品レコメンドを考える  11 • 3つの商品しかないサイトとする   • 3つの商品のどれかを推す   • 報酬は売り上げで何が買われても良い
 

累積の因果効果を最大にする  選択肢aの効果を以下のように考える  aが選ばれた時の  aの売上  aが選ばれない時の  aの売上  aが選ばれた時の  報酬  選択肢aを選ぶときの報酬は以下のようになる  ※
行動した後の売上を全て報酬とする   ※ aを選択した場合にはb,cには影響がないとする   12

報酬最大化  以下のような報酬を推定して比較する  13

報酬最大化  Rを推定して比較するのは、因果効果を比較するのと同じ。  14 Contextual BanditではITEの比較と同じ。  

バンディットがそもそも面白い点  • 意思決定までを意識した機械学習の応用  ◦ 予測がゴールでは無い  ◦ 意思決定して報酬がもらえてなんぼ  • それ自体で因果効果を大きくする  ◦
RCTの拡張  ◦ 因果推論→意思決定　の流れを自動化している  • ログデータを実験データとして捉えられる  ◦ 今日のお話  15

本題その１  Off-Policy Evaluation, OPE    16

ここでの前提  • Batched Contextual Bandit  ◦ Policyの学習はバッチで行われる  ◦ 数時間/1日ごとに学習が行われる   
• Policyの意思決定は確率的  ◦ Thompson Sampling  ◦ Epsilon-Greedy  ◦ etc...  17 この辺の仮定は研究が進めばいらなくなりそう  

AD Template Selection  18 x candidates a,b,c,d b Y •
ユーザーに対して見せる広告を決定する • ユーザーの情報Xを得て、選択肢{a,b,c,d}に対してCTRの予測を行う。 • 予測値が最大の選択肢を選ぶ (上の例ではb) • Clickを観測する(Y) Predict + decision (Contextual Bandit) slot _1 slot _2 slot _3 slot_1 slot _2

model update  19 x candidates A = {a,b,c,d} b Y_b
Predict + decision dataset X, A, Y x candidates A = {a,b,c,d} b Y_b Predict + decision モデルの学習と更新 1日この仕組みを回す更新したモデルで回すデータの蓄積 new system c Y_c ex)線形回帰→DNN counterfactual!

Research Question  How to compare two AI systems?  20

Golden Standard Research Design  21

RCT(ABテスト)はコストが高い  • Policyの実装はそもそも大変  • 微妙なPolicyを投入するリスク  • 試せるアイデアの数に限界がある  = なるべくABせずに検証したい  22

評価データの特徴  23 X Y X1 1 a b X2 1
c c X3 0 b b X4 1 a a X5 1 b c • 得られているデータは   ◦ X：特徴量  ◦ Y：報酬（click）  ◦ A：選択された腕  ◦ A以外の腕を選んだ時のYは未知     • 新規のPolicyを走らせる   ◦ Xを入力するとA’が得られる   ◦ A’ = AならYがわかる  ◦ それ以外ではYは欠損  

ここでやりたいこと  24 X Y X1 1 a b X2 1
c c X3 0 b b X4 1 a a X5 1 b c • 全データでYを観測した時の評価をしたい       • 実際にYを観測できるのは A’=Aの時のみ      • 得られたデータから全体をどう推測するか？   ◦ Importance Sampling   ◦ Propensity Score  A’=Aなら1になる

Inverse Propensity Score, IPS  ←本当に欲しい評価   ←Unbiasdnessをもつ   既存のPolicyにおいて  
aが選ばれる確率で割る   評価の算出を行う時に傾向スコアの逆数で重みをつければ良い   25

26 傾向スコア = 既存のPolicyが選ぶ確率  x candidates a,b,c,d {a = 0.2,
b = 0.3, c = 0.1, d = 0.4}  Thompson Sampling/ Epsilon Greedy   ではここの確率は決まっている。   X, Aのデータから確率予測を行う →傾向スコア / Importance Weight シミュレーションでEmpiricalな確率を得る →いわゆる真の傾向スコア

どっちでやる？  真の傾向スコアを使うケース   • 文脈付きバンディットでは面倒   • ログの設計も面倒  • 計算量多いけど分析者が考える事が少ない
  ◦ BQ+JavaScriptで出来る   傾向スコアを推定するケース  • 選択肢が増減すると使えない   • チューニングが面倒   • 分散は小さくなる  27 Narita, Yusuke, Shota Yasui, and Kohei Yata. "Efficient Counterfactual Learning from Bandit Feedback." AAAI 2019.

因果推論とオフライン評価  X Y_A X1 1 a c X2 1 c
c X3 0 b c X4 1 c c X5 1 b c • 常にcを選ぶPolicyを評価する ◦ cが選ばれた部分から全体の期待値を考える ◦ 別の選択肢の結果との差分は ATE • 因果推論のIPW(Holvitz Thompson Estimator)はオフライン評価のIPSの特殊な形？ 28

余談  29 Doubly Robust Estimator 

Doubly Robustも使われる  30 何かしらのモデルでの報酬予測   モデルの誤差  • 傾向スコアと予測モデルを使ったアプローチ   •
報酬予測/傾向スコアどちらかがあっていれば良いという評価方法   Dudík, Miroslav, et al. "Doubly robust policy evaluation and optimization." Statistical Science 29.4 (2014): 485-511.

More Robust Doubly Robust, MRDR  • Yをどの様なモデルで学習するか？  • Doubly Robustの分散が最小になる様に学習する 
31 Farajtabar, Mehrdad, Yinlam Chow, and Mohammad Ghavamzadeh. "More Robust Doubly Robust Off-policy Evaluation." International Conference on Machine Learning. 2018. 分散の制御可能な部分  

本題その２  バンディットの事後的な分析を考える  32

Unconfoundedness / CIAが成立する  • 確率的に腕を選択しているので・・・  ◦ Xの値が固定されている時  ◦ Potential Outcomeと腕の選択は独立 
  • XはPolicyで使われている特徴量なので既知  ◦ 因果推論ではどの変数を使うか悩むケースが多い  ◦ ここではバンディットで使うものを使えば良い  腕の選択  33

後から因果推論を使う意味はあるのか？  • そもそもバンディットはTreatment Effectを最大化する  • 文脈付きは特徴量 x を加味してこれを行う  • 今更
因果推論する意味とは・・・？  34

意味はきっとある  • バンディットでも説明責任がある場合  ◦ どんな時にどんな選択肢が優れているのか？(ITE/HTE)    • 報酬以外のKPIへの因果効果を考える場合  ◦ 売上は増えたけど、ユーザー体験は？ 
  • 他にも多分あるはず  ◦ 実際まだよくわかってない  ◦ 是非みなさんと議論したい  35

模索しながらCAでやっている事  • Off-Policy Evaluation  ◦ アドテクにおけるBandit Algorithm by Fujita Komei 
◦ Efficient Counterfactual Learning from Bandit Feedback  (AAAI2019) with Yusuke Narita, Kohei Yata    • 選択肢のATE/HTEの推定  ◦ Bandit with Causality by Shota Yasui  36

さいごに  37

理想的にはこんな感じにしたい  Policy log state  action  off-policy  evaluation  Interpretation  Incentive Design 
Causal Inference  報酬を最大化する  MLエンジニアなみなさん   事後的な分析に従事する   データアナリスト/社会科学なみなさん   reward  38

しかし、悲しい現実  39

悲しい現実2  40

確率的に意思決定にしよう！  • 確率的にすれば色々始まる  ◦ Off-Policy Evaluation/learning  ◦ ATE/HTE推定等の因果推論    •
事後分析以外のメリットもちらほら  ◦ feedback loop  41

参考資料  42 • SIGIR 2016 Tutorial: Counterfactual Evaluation and Learning 
• Cornell University CS7792: Counterfactual Machine Learning  • KDD 2018 Tutorial: Real World Interactive Learning 

バンディットと因果推論

バンディットと因果推論

More Decks by Shota Yasui

Other Decks in Research

Featured

Transcript