論文読んだメモ: Cost-sensitive Learning for Utility Optimization in Online Advertising Auctions (2017 AdKDD)
KDD 2017 のワークショップ、2017 AdKDD & TargetAd の論文がいくつか事前に公開されていたので、読んだメモを残しておきます。
今回読んだのは Criteo 社の Cost-sensitive Learning for Utility Optimization in Online Advertising Auctions です (勘違い・読み間違いなどあるかもしれませんがご容赦ください)。
概要
- CTR / CVR 予測を用いた広告配信の費用的なパフォーマンスを改善する話
- 予測精度を改善する話 ではない
- 予測モデルの精度は log loss で評価する一方で、広告配信のパフォーマンスは (経済学でいうところの)「効用 (Utility)」で評価していて、この評価メトリクスの観点でギャップが存在している
- この 「効用」が良くなるように予測モデルを学習したい、というのがこの論文の狙いとなる
メトリクスの話
- 予測モデルの精度は、log loss で評価している
- (以下の式は、L2 正則化付きロジスティック回帰の目的関数)
- $\underset{w}{\arg\min} \sum_{i=1}^N \log(1 + \exp(-y_i \boldsymbol{w} \cdot \boldsymbol{x}_i)) + \frac{\lambda}{2} ||\boldsymbol{w}||^2$
- 広告配信の「効用」を表すメトリクスは二つ考えられる
- $\boldsymbol{MSEW} = \frac{1}{N} \sum_i((y_i - p(\boldsymbol{x}_i)) \cdot v_i)^2$
- $v_i$ は、アクション (クリック / コンバージョン) に対して広告主が設定する価値を表す
- すなわち入札価格であろう
- このメトリクスはつまり、予測が外れた場合の誤差に 入札価格の大きさ が加味されることを意味する
- $v_i$ は、アクション (クリック / コンバージョン) に対して広告主が設定する価値を表す
- $\boldsymbol{Utility} = \sum_i \int_0^{p(\boldsymbol{x}_i) v_i} (y_i \cdot v_i - \tilde{c}) \Pr(\tilde{c}|c_i) d \tilde{c}$
- $c_i$ は実際に観測されたセカンドプライスを表し、$\Pr(\tilde{c}|c_i)$ は生じうるセカンドプライス $\tilde{c}$ の確率を表す
- $\Pr(\tilde{c}|c_i)$ の確率分布はガンマ分布 $Gamma(\beta c + 1, \beta)$ を仮定している
- $y_i \cdot v_i - \tilde{c}$ の部分は利得 (payoff) を表す
- 予測が外れれば ($y_i = 0$ なら) $\tilde{c}$ の分だけ無駄なコストが生じ、また予測が当たれば $v_i - \tilde{c}$ だけ得をする
- $c_i$ は実際に観測されたセカンドプライスを表し、$\Pr(\tilde{c}|c_i)$ は生じうるセカンドプライス $\tilde{c}$ の確率を表す
- $\boldsymbol{MSEW} = \frac{1}{N} \sum_i((y_i - p(\boldsymbol{x}_i)) \cdot v_i)^2$
提案手法
- 広告配信における「効用」を損失関数 $Utility \ loss$ にして学習できればそれに越したことはないが、これは非凸らしく、難しい
- 代わりに、Weighted log loss を提案している
- $WNLL = \sum_{i=1}^N v_i \log(1 + \exp(-y_i \boldsymbol{w} \cdot \boldsymbol{x}_i)) + \frac{\lambda}{2} ||\boldsymbol{w}||^2$
- 入札価格 $v_i$ で重み付けしただけっぽい
- 単に入札価格を乗じるだけでは、その値が大きな場合に過学習を引き起こす要因になりうるので、実際には上限値を設けたり $v_i^\frac{1}{2}$ もしくは $v_i^\frac{1}{4}$ のように調整することも論文中で言及している
- 入札価格 $v_i$ で重み付けしただけっぽい
- $WNLL = \sum_{i=1}^N v_i \log(1 + \exp(-y_i \boldsymbol{w} \cdot \boldsymbol{x}_i)) + \frac{\lambda}{2} ||\boldsymbol{w}||^2$
- 正則化パラメータ $\lambda$ は次のように設定する
- $\lambda_{WNLL} = \lambda_{NLL} \times \frac{\sum_i v_i}{N}$
評価
- オフラインでの評価方法
- Modeling Delayed Feedback in Display Advertising の評価で利用したデータセットと同じものを利用する
- 同データセットには入札価格や CPA の情報がないので、入札価格はキャンペーンによらず一律 $1 とし、また CPA はキャンペーンごとの実績 CVR (post-click CR) の逆数とする
- 通常の log loss (NLL) と weighted log loss (WNLL) とを、MSEW, Utility のメトリクスで比較する
- Modeling Delayed Feedback in Display Advertising の評価で利用したデータセットと同じものを利用する
- オフラインの評価結果
- Table3:
- 重みは $v_i^\frac{1}{2}$ とする
- (1) 全キャンペーンの結果、(2) CPA が高いキャンペーン (CPA > 10 なので、post-click CR が < 10%) に絞った結果、また (3) CPA が高くて sales 件数 (すなわちコンバージョン数、かな？) が低いキャンペーンに絞った結果ごとに、NLL と WNLL それぞれの MSEW, Utility を比較している
- いずれも改善しており、特に改善幅は (3) > (2) > (1) となっている
- CPA が高くてコンバージョンが少ないキャンペーンにおいて、良い結果が期待できる手法と考えられそう
- Table3:
- オンライン
- ROI 的に +2% の lift が得られた