社内の勉強会で使ったやつの焼き直しです。

TL;DR;

Managing Risk of Bidding in Display Advertising (WSDM'17) の紹介論文リンク
(CPC課金において) CTR予測を高く見積もって入札したときの赤字リスクの削減を金融工学的アプローチを考慮した二種の入札ロジック(VaR, Risk Management Profit )で考える
CTR予測をBayesian Logistic Regeression + ラプラス近似で分布推定し, 予測の標準偏差を入札に利用する。
既存入札ロジック (Logistic regression + Linear bidding) 比で , 実験対象のキャンペーン全体で見たときにiPinYou でオフライン検証 Profit + 15.4%, 匿名DSPのオンライン検証で 17.5% Profit 上昇

モチベーション

https://github.com/wnzhang/rtb-papers/issues/29 にあって気になった
financial approach に興味あった
オフライン実験のsourceがopen
- fork したもの https://github.com/Schumi543/bidding-at-risk-experiment
オンライン検証で有効性を示していた

問題定義 Risk of Bidding (4.1 より)

変数定義

$ \hat{y} \sim p_\hat{y}(\hat{y})$ : 予測CTR
$v$ : 広告主が定義するuser action (click, conversion の価値) = CPC単価
$r = v \cdot \hat{y}$ : utility, impression の価値
$z \sim p_z(z)$ : market price(= second price)
$b$ : 自DSPの入札価格
$R(b)$ : Profit

Truth-telling bidding

Truth-telling bidding : 予算制約やオークションのボリュームを考慮しないケース
Profit $( v \cdot \hat { y } - z )$ を最大化する場合, (14) ~ (18) より $ \mathbb{E}[r] = v \cdot \mathbb{E}[\hat{y}] $が最適な入札価格
キャンペーン予算とオークションボリュームを考慮する場合は補正係数$\phi$ をかけて, $\phi \cdot \mathbb{E}[r]$ を考える。

Discussion of Risk

$v \cdot \hat{y} < z $つまり $R[b] < 0 $となるケースは赤字となる
P(R(b)<0) の算出は以下式(19)

P ( R ( b ) < 0 ) = \int _ { 0 } ^ { 1 } p _ { \hat { y } } ( \hat { y } ) P ( b > z > v \cdot \hat { y } ) d \hat { y }= \int _ { 0 } ^ { 1 } p _ { \hat { y } } ( \hat { y } ) \int _ { v \cdot \hat { y } } ^ { b } p _ { z } ( z ) d z d \hat { y } \tag{19}

具体例でシミュレーション

予測CTR分布
- 式(12) で $\sum _ { i } \mu _ { i } x _ { i } = - 1 , \sum _ { i } q _ { i } ^ { - 1 } x _ { i } = \frac { 1 } { 3 }$ とする
- このときCTRの期待値は 0.283
market price
- 対数正規分布で, $\mu = 4 , \sigma = 0.5$
click value = 300

先述の truth-telling bidding では 84 での入札が最適だが, 16.7 % の赤字リスクを負う
$\hat {y}$ の標準偏差(分散)が大きいと, この赤字リスクは大きくなる -> VaR などの予測の分散を考慮した入札戦略を考える。

提案手法

前提知識

Baysian Logistic Regression

単純に Logistic Regression のベイズバージョン, 分布推定可能
今回の論文ではラプラス近似を用いて, 閉形式で予測CTR分布を導出 (12)
式の導出は PRML と同様なので省略
本文献中ではオンライン環境でどうベイズ更新したかは書いていなかった

linear bidding

pCTRに予算制御などを考慮した, 係数をかける入札戦略

VaR

Value at Risk

バリュー・アット・リスクは、ある期間 $T$ における資産価値の損失リスクを推定した値で、統計上の信頼水準 $X %$において推定される最大損失 $Y$のことである
https://ja.wikipedia.org/wiki/バリュー・アット・リスクより

効率的フロンティア

方程式(1)をリスク・リターン平面上で図示したものを最小分散フロンティア(英: minimum variance frontier)と言う。
さらに最小分散フロンティアにおいて大域的最小分散ポートフォリオより上側の部分の曲線を効率的フロンティア(英: efficient frontier)と呼ぶ
https://ja.wikipedia.org/wiki/現代ポートフォリオ理論より

提案手法

lem1. Cantelli's Inequality

$P ( r < \mu - \alpha \sigma ) < \frac { 1 } { 1 + \alpha ^ { 2 } } \tag{20}$

チェビシェフの不等式の仲間, 確率分布のtailの確率のbound
これを使って, 2種類の入札ロジックを考える

Bidding with Value-at-Risk(VaR) utility

VaRの派生として, VaR utility を以下の式で考える

\tilde { r } = \mathbb { E } [ r ] - \alpha \operatorname { Std } [ r ] \tag{21}

このとき, 実utility $r < \tilde { r } $ となる確率は, lem1より $\frac { 1 } { 1 + \alpha ^ { 2 } }$ でboundされる。

このとき, (18)は以下のように変形される。

b _ { \mathrm { VaR } } ( r ) = \tilde { r } = v \cdot ( \mathbb { E } [ \hat { y } ] - \alpha \operatorname { Std } [ \hat { y } ] ) \tag{22}

$ \alpha$の各場合について以下のように名付け
- $\alpha < 0$ : risk seeking リスク追求(強気入札)
- $\alpha = 0$ : risk neutral リスク中立(通常入札)
- $\alpha > 0$ : risk averse リスク回避(弱気入札)

式(12)から直接導かず, lem1を経由して, VaR入札戦略を決めた理由は以下

解析的なCTR予測分布でなくても適用可能
$\alpha$ を定数パラメータとして扱うことで計算が効率的に行える

さらに, campaign budgetを考えるための係数 $\phi$ を考えるので実際の入札額は以下のように決まる。

b _ { \mathrm { VaR } } ( r ) = \phi \cdot v \cdot ( \mathbb { E } [ \hat { y } ] - \alpha \operatorname { Std } [ \hat { y } ] )

Bidding for Risk Management Profit

VaR 以外のアプローチとして直接profit R(b) を最適化する方法とそのリスクの考慮を考える。

profit R(b)は以下の式で表される。

R ( b ) = \left\{ \begin{array} { l l } { 0 } & { b \leq z \quad ( \operatorname { lose } ) } \\ { v \cdot \hat { y } - z } & { b > z }  \quad ( \operatorname { win } )  \end{array} \right.  \tag{23}

※ $\hat{y} , z$ が確率変数であることに留意

R(b)についても, lem1 からrisk のboundを考えるための VaR Profit を以下で定義

$\tilde { R } ( b ) = \mathbb { E } [ R ( b ) ] - \alpha \operatorname { Std } [ R ( b ) ] \tag{24}$

このとき, 入札額 $b_{RMP}$は以下の式から導出される

$b _ { \mathrm { RMP } } ( R ( b ) ) = \underset { b } { \arg \max } \mathbb { E } [ R ( b ) ] - \alpha \operatorname { Std } [ R ( b ) ] \tag{25}$

$ \mathbb { E } [ R ( b )$ と $\alpha \operatorname { Std } [ R ( b ) ]$ は非自明な trade offを持つので, bは Efficient Fontierに基づき決定する。

詳細は参考資料 ¹ を参照

実験

オフライン検証(iPinYou)

データセット

2013年に公開された open dataset, 10日分, 9キャンペーン 19.5M imps, 14.89K clicks の配信ログ
後半3日がテスト用のデータとなっている

実験プロトコル

CTR予測モデルは training dataで学習
ハイパーパラメータ $\alpha, \phi$ はtest data の前半をsplitしたvalidation dataを用いて調整
- $\phi$ : 予算制約およびオークションボリューム考慮のための係数
- $\alpha$ : risk をどの程度考慮するかの係数
残りのテストデータでパフォーマンスをテスト
CPC単価はキャンペーン単位でtraining データのCPCの平均を利用
テストの入札リクエストが尽きた場合, もしくはキャンペーン予算を使い切ったときにテストは打ち切られる

比較した手法

LR + Linear Bidding
VaR
RMP

Evaluation Measure

campaign profit
campaign ROI
- profit/cost
CPM
win rate
CTR
eCPC
Cost - Penalized profit
- この論文で著者が定義したmetrics
- パフォーマンスとコストは通常トレードオフなので, いくつかの$\lambda$ に対して, この値をみてハイパーパラメータ $\alpha, \phi$ をチューニング(5.5で説明)

profit -  \lambda \space cost 
(= total\_click\_value -  (1+\lambda) \space cost)

Profit and Cost analysis

ハイパーパラメータ $\alpha, \phi$ チューニングのために様々な条件下でのprofit- cost のトレードオフを分析
このとき $\phi = 1$ としてOK
$ \alpha$の各場合について profit -cost トレードオフは以下
- $\alpha < 0$ : risk seeking リスク追求(強気入札)
- $\alpha = 0$ : risk neutral リスク中立(通常入札)
- $\alpha > 0$ : risk averse リスク回避(弱気入札)

Non-Budgeted Settings

予算制約を考慮しない場合において, $\alpha$ を変化させたときのVaR bidding, RMP bidding のProfit とCost の関係は以下

図のようにほぼ凸な形状になる, かつ peak は Risk-averse
従って経験的に Risk-averseがこの場合の支配戦略となる

Budgeted Settings

実環境では予算制約がある。
文献[38] と同様に複数パターンの予算制約でのパフォーマンスを評価するために, 予算を 1/2, 1/4, 1/8… として実験を行った。

Selected model は CP-profit を用いて $\lambda = 0, 0.2, 0.4$ に対して$\alpha, \phi$ をチューニングしたもの, こちらもProfit でみた場合Risk-averseなモデルが支配的

Distinction with Lower Biddings

Risk-averse bidding とlinear biddingで入札を弱める戦略(Lower Bidding)の差を考える

当然, linear biddingでも全体の入札を弱めると, cost と profitの両方が低下し, ROIは増加する。

図5で示されたように, Risk-averse biddingでは Lowere Bidding と同等のコストで profit と ROI を増加させた。

この意味で Risk-averse なモデルのほうが, Lower bidding より優れている。

Bidding without Budget Constraints

図6は $\alpha$ を変えて, Profit-Costの点をplotしてそれぞれの $\lambda$ に対して, CP-Profit を最大化するように, $\alpha$ を選択する方法

図7はそれぞれの $\lambda$ に対して, LR と$\alpha$ をチューニングした VaR, RMPでのCP-Profit の比較

実験結果から以下の結論を得た

VaR, RMPはいずれの場合もLRよりCP-Profitで優位
純粋なProfit を考える $\lambda =0$ のケースで, VaR, RMPはそれぞれLRに対して Profitを 50.7%, 25.1%改善した。
図7の $\lambda$ - CR-Profit でLRは直線的だが, VaR とRMP は凸だったため, $\lambda$ が大きいほうが, ROIは大きくなる

9つのキャンペーン全体での全体のKPIについては以下の通り

実験結果から以下の結論を得た

提案手法は全体的にベースラインより高いProfitを示した
VaR はLRと比較して大幅にROI を改善した。
RMPは$\lambda$ によらず, Profitは安定して10%改善した。これはRMPは直接Profitを最大化する戦略であるため。一方でCPMや eCPCは高騰したため ROIは低い
提案手法は全てのケースで CTRを改善したが, これは CTR予測が不確実なものから確実なものに予算が割り振られたためと考えられる。

Bidding with Budget Constraints

それぞれの $\lambda$ に対して, $\alpha$ を図6の方法で選択した。選択したモデルは図5の赤丸のもの。

$\phi$ はvalidation setでprofitを最大化するように選択した。

以下に予算 1/2で実験した結果のKPIを示す。

実験結果から以下の結論を得た

$\lambda$ が小さいときは提案手法の方が Profit が大きい。具体的にはLRでのCTR予測値が低いキャンペーンについて特にProfitを改善した。
$\lambda = 0, 0.2$ で提案手法はともに LRより, ROIとProfit両方において優れた結果を示した。
$\lambda = 0.4$ のVaR を除いて, 提案手法はいずれも CTRを改善した
VaR はCPM, eCPC, WRいずれも低くなった, 一方RMPは CPM, eCPC, WRいずれも高くなった

オンライン検証(匿名DSP)

学習データについて

匿名のDSPにおいて, オンライン環境で提案手法を検証した。request の規模は 50B/day でCPCキャンペーンの有効なリクエストは 200M(4%), テスト用には 10CPCキャンペーンの1.5%のボリューム, つまり約3M/dayのbidを割り当てた。

トレーニング用の2016/01以前のデータは 424M imps, 532K clicks, 47.2K USD の利用が含まれていた。トレーニングデータのeCPCは0.087 USD。学習click dataは2%のnegative down samplingを行ったもの。

テストデータは全キャンペーンの平均CPC 0.54USDを入札時には指定した。

実験設定

2016/01 の7日間で以下の2つの戦略でABテストを行った。

ベースラインのLR戦略, これは AUC 88%のLRモデルと, 運用者が設定した $\phi =0.56$ の線形入札関数となる。
提案手法のVaR戦略, $\alpha$ >0 は毎日微妙に変化させる(手作業でチューニング?) $\phi$ はLRより大きく設定した。
(この $\alpha$ と $\phi$ の設定は入札価格を逆向きに調整するので, 結果的に平均入札額はbaselineに近い値)

それぞれに割り当てられたbidのボリュームは19.5M, 合計39M, 発生したimpは 3.3M, click は7.4Kだった。
VaRは $\phi$ の学習を行ったため, 予算は12%多く使用された。

結果の議論

実験結果

実験結果から以下の結論を得た

ROIは+5%, この意味で提案手法の優位性は示される
Profitは +17.5% (ただしbaselineより予算は多く投下している), リクエスト数は等しいので, 同一リクエストでROIを改善したい場合は役立つ。広告主は通常ROIに応じて予算を配分するため, 予算獲得には役立つ。
WRは大幅に低下した。これは VaRによる入札額を低下させたrisky caseが入札額を増加させた confident caseより多かったためだと思われる。
CTR は+ 64.4% と大幅に改善したため, 高品質なimpを買い付けられたと思われる。
VaRでCPMは悪化した。これは高CTRの枠を買い付けるために入札額が高くなったことが原因と思われる。

conclusion

CTRの分布推定を行い, 推定値の分散を考慮した2種の入札モデル VaR, RMP でオフライン検証, オンライン検証のそれぞれでROI, Profit, CTRが改善しうることを示した。

future work

risk aware bidding の均衡市場分析
multi-frameなDynamic Creative はポートフォリオ最適化としてみなせる(?)
広告表示によるuserの関心のupdateをmodelに組み込める(?)

RMP biddingについての補足資料https://www.dropbox.com/s/qpv82dtrvdhk4zb/supplementary.pdf?dl=0 ↩