[論文要約] Web広告入札価格の最適化について: "Optimal Real-Time Bidding for Display Advertising"

最近読んだ以下の論文の内容を要約して記録しておきます。

• Zhang, Weinan, Shuai Yuan, and Jun Wang. 2014. “Optimal Real-Time Bidding for Display Advertising.” In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’14, 1077–86. New York, New York, USA: ACM Press. DOI: 10.1145/2623330.2623633.

要約の要約

オンライン広告配信のリアルタイム入札システム (RTB) について、最適な入札価格を数理最適化で決める方法を提案しています。入札価格とオークションの勝敗関係のわかるログデータと、インプレッションごとの予測CTR (pCTR) をもとに、ある予測CTRに対して最適な入札価格の値を決める関数を導出する方法です。

問題設定

この論文では、最適な入札戦略を、あるキャンペーン期間中の予算制約内での期待クリック数の最大化するような入札価格決定ルールとして定義しています。つまり Click-Through Rate (CTR) を KPI として設定した、Cost-per-Mille (CPM) 型の広告プラットフォームを想定していますが、著者らはCPAなど他の方式でも応用できるとしています。
問題に登場する変数・関数は以下のとおりです。

• $x$: 広告リクエスト単位の特徴量 (ユーザのデモグラ属性などです)
• $p_x(x)$: $x$ の確率です。x はリクエストの特徴量なので、どのような性質の広告枠が現れるかの確率分布と解釈できます。
• $\theta(x)$: $x$ に対する KPI。ここでは、リクエストごとの予測CTR (pCTR) とします。
• $p_\theta(\theta)$: $\theta$ の確率分布です。
• $b(\theta(x),x)$: $\theta, x$ に対する入札戦略関数 (bid strategy)。pCTR と広告リクエストの特徴量に対する入札価格の関数です。最終目的はこの関数を決めることです。
• $w(b(\theta(x), x), x)$: 入札額 $b()$, 特徴量 $x$ に対する勝率を表す関数 (win-rate function)。
• $N_T$: キャンペーン期間 $T$ の間にあると予想される広告枠オークションの回数。 $T$ はこれ以降の式では直接扱いません。
• $B$: キャンペーンの予算上限。キャンペーン期間を通して総費用がこの額におさまるようにします。

以上から、目的関数を以下のように定義します。
$$F[b] = N_T\int_x \theta(x)w(b(\theta(x), x), x)p_x(x)dx$$
これは、$\theta(\cdots)\times w(\cdots)$, つまり、オークションごとの予測クリック率を $x$ の確率で積分しているので、$F[b] =N_T \mathrm{E}_x[\theta w]$, つまりキャンペーン中の期待クリック数ということになります。この $F[b]$ が最大となるような $b()$ を求めることになります。

さらに、入札価格と勝率の積を、やはり $p_x(x)$ で積分することで、期中の消費予算の期待値になります。よって、予算制約を以下の式で表せます。
$$N_T \int_x b(\theta(x), x)w(b(\theta(x), x), x)p_x(x)dx \leq B$$

以上から、式は以下のようになります。
$$\begin{align}
b(\cdots) &= \arg\max_{b()} N_T\int_x \theta(x)w(b(\theta(x), x), x)p_x(x)dx\
\text{s. t. } & N_T \int_x b(\theta(x), x)w(b(\theta(x), x), x)p_x(x)dx \leq B
\end{align}$$

解き方

しかし、$x$ はふつう、次元の大きなベクトルなので、多変量の分布の積分を計算することになります。これのような計算は一般に難しいです。そこで、いくつかの仮定をおいて、式を簡単にします。

1. 入札価格は CTR にのみ依存する と仮定します。これにより、$$b(\theta(x), x):=b(\theta(x))$$ となります。
2. 特徴量 $x$ は勝率 $w$ に対して, 入札関数 $b()$ を通してのみ影響する と仮定します。これによって、$$w(b(\theta(x), x), x) = w(b(\theta(x)))$$ となります。
3. pCTR $\theta$ の確率と $x$ にははっきりとした関係があるため、以下のように表せるとします。$$p_\theta(\theta(x)):=\frac{p_x(x)}{\left\Vert \nabla\theta(x)\right\Vert }$$

以上により、当初の問題は、以下のように書き換えられます。
$$\begin{align}
b(\cdots) & = \arg\max_{b()} N_T \int_\theta \theta w(b(\theta))p_\theta(\theta)d\theta \
\text{s. t. } & N_T \int_\theta b(\theta)w(b(\theta))p_\theta(\theta)d\theta \leq B
\end{align}$$
よって、積分変数がベクトルからスカラである $\theta$ になりました。この式からラグランジュ関数を作り、変分法で解くことで、$b$ が最適となる条件式 (いわゆるオイラー=ラグランジュ方程式) を得られます。 ここでの $\lambda$ はラグランジュ乗数です。
$$\begin{align}
\theta p_{\theta}(\theta)\frac{\partial w(b(\theta))}{\partial b(\theta)}-\lambda p_{\theta}(\theta)\left[w(b(\theta))+b(\theta)\frac{\partial w(b(\theta))}{\partial b(\theta)}\right]=&0,\
\lambda w(b(\theta))-(\theta-\lambda b(\theta))\frac{\partial w(b(\theta))}{\partial b(\theta)}=&0
\end{align}$$

入札価格の求め方

この方程式は $b(), w(), \theta$ の関係式なので、 $w(), \theta$ がなければ最適入札価格 $b$ もわかりません。そこで、実際のログデータから 勝率関数 $w(\theta)$ の形を確認する必要があります。著者らは中国の大手 DSP, iPinYou のデータを利用しています¹。

データを確認したところ、入札価格の増加に対して勝率が単調増加し、かつ傾きが緩くなっていく傾向がありました。そこで、可能性の1つとして以下のような双曲線関数を提案しています。
$$w(b(\theta)) = \frac{b(\theta)}{c+b(\theta)}$$
$c$ はパラメータで、実際のデータに当てはめて調整します。このとき、入札戦略は
$$\begin{align}
b(\theta) =& \sqrt{\frac{c}{\lambda}\theta+c^{2}-c}
\end{align}$$
となります。

元の論文からの転載になりますが、これらの関数の形は以下のようになります(左:勝率関数, 右:入札価格関数)。

$\theta$ については、もはや問題から $\theta$ を削除したため、外部から代入することになります。機械学習による予測値でも、単純平均をとったものでも与えることができます (もちろん、精度が良い pCTR のほうが望ましいです)。

ラグランジュ乗数 $\lambda$ については、$b(\theta, \lambda)$ と予算制約式から求められますが、必ずしも解析的に求められるとは限りません。しかし、通常は $\lambda$ の減少は制約式の積分部分の増大につながるため、$\lambda$ が減少すると常に $B/N_T$ が増大します。この性質を考慮して、手動で調整することができます。

補足・感想

• pCTR をどうやって求めればいいかについては明記されていませんが、CTR予測モデルについては他にいろいろな研究があるため、そちらを参考にすればいいと思います。
• 期間中のオークション発生回数である $N_T$ も、何らかの方法で予測することが必要です。
• 勝率関数について、 $w(b(\theta(x)), x) = w(b(\theta))$ という仮定をおいています。広告枠の特徴量に関係なく、一律で同じ勝率カーブになるという仮定は、少々無理があるのではないか、という疑問がありますが、著者らのデータでは箱ひげ図を掲載した上で「入札価格に比べると、他の特徴量と勝率の関係はずっと弱い」としています。

1. データの詳細は、以下の文献で説明されています。 Zhang, Weinan, Shuai Yuan, and Jun Wang. 2014. “Real-Time Bidding Benchmarking with IPinYou Dataset.” arXiv: abs/1407.7073. ↩