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
Offline A/B testing for Recommender Systems
Search
alpicola
November 20, 2018
Technology
0
1.9k
Offline A/B testing for Recommender Systems
alpicola
November 20, 2018
Tweet
Share
More Decks by alpicola
See All by alpicola
Recommending What Video to Watch Next: A Multitask Ranking System
alpicola
1
820
Kibanaを用いたアクセスログ調査と解析 / Access Log Analysis Using Kibana
alpicola
0
850
Other Decks in Technology
See All in Technology
VPC間の接続方法を整理してみた #自治体クラウド勉強会
non97
1
840
Fargateを使った研修の話
takesection
0
110
Amazon_CloudWatch_ログ異常検出_導入ガイド
tsujiba
4
1.6k
【技術書典17】OpenFOAM(自宅で極める流体解析)2次元円柱まわりの流れ
kamakiri1225
0
210
ガバメントクラウド先行事業中間報告を読み解く
sugiim
1
1.3k
Amazon FSx for NetApp ONTAPを利用するにあたっての要件整理と設計のポイント
non97
1
160
2024-10-30-reInventStandby_StudyGroup_Intro
shinichirokawano
1
630
新R25、乃木坂46 Mobileなどのファンビジネスを支えるマルチテナンシーなプラットフォームの全体像 / cam-multi-cloud
cyberagentdevelopers
PRO
1
130
サイバーエージェントにおける生成AIのリスキリング施策の取り組み / cyber-ai-reskilling
cyberagentdevelopers
PRO
2
200
ABEMA のコンテンツ制作を最適化!生成 AI x クラウド映像編集システム / abema-ai-editor
cyberagentdevelopers
PRO
1
180
よくわからんサービスについての問い合わせが来たときの強い味方 Amazon Q について
kazzpapa3
0
220
わたしとトラックポイント / TrackPoint tips
masahirokawahara
1
240
Featured
See All Featured
Mobile First: as difficult as doing things right
swwweet
222
8.9k
Navigating Team Friction
lara
183
14k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
159
15k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
9
680
Making Projects Easy
brettharned
115
5.9k
GraphQLの誤解/rethinking-graphql
sonatard
66
9.9k
Building Applications with DynamoDB
mza
90
6.1k
Designing on Purpose - Digital PM Summit 2013
jponch
115
6.9k
Fireside Chat
paigeccino
32
3k
A Tale of Four Properties
chriscoyier
156
23k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
231
17k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
43
6.6k
Transcript
Offline A/B testing for Recommender Systems ͯͳ ాத (alpicola) @
จಡΈձ 11/19 1
Offline A/B testing for Recommender Systems — CriteoͷWSDM'18ͷจ — SpotifyͷRecSys'18จͰݴٴ
2
Offline A/B testing for Recommender Systems — CriteoͷWSDM'18ͷจ — SpotifyͷRecSys'18จͰݴٴ
— ΫοΫύου։࠵ͷಡΈձͰ͢Ͱʹհ͞Ε͍ͯͨ — ͕ɺվΊͯ۷ΓԼ͕͛ͨͰ͖Εͱࢥ͍·͢ 3
ΦϑϥΠϯABςετ? — ΦϯϥΠϯͰߦ͏ABςετ࣌ؒͱ͕͔͔ۚΔ — ΦϑϥΠϯͰͦΕʹ͍ۙධՁ͕ߦ͑ΕΞϧΰϦζ ϜվળͷαΠΫϧΛߴԽͰ͖Δ — Ͱਫ਼? ! 4
ϩάʹجͮ͘ΦϑϥΠϯධՁͷݚڀ — Counterfactual estimationͱ͔off-policy estimationͱ ݺΕΔ — WSDM'15ͷνϡʔτϦΞϧ — SIGIR'16ͷνϡʔτϦΞϧ
— ධՁ͚ͩͰͳֶ͘शͷతؔʹ͏͜ͱͰ͖Δ — ͜ͷจͰධՁͷΈΛѻ͏ 5
จͷߩݙ — ΦϑϥΠϯABςετͰ༻͍Δใुͷਪఆख๏NCISͷ ͋Δछͷ࠷దੑΛࣔ͢ — ͜ͷݟʹج͍ͮͯNCISͷ֦ுPieceNCISͱ PointNCISΛఏҊ — ΦϯϥΠϯABςετ݁Ռͱͷ૬͕ؔେ্͖͘ 6
ઃఆ — Top-k ϥϯΩϯά — : ϩά — : ίϯςΩετ
— : ΞΫγϣϯ — : ใु 7
ઃఆ — : ίϯςΩετ͔ΒΞΫγϣϯΛબͿϙϦγʔ — : ݱߦͷϙϦγʔ — : ςετ͍ͨ͠ϙϦγʔ
— : ฏۉॲஔޮՌ — ͜ΕΛਪఆ͍ͨ͠ 8
ઃఆ — ΦϯϥΠϯABςετ — ͷݩͰͷϩάͱ ͷݩͰͷϩά͕͋Δ — ඪຊฏۉͰ , ͦΕͧΕਪఆ
— ΦϑϥΠϯABςετ — ͷݩͰͷϩά͔Β ਪఆ ! 9
ैདྷख๏ — Importance sampling (IS) — Normalized importance sampling (NIS)
— Doubly robust estimator (DR) — Capped importance sampling (CIS) — Normalized capped importance sampling (NCIS) ౷ܭϞϯςΧϧϩ๏ͷจ຺Ͱొ 10
Importance sampling (IS) — ! όΠΞε͕ͳ͍ — — " ʹΑΔߴόϦΞϯε
(unbounded) — όϦΞϯε͕େ͖͍ͱ ͱ ΛൺֱͰ͖ͳ͍ 11
Normalized importance sampling (NIS) Λͬͯ Λஔ͖͑ — ! ҰகਪఆྔʹͳΔ —
— " ґવͱͯ͠όϦΞϯεେ 12
Capped importance sampling (CIS) ॏΈͷ࠷େΛ ʹ (max capping) ॏΈ͕ Ҏ্ͷ߲ࣺͯΔ
(zero capping) 13
CISͷόΠΞε 14
CISͷόΠΞε — όΠΞε ͷ࣌ͷ Ͱbound͞ΕΔ — — ใु͕େ͖͍ͱ͜ΖΛऔΕΔΑ͏ʹվળ͍ͨ͠ ͕ͦ͏͢ΔͱόΠΞε͕େ͖͘ͳΔ !
15
CISͷόΠΞε Cappingͷઃఆʹ͍͍τϨʔυΦϑ͕ଘࡏ͠ͳ͍ ! 16
Normalized capped importance sampling (NCIS) NIS, CIS྆ํͷΞΠσΞΛ࣋ͪࠐΉ 17
NCISͱCISͷؔ 18
NCISͱCISͷؔ CIS͕͍࣋ͬͯͨόΠΞε Λୈೋ߲ͰϞσϧ ͍ͯ͠ΔͱݟͳͤΔ 19
NCISͱCISͷؔ (ಛʹzero cappingͷ࣌) 20
NCISͱCISͷؔ (ಛʹzero cappingͷ࣌) — ͳΒۙతʹόΠΞ ε͕ͳ͘ͳΔ ! — ͷ ,
ʹର͢Δґଘ͕খ͍࣌͞ͳͲ 21
NCISͷόΠΞε 22
NCISͷόΠΞε — ͱcappingͷ༗ແʹ૬͕ؔ͋ΔͱόΠΞε͕େ͖͘ ͳΔ ! — ަབྷҼࢠϢʔβʔͷλΠϓͳͲ͕ߟ͑ΒΕΔ (Table 1) 23
NCISͷόΠΞε 24
จͷΞΠσΞ — ͷϞσϦϯάΛάϩʔόϧ㱺ϩʔΧϧʹ — ίϯςΩετ ʹରͯ͠ہॴతͳNCIS — ͱcappingͷ૬ؔΛݮΒ͢ — Piecewise
NCIS: ׂ͞ΕͨྖҬ͝ͱʹNCIS — Pointwise NCIS: ཁૉ͝ͱʹNCIS 25
Piecewise NCIS (PieceNCIS) ίϯςΩετͷू߹ ͷׂ Λߟ͑Δ 26
Piecewise NCIS (PieceNCIS) ׂ֤ʹରͯ͠NCIS 27
ׂͷྫ దͳؔ ΛఆΊͯ ֤ Ͱ ͷ ʹର͢Δґଘ͕খ͘͞ͳΔΑ͏ʹ 28
Pointwise NCIS (PointNCIS) ཁૉ୯ҐͰׂ͢Δ (i.e. ) ಛఆͷίϯςΩετʹର͢Δαϯϓϧ͘͝গͳ͍ͷ ͰૉʹNCISΛద༻Ͱ͖ͳ͍ 29
Pointwise NCIS (PointNCIS) — ΞΫγϣϯʹ͍ͭͯपลԽ͢Δ ͱਖ਼֬ʹٻΊΒΕΔ — ΞΫγϣϯͷ͕ଟ͍ͱܭࢉ͕ߴίετ ! —
ΛαϯϓϦϯάͰٻΊΔ 30
Midzuno-Sen method 1. Λαϯϓϧ 2. Λ ͔Β ͳͷ͕ಘΒΕΔ·Ͱαϯϓϧ 3. Λ
͔Βαϯϓϧ 4. Λฦ͢ ͜͏ͯ͠ಘΒΕΔΛ ͱॻ͘ 31
Pointwise NCIS (PointNCIS) — ͷ͏ͪ ͕ ͷσʔλແࢹͰ͖Δ — ใु͕εύʔεͳ࣌ʹޮతʹܭࢉͰ͖Δ !
32
࣮ݧ — ϓϩϓϥΠΤλϦͷσʔληοτ — 39छɺ߹ܭͰઍԯ݅ͷϩάσʔλ — ΫϦοΫϕʔεͷใु (εύʔε͔ͭࢄେ) — ରCIS,
NCIS, PieceNCIS, PointNCIS ( ) — IS, NISόϦΞϯε͕ߴ͗͢ΔͷͰআ֎ 33
ΦϯϥΠϯʗΦϑϥΠϯABςετͷ૬ؔ 34
ద߹ͱِӄੑ ʮ ͕ ΑΓΑ͍͔Ͳ͏͔ʯͷ2༧ଌͱͯ͠ݟΔ 35
࣮ݧ݁Ռͷ·ͱΊ — CIS૬͕ؔෛ — શମతʹΊͷਪఆ͕ग़͍ͯͨ (Figure 4) — CIS⇒NCISͰେ͖͘վળ —
NCIS⇒PointNCISͰِཅੑ͕͞ΒʹԼ͕Δ — ద߹NCISҎޙͦ͜·ͰΑ͘ͳΒͳ͍ — ࣮ߦʹ͓͍ͯਫ਼ʹ͓͍ͯPointNCIS͕Α͍ 36
Appendix — ͕খ͍͞ͱ ͕ cappingΛ͑Δ͜ͱ — Max cappingͰ ʹͳΔΑ͏ͳ ৽͍͠capping
͕ͱΕΔ (Lemma A.3) 37