バンディットアルゴリズムと因果推論 / Bandit Algorithm And Casual Inference

サイバーエージェントの技術者（エンジニア・クリエイター）向けカンファレンス『CA BASE CAMP 2019』
バンディットアルゴリズムと因果推論
安井 翔太

Transcript

1. Bandit Algorithm And Causal Inference / / Shota Yasui
2. Who are you? Shota Yasui( ) @housecat 経歴 2013 新卒総合職⼊社（広告事業本部） 2015 アドテクスタジオへ異動
 DMP/DSP/SSPで分析 AILabスタート ADEconチームスタート !2
3. .Bandit Algorithmとは？ .Causal Inference + Bandit .Off-Policy Evaluation .Future Work + まとめ !3
4. Banditとは何か？
5. Bandit Problem? • 広告画像の選択肢がM個ある（ex. M = ） • ユーザーアクセス毎に選択肢を選ぶ • 広告画像を⾒たユーザーがClickするか決める • この操作をT回のアクセス分だけ繰り返す • 最もClickを稼げる選び⽅は何か？ !5
6. Bandit Algorithmの概要 arm_a arm_b Request !6
7. Bandit Algorithmの概要 arm_a E[r|A = a] V[r|A = a] arm_b E[r|A = b] V[r|A = b] Request !7
8. Bandit Algorithmの概要 arm_a E[r|A = a] V[r|A = a] arm_b E[r|A = b] V[r|A = b] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm !8
9. Bandit Algorithmの概要 arm_a E[r|A = a] V[r|A = a] arm_b E[r|A = b] V[r|A = b] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm Feedback
 +Update !9
10. Banditの良いところ • 古典的にはAB-test（RCT）が使われていたタスク 前半AB-testして、後半は良かったのを使う。 代理店とかでよくやる。
 • Banditだと得られるclick数がより多くなる armのモデルを更新しつつ モデルに従って選ぶ !10
11. Bandit Algorithmの概要 arm_a E[r|A = a] V[r|A = a] arm_b E[r|A = b] V[r|A = b] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm Storage Feedback Batched Bandit Setting/interactive machine learning !11
12. Bandit Algorithmの概要 arm_a E[r|A = a] V[r|A = a] arm_b E[r|A = b] V[r|A = b] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm Storage Feedback Update Batched Bandit Setting/interactive machine learning !12
13. Bandit Algorithmの概要 arm_a E[r|A = a,X] V[r|A = a,X] arm_b E[r|A = b,X] V[r|A = b,X] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm Storage Feedback Update Batched Bandit Setting/interactive machine learning Contextual Bandit Case !13
14. Policyと呼ばれる部分 arm_a E[r|A = a,X] V[r|A = a,X] arm_b E[r|A = b,X] V[r|A = b,X] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm Storage Feedback !14
15. Thompson + Batch arm_a E[r|A = a,X] V[r|A = a,X] arm_b E[r|A = b,X] V[r|A = b,X] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm !15 腕の選択を複数回繰り返せば、
 あるバッチでの真の確率を得られる。 ⼊ってくるリクエストに対して、 選択肢の選択確率が決まる。
16. バンディットのログで 因果推論(CI)
17. AD Template Selection • 広告のテンプレートを選ぶ問題（アイテムは独⽴した別の機構で決定される） • ユーザーの情報Xを得て、選択肢{a,b,c,d}に対してCTRの予測を⾏う • 予測値が最⼤の選択肢を選ぶ(上の例ではb) • Clickを観測する(Y) • モデル更新は1⽇1回 Policy !17
18. よくある依頼 どちらのテンプレートが どのくらいCTRが⾼いか？ !18
19. Golden Standard Research Design !19
20. 因果推論による情報の復元 • 選択肢bのCTRを評価したい • バンディットの選択がbの場合にはYの値がわかる • 観測できたYだけで評価をするべきか？ • 分布が全体のデータの分布と同じなら問題ない • バンディットがbを選んだというバイアスが存在 →観測できたデータから全体での結果を推測する →因果推論の出番！ !20
21. IPW(Inverse Probability Weighting) • ex)ある学校で平均⾝⻑を知りたい • 体重だけはなぜか知っている たまたまラグビー部が試合で⽋席 体重が60kg以上の⼈の50%がラグビー部 • 本当の平均⾝⻑（⻘線） • ラグビー部不在の⾝⻑（⾚線） • ⾚線は⻘線よりも下がっている ⾼⾝⻑のデータが⽋損しているから !21 ⾝⻑ 体重
22. IPW • ⾼⾝⻑が不在という情報はある 体重60kg以上の50%がラグビー部 いない分データを⽔増しする • 体重/出席率すると… kg以上の観測データを２倍に⽔増し kg以下は１倍 • このデータで平均を算出（緑線） • ⻘線に近くなった！ !22 ⾝⻑ 体重
23. データが⽋損していて、 !23
24. 得られたデータの
 観測確率が分かっていれば、 = Propensity Score 再掲 !24
25. データを⽔増しして、 元の平均を推定することが可能。 !25
26. 因果推論による情報の復元 •黒のデータは⽋損(ラグビー部) •⽋損の理由はバンディットでbが選 ばれないから •では観測確率は？ →Policyがbを選ぶ確率 !26
27. True Propensity Score arm_a E[r|A = a,X] V[r|A = a,X] arm_b E[r|A = b,X] V[r|A = b,X] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm Storage Feedback Batched Bandit Setting/interactive machine learning !27
28. Estimator CTRnaive = N−1 N ∑ i clicki CTRIPW = K−1 K ∑ j Dj clickj pj 選択が⼀致したデータ 全てのデータ 選択が⼀致すると1
 しない場合は0 腕の選択確率 !28
29. Biased Result • Contextual Banditのログから集計 • ログからそのままCTRを集計したもの • 事業責任者やコンサルの⽅が⾒るよう なデータの結果。 • template_ が最も良い結果 26以外必要ないのか？ CTRnaive = N−1 N ∑ i clicki !29
30. IPW Result • バンディットのバイアスを取り除く ためにIPWを利⽤。 • どのテンプレートも優劣無し。 CTRIPW = K−1 K ∑ j Dj clickj pj !30
31. Heterogeneity • GRFを使う • 条件別の因果効果を推定する • CV的な操作を⾏いRobust性を担保 • GRFで因果効果の傾向が変わる変数を 探索する。 !31
32. IPW by Interstitial Interstitial ad Not Interstitial ad Interstitial ad !32
33. Banditのログでバイアスの少ない 事後的な分析が出来る。 !33
34. Off-Policy Evaluation (OPE)
35. ADTemplate Selection • 広告のテンプレートを選ぶ問題（アイテムは独⽴した別の機構で決定される） • ユーザーの情報Xを得て、選択肢{a,b,c,d}に対してCTRの予測を⾏う • 予測値が最⼤の選択肢を選ぶ(上の例ではb) • Clickを観測する(Y) Bandit Algorithm 再掲 !35
36. !36 Counterfactual Policyを考える Counterfactual Policy
37. Research Question How to compare two AI Systems? !37
38. Golden Standard Research Design !38
39. RCT is costly • RCTの為にモデルの実装が必要 • ⼤量のアイデアを同時に試すのは不可能 • ハイパーパラメーターなどの調整での利⽤は⾮現実的 • CF Policyがダメダメだと損失のリスクもある‧‧‧ →なるべくRCTせずに評価を⾏いたい !39
40. OPE(Off-policy Evaluation) • 既存のPolicyは全てのサンプルでYが観測できている • Yの平均が評価になる。 • 新規のPolicyは既存のPolicyと選択が同じ時だけYがわかる • Yの⾚字の平均が評価になる？ • ⾚字のデータが黒字のデータのランダムサンプルである場合 • ⾚字のデータは全データと同⼀の分布 • 実際にはPolicyの決定に依存しているのでこれはない • どちらかがランダム選択であれば違う →全部のデータに対する評価を得たい !40
41. そうだ、IPWを使おう。 !41
42. データが⽋損していて、 再掲 !42
43. 得られたデータの
 観測確率が分かっていれば、 = Propensity Score 再掲 !43
44. データを⽔増しして、 元の平均を推定することが可能。 再掲 !44
45. True Propensity Score arm_a E[r|A = a,X] V[r|A = a,X] arm_b E[r|A = b,X] V[r|A = b,X] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm Storage Feedback Batched Bandit Setting/interactive machine learning 再掲 !45
46. 因果推論とOPEの差 • 因果推論 常に⼀つの選択肢を選ぶpolicyの評価 • Off-Policy Evaluation 状況によって選択が変化するpolicyの評価 因果推論はむしろOPEの特殊な形 CTRIPW = K−1 K ∑ j Dj clickj pj CTROPE = K−1 K ∑ j m ∑ a clickj Dj,a π(a|Xj ) pj 腕aが⼀致した選択か？ 評価したいpolicyの決定 !46
47. Efficient CF Evaluation • AAAI (oral + poster) https://arxiv.org/abs/ . • ⼤まかな内容 傾向スコアの作り⽅を変える MLで傾向スコアを推定する OPEでの不確実性が減少 !47
48. True Propensity Score arm_a E[r|A = a,X] V[r|A = a,X] arm_b E[r|A = b,X] V[r|A = b,X] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm Storage Feedback Batched Bandit Setting/interactive machine learning 再掲 !48
49. True Propensity Score arm_a E[r|A = a,X] V[r|A = a,X] arm_b E[r|A = b,X] V[r|A = b,X] Decision Rule
 (UCB/Thompson Sampling) Request arm_b Selected Arm Storage Feedback Batched Bandit Setting/interactive machine learning 提案:選択確率をMLで推定してしまう。 •TPS= %でも実際のデータ上では55%だったりする。 •IPWではデータ上の割り振りを修正したい •ML/nonparametric-modelでデータ上の割り振りを学習する !49
50. 実験結果 • DSPのデータでの実験 • 新しいアイデアを使ったPolicyを作ってOPE • TPSとEPSで評価 • 縦軸：報酬性能の推定値 • 横軸：PSの種類 • EPSだと信頼区間が⼩さい !50
51. True Propensity Score Case Estimated Propensity Score Case !51
52. Banditのログでバイアスの少ない Policy評価ができた。 （しかも統計的に効率的に。） !52
53. Future Work + まとめ
54. 分析（not予測）環境の変化 • 機械学習を利⽤した意思決定の⾃動化が進んできた RTB/Recommend/Ad Selection/Ranking/etc この６年間肩⾝が狭くなる⼀⽅
 • ⼀⽅で）⾃動意思決定によって残されたデータを分析する必要性 What is good policy? / Causal effect of some items →プロダクトとして⾃動意思決定と事後分析をセットで考える必要性 • バンディットはたまたまこの流れが早かった 他の機械学習タスクでもこの流れになる !54
55. 分析者(not予測)が⽬指したいところ • ⾃動意思決定をデザインする（with ML Engineer） 事後的な分析を⾒込んだデザインをする必要がある arg maxやUCBからの卒業(報酬性能も低い)
 • ⾃動意思決定のデザインに応じた分析をデザインする MDPを仮定する強化学習のログで因果推論はどうやるか？
 • 結局両⽅デザインしに⾏く必要がある データが⽣まれるプロセスから、 事後的な分析のプロセスまでをデザインする。 !55
56. ２１世紀の分析者は、 データのゆりかごから 墓場までをデザインする。 !56
57. Enjoy Your Design!