数理最適化を用いて広告オークション入札金額を自動で調整してみた

こんにちは、UZOU事業部の久松 @hisao_00 です。
業務としては、ネイティブ広告配信アルゴリズムの調査、設計、プロトタイプ開発を行っています。先日開催された、SpeeeKaigi#4にて「数理最適化を用いた広告オークション入札金額の最適化」について発表しました。
数学好きの方、アドテク界隈の方、ぜひ読んで頂ければ幸いです。

概要

制約つき非線形最適化問題を解くことで、広告主がメディアの配信枠に対して入札する金額を最適化するロジックを考え、シミュレーションしてみました。

背景

広告主はUZOUを通してメディアに配信されますが、広告主に継続して出稿してもらうためには、広告成果を合わせることが重要です。

f:id:yuki-hisamatsu:20180417124413p:plain

広告成果とは

Web広告の大多数は、パフォーマンス広告と呼ばれるもので、
健康食品や化粧品など、ネット上に配信された広告を導線として
商品の購入までを想定して配信されています。

そのため、商品1単位の購入にかける広告予算が決まっています。
(これを 目標CPA といいます、CPAはCost Per Acquisitionの略)

広告主に継続的に使ってもらえるプロダクトにするためには、
目標CPAを越さない範囲で、配信金額を最大化する必要があります。

そのためには、メディア毎に細かい入札金額の調整が必要になります。
ただ、これを人力で随時調整するのは辛い、、、
(数百メディアの配信結果を見ながら、適宜調整することになります。)

ということで自動化を試みます。

解決方法

下記の制約条件の下、目的関数を最大化させる $b_{ix}$ , $i \in \{1,...,N\}$ を求めます。

▶︎目的関数

$f(b_{1x},b_{2x},...,b_{Nx}) = T \sum\limits_{i=1}^N b_{ix} W(b_{ix}, \tilde{\theta}_{ix}) \tilde{\theta}_{ix} p_i$

▶︎制約条件

$T \sum\limits_{i=1}^N b_{ix} W(b_{ix}, \tilde{\theta}_{ix}) \tilde{\theta}_{ix} p_i \leq r_x T \sum\limits_{i=1}^N \theta_{ix} W(b_{ix}, \tilde{\theta}_{ix}) \tilde{\theta}_{ix} p_i$

▶︎注釈

$x$ ：広告主
$i \in \{i, \dots, N\}$ ：メディア
$T$ ：対象メディアの合計 $\mathit{imp}$
$b_{ix}$ ：広告主 $x$ がメディア $i$ に入札する金額
$W(b_{ix}, \tilde{\theta}_{ix}) = \cfrac{1000b_{ix}\tilde{\theta}_{ix}}{1000b_{ix}\tilde{\theta}_{ix} + \ell_i}$ ： $b_{ix}, \tilde{\theta}_{ix}$ でオークションに勝利して配信される確率
$\tilde{\theta}_{ix}$ ：広告主 $x$ がメディア $i$ に配信する際の予測 $\mathit{CTR}$
$\theta_{ix}$ ：広告主 $x$ がメディア $i$ に配信する際の予測 $\mathit{CVR}$
$p_i$ ：対象メディア全 $\mathit{imp}$ 中のメディア $i$ の $\mathit{imp}$ 比率
$\ell_i$ ：各メディア毎の勝率モデル構築の際のパラメータ
$r_x$ ：広告グループ $x$ の目標 $\mathit{CPA}$

簡単に見ていきます

目的関数

${\displaystyle f(b_{1x},b_{2x},...,b_{Nx}) = \bbox[5px,border: 2px solid #56a7dc]{T} \sum\limits_{i=1}^N \bbox[5px,border: 2px solid gray]{b_{ix}} \bbox[5px,border: 2px solid #56a7dc]{W(b_{ix}, \tilde{\theta}_{ix})} \bbox[5px,border: 2px solid #d42530]{\tilde{\theta}_{ix}} \bbox[5px,border: 2px solid #56a7dc]{p_i} }$

青の部分 : 予測imp
赤の部分 : 予測CTRなので、青 × 赤でClick
灰の部分 : 入札金額なので、青 × 赤 × 灰で配信金額

つまり、目的関数は広告の配信金額を表現しています。

制約条件

${\displaystyle \bbox[5px,border: 2px solid gray]{T \sum\limits_{i=1}^N b_{ix} W(b_{ix}, \tilde{\theta}_{ix}) \tilde{\theta}_{ix} p_i} \leq \bbox[5px,border: 2px solid #91bd5a]{r_x} \bbox[5px,border: 2px solid #56a7dc]{T} \sum\limits_{i=1}^N \bbox[5px,border: 2px solid #f39b2d]{\theta_{ix}} \bbox[5px,border: 2px solid #56a7dc]{W(b_{ix}, \tilde{\theta}_{ix})} \bbox[5px,border: 2px solid #d42530]{\tilde{\theta}_{ix}} \bbox[5px,border: 2px solid #56a7dc]{p_i} }$

灰の部分 : 目的関数(配信金額)と同じ
青の部分 : 予測imp
赤の部分 : 予測CTR、橙の部分 : 予測CVRなので、青 × 赤 × 橙でCV
緑の部分 : 目標CPAなので、青 × 赤 × 橙 × 緑で配信impに対する上限金額

制約条件は、目標CPAを越さないように配信しなければならないという条件を不等式で表現しています。

実際に解いてみる

目的関数は凸関数となるので、ラグランジュの未定乗数法で解きます。

${\displaystyle b_{ix} = \cfrac{ -\ell_i + \sqrt{ \ell_i^2 + \frac{1000\lambda\ell_i r_x \theta_{ix} \tilde{\theta}_{ix}}{1 + \lambda} } }{ 1000\tilde{\theta}_{ix} } }$

ただし、 $\lambda$ は、
${\displaystyle h(\lambda) = \sum_{i=1}^N p_i \tilde{\theta}_{ix} \cfrac{1000b_{ix}\tilde{\theta}_{ix}}{1000b_{ix} \tilde{\theta}_{ix} + \ell_i} (b_{ix} - r_x \theta_{ix}) = 0 }$
の解になります。

$h(\lambda)$ は $\lambda = -1$ で非連続ですが、 $\lambda \in (-\infty,-1) , \lambda \in (-1,\infty)$ で単調増加(減少)関数となります。
そのため、定義域の場合分けさえ行えば、 $\lambda$ の近似解をニュートン法を用いて求めることが出来ます。

手こずった所

微分計算大変

久しぶりにラグランジュの未定乗数法を用いて微分計算を行いました。
大学院入試を思い出して懐かしい気分になりました。

目的関数が連続でない場所がある

はじめは、おそらく凸関数だろう、単調連続関数だろうと思って
詳細を考えずニュートン法で計算させていたのですが、
上で述べた通り、実は非連続な関数なので注意が必要です。
※実際、微分計算して凸性と単調性は確認済みです。

解の絶対値が極端に大きくなる

$h(\lambda) = g(\frac{\lambda}{1 + \lambda})$ なので、 $\frac{\lambda}{1 + \lambda}→1$ のとき、 $|\lambda|→\infty$ となってしまいます。
そこで、予め閾値を設定し、その値よりも大きくなった場合にはその値で置き換えることにしました。(下記のコードでは、閾値を10000にしています)

f:id:yuki-hisamatsu:20180417184240p:plain

import scipy.optimize as optimize
import pandas as pd

def optimize_lambda(self):
    maxiter = 10000
    tol = 1e-3
    x0_first = -2
    x0_second = 0
    lambda_default_minus_value = -10000

    for adid in self.adgroup_id_target:
        param_set = self.target_param[self.target_param['ad_group_id'] == adid]
        param_set = pd.merge(param_set, self.placement_param[['placement_id', 'optimize_l', 'imp_ratio']],
                             how="left", on='placement_id')
        try:
            result_lambda = optimize.newton(func=self.lagurandian_derivative_lambda, x0=x0_first, fprime=self.lagurandian_derivative_lambda_prime,\
                            args=(adid, param_set), maxiter = maxiter, tol = tol)
            if result_lambda < lambda_default_minus_value:
                logger.debug("newton_result ad_group_id:{} success first oprimize.newton() result_lambda:{} orginal_result_lambda:{}".format(
                    adid, lambda_default_minus_value))
                result_lambda = lambda_default_minus_value
            else:
                logger.debug("newton_result ad_group_id:{} success first oprimize.newton() result_lambda:{}".format(
                    adid, result_lambda))

        except Exception as e:
            logger.info("newton_result ad_group_id:{} fail first optimize.newton. error:{}".format(adid, e))
            try:
                result_lambda = optimize.newton(func=self.lagurandian_derivative_lambda, x0=x0_second, \
                                fprime=self.lagurandian_derivative_lambda_prime, args=(adid, param_set),\
                                maxiter = maxiter, tol = tol)
                logger.debug("newton_result ad_group_id:{} success second oprimize.newton() result_lambda:{}".format(adid, result_lambda))
            except Exception as e:
                logger.error("newton_result ad_group_id:{} fail second optimize.newton. error:{}".format(adid, e))
                raise

        logger.debug("optimize.newton ad_group_id:{} ret:{}".format(adid, result_lambda))
        self.adgroup_param.loc[self.adgroup_param['ad_group_id'] == adid, 'optimize_lambda'] = result_lambda

シミュレーション結果

自動化する前と自動化した後で、広告成果が上昇していることがわかります。

	CPA達成率	配信金額
前後比	+9.0%	+7.3%

まとめと今後

使っているライブラリは非常に基本的なものです。(今回でいうと、scipy.optimize.newtonのみ)
ただ、裏側の数学的理解があるかないかで、問題の設定の仕方や、用いる解法が大きく異なってくると改めて感じました。
(例えば、今回だとSGD使わなくていいよね、、、みたいな)
やはり、数学大事です。

上では割愛しましたが、
実は、予測CVR、予測CTR、パラメータの精度次第でこの最適化の精度は大きく変わります。
いかにこの精度を担保するかについては引き続き試行錯誤していこうと思います。