日本オペレーションズ・リサーチ学会
2023 年春季研究発表会

1-F-7

実績データが少ない広告に対する入札額最適化ロジック
014054301.

negocia 株式会社
東京工業大学*川上孝介
中田和秀

はじめにGoogle、Yahoo!、Amazon に出稿するリスティ
ング広告やディスプレイ広告などのインターネッ
ト広告は、顧客が設定した予算制約や、クリック単価等 KPI に関わる複数の制約を守りつつ、売り上げなどの目的となる指標が最も高くなるように、広告の日予算や入札額を日々調整しなければならない。しかし、インターネット広告は、媒体ごとに客層などの特徴が異なるほか、運用方法も異なるため、効率な広告運用は難しい。このため、たとえ優れた商品を保有する事業者でも、適切なノウハウを持ち合わせていない事業者は、自社商品を世の中に広められない課題がある。我々は、この課題を解決するために、インターネット広告に対する日予算/入札額最適化システムを開発している。本報告では、実績データが少なく予測モデルの精度が十分に出ないケースにおいても効率良く入札額が最適化できるアルゴリズムを考案したので報告する。

2.

入札額最適化問題

入札額最適化問題は、予算制約、KPI 制約を守りながら広告価値を最大化する問題として以下の通り定式化できる。
∑maximizexi v i ,subject toi∈N∑i∈N∑xi wi θi ≤ B,
xi w i θii∈N∑

xi v i(1)≤Ci∈N0 ≤ xi ≤ 1
ここで、xi は、広告 i に入札するとき 1、しないと
き 0 となる決定変数であり、本問題では 0-1 の連続変数に緩和している。vi は、1 クリックあたりの広告 i の価値を表す。wi は、広告 i のクリック単価を表す。θi は広告 i の Click through rate (ctr)

KAWAKAMI Kosuke
NAKATA Kazuhideを表す。B は、当該アカウントが 1 日に利用可能な予算の上限（日予算）を表す。C は KPI の制約条件である。
Yang ら [1] は、式 (1) と同等の問題に対して双対問題を考えることで、相補正条件から最適な入札戦略を導出する手法を提案している。Yang らの手法を利用すると、式 (1) から最適入札額 bidi は以下の通り計算できる。

bidi =

qvi
vi+C(p + q) (p + q)(2)

ここで、最適入札額 (2) に現れる p, q は当該広告に関わるオークションがすべて完了しないと真の値がわからない未知のパラメータであり、実績データから逐次的に求めなければならない。Yangら [1] は p, q を PID 制御やモデル予測制御を利用して逐次的にアップデートする手法を提案している。また、He ら [2] らは、実績データを利用した学習環境を構築し、連続最適化問題に対応した強化学習によりパラメータを学習する手法を提案している。本研究では、取得可能なデータの制約から Yang ら [1] の制御ロジックを踏襲して最適化システムを構築した。

3.

従来手法の課題

最適入札戦略に現れるように、最適な入札額を求めるためには p, q 以外に、vi の予測が必要である。ここで、広告のうち、impression や click などのデータ数が十分な広告は機械学習で比較的高精度な予測が可能となる。一方、データ数が少ない広告は、相対的に予測精度が低くなる。このため、データが少ない広告の vi が低く見積もられすぎたり、逆に大きく見積りすぎたりと、予測誤差の影響で機会損失が発生する可能性が高い。

4.

提案手法

そこで、我々は、以下の 3 ケースに分けて、データ数に応じて、広告ごとに適用する入札戦略を変更することとした。

-132-

6.

予測モデルのみ
今回手法

20.0 %
30.0 %

60.0 %
96.7 %

1. 広告のクリックが 0 超かつ売り上げ 0 超十分なデータがあると考え、vi には予測モデルから計算した広告の推定値を適用する
2. 広告のクリックが 0 超だが、売り上げ 0
売上データが存在しないため、予測モデルではな
く、過去実績値から vi を推定する。具体的には以下の式で決定する。
vi = min(1/広告のクリック数合計, 全体平均 cvr)
×全体平均売上単価/広告平均クリック単価(3)
上記の式 (3) のように vi 設定することによって、クリック単価の過去の実績が広告全体の平均値と比較して相対的に安い広告は入札額が上げられ、高い広告は入札額が下げられる。これによって、実務者運用視点から問題がある入札額の制御を防ぐことが可能となる。
3. 広告のクリックが 0
広告のクリックが 0 のケースでは、そもそも広告費用が発生していないため、当該広告の入札額を一律で 1.2 倍する制御を実施した。

5.

実務適用結果図 1 は、今回提案したアルゴリズムを実装し、構築したシステムをある一つのアカウントに実際に適用した例である。青色の線が同一月内における広告消費量の累計値を表し、赤い線が、当月における目標予算の値を表す。背景が赤く塗られた範囲は、本システムが適用された期間を表し、それ以外は従来ルールベースのロジックと人手によるオペレーションの組み合わせで入札額等が調整されている。図 1 に示した通り、本システムを導入したことによって、広告費用の消化量が増え、目標に追従した制御が行われていることが確認できた。
広告全体としては効率制約も遵守しており、本アルゴリズムを含むシステムを利用することで、入札額調整をより効率的に実施できることを実証できた。
− 実績広告費⽤(⽉次累積)− 理想的な消化ペース− ⽬標⽉次予算広告費用（月次累計）

表 1: 性能検証結果
予算達成率 KPI 遵守率計算実験

図 1: 入札額最適化システム適用結果

まずは、アルゴリズムの性能を仮想的なシミュレーション環境上で検証した。具体的には、過去の実績データから、広告の入札額に対する広告パラメータ (クリック率、コンバージョン率等) の予測モデルを構築し、決定した入札額に対して、予測モデルから乱数を生成し、アルゴリズムの性能を検証する。表 (1) は同一のシミュレーション環境において 30 回シミュレーションを実行し、シミュレーション期間内である 30 ステップ以内に、予算目標に達成できた予算達成率と、制約条件となる売上と広告費用の比率を表す KPI を守れた確率を集計した結果である。シミュレーション結果から、予算達成率、KPI 遵守率ともに従来手法よりも改善することが確認できた。

参考文献[1] X. Yang, Y. Li, H. Wang, D. Wu, Q. Tan,
J. Xu, and K. Gai. Bid optimization bymultivariable control in display advertising.
Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining, pp. 1966–1974, 2019.
[2] He, Y., Chen, X., Wu, D., Pan, J., Tan,Q., Yu, C., … Zhu, X. (2021). A Uniﬁed Solution to Constrained Bidding in Online Display Advertising. Proceedings of theACM SIGKDD International Conference onKnowledge Discovery and Data Mining, pp.
2993–3001, 2021.

-133-