論文読んだメモ: Cost-sensitive Learning for Utility Optimization in Online Advertising Auctions (2017 AdKDD)

1 minute read

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$ は、アクション (クリック / コンバージョン) に対して広告主が設定する価値を表す
        • すなわち入札価格であろう
      • このメトリクスはつまり、予測が外れた場合の誤差に 入札価格の大きさ が加味されることを意味する
    • $\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}$ だけ得をする

提案手法

  • 広告配信における「効用」を損失関数 $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}$ のように調整することも論文中で言及している
  • 正則化パラメータ $\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 のメトリクスで比較する
  • オフラインの評価結果
    • 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 が高くてコンバージョンが少ないキャンペーンにおいて、良い結果が期待できる手法と考えられそう
  • オンライン
    • ROI 的に +2% の lift が得られた