要約の要約
Zhang, Weinan, and Jun Wang. 2015. “Statistical Arbitrage Mining for Display Advertising.” In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’15, 1465–74. New York, New York, USA: ACM Press. DOI: 10.1145/2783258.2783269. arXiv: 1506.03837 について説明します。
この論文では、 statistical arbitrage mining (SAM) という方法を提案しています。数理ファイナンス (金融工学) の現代ポートフォリオ理論 (MPT) 的な、裁定取引のアイディアを取り入れた最適化問題です。
[論文要約] Web広告入札価格の最適化について: "Optimal Real-Time Bidding for Display Advertising" で紹介した論文と同じ著者が関わっており、数学テクニックの使い方も似ています。そこで、以降の説明ではこの論文を [ZSJ2014] という略称で参照します。
問題設定
$M$ 個の、CPAを設定したキャンペーン、 CV に対する利得$r_i$、$T$期間中、メタ入札者は入札リクエストを受け続け、それに対して期間中の期待総裁定純利益 (total arbitrage net profit) が最大化されるように、どのキャンペーンを、いくらで入札するか、を決めます。よって、入札価格の最適化というよりは、複数のキャンペーンを運用する広告主にとってのコストベネフィットをどう最適化するか、という問題に対する答えを提案しています。
次のように記号を決めておきます。
* $M$: キャンペーンの数
* $T$: キャンペーンの期間。言い換えると、$T$ 期間中に $M$ 個のキャンペーンを運用するという設定。また、各期でリクエストが発生するので、実際にはリクエスト発生回数と言い換えたほうが良いでしょう。
* $r_i$: キャンペーン $i$ で、CVが1回発生したときの利得。ここでは CPA などを想定します。
* $\theta(x, i)$: $i$ でオークションに勝った場合の予測KPI。ここでは予測 CVR (pCVR) とします。
* $b(\theta, r)$: 入札価格関数
* $w(b)$: 勝率関数
* $v_i$: メタ入札者によって、全てのキャンペーン中から $i$ の選ばれる確率。 よって、すべての $v_i$ は$0\leq v_i\leq 1$ の範囲の値で、かつ合計が1となります。
メタ入札者の総裁定純利益 $R$ は以下のような式になります。 $$R(v, b(\theta, r))= \sum_{t=1}^{T} \sum_{i=1}^M \left(\theta(x_t,i)-b(\theta(x_t, i), r_i)\right)\cdot w\left(b(\theta(x_t, i), r_i) \right)v_i$$
$\theta \times r_i$ は期待利得、 $b$ は期待費用なので、$(\theta r_i - b)$ は勝利したオークション1件あたりの純利益。 $w(b)\times v_i$ はメタ入札者がキャンペーン $i$ を選び、かつオークションに勝つ確率なので、結局 $R$ は純利益の合計期待値を表します。よって、費用の上限は、
$$
C(v, b(\theta, r)) = \sum_{t=2}^T\sum_{i=2}^M b(\theta(x_t, i), r_i)w(b(\theta(x_t, i), r_i))v_i
$$
さらに $p_x$ で期待値を取ります:
$$\begin{align}
\mathrm{E}_x\left[R(v,b(\theta,r))\right]&=T\int_{x}\sum_{i=1}^{M}\left(\theta(x,i)r_{i}-b(\theta(x,i),r_{i})\right)w\left(b(\theta(x,i),r_{i})\right)v_{i}p_{x}(x)dx\\
&= T\sum_{i=1}^M v_i \int_\theta \left( \theta r_i - b(\theta, r_i) \right) w(b(\theta, r_i ))p_{\theta}^i(\theta)d\theta
\end{align}$$
この変形は、 $p_\theta^i(\theta(x,i))=p_x(x)/\left\vert\vert\nabla \theta(x, i)\right\vert\vert$ を根拠にしています。これは [ZSJ2014] と同じ理屈です。同じように、総費用の期待値も、以下のように表せます。
$$\begin{align}
\mathrm{E}\left[C(v,b(\theta,r))\right]= T\sum_{i=1}^{M}v_{i}\int_{\theta}b(\theta,r_{i})w(b(\theta,r_{i}))p_{\theta}^{i}(\theta)d\theta
\end{align}$$
この期待利益を、期待予算制約のもとで最大化することになりますが、実際には不確実性によるリスクが存在します。よって、リスクを収益の分散 $\mathrm{V}\left[ R \right]$ として、取れるリスクに上限値 $h$ を設けます。以上から、問題は以下のような制約付き最大化問題になります。
$$\begin{align}
b(), v_i() &= \arg\max_{b(), v_i} \mathrm{E}\left[R(v, b(\theta, r))\right]\\
\text{s. t. } & \mathrm{E}\left[C\right] \leq B,\\
& \mathrm{V}\left[R\right] \leq h,\\
& 0 \leq v_i\leq 1,\\
& \sum_iv_i = 1
\end{align}$$
計算方法
$v_i$ は未知の確率なので、 EMアルゴリズムを応用して計算することになります。EM アルゴリズムといえば、
1. E ステップでは、 2.の暫定解で $b(\theta, r)$ を固定し、上記の最大化問題をキャンペーン選択 $v_i$ について解く
2. M ステップでは、 1.の暫定解で $v_i$ を固定し、入札価格先着 $b(\theta, r)$ について解く
を2つの解がそれぞれ収束するまで繰り返します。ただし、「EM風」と表現しているように、よくあるEMアルゴリズムよりも手順が複雑です。
(訳注: 単純に期待収益を最適化するだけならば、予算制約のもとでの最大化問題として扱えるので、EMアルゴリズムは不要です。しかし、今回は最適ポートフォリオ理論の考えを応用し、期待値の最大化だけでなく、リスクも抑えるべきだ、と考えているようです。)
入札価格戦略の最適化
まず、 M ステップに対応する、入札価格戦略の最適化について説明します。 $v_i$ は固定されているので、予算制約式だけで以下のラグランジュ関数を作り、解きます。
$$\begin{align}
\mathcal{L}(b(\theta, r_i), \lambda) & = \mathrm{E}\left[R\right] - \lambda(\mathrm{E}\left[C\right] - B) \\
& = T\sum_{i=1}^Mv_i\int_\theta \left(\theta r_i - (\lambda + 1) b(\theta, r_i)\right)w(b(\theta, r_i))p_\theta^i(\theta) d\theta + \lambda B
\end{align}$$
その最適化条件は、以下のようになります。
$$
\left(\frac{\theta r_{i}}{1+\lambda}-b(\theta,r_{i})\right)\frac{\partial w(b(\theta,r_{i}))}{\partial b(\theta,r_{i})}= w(b(\theta,r_{i}))
$$
ここから、入札価格戦略を導き出します。単純な例として、もし仮に入札価格と勝率が比例するのならば、一様市場価格の理論1に当てはめれば、
$$
w(b(\theta,r)) = \frac{b(\theta, r)}{l}
$$
と書けます。これは、広告の市場価格が $[0,1]$ の範囲の範囲で一様分布になっていると仮定しています。この場合の市場価格とはオークションでの自分以外の入札者のうち最高入札額を意味します。よって、 $l$ 入札すれば確実にオークション勝利できるということになります。よって、この仮定ならば勝率は上記のようになります。
ここから最適入札戦略は
$$
b(\theta, r) = \sqrt{\frac{Bl}{T\phi}\theta}
$$
となります。$\phi:=\int_\theta\theta^2p_\theta(\theta)d\theta$ です。 よって、このケースでは入札価格は $r$ に依存しないことがわかります。 $\phi$ は $p_\theta$ の経験分布から計算できます。
[ZSJ2014] でも提案されたように、勝率関数を双曲線関数にすると、以下のようになります。
$$
w(b(\theta, r)) = \int_0^{b(\theta, r)} p_z(z)dz = \frac{b(\theta, r)}{b(\theta, r)+l}
$$
で、ここから
$$
b(\theta, r) = \sqrt{\frac{rl\theta}{1+\lambda}+l^2}-l
$$
となります。これは、市場価格の分布がロングテイルになっていると想定した場合の解です。
キャンペーン選択の最適化
次に、Eステップに対応する $v_i$ の最適化計算について考えます。ここまでで求めた $b(\theta, r)$ から、ポートフォリオ最適化理論のように、利益とコストの比率をもとに考えます。これをポートフォリオマージンといいます。今、キャンペーン $i$ に全額投資し、それ以外の枠には一切投資しない場合を考えます。つまり、$v_i=1, v_j=0, j\neq i$です。このときの利益とコストをそれぞれ $R_i(v_{i=1},b), C_i(v_{i=1},b)$ と表すと、ポートフォリオマージンを
$$\gamma_i:=R_i(v_{i=1},b)/C_i(v_{i=1},b)$$
と表せます。このとき、$\gamma_i$ の期待値と分散をそれぞれ $\mu_i(b), \sigma_i^2(b)$ と表します。つまり、以下のように表されます。
$$\begin{align}
\mu_i(b)&:=\mathrm{E}\left[\gamma_i\right] = \mathrm{E}\left[\frac{R_i(v_{i=1}, b)}{C_i(v_{i=1}, b)}\right]\\
\sigma_i^2(b)&:=\mathrm{V}(\gamma_i)=\mathrm{E}\left[\frac{R_i^2}{C_i^2}\right] - \mathrm{E}\left[\frac{R_i}{C_i}\right]^2
\end{align}$$
これを全キャンペーンについて計算します。これらは解析的に求めるには複雑なので、モンテカルロ法で計算することになります。
全キャンペーンについて計算すれば、期待値ベクトルと共分散行列を
$$\begin{align}
\boldsymbol{\mu}(b)&:=\left[\begin{matrix}\mu_{1}(b)\end{matrix}\right]\\
\boldsymbol{\Sigma}(b) &:={\sigma_{i,j}(b)}_{M\times M}
\end{align}$$
と表せます。共分散行列の対角成分は $\sigma_i^2(b)$ ですが、キャンペーンどうしは独立とは限らないため、非対角成分は、相関要因パラメータ $\beta_{i,j}\in [-1, 1]$ を使って $\beta_i,j\sigma_i(b)\sigma_j(b)$ と表します。この計算は、ポートフォリオマージンの時系列データを用意して計算する必要があります。
以上から、$\boldsymbol{v}_{i}$ に対する期待利益は $\boldsymbol{v}^\top \boldsymbol{\mu}(b)$、リスクは $\boldsymbol{v}^\top \boldsymbol{\Sigma}(b)\boldsymbol{v}$ となります。これをラグランジュ関数で表すと、以下のようになります。$\alpha$ はラグランジュ乗数ですが、数理ファイナンス的にはリスク回避度とも解釈できます。
$$\begin{align}
\max_\boldsymbol{v} & \boldsymbol{v}^\top \boldsymbol{\mu}(b) - \alpha \boldsymbol{v}^\top \boldsymbol{\Sigma}(b)\boldsymbol{v}\\
\text{s. t. } & \boldsymbol{v}^\top \boldsymbol{1} = 1,\\
& 0\leq v_i \leq 1
\end{align}$$
(訳注: つまり、この論文で提案している方法を短くまとめると、(1)予算制約とリスク制約のもとで、複数のキャンペーン全体の期待利益を最大化する最適入札価格関数を求め、(2) (1) の結果からシミュレートした各キャンペーンの期待リターンとリスクをもとに、リスクを抑えた利益最大化問題を解く、という2工程をパラメータが収束するまで繰り返す、というものになります。)
この方法の時間計算量は、Eステップの MCMC 計算で $O(MNT)$, 共分散行列の計算には $O(M^2NT)$ かかります。一方で M ステップは基本的な最適化計算のため、実際のデータの値に依存するものの、比較的計算量が少ないです。
実験
[ZSJ2014] と同様に、この論文でも中国の大手 DSP, iPinYou のデータと、 BigTree のデータで実験を行っています。今回提案した SAM に対して、「入札価格が常に一定」「ランダム入札」「CVRに比例するように入札する (線形入札戦略)」「CPAxCVR (truth-telling戦略)」などの他の戦略と比較しつつ、パフォーマンスを測定しています。単一のキャンペーンの場合と、複数のキャンペーンの場合の両方で実験したところ、いずれでも今回提案した方法は良い結果を出しています。今回の提案方法以外では truth-telling 戦略は比較的良いパフォーマンスですが、予算制約を考慮していないため、予算が少なくなるほどパフォーマンスが低下する傾向があります。[ZSJ2014]の方法も比較対象に含めており、単一のキャンペーンでは、今回の方法と似たパフォーマンスを出しています。
また、 SAM をさらに調整した方法とも比較しています (これは詳しく調べるのに時間がかかりそうなので確認してません)。
複数のキャンペーンを扱う実験では、今回の方法と、線形入札と[ZSJ2014]とを比較しています。後二者は単一キャンペーンだけを最適化する問題なので、ポートフォリオ選択部分は uniform, greedy, portfolio の3種類の方法で比較しています。細かい説明がありませんが、たぶん、uniform は一様乱数でキャンペーンのポートフォリオを選択する方法で、 greedy は greedy アルゴリズムで期待利得を最大化したポートフォリオを選択する方法で, portfolio は今回提案した方法だと思います。
感想
- 複数のキャンペーンで実験した、といっても、6つ程度です。より多くのキャンペーンを同時に扱う場合の計算量は考慮されていません。
- 数理ファイナンスのアイディアを応用すれば、入札価格の最適化問題を考えやすくなるかもしれません。
- ポートフォリオ最適化は、一定の期待リターンのもとでのリスク最小化問題として定式化されていますが、この論文では逆に、一定のリスクのもとでのリターン最大化問題として定義されているのが気になります。両者はいわゆる双対関係になるんでしょうか?