RTBにおける落札額・落札確率予測

はじめに

こんにちは、機械学習エンジニアの大庭です。昨年の4月に新卒でマイクロアドに入社し、現在はUNIVERSE Adsというプロダクトで入札アルゴリズムの研究開発および実装を担当させていただいてます。この記事では、僕が現在検証している機械学習による落札予測タスクについてご紹介していこうと思います。皆さんにマイクロアドの事業内容を理解していただく助けとなれば幸いです。

はじめに
RTBと入札額決定
落札予測とは？
- 入札額の最適化
- 入札額の安定化
落札予測の課題
- 出力が確率分布
- 右側打ち切り問題
実装
精度検証
おわりに

RTBと入札額決定

Real-Time Bidding（RTB）では下図のように、広告主とメディア間でリアルタイムにオークションが開催され、オークションに勝利した広告がメディアに表示されるという仕組みになっています。

このRTBへの入札額をマイクロアドでは主にClick Through Rate(CTR)予測によって決定しています。CTRとはユーザーが表示された広告をみてそれをクリックする確率のことで、ユーザー情報や表示したい広告情報、広告枠の情報などから予測を行います。この予測CTRにクリック毎の目標単価であるCost Per Click(CPC)を掛け合わせることで、ユーザーに広告を表示した場合の効果を求め、入札額決定に利用しています。

f:id:oba_atsushi:20210128154105p:plain

詳しくは以下のCTR予測についてのスライド、記事をご一読いただければと思います。

マイクロアドにおけるCTR予測への取り組み from MicroAd, Inc.(Engineer)

www.slideshare.net developers.microad.co.jp developers.microad.co.jp

落札予測とは？

RTBのリクエスト情報からそのリクエストがいくらで、どのくらいの確率で落札されるのかを予測するタスクのことで、研究領域ではBid Landscape Forecastingと呼ばれています。以下の図のように落札予測ではRTBリクエストの情報から落札確率の分布を予測します。

f:id:oba_atsushi:20210128153751p:plain

入力データはRTBリクエストに含まれるユーザー情報・広告枠情報などでCTR予測とおおよそ同じですが、広告情報が含まれないことに注意してください。これは落札予測はRTBリクエストの市場価値を求めるという性質から表示する広告の情報を必要としないためです。

また、リクエストの市場価値を直接求めるのではなく落札額の確率分布として予測することも落札予測の特徴となっています。これにより、落札額の算出・ある入札額での落札確率の算出・分布に基づいた入札額の補正など、複数の用途に予測結果を利用できるようになっています。

CTRを予測だけでも入札額を決定することは可能ですが、落札予測の結果を入札額決定に加えることで以下のような効果が期待できます。

入札額の最適化

近年RTBではファーストプライスオークションと呼ばれる最も高い入札額をそのまま落札額として扱う形式が主流になりつつあります。ファーストプライスにおける理想的な入札とは市場価格（競合他社の入札の内最高額のもの）よりわずかに高い額での入札であり、それを行うためには過去の落札額の傾向を考慮する必要があります。落札予測の結果を用いて市場価格に基づいて入札金額を調整することで、入札額を最適化することができます。

入札額の安定化

また、落札予測とCTR予測の結果を組み合わせることは入札額決定の安定化にもつながります。例えば、CTR予測では新規に追加された広告に対しては少ないデータを元に学習が行われてしまい予測値が不安定になる傾向がありますが、落札予測では広告情報を入力データとして用いないため、このような新規の広告に対しても安定した予測を行うことができます。このように広告効果の観点で予測を行うCTR予測に広告枠の市場価値という観点で予測を行う落札予測を加えることで、より安定した信頼性の高い落札額決定が可能となります。

落札予測の課題

次に落札予測タスクの機械学習的な問題設定についてご説明していこうと思います。このタスクで考慮が必要となっているのは主に以下の２点です。

出力が確率分布

落札予測では用途を広げる目的で予測対象を確率分布としているため、モデルも出力が確率分布となっている必要があります。この時、連続型確率分布を求めるか、離散型確率分布を求めるかの２通りがあるのですが、実際の落札額の分布は不規則な場合が多いため、離散型確率分布を利用する手法が主流となっています。

右側打ち切り問題

RTBのログでは、落札できた場合には落札額の情報が得られるのですが落札できなかった場合は実際に広告を出稿することができないため落札額が自社の入札額よりも高かったという情報だけが残ります。

つまり、勝利ログの集合 $\mathcal{D_{\rm win}}$ では入力データ $\boldsymbol {x}$ 、入札額 $b$ 、落札額 $z$ を利用できます。

$\mathcal{D}_{\rm win } = \{(\boldsymbol {x} _ i, z _ i, b _ i)\}_{i=1}^{N_{\rm win}}$

しかし、敗北ログの集合 $\mathcal{D_{\rm lose}}$ では落札額 $z$ を利用できず、入力データ $\boldsymbol {x}$ と入札額 $b$ のみが利用できます。

$\mathcal{D}_{\rm lose} = \{(\boldsymbol {x} _ i, b _ i)\}_{i=1}^{N_{\rm lose}}$

この時、不明な落札額 $z$ は $z > b$ となることのみわかります。

この、あるイベント（RTBにおいてはオークションの勝敗）の結果によっては特定のラベルが取得できず、他ラベルとの大小関係のみ利用できることは右側打ち切り問題と呼ばれ、落札予測ではこの問題を考慮してモデルを学習する必要があります。

実装

以上のような落札予測タスクの機械学習的な課題を解決するため、今回の記事では以下のような実装を行っています。

DeepHitモデル

この記事ではLee et al. 2018にて提案されたDeepHitモデルを利用しています。DeepHitモデルはシンプルなニューラルネットで構成されており、出力層にSoftmax関数を適用することで、確率分布として扱えるようにしていることが特徴です。

落札額予測には他にも決定木を用いたSurvival Tree Model(STM)(Yuchen et al. 2016)やRNNベースのDeep Landscape Forecasting(DLF)(Kan et al. 2019)など有力なモデルがいくつも提案されていますが、今回は予測精度が高いこととRTBにおける実行時間の制約をクリアできることからDeepHitモデルを採用しています。

以下はpytorchでのDeepHitモデルの実装例になります。

class DeepHit(nn.Module):
    """
    Attributes:
        x_size(int): 入力の次元数
        h_size(int): 隠れ層の次元数
        p_size(int): 出力する確率分布の次元数（ビンの分割数）
        drop_rate(float): ドロップアウトの比率
    """
    def __init__(self, x_size, h_size, p_size, drop_rate=0.):
        super(DeepHit, self).__init__()
        self.emb = nn.EmbeddingBag(x_size, h_size)
        self.fc = nn.Sequential(
            nn.Linear(h_size, h_size), nn.ReLU(), nn.BatchNorm1d(h_size), nn.Dropout(drop_rate), 
            nn.Linear(h_size, p_size))
        self.softmax = nn.Softmax(dim=1)

    def forward(self, x):
        h = self.emb(x)
        h = self.fc(h)
        P = self.softmax(h)
        return P

入札額・落札額のビニング

また、DeepHitモデルの出力は離散型の確率分布であるため、本来連続量である入札額・落札額を離散量に変換する処理が必要となります。今回の検証では以下のような手順でビニングを行い、入札額・落札額を離散量のインデックスに変換しています。

1. データセットの入札額・落札額を連結してソート
2. ソートしたリストからbin数 * nのインデックスの値を取得
3. bin幅を取得
4. ビン幅を元に入札額・落札額をインデックス化

この処理では実際の入札額・落札額からカウントベースでビンサイズを決定することで変換後に全てのインデックスで分布が均等になるようにしています。以下が適用例です。

# 元データ
入札額リスト: [0.1, 20, 0.4, 0.3, 50, 100]
落札額リスト: [10, 0.2, 0.1, 70, 0.4, 0.9]

# step 1. データセットの入札額・落札額を連結してソート
=> [0.1, 0.1, 0.2, 0.3, 0.4, 0.4, 0.9, 10, 20, 50, 70, 100]

# step 2. ソートしたリストからbin数 * nのインデックスの値を取得（bin数 = 3 の場合)
=> [0.3, 10, 100]

# step 3. bin幅を取得
=> bin[0] :   0 <= b < 0.3  # bin[0]の下限は0
   bin[1] : 0.3 <= b <  10
   bin[2] :  10 <= b < 100

# step 4. ビン幅を元に入札額・落札額をインデックス化
=> インデックス化した入札額リスト: [0, 2, 1, 1, 2, 2]
   インデックス化した落札額リスト: [2, 0, 0, 2, 1, 1]

損失関数

今回の検証ではK. Ren et al. 2019で提案されている損失関数を利用します。

まず前提として入力データ $\boldsymbol {x}$ に対するモデルの予測確率分布を

$P(\boldsymbol {x}) = model(\boldsymbol {x})$

とした場合、この入札リクエストへ入札額 $b$ で入札した場合の落札確率 $W(b | \boldsymbol {x})$ は以下のように求めることができます。この時、落札額 $z$ は $z \geq 0$ です。

$\displaystyle W(b | \boldsymbol {x}) = \sum _ {z < b} P(z | \boldsymbol {x})$

次に本題の損失関数 $L$ ですが、以下のようにハイパーパラメーター $\alpha$ によって比率を制御された２つの損失関数 $L _ 1$ 、 $L _ 2$ から構成されます。

$L = \alpha L_1 + (1 - \alpha) L_2$

ここで $L_1$ は $\mathcal{D} _ {\rm win}$ 中の入力データ $\boldsymbol {x} _ i$ と落札額 $z _ i$ から

$\displaystyle L_1 = - \sum_{(\boldsymbol {x} _ i, z _ i) \in \mathcal{D}_{\rm win}} log P(z _ i | \boldsymbol {x} _ i)$

と求めることができ、実際の落札額に対応するビンでの予測落札確率における負の対数尤度を最小化することで、モデルの予測確率分布を最適化する働きがあります。

また $L_2$ は $\mathcal{D} _ {\rm win}$ 、 $\mathcal{D} _ {\rm lose}$ 中の入力データ $\boldsymbol {x _ i}$ と入札額 $b _ i$ から

$\displaystyle L_{\rm win} = - \sum_{(\boldsymbol {x} _ i, b _ i) \in \mathcal{D}_{\rm win }} log W(b _ i | \boldsymbol {x} _ i) \\ \displaystyle L_{\rm lose} = - \sum_{(\boldsymbol {x} _ i, b _ i) \in \mathcal{D}_{\rm lose}} log (1 - W(b _ i | \boldsymbol {x} _ i)) \\ \displaystyle L_2 = L_{\rm win} + L_{\rm lose}$

と求めることができ、勝利データ・敗北データのそれぞれでログの入札額での予測勝率・敗北率の誤差を最小化します。

このように落札額を利用した確率分布のズレに敏感な損失関数である $L _ 1$ と落札額を入力として必要とせず勝利ログと敗北ログの両方で利用可能な $L _ 2$ を組み合わせることで、右側打ち切り問題を考慮したモデルの学習を行うことができます。

精度検証

ビニングによる落札額分布の変化

まずはじめに、ビニングで落札額を離散量に変換した場合の分布の変化を確認します。bin数は100に設定しています。

f:id:oba_atsushi:20210201125934p:plain — 変換前の分布（左：落札額、右：入札額）

f:id:oba_atsushi:20210201125806p:plain — 変換後の分布（左：落札額、右：入札額）

入札額・落札額はインデックス化され 0 ~ 100 の離散値になっているのに加え、変換前は 0 付近に集中していた分布が均されているのが確認できます。

落札確率予測

次に配信ログを用いて落札確率の予測精度の検証を行います。教師ラベルは落札したかどうかの２値、予測落札確率はモデルの出力である落札確率分布から自社の入札額での落札確率を以下の式で求めたものです。

$\displaystyle W(b | \boldsymbol {x}) = \sum _ {z _ i < b} P(z _ i | \boldsymbol {x})$

Area Under the Curve of the Receiver Operating Characteristic (AUROC)とPrecision-Recall Area Under Curve (PRAUC)の２つの評価指標でのスコアが以下になります。また、ファーストプライスオークションとセカンドプライスオークションでは落札額の算出方法が異なることからモデルを分割して予測しています。*1