オンライン広告運用に関わる論文まとめ

はじめに

negocia株式会社では、「うれしい広告」の実現をミッションに、機械学習、数理最適化の技術を活かして、オンライン広告向けのSaaSを開発しています。今回、オンライン広告運用に関わる最適化、機械学習技術の中から、主にReal time bidding(RTB)周りの論文の動向をまとめました。

動向把握に有用な文献

個別の研究を紹介する前に、まず全体の研究動向を把握するために有用な文献の紹介です。

• Display Advertising with Real-Time Bidding (RTB) and Behavioural Targeting

  • RTB & ディスプレイ広告に関する教科書的な資料
  • この教科書を読んだことで2016年くらいまでの技術を一通りキャッチアップできました

• Learning, Prediction and Optimization in Real-Time Bidding based Display Advertising

  • CIKMのチュートリアル

研究カテゴリ

効用(CTR, CVR)予測

• 過去の実績データを元にCTR, CVRなどの効用を予測する技術
• ロジスティック回帰、Factorization machines, Gradient Boost, Deep Learningなど

インプレッション獲得確率の予測(bid landscape)

• 入札額に対してオークションに勝利する確率を求める技術
• オークションに負けた入札額も含めた打ち切り回帰など

入札額最適化

• インプレッション、CTRやCVRの推定モデルを元に、入札額を最適化する技術
• 貪欲法ベースのロジック、 傾斜勾配法などを用いた最適化

バンディット方策

• 探索と最適化のバランスを取りながらリグレットの最小化（利益の最大化）
• ガウシアンプロセスをもとに、文脈付与、不等式制約、組み合わせ制約など派生

理論解析

• 広告配信の枠組みをゲーム理論で評価する研究など

論文まとめ

効用(CTR, CVR, CPA, CPC)予測

ロジスティック回帰(LR)

• Estimating conversion rate in display advertising from past performance data
  • kwdだけではなくキャンペーン、広告グループなどの上位層の情報を説明変数として追加して、kwdごとのCVRを求めるLRを構築

Factorization machines(変数間の相関を考慮したモデル)

• Factorization machines
  • 特徴量の交互作用をうまく計算できるモデル
• fastFMがいいらしい

Gradient Boost

• 予測モデルの比較実験で使われることが多い

Deep Learning

• DeepCTR予測系の各種手法の実装&検証できるように公開されているレポジトリ

• Deep CTR Prediction in Display Advertising

  • ディスプレイ広告のクリエイト画像+textを入力としてCTRをDeep neural networkで予測しクリエイトを評価

• DeepFM: A Factorization-Machine based Neural Network for CTR Prediction

  • Factorization machineとDeep Neural networkを組み合わせたDeepFMでCTRを予測

• Product-based Neural Networks for User Response Prediction over Multi-field Categorical Data

  • DeepFNNで、パラメータの最適化が収束しない問題を解決したPNNモデルを提案

トピックモデル

• Examining the Impact of Keyword Ambiguity on Search Advertising Performance: A Topic Model Approach

  • キーワードのトピックモデル分類結果のエントロピーを”キーワードの曖昧さ”として定義し、キーワードの曖昧さを説明変数としてCTRを予測

インプレッション取得確率の予測 (bid landscape)

Tree-based log-nominal model

• Bid Landscape Forecasting in Online Ad Exchange Marketplace
  • 入札額に対するRTBの勝率がlog-nominal分布に従っていると仮定。分布の平均・分散をGBDTで推定
  • スパースデータに対応するため実績データをツリー構造でモデル化していることが特徴

Censored regression

• Predicting Winning Price in Real Time Bidding with Censored Data
  • RTBオークションに勝てなかったデータを打ち切りデータとして扱い、トービッドモデル を使った打ち切り回帰分析(Censored regression)を実行
• Scalable Bid Landscape Forecasting in Real-time Bidding
  • 上記論文の等分散性、ユニモーダル性の制約条件を取り除いて汎用性を確保した回帰モデル

Survival Model

• 患者の生存率モデルをヒントに作られたモデル(患者の生存日数は打ち切りデータのため)
• Budget Optimization for Sponsored Search: Censored Learning in MDPs
  • カプランマイヤー法(サバイバルモデル)で入札額に対する入札勝率のノンパラメトリックな最尤推定を行い、推定した確率分布上で広告の入札額を決定し、戦略の有効性をマルコフ決定過程上で検証
• Bid-aware gradient descent for unbiased learning with censored data in display advertising
  • CTRの予測モデルの損失関数を、Bid landscape(サバイバルモデル を利用)で重みつけし、勝率が低いサンプルデータの重要度を増やすことで、入札額によるバイアスを取り除いたアンバイアスなCTR予測を実施
• Deep landscape forecasting for real-time bidding advertising
  • LSTMで入札額に対する勝率を予測するモデルを作成し、サバイバルモデル の考えを取り込んだ損失関数の元でパラメータを最適化することでBid landscapeを予測

入札額最適化

数理最適化

• Efficient Large-Scale Internet Media Selection Optimization for Online Display Advertising

  • 顧客の訪問数がポアソン分布に従うと仮定し、リーチ最大化問題を制約つき凸計画問題に落とし込んだ後に、大規模問題に適用可能なCoodinate Descent法を適用。※リーチ最大化以外でも使えると思われる

• Optimal Real-Time Bidding for Display Advertising

  • 入札額とimpression獲得確率の関係を過去データより最小二乗法で推定し、推定関数の微分により最適な入札戦略を決定

• Statistical Arbitrage Mining for Display Advertising

  • 解析的に入札戦略を決定した後に、その入札戦略で得られる利益の分布をMCMCで推定し、推定した分布の平均と分散を使って、キャンペーンごとの予算配分を二次計画法で決定

• Optimal Bidding in Multi-Item Multislot Sponsored Search Auctions

  • Googleのようなスポンサードサーチオークションに対して、広告ポジション(表示順番)の予測モデルと広告ポジションにおけるCTRの予測モデルを組み合わせてクリック数と広告費費用の予測モデルを構築し、入札額の最適化

• Joint Optimization of Bid and Budget Allocation in Sponsored Search, Zhang et al., 2012

  • Sponsored Search広告における入札額と日予算を同時に最適化.広告ポジションごとの発生確率及び利益はガウシアンモデルを利用

強化学習

• Real-Time Bidding by Reinforcement Learning in Display Advertising
  • RTBを再現する状態空間を計算機上に構築し、強化学習で最適戦略の探索
  • 大規模問題に対応するためにNeural networkでの近似処理を実施

ロジック

• Bid optimizing and inventory scoring in targeted online advertising

  • ロジスティック回帰でコンバージョンのされやすさをサイトごとにスコア付。スコアがいつもより高い(コンバージョン確率が通常より高い)と予測されるサイトの入札額を増やす貪欲法ベースのロジックを構築

PID制御

• Bid Optimization by Multivariable Control in Display Advertising, Xun Yang et al., 2019

  • 最適入札戦略のハイパーパラメータをモデル予測PID制御で逐次アップデートすることで、CPC制約及び広告費用制約を守りつつ、コンバージョン数の最大化

• Unbiased Lift-based Bidding System, Moriwaki et al., 2020

  • 広告リフトアップ効果をIPSを利用してアンバイアスに推定し、広告リフトアップ効果に応じて入札額をPID制御する手法

バンディット

基本理論

• Gaussian Processの教科書

• Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design

  • 腕が無限にある連続腕バンディット問題に対してパラメータ設定方法とリグレット上限を与えた論文
  • GP-UCBと呼ばれる

• Contextual Gaussian Process Bandit Optimization

  • GP-UCBに文脈(曜日、性別・・・)を付与した連続腕バンディット

• Bayesian optimization with inequality constraints

  • GP-UCBに不等式制約条件の付与

• Combinatorial Multi-Armed Bandit: General Framework, Results and Applications

  • 多腕バンディット問題において例えばM本の腕からN本だけ選ぶ状況における報酬の最大化（表示する広告の選択などに使われている）

応用

• Online Joint Bid/Daily Budget Optimization of Internet Advertising Campaigns
  • 広告配信するキャンペーンをCMABを利用して選択。選択したキャンペーンの予算を最適化問題(Multi-knapsack)として定式化し、動的計画法にて最適化

理論解析

ゲーム理論

• Real-Time Bidding in Online Display Advertising
  • RTBで広告配信元と発行元で得られる利益をゲーム理論の立場から解析

おわりに

論文はまだまだ調べたりないところがあるので今後も随時内容を更新していきたいと思います。