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
The Fellowship of Trust in AI
tomzimmermann
0
130
多様かつ継続的に変化する環境に適応する情報システム/thesis-defense-presentation
monochromegane
1
510
MetricSifter:クラウドアプリケーションにおける故障箇所特定の効率化のための多変量時系列データの特徴量削減 / FIT 2024
yuukit
2
110
Leveraging LLMs for Unsupervised Dense Retriever Ranking (SIGIR 2024)
kampersanda
2
150
Weekly AI Agents News! 9月号 論文のアーカイブ
masatoto
1
110
いしかわ暮らしセミナー~移住にまつわるお金の話~
matyuda
0
140
3次元点群の分類における評価指標について
kentaitakura
0
390
2024/10/30 産総研AIセミナー発表資料
keisuke198619
1
310
ヘルプデスクの事例で学ぶAIエージェント
masatoto
14
8.5k
文書画像のデータ化における VLM活用 / Use of VLM in document image data conversion
sansan_randd
2
150
20240725異文化融合研究セミナーiSeminar
tadook
0
150
「並列化時代の乱数生成」
abap34
3
810
Featured
See All Featured
Become a Pro
speakerdeck
PRO
25
5k
Building Adaptive Systems
keathley
38
2.3k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
4
360
Building Flexible Design Systems
yeseniaperezcruz
327
38k
jQuery: Nuts, Bolts and Bling
dougneiner
61
7.5k
GitHub's CSS Performance
jonrohan
1030
460k
It's Worth the Effort
3n
183
27k
Building a Modern Day E-commerce SEO Strategy
aleyda
38
6.9k
Fontdeck: Realign not Redesign
paulrobertlloyd
82
5.2k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
47
5k
4 Signs Your Business is Dying
shpigford
180
21k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
665
120k
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ཧͷԠ༻Մೳੑ - ଞͷछྨͷϞσϧߟྀ͢Εɺߋʹվྑ͕ग़དྷΔͷͰͳ͍͔