kenju's blog

About Programming and Mathematics

読了『人工知能 Vol 32 No.4(2017年7月号)』の「アドネットワークにおける広告配信計画の最適化」

週末に以下の雑誌をKindleで購入して読んで見た。

haginoさんがこの号に寄稿したことを以下のブログポストで知り、是非読んで見たいと思ったので速攻購入。紙版はAmazon.co.jpではすでに取り扱われていなかったけど、Kindle版があってよかった。

hagino3000.blogspot.jp

非常に内容の濃い特集で、特にhaginoさんの論文は予想以上に勉強になりました。特に数理モデルを実践の場で適用する際にどのような課題にあたり、それをどのように解決するかという知見が非常にありがたかったです。

「アドネットワークにおける広告配信計画の最適化」読書メモ

Disclaimer: 以下の読書メモは自分の言葉で書き換えながらメモしているので、間違っている箇所があるかもしれない。その場合はぜひご指摘いただければ嬉しい&正確な情報については本雑誌をご参照ください

前提:多腕バンディット問題の広告配信最適化への適用

  • 最も収益性が高い広告を選択する手法としての多腕バンディット適用における実践レベルので手法の説明と課題
  • 広告配信は、報酬が何らかの確率分布によって生成されるとする確率的バンディット問題に当てはめて考えることができる
    • ex. CPC広告における収益とクリックの関係性

多腕バンディット問題の広告配信最適化適用の際の課題

数理モデルとしての多腕バンディットをそのまま広告配信最適化問題に適用できるわけではなく、実際の場では以下の課題が存在する

  • 一般的な確率的バンディット問題ではアームの数・アーム個々に設定された報酬の期待値が固定であるが、実際の広告配信システムではアームの数・報酬の期待値が常に変動する
  • 広告配信後、報酬(CT/CV)が観測できるまでにタイムラグが存在するため、アーム選択後に報酬がリアルタイムで観測できる前提のアルゴリズムはそのまま利用できない

Thompson Samplingアルゴリズムが利用しやすい

^の課題を考えると、Thompson Samplingが利用しやすい

  • 報酬の観測遅延に対する堅牢性がUCB法よりも優れている
  • 報酬の生成過程を拡張し、時刻やAudienceデータを利用できる
  • マルチスレッドや複数サーバーでの分散実行が容易
  • statelessであるためデプロイ時のリスクも低い

配信システムのアーキテクチャ

Zucks AdNetworkの簡単なバッチアーキテクチャが図として載せられていたので参考になった

  • 広告は50ms or dieの世界であり、時間のかかる予測処理はオンラインで処理しきれないので、処理に時間のかかるロジックはバッチで結果Viewを生成しておく典型的なLambda Architectureっぽい(Speed Layerの図はなかったけどおそらく)
  • データ分析システムが障害で停止したとしても、配信サーバは予測データ無しで動作するモードにfallbackさせて頑強性を確保

配信最適化

前提:AdNetworkが目指すのは、広告主の求めるCPAを満たした上での媒体社収益(eCPM)最大化

このうち、配信ロジックのコントロールできる特徴量は以下の二つ

  • 広告リクエストに対して返す広告
  • 広告のクリック単価

ポイント:

  • CVRの推定には、ベイズの定理を用いて、「クリック数nのうちk個のCVを観測した後のCVRの事後確率」を用いることで、サンプルサイズが小さい時の外れ値の発生を抑制している
  • time decay(時間経過による評価の割引き)オプションが存在する
  • すべての配信可能なキャンペーンの報酬の計算を行うコストは非現実的なので、広告枠ごとの実績eCPMに「この値よりも低いeCPMとなる広告は配信停止」という閾値を儲け(これをeCPMの信頼上限と呼ぶ)、それ以下のキャンペーンの枝刈りをする

参考文献