DSP広告配信最適化における技術概要

初めまして、[アルファアーキテクト](https://alpha-architect.co.jp/recruit/)でVPoEをやっております胡 恩召（Ethan Hu）です。
2020年5月よりアルファアーキテクト株式会社に入社をしました。

プロフィール

* 2011年7月、北京交通大学（Beijing Jiaotong University）大学院 
 Computer Science専攻 卒業。
* 2011年10月、株式会社VOYAGE GROUPに新卒入社、ソフトウェアエンジニアとして会員行動履歴データを活用し、新規[レコメンドシステム](https://techlog.voyagegroup.com/entry/2016/08/22/080000)の設計・開発・効果検証など作業を担当。
* 2017年9月、Supership株式会社に入社、プロダクトマネージャーとしてデータマイニングチームをリードし、広告プロダクト[ScaleOut DSP](https://supership.jp/business/scaleout/)の開発・配信最適化・チームマネジメントなど業務をメインに担う。
* 2020年5月、アルファアーキテクト株式会社に入社、執行役員VPoE（Vice President of Engineering）として就任。

その前までもずっとアドテクノロジー業界におり、今回は、プログラマティック広告のDSP配信最適化について簡単に紹介いたします（※一般的な知識を紹介したいので、主に参考資料よりまとめました）。

# 前提知識

インターネットの技術は進化しながら、インターネット広告のビジネスモデル・取引方法も進化しています。1996年ごろから予約型広告としてスタートして、1999年ごろ成果保証型広告、2002年ごろ検索連動型広告、2008年ごろアドネットワーク、2010年ごろプログラマティック広告が登場しました。その後プログラマティック広告の動向は、ビッグデータを利用して、ターゲティング対象が「枠」から「人」へ発展しています。直近の動向は、SSPのファーストプライス移行やChromeのクッキー廃止が話題になりました。

プログラマティック広告は、需要側のプラットフォームがリアルタイムでメディアの広告枠を自動買い付け出来る仕組みです。システム構成は、メディア側の在庫を集める供給側SSP（Supply Side Platform）、広告主側の在庫を買い付ける需要側DSP（Demand Side Platform）、リアルタイムでSSPとDSPのオークションによる取引のことRTB（Real Time Bidding）です。


## SSPとは 

SSPは、Supply Side Platformの略で、メディアの広告枠を供給する側のプラットフォームのことです。メディアの要望が出来るだけ高単価で広告枠を売れて、収益を最大化します。SSPの仕組みは、１つの広告枠を複数なDSP/アドネットワーク業者に広告掲載を請求して、各DSP/アドネットワークからRTBでリアルタイムに入札された単価を受け取り、一番高額と判定されたDSP/アドネットワークの広告が配信されます。


## DSPとは 

DSPは、Demand Side Platformの略で、広告枠を提供してもらう側のプラットフォームということです。DSPのゴールは、広告主の成果を最大化することです。広告主/代理店より広告を入稿して、予算や配信条件の制約で、最適なSSP在庫を買い付けに行う。広告効果を最大化するのため、ユーザーの理解やビッグデータ解析など技術採用が必要です。


## RTBとは  

RTBは、Real Time Biddingの略で、リアルタイムで広告枠をオークション形式で売買する仕組みです。
![RTB system.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/641596/73a274c5-9fa7-66bf-ea2c-7960239e5adc.jpeg)
RTBの仕組み[参考出典: 資料3]

RTBの仕組みの詳細：
（１）広告入稿
DSP側で広告主/代理店より広告を入稿する。広告主が入札条件を提示しています。入札条件として、予算、広告の掲載基準、上限入札価格、ターゲットユーザ属性などを指定します。

（２）ユーザーがメディアへアクセス
あるユーザーが、SSP側のメディアのページにアクセスして、ページに埋め込まれた広告JSタグが起動し広告枠がリクエストされます。

（３）広告枠発生処理
メディア側の広告枠は、SSPへリクエストする際に、Cookieによって獲得してユーザー情報、メディアページ情報をSSPに送ります。

（４）ビッドリクエスト処理
SSPがDSPに広告ビッドリクエストする際に、ユーザー関連情報（CookieID、IPアドレス、UserAgentなど）、メディア情報（カテゴリー、URL、広告枠ID、広告サイズなど）、条件情報（許可広告主種類、フロープライスなど）を一緒に送ります。

（５）ビッドリクエストの解析
DSP側受けたビッドリクエストを解析して、配信中な広告の配信条件を確認する上で、一番適切/収益が高い広告を選択する。適切かどうか、収益の判断など、複雑な技術が必要ですが、この後、紹介します。

（６）DSPから入札処理
入札希望なDSPからSSPへ入札価格、広告のクリエイティブなど情報をレスポンスします。

（７）オークション処理と結果通知
オークションに参加したDSPの入札価格で勝利DSPを確定して、勝利通知と落札価格を送ります。オークションは、SSPによって、ファーストプライスとセカンドプライスが二種類があります。

（８）広告掲載通知
SSPのアドサーバーからユーザーへ掲載予定広告情報を送ります。

（９）インプレッションリクエスト
ユーザー画面に埋め込まれたJSタグが掲載広告情報を受け取り、広告をDSPへリクエストします。

（１０）ユーザーに表示
DSPからインプレッションがユーザへ送られ、画面に広告が表示されます。

上記RTB仕組みの処理時間が0.1秒以下で実施完了が必要です。遅くなると、ユーザーの体験に影響を与えます。

# DSP側配信最適化における技術概要

## 配信最適化に関わる要素

DSPの入札最適化は、簡単に言うと「広告主にはより多くの成果を出すこと」です。この目的を達成するため、ユーザーに良い体験な広告を配信することが必要です。ユーザーに最適な広告を出さないと、あまり効果（主にクリックやコンバージョン）を出ない。配信最適化に関わる要素は、６個があります。

* What（どんな広告を）
* When（いつ）
* Where（どこで）
* Who（誰に）
* How Much（いくら）
* Why（なぜ）

上記の６個要素をRTBの仕組みに表現
![RTB system - 5W1H.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/641596/7bd97945-9ee6-0cd1-5022-2563f641b112.jpeg)
RTBの仕組み[参考出典: 資料3]

配信最適化に関わる要素から、最適化配信に実現方法は、機械学習で要素とユーザー行動の相関関係モデルを学習します。そのモデルを使って、ユーザー行動の確率を推定出来ます。
![rtb-user-context-ad.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/641596/41df8fa1-b7a0-ac87-58bc-a3c1232d21a1.png)


## 配信最適化における技術概要

配信最適化に関わる要素の紹介は、超ざっくり内容ですが、実際にDSP側の配信最適化は、いろんな細かい作業や支えるシステムが必要です。例えば、ユーザープロファイル、興味関心推定など、データ集計基盤、ABテスト基盤、機械学習基盤などが必要です。

配信最適化作業の中で、一番コアの部分は、３つがあると思います。
* CTR推定（Click-through Rate Estimator）
* マーケットプライス予測（Bid Landscape Forecasting）
* 入札策略最適化（Bid Optimisation）

![rtb-optimisation.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/641596/5d86e0c6-03aa-1d21-4329-583d1edd7d28.jpeg)
RTB最適化の詳細[画像出典: 資料4]

### CTR推定

広告主のKPIは、主にCPC（Cost Per Click）、CPA（Cost Per Action）、動画のCPCV（Cost Per Completed View）があります。DSP側毎回ビッドリクエストの「価値評価」を行い、その時CTR、CTVR、VTR推定が必要です。今回はCTR推定方法を簡単で紹介します。
![ctr-models.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/641596/b3a4a823-3abc-0340-de80-967710c1fdb1.jpeg)
CTR推定発展[画像出典: 資料5]

広告のデータ量（ユーザー x 広告枠 x 広告）が非常に膨大なので、CTR推定はほぼ機械学習手法でやる。推定精度がもちろん、パフォーマンスも考慮が必要です。アドテック業界で有名なアルゴリズムは、Steffen Rendleさん2010年にICDMコンファレンスで発表されたFactorization machines（FM）です。広告のCTR(click-through rate)やCVR(conversion rate)の予測タスクにおいて、FMモデルが良いを証明された。FMモデルの特徴は、特徴間の組み合わせができるようにしました。

```math
\bar{y}(x) := w_0 + \sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}w_{ij}x_ix_j 
```

数式モデルの第３項目のウェイト $w_{ij}$ の学習のための充分な $x_i$ と $x_j$ の組み合わせが揃わないことになります。各特徴量に $k$ 次元のベクトルを持たせておいて、そのベクトルの内積で組み合わせのウェイトを表現します。 <$v_i,v_j$> の部分です。

```math
\bar{y}(x) := w_0 + \sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}<v_i, v_j>x_ix_j 
```
```math
<v_i, v_j> := \sum_{c=1}^{k}v_{i,c} ・v_{j,c}
```
数式の $v_i$ が $x_i$ の $k$ 次元ベクトルで、$v_j$が $x_j$ の $k$ 次元ベクトルです。<$v_i$,$v_j$> と <$v_i$,$v_l$> とでは、お互いに $v_i$ を共有しているため、$v_i$ をより多くのサンプルから学習することができる。

FMモデルに基づいて、いろいろ改善版モデルが出ました、例えばField-awareFM（FFM）モデル、深層学習を結合してDeepFMやDeepFFMなど。

### マーケットプライス予測

DSPの立場で、SSPからのビッドリクエストを入札する際に、他のDSPと競争しているのため、マーケット当時の状況を予測が必要です。いくらで入札すれば、このオークションを勝って、インプレッションを取れます。

数学でモデリングすると、あるbid request $x$、入札単価 $b_x$、オークションの勝率は $P(win|x, b_x)$ です。$b_x$ は $x$ の勝率を影響されます。この関係は、 $w(b_x) = P(win|x, b_x)$ と表示されます。

オークションのルールより、勝率は マーケットプライス $z$ が $b_x$ より低い確率は：

```math
w(b_x) := P(win|x, b_x) = \int_{0}^{b_z} p_z^x(z)dz.
```

次の作業は、$p_z(z)$ を推定します。一般的な方法は、以前の入札履歴から算出します。

```math
w_o = \frac{\sum_{}^{}{}_{(\bar{x}, y, z) \in  D}I(z < b_x)}{|D|}
```

$y$：ビッドリクエスト $\bar{x}$ のユーザーアクション（クリック、コンバージョンなど）、オークションが勝った後獲得出来る。
$z$：ビッドリクエスト $\bar{x}$ の実際マーケットプライス、オークションが勝った後獲得出来る。
$D = {(x, y, z)}$：獲得されたオークション勝ったデータ。
$I$：indicator functionです、条件を満たす場合の値が１、満たない場合の値が０。

モデリングした後、モデル学習はいくつ方法があり、例えばGBDT[8]、深層学習[9]があります。

### 入札策略最適化

入札する時、マーケットプライス予測以外、入札策略最適化も必要です。主な作業は、ビッドリクエストの質（CTR、CVR）に応じて、オークションの勝率と一緒に考慮する上で、入札単価を調整します。

仮で広告主は、CPCが重視しています。簡単な入札単価計算式は 

$bid\\_price = CTR x CPC$ 

CPCが固定ですが、CTRが $n$ 倍の場合、入札単価も $n$ 倍になります。ただし、実際なマーケットプライスを参考して、 $n$ 倍になれなくても大丈夫です。
そのため、入札単価計算式を修正します

$bid\\_price = CTR x CPC - a$ 

$a$ は、調整係数ですが、マーケットの競争が激しい場合、$a$ を下げて入札単価を上げて、オークション勝率を上げます。$a$ の値も入札履歴データから計算します。

入札最適化は、個別広告の効果最適化ではなく、全て広告案件に対して、全ての広告在庫ボリューム（全てSSPからのビッドリクエスト）を買い付け最適化です。簡単に言うと、広告予算と広告在庫の制約で、広告の収益を最大化する。

モデリングの問題定義[10]：

```math
arg maxT \int_{x}^{}f(x)w(b(f(x)))p_x(x)dx
```
```math
subject to T \int_{x}^{}b(f(x))w(b(f(x)))p_x(x)dx=B
```

T：広告在庫ボリューム
B：広告予算
$x$：bid request
$f(x)$：CTR推定関数
$b(f(x))$：入札価格計算関数
$w(b(f(x)))$：オークションの勝率

上記の問題を解決するは、数学の最適化知識が必要です。参考資料の論文[10]がEuler-Lagrangianを利用した。


# まとめ

アドテック技術が迅速に発展していますが、最新な研究結果をキャチアップして、常に配信最適化のロジックも進化することが必要です。直近のアドテック業界動向は、SSP側のファーストプライスオークションへの移行以外、プライバシーポリシー規制が厳しくなり、クッキーレス時代のオーディエンス・ターゲティング方法が対応などが必要です。常に最前線でサービスを考えること、最新の技術取り込むことによるやりがい・楽しさが一番の魅力だと思っています。

アルファアーキテクトは現在IPOを目指しています。『VeleT』の発展を加速させるため、 現在[インフラエンジニア](https://alpha-architect.co.jp/935/)、[バックエンドエンジニア](https://alpha-architect.co.jp/939/)、[テックリード](https://alpha-architect.co.jp/384/)などを積極的に募集しています。動画広告サービス『VeleT』の開発を一緒に推進してくれる方、是非応募をお待ちしています！

# 参照資料
[1] http://blog.katty.in/5143
[2] https://webtan.impress.co.jp/e/2018/04/16/28775
[3] https://www.ogis-ri.co.jp/rad/webmaga/1231408_6728.html 
[4] https://zhuanlan.zhihu.com/p/32664649 
[5] https://zhuanlan.zhihu.com/p/104307718 
[6] https://github.com/wnzhang/rtb-papers
[7] https://github.com/wzhe06/CTRmodel 
[8] [Bid Landscape Forecasting in Online Ad Exchange Marketplace](http://wnzhang.net/share/rtb-papers/bid-lands.pdf)
[9] [Deep Landscape Forecasting for Real-time Bidding Advertising](https://arxiv.org/pdf/1905.03028.pdf)
[10] [Optimal Real-Time Bidding for Display Advertising](http://wnzhang.net/papers/ortb-kdd.pdf)