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
Real-Time_Bidding_Algorithms_for_performance-Ba...
Search
jujudubai
August 17, 2014
Research
0
720
Real-Time_Bidding_Algorithms_for_performance-Based_Display_Ad_Allocation.pdf
いろいろと参考にしながら、要約を。
この論文はとても参考になります。
jujudubai
August 17, 2014
Tweet
Share
More Decks by jujudubai
See All by jujudubai
juju1008
juju1008
1
4.2k
Realtime Bid Optimization with Smooth Budget Delivery in Online Advertising
juju1008
2
880
Estimating Conversion Rate in Display Advertising from Past Performance Data
juju1008
1
860
Other Decks in Research
See All in Research
第79回 産総研人工知能セミナー 発表資料
agiats
2
160
データサイエンティストをめぐる環境の違い 2024年版〈一般ビジネスパーソン調査の国際比較〉
datascientistsociety
PRO
0
580
Large Vision Language Model (LVLM) に関する最新知見まとめ (Part 1)
onely7
21
3.6k
Geospecific View Generation - Geometry-Context Aware High-resolution Ground View Inference from Satellite Views
satai
1
100
非ガウス性と非線形性に基づく統計的因果探索
sshimizu2006
0
370
Physics of Language Models: Part 3.1, Knowledge Storage and Extraction
sosk
1
950
20240918 交通くまもとーく 未来の鉄道網編(こねくま)
trafficbrain
0
230
12
0325
0
190
129 2 th
0325
0
240
Weekly AI Agents News! 7月号 論文のアーカイブ
masatoto
1
230
渋谷Well-beingアンケート調査結果
shibuyasmartcityassociation
0
260
KDD論文読み会2024: False Positive in A/B Tests
ryotoitoi
0
200
Featured
See All Featured
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
16
2.1k
Practical Orchestrator
shlominoach
186
10k
The Art of Programming - Codeland 2020
erikaheidi
52
13k
Adopting Sorbet at Scale
ufuk
73
9.1k
Intergalactic Javascript Robots from Outer Space
tanoku
269
27k
Thoughts on Productivity
jonyablonski
67
4.3k
A better future with KSS
kneath
238
17k
Faster Mobile Websites
deanohume
305
30k
Scaling GitHub
holman
458
140k
Visualization
eitanlees
145
15k
A Tale of Four Properties
chriscoyier
156
23k
Gamification - CAS2011
davidbonilla
80
5k
Transcript
Review: “Real-Time Bidding Algorithms for performance-Based Display Ad Allocation” Tatsuki
Sugio
ຊจͷ֓ཁ A. demand-side, supply-side • ༧ࢉࢿͷ࠷దԽɺऩӹʢrevenueʣͷ࠷େԽ • RTB Exchangeʹ͓͍ͯɺimpຖʹΩϟϯϖʔϯΛׂΓͯΔ ➡
ϦΞϧλΠϜͰͷ࠷దԽʹΑΓ࣮ݱ ➡ errorͷେ͖͞ʹԠͯ͡ύϥϝʔλΛௐ B. ՝ • มɺ੍͕ଟ͍ ➡ ઢܗܭըͷରͷղʹΑΓ࣮ݱ • ΦϑϥΠϯ࠷దԽͰཻ͕ૈ͍ ࢢͷมԽʹରͯ͠దԠతͳbid͕Ͱ͖ͳ͍ ➡ ϦΞϧλΠϜͰͷ࠷దԽʹΑΔࡉཻ͔͍Ͱͷ࠷దԽΛ࣮ݱ C. ํ๏ • online bidding algorithm frameworkΛఏҊ • Ωϟϯϖʔϯຖͷbidػೳύϥϝʔλͷߋ৽ํ๏ʢWaterlevel or Model-based ʣͱͯ͠ɺطଘͷϦιʔε ͷۙࣅΞϧΰϦζϜʹinspire͞Εͨํ๏ͱɺbidͷউͷΛϞσϧԽͯࣜ͠ʹΈࠐΜͩͷΛఏҊɻ
Formulation A. ऩӹͷఆٛ B. ೖࡳֹͷܾఆɺௐ ࠂओผ
ೖࡳֹௐͷ߲ ͜Ε͔Β͜ͷzЋzΛٻΊͯɺ࠷దͳzCJEQSJDFzΛਪఆ͠·͢
LR Formulation • ࠷దԽ ΩϟϯϖʔϯKͷJ൪ͷJNQνϟϯεʹJNQͰ͖͔ͨ൱͔ʢೋʣ WJKQJK RJKˡ $53 $1$ ΩϟϯϖʔϯKͷඪJNQʢ༧ࢉ੍Λ݉ͶΔʣ
εϥοΫ݅
• ࠷దԽͷର
➡ α,βΛٻΊΔ͜ͱ͕త ܭࢉճɺO(mn)Ͱͳ͘ɺO(m+n) ➡ શϢχϞδϡϥߦྻʢtotally unimodular matrix, TU ߦྻʣʹجͮ͘ ࢀߟʣhttp://ja.wikipedia.org/ ๚ऀͷ૿ՃͷܦࡁతʢJNQͷ࠷খՁ֨ͱʣ ༧ࢉͷ૿Ճͷܦࡁతʢ࠷খརӹͱʣ
Real-Time Bidding Algorithm • ٙࣅίʔυ HPBMBDIJFWFE Ќͷܭࢉ POMJOF"MHPSJUINͷద༻
Control-theoretic Bid Adjustment • waterlevel-base update (online algorithm) - ίετߟྀ͠ͳ͍
- PIɺPIDཧ JNQ FSSPS FSSPSʹͲΕ͚ͩૣ͘Ԡ͢Δ͔ͷ
1*%੍ޚཧ 1*%੍ޚͷجຊࣜɺภࠩFʹൺྫ͢Δग़ྗΛग़͢ൺྫಈ࡞ʢ1PQPSUJOBMBDUJPO1ಈ࡞ʣͱɺ ภࠩFͷੵʹൺྫ͢Δग़ྗΛग़͢ੵಈ࡞ʢ*OUFHSBMBDUJPO*ಈ࡞ʣͱɺ ภࠩFͷඍʹൺྫ͢Δग़ྗΛग़͢ඍಈ࡞ʢ%FSJWBUJWFBDUJPO%ಈ࡞ʣ͔ΒͳΔɻ ௨ৗɺ1ಈ࡞Λओମʹͯ͠ɺิॿతʹ*ಈ࡞ͱ%ಈ࡞Λ੍ޚରʹԠͯ͡దʹΈ߹ΘͤΔɻ ૢ࡞ྔ.7ɺͦΕͧΕͷͱͯ͠ɺ࣍ࣜͷ༷ʹද͞ΕΔɻ IUUQXXXOJDPNXIJUFQBQFSKB
Model-based Bid Adjustment • γεςϜ੍ޚཧʹجͮ͘Ξϓϩʔν(PI:online algorithm) - ίετɺೖࡳֹߟྀ FSSPSʹૣ͘ͲΕ͚ͩૣ͘Ԡ͢Δ͔ͷ ཧతͳೖࡳՁ֨
ཧతͳউʢHJʹ߹ΘͤΔͨΊʹඞཁͳউʣ ؍ଌ͞Εͨউ ೖࡳίετ .-&ͷύϥϝʔλɻ XJOͨ͠ೖࡳ X ͷ౷ܭྔ͔Βಋ͔ΕΔɻ
a Practical formulation • ίετ߲ͷಋೖʹΑΓߋʹҰൠԽͨ͠ओ
• ίετ߲ͷಋೖʹΑΓߋʹҰൠԽͨ͠ର JNQ(SPVQ QMBDFNFOU Jͷ֫ಘͰ͖ͦ͏ͳJNQ
Experiments • ࣮ݧ݁Ռͷ֓ཁ - αͷௐʹΑͬͯೖࡳͷ࠷దԽ͕ߦ͑Δ͔Ͳ͏͔ - ҟͳΔ࠷దԽख๏ͷಋೖʹΑΓͲͷఔύϑΥʔϚϯε͕ҟͳΔͷ͔ - αͷॳظ͕ͲͷఔӨڹ͢Δͷ͔ •
࣮ݧ݅ - ༻σʔλσΟεϓϨΠωοτϫʔΫͷσʔλ - ฏۉ120Mͷimp͕͋ΔαΠτͰ࣮ݧ - 4ͭͷCPCΩϟϯϖʔϯ͕ର • σʔλ • timestamp,placement,user,campaign,clicks,impressions • ॱʹt,i=(placement:user),j,cij(t),xij(t)
MJGU ʹ ࢪࡦΛ࣮ࢪ͠ͳ͍࣌ͷ݁Ռ ࢪࡦΛ࣮ࢪͨ࣌͠ͷ݁Ռ IUUQXXXBMCFSUDPKQUFDIOPMPHZDSNMJGUIUNM
- Experiments 1 • ؍ଌͱγϡϛϨʔγϣϯʹΑΔͷlift ➡ offlineͷΈΑΓonlineͰαΛௐͨ͠ํ͕͕ྑ͍
➡ model-based bid ͱ Waterlevel bidͷൺֱ - offlineͰͷαͷࢉग़1ͷσʔλ - αࢉग़ޙͷ4ؒͷσʔλΛൺֱ ➡ online algorithmoffline algorithmʹରͯ͠90ˋҎ্ͷ ➡ ҆ఆੑModel Bidder͕ྑ͍
- Experiments 2 • hourlyͷมಈʢ࣌ؒͷ҆ఆੑ֬ೝʣ ➡ Waterlevel Bidder࣌ؒతͳ҆ఆੑ͕ߴ͍ ➡ Model
Bidderෆ҆ఆ
- Experiment 3 • online algorithm(Waterlevel Bidder)ʹ͓͚ΔαͷॳظͷӨڹ ➡ ॳظͷมಈ΄ͱΜͲͳ͍ ͔͠͠ɺΩϟϯϖʔϯ༧ࢉͷ੍͕ݫ͚͠ΕӨڹ͕͋Δ͔…
• ༧ࢉ੍ʢݫʣ ➡ ༧ࢉ੍͕ݫ͚͠Εɺ ॳظͷมಈ͋Δɻ offline࠷దԽͨ͠αͷ͕ྑ͍ɻ - Experiments 4
Conclusion • ݁ - γϯϓϧ͕ͩཧతഎܠͷ͋Δonline algorithmΛఏҊ - PIDཧͷԠ༻Մೳੑ - ଞͷछྨͷϞσϧߟྀ͢Εɺߋʹվྑ͕ग़དྷΔͷͰͳ͍͔