Bidding Machine: Learning to Bid for Directly Optimizing Profits in Display Advertising
Ren, Kan, et al. "Bidding machine: Learning to bid for directly optimizing profits in display advertising." IEEE Transactions on Knowledge and Data Engineering 30.4 (2017): 645-659.
論文読み会資料version
Meta
TKDE 2017 (Transactions on Knowledge and Data Engineering) に投稿されたもの。TKDEはIEEE ICDE (International Conference of Data Engineering) の 1トラックの模様。
1st authorは投稿時点では博士課程、2020年現在はMicrosoft Research所属
Bid Landscape Forecasting等、DSPのタスクに関する論文を他にも投稿している
概要
従来の方法は (1) インプレッションの効用推定、(2) 市場価値の推定、(3) 1と2 を使った最適入札を求める
というものであった。著者らはこれら3つの問題を独立して処理するのではなく一緒に最適化を行なう包括的なフレームワークを提案している。オフライン実験およぼオンライン A/B テストで提案手法の有効性を示している。
1.背景
DSPのよくある入札最適化の手順の紹介
CTR予測はバイナリ回帰問題として定式化してでき、これはロジスティック回帰や勾配ブースティング、factorization machineなどの機械学習モデルで解く事ができる
コスト推定は市場価格分布を予測するタスク
CTRとコストに基づいて、キャンペーン予算・オークションボリューム等を考慮いて最適な入札関数を求める
ただしこのsequentialな最適化は実は上手くいかない。
CTR予測・BidLandscape予測は最終的な入札の効用に基づいて学習されるべき
CTR予測だとクリックが得られなかった時のコストは発生するが、インプレッションを失なうコストは無いためCTR予測の必要な精度は 0〜1 の範囲で同じではない
競争の激しいキャンペーンにおいては落札できるかどうかの予測の信頼度は低い
予算制約下においてCTR予測と落札価格の両方について2つの最適化モデルを組みあわせると有効
提案手法
which considers the three challenges as a whole and directly pushes the limit of the campaign profit by jointly optimizing the three components: user response prediction, bid landscape forecasting and bid optimization.
貢献
RTBにおけるメインタスク、User Response Prediction, Bid Landscape 予測, 入札最適化は強く相関しているが今までは別々に取りくまれていた事を示した
↑ の3つを一緒に最適化するフレームワークであるBidding Machineを提案
オフラインおよびオンラインA/B Test により有効性を実証した
2. Related Works
Response Prediction
CTR予測CVR予測
Logistic Regression
tree based model
factorization machine
他にはFTRLやBayesian probit regression...
CTR予測の評価指標としてはAUCや Relative Information Gain (RIG)
we use a logistic regression as a working example and go one step further over 7 to reformulate the CTR estimation learning by directly optimizing campaign performance (profit) Bid Landscape予測
広告インベントリの種類ごと
ツリーモデル
入札ストラテジ
オークション理論によりセカンドプライスオークションではTruthful Biddingが最適だと証明されている
ただし予算制約などがあるときには最適ではないかもしれない
linear bidding strategyは広く使われている、これは CTR・CVRに定数値を乗算した値
CVRリフトによって入札価格を決定するリフトベースの入札戦略の提案もある
しかしながら市場価格の分布の影響はそれほどされていないし最終的なキャンペーンの効用は目的関数に反映されていないため、高いeCPCや低いROIという好ましくない結果になるかもしれない。
3. Problem Definition of Bidding Machine
定式化もサーベイしていて文献でよくあるNotationはこうだと書いてある
セカンドプライスオークションにおける効用の総和 = sum(財の価値 - 約定金額) を最大にしたい
4 User Respoinse Learning
効用から損失関数を導出、効用が最大になるにように訓練する
vy は y がCVだとしたらCV一件あたりの価値、CVが取れなかったらゼロ。CV(Click)が取れないときにオークションに勝つと期待効用はマイナスになる
4.3 Model Realization
Linear Bidding functionを採用
最初にBid Landscapにはノンパラメトリックな分布を採用したが、パラメトリックな分布も議論する
4.4 Links to Previous Work
5. Cost: Market Competition Modeling
5.1 Linear Form
5.2 Quadratic Form
5.3 Double Optimization for Campaign Performance
6. Bid Optimization
6.1 Bidding Machine Algorithm
7. Experiments
7.1 Datasets
YOYI
iPinYou
negative downsamplingして使った
オンラインテストは YOYI DSP
7.2 Experiment Setup
CTR予測とBid Landscape予測は予算制約なし
入札戦略は予算制約あり
For the bidding strategy optimization, we follow 47, 48 to run the evaluation test using 1/64, 1/32, 1/16, 1/8, 1/4, 1/2 of the original total cost respectively in the test log as the budget constraints. 7.3 Evaluation Measures
campaign performance
profit, ROI, eCPC, CPM, CTR
CTR
AUC, RMSE
Bid Landscape
ANLP (averaged negative log probability)
7.4 Compared Settings
CTR予測
CE: ロジスティック回帰
SE: 二乗誤差で訓練したロジスティック回帰
EU: Expected Utility
RR: risk-return model
BM: CTR estimation model with market modeling
入札
CELIN
Cross Entropy最小化で訓練したCTR予測モデル + 価値評価Linear Model
ORTB 前の論文
PROUD prudent bidder
BM (FULL)
7.5 Campaign Profit Optimization
1つ過学習してる
Our models, both EU and RR, outperform the baselines in terms of CTR and eCPC with comparable CPM and a relatively low winning rate. This indicates EU and RR successfully allocate the budget to high quality cost-effective ad inventories and avoid on the low quality ones.
7.6 Bidding Data Analysis
安く買えている、market priceと入札価格の差が小さい
高額Bidの割合とそれに使った金額
baseline
14%
1.49%
7.7 Bidding Machines
7.8 Online A/B Testing
YOYI PLUS platformに載せてテストした、これは中国のmain DSP
test は 2 phase
CTR予測モデルのテストをデスクトップトラフィックで
モバイルインベントリ限定キャンペーンで入札ストラテジの比較
比較するのにモデル毎の予算は同じに設定した
通過は人民元
Phase 1
We test over 10 campaigns during 25-26 January, 2016
CTR予測器比較
EU (Expected Utility), RR (Risk Return), CE
FM (Factorization Machine)
89M auctions including 3.3M impressions, 8,440 clicks and 1,403 CNY budget cost.
EUのROIが高くてProfitも大きい、EUはeCPCが低いのでクリックが安く変えている
しかもCTRが高い
Phase 2
We test over 5 campaigns on the mobile platform during 30 days in April, 2017.
The whole tested bid flow involves 224M auctions including 23M impressions and 168K clicks and totally 50K CNY budget cost.
CELIN
EULIN
BM
BMが一番利益が大きい
オフライン検証と結果違うけどオフラインテストはデータにバイアスがあるからそんなこともある。
8. Conclusions
RTBの入札において広告主の利益を最大化する学習フレームワークを提案した
我々の数学的な導出により、各コンポーネントの勾配が他のコンポーネントの挙動から利益を得ることが示された。
?
オンラインテストで有効性を実証した
次は打ち切りデータに対して上手く学習する
セカンドプライスオークションでもBid Landscapeちゃんと使おう