新しい広告配信アルゴリズムをリリースするまでのモロモロ

## この記事は

Speeeアドベントカレンダーの3日目です!

よければ他のメンバーの記事も読んでみてください。
https://qiita.com/advent-calendar/2017/speee

## 自己紹介
twitterID : hisao_00
弊社ネイティブアド事業の[UZOU](http://webmarketing-sp.jp/uzou/)のアナリティクスチームでリサーチャーをしています。
配信結果の統計分析から、広告配信アルゴリズムの調査/設計/プロトタイプ開発、、、などCTR向上のためにできることは何でもやっています。最近やっと新卒入社して1年経ちました。

## 3行でまとめると

- 新しい広告配信アルゴリズムを開発する際の注意点についてまとめた

- 今回シミュレーションしたアルゴリズムについてまとめた

- シミュレーション結果についてまとめた

## 新しい広告配信アルゴリズムを導入するとき
<img width="576" alt="スクリーンショット 2017-12-03 20.52.20.png" src="https://qiita-image-store.s3.amazonaws.com/0/146331/2b90f030-2d39-a17d-022a-8db0e60e5345.png">

基本的にこのような流れで進めていくのですが、
ここで重要なのは、3点あります。

- 必ずゲートを予め設定し、関係者とすり合わせを行う

- プロトタイプを作る時間をなるべく短くする

- プロトタイプを作っているときから、本番実装するエンジニアと連携しておく

### 必ずゲートを予め設定し、関係者とすり合わせを行う

もちろん精度の良いアルゴリズムを一発で作れれば何の問題もないのですが、実際本番にリリースしたら思っていたより精度が出ないってことはしばしばあると思います。

その場合、潔く諦めて反省を活かし、次のアルゴリズムのプロトタイプを作るまでの時間を短くするのは非常に重要です。

そのためにも、予め指標を設定しておき、その値に達したら次のステップに進み、達しない場合は戻るというロードマップを作成し、関係者に共有しておきましょう。

実際、今年の夏はこの期待値すり合わせを疎かにして本番開発に進んだせいで結構辛い状態になってしまいました、、、

### プロトタイプを作る時間をなるべく短くする

これも上の理由と近いのですが、工数が長くなれば長くなるほど期待値も自然に上がってしまうものです。本番で初めてわかることのほうが圧倒的に多いので、初めから作り込み過ぎず、スピード感を重要視して本番にリリースしながらチューニングするくらいでいいと思います。

### プロトタイプを作っているときから、本番実装するエンジニアと連携しておく

これは、プロトタイプを作る人と本番の開発をする人が異なる場合限定の話ですが、プロトタイプを作るときって、あまり処理速度を考慮せず作ることが多いと思います。(お前がエンジニアじゃないから気にしないだけだと言われればそれまでですが、、、)

いかに精度のいいプロトタイプを作っても、それが本番で耐えうるものでないと意味がありません。本番での実現可能性があとでネックになって悩むことの無いよう、予め連携してディスカッションしておきましょう。

弊社では優秀なエンジニアがたくさんいるので、この点に関してはあんまり気にしなくてもどうにかしてくれますw(もしかすると、毎回無理難題をつきつけやがってと思われているかもしれませんが本当に感謝しています)

精度の高いアルゴリズムを作って本番にリリースして結果が出るのは非常に楽しいものですので、余計なところで苦しまないように上記は必ずクリアにしておきましょう。

## 今回シミュレーションした広告配信アルゴリズムについて

広告配信について簡単におさらいすると、トランプの大富豪のようなもので、

- 手札(広告)をいかにタイミングよく上手に出すかで勝ち負け(成果)が決まる
- 手札(広告)はその時その時で増えたり減ったりするので常にその場に応じた戦略が必要
    - 予算などの制約によって急に配信成果の良い広告が出せなくなったり、月の途中で新しい広告が配信開始されたり、、、

ただ、大富豪と少し違うのは、あらかじめ手札の1枚1枚の強さ(配信成果)がわからないことです。
いつ、どこに、誰に出すかで大きく配信成果は異なってきます。

ということは、広告配信には大きく分けると2つのフェイズがあり、

- どの状況で何を出すのが1番成果がいいのか探索する(exploration)
- 成果が良いと判断した広告を配信することで成果を得る(exploitation)

![image](https://user-images.githubusercontent.com/21776253/30268390-7aea5658-9720-11e7-8267-9be00d13e9e1.png)
元々、探索部分に非常にシンプルなbanditアルゴリズムを動かしていたのですが、精度が悪かったので、各armのスコアの計算方法を改良してみました。
各armのスコアの計算に使用する計算式や、ハイパーパラメータの設定方法は残念ながらここに書くことはできませんが、、、

bandit？arm？みたいな方はこちらを参考にしてみてください
[多腕バンディット問題の理論とアルゴリズム 本多淳也 IBIS2014 2014/11/18](http://ibisml.org/archive/ibis2014/ibis2014_bandit.pdf)


## シミュレーション結果について
いくつかの配信先の9月の配信実績を用いて、出来るだけ現実に即したシミュレーションを行いました。

その結果がこちらです。
基本的に全て改良版のほうが良い成績を出していますね

|配信先|改良版(eCPM)|ベンチマーク(eCPM)|
| :--: | --: | --: |
| A| __¥104.91__ | ¥50.72 |
| B| __¥47.17__ | ¥10.96 |
| C| __¥181.51__ | ¥53.79 | 


### Aの例
#### 1ヶ月のimpの配信開始割合(改良版)
<img width="402" alt="スクリーンショット 2017-12-03 20.53.56.png" src="https://qiita-image-store.s3.amazonaws.com/0/146331/e0b8745e-f1e6-5983-e8ee-58694f7733d2.png">

#### 1ヶ月のimpの配信開始割合(ベンチマーク)
<img width="405" alt="スクリーンショット 2017-12-03 20.54.07.png" src="https://qiita-image-store.s3.amazonaws.com/0/146331/c09d0d11-d11f-712a-762f-6ad344e185bb.png">

改良版は途中から配信が開始した広告も適切に候補にはいっています。
一方、元のアルゴリズムは初めの候補をいつまでも高く評価してしまい、途中から配信が開始された広告をあまり出せていません。

#### imp内訳(左が改良版、右がベンチマーク)
<img width="702" alt="スクリーンショット 2017-12-03 20.54.23.png" src="https://qiita-image-store.s3.amazonaws.com/0/146331/e4c55848-b2b7-13e6-b734-a7ec49d83915.png">

また、各armの平均eCPMより高いarmをgood、低いarmをbadとしたときのimp割合を確認したところ改良版のほうが良いarmのimp割合が高くなっています。

これらから、探索が上手く行っていることがわかります。

上記は一例ですが、探索が上手くいくと、その他に走っている活用部分のアルゴリズムの精度もあがるという相乗効果も期待されるので一石二鳥ですね。

あくまでシミュレーションの結果でしかないので、A/Bテストをして同じような結果になるとは限りません。１つゲートを越えることができたというだけです。

## 最後に
まだまだ勉強不足な点が多く、使える技術も少ないので、新しい技術のキャッチアップを進めていくとともに、問題を解決できる方法を適切に選択できるように思考錯誤していこうと思います。

最後まで読んでいただきありがとうございます、
明日は hatappi より、『Goとポモドーロについて書く』です
お楽しみに！！