Ad-DS Paper Circle Intro

Intro: 予測モデル  AI事業本部金子雄祐   1

目次 2 • DSPにおける予測問題と、その発展の歴史  • 各モデルの概観  • ターゲティングの未来と現在地   

はじめに 3 • Clickなどの事象の確率を正しく予測できることがDSPにとって望ましいことは所与とする  ◦ pricing回で触れる  • 歴史認識などは実は厳密でない部分があるが、やや大雑把にまとめている 

DSPにおける予測問題と  その発展の歴史  4

DSPにおける予測モデルの発展はどういう歴史か? 5 • 簡単に言うと、推論制約とパフォーマンスのトレードオフ   ◦ RTBでは、全体のプロセスは約100ms(0.1秒)以内に処理される  ◦ そのうち、DSPの広告処理選定の時間は更に短い  ▪
ましてやMLの推論機構となるとなおさら  • このような厳しい推論制約の中で、少しでも表現能力が高いモデルを活用したい 

DSPにおける予測問題の特徴 6 • 以下の特徴を持つ  ◦ テーブルデータ  ▪ userの属性情報・user行動データ(過去のclick履歴など)・広告枠データ  ▪ これらの相互作用が存在 
◦ 高次元かつスパースデータ  ▪ テーブルの大部分が0で特徴量の数が非常に多い  ▪ このようなデータでも機能するモデルを使用しないといけない  ◦ 不均衡データ  ▪ 正例の数が非常に少ない 

予測モデルの発展史 7 • 大きく分けると、3つに分割できる  ◦ ロジスティック回帰(2011 ~ 2014)  ◦ FM,
FFM(2014 ~ 2017)  ◦ DeepFM, DCNなどのDeep系の台頭(2017~)  • これらの期間における代表的なpaperや細かいテクニックを簡潔に紹介する 

各モデルの概観  8

LR 9 • RTB系の初期のpaperはロジスティック回帰を用いることが標準的だった  • 以下のメリット・デメリットが存在する  ◦ メリット  ▪ 推論が軽く、実装が簡単 
▪ 高次元スパースデータでも十分機能する  ◦ デメリット   ▪ 交互作用項の考慮を手動で特徴量を作る必要がある  • 代表的なpaper  ◦ Chen, Ye, et al [KDD 2011]  ◦ He, Xinran, et al [AdKDD 2014]  ◦ Chapelle et al [TIST 2014] 

Negative down sampling 10 • 不均衡データのMLの学習において、一般的に用いられるテクニックの一つ  ◦ 大量にある負例データのみをsamplingする  ◦ 出力される予測値についてはなんらかのcalibrationをかける 
• 上記は、He, Xinran, et al [AdKDD 2014] で提案されたcalibration 

Negative down sampling 11 • He, Xinran, et al(AdKDD 2014)での検証結果 

hashing trick 12 • 大規模データにおける省メモリ化の手法の一つ; [Weinberger et al. 2009]  ◦
ハッシュ関数を特徴量に適用し、その値のmodを直接インデックスとして使用  ◦ ハッシュの衝突などの問題は一部存在する  • 上記はChapelle et al [TIST 2014] からの引用 

FM, FFM 13 • それぞれの正式名称は以下  ◦ Factorization Machines [Rendle TIST
2012]  ◦ Field-aware Factorization Machines [Yuchin et al WWW 2017]  • 以下のメリット・デメリットが存在する  ◦ メリット  ▪ 高次元スパースデータでも十分機能する  ▪ 2次の交互作用項目の考慮が可能  ◦ デメリット   ▪ LRに比べると推論が重い 

FFMが席巻した経緯 14 • Kaggleのcompetition(3 idiots)がきっかけ  ◦ 上が2014年のCriteo Display Advertising Challenge 
◦ 下が2015年のAvazu Click-Through Rate Prediction  • FMを拡張したFFMを使用していた 

FFMが席巻した経緯 15 • libffmというパッケージを提供している 

社内事例(公開情報) 16 • 社内事例は上記の発表を参照  ◦ サイバーエージェントにおけるMLOpsに関する取り組み 

Deep時代 17 • FM, FFMをDeep系に拡張したモデルの登場  ◦ DeepFM [Huifeng Guo et
al. IJCAI 2017]  ◦ DCN [Wang et al. ADKDD 2017]  • 以下のメリット・デメリットが存在する  ◦ メリット  ▪ FM、FFMより更に表現能力が高い  ◦ デメリット   ▪ 推論がさらに重い 

大量のモデル 18 • DeepCTRというパッケージが存在する  ◦ 提案された大量のモデルを概観できる  ◦ スクショ以下もまだ続いている  • 当時はモデルの提案を競う時代だった 
◦ ベンチマークの精度改善を競う時代  ◦ LLMの登場で終わった気もする 

ターゲティングの未来と現在地  19

プライバシー保護とターゲティング広告 20 • 近年，Web上におけるプライバシー保護は非常に重要な問題   ◦ (是非は置いておくとして)ユーザー行動のトラッキングをベースにしたビジネスモデルは変化や適応を余儀なくされている  •
色々な出来事(3rd party cookie規制 → IDFA規制の流れ)   ◦ 2018年5月 : 欧州でGDPR制定   ◦ 2020年1月 : アメリカでCCPA(カリフォルニア州消費者プライバシー法)制定   ◦ 2021年4月 : iOS14.5, ATTリリース 

プライバシー保護とターゲティング広告 21 • これらの変更に置いてターゲティング広告配信事業者(DSP/SSP)が困難になること   ◦ 広告効果の適切な計測  ▪ 広告をclickした後のユーザー行動計測が困難に  
◦ 効果的なターゲティング広告配信  ▪ そもそも識別子が流れてこないのでターゲティングもなにもない   • また、予測モデル的には以下の影響が存在する   ◦ 「大量の特徴量を元に、高度なターゲティングを行う」という世界観の崩壊   ◦ これらに対応する手法は何なのか?  

Learning a logistic model from aggregated data 22 • AdKDD
2021のpaper   • 著者はCriteo所属 

Learning from aggregated data 23 • 従来得られているデータは左のTable 1のようなデータ   •
個人Idによる識別が不可能になると，例えばTable 2のような集計データしか得られなくなる   • このようなデータしか得られなくなった時に，既存の予測モデル(CTR予測など)は機能しなくなる   • どのようなモデルを使えばいいのか?  

Googleの対応と今後 24 • Googleは2024年にはサードパーティークッキーの廃止を予定していた   • 代替的にGoogleはプライバシー配慮を行う広告プラットフォームの開発を行なっていた   ◦ プライバシーサンドボックス
  • しかし、2024年7月に廃止の撤回を宣言   ◦ プライバシー保護の潮流に全く反するこの宣言がどのような顛末を迎えるかは全く不明  

現在地: Deepモデルは実適用可能なのか? 25 • DeepCTRにあるDeepモデルだがABテストをやっているpaperは多くない(はず)  • 理由は当然ながら、推論制約によるもの  • 一方で、Deep系を使っていると主張するDSP系プロダクトが現在は台頭(RTB House
etc)  ◦ レコメンドタスクなどでは、バッチで学習で問題ないので可能ではある  • Q: このようなDeep系モデルを予測に実適用するMLOps的なアプローチは存在するのか?   ◦ 今回輪読するOutbrain論文につながっていく... 

paper 26 • Chen, Ye, et al. "Real-time bidding algorithms
for performance-based display ad allocation." Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 2011.   • He, Xinran, et al. "Practical lessons from predicting clicks on ads at facebook." Proceedings of the eighth international workshop on data mining for online advertising. 2014.   • Chapelle, Olivier, Eren Manavoglu, and Romer Rosales. "Simple and scalable response prediction for display advertising." ACM Transactions on Intelligent Systems and Technology (TIST) 5.4 (2014): 1-34.   • Rendle, Steffen. "Factorization machines with libfm." ACM Transactions on Intelligent Systems and Technology (TIST) 3.3 (2012): 1-22.   • Weinberger, Kilian, et al. "Feature hashing for large scale multitask learning." Proceedings of the 26th annual international conference on machine learning. 2009.   • Juan, Yuchin, Damien Lefortier, and Olivier Chapelle. "Field-aware factorization machines in a real-world online advertising system." Proceedings of the 26th International Conference on World Wide Web Companion. 2017.   • Guo, Huifeng, et al. "DeepFM: a factorization-machine based neural network for CTR prediction." Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2017.  • Wang, Ruoxi, et al. "Deep & cross network for ad click predictions." Proceedings of the ADKDD'17. 2017. 1-7.   • Gilotte, Alexandre, and David Rohde. "Learning a logistic model from aggregated data." AdKDD Workshop. 2021.  

Intro: CVR予測  AI事業本部金子雄祐   27

目次 28 • CV予測固有の問題  • 遅れCV  • imp-click-cvのログの差異と、セレクションバイアス  • 現在地? 
 

CV予測固有の問題  29

CVR予測の問題定義と固有の課題 30 • まず、CVR予測モデルを次のように定義する  ◦ imp, clickの条件付きのCV確率を予測する問題  ◦ つまり、p(conversion|click,
impression) の推定問題とする  • CTR予測モデルに比べて、次の問題を持つ  ◦ 正例データが更に少ない  ▪ clickより、さらに得られるデータは少なくなる  ◦ 遅れCVの問題の存在  ◦ 学習データと推論データの差異の問題(セレクションバイアス )  • 遅れCVとセレクションバイアスについて、本スライドは解説する 

遅れCV  31

遅れCVとは何か? 32 • CVは、広告主によって種々の形態がある  ◦ ゲームApp: アプリインストール  ◦ EC: 商品購入 
• 通常、impからclickまでは短時間で行われるが、clickからcvまでは通常長い時間がかかる  ◦ 短いものだと数分だが、長いものだと10 ~ 20日(図はChapelle 2014)  • このようなタイムラグは、どのような問題を引き起こすのだろうか? 

遅れCVはなぜ問題か? 33 • CV予測の学習時に、遅れのせいで本来の正例が負例に入ってしまう (CAプレスより引用)  ◦ これにより、予測モデルは本来のCV確率を下回る予測を行う  ◦ 機械学習におけるバイアス除去といった話につながる 

Chapelle(KDD 2014) 34 • 遅れCV関連で最も古典的なpaper  • アプローチ自体はシンプルで、CVまでの時間を別途モデリングする 

社内事例 35 • 社内事例で最も有名なのはYasui et al. (WWW 2020)  ◦ AI
Lab & Dynalystでの研究結果  ◦ DynalystでのABテストまで行なっている結果も示されている  • IPWによるバイアス補正を行なっている 

実務上の問題: 計測ツールとの関係 36 • 遅れCV自体は一般的な問題だが、実務上の一般性には注意をする必要がある  • これは、last click という計測上の慣例が問題となる  ◦
これは、最後にclickをした配信媒体に成果紐づけをするというもの   ◦ つまり、last clickがある場合、極端な遅れがあるCVはそもそも成果紐づけされない  • 計測上の優位性があるプラットフォーマーや、競合がいない広告施策(例えば広告を通じたクーポン認知による販促企画)などで相対的に重要度が高くなる  ◦ 「計測上の優位性がある」についてはトラッカー周りの話をドメイン知識のある人に聞いてみるのが良い  ◦ 遅れCVが重要でない場合、practicalには正例をclick後N日以内のものに絞る 

imp-click-cvのログの差異と、セレクションバイアス  37

CVR予測モデルとセレクションバイアス 38 • CVR予測モデルが、click, impressionで条件付きのcvを予測する問題であったことを思い出す   ◦ p(conversion|click, impression) の推定問題 
◦ つまり我々はclickされたデータからCVを推定するMLモデルの構築をする  • しかし、実際はimpした広告に対して、clickとcvの両方が発生しないと成果計測がされない  • これは次の問題を引き起こす  ◦ 定義上の制約  ▪ コンバージョンはクリックなしには発生し得ない   ▪ クリックしていない広告のコンバージョン確率は定義できない   ◦ データの性質  ▪ クリックされていないデータのコンバージョンラベルは「0」ではなく「未定義」  ▪ これはデータが欠損しているのではなく、そもそも存在し得ないデータ 

CVR予測モデルとセレクションバイアス 39 • これも、次のようなunbiased learningの問題につながる(図はESMMより)  ◦ 次のようなデータの差異が存在する  ▪ 学習時：clickされたimpressionのみ  ▪
推論時：全impression(当然、実務上そうせざるを得ない)  ◦ したがって、分布の違いによる予測精度低下が発生する 

Zhang et al(2016 KDD) 40 • CVR予測ではなく、CTR予測ではあるがZhang et al(2016 KDD)を簡単に紹介 
◦ 「分布の差」の問題がどのように発生するかの一例として紹介  • オークションなので、勝利有無を通じてbid requestとimpのデータの分布差が発生 

Zhang et al(2016 KDD) 41 • オークションによるセレクションバイアスは上の(1)式に分解できる  • つまり、win rate予測
を行えばうまく補正ができる  ◦ 過去の入札履歴から推定した勝率で重み付けを行う  ◦ 次々回のbid landscape回とも関係  • CVR予測のケースとはセレクションの発生経由が違うので、このアプローチ自体は使えない 

現在地?  42

遅れCV 43 • Yang et al.(AAAI 2021), Wang et al.
(KDD 2023)など、直近でも新規事例がある  • これや、過去のChapelle, Yasui et al. の実装は以下のレポジトリに存在  ◦ https://github.com/ThyrixYang/es_dfm  ◦ https://github.com/yfwang2021/ULC 

サンプリングバイアス 44 • さきほど述べた通り、Zhang et al自体はCVR予測問題には使用できない  • これらの疑問は、今回輪読するESMMにつながる  ◦ サンプリングバイアスへの対処 
◦ データスパース性の対処 

paper 45 • Yasui, Shota, et al. "A feedback shift
correction in predicting conversion rates under delayed feedback." Proceedings of The Web Conference 2020. 2020.   • Chapelle, Olivier. "Modeling delayed feedback in display advertising." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014.   • Yang, Jia-Qi, et al. "Capturing delayed feedback in conversion rate prediction via elapsed-time sampling." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 5. 2021.  • Wang, Yifan, et al. "Unbiased Delayed Feedback Label Correction for Conversion Rate Prediction." Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.   • Zhang, Weinan, et al. "Bid-aware gradient descent for unbiased learning with censored data in display advertising." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.   • Ma, Xiao, et al. "Entire space multi-task model: An effective approach for estimating post-click conversion rate." The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval. 2018.  

Intro:   Pricing,   Bid Shading  AI事業本部金子雄祐  
46

はじめに 47 • 本稿はゲーム理論に基づく記述が多く、参加者の多くはこの知識はないと思われるので特に専門用語についてはなんとなくの理解で構わない  • また、おそらくはやや独自の視点に基づく歴史理解になっていると思われるので(一定以上の価値はあると金子は信じているが)、これが業界の共有知識のように受容するのは注意が必要である  • 割とあやふやな記憶で書いているので、特に今回の資料は不正確な記述があり得るのでこちらも注
意すること  ◦ 金子が学部1年くらいに勉強した + 学部3年で神取道宏ゼミでゲーム理論のTheoryよりの研究を志していた頃のうろ覚え  ◦ AI Labにもっと詳しい人がいます 

目次 48 • オークション理論とPricing  • 収入同値定理と第一価格オークションへの移行  • Bid Shading 

オークション理論とPricing  49

第1価格オークションと第2価格オークション 50 • Open RTBにおいては、上記のようなパラメータ、atが存在する  ◦ スクショはOpen RTB 2.6からの引用  •
これは、オークションタイプと呼ばれるものである  ◦ First Price(第一価格オークション): 最高入札価格が勝利者の支払い価格となる  ◦ Second Price(第二価格オークション): 第二位入札価格が勝利者の支払い価格となる  • このような二つの形式がわざわざ指定されている理由はどこにあるのだろうか? 

経済学とオークション 51 • 経済学分野では、オークション理論は古くから研究の対象であった   ◦ Nobel Prize in 1996:
William Vickrey   ◦ Nobel Prize in 2007 : Myerson & Maskin & Hurwicz   ◦ Nobel Prize in 2020: Milgrom & Wilson   • RTBでも、最古のものの研究は経済学の分野からいくつか出ている   ◦ Edelman et al. (2007, AER)   ◦ Varian(2009 AER)  Photo from the Nobel Foundation archive. Photo from the link

プラットフォームとオークション形式 52 • 上記記述はVarian et al. (2014 AER)よりの引用  ◦ 検索型広告やFacebookは複数枠を扱うので一般的に問題が難しい 
▪ Edelman et al.(2007)もGSPやVCGを対象にしたものだった  ◦ 一方で、ディスプレイ広告は基本的に単一枠なので問題が比較的シンプル  • 上記記述でも分かる通り、当時のディスプレイ広告では第二価格オークションが主流だった  ◦ これは一体なぜなのか? 

正直申告戦略 53 • 第二価格オークションにおいて、以下の有名な結果が存在する  ◦ 入札者は、自分が本当に支払ってもよいと考える金額をそのまま入札する (= 正直申告戦略)のが最適な戦略となる  •
Googleが2009年頃にAdXにおいて第二価格オークションを採用  ◦ 正直申告戦略自体はシンプルだというメリットが有る  • 上記の記述はChen et al.(2011 KDD)からの引用  ◦ (非制約環境なら)正直申告戦略が最適だという解釈が可能な記述になっている 

DSPにおける正直申告とその値付け 54 • DSPの正直申告は、種々の請求形式によって差分はあるが、基本的に以下の式で良い   ◦ CPM = eCTR *
eCVR * Conversion Value   • これが、第1, 2回で扱ったようなCTRやCVRの推定をうまく行うことが望ましい根拠となる   • Lee et al(2012 KDD)にも上記の引用のように同様の”value”の記述が存在   最適な入札額は、 CPC目標とCTR の積（もしくは CPA目標とCVRの積）として算出できる

DSPにおける正直申告とその値付け 55 • 現実的には種々の制約があるので、正直申告を行えばいいわけではない  • 上記はChen et al.(2011 KDD)の提案  
◦ αをbidの調整項として提案  • αの決め方のアプローチも論文内では提案されている  ◦ win rateの推定の利用など  • 次回以降の bid land scapeなどの話につながる  

収入同値定理と  第一価格オークションへの移行  56

SSP側の事情 57 • なぜSSPは第二価格オークションをやっていたのか?  ◦ 第一価格オークションのほうが収益が多いならそちらをやるはず  • 第一価格オークションの時に何が起きそうか?  ◦ 以下のどちらが起きるかは直感的にはどちらもありえそうではある 
▪ 高値で入札しないように価格を下げようとするかもしれない  ▪ 逆に競争が激化して値付けが高すぎることになるかもしれない  • この疑問について、なんらかの結果はないだろうか? 

収入同値定理 58 • オークション理論における最も有名な定理の一つに収入同値定理が存在する  ◦ 一定の条件下で、第一価格オークションと第二価格オークションのどちらも、売り手の期待収入は等しくなる
  • 要するにSSPの期待収益は変わらないというのが結論である   • 収入同値定理の上記の記述自体はもっと一般化可能で、仮定もゆるめたverはあるのだが、そこまで詳しくないので紹介しない   • 上はChen el al.(2011 KDD)の記述だが”revenue equivalence theorem”と実は触れられている  

第1価格オークションへの移行 59 • 2019年の秋にGoogleが第一価格オークションへの移行を宣言した  ◦ そもそも、OpenRTBで見た通りで、以前は第一価格と第二価格は混在している状態だった   •
Googleの移行をきっかけに、業界標準は第一価格になった   ◦ なぜこの移行は起こったのか?  

第1価格オークションへの移行; その理由 60 • 収入同値定理が現実にはRTBにおいて成り立たない   ◦ そもそも仮定がRTBにおいて成立するかが全く自明ではない   ◦
実証的にもRTB以外の場面で現実には成り立たない例が知られている   • 第二価格オークションはそもそも開催主の不正に弱い   ◦ 例えば、勝利価格を誤魔化せばその差分を開催主が詐取することができる   ◦ Rothkopf et al. (1990 JPE)でも触れられている   ◦ 金子は2018の駒場祭で不正などに対して頑健なメカニズムについての発表が、現在UTMDに所属している院の同期からされているのを聞いたのを覚えている   ◦ SSPの不正については確かに問題で、Googleの発表でも触れられていた   • 収益性?  ◦ 定かではないが、結局こちらのほうがSSPやmediaの収益が大きいのでは?  

Bid Shading  61

DSPの対応; オークション理論的アプローチ 62 • 第一価格オークションの移行に対して、DSP側はどのような値付けをすべきなのか?   • オークション理論の文脈では、上のVickrey(1961)の結果が最もシンプルな結果   ◦
Nはオークション参加人数   • ただし、RTBではそもそもこのNが不明な上に、これが成り立つ仮定を満たすかも怪しい   • それではどうすべきか?  

DSPの対応; 正直申告との関係 63 • 一方で、かなりシンプルな仮定に基づいて、次の事を言うことはできる   ◦ 「正直申告より高い値付けをすることは適切ではない」   •
まず、プレイヤーiについて以下のnotationを置く   ◦ 真の評価額(=正直申告額)：vi   ◦ 入札額：bi > vi  ◦ 効用関数：u(・)（ただし、狭義単調増加関数とする）   • 勝利価格をhとすると、次のパターンで分類ができる   ◦ パターン1: h < vi < bi   ▪ biで入札：u(vi - bi) < u(vi - vi) = u(0)   ▪ viで入札：u(vi - h) > u(0)   ▪ よって、viで入札したほうがいい  

DSPの対応; 正直申告との関係 64 • 勝利価格をhとすると、次のパターンで分類ができる   ◦ パターン2: vi <
h < bi   ▪ biで入札：u(vi - h) < u(0)   ▪ viで入札：winできないので、u(0)   ▪ よって、viで入札したほうがいい   ◦ パターン3: vi < bi < h   ▪ biで入札：winできないので、u(0)   ▪ viで入札：winできないので、u(0)   ▪ どちらも変わらない  • よって、基本的に正直申告以上の価格をつけるのはよくないといえる  

DSPの対応; 正直申告との関係 65 • 前述の証明における仮定は、(おそらく)以下だけ   ◦ 効用関数が狭義単調増加(一般的な仮定)   ◦
自分の評価額が他者の入札や評価額に依存しない   ▪ この2番目の仮定が、そもそも予算アロケなどが存在するRTB、特にターゲティング広告において成立するのかはやや怪しいが...   • だが、上記の結果からも適切な価格下げ、 bid shading というアプローチが要請されるはず   ◦ しかし、どのようにbid shadingをすべきか?  

MINIMUM_BID_TO_WIN 66 • 再びOpenRTB2.6を見ると、実は上記のようなパラメータがある   ◦ ${AUCTION_MIN_TO_WIN}; オークションに必要な最低勝利価格   •
Googleも、MINIMUM_BID_TO_WINという同様のパラメータを提供している   • このような情報がRTBで得られている中で、どうbid shadingを上手くやるか?   ◦ これが今回の輪読論文につながっていく...  

余談 67 • 第二価格オークションにおける正直申告戦略周りの結果や収入同値定理の証明は上記の坂井(2010)に直感的な証明が載っていた気がする  ◦ 金子は学部1年のころに読んでいたが、正直かなり狐に化かされたような気持ちになったのをよく覚えている   ▪ こういうのを直感的に理解できないとゲーム理論家にはなれないという挫折の始まりだった気がしている
  ◦ 部署のライブラリにあるはずなので気になる人は読んでみるとよいかもしれない  

paper 68 • IAB TechLab, "IAB OpenRTB" https://iabtechlab.com/standards/openrtb/#versions   •
Edelman, Benjamin, Michael Ostrovsky, and Michael Schwarz. "Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords." American economic review 97.1 (2007): 242-259.   • Varian, Hal R. "Online ad auctions." American Economic Review 99.2 (2009): 430-434.   • Varian, Hal R., and Christopher Harris. "The VCG auction in theory and practice." American Economic Review 104.5 (2014): 442-445.   • Chen, Ye, et al. "Real-time bidding algorithms for performance-based display ad allocation." Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 2011.   • Lee, Kuang-chih, et al. "Estimating conversion rate in display advertising from past erformance data." Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. 2012.   • Rothkopf, Michael H., Thomas J. Teisberg, and Edward P. Kahn. "Why are Vickrey auctions rare?." Journal of Political Economy 98.1 (1990): 94-109.   • Vickrey, William. "Counterspeculation, auctions, and competitive sealed tenders." The Journal of finance 16.1 (1961): 8-37.   • 坂井豊貴. "マーケットデザイン入門: オークションとマッチングの経済学." (2010).  

Intro:   Bid Land scape,  winrate予測  AI事業本部金子雄祐  
69

はじめに 70 • 以降の第4 ~ 第6回は、topic単位で完全に論文を内包できるものではないので、論文の紹介が前後したり重複することが多くなる  ◦ あまりスマートな構成ではないが、Introスライドの相互参照が多くなっていくため、注意してほしい 

目次 71 • 第4回 ~ 第6回の流れ  • bid landscapeとその活用法  ◦
入札価格最適化  ◦ Sample Selection Biasの補正  • bid landscapeのアプローチ  ◦ Cui et al.(2011 KDD)  ◦ Wu et al.(2015 KDD)  ◦ Zhang et al.(2016KDD) 

第4回 ~ 第6回の流れ  72

1~3回の振り返りと、種々の条件 73 • 1〜3回は入札の基礎となるbidの価値の算定について扱った   • しかし、この算定価格をこのまま入札に利用できない種々の制約や条件が存在する   ◦ そもそも広告オークション自体はone-shotの入札問題ではないから
  ◦ 例えば、以下のような問題として考えることができる   ▪ 預かり予算制約や営利制約などの下で、クライアントKPIを最適化する問題   ▪ クライアントのKPI制約と預かり予算制約などの下で、利益を最大化する問題   ◦ これらは一定の期間内(= 動学的)の最適化問題である   • これらの最適化のために、考慮すべき条件は例えば以下のものが存在する   ◦ 競合の入札やwin rate   ◦ 広告在庫  ◦ 預かり予算  ◦ KPI制約 

予測と制御; 4~6回の流れ 74 • これらの条件を雑に以下のように分類してみる   ◦ 予測問題  ▪ 競合の入札やwin
rate; 今回はこれを扱う   ▪ 広告在庫  ◦ 制御問題  ▪ 予算  ▪ KPI制約  • また、これらの予測問題と制御問題を統合した意思決定問題として強化学習(RL)が存在する   • この予測 → 制御 → RLという流れが以降の４〜６回の流れとなる  

bid landscapeとその活用法  75

bid landscapeとは? 76 • bid landscapeとは、要するに勝率や市場価格の予測のこと  • なぜこれが必要かというと、予算が限られている中で効率的に広告を出稿したいから
  ◦ 高すぎる入札は予算の無駄遣いとなる   ◦ 安すぎる入札は機会損失となる   ◦ 適切な入札額を設定することで、限られた予算で最大の効果を得られる   • したがって、ある価格で入札した場合の勝率や、勝利価格の予測を適切に行いたい   • しかし、CTR予測やCVR予測と違って以下のどのような点が違うのだろうか?   ◦ 予測問題としての特性   ◦ win rateの予測値の使われ方  

CTR予測やCVR予測と異なる難点 77 • まず、予測問題として、１〜２回で扱ったCTR予測やCVR予測と何が違うのか?   ◦ 競合他社の戦略変化による不確実性   ▪ 競合他社の入札戦略も動的に変化している
  ▪ これは、user行動に基づくCTRやCVR予測よりも急激な変化となる   ▪ したがって、モデルのフレッシュネスなども更に求められる   ◦ 市場と自分の相互性  ▪ 自分の入札行動が市場に影響を与えてしまう   • 価格を吊り上げると競合がさらに価格を吊り上げるなど   ▪ ClickやCVについては、広告価格を変化させてもこのような行動変容は起きない   ◦ Sample Selection Bias問題   ▪ かつては実際の落札価格は、自社が勝った場合のみ観測可能だった   ▪ したがって、これはcensored dataの問題となるが、現在はやや違うことに注意   • 第3回Intro参照 

win rateの予測値の使われ方 78 • 次に、win rateをどのように使うのかのパターンを紹介する。   • 大まかにわけると、以下の使われ方が代表的である  
◦ 入札価格最適化  ▪ Chen et al.(2011 KDD)   ▪ Zhang et al.(2014 KDD)   ◦ Sample Selection Biasの補正   ▪ Zhang et al.(2016 KDD)  

入札価格最適化(Chen et al.) 79 • Chen et al.自体は、第3回のIntroで紹介した  • 論文ではαの調整アプローチを以下の2種提案し、その比較も行なっている 
◦ Control-theoretic Bid Adjustment  ◦ Model-based Bid Adjustment  ▪ こちらがwin rateを活用しているので紹介する 

入札価格最適化(Chen et al.) 80 • この(14)式が更新式となる(この式だけだと意味不明だと思うので気になる場合は論文内を参照してほしい)  ◦ rj(t): 目標勝率  ◦
r`j(t): 観測された勝率  ◦ F^{-1}: 論文内(13)式で示されるbiding priceに対する勝率予測分布の逆CDF  ◦ γ: 更新速度の制御パラメータ  • 要するに、目標勝率と実績勝率のそれぞれから逆算された入札額の誤差から、入札額を調整するというアプローチ 

入札価格最適化(Zhang et al.) 81 • Zhang et al.(2014 KDD)はRTBにおける最適な入札戦略を数理的に導出し
た論文  • 以下の左のようなnotationが記載されている  • wがwin rateである 

入札価格最適化(Zhang et al.) 82 • 複雑になるので詳細は触れないが、上の(1)が解くべき最適化問題となる  ◦ ここに、win rateが繰り込まれている  •
win rateの導出自体は、論文では近似によるアプローチを取っている  ◦ そのため、bid landscapeの予測の例としては紹介しない 

Sample Selection Biasの補正(Zhang et al.) 83 • バイアス補正のモチベーションについては、第２回Intoで触れた  • オークションによるセレクションバイアスは上の(1)式に分解できる 
• つまり、win rate予測を行えばうまく補正ができる  ◦ 過去の入札履歴から推定した勝率で重み付けを行う  • 論文のタイトルの通り、確率的勾配降下法(SGD)にバイアス補正を拡張したもの 

Sample Selection Biasの補正(Zhang et al.) 84 • 式自体は難解で追わなくていいが、w(b_x)(= win rate)が分母に来ることで補正
をしている  • SGDとImportance Sampligの組み合わせは、要はオフ方策学習(のはず)  ◦ 詳しく勉強するなら斎藤『反実仮想機械学習』5章?(to 伊藤さん) 

bid landscapeのアプローチ  85

Bid Landscapeの代表論文 86 • Bid Landscapeについてはいくつかの研究があるが、今回は代表的な論文を3つ紹介する   ◦ Cui et
al.(2011 KDD)  ▪ 最も初期のbid landscape論文   ▪ ただしSSP向けの設定  ◦ Wu et al.(2015 KDD)  ▪ lossデータの考慮; 打ち切り回帰の導入   ▪ DSPにおける打ち切りデータを考慮したbid landscapeのおそらく初めての論文   ◦ Zhang et al.(2016 KDD)  ▪ ノンパラメトリックなアプローチ   ▪ ただしbid landscapeそのものよりかは入札アルゴリズムが焦点  

Cui et al.(2011 KDD) 87 • 各サンプルの入札額が上述の対数正規分布に従うと仮定   ◦ この「サンプル」は論文内で「ターゲティング属性値のユニークな組み合わせ」と定義されていることに注意
  ◦ 各キャンペーンは複数のターゲティング属性を持ち、それぞれに複数の値が設定される   ◦ 広告主の多様なターゲティング要件に対応する設定   • サンプルレベルの推定値を集約することで、キャンペーン粒度の平均と分散を推定したい  

Cui et al.(2011 KDD) 88 • キャンペーン粒度のbid priceの確率密度については、上の有限混合分布モデルでモデリングする   ◦
この重みのπについては、最尤法などで推定する  

Cui et al.(2011 KDD) 89 • サンプル粒度の分布のパラメータ(μ、σ)は、平均と標準偏差から上の(4)式で求められる   ◦ (意外と導出は行間を埋める必要がある)
  • この平均と標準偏差は、各 GBDTを用いて推定する 

Cui et al.(2011 KDD) 90 • 擬似コードは上述の通り 

Wu et al.(2015 KDD) 91 • Cui et alの問題点  ◦
そもそもSSPの問題設定である   ▪ DSPは入札に負けたときの打ち切りデータが存在する   ▪ また、特徴も一部しか得られない   • DSP向けの設定として、Wu et al.(2015 KDD)が存在(セカンドプライスオークション前提である)  

Wu et al.(2015 KDD) 92 • まず、真の勝利価格を次の線形回帰で予測する   ◦ これは、勝利したデータから推定される
 

Wu et al.(2015 KDD) 93 • この(5)式の損失関数(負の対数尤度)の最小化問題を解く   ◦ ただし、Wは勝利したbid 
• しかし、敗北したときの情報は使えないだろうか?  

Wu et al.(2015 KDD) 94 • ここで、(2)式は、上の(4)式のように変形すれば、勝利価格だけではなく勝利確率の予測になることに留意   ◦ ただし、Φは標準正規分布の累積分布関数
  ◦ これを、敗北時のケースにも適応してみる  

Wu et al.(2015 KDD) 95 • この(5)式の損失関数(負の対数尤度)の最小化問題を解く   ◦ ただし、Wは勝利したbid、Lは敗北したbid
  ▪ w_i: 勝利価格  ▪ b_i: 敗北したbid 

Wu et al.(2015 KDD) 96 • 結果上の(6)式で勝利価格の予測問題を解くことができる   ◦ ただし、P(ν_i
< b_i)はν_i の確率分布に影響を受けるなどの理由から(4)式はそのまま使えないので、ロジスティック回帰での予測を行う  

Zhang et al.(2016 KDD) 97 • 前述の2アプローチは、ゴリゴリに分布に仮定を入れていた   ◦ もうちょっと柔軟なノンパラ的なアプローチはないだろうか?
  • 生存時間分析のアプローチを応用する  

Zhang et al.(2016 KDD) 98 • 次のタプルを作成する  ◦ b_j: bid価格(ただし、b_j
< b_{j + 1})   ◦ d_j: 市場価格がちょうどb_j - 1のときの広告オークションの勝利ケースの数 ◦ n_j : 市場価格がちょうどb_j - 1のときの広告オークションの敗北ケースの数

Zhang et al.(2016 KDD) 99 • このとき、次の式でbid priceがb_xのときの勝利確率を予測する   ◦
これ自体はカプランマイヤー法と呼ばれる生存時間解析の手法の適用である   ◦ また、広告への応用はAmin et al.(UAI 2012)が初出  

アプローチのまとめと輪読論文 100 • これまで、種々のアプローチを紹介してきた   ◦ Cui et al. ,
Wu et al.はゴリゴリのパラメトリックなアプローチ   ▪ メリット  • 特徴量の利用が可能  ▪ デメリット  • 仮定が強すぎる  ◦ Zhang et al., Amin et al.は生存解析を応用したノンパラメトリックアプローチ   ▪ メリット  • 仮定が少ない  ▪ デメリット   • 特徴の考慮がなく、予測精度が低い   • これらのメリットをまとめた、より高度化させたモデルは可能だろうか？   ◦ 今回の輪読論文につながる  

paper 101 • Cui, Ying, et al. "Bid landscape forecasting
in online ad exchange marketplace." Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 2011.   • Wu, Wush Chi-Hsuan, Mi-Yen Yeh, and Ming-Syan Chen. "Predicting winning price in real time bidding with censored data." Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015.   • Zhang, Weinan, et al. "Bid-aware gradient descent for unbiased learning with censored data in display advertising." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.   • Ou, Weitong, et al. "A survey on bid optimization in real-time bidding display advertising." ACM Transactions on Knowledge Discovery from Data 18.3 (2023): 1-31.   • Amin, Kareem, et al. "Budget optimization for sponsored search: censored learning in MDPs." Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence. 2012.  • Zhang, Weinan, Shuai Yuan, and Jun Wang. "Optimal real-time bidding for display advertising." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014.   • Chen, Ye, et al. "Real-time bidding algorithms for performance-based display ad allocation." Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 2011.   • 齋藤優太. "反実仮想機械学習: 機械学習と因果推論の融合技術の理論と実践."  

Intro:   Pacing; 予算制約内の最適化問題  AI事業本部金子雄祐   102

はじめに 103 • ペーシングに関しては、初期論文については特にpracticalなものが多い  ◦ 特に、初期論文は実装ideaを含め、特に参考になる点が多いと思う  ◦ 全てをこのスライドで詳細に紹介するのはコスト上無理なので、特に今回については初期論文については元論文を参照することを推奨する 

目次 104 • pacingの問題意識  • pacingのアプローチ  ◦ Lee et al.(KDD
2015)  ◦ Agarwal et al.(KDD 2014)  ◦ Zhang et al. (WSDM 2016)  ◦ Cai et al.(WSDM 2017) 

pacingの問題意識  105

pacingはなぜ必要か? 106 • 広告配信において、配信事業者は月単位や日単位での配信予算が設定される   • 日単位でも、広告リクエストは時間によって波がある   ◦ 上記図は、Lee
et al.より(ただし、これはシミュレーションだが...)   ◦ 未明にリクエストが少なく、夕方や夜などに多くなるようなパターンが一般的  

pacingはなぜ必要か? 107 • このようなリクエストの増減の波がある中で、配信事業は以下のトレードオフに苛まれる   ◦ 予算を早く使い切ってしまうと、後半でより価値の高い広告枠を逃してしまう可能性がある   ◦ 予算消化が遅すぎると、予算を使い切れず広告効果を最大限に活用できなかったり売上が下がっ
てしまう  • そもそも前回のスライドで紹介した通り、広告配信は以下のような問題として考えることができる   ◦ 預かり予算制約や営利制約などの下で、クライアントKPIを最適化する問題   ◦ クライアントのKPI制約と預かり予算制約などの下で、利益を最大化する問題   • このような予算制約の中で、どのようにして予算を効率的に配分して最適化を行うのか?  ◦ これが、ペーシング機構が担っている問題である  

pacingのアプローチ  108

Pacingの代表論文 109 • Pacingについてはいくつかの研究があるが、広告分野での代表論文はそこまで多くない   ◦ 2014-2015: 初期の予算配分最適化の研究   ▪
Lee et al.(KDD 2015): Yahoo論文. 理論寄り   ▪ Agarwal et al.(KDD 2014): LinkedIn論文. 実務寄り   ◦ 2016: PID制御の応用  ▪ Zhang et al. (WSDM 2016)  ◦ 2017: 強化学習アプローチの登場   ▪ Cai et al.(WSDM 2017): 広告配信にRLの適用を行なった最初期の論文   • これらを概観していく 

Lee et al.(KDD 2015) 110 • Yahooのペーシング論文  ◦ LinkedInのペーシング論文と同じく、ペーシング周りの初期の代表論文  
▪ こちらのほうが理論寄りでテクニカル   • ペーシング問題の数理的な定式化や、リアルタイム性の重視などが特徴  

Lee et al.(KDD 2015) 111 • 予算消化の誤差を測る指標(Ω)を上の式で定式化している   ◦ B(t):
時間枠tでの目標予算額   ◦ C(t): 時間枠tでの実際の支出額   ◦ K: 全時間枠数（例：1日を144分割）   • このΩを用いて、KPI制約があるパターンとそうでないパターンの2つの定式化が可能である  

Lee et al.(KDD 2015) 112 • KPI制約がないパターンの式は上で定式化が可能   ◦ P:
キャンペーンのパフォーマンス(クリックが望ましい場合は、eCPCなど)   ◦ ri: 入札に参加する確率(確率的にペーシングしている)   • また、制約の意味は以下  ◦ C=B: 予算は消化しきる(売上のロスになるから)   ◦ Ω : 予算の消化パターンからの逸脱を一定のロス、ε以内に抑える  

Lee et al.(KDD 2015) 113 • KPI制約があるパターンの式は上で定式化が可能   ◦ G:
パフォーマンス目標  • つまり、こちらはパフォーマンス制約を厳守しつつ、一定の予算消化の未達を許容しながら、予算消化のパターンを維持する最適化問題になっている  

Lee et al.(KDD 2015) 114 • 3.3 Solution Summaryでアプローチの要約をしているが、以下の3 stepで行われる
  ◦ オフラインのログからレスポンス予測モデルを構築   ▪ pi = P(respond|Reqi, Ad)を推定   ◦ 類似レスポンス率のリクエストをグループ化による解空間の削減   ▪ 同グループ内で同じペーシング率を共有   ▪ 高レスポンス率のグループには高いペーシング率を設定   ◦ オンラインフィードバックに基づいて制御アルゴリズムを回す   ▪ グループペーシング率を動的に調整  

Lee et al.(KDD 2015) 115 • 予算消化のペースを上げる場合の図解が上のFig3となる  

Agarwal et al.(KDD 2014) 116 • LinkedInのペーシング論文   ◦ こちらのほうが、よりシンプルだが堅牢なアルゴリズムになっている
  ◦ こちらも、入札に参加する確率(Pass Through Rate, PTR) を動的に調整するアプローチ  

Agarwal et al.(KDD 2014) 117 • 予測トラフィックに基づく時間窓ごとの予算配分を上のように定式化する   ◦ f_{i,t}:
時間窓tまでの予測されるeligibleなインプレッション数   ◦ f_{i,T}: 1日の総予測インプレッション数   ◦ di: キャンペーンの1日予算   • つまり、予測されるトラフィック量の割合で各時間窓の予算を配分しているだけ  

Agarwal et al.(KDD 2014) 118 • これに基づいて、PTRの制御式は上の式になる   ◦ p_{i,t}:
時間窓tでのPass Through Rate (PTR)   ◦ si,t: 時間窓t開始時点までの実際の累積支出   • つまり、以下の制御をおこなっている   ◦ 予算消化が計画より遅れている場合はPTRを増加   ◦ 予算消化が計画より速い場合はPTRを低下  

Agarwal et al.(KDD 2014) 119 • Agarwal et al.では、いくつかのシンプルな実装上の工夫を行なっている  
◦ (2)式のr_t(つまり調整幅)は 10%に固定する  ◦ 初期PTRを10% に設定(Slow Start)  ◦ 22時間で予算を消化し切るような設定を行う(Fast Finish)   ◦ 各キャンペーンの消化率は 1分事に更新  ▪ 実装上の工夫として、7秒おきに全キャンペーンの12%事を更新していく  

初期アプローチ群の特徴と限界 120 • Yahoo論文もLinkedIn論文もアプローチについては実務的なメリットが多く認められる   ◦ 実応用上でも簡単で、practicalで参考になる部分が多い   ◦ しかし、制御についてはヒューリスティックではある
  • この制御について、なんらかの理論保証のある制御理論の応用は可能だろうか?   ◦ PID制御  ◦ WaterLevel制御  • これを行なったのがZhang et al. (WSDM 2016)   ◦ eCPC(有効クリック単価)とAWR(オークション勝率)を制御する  

Zhang et al. (WSDM 2016) 121 • まず、入札価格の基本式を上式とする   ◦
b(t): 時刻tにおける入札価格   ◦ b0: ベース入札価格（基準となる価格）   ◦ θt: そのbid requestに対する予測CTR   ◦ θ0: ターゲット条件(ユーザーセグメントなど)における平均CTR   • 要するに、以下の挙動をする   ◦ 予測CTRが平均より高ければ、より高い入札価格になる   ◦ 予測CTRが平均より低ければ、より低い入札価格になる   • これをどうやって調整していくのか?  

Zhang et al. (WSDM 2016) 122 • 上の(2)式が、入札価格の調整式となる   ◦
b_a(t): 時刻tにおける調整後の最終入札価格   ◦ φ(t): 制御信号（後述）  • 指数関数を用いて調整する   ◦ 負の入札価格を避けるため   ◦ linearモデルにしなかった理由として擧げられている  

Zhang et al. (WSDM 2016) 123 • PID制御の制御式は上の(3), (4)式となる。まずはnotationだけ簡単に導入する  
◦ e(tk): エラー値（時刻tkでの誤差）   ◦ xr: 目標値(論文内3.4節ではeCPCを例にしてこの制御の例を挙げている)   ◦ x(tk): 実測値  ◦ △tj: 時間間隔( = t_j - t_{j-1})   ◦ △e(tk): エラー値の変化量( = e(t_k) - e(t_{k-1}))   ◦ λP, λI, λD: それぞれP制御、I制御、D制御の重み係数  

Zhang et al. (WSDM 2016) 124 • 上式だとさっぱりだと思うが、簡単に(4)式を分解すると...   ◦
λP項（比例）:e(tk)、つまり現在の誤差に比例した修正。   ◦ λI項（積分）: 過去の誤差の累積を考慮.   ◦ λD（微分）: 誤差の変化率、つまり将来の誤差を考慮   • 連続時間の制御を離散に置き換えているので、このような式になる  

Zhang et al. (WSDM 2016) 125 • Waterlevel-based 制御の制御式は上の(5)式となる  
◦ xr: 目標値  ◦ γ: ステップサイズパラメータ   • PIDより更にシンプルな制御となっている  

制約付き動学的最適化問題としての定式化 126 • ここまでは、ヒューリスティックな制御やPID制御を紹介した   • しかし、何回か繰り返している通り、DSP自体は制約付き動学的最適化問題のはずである   ◦ 「限られた予算と時間の中で、逐次的に入札額を決定し、最終的なKPIを最大化する問題」
  • これに基づいた定式化や解法はあるだろうか?   ◦ MDP、及び、RL の導入  ▪ RLのより詳細な導入自体は次回のIntroスライドで行う  

Cai et al.(WSDM 2017) 127 • RTBを動的な最適化問題として扱うためにMDPを導入した最初のpaper  ◦ スポンサード広告などでMDPでのモデリングを行った先行研究はあった  •
従来は，入札決定を各広告表示の価値を独立して扱うか，広告の各セグメントごとに入札価格を設定する静的最適化問題にしていた  ◦ しかし，実際は配信には予算制約があるため，これを動的に割り当てることが必要  ◦ オークションの状態遷移を動的にモデル化するためにMDPを導入 

Cai et al.(WSDM 2017) 128 • 通常のMDP <S , A
, P , R>  ◦ S : 状態, A : 行動, P : 状態の確率遷移関数, R : 報酬  ◦ 状態空間はLarge Scaleの場合はNNで近似 

Cai et al.(WSDM 2017) 129 • ベルマン方程式などの知識がないとすんなり理解しづらいと思うが、簡単に定式化を紹介する  ◦ 知りたい場合、森村『強化学習』を推薦する(私はStokey-Lucasで勉強したが思い出として挙げておく)  •
まず、notationは上式となる  ◦ 前スライドの通り、bはBudget 

Cai et al.(WSDM 2017) 130 • 遷移確率関数や報酬関数は上の式で定式化される   • 難解に見えるが、以下のことを言っているだけ
  ◦ μの2式目はmarket priceが自分の入札より高かったら勝てないので、summationを取っている   ▪ ここのmはノンパラ推定で近似する( 第4回 win rate予測と関連 ) 

Cai et al.(WSDM 2017) 131 • 難解に見えるが、以下のことを言っているだけ   ◦ rewardは総クリックにしている
  ▪ したがって、入札に勝てなかったら0   ▪ 勝てたら期待CTRのΘがaddされる  

Cai et al.(WSDM 2017)   132 • Policy πは、各状態ｓ∈Ｓからアクションａ∈Ａsへの関数．つまりａ
= π(s) ◦ RTBにおける入札戦略に対応 • ポリシー πに従うValue Function VΠ(s)が存在。 ◦ これは状態sで開始し、ポリシーπに従うことによる期待総報酬 ◦ クリックされるタイミングは関係なく，合計クリック数が最適化の対象となる ▪ つまり割引率γ= 1のBellman方程式とみなせる • 最適なPolicyは以下で書ける

Cai et al.(WSDM 2017)  133 • Small Scaleの場合は前Slideの最適Policyは直接Dynamic Programmingで解ける. •
(t,b)を初期stateとした時のValue Functionは以下で近似可能 • そこから最適なactionを求めると，以下(10)式

Cai et al.(WSDM 2017)    134 • Small Caseの場合は，以下のプロセスを取っていた ◦
第1段階では価値関数V(t、b)の更新 ◦ 第2段階ではV(t、b)に基づいて現在の状態に最適な行動をとる • TやBが大きいLarge Scaleのケースでは価値関数の更新コストが高い ◦ これを上手く近似する ◦ 実際には，(9), (10)式の g(δ) = V (t−1, b−δ)−V (t−1, b)を気にしているので，こっちを近似する ◦ D(t, b) = V (t, b+ 1)−V (t, b)とすると，これは非線形なのでNNで近似する

Cai et al.の限界(金子の意見)  135 • 簡単そうに言っているが，m(δ, x)，つまり自分以外の最高入札額の推定は難しい ◦ ここらへんの分布の誤差が推定にどう影響するかは不明 •
そもそもTとBをどう決めるかがよく分からない ◦ 実務的にはBは所与で，Tが暗黙的に決まる ◦ Tは事前には見積もりづらい → finite horizonなのが微妙? • RTB環境はstateの分布が時系列でかなり変わる．要はめちゃくちゃ非定常 ◦ 他の入札者などの影響を強く受ける • この非定常性に対処する有効な方法はあるか? ◦ モデルフリー RLの導入 ◦ これが、今回のWu et al.につながる...

paper 136 • Xu, Jian, et al. "Smart pacing for
effective online ad campaign optimization." Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 2015.   • Agarwal, Deepak, et al. "Budget pacing for targeted online advertisements at linkedin." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014.   • Zhang, Weinan, et al. "Feedback control of real-time display advertising." Proceedings of the Ninth ACM International Conference on Web Search and Data Mining. 2016.   • Cai, Han, et al. "Real-time bidding by reinforcement learning in display advertising." Proceedings of the tenth ACM international conference on web search and data mining. 2017.   • Wu, Di, et al. "Budget constrained bidding by model-free reinforcement learning in display advertising." Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 2018.   • Stokey, Nancy; Lucas, Robert E.; Prescott, Edward (1989). Recursive Methods in Economic Dynamics. Harvard Univ. Press..  

Intro:   RLの広告応用  AI事業本部金子雄祐   137

はじめに 138 • 本スライドはRLの基本知識やコンセプトの説明を目指すものではない  ◦ 理由はAI Lab RLチームによる、社内での新卒研修資料などが存在するため  ◦ むしろ、記述の誤りや厳密でない記述などがあれば指摘いただけると助かります 
• また、今までは2018年以前の分野の発展の記述を主な目的としてきたが、本スライドはそのコンセプトから逸脱し、近年に至る発展のアウトラインを掴むことを目的とする 

目次 139 • RLの広告応用の発展  • 振り返り  ◦ Zhang et al.
(2014 KDD)  ◦ Cai et al. (2017 WSDM)  • RL応用の発展の歴史  ◦ Wu et al. (2018 CIKM)  ◦ He et al. (2021 KDD)  ◦ Wang et al.(2022 KDD)  • 今回の論文について 

RLの広告応用の発展  140

広告配信のRL応用の歴史の概観 141 • 入札問題が制約付き動学的最適化問題の枠組みで定式化可能なのはIntroスライドで述べてきた通り   ◦ RLの応用自体は発想としては自然と言える   • RTBにおける広告応用の発展の歴史は、以下のようにまとめられる
  ◦ 理論的基礎：Zhang et al. (2014 KDD)   ◦ RLの導入期：Cai et al. (2017 WSDM)   ◦ 発展期：  ▪ モデルフリーRL：Wu et al. (2018 CIKM 第5回輪読論文)  ▪ マルチエージェント：Jin et al. (2018 CIKM 今回輪読論文)  ▪ 複数制約：He et al. (2021 KDD)   ▪ Bayesian RL : Wang et al.(2022 KDD)   • これらの歴史について、過去のIntroスライドや輪読論文との重複はありつつ、簡単に触れることを目指す  

広告配信のRL応用の歴史の概観 142 • 左はOu et al. (TKDD 2023)から   ◦
最直近のRTB関連のサーベイ論文   • Cai et al.以降のRL応用の概観が見られる   • ここから、3本をpick upして紹介   ◦ Wu et al. (2018 CIKM)  ◦ He et al. (2021 KDD)  ◦ Wang et al.(2022 KDD)  • まずは過去スライドと重複する振り返りを行う   ◦ Zhang et al. (2014 KDD)  ◦ Cai et al. (2017 WSDM) 

振り返り  143

Zhang et al. (2014 KDD) 144 • Zhang et al.(2014
KDD)はRTBにおける最適な入札戦略を数理的に導出した論文  • notationは左 

Zhang et al. (2014 KDD) 145 • 上の(1)が解くべき最適化問題となる  • しかし、これは予算付き静学的最適化問題として定式化されている 
◦ オークション環境の動的な性質は考慮できていない  ◦ これをモデリングするには、動学的な最適化問題にしないといけない 

Cai et al.(WSDM 2017) 146 • RTBを動的な最適化問題として扱うためにMDPを導入した最初のpaper  ◦ スポンサード広告などでMDPでのモデリングを行った先行研究はあった  •
従来は，入札決定を各広告表示の価値を独立して扱うか，広告の各セグメントごとに入札価格を設定する静的最適化問題にしていた  ◦ オークションの状態遷移を動的にモデル化するためにMDPを導入 

Cai et al.(WSDM 2017)   147 • Policy πは、各状態ｓ∈Ｓからアクションａ∈Ａsへの関数．つまりａ
= π(s) ◦ RTBにおける入札戦略に対応 • ポリシー πに従うValue Function VΠ(s)が存在。 ◦ これは状態sで開始し、ポリシーπに従うことによる期待総報酬 ◦ クリックされるタイミングは関係なく，合計クリック数が最適化の対象となる ▪ つまり割引率γ= 1のBellman方程式とみなせる • 最適なPolicyは以下で書ける

RL応用の発展の歴史  148

Wu et al. (2018 CIKM)  • 第5回輪読論文なので簡単に触れる ◦ 予算制約を満たしつつ入札をするモデルフリーなRLを導入した最初の論文 ◦
モデルフリーのRLを導入した理由はRTB環境の高い非定常性によるもの ◦ 報酬関数設計やDQNの拡張もキモ ◦ 制約なし版はWang et al.(2017) • 入札のやり方は非常にシンプル 149

Wu et al. (2018 CIKM)  • 上の(1)式がProblem Definitionである ◦ x
: 広告表示がされた否かのindicator. ◦ v i : 広告表示の価値 ◦ c i : 広告表示の cost ◦ B: 予算 150

Wu et al. (2018 CIKM)  • 入札額を上の式で調整する • ラムダで調整する ◦
入札額にファクターをかける感じ • ここのラムダを上手くモデルフリー RLで学習するという設定 151

Wu et al. (2018 CIKM)  • コスト制約があるので，Constrained MDPでこれを学習する • ただしnotationは以下
◦ π: Policy ◦ Ck : K種類のコスト. • これで、複数コスト制約を満たすような制約条件として表現する 152

Wu et al. (2018 CIKM)  • Stateを以下で表現する ◦ t：現在のタイムステップ ,
◦ Bt：タイムステップtでの残り予算, ◦ ROL t ：ステップtに残されたλ調整機会数 ◦ BCR t = (B t - B t-1 )/B t-1 ：予算消費率, ◦ CPM t: t -1 から t までの広告表示単価 , ◦ WR ｔ：オークション勝利率 , ◦ r t-1 タイムステップ t -1 における総クリック数などのリワード合計値 153

Wu et al. (2018 CIKM)    • ラムダを小さくすると入札額が高くなって，rewardが瞬間的に大量に得られる ◦ しかし，予算をすぐに使い果たすし，探索をしなくなる
◦ 要はすぐに局所解に陥る. • したがって、妥当な報酬関数設計をしないといけない • 以下の設定にする ◦ E(s,a): 過去にstate sで action aを取ったエピソードの集合 ◦ r t (e) : エピソードeのstep tにおける即時報酬 • 過去の状態sでaction aを取った全てのepisodeについて即時報酬の和の最大値を返す ◦ エピソード全体の評価をできるようにする(ただちょっと変らしい?) 154

He et al. (2021 KDD)  • 複数制約を考慮したRL   ◦ arxivに公開されていない 
◦ Videoは公開されている(link)ので、ここから引用する  155

He et al. (2021 KDD)  • 上の線形計画問題で定式化を行う   ◦ KPI
constraintsが複数の制約条件を表現している   ▪ Table 1のようにすれば表現が可能   156

He et al. (2021 KDD)  • 前スライドの最適化問題は、次のTheorem2.1.によって(2)式で解くことができる   ◦ Mは制約式の個数 
• それでは、このパラメーターである ω*をどのように得ればよいのだろうか?   ◦ impが全量あらかじめ得られていれば最適化問題を解くだけ   ◦ しかし、impは逐次的に来るし、オークション環境は非定常である   • RLの導入を行う  157

He et al. (2021 KDD)  • MDPを用いて定式化を行う   • 次のスライドにStateやActionの内容は引用している
  ◦ Stateは残り予算や現時点のKPIなど   ◦ ActionはM + 1次元のparametorでbid parametorの更新を行う   ◦ rewardは各ステップの勝利imp数   ◦ 遷移確率はモデルフリーRLで表現   ◦ 割引因子はγ = 1(各キャンペーンの有効性はdailyで判断されるから)   158

He et al. (2021 KDD)  159

He et al. (2021 KDD)  • 任意のキャンペーンの任意の時点tで、agentの最適行動は何か?   ◦ これは上のThm
3.1.で示される  • 訳すと以下  ◦ 「各時刻tでの部分問題において、入札エージェントの最適なアクション列は、現在のw_tを最適なw_t*に修正し、その後の時間ステップではそれを固定し続けることである」  • 一体これはどういう意味なのか?   160

He et al. (2021 KDD)  • 要するに、「一度最適なパラメータに調整してそれを固定する」という単純な戦略が最適であることが証明された  ◦ パラメータの更新頻度を減らせる上に、パラメータが頻繁に変動しない 
◦ これはシステムの安定性の面で、実務上でも大きなメリットが有る  161

Wang et al. (2022 KDD)  • 従来手法は、市場のデータが定常だという仮定がされてきた  ◦ 要するに他のbidderが戦略を変えないという仮定 
◦ しかし，bidderはお互いに戦略的に行動してbidを変更するのでこの仮定は実務的には成立しない  • この市場の非定常性をモデリングする  ◦ Bayesian RL の導入  162

Wang et al. (2022 KDD)  • まず、(1)式で定式化をしている  ◦ b: 入札戦略を表す変数 
◦ D(ϵT): T期間での総配信量(delivery)を表す目的関数  ◦ ROI(ϵT):ROI(配信量と費用の比率)  ◦ B: 予算  ◦ C(ϵT): 配信コスト  ◦ B - C(ϵT): 予算制約  ◦ ϵT: episode (入札額, 市場価格などが含まれる。次スライド参照)  • D, C, ROIは次のスライドで定義する  163

Wang et al. (2022 KDD)  • 指示関数によって、勝利した入札のみを対象としている  ◦ bi: 入札額 
◦ mi: 市場価格  ◦ ci: 費用  ◦ di: 実際の配信量  164

Wang et al. (2022 KDD)  • 定式化は、Partially Observable Constrained MDP(POCMDP)
によって行う  ◦ stateが部分的に観測可能という設定になっている。これについては後述  • 報酬関数とコスト関数は上で定式化される  ◦ R(si, ai): 総配信量と下限値の差分(ただし、指示関数によりT時点で評価)  ◦ C(si, ai)  ▪ FLは ROI制約を満たさない状態の集合。第一項はROI制約違反のペナルティを表す  ▪ FBは予算I制約を満たさない状態の集合。第二項は予算制約違反のペナルティを表す  165

Wang et al. (2022 KDD)  • 部分観測は上の定式化で導入している  ◦ 状態空間Sから観測空間Oへのマッピング  ◦
ここでは、3つの情報が抜け落ちている  ▪ di: 実際の配信量  ▪ ci: コスト  ▪ mi: 市場価格  • 第二価格オークションにおいて、市場価格miは落札時にのみコストciとして観測可能  ◦ したがって、これが「条件付き」で市場条件がわかることをモデリングしている  166

Wang et al. (2022 KDD)  • 遷移確率密度 T(si+1|si, ai) で2つを表現 
◦ マルコフ的な推移  ◦ 市場の確率的な動き: これが時間によって変化する  • T, μの正確な形式は未知なので、ログデータを用いた経験分布で近似する  167

Wang et al. (2022 KDD)  • (3), (4)式をまとめて、上がPOCMDPの定式化となる  • 期待値になっていることに注意 
◦ 市場の不確実性、非定常性を織り込んでいる  168

Wang et al. (2022 KDD)  • なんと、(1)式は第二価格オークションの場合は上の式で解ける  ◦ ui: impの推定効用 
• これは以下の意味を持つ  ◦ 最適な入札は効用に比例する、βが制御可能な単一のパラメータ  ◦ 問題の次元を大幅に削減可能  169

Wang et al. (2022 KDD)  • (1)を解くための補助的な問題として(9)を用いる  ◦ 理由: 元の問題では報酬が最終時点Tでしか得られないから 
▪ 即時の学習シグナルが必要  ◦ これにより、段階的な学習を実現する  ▪ 学習の効率性向上を試みる  • やっていることは、各時点tで追加のROI制約、予算制約を導入  170

Wang et al. (2022 KDD)  • Evidence Lower Bound (ELBO)
という変分ベイズの手法を用いて目的関数を(13)式のようにする  ◦ 全く金子は詳しくない...  • このような表現をする理由は以下  ◦ 部分観測性への対処: ELBOは潜在変数による確率的なモデリングを可能にする  ◦ 市場状態に対する確信度を確率分布として表現したいが、q(z|τ)で事後分布を近似  ▪ KLダイバージェンス項(D_KL)で補正をするらしい  171

超余談: POMDPとゲーム理論; RLと経済学の結節点  • ゲーム理論の分野では、無限回繰り返しゲームという問題が存在する  ◦ これは例えば囚人のジレンマなどのゲームを無限回繰り返し行う設定である  • その分野では「フォーク定理」と呼ばれる有名な定理がある 
◦ generalなversionを言明しても意味不明だと思うので、簡単に囚人のジレンマを例に出す  ◦ 囚人のジレンマでは、お互い裏切る(自白する)が均衡になることはよく知られる  ◦ しかし、無限回繰り返しの設定だと、お互いが黙秘するつまり協調行動が取られることが示せる  ▪ 「相手が裏切った場合に永久に自白する」という戦略をおたがいが取る均衡がある  ◦ 協調行動の分析などで、経済学では用いられる事が多い  ▪ 無限回は、本当に無限回やるわけではなくいつゲームが終わるかがわからない状態に等しい  • なぜフォーク定理と呼ばれていたかというと、長年証明はないが暗黙的に結果だけ知られていた(=folk)から  • これらの証明は、以下の論文でなされている(繰り返しゲームについて気になったら神取(2015, 2016)が詳しい)  ◦ 完全観測のケース: Fudenberg and Maskin(1986 Econometrica)  ◦ Public Monitoringのケース(共通して観測可能なシグナルが存在): Fudenberg et al.(1994)  ◦ Private Monitoringのケース(相手の行動を一定確率で見間違えるようなケース): Sugaya(2022)  172

超余談: POMDPとゲーム理論; RLと経済学の結節点  • さて、このPrivate Monitoringのケースだが、そもそも均衡の計算自体が難しいことで知られている  ◦ この均衡計算に、実はさきほど紹介したPOMDPが使用可能である  ▪
ちなみに、制約付きのものはCPOMDPの名称が一般的だと思うのだが、なぜPOCMDPなのかは不明  • 岩崎 et al.(2012)では、POMDPを用いたソルバーが提案されている  • しかし、POMDP自体は計算量が決定不能なので、RLの使用が試みられている  • AI Labの坂本、阿部両名が電通大の岩崎先生と2021にpaperを書いていたりする  ◦ POMDPについて気になったら聞いてみるのがよい  ◦ 金子もかつてゲーム理論系のゼミでPOMDPの勉強を少しやったが当時は本当に意味不明だった  173

今回の論文について  174

MARLの応用へ...  • Wang et al.は、市場の非定常性をモデリングして解くようなアプローチだった • しかし、競合をエージェントとしてこれを明示的にモデリングするような方法はないだろうか? ◦ Jin et
al.ではゲーム理論的なアプローチを導入 ◦ multi-agent RL(MARL)を用いてRTBを解く 175

paper 176 • Ou, Weitong, et al. "A survey on
bid optimization in real-time bidding display advertising." ACM Transactions on Knowledge Discovery from Data 18.3 (2023): 1-31.   • Zhang, Weinan, Shuai Yuan, and Jun Wang. "Optimal real-time bidding for display advertising." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014.   • Cai, Han, et al. "Real-time bidding by reinforcement learning in display advertising." Proceedings of the tenth ACM international conference on web search and data mining. 2017.   • Wu, Di, et al. "Budget constrained bidding by model-free reinforcement learning in display advertising." Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 2018.   • Jin, Junqi, et al. "Real-time bidding with multi-agent reinforcement learning in display advertising." Proceedings of the 27th ACM international conference on information and knowledge management. 2018.   • He, Yue, et al. "A unified solution to constrained bidding in online display advertising." Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021.  • Wang, Haozhe, et al. "ROI-constrained bidding via curriculum-guided Bayesian reinforcement learning." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.   • Wang, Yu, et al. "Ladder: A human-level bidding agent for large-scale real-time online auctions." arXiv preprint arXiv:1708.05565 (2017).   • Fudenberg, Drew, and Eric Maskin. "THE FOLK THEOREM IN REPEATED GAMES WITH DISCOUNTING OR WITH INCOMPLETE INFORMATION." Econometrica (1986-1998) 54.3 (1986): 533.   • Sugaya, Takuo. "Folk theorem in repeated games with private monitoring." The Review of Economic Studies 89.4 (2022): 2201-2256.   • Fudenberg, Drew, David Levine, and Eric Maskin. "THE FOLK THEOREM WITH IMPERFECT PUBLIC INFORMATION1." Econometrica 62.5 (1994): 997-1039.   • 坂本充生, 阿部拳之, and 岩崎敦. "見間違えのある繰り返し囚人のジレンマにおける方策勾配法に関する研究." IEICE Conferences Archives. The Institute of Electronics, Information and Communication Engineers, 2021.   • 岩崎敦, et al. "部分観測可能マルコフ決定過程を用いた私的観測付き繰返しゲームにおける均衡分析プログラム." 情報処理学会論文誌 53.11 (2012): 2445-2456.  

paper 177 • 神取道宏. "見間違えのあるくり返し囚人のジレンマ―私的不完全観測下の実験とトーナメント―." 三菱経済研究所経済研究書 2016.114 (2016): 1-91.
  • 神取道宏. "人はなぜ協調するのか―くり返しゲーム理論入門―." 三菱経済研究所経済研究書 2015.113 (2015): 1-81.  

Intro:   Creative  AI事業本部金子雄祐   178

はじめに 179 • 本スライドはBanditの基本知識やコンセプトの説明を目指すものではない  ◦ 理由はAI Lab RLチームによる、社内での新卒研修資料などが存在するため 

目次 180 • 第7~9回の流れ  • Banditの形式  • BanditのWeb系応用の初期の歴史  • 社内事例と非定常性 

第7~9回の流れ  181

DSPにおける実験 182 • Webや広告配信の領域は、古くからABテストの活用先として知られている   • メリット  ◦ 大規模トラフィックでsample sizeが大きい
  ◦ 実験のコストが低い  ▪ 被験者を集めるコストが低く、また、施策も機構をdeployすればいい   ◦ リスクが少ない  ▪ 薬や政策と違って、被験者の身体や人生に負の影響を及ぼすリスクが極度に少ない   • DSPにおいては、例えば1〜6回で紹介してきたような、以下の要素が実験の対象となる   ◦ 予測モデル  ◦ pricingロジック  ◦ クリエイティブ; 今回扱う 

ABテストとBandit 183 • このような実験を行う方法として、以下のような方法が考えられる   ◦ ABテスト  ◦ Bandit(適応的実験)  
• Banditの最適腕識別(後述)がABテストの一般化と呼ばれることもある   • ただ、以下のようなプロセスの違いがある(と思う)   ◦ ABテスト  ▪ 最初にsample sizeを決める   ▪ 実験後に適切に仮説検定を行う   ▪ 基本的には実験中に動的に割合を変更しない   ◦ 最適腕識別  ▪ 適応的にリソースを配分する   ▪ 基本的には仮説検定を行わない   • 目的や検証する物によって使い分けるのがいい   ◦ 例: 予測モデルや入札ロジックは複数のビジネスKPIへの影響を見たいのでABテスト   ◦ 例: クリエイティブ選択は、最もいいCRをなるべく機会損失をせずにみつけたいのでBandit  

第7~9回のtopic 184 • 第7〜９回では、これらの実験に伴うTopicをDSPや広告配信の文脈に関連させて扱う   ◦ 第7回: Banditの実応用としてのCR選択   ◦
第8~9回: 広告におけるABテスト、効果検証   • Banditの理論そのものや、ABテストの理論的な内容そのものには深く立ち入らない   ◦ 社内資料や社外の教科書が豊富に存在   ◦ Bandit  ▪ 本多・中村『バンディット問題の理論とアルゴリズム』   ◦ ABテスト  ▪ 次回Introで紹介 

Banditの形式  185

考えるお題 186 （例えばEC系の広告で )どちらの広告クリエイティブを見せるべきか → よりクリックされやすそうな広告を見せるべき(KPIがCTRなら) Creative A(人物あり) Creative B(文字メイン)

バンディットアルゴリズム 187 • 複数の候補から最もいいものを逐次的に探す • 「探索」と「活用」のトレードオフ • スロットマシーンの腕（アーム )の例がよく用いられる ◦
今回のように、広告などのアプリケーションが存在

Banditの二形式 188 • 目的関数によって、以下の 2つに形式に分けられる ◦ 累積報酬最大化 ▪ 期待値最大の腕もしくは期待値最大の腕に限りなく近い期待値の腕をできる限り多く引いて累積報酬を最大化することが目的
◦ 最適腕識別 ▪ 期待値最大の腕を高確率で識別することが目的

Banditの手法 189 • 次に、以下の2つの手法を簡単に紹介 ◦ Thompson Sampling ▪ 最もシンプルで有用な手法 ▪
実装が容易で理論的保証もある ◦ Contextual Bandit ▪ 特徴量の考慮 ▪ つまり、ユーザーの属性などに応じて最適な選択が可能

Thompson Sampling 190 • それぞれのアームを「そのアームの期待値がすべてのアームのうちで最大になる確率」で選択 ◦ 簡単に言うと、「良さそうなアームをそれが良さそうである確率で引く」手法 • プロセスは以下の方法で行う ◦
各アームが当たる確率を確率分布で推定する ◦ 各試行では、アーム毎に確率分布から値をサンプルし、その値が最大となるアームを引く ◦ アームを引いた結果を使ってそのアームが当たる確率の確率分布を更新する • 確率分布に何を用いるかだが、広告だとベータ分布のケースが多い ◦ 成功数α, 失敗数βのパラメータで表現

Contextual Bandit 191 • ユーザーや腕の特徴量によって各腕の報酬分布が変化すると仮定 ◦ 例: r t =
<A t , θ> + ε ｔ ▪ r t : 報酬, A t :context，θ:未知のパラメータ，ε ｔ :ノイズ ◦ 取られたActionもcontextに相当 ◦ どのactionを取るかによってcontextが変化する ◦ よって，期待報酬もどのactionを取るかで変化する • メリット ◦ 状況ごとに適切な腕を選択 ▪ 例:配信面ごとに各クリエイティブのCTRが大きく異なる ◦ 新しい腕が入ってきたときにある程度事前に報酬を推定可能 ▪ 例:新しい画像のサイズは320*50 → 別の320*50の画像の配信結果から推定

CR選択におけるBanditの使い方の例 192 • 例えば、以下のような分け方ができる ◦ クリエイティブ配信の最適化 ▪ よりクリックが稼げるクリエイティブに対して配信を寄せたい ▪
できれば属性(特徴量)も考慮したい ▪ 累積報酬最大化のための contextual bandit ◦ クリエイティブ評価 ▪ どのクリエイティブが良いかを適切に評価したい ▪ 限られたサンプルサイズの中で効率的にいいクリエイティブを選ぶ ▪ 最適腕識別としての Bandit • CR実験の自動化という目的で最適腕識別を使うこともある ◦ Katsuragawa et al. (2025 WSDM)

BanditのWeb系応用の  初期の歴史  193

TSが主流になった理由  • ここ10年のBanditの実応用では、基本的に Thompson Samplingがベースラインだと思われる ◦ 先スライドでも述べた通り、実装が容易で理論的保証もある • ただ、これは明確なきっかけがあり、 Chapelle
and Li(2011 NeurIPS)が端緒 ◦ このChapelle and Liの内容に簡単に触れる 194

Chapelle and Li(2011 NeurIPS)  • 当時は、TSは理論解析が不十分であまり注目されていなかった (らしい) ◦ 広告とニュースレコメンドの 2つの実例で、Banditの各手法を比較
◦ その結果、TSが優れた性能を発揮した 195

Chapelle and Li(2011 NeurIPS)  • 広告の例 • TS, LinUCB, ε-greedy等を比較
• TSが最小regretを達成 196

Chapelle and Li(2011 NeurIPS)  • ニュースレコメンドの例 ; 正規化したCTRを比較 ◦ TSが良いパフォーマンスを発揮している
◦ また、更新遅延に対して頑健であることもわかる 197

Bietti et al.(2021 JMLR)  • contextual banditでChapelle and Liのような検証をした論文 ◦
ただし、データセットの数などが膨大にある ◦ かなり長いので、簡単に結果のみ触れる 198

Bietti et al.(2021 JMLR)  • 大量のデータセットで手法の勝ち負けを比較 • 右はパラメータ最適化が上手く行っているような設定
• 左のほうがより実務的 ◦ RegCB-optimistic (RO) が性能がいい ◦ Greedy(G)が意外と強い 199

Bietti et al.(2021 JMLR)  • Yahooデータセットなどでの比較 ◦ ROとGがかなりいい • 特に、実装が非常にシンプルな
Greedyが強いのが論文ではメリットとして挙げられている 200

初期のWeb系への応用  • Banditの広告の応用についての論文は (意外と)有名論文は見つからない • 2010年前後に書かれたWeb系の産業応用の論文をいくつか pick upする ◦ Li
et al. (2010 KDD) ▪ 広告 ◦ Li et al. (2010 WWW) ▪ ニュースレコメンド ◦ Tang et al.(2013 CIKM) ▪ 広告 • 基本的にChapelle and Li 以前なので、簡単に触れる 201

Li et al. (2010 KDD)  • Yahoo Labのpaper • contextual
banditの広告への応用 ◦ dynamic ε-greedy法; εを動的に変える ◦ Confidence-based Exploration: 広告の表示回数に基づく信頼度指標の導入 202

Li et al. (2010 KDD)  • confidenceの手法が、短いiterraion で平均eCTRで上位に来ていることがわかる 203

Li et al. (2010 WWW)  • Yahooのpaper. ニュース記事のレコメンドを contextual banditで行う
• LinUCBという手法の提案 ◦ ユーザーと記事の特徴を利用して推薦 204

Li et al. (2010 WWW)  • ε-greedyと比較した結果が上の表 • LinUCBが以下のメリットを持つことがわかる ◦
性能(deploy & learnの両方で) ◦ データが少なくても十分機能する 205

Tang et al.(2013 CIKM)  • 広告フォーマット(= レイアウト)をcontextual banditで最適化 • オフライン評価手法を開発
し、実際のトラフィックを使わずに様々なアルゴリズムを評価 ◦ 過去のデータを用いてリプレイを行う • 種々の手法を比較 206

Tang et al.(2013 CIKM)  • 2種の方法で比較 ◦ 過去データあり ◦ 過去データなし
• TSが最も良い結果だった 207

社内事例その1: Off-Policy Evaluation  • AI Labの最も初期のトップカンファpaper(link) • BanditとOff-Policy Evaluationの組み合わせ ◦
オフラインのバンディットデータを使って最も統計的にEfficientな方法で新しいPolicyの評価と最適化を行う 208

社内事例その2: TH Lasso  • RLチームのpaper(link) • TH Lassoという手法の開発 ◦ 高次元の特徴ベクトルを持つcontextual
linearバンディット問題を扱う ◦ これに、Lassoとしきい値処理を組み合わせた新しいアルゴリズム ◦ 広告みたいな例だと特徴量が高次元ベクトルになる 209

社内事例と非定常性  210

社内事例; 技術ブログより  • Dynalystでのバンディットの話が、全社の技術ブログにあがっている (link) ◦ 当時、DynaではTSが一部の広告配信で運用されていた • 執筆者は当時内定者バイトの黒岩さん (投稿だけ藤田さんがやっている
) ◦ 今何をしているのかと思って久しぶりに調べたら、 2024年にNIIの助教になっていた。それはそう 211

TSの拡張; Clustered Thompson Sampling  • 試したことは、TSに特徴量を反映させるようなもの ◦ 具体的には、クリックしやすい広告が異なる傾向を持つようにユーザをクラスタリングし、クラスタ毎に TSを行う ◦
Clustered Thompson Sampling（CTS）と名付けられている • このクラスタを作る前に、ちゃんと以下のプロセスは行なった ◦ CTSの有効性を確認するために、ユーザの属性によってクリックされやすい広告の傾向が変わるのかを調査 ▪ ちゃんとこのクラスタは見つかった • シミュレーションも行った ◦ TSと大きな差はつかなさそうではあった • とりあえずこれを実装して、 ABテストを行なった ◦ 結果はどうなったのか ? 212

ABテストの結果  • TSのほうがCTSより有意によかった設定が複数あった一方で、逆は存在しなかった • 全体で見ても、CTRはTSのほうが良かった • なにがよくなかったのか ? 213

CTSの振り返り  • 記事内では、以下の振り返りがされている ◦ 全体的に、TSの方が表示する広告の偏りが大きく、一つの広告ばかり出す傾向にある • CTSではクラスタ毎にデータが分割されるため、TSと比べると利用できるデータの量が少ない ◦ そのために探索が十分に行えなかった •
つまり、学習データが少なくて収束しなかったのでは ? という解釈で帰結していた ◦ かといって、集計期間を伸ばしすぎるとあまりに昔のデータを反映してしまう • ここで、もうちょっと広い視点でこの振り返りを行なってみる ◦ それは、「そもそもTS自体が有効なのだろうか?」というツッコミ 214

そもそも広告市場でTSは有効なのか?  • 実は、TSはとある弱点を持っている ◦ それは、環境の報酬分布が時間の経過とともに一定である、つまり定常であるということ • (一般論として)クリエイティブの効果というのは時間によってコロコロ変わる ◦ 上図は今回の輪読論文、Fiez
et al. からの引用 ◦ 実務的にもは「常に特定のCRの効果が一番いい」という状況すら達成されないことが多い • そんな状態で、TSがワークするのだろうか? 215

そもそも広告市場でTSは有効なのか?  • なぜここまでCRのrankの順序が変わるのか? ◦ varianceが大き過ぎる? ◦ sample sizeが少なすぎる…? ◦ そもそもCRの効果が少なすぎて本質的にほぼ差異がない?
◦ userの変化やCRの嗜好の変化 • また、実務的には以下のようなさらなる制約も存在する ◦ 運用上の課題・ビジネス上の課題 ▪ CRの差し替え ▪ 期間限定CRなどの存在 • ゲームのイベントなど ◦ システム的な制約 ▪ バッチ更新のタイミング • 不均一なトラフィック量の影響を受けやすくなる 216

そもそも広告市場でTSは有効なのか?  • このような非定常な環境において、Banditのような適応的実験はそもそもうまくいくのだろうか? ◦ 実はそれすらよくわかっていない • この疑問が、今回の輪読論文につながっていく... 217

paper 218 • Tang, Liang, et al. "Automatic ad format
selection via contextual bandits." Proceedings of the 22nd ACM international conference on Information & Knowledge Management. 2013.   • Li, Wei, et al. "Exploitation and exploration in a performance based contextual advertising system." Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 2010.   • Chapelle, Olivier, and Lihong Li. "An empirical evaluation of thompson sampling." Advances in neural information processing systems 24 (2011).   • Narita, Yusuke, Shota Yasui, and Kohei Yata. "Efficient counterfactual learning from bandit feedback." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.  • Ariu, Kaito, Kenshi Abe, and Alexandre Proutière. "Thresholded lasso bandit." International Conference on Machine Learning. PMLR, 2022.   • Fiez, Tanner, et al. "Best of three worlds: Adaptive experimentation for digital marketing in practice." Proceedings of the ACM on Web Conference 2024. 2024.   • Li, Lihong, et al. "A contextual-bandit approach to personalized news article recommendation." Proceedings of the 19th international conference on World wide web. 2010.   • Bietti, Alberto, Alekh Agarwal, and John Langford. "A contextual bandit bake-off." Journal of Machine Learning Research 22.133 (2021): 1-49.  

Intro:   ABテスト  AI事業本部金子雄祐   219

はじめに 220 • 本スライドはABテストの基本知識やコンセプトの説明を目指すものではない  ◦ 理由は社内でのあまりにも豊富な新卒研修資料などが存在するため  • また、言い訳がましいが、今回のpaper紹介はかなりラフなものとなる  ◦ 理由;
今回は経済学やマーケティング・サイエンス系の論文が多いから  ▪ AI系のpaperと比べて長いので端折らないとスライド枚数がとんでもないことになる 

目次 221 • ABテストについて  • 広告効果測定の困難さとABテスト  • 広告におけるABテスト以外の推定手法  • 広告の効果測定という”地獄” 

ABテストについて  222

「kohavi本を読め」 223 • ABテストについての包括的な解説は、あまりにtopicが広い   ◦ 正直、「kohavi本を読め」で話が終わってしまう   ▪ 邦訳もあります 
◦ 手前味噌だが、安井伊藤金子のPython本もいいと思う   • 論文そのものにあたるなら、以下のものがある   ◦ Kohavi et al. (2009 KDD)  ◦ Kohavi et al. (2022 KDD); 第8回輪読論文   • それでは、何を今回は紹介するのか?  

Lewis & Johnson 224 • 広告というtopicの効果検証周りの話題は、経済学やマーケティングサイエンスの分野に実は多い  • 今回は、LewisとJohnsonの2人に中心に、2015年以降のリサーチの話題を扱う  • Lewis;
ずっとIndustryで効果検証系の仕事をしている  ◦ Yahoo -> Google -> Netflix -> Nanigans -> Amazon(Senior Principal Economist らしい)  • Johnson  ◦ 現在ボストン大学のAssistant Professor  ◦ 最近はGDPRやターゲティング規制、Privacy Sandboxなどの研究をしているので気になる人は要確認  ▪ Goldberg et al.(2024 AEJ: PE), Johnson et al. (2023 MS) 

Lewis & Johnson 225 • 以下のpaperを通じて広告の効果検証の困難さと検証手法などを概観していく   ◦ Lewis and
Rao (2015 QJE)   ◦ Johnson et al. (2017 MS)  ◦ Johnson et al. (2017 JMR)   ◦ Johnson et al. (2017) 

広告効果測定の困難さと  ABテスト  226

Lewis and Rao (2015 QJE) 227 • 広告のROIの測定に関する論文   ◦
QJEという経済学系のトップジャーナルに採択   • ROIの測定に対して、25個の大規模実験(ABテスト)を行なった   ◦ その結果、ROIの信頼区間は中央値で100%以上の幅が発生した  • このような、ROIの測定の困難さが、広告支出の最適化の困難さを示している  

Lewis and Rao (2015 QJE) 228 • そもそも、なぜROIの測定が困難なのか?   •
論文の2.2節から以下の例を考えてみる   ◦ 広告CPN  ▪ 期間：2週間  ▪ 1人あたり広告費用：$0.14(20-80回のディスプレイ広告 or 7-10回のTVCMに相当)   ▪ 粗利益率：50%  ◦ 基本的な売上データ   ▪ 平均売上：$7/人   ▪ 売上の標準偏差：$75/人   ▪ 目標ROI：25% 

Lewis and Rao (2015 QJE) 229 • これを検出するにはどうすればいいのか?   ◦
必要な効果量: 1人あたり$0.35の売上増加(= これは平均売上の5%の増加に相当)  ◦ 売上のばらつき: $75（標準偏差）   • これによって、決定係数は上のような数式となる   ◦ つまり、広告効果による売上の変動の0.00054%しか説明できないということ  • 大きな売上のバラツキから、僅かな効果の検出を頑張らないといけない  

Lewis and Rao (2015 QJE) 230 • 先程の例をまとめると、なぜROIの測定が困難なのか?   ◦
個人レベルの売上の変動が非常に大きいから   ▪ 広告コストに対して、10倍以上の標準偏差を示すことが一般的   ◦ 広告効果による売上の変動が小さく、サンプルサイズが足りないから   ◦ 検出力が足りない  • そのため、以下の測定上の問題が発生する   ◦ 意味のある実験のためには、1000万人の週以上のsample sizeが必要   ▪ こんなのを実施できる企業はほぼ存在しない   ◦ 仮にROIを10%の精度で実験するには、一般的な実験の62倍が必要   • 次スライドに示す25個の実験の結果が、この上の内容を表している  

Lewis and Rao (2015 QJE) 231 • ROIの仮説検定のシナリオごとに、どれほどの倍率のサンプルサイズが必要かをしめしたもの   ◦
xがついている列がそれ  • 10%の向上をしめすことすらほぼ無理なのがわかる   • そんな状態で、どのように広告の効果測定を上手くやればいいのか?   ◦ 広告の効果測定手法を開発できないか?  

Johnson et al. (2017 MS) 232 • Yahoo reaserchのオンライン広告についての効果検証論文  
◦ 小売業者の広告を対象としている   • 以下のような実験デザインにすることで、検出力を向上   ◦ Full群：小売業者の広告のみ表示   ◦ Half群：小売業者の広告と対照広告を50%ずつ表示   ◦ Control群：対照広告のみ表示   • Control群と比較して、有意な売上の向上(= 3.6%)を確認できた  

Johnson et al. (2017 MS) 233 • Control群の広告は、上のようにYahooの検索広告を出している   •
なぜこのようなデザインで検出力を向上できるのか?   ◦ 「広告を見る可能性がある人」を特定できるから   ▪ Control群で対照広告を見た人 = Full群で小売業者の広告を見たであろう人  

Johnson et al. (2017 MS) 234 • このようなデザインにすることで、以下のデータを除外できる   ◦
Yahooにログインしていなかったり、広告が表示されなかったuser   ◦ 広告露出前の購買データ   ▪ 対象広告を出すことによって、Control群でもいつから広告の影響を受けたかがわかる   • これによって、データの52.4%を無関係として除外可能   ◦ そして、推定精度も向上  ◦ これが論文タイトル、「Less is More(「データが」少ないほうがいい) 」の意味  • また、推定しているものが実は変わっている   ◦ 従来は ITT(＝広告を当てようとした効果) を広告の露出確率で割ることで推定していた   ◦ しかし、対象広告を使うことで、 TOT(=広告があたったことの効果) を直接推定可能になる  • しかし、このデザインは流石にコストがかかりすぎではないだろうか?   ◦ 対照広告をもっと工夫できないか?  

Johnson et al. (2017 JMR) 235 • 対照広告について、更に改良を行なった実験システム(Ghost Ads)の提案  
◦ 簡単に言うと、別の広告を出してしまう   • Googleの広告プラットフォームにおいて、リターゲティングオンライン広告で実験   ◦ ウェブサイト訪問が17.2%増加、購入が10.5%増加   ◦ これを、従来のものより一桁以上少ないコストで測定  

Johnson et al. (2017 JMR) 236 • 内部的には、上の仕組みになっている   ◦
広告プラットフォームは、内部オークションを回してどの広告主を出すか決める   ◦ 対照群のuserには、内部オークションの候補からこの主をomitしてしまう   ◦ ただし、オークションのsimulateをして、その主をいれた場合の内部オークションを行った結果のloggingをする   • また、Predicted Ghost Adsという手法も提案している(実験はそちらで行なった)  

Johnson et al. (2017 JMR) 237 • Figure 4がGhost Adsで実際に起こる挙動
 

Johnson et al. (2017) 238 • Ghost Adsの実践編  • 432の実験を実施した 

Johnson et al. (2017) 239 • 結果のまとめ  ◦ サイト来訪の効果は結構あった  
◦ 売上の効果は思ったよりないかも  

広告におけるABテスト以外の推定手法  240

その他の推定手法の応用例 241 • 効果検証のGold StandardはABテストで、それを行えるに越したことはない   ◦ 他の手法を広告に使った例はあるか?   •
ここでは、以下の2つの例を紹介する   ◦ Blake, Nosko and Tadelis(2015 Econometrica): DID   ◦ Gordon et al. (2019 MS): ABテスト VS その他手法  

Blake, Nosko and Tadelis(2015 Econometrica) 242 • eBayのペーパー  ◦ Econometricaという経済学系のトップジャーナルに採択
  ◦ 理論系論文が多いので珍しいかも?   • Difference in differencesという因果推論の手法を適用  

Blake, Nosko and Tadelis(2015 Econometrica) 243 • Googleなどで検索すると、検索結果の上に広告が表示される。   •
検索キーワードに条件づけて表示される  

Blake, Nosko and Tadelis(2015 Econometrica) 244 • Brand Keyword: 会社の名前(eBay)などのこと
  ◦ eBayで検索すると、広告にeBayが表示され、検索結果にもeBayが表示される。   • MSN(Bing), GoogleでそれぞれBrand Keywordの広告を止めてみた   • 今まで広告でクリックしていた人たちが、そのまま検索結果をクリックするようになった。  

Blake, Nosko and Tadelis(2015 Econometrica) 245 • ある地域において、eBayで販売されるような商品名に関する検索連動型広告を止めてみた   ◦
時系列トレンドが両グループで同じになるように州をグループに分けた(= DID)  • 左は広告のクリックを経由して発生した購買の量: TESTでは広告が止まっているので広告経由の購買が激減   • 右は全体の購買量の差（止まってない地域 - 止まった地域）: ほぼ変化はなかった  

Blake, Nosko and Tadelis(2015 Econometrica) 246 • ユーザーレベルの購買データがあるので分析   •
ユーザーを購買頻度（Frequency）と購買間隔（Recency）で細分化して効果を検証   ◦ 購買頻度が低いユーザーほど効果が高い（eBay使ったことない人には有効）   ◦ 最近使ってないユーザーほど効果が高い（eBayを最近使ってない人には有効）  

Gordon et al. (2019 MS) 247 • Facebookのデータを用いて、観察的手法がRCTの結果を復元できるのか? というのを検証  
◦ 結果は、全然復元できなかった   ◦ 15個のケース、5億のユーザー実験オブザベーションと16億の広告インプレッションを使用   ◦ こういうpaperのハシリはLaLonde(1986). 論文内でも触れられている   • ちなみに、Gordon et al.(2023)で手法などを別に変えた続編っぽいものもある  

Gordon et al. (2019 MS) 248 • 手法は以下  ◦ EM;
完全一致マッチング   ◦ STRAT; 層化マッチング   ◦ PSM; 傾向スコアマッチング   ◦ RA; 回帰調整  ◦ IPWRA: 逆重み付け法   • ケース4の結果が左   ◦ RCTとずれまくっている  

広告の効果測定という”地獄”  249

色々見てきたが... 250 • 広告の効果測定そのものが、実は結構ハードルが高い   ◦ ABテストはお金も規模もかかる   ◦ Ghost
Adsを理解してくれるクライアントどれだけいる?   ◦ 代替手法もなんかうまくいかなそう   • Johnsonはオンライン広告の実験をこう表現している   ◦ “inferno(地獄) ” (2023 JoEMS)  • 何がこんなに地獄なのかをまとめる   ◦ ダンテの『神曲』にあわせて” 9つの地獄の輪”と表現している 

地獄めぐり 251 1. 実験の必要性（Resigned to field experiments）   ◦ Gordon
et al.でみた通り、観察データだけでは広告効果の因果推論が困難   ◦ 広告の露出タイミングや対象者が内生的に決定されることが問題(冬にカイロの広告を出す、とか)   ◦ ユーザーの興味・関心に基づく自己選択バイアスや、オンライン行動の時間バイアスも存在   2. (非)遵守（Experimental (non-)compliance）   ◦ 処置群のユーザーが必ずしも広告に接触するわけではない(アドブロッカーやサイト内行動による)   ◦ Ghost Adなどがこの解決策になる   3. 検出力の限界（Statistical power limits learning）   ◦ Lewis and Raoで見た通り極めて小さい効果を検出するために大規模なサンプルが必要   4. 広告頻度の内生性（Endogenous exposure intensity）   ◦ 広告頻度はユーザーの行動に依存し、これをアルゴリズムが決定してしまう   ◦ Impressionレベルでの randomizationがこの解決策となる  

地獄めぐり 252 5. ID分断化（Identity fragmentation）   a. ユーザーの多デバイス使用による追跡の困難さが存在   i.
cookieについては、中央値でuserは2つ持っている   b. デバイスレベルでの効果測定はバイアスの源泉になる   c. 個人識別IDの導入や地理別の層化集計がこの解決策となる   6. スピルオーバー効果（Spillovers）; 後述   a. 競合他社の広告との相互作用などが存在   b. また、処置群の結果が対照群に影響を与えることがある   7. インクリメンタリティ最適化（Incrementality-based optimization）   a. Cost per Incremental Action (CPIA)の最適化の必要性(ちょっとここらへんはよくわからず)  

地獄めぐり 253 8. プライバシー中心の変更への対応（Privacy-centric changes）   a. GDPRなどの規制強化やサードパーティCookieの廃止で、そもそも計測が困難になっている   b.
新しい測定手法の開発がこの解決策となる   9. その他(Depths of the inferno）   a. 組織間の調整、オフライン効果の測定困難などが挙げられている  

Spillover効果について 254 • そもそも、DSPのような広告配信だと処置群が対照群に影響を与えるのはほぼ避けられない   • 例: 値付けロジックの変更   ◦
処置群で値付けが高く付くようになり、win rateが向上   ◦ 配信予算は有限なので、処置群のほうが必然的にimp数や売上が多くなる   ◦ その結果、対照群のimpや売上が少なくなる   • これはABテストなどにおける SUTVA (Stable Unit Treatment Value Assumption) の仮定に違反  ◦ 「ある単位(unit)の潜在的な結果は、その単位が受け取る処置のみに依存する」という仮定   • 上記のような事象は値付けロジックだけでなく、クリエイティブ実験や予測モデル改善でも当然起きる   • ではどのように、このABテストを円滑に完遂可能なのか...?   ◦ 第9回論文につながる... 

paper 255 • Lewis, Randall A., and Justin M. Rao.
"The unfavorable economics of measuring the returns to advertising." The Quarterly Journal of Economics 130.4 (2015): 1941-1973.   • Johnson, Garrett A., Randall A. Lewis, and David H. Reiley. "When less is more: Data and power in advertising experiments." Marketing Science 36.1 (2017): 43-53.   • Johnson, Garrett A., Randall A. Lewis, and Elmar I. Nubbemeyer. "Ghost ads: Improving the economics of measuring online ad effectiveness." Journal of Marketing Research 54.6 (2017): 867-884.   • Johnson, Garrett, Randall A. Lewis, and Elmar Nubbemeyer. "The online display ad effectiveness funnel & carryover: Lessons from 432 field experiments." Available at SSRN 2701578 (2017).   • Johnson, Garrett A. "Inferno: A guide to field experiments in online display advertising." Journal of economics & management strategy 32.3 (2023): 469-490.   • Goldberg, Samuel G., Garrett A. Johnson, and Scott K. Shriver. "Regulating privacy online: An economic evaluation of the GDPR." American Economic Journal: Economic Policy 16.1 (2024): 325-358.   • Johnson, Garrett A., Scott K. Shriver, and Samuel G. Goldberg. "Privacy and market concentration: intended and unintended consequences of the GDPR." Management Science 69.10 (2023): 5695-5721.   • Kobayashi, Shunto, Garrett Johnson, and Zhengrong Gu. "Privacy-Enhanced versus Traditional Retargeting: Ad Effectiveness in an Industry-Wide Field Experiment." Available at SSRN (2024).   • Blake, Thomas, Chris Nosko, and Steven Tadelis. "Consumer heterogeneity and paid search effectiveness: A large‐scale field experiment." Econometrica 83.1 (2015): 155-174.   • Gordon, Brett R., et al. "A comparison of approaches to advertising measurement: Evidence from big field experiments at Facebook." Marketing Science 38.2 (2019): 193-225.   • Kohavi, Ron, et al. "Controlled experiments on the web: survey and practical guide." Data mining and knowledge discovery 18 (2009): 140-181.   • Kohavi, Ron, Diane Tang, and Ya Xu. Trustworthy online controlled experiments: A practical guide to a/b testing. Cambridge University Press, 2020.  

paper 256 • Kohavi, Ron, Alex Deng, and Lukas Vermeer.
"A/B testing intuition busters: Common misunderstandings in online controlled experiments." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.   • LaLonde, Robert J. "Evaluating the econometric evaluations of training programs with experimental data." The American economic review (1986): 604-620.   • Gordon, Brett R., Robert Moakler, and Florian Zettelmeyer. "Close Enough? A Large-Scale Exploration of Non-Experimental Approaches to Advertising Measurement." Marketing Science 42.4 (2023): 768-793.   • Liu, Min, Jialiang Mao, and Kang Kang. "Trustworthy and powerful online marketplace experimentation with budget-split design." Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021.  

Intro:   Look-alike model  AI事業本部金子雄祐   257

はじめに 258 • おまけ回なので、手法の理解よりはpaperのreference用程度に捉えてください 

目次 259 • look-alike modelとは?  • 論文紹介 

look-alike modelとは?  260

Look-alike model 261 • 既存顧客の中で特定の行動(例: 購買、会員登録)をとった顧客と類似した潜在顧客を見つけるモデル   ◦ この、「特定の行動をとった顧客」をseed(種)と呼ぶ  
◦ seed顧客のデータ（デモグラ情報など）を分析し、その特徴を学習することで、seed顧客と似た属性を持つユーザーを、より広い顧客プールの中から探し出す   • 上記図はShen et al.(2015 KDD) より引用  

Look-alike model 262 • 主にMeta, Google, LinkedInなど、多様な顧客情報を持つプラットフォーマーにおけるモチベーションが高い   • アプローチは実は多様な例がある(上はRahman
et al.(2023 SIGIR)より)   ◦ ルールベース、回帰ベース、DNNベース、グラフベース、行列分解ベースなど...   ◦ レコメンド的な問題設定が多い   • これらを全て紹介するとキリがないので、限られた論文を紹介する  

論文紹介  263

アプローチ 264 • 本スライドでは、以下の5論文を簡潔に紹介する   ◦ Shen et al.(2015 KDD):
初の定式化, ルールベース   ◦ Liu et al.(2016 KDD): LinkedInの実例   ◦ Liu et al.(2019 KDD): リアルタイムの大規模look-alike modeling   ◦ Doan et al.(2019 CIKM):敵対的学習の利用   ◦ Rahman et al.(2023 SIGIR):  

Shen et al.(2015 KDD) 265 • この以前にも、Look-alike modelingのpaperはいくつもある   •
なぜこの論文からなのか?   ◦ 理由: オーディエンス拡張問題の定式化をおこなったのが初めてだったから   ◦ これ以前は、MLモデルの単なる応用に留まるものが多かった   ▪ LRや協調フィルタリング etc…  

Shen et al.(2015 KDD) 266 • (a)は広告主が定義したセグメントの例   • (b)は広告主が定義したセグメントに対して拡張したセグメ
ントの例 

Shen et al.(2015 KDD) 267 • オーディエンス拡張問題を、次の3つのmetricを用いて定義している   ◦ 広告主のセグメントルール
Sに対して、拡張セグメントルール S’をオーディエンス拡張は推奨する   ▪ similarity: 類似度   • S と S' の類似度がある閾値 α より大きい   ▪ performance: パフォーマンス(CVRなど)   • S' のパフォーマンスが S のパフォーマンスと比べてある閾値 β より改善している   ▪ Audience: ユーザー数（リーチ）   • S と S' の和集合のユーザー数が、元のセグメント S のユーザー数より十分に大きい   • どうやってこのようなセグメントを見つけるのか?  

Shen et al.(2015 KDD) 268 • ベースライン: 貪欲法   ◦
S: 元のセグメント  ◦ m: 所望のセグメントサイズ   • 手順は以下  ◦ Ωに元のセグメントのユーザー集合を代入   ◦ 候補カテゴリーの収集(C)   ▪ 元セグメント(S)のユーザーが持つすべてのカテゴリから  ◦ カテゴリの評価とソート   ▪ 各カテゴリcjについて、Ωに含まれるユーザーのうちそのカテゴリを持つユーザー数をカウントして降順にソート  ◦ 目標サイズmに達するまで、または候補がなくなるまで反復   ◦ S ∨ S' (元のセグメントと拡張セグメントの論理和)を出力  

Shen et al.(2015 KDD) 269 • 貪欲法の問題  ◦ 計算コストが高い  ▪
ユーザー集合を何度も走査するから   ◦ 拡張セグメントの品質を考慮していない   ▪ パフォーマンス指標（CTRなど）を考慮していない   ◦ 新規性（リーチ）が限定的   ▪ 純粋にカバレッジのみを最適化しているから   • Betterなアプローチはあるか?  

Shen et al.(2015 KDD) 270 • 2番目のアプローチはこの重み付きスコア関数   ◦ これらのsimilarityなどを用いて(6)式を計算する
  ◦ 計算が容易なのが大きなメリット   • スコアの高い順にtop-kカテゴリを選択し、選択したカテゴリの論理和を取ってセグメントを作成  

Shen et al.(2015 KDD) 271 • Hadoopを用いた実装   ◦ MapReduceを使う 

Shen et al.(2015 KDD) 272 • weightedのほうが良い性能を発揮  

Liu et al.(2016 KDD) 273 • LinkedInの論文  • Shen et
al. (2015)とは別種のアプローチ  

Liu et al.(2016 KDD) 274 • 以下の2つのアプローチのハイブリッドを提案   ◦ Campaign-Agnostic
Expansion   ▪ ユーザープロファイルの属性を類似属性に拡張   ▪ 例：「Data Mining」スキル → 「Big Data」「Machine Learning」   ▪ メリット：即時利用可能、新規キャンペーンにも適用可能   ◦ Campaign-Aware Expansion   ▪ キャンペーンの元のターゲットユーザーに類似したユーザーを特定   ▪ Similar-Profilesアルゴリズムを使用   ▪ メリット：より正確な拡張が可能   • 詳細はCh.4の話でされており、割愛するが、これらの特定手法は例えば以下のものを用いている   ◦ コンテンツベースのフィルタリングアプローチ   ◦ TF-IDFを用いた重み付けをして、コサイン類似度で類似性を計算  

Liu et al.(2016 KDD) 275 • ABテストを実施。メトリックの改善についての表   • 結果
  ◦ インプレッション：+10.36%, リーチ：+10.40%, 収益：+17.47%   ◦ CTRの低下を最小限に抑制（-0.44%)   • 広告主とプラットフォーム双方にメリット   ◦ 広告主：より簡単な設定で効果的なリーチ   ◦ LinkedIn：広告在庫の活用率向上  

Liu et al.(2019 KDD) 276 • WeChatの論文  • 推薦アルゴリズムにおいて、look-alikeモデルを活用したpaper  
◦ そもそも推薦においてどのように活用しているか?   ◦ リアルタイムの大規模look-alike modelingのpaper  

Liu et al.(2019 KDD) 277 • 推薦における「マシュー効果」の問題   ◦ 人気コンテンツがより多くの露出を獲得
  ▪ 多くのユーザーの行動履歴があり、CTR予測が容易   ◦ ロングテールコンテンツ：行動履歴が少なく、CTR予測が困難   ▪ 結果として、人気コンテンツばかりが推薦される悪循環が発生   • これをlook-alike modelを用いて解決したい   ◦ コンテンツの行動履歴ではなく、「シードユーザー」の特徴を活用   ◦ シードユーザー：そのコンテンツに既に興味を示した少数のユーザー群   ◦ シードユーザーと似た特徴を持つユーザーを見つけることで、配信対象を拡大   • 結果として、質の高いロングテールコンテンツでも適切なユーザーへ到達可能  

Liu et al.(2019 KDD) 278 • RALMアルゴリズムの提案   ◦ 主要なコンポーネントは以下
  ▪ ユーザー表現学習  • 新しいAttention Merge層  ▪ Look-alike学習  • グローバルAttention：シードの頑健な表現   • ローカルAttention：ユーザー固有の適応   • リアルタイムなシードクラスタリング   • かなり長いし難解なので簡単に要約    

Liu et al.(2019 KDD) 279 • ユーザー表現学習  ◦ 入力：ユーザーの多様な特徴  
▪ ドメイン情報、カテゴリ興味、行動履歴 etc…   ◦ Attention Merge層  ▪ 各特徴フィールドの重要度を学習   ▪ 強い特徴と弱い特徴のバランスを調整   ◦ 出力: ユーザー埋め込みベクトル  

Liu et al.(2019 KDD) 280 • シードユーザーの表現学習   ◦ グローバルAttention 
▪ シード全体の一般的な特徴を抽出   ▪ ノイズの多いユーザーの影響を軽減   ◦ ローカルAttention  ▪ ターゲットユーザーに関連する特徴を強調   ▪ シード群の部分的な類似性を捕捉   • K-meansクラスタリング  ◦ シードユーザーをk個のクラスタに分類; 計算量を大幅に削減（数百万 → 数十）    

Liu et al.(2019 KDD) 281 • RALMアルゴリズムの図   

Liu et al.(2019 KDD) 282 • ABテストの結果   

Doan et al.(2019 CIKM) 283 • 性能評価の結果を見せたいので簡単に紹介   ◦ 既存手法の課題 
▪ 類似度ベース手法: データのクリティカルな性質を見落としたり、精度に問題   ▪ 回帰ベース手法: 計算コストが高く、新規キャンペーンで性能が悪い   ◦ 敵対的学習の利用 

Doan et al.(2019 CIKM) 284 • Factorization層  ◦ 特徴量間の相互作用を学習, スパースデータへの効果的な対応
  • 敵対的学習  ◦ バイナリ表現の最適化, 効率的な類似度計算の実現   • 教師なし学習  ◦ 新規キャンペーンにも対応可能, スケーラビリティの向上  

Doan et al.(2019 CIKM) 285 • 6つのパートナーの実データを用いて検証   ◦ 精度面:
小規模シードのデータセットでAFAが有効, 大規模シードだとGBTが有効  • GBTについては、以下のmeritがある   ◦ 高次の特徴量の相互作用を学習可能   ◦ 欠損値に強い  ◦ スケーラビリティが高い  

Rahman et al.(2023 SIGIR) 286 • 楽天のpaper  ◦ 顧客の異なる行動や特徴を統合した”360度ビューを活用した” look-alike
modelingの提案  

Rahman et al.(2023 SIGIR) 287 • 5つの顧客ビュー  ◦ デモグラフィックビュー：年齢、性別、地域など  
◦ ロイヤリティビュー：店舗・ブランドへの忠誠度   ◦ Eコマースビュー：楽天市場での行動   ◦ トラベルビュー：楽天トラベルでの予約行動   ◦ 家族ビュー：家族メンバーの購買行動  

Rahman et al.(2023 SIGIR) 288 • E-CLMの提案  ◦ 5つのビューの統合したembeddingを生成  
◦ コサイン類似度ベースのマッチング + 閾値Tでのフィルタリング   • E-CLM++  ◦ XGBoost(ベースラインモデル)にこのE-CLMのfeatureを食わせる  

Rahman et al.(2023 SIGIR) 289 • ベースラインはXGBoost(with GPU V100)  
◦ XGBoost(TP)に他のfeatureを食わせたり、E-CLM++のようにXGBoostに今回のfeatureを食わせたり  

paper 290 • Liu, Yudan, et al. "Real-time attention based
look-alike model for recommender system." Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.   • Rahman, Md Mostafizur, et al. "Exploring 360-Degree View of Customers for Lookalike Modeling." Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2023.   • Liu, Haishan, et al. "Audience expansion for online social network advertising." Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016.   • Doan, Khoa D., Pranjul Yadav, and Chandan K. Reddy. "Adversarial factorization autoencoder for look-alike modeling." Proceedings of the 28th ACM International Conference on Information and Knowledge Management. 2019.   • Shen, Jianqiang, Sahin Cem Geyik, and Ali Dasdan. "Effective audience extension in online advertising." Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015.  

Ad-DS Paper Circle Intro

Ad-DS Paper Circle Intro

More Decks by Yusuke Kaneko

Featured

Transcript