Upgrade to Pro — share decks privately, control downloads, hide ads and more …

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

CyberAgent
February 22, 2019

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

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

CyberAgent

February 22, 2019
Tweet

More Decks by CyberAgent

Other Decks in Technology

Transcript

  1. Who are you? Shota Yasui( ) @housecat 経歴 2013 新卒総合職⼊社(広告事業本部)

    2015 アドテクスタジオへ異動
 DMP/DSP/SSPで分析 AILabスタート ADEconチームスタート !2
  2. Bandit Problem? • 広告画像の選択肢がM個ある(ex. M = ) • ユーザーアクセス毎に選択肢を選ぶ •

    広告画像を⾒たユーザーがClickするか決める • この操作をT回のアクセス分だけ繰り返す • 最もClickを稼げる選び⽅は何か? !5
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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 腕の選択を複数回繰り返せば、
 あるバッチでの真の確率を得られる。 ⼊ってくるリクエストに対して、 選択肢の選択確率が決まる。
  10. IPW(Inverse Probability Weighting) • ex)ある学校で平均⾝⻑を知りたい • 体重だけはなぜか知っている たまたまラグビー部が試合で⽋席 体重が60kg以上の⼈の50%がラグビー部 •

    本当の平均⾝⻑(⻘線) • ラグビー部不在の⾝⻑(⾚線) • ⾚線は⻘線よりも下がっている ⾼⾝⻑のデータが⽋損しているから !21 ⾝⻑ 体重
  11. 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
  12. Estimator CTRnaive = N−1 N ∑ i clicki CTRIPW =

    K−1 K ∑ j Dj clickj pj 選択が⼀致したデータ 全てのデータ 選択が⼀致すると1
 しない場合は0 腕の選択確率 !28
  13. OPE(Off-policy Evaluation) • 既存のPolicyは全てのサンプルでYが観測できている • Yの平均が評価になる。 • 新規のPolicyは既存のPolicyと選択が同じ時だけYがわかる • Yの⾚字の平均が評価になる?

    • ⾚字のデータが黒字のデータのランダムサンプルである場合 • ⾚字のデータは全データと同⼀の分布 • 実際にはPolicyの決定に依存しているのでこれはない • どちらかがランダム選択であれば違う →全部のデータに対する評価を得たい !40
  14. 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
  15. 因果推論と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
  16. Efficient CF Evaluation • AAAI (oral + poster) https://arxiv.org/abs/ .

    • ⼤まかな内容 傾向スコアの作り⽅を変える MLで傾向スコアを推定する OPEでの不確実性が減少 !47
  17. 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
  18. 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
  19. 分析(not予測)環境の変化 • 機械学習を利⽤した意思決定の⾃動化が進んできた RTB/Recommend/Ad Selection/Ranking/etc この6年間肩⾝が狭くなる⼀⽅
 • ⼀⽅で)⾃動意思決定によって残されたデータを分析する必要性 What is

    good policy? / Causal effect of some items →プロダクトとして⾃動意思決定と事後分析をセットで考える必要性 • バンディットはたまたまこの流れが早かった 他の機械学習タスクでもこの流れになる !54
  20. 分析者(not予測)が⽬指したいところ • ⾃動意思決定をデザインする(with ML Engineer) 事後的な分析を⾒込んだデザインをする必要がある arg maxやUCBからの卒業(報酬性能も低い)
 • ⾃動意思決定のデザインに応じた分析をデザインする

    MDPを仮定する強化学習のログで因果推論はどうやるか?
 • 結局両⽅デザインしに⾏く必要がある データが⽣まれるプロセスから、 事後的な分析のプロセスまでをデザインする。 !55