## 定義 リアルタイム入札(Real-Time Bidding, RTB)とは、オーディエンスがWebサイトやモバイルアプリ(メディア)を閲覧するタイミングごとに、広告枠の売買をオークション形式でそのつど行う仕組みである。オーディエンスの閲覧が発生すると広告リクエストがアドエクスチェンジ(広告の取引所)に飛び、アドエクスチェンジは広告主向けの広告配信事業者(Demand Side Platform, DSP)各社に入札リクエストを送ってオークションを実施する。この一連の流れは媒体の閲覧から広告表示まで100ミリ秒程度で完了し、DSPは50ミリ秒以内に入札しなければならない。落札方式は、最高額入札者が入札額をそのまま支払うファーストプライスオークション(封印入札一位価格方式)が主流になりつつある。以前主流だったセカンドプライスオークション(2番目に高い入札額を勝者が支払う方式)は、多段階オークションとの相性の悪さや、オークショナーが2番目に高い入札金額を偽って過剰請求できるリスクから、ファーストプライスオークションへの移行が進んでいる。(Source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 12 オンライン広告における機械学習]] §12.1.1) ## DSPの行動方策と最適化問題 DSPの行動方策として代表的なのは、限られた予算で顧客(広告主)が得る広告効果を最大化する方策であり、これには(1) 広告を表示したときのオーディエンスのレスポンス予測、(2) 広告枠の市場価格の予測、(3) 予算制約下での入札金額の最適化、という3つの機能が必要になる。ファーストプライスオークションでは、財の評価額と同じ金額で入札すると勝っても余剰(経済学でいう効用)がゼロになるため、評価額からどれだけ下げて入札するかが最適な入札金額を決める核心的な問いになる。買い手によって評価額が異なるのは、同じ広告枠でも広告主が置かれた状況(モバイルゲームのユーザーをその場で獲得したいか、産業機器の見込み顧客を獲得したいか等)によって価値が異なるためであり、この前提を私的価値(private value)と呼ぶ。 オークションが1日に何億回と繰り返されることから、他の買い手の最高入札金額 $z > 0$ を確率密度分布 $p_z(z)$(市場価格の分布)として扱い、入札金額 $b$ を決めたときの勝率 $w(b)$ をこの分布の累積分布関数 $w(b) = \int_0^b p_z(z)dz$ として定義する。市場価格は広告枠の種類やオーディエンスの属性に依存するため、実際には入札リクエスト $x$ に条件づけた勝率関数 $w(x, b)$ を使う。オーディエンスのレスポンス $y \in \{0, 1\}$ を金額換算した値 $v$ を用いると、1回のオークションの効用は勝ったときに $vy - b$、負けたときに0となる。N回のオークションの期待効用最大化は、入札リクエスト $x_i$ に対する反応確率を返す関数 $f(x_i)$ を用いて次の制約付き最適化問題として定式化できる。 $\underset{b_1 \ldots b_N}{\text{maximize}} \sum_{i=1}^N \left[ v f(x_i) - b_i \right] w(x_i, b_i) \quad \text{subject to} \quad \sum_{i=1}^N b_i w(x_i, b_i) \le B$ $w(x, b)$ に2階微分可能な関数を選んでおくと、ニュートン法で1ミリ秒未満の計算時間で解が求まり、リアルタイムオークションのレイテンシー制約(広告主あたり50ミリ秒以内の入札)を満たせる。この定式化を実装するには、レスポンス予測 $f(x)$ を担う[[CTR予測]]・CVR予測モデルと、勝率関数 $w(x, b)$(市場価格分布の予測)を担うモデルの2つが必要になる。(Source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 12 オンライン広告における機械学習]] §12.1.2-§12.2.2, §12.3.2) ## 横断的知見 1 ソース目のため、複数ソースの突き合わせによる横断的知見は今後の蓄積に委ねる。ただし本書内の既存概念とは明確な接続点がある。オークションが「1日に何億回」も繰り返されるという性質は、確率分布を用いた統計的な扱いを可能にする点で[[多腕バンディット]]が前提とする「試行の繰り返し」と構造的に似ているが、RTBの各オークションは独立した一回勝負の制約付き最適化問題として解かれる点で、逐次的に事後分布を更新しながらアーム選択を行うバンディット問題とは異なる。この対比は、[[CTR予測]]の横断的知見で扱うLogged Bandit Feedbackの議論(ch.12 §12.4.1)を通じて多腕バンディット概念とより具体的に接続する。また、本概念が扱う「予測を用いた事前の意思決定最適化」は、[[因果効果の推定]]が扱う「施策実施後の効果の事後的な統計的検証」とは異なる、予測を意思決定に繋げるもう1つの回路である。両者の対比は[[因果効果の推定]]の横断的知見で扱う。 ## 未解決の問い - ファーストプライスオークションへの移行は「セカンドプライスオークションとの相性の悪さ」「オークショナーの不正請求リスク」の2点から説明されるが、この移行がDSP側の最適入札戦略(評価額からの値引き幅の決め方)に与えた影響の定量的な分析は本ソースの範囲外。 - 私的価値(private value)の前提のもとでは買い手ごとに評価額が異なるが、広告主が複数存在する場合に評価額の分布そのものをどう推定するかは本ソースでは扱われていない。 - $w(x, b)$ に選ぶ「2階微分可能な関数」の具体例(対数正規分布のCDF等)とニュートン法の収束性の関係は、本ソースでは名前が挙がるのみで数値的な検証には立ち入らない。 - DSPが得るマージン(利益)を最大にする方策など、広告効果最大化以外のDSPの行動方策は脚注で言及されるのみで、定式化は本章の範囲外とされている。 ## 関連 - source: [[@2021__OReillyJapan__仕事ではじめる機械学習 - Chapter 12 オンライン広告における機械学習]] - concept: [[CTR予測]](本概念の最適化式が必要とするレスポンス予測モデル) / [[多腕バンディット]](繰り返し試行を確率分布で扱う点で構造的に近い隣接概念) / [[因果効果の推定]](予測を意思決定に繋げるもう1つの回路との対比) ## 出典 - 有賀康顕・中山心太・西林孝, 『仕事ではじめる機械学習 第2版』, オライリー・ジャパン, 2021, 第12章, §12.1-§12.3.