アドテクコンペ準優勝しました

9/9~9/11の3日間、サイバーエージェントさんのコンペティションインターンである「アドテクコンペ」に参加してきました。

アドテクとは普段疎遠な生活をしているのですが、社員の黒崎さんにこうゆうのあるから参加してみない?と誘われたのがきっかけで申し込んだところ、サイバーエージェントインターンの中で最も倍率が高かったらしかったのですが無事審査を通過することができアドテクコンペインターンに参加することになりました。

インターン内容をざっくりと説明すると、3~4人1チームで3日間でDemand Side Platform(以下DSP)というものを開発し、実際に最終日に4時間かけてRTBで利益率や予算消化率、プレゼンテーション内容などを競う内容でした。

コンペティションの結果は準優勝&アドテクコンペ史上初らしい完走賞をもらえて嬉しかったです。(1位と1点差だったのですごく悔しい)

どんなものを開発したのかインターンを振り返りながら紹介していこうと思います。

チームメンバー構成

チームメンバーは、サイバーエージェントさんの方で組んだ形で、インターン初日に初顔合わせでした。

メンバーは、

  • 東大 松尾研M1の方
  • 京大 吉川・馬研M1の方
  • 東北大 乾・岡崎研M1の方

という構成で、チームCとしてコンペに参加しました。

(ここだけの話顔をあわせるまで学歴的に潰されそうですごい怖かったですww)

アドテクコンペ

アドテクとは?

まず、アドテクとはアドテクノロジーの略で、広告を出したい人がより広告効果の高い場所に広告を出したり、広告配信や広告枠の売買のシステム効率化を図り、利益を高めるなどを目的とした技術です。

基礎知識については、サイバーエージェントさんがすごくわかりやすい資料を書いてくれているので、こちらを参考にしてください。

日本一やさしいアドテク教室 | 株式会社サイバーエージェント

SSPDSP

今回は、まずとあるユーザーがウェブサイトAにアクセスした時、Aの広告枠になんの広告を出すかを決めるオークションを開催するSSP(Supply−Side Platform)サーバーを運営が用意していました。

僕ら参加者は、以下のような動作をするDSPを開発しました。

  1. SSPから、オークションに関する様々な情報が入っているBidRequestを受け取る。
  2. 事前に渡された学習データから作成した学習モデルによって最も適切な広告主を決め、オークションに入札(適切な広告主がいなかった場合は入札を見送り)する。
  3. オークションに勝った場合、Win noticeという落札金額とその広告がユーザーによってクリックされたかどうかを知らせるリクエストを受け取る。
  4. クリックされたらCPC分広告主の予算から減らし、予算管理を行う。(140%を超過すると失格)

また、今回はSSPからのBidRequestのresponse受付が100ms以内で、それを2000QPS捌く必要があり、スケールを考えないといけないようになっていました。

開発したDSP詳細

全体構成

まず、今大会はサイバーエージェントさんがGoogleGCPを提供してくださり、GCPを良識のある範囲内で自由に使用することができました。Bitcoinは掘ってません。

APIサーバーはGCPロードバランサーを使用させていただき、最終的に以下のような構成になりました。

f:id:palloc:20160912170812p:plain

DBサーバーは、以下のようになりました。

f:id:palloc:20160912171003p:plain

2000QPSという量のBidRequestを捌き、予算管理をするにはディスクを高速化する必要があったため、GCPのNVMe(爆速ローカルSSD)を今回は利用しました。

API/予測モデルに通す処理をするサーバー

APIに関しては、今回は軽量さを重視&せっかくなのでほとんど触ったことのないものにチャレンジしようということで、pythonフレームワーク「tornado」を使用しました。

API自体はごく普通のもので、すべてのログを取っているのとCPUを使い切るためコア数分forkしているくらいです。

予測モデルはpythonで別ファイルにて関数として定義し、importして使用しています。

予算管理

予算管理が今回は一番のボトルネックで、Redisでは1台構成で捌ききれず、複数台構成が必須でした。

そこで、チャレンジしたくない?ということで誰も触ったことがなかったのですがLedisよりもはるかに高速なKVS「Aerospike」を使用させていただきました。

ディスクが爆速なため、Aerospikeの性能を最大限引き出すことができ、以下のように2000QPS環境下で愚直に毎回全データを問い合わせる処理でも安定していました。

f:id:palloc:20160912173810p:plain

また、常に予算を人間の目で監視できるように予算監視ツールをチームメイトが作ってくださってシミュレーションに基づく分析が容易になるなどすごく助かりました。

f:id:palloc:20160912180958p:plain

動作テスト

APIとAerospikeは2日目の昼前後には動作する状態だったため、動作テストを無限に繰り返しました。

予算管理、予算が全て尽きた後エラーを起こさないか、NULLデータが来た際に異常を起こさないか、4時間エラーを起こさず走らせられるか、1台落ちても動作し続けるか、復旧後にロードバランサーが正常に動作するかなどなど。。

また、floor price以下で入札していないか、各広告主のNGリストにいるサイトに入札していないかなどのチェックもあり、とにかく作業内容が多かったです。

テスト中にバグが見つかって修正して…を夜中ずっとやっていて、この作業がコンペ中一番つらかったですw

オークション戦略

CTR(クリックされる確率) × CPC × α が最大となる広告主に入札するようにしました。

αは重み付けで、本当は利益率から自動で最適化しなければならないのですが、3日間では他のチームがどれだけの金額で入札するかによって重みを最適化する式を模索しきれず、経過時間と予算消化率からαを求め、オークション状況によって動的に調整するように実装しました。

CTRは、予測するモデルを作成しました。(チームメイトの方が)

予測モデル

まず、学習データの次元が多すぎるため、データを可視化し、相関などを調べCTRに関係のなさそうな要素を除外しました。

f:id:palloc:20160912182344p:plain

その後、重要であろう要素をk-meansによりクラスタリングし、1-of-Kベクトルに次元圧縮しました。

予測モデル作成の手法は、ロジスティック回帰、SVM、ランダムフォレスト、XBGを試し、ロジスティック回帰が最も精度や時間的に適切だったため、ロジスティック回帰を用いました。

こちらの実装は優秀なチームメイトの方々が主に行ってくれていたので、本当に感謝の気持ちでいっぱいです。

コンペティション結果

コンペの結果、惜しくも1位と1点差で優勝を逃してしまいましたが、準優勝という結果でした!

また、今までのアドテクコンペ史上初の完走賞をもらい、結果的に2つも賞をいただけてとても嬉しかったです。

余談ですが、チームメイトのみなさんがとても優秀でいい人ばかりで、全チーム中一番仲がよかったチームらしいですw

チームメイトの皆さん本当にお世話になりました!

f:id:palloc:20160912184216j:plain

ソースコード

github.com

感想

開発環境について

オフィスがまず駅直結というか真上にあってアクセスがとても便利でした。

とても綺麗な部屋を用意していただけて、モニターの大量貸し出しやホワイトボードもあり作業がとてもはかどりました。

また、お菓子や飲み物や美味しいお弁当(値段みてびっくり)も用意していただき、何も不自由のない開発環境でした。

コンペティションについて

アドテクという個人的に全く知らない分野でのコンペティションだったので、とても緊張していたのですが、メンターさんの技術的&精神的サポートがとても手厚く、本当に助かりました。

コンペティション自体も、DSP開発期間中は何回かSSPが止まり自分で擬似SSPを書いたりしていたのですが、オークション本番はとても安定して動いていて、管理画面もすごくわかりやすいものが用意されていてプロのお仕事だ…と思いました。

お寿司について

とても美味しくて幸せでした。 f:id:palloc:20160912190126j:plain f:id:palloc:20160912185726j:plain

知見がたくさん得られ、たくさんの人と繋がれて、本当にアドテクコンペに参加できてよかったです。

サイバーエージェントさん本当にありがとうございました!

f:id:palloc:20160912190031j:plain