Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
バンディットアルゴリズムと因果推論 / Bandit Algorithm And Casual...
Search
CyberAgent
PRO
February 22, 2019
Technology
1
1.6k
バンディットアルゴリズムと因果推論 / Bandit Algorithm And Casual Inference
サイバーエージェントの技術者(エンジニア・クリエイター)向けカンファレンス『CA BASE CAMP 2019』
バンディットアルゴリズムと因果推論
安井 翔太
CyberAgent
PRO
February 22, 2019
Tweet
Share
More Decks by CyberAgent
See All by CyberAgent
未来のテレビを形づくる ABEMAのグロース戦略:ユーザー体験と品質向上のアプローチ
cyberagentdevelopers
PRO
0
130
IBC 2024 動画技術関連レポート / IBC 2024 Report
cyberagentdevelopers
PRO
1
120
生成AIは安心・安全に貢献できるのか
cyberagentdevelopers
PRO
0
14
AIの血肉となるアノテーションデータのために大事にしている事
cyberagentdevelopers
PRO
2
17
ABEMA NEWSにおける映像データを活用した記事生成AI 〜記事制作者に寄り添ったソリューションにするまで〜
cyberagentdevelopers
PRO
0
33
ACL 2024 参加報告
cyberagentdevelopers
PRO
0
48
生成AIの強みと弱みを理解して、生成AIがもたらすパワーをプロダクトの価値へ繋げるために実践したこと / advance-ai-generating
cyberagentdevelopers
PRO
1
270
SNSマーケティングに革新! ABEMA サッカー動画切り出しを生成AIで自動化し、業務効率化を狙う! / abema-ai-marketing
cyberagentdevelopers
PRO
2
150
新卒1年目が挑む!生成AI × マルチエージェントで実現する次世代オンボーディング / operation-ai-onboarding
cyberagentdevelopers
PRO
1
230
Other Decks in Technology
See All in Technology
TypeScript、上達の瞬間
sadnessojisan
46
13k
組織成長を加速させるオンボーディングの取り組み
sudoakiy
2
220
Lexical Analysis
shigashiyama
1
150
アプリエンジニアのためのGraphQL入門.pdf
spycwolf
0
100
CysharpのOSS群から見るModern C#の現在地
neuecc
2
3.5k
マルチモーダル / AI Agent / LLMOps 3つの技術トレンドで理解するLLMの今後の展望
hirosatogamo
37
12k
あなたの知らない Function.prototype.toString() の世界
mizdra
PRO
1
260
エンジニア人生の拡張性を高める 「探索型キャリア設計」の提案
tenshoku_draft
1
130
【Startup CTO of the Year 2024 / Audience Award】アセンド取締役CTO 丹羽健
niwatakeru
0
1.3k
TypeScriptの次なる大進化なるか!? 条件型を返り値とする関数の型推論
uhyo
2
1.7k
個人でもIAM Identity Centerを使おう!(アクセス管理編)
ryder472
4
240
Why App Signing Matters for Your Android Apps - Android Bangkok Conference 2024
akexorcist
0
130
Featured
See All Featured
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.3k
Automating Front-end Workflow
addyosmani
1366
200k
5 minutes of I Can Smell Your CMS
philhawksworth
202
19k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
16
2.1k
A Tale of Four Properties
chriscoyier
156
23k
Code Review Best Practice
trishagee
64
17k
How STYLIGHT went responsive
nonsquared
95
5.2k
The Power of CSS Pseudo Elements
geoffreycrofte
73
5.3k
Reflections from 52 weeks, 52 projects
jeffersonlam
346
20k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
4
380
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.1k
Fantastic passwords and where to find them - at NoRuKo
philnash
50
2.9k
Transcript
Bandit Algorithm And Causal Inference / / Shota Yasui
Who are you? Shota Yasui( ) @housecat 経歴 2013 新卒総合職⼊社(広告事業本部)
2015 アドテクスタジオへ異動 DMP/DSP/SSPで分析 AILabスタート ADEconチームスタート !2
.Bandit Algorithmとは? .Causal Inference + Bandit .Off-Policy Evaluation .Future Work
+ まとめ !3
Banditとは何か?
Bandit Problem? • 広告画像の選択肢がM個ある(ex. M = ) • ユーザーアクセス毎に選択肢を選ぶ •
広告画像を⾒たユーザーがClickするか決める • この操作をT回のアクセス分だけ繰り返す • 最もClickを稼げる選び⽅は何か? !5
Bandit Algorithmの概要 arm_a arm_b Request !6
Bandit Algorithmの概要 arm_a E[r|A = a] V[r|A = a] arm_b
E[r|A = b] V[r|A = b] Request !7
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
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
Banditの良いところ • 古典的にはAB-test(RCT)が使われていたタスク 前半AB-testして、後半は良かったのを使う。 代理店とかでよくやる。 • Banditだと得られるclick数がより多くなる armのモデルを更新しつつ モデルに従って選ぶ !10
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
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
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
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
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 腕の選択を複数回繰り返せば、 あるバッチでの真の確率を得られる。 ⼊ってくるリクエストに対して、 選択肢の選択確率が決まる。
バンディットのログで 因果推論(CI)
AD Template Selection • 広告のテンプレートを選ぶ問題(アイテムは独⽴した別の機構で決定される) • ユーザーの情報Xを得て、選択肢{a,b,c,d}に対してCTRの予測を⾏う • 予測値が最⼤の選択肢を選ぶ(上の例ではb) •
Clickを観測する(Y) • モデル更新は1⽇1回 Policy !17
よくある依頼 どちらのテンプレートが どのくらいCTRが⾼いか? !18
Golden Standard Research Design !19
因果推論による情報の復元 • 選択肢bのCTRを評価したい • バンディットの選択がbの場合にはYの値がわかる • 観測できたYだけで評価をするべきか? • 分布が全体のデータの分布と同じなら問題ない •
バンディットがbを選んだというバイアスが存在 →観測できたデータから全体での結果を推測する →因果推論の出番! !20
IPW(Inverse Probability Weighting) • ex)ある学校で平均⾝⻑を知りたい • 体重だけはなぜか知っている たまたまラグビー部が試合で⽋席 体重が60kg以上の⼈の50%がラグビー部 •
本当の平均⾝⻑(⻘線) • ラグビー部不在の⾝⻑(⾚線) • ⾚線は⻘線よりも下がっている ⾼⾝⻑のデータが⽋損しているから !21 ⾝⻑ 体重
IPW • ⾼⾝⻑が不在という情報はある 体重60kg以上の50%がラグビー部 いない分データを⽔増しする • 体重/出席率すると… kg以上の観測データを2倍に⽔増し kg以下は1倍 •
このデータで平均を算出(緑線) • ⻘線に近くなった! !22 ⾝⻑ 体重
データが⽋損していて、 !23
得られたデータの 観測確率が分かっていれば、 = Propensity Score 再掲 !24
データを⽔増しして、 元の平均を推定することが可能。 !25
因果推論による情報の復元 •黒のデータは⽋損(ラグビー部) •⽋損の理由はバンディットでbが選 ばれないから •では観測確率は? →Policyがbを選ぶ確率 !26
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
Estimator CTRnaive = N−1 N ∑ i clicki CTRIPW =
K−1 K ∑ j Dj clickj pj 選択が⼀致したデータ 全てのデータ 選択が⼀致すると1 しない場合は0 腕の選択確率 !28
Biased Result • Contextual Banditのログから集計 • ログからそのままCTRを集計したもの • 事業責任者やコンサルの⽅が⾒るよう なデータの結果。
• template_ が最も良い結果 26以外必要ないのか? CTRnaive = N−1 N ∑ i clicki !29
IPW Result • バンディットのバイアスを取り除く ためにIPWを利⽤。 • どのテンプレートも優劣無し。 CTRIPW = K−1
K ∑ j Dj clickj pj !30
Heterogeneity • GRFを使う • 条件別の因果効果を推定する • CV的な操作を⾏いRobust性を担保 • GRFで因果効果の傾向が変わる変数を 探索する。
!31
IPW by Interstitial Interstitial ad Not Interstitial ad Interstitial ad
!32
Banditのログでバイアスの少ない 事後的な分析が出来る。 !33
Off-Policy Evaluation (OPE)
ADTemplate Selection • 広告のテンプレートを選ぶ問題(アイテムは独⽴した別の機構で決定される) • ユーザーの情報Xを得て、選択肢{a,b,c,d}に対してCTRの予測を⾏う • 予測値が最⼤の選択肢を選ぶ(上の例ではb) • Clickを観測する(Y)
Bandit Algorithm 再掲 !35
!36 Counterfactual Policyを考える Counterfactual Policy
Research Question How to compare two AI Systems? !37
Golden Standard Research Design !38
RCT is costly • RCTの為にモデルの実装が必要 • ⼤量のアイデアを同時に試すのは不可能 • ハイパーパラメーターなどの調整での利⽤は⾮現実的 •
CF Policyがダメダメだと損失のリスクもある‧‧‧ →なるべくRCTせずに評価を⾏いたい !39
OPE(Off-policy Evaluation) • 既存のPolicyは全てのサンプルでYが観測できている • Yの平均が評価になる。 • 新規のPolicyは既存のPolicyと選択が同じ時だけYがわかる • Yの⾚字の平均が評価になる?
• ⾚字のデータが黒字のデータのランダムサンプルである場合 • ⾚字のデータは全データと同⼀の分布 • 実際にはPolicyの決定に依存しているのでこれはない • どちらかがランダム選択であれば違う →全部のデータに対する評価を得たい !40
そうだ、IPWを使おう。 !41
データが⽋損していて、 再掲 !42
得られたデータの 観測確率が分かっていれば、 = Propensity Score 再掲 !43
データを⽔増しして、 元の平均を推定することが可能。 再掲 !44
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
因果推論と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
Efficient CF Evaluation • AAAI (oral + poster) https://arxiv.org/abs/ .
• ⼤まかな内容 傾向スコアの作り⽅を変える MLで傾向スコアを推定する OPEでの不確実性が減少 !47
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
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
実験結果 • DSPのデータでの実験 • 新しいアイデアを使ったPolicyを作ってOPE • TPSとEPSで評価 • 縦軸:報酬性能の推定値 •
横軸:PSの種類 • EPSだと信頼区間が⼩さい !50
True Propensity Score Case Estimated Propensity Score Case !51
Banditのログでバイアスの少ない Policy評価ができた。 (しかも統計的に効率的に。) !52
Future Work + まとめ
分析(not予測)環境の変化 • 機械学習を利⽤した意思決定の⾃動化が進んできた RTB/Recommend/Ad Selection/Ranking/etc この6年間肩⾝が狭くなる⼀⽅ • ⼀⽅で)⾃動意思決定によって残されたデータを分析する必要性 What is
good policy? / Causal effect of some items →プロダクトとして⾃動意思決定と事後分析をセットで考える必要性 • バンディットはたまたまこの流れが早かった 他の機械学習タスクでもこの流れになる !54
分析者(not予測)が⽬指したいところ • ⾃動意思決定をデザインする(with ML Engineer) 事後的な分析を⾒込んだデザインをする必要がある arg maxやUCBからの卒業(報酬性能も低い) • ⾃動意思決定のデザインに応じた分析をデザインする
MDPを仮定する強化学習のログで因果推論はどうやるか? • 結局両⽅デザインしに⾏く必要がある データが⽣まれるプロセスから、 事後的な分析のプロセスまでをデザインする。 !55
21世紀の分析者は、 データのゆりかごから 墓場までをデザインする。 !56
Enjoy Your Design!