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
730
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
900
Estimating Conversion Rate in Display Advertising from Past Performance Data
juju1008
1
890
Other Decks in Research
See All in Research
NLP2025参加報告会 LT資料
hargon24
1
280
Principled AI ~深層学習時代における課題解決の方法論~
taniai
3
1.1k
公立高校入試等に対する受入保留アルゴリズム(DA)導入の提言
shunyanoda
0
1.9k
Weekly AI Agents News! 12月号 論文のアーカイブ
masatoto
0
290
Prithvi-EO-2.0: A Versatile Multi-Temporal Foundation Model for Earth Observation Applications
satai
3
330
データサイエンティストの採用に関するアンケート
datascientistsociety
PRO
0
480
博士論文公聴会: Scaling Telemetry Workloads in Cloud Applications: Techniques for Instrumentation, Storage, and Mining / PhD Defence
yuukit
1
120
Weekly AI Agents News! 2月号 アーカイブ
masatoto
1
150
A Segment Anything Model based weakly supervised learning method for crop mapping using Sentinel-2 time series images
satai
3
290
ノンパラメトリック分布表現を用いた位置尤度場周辺化によるRTK-GNSSの整数アンビギュイティ推定
aoki_nosse
0
260
Security, Privacy, and Trust in Generative AI
tsubasashi
0
110
請求書仕分け自動化での物体検知モデル活用 / Utilization of Object Detection Models in Automated Invoice Sorting
sansan_randd
0
160
Featured
See All Featured
Making Projects Easy
brettharned
116
6.1k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Large-scale JavaScript Application Architecture
addyosmani
512
110k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
29
9.4k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
356
30k
Navigating Team Friction
lara
184
15k
Faster Mobile Websites
deanohume
306
31k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
2.9k
Measuring & Analyzing Core Web Vitals
bluesmoon
7
390
Why Our Code Smells
bkeepers
PRO
336
57k
The Pragmatic Product Professional
lauravandoore
33
6.5k
Building Adaptive Systems
keathley
41
2.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ཧͷԠ༻Մೳੑ - ଞͷछྨͷϞσϧߟྀ͢Εɺߋʹվྑ͕ग़དྷΔͷͰͳ͍͔