KDD2018, AdKDD参加レポート

こんにちは@hagino3000です。インターネット広告配信システムの開発をしております。去年に引き続き今年も国際会議のKDDに参加してきました。本稿は私がアドテクと業務に関係する発表を聴講したレポートになります。

KDDとは

KDD 2018 | London, United Kingdom

KDDはデータマイニング分野のトップ会議です。採択論文はResearch Track PapersとApplied Data Science Track Papersに分かれており、後者は実際のアプリケーションに適用した題材が対象です。よって、アプリケーション開発現場で対面する問題をいかに解いたか、なぜその手法を利用したのかについて発表・議論される場であるのが特徴です。Facebook, Amazon, LinkedIn, Microsoft, Airbnb, Netflix, Alibaba, Google といったネット企業が多く発表しています。

Tutorial Day

1日目はTutorial Day、午前はOnline Evaluationのセッション、午後は因果推論のセッションに参加しました。

Online EvaluationのTutorialはYandexにおけるA/Bテストの彼等の失敗事例やベストプラクティス、メトリクスの選定基準に始まり、テクニカルな話では統計的検定をオンライン評価の状況設定(Sequencial Testing)に適用するための手法の紹介。途中で組織的な話になり、A/Bテストの内容と結果をチェックするエキスパートがチームに配置されておりリリース判定をしているという話が印象的でした。質疑になると去年のA/B Test Tutorialを担当したMicrosoft ExP Teamのメンバーが存在感を発揮していたのも面白かったです。

因果推論のTutorialは超満員で参加者の注目度の高さが伺えました。こちらは統計的因果推論の基礎と準実験で使う手法を中心に解説があり最後にDoWhyを開発した話がありました。私の今の業務ではRCT一択で準実験をやる事が無いのですが、いつか役に立ちそうです。

2018 AdKDD & TargetAd

2日目のWorkshop Dayはインターネット広告がテーマのAdKDDに参加すると決めていました。メディア・SSP・DSP・データプロバイダ・アカデミアと様々な立場での研究発表と招待講演が丸一日あります。

adkdd-targetad.wixsite.com

個人的に一番だったのはVahab Mirrokni氏が登壇した点です。私が彼の論文を読んでいた最中というのが大きいですが、Online Ad Allocationの歴史と今の潮流が参考になったのとRTBのオークションメカニズムを改良するとSocial Welfareが増やせる[1]という話は夢があって素晴らしいと感じました。メカニズムデザインは不勉強で理解しきれない所が多くありましたが、価格メニューや業務設計に役立つので注目しています。

f:id:hagino_3000:20181029163116j:plain:w550
Market Algorithms Research for Display & Search Ads

DSPにおけるRTB入札最適化の発表は予算制約付き繰り返しオークションで1st Price Auctionと2nd Price Auctionが混在する設定なのが新しかったです。最適化問題を主問題と双対問題で交互に解く[2]のは入札最適化にしろ広告配信選択にしろ頻出パターンなので習得する必要があるなと。

他にも2nd Price AuctionのReserve Price設定手法の歴史、AUCをミニバッチで計算して省コスト化する手法を開発して利用している話、Facebookにおける広告キャンペーンの効果測定など興味深いネタが多く非常にエキサイティングでした。

本会議

本会議は主にApplied Data Science Trackを聴講しました。講演はマーケットデザイン研究の実社会適用[3]や予測による差別[4]といった、データマイニングが実社会に与える影響。産業界からはAmazon, Criteo, LinkedIn各社の研究トピックと、組織でいかにインパクトのある仕事を成すかという話がありました。

ここではネット広告関連で面白かった発表を2つ紹介します。

Audience Size Forecasting: Fast and Smart Budget Planning for Media Buyers

KDD 2018 | Audience Size Forecasting: Fast and Smart Budget Planning for Media Buyers

DSPの広告運用者向けに広告キャンペーンの配信セグメント設定と入札金額設定からインプレッションボリュームを推定する機能を作った話です。予算を考慮して適切なサイズの配信セグメントを作るのに利用しているそうです。

論文はビジネス要件が丁寧に書いてあり、配信セグメントをどのように作っているか、なぜこの機能が必要なのか詳細に記されているためDSPの運用者にとっては非常に参考になるでしょう。 制約は著者らのDSPの入札リクエストの規模が1,000億/Dayあるため、ナイーブにログから条件にマッチする入札リクエストをカウントするのでは実用に耐えない点。これを解決するために集合の圧縮表現としてMin-Hashを使って条件にマッチするデバイスの数の推定値を得たり、入札金額に対する勝率を関数フィッティングで求めたりしている。入力は次の通り

  • 配信セグメント設定
    • EnvType (Web or App or Both)
    • Device Type (desktop, smartphone, tablet, or any combination of these)
    • Ad Type (Display or Video)
    • Geographical Area
    • Viewability (Top X%を指定)
    • ターゲティング端末リスト、除外端末リスト
  • 入札金額設定
    • price for the average or maximum bid

「User Feedback」の節に実現した機能の利用者の感想があるのもApplied Scienceならでは。一つの機能を実現するのに、回帰・集合の圧縮・関数フィッティングと様々なテクニックの合わせ技になっている所がエンジニア的に面白かったです。

Optimization of a SSP’s Header Bidding Strategy using Thompson Sampling

KDD 2018 | Optimization of a SSP’s Header Bidding Strategy using Thompson Sampling

SSPがヘッダー入札の収益を最大化するための方策。SSP同士のオークションの入札金額をバンディットアルゴリズムで求めています。

f:id:hagino_3000:20181029163654p:plain

オークションに勝利した時のSSPの収益はDSPへの請求と媒体への支払いの差額となるため、期待収益はこれとオークションの勝率の積で表わされます。入札金額に対する勝率を求めるには他社の最高入札金額の分布が必要となりますが、この分布のパラメータθが学習できれば収益を最大化する入札金額が求まるというアプローチです。実装には対数正規分布を採用しています。 ここでパラメータθを学習するための配信(探索)と収益を得るための配信(活用)のバランスが必要となりますが、Thompson Samplingを利用して実現しています。パラメータθの事後分布の更新は非常に計算コストが高いためMCMCのオンライン版であるParticle Filterを採用したとあります。 実験データの作り方も一工夫しています。ヘッダー入札(1st Price Auction)において買い手は他者の入札金額が得られませんが、特定のパブリッシャで通常のRTBを行なった時のDSP各社の入札ログを2群に分けて仮想的なヘッダー入札の状況を作って実験用の最高入札金額を得ています。著者がSSPの人間だから可能な技ですね。

バンディットアルゴリズム適用事例として上手いなと思いました。オークションで使える対数正規分布に限らず任意の分布に一般化した話が導入になっている点も好きです、Thompson Samplingで上手くやりましたに留まらない所が。 しかしDSPからすると最終的な入札金額がSSPに操作されるので嬉しくは無いでしょう。そこに違和感を感じたのは自分だけでは無く、質疑でも「そんな契約をしているの?」というやりとりがありました。また、SSP同士のオークションが2nd Priceで、DSP同士のオークションが1st Priceの方がオークションメカニズム的に優れている気はするので、何故現状がこうなっているかも調べてみようかと。

感想

去年と比較すると1st Price Auctionを扱う発表が増えたのが印象に残りました。入札ロジックで対応するDSPの話があったかと思えば、ヘッダー入札は「入札する価値なし」としてフィルタで落しているDSPもあるのが興味深かったです。価格調整やマッチングになるとミクロ経済学・ゲーム理論のテクニックが登場するため、アプリケーション開発者でも習得すると便利なのがわかります。

学ぶ事が多く気になっている研究者に直接質問できたりと嬉しい事もありました。惜しむらくは自分の発表が無い事ですが、Applied Data Science Trackは新規性のある手法で無くともインパクトのある適用事例であれば採択されているので狙っていきたいです。

脚注

[1] Mirrokni, Vahab S., et al. "Dynamic Auctions with Bank Accounts." IJCAI. 2016.

[2] Lobos, Alfonso, et al. "Optimal Bidding, Allocation and Budget Spending for a Demand Side Platform Under Many Auction Types." arXiv preprint arXiv:1805.11645 (2018).

[3] https://www.kdd.org/kdd2018/keynotes/view/alvin-e.-roth

[4] https://hagino3000.blogspot.com/2018/10/kddandcausalinference.html に少し書きました