第12章：広告クリック最適化

章概要

本章では、GoogleやFacebookなどのeコマースプラットフォームでの入札を行う方策を最適化し、収益を最大化する問題を扱う。これらのプラットフォームは、表示する広告に対して市場価値通りの対価を確実に得るために、洗練されたオークションを実施している。この問題のモデル化と方策の設計は、3種類の不確実性を表現する必要があるために複雑になる。すなわち、我々が行った入札で勝つ確率、その入札に勝つかどうかという結果、そして入札に勝った際に得られる収益、の3つである。

我々は3つの方策を検討する。最初の2つは比較的単純である。すなわち、すべての不確実な量に関する現在の推定値に基づいて最善の入札を選ぶ貪欲方策と、探索を促すためのその貪欲方策のランダム化版である。3つ目はより洗練されたもので、「知識勾配」として知られ、特定の入札を行うことによる情報の価値を最大化する。これには、ある入札から得られる学習による改善量の期待値を求める必要がある。知識勾配は比較的高度な確率計算を伴う。

ナラティブ

Googleのようなインターネットサイトに広告を出す企業は、自社の広告を目立つ位置(すなわち、スポンサー広告リストの上位)に表示させるために入札を行わなければならない。顧客が検索語を入力すると、Googleは自らの広告ワードリストに同じ(または類似の)検索語を登録しているすべての入札者を特定する。次にGoogleは、そのすべてのマッチした入札者を集め、各参加者の入札額に応じて並べ替え、オークションを実施する。入札額が高いほど、その広告がスポンサー広告リストの上位に配置される可能性が高くなり、クリックされる確率が高まる。図 12.1 は、”hotels in baltimore md”という検索語を入力した後に表示される例である。

顧客が広告をクリックすると、顧客がその企業のウェブサイトを訪れた際に費やす平均額を反映した期待収益が生じる。問題は、我々が入札応答曲線を知らないことである。図 12.2 は、あり得る応答曲線の集合を示している。我々の課題は、様々な入札額を試し、どの曲線が正しいかを学習することである。

図 12.2. 入札額が与えられたときに広告がクリックされる確率のあり得る事例。

まず、我々は各オークションの後で入札額を調整できると仮定する。これは、単一の応答(顧客がリンクをクリックしたかどうか)しか学習できないことを意味する。顧客が表示されたリンクを見てクリックしないことを決めた可能性もあれば、我々の入札額が低すぎて表示広告のリストにすら入っていなかった可能性もある。

我々の課題は、入札額を設定する方策を設計することである。目標は、製品やサービスの販売から得られる収益から、広告クリックに費やす金額を差し引いた純収益を最大化することである。

問題の枠組み

我々の3つの枠組み設定の質問に対する答えは以下の通りである。

評価指標: プラットフォームで宣伝された製品を販売することによる期待純収益(広告の運用に支払った金額を差し引いたもの)を最大化する。
決定: 広告にいくら入札するか。
不確実性: 入札が成功するかどうか、そして成功した入札から得られる収益額。

基本モデル

顧客が広告をクリックする確率を捉えるために、何らかのパラメータ化されたモデルを使用すると仮定する。この確率は、少なくとも広告にいくら入札したかに依存する。入札額が高いほど、広告はスポンサー広告リストの上位に表示され、顧客がクリックする可能性が高まる。$K^n = 1$を、$n$番目の顧客が広告をクリックした場合とする。

\[P^{click}(\theta_k,x) = Prob[K^{n+1}=1\vert \theta=\theta_k,x]\]

とし、ここで$Prob[K^{n+1}=1\vert \theta=\theta_k,x]$は以下のロジスティック関数で記述される。

\[\begin{align} Prob[K^{n+1}=1\vert \theta=\theta_k,x^n, H^n] = \frac{e^{\theta^{const,n}_k + \theta^{bid,n}_k x^n}}{1+e^{\theta^{const,n}_k + \theta^{bid,n}_k x^n}}. \label{eq:adclicklogisticregression} \end{align}\]

この関数は$\theta = (\theta^{const}, \theta^{bid})$によってパラメータ化されている。我々は$\theta$が何であるかを知らないが、サンプリングされた集合$\Theta = \lbrace \theta_1, \ldots,\theta_K\rbrace $のうちの一つであると仮定する。

状態変数

初期状態$S^0$には、$\theta$が取り得る値の集合である$\Theta = \lbrace \theta_1, \ldots, \theta_K\rbrace $、および顧客がリンクをクリックした際に得られる収益の初期推定値である$\Rbar^0$が含まれる。

動的状態変数$S^n$には、真の$\theta = \theta_k$が確率であるという$p^n_k$($p^n = (p^n_k)_{k=1}^K$を伴う)、そして$n$回のオークション後の広告クリックから得られる収益の推定値である$\Rbar^n$が含まれる。

したがって、我々の動的状態変数は

\[S^n = (\Rbar^n, p^n).\]

である。$n$回の観測後に$\thetabar^n = \sum_{k=1}^K p^n_k \theta_k,$を用いて$\theta$の点推定値を作成できることに注意されたい。

\[\thetabar^n = \sum_{k=1}^K p^n_k \theta_k,\]

しかし、これは$S^n$内の情報から計算できる統計量であるため、$\thetabar^n$を状態変数には含めない。

決定変数

我々の唯一の決定変数は入札額であり、これを$(n+1)$番目のオークションに対する入札額(1クリックあたり＄)である$x^n$として定義する。これまでと同様、$S^n$で表される我々が利用可能な情報の関数として入札額$x^n$を与える汎用方策を$X^\pi(S^n)$とすると、以下のように書ける。

\[x^n = X^\pi(S^n).\]

方策があらゆる制約を強制すると仮定する。例えば、入札額が負にならないように、あるいは大きくなりすぎないようにすることなどである。

外生情報

初期モデルでは、単一のオークションの結果のみを観測し、これを以下でモデル化する。

\[K^{n+1} = \begin{cases} 1 & \text{if the customer clicks on our ad,} \\ 0 & \text{otherwise.} \end{cases}\]

および、$n+1$番目のオークションから得られる収益である$\Rhat^{n+1}$。これにより、完全な外生情報変数は

\[W^{n+1} = (\Rhat^{n+1},K^{n+1}).\]

となる。

遷移関数

この問題の遷移関数は、本書の他の遷移関数よりもはるかに複雑に見えるだろうが、これはパラメータベクトル$\theta$の不確実性に関する信念を更新しているためである。すべての遷移方程式は比較的容易にコード化できることを強調しておく必要がある。

顧客が広告をクリックした際の推定収益は、以下を用いて更新する。

\[\begin{align} \Rbar^{n+1} = \begin{cases} (1-\alpha^{lrn}) \Rbar^n + \alpha^{lrn} \Rhat^{n+1} & \text{if } K^{n+1} = 1, \\ \Rbar^n & \text{otherwise.} \end{cases} \label{eq:adclicktransition1} \end{align}\]

したがって、クリックが発生したときのみ推定収益を更新する。パラメータ$\alpha^{lrn}$は、0と1の間の平滑化パラメータ(「学習率」と呼ばれることもある)であり、事前に固定しておく。

次に、確率$p^n_k$の更新を扱う。状態、決定、外生情報の履歴を$H^n$とする。

\[H^n = (S^0,x^0,W^1, S^1, x^1, \ldots, W^n, S^n, x^n).\]

これを用いて以下のように書く。

\[p^n_k = Prob[\theta=\theta_k\vert H^n].\]

履歴$H^n$による条件付けの読み方は、「$p^n_k$は$n$回の観測後に我々が知っていることが与えられたときの$\theta = \theta_k$の確率である」というものである。次に、ベイズの定理を用いて以下のように書く。

\[\begin{align} p^{n+1}_k &= Prob[\theta=\theta_k\vert W^{n+1}, H^n] \nonumber\\ &= \frac{Prob[K^{n+1}\vert \theta=\theta_k,H^n]Prob[\theta=\theta_k\vert H^n]}{Prob[K^{n+1}\vert H^n]}. \label{eq:adclicktransition2} \end{align}\]

履歴$H^n$には決定$x^n$が含まれており、これらの決定を行う方策が与えられれば、その決定は状態$S^n$の直接的な関数である(これは履歴$H^n$の関数でもある)ことを思い出してほしい。ここで式$\eqref{eq:adclicklogisticregression}$のロジスティック曲線を用いて以下のように書く。

\[\begin{align} Prob[K^{n+1}=1\vert \theta=\theta_k,H^n] &= Prob[K^{n+1}=1\vert \theta=\theta_k, x^n]\nonumber\\ &= \frac{e^{\theta^{const}_k + \theta^{bid}_k x^n}}{1+e^{\theta^{const}_k + \theta^{bid}_k x^n}}. \label{eq:adclicktransition2a} \end{align}\]

次に以下に注意する。

\[\begin{align} Prob[\theta=\theta_k\vert H^n] = p^n_k. \label{eq:adclicktransition2b} \end{align}\]

最後に、分母は以下を用いて計算できることに注意する。

\[\begin{align} Prob[K^{n+1}\vert H^n] = \sum_{k=1}^K Prob[K^{n+1}\vert \theta=\theta_k,H^n] p^n_k. \label{eq:adclicktransition2c} \end{align}\]

$\theta$の取り得る結果をサンプリングされた表現で表したことが、ここで役立っている。たとえ$\theta$が(ここではそうだが、あくまで今のところ)2次元しか持たない場合であっても、$\theta$に対する多変量分布の2次元積分を実行することは問題になりかねない。

式$\eqref{eq:adclicktransition2a}$–$\eqref{eq:adclicktransition2c}$により、$\eqref{eq:adclicktransition2}$内の確率に対するベイズ更新方程式を計算できる。式$\eqref{eq:adclicktransition1}$–$\eqref{eq:adclicktransition2}$は我々の遷移関数を構成する。

\[S^{n+1} = S^M(S^n,x^n,W^{n+1}).\]

目的関数

まず、単一期間の利益関数を以下のように書く。

\[C(S^n,x^n,W^{n+1}) = (\Rhat^{n+1} - x^n) K^{n+1},\]

これは、顧客が広告をクリックしなければ($K^{n+1} = 0$)何も得られないことを意味する。顧客が広告をクリックすれば($K^{n+1} = 1$)、$\Rhat^{n+1}$で与えられる収益を得るが、同時に広告クリックに対して入札した金額、すなわち入札額$x^n$も支払わなければならない。

最終的には期待貢献を取ることになり、これを以下のように書く。

\[\E \{C(S^n,x^n,W^{n+1})\vert S^n\} = \E \{(\Rhat^{n+1} - x^n) K^{n+1} \vert S^n\}.\]

この期待値には3つの確率変数が隠れている。

$\theta$。分布は$p^n = (p^n_1, \ldots, p^n_K)$($S^n$に含まれる)。
$K^{n+1}$。ただし$P^{click}(\theta,x) = Prob[K^{n+1}=1\vert \theta,x]$。
$\Rhat^{n+1}$。これは$K^{n+1}=1$の場合、何らかの未知の分布から観測され、$K^{n+1}=0$の場合は$\Rhat^{n+1}=0$である(顧客が広告をクリックしなければ収益は得られない)。

期待値を3つの入れ子になった期待値に分解できる。

\[\E \{(\Rhat^{n+1} - x^n) K^{n+1} \vert S^n\} = \E_{\theta} \E_{K\vert \theta} \E_{\Rhat} \{(\Rhat^{n+1} - x^n) K^{n+1} \vert S^n\}.\]

まず、$\Rhat$に関する期待値を取ることから始める。ここでは単に$\E \lbrace \Rhat^{n+1}\vert S^n\rbrace = \Rbar^n$を用いる($\Rbar^n$は状態変数$S^n$に含まれていることを思い出されたい)。これにより以下のように書ける。

\[\E \{(\Rhat^{n+1} - x^n) K^{n+1} \vert S^n\} = \E_{\theta} \E_{K\vert \theta} \{(\Rbar^n - x^n) K^{n+1} \vert S^n\}.\]

次に、与えられた$\theta$に対して$K^{n+1}$に関する期待値を以下を用いて取る。

\[\E_{K\vert \theta} \{(\Rbar^n - x^n) K^{n+1} \vert S^n\} = (\Rbar^n - x^n) P^{click}(\theta,x).\]

ここでは、$K^{n+1}=0$の場合$(\Rbar^n - x^n) K^{n+1}=0$であるという事実を用いた。

最後に、$\theta$に関する期待値を以下を用いて取る。

\[\E_{\theta} \{(\Rbar^n - x^n) P^{click}(\theta,x^n) \vert S^n\} = \sum_{k=1}^K (\Rbar^n - x^n) P^{click}(\theta=\theta_k,x^n) p^n_k.\]

$\Cbar(S^n,x)$を期待貢献とする。すなわち、

\[\Cbar(S^n,x) = \E_{\theta} \E_{K\vert \theta} \{(\Rbar^n - x^n) K^{n+1} \vert S^n\}.\]

これで我々の目的関数は以下のように書ける。

\[\max_\pi \E_{S^0} \E_{W^1, \ldots, W^n\vert S^0} \left\{\sum_{n=0}^N C(S^n,X^\pi(S^n),W^{n+1})\vert S_0\right\}.\]

$S_0$による条件付けは、事前分布$p^0_k = Prob[\theta=\theta_k]$をモデルに伝える方法であることに注意されたい。これまでと同様、真の値$\theta$、観測されたクリック$K^n$、および収益$R^n$のシミュレートされたサンプルにわたって平均を取ることで期待値を近似する。

不確実性のモデル化

我々には3種類の不確実性がある。広告クリック$K^{n+1}$、$K^{n+1}=1$の場合に得られる収益$\Rhat^{n+1}$、そして$\theta$の真の値である。$\Rhat^{n+1}$は実際のデータストリームから単に観測されると仮定するため、これらの確率変数に対する正式な確率モデルは必要ない。$K^{n+1}$は我々のロジスティック関数

\[\begin{align} P^{click}(\theta,x) &= P[K^{n+1} = 1\vert \theta,x=x^n] \nonumber \\ &= \frac{e^{\theta^{const} + \theta^{bid} x}}{1+e^{\theta^{const} + \theta^{bid} x}}, \label{eq:adclicklogistic} \end{align}\]

によって記述されると仮定するが、これは単に当てはめられた曲線に過ぎないことを認識しておくことが重要である。$K^{n+1}$の値はデータから観測されるため、その分布がロジスティック回帰と正確に一致する保証はない。

最後に、$\theta \in \Theta = \lbrace \theta_1, \ldots, \theta_K\rbrace $であると仮定するが、これも近似である。サンプリングされた集合という要件を緩和する方法はあるが、その論理は教育的価値をあまり高めることなく、いくぶん複雑になる。

方策の設計

学習のための3つの方策を検討する。

純粋な活用 – ここでは、現在の推定値に基づいて最善と思われる入札を常に行う。
励起方策 – 活用方策にランダムノイズ項を加えることで探索を導入し、システムが最善と思われる領域の近くで探索するように仕向ける(これは状態と決定が連続的である工学分野で人気がある)。
情報価値方策 – 入札を行いその結果を学習することによる情報の価値を最大化する。

純粋な活用

オンライン方策の出発点は常に純粋な活用であるべきであり、これは我々ができる最善を尽くすことを意味する。これを計算するために、まず以下を用いる。

\[\E \{\Rhat^{n+1} K^{n+1}\} = \E \{\Rhat^{n+1}\vert K^{n+1} = 1\} Prob[K^{n+1}=1\vert \theta=\theta_k] = \Rbar^n P^{click}(\theta,x).\]

最善の入札を見つけるために、入札$x$に関する導関数を求める(いくぶんの代数計算の後で)。

\[\frac{d \Cbar(x)}{d x} = (\Rbar^n - x)\frac{d P^{click}(\theta,x)}{d x} - P^{click}(\theta,x)\]

ここで

\[\frac{d P^{click}(\theta,x)}{d x} = \frac{\theta_1 e^{-\theta_0 - \theta_1 x}}{(1+e^{-\theta_0 - \theta_1 x})^2}.\]

さて、以下を満たす入札$x^\ast $を見つけたい。

\[\left.\frac{d \Cbar(x)}{d x}\right\vert _{x=x^\ast } = 0.\]

図 12.3 は$\frac{d \Cbar(x\vert \theta)}{d x}$を入札額$x$に対して示しており、正の値から始まり負の値へと転じる挙動を示している。それがゼロと等しくなる点が最適な入札額であり、この点は数値的に容易に求めることができる。$d \Cbar(x)/dx = 0$を満たす入札額$x^\ast $を$X^{explt}(S^n)$とする。

これは、方策を計算するために数値アルゴリズムを実行しなければならないことを意味する。これはCFAクラスに属する貪欲方策であるが、調整可能なパラメータは持たない。

励起方策

我々の純粋な活用方策の潜在的な限界は、$\theta$の正しい値を学習するプロセスを助けるために、より広い範囲の入札額を試すことの価値を無視している点である。よく用いられる戦略は、工学において「励起」として知られるノイズ項を加えることであり、これにより以下の方策が得られる。

\[X^{excite}(S^n\vert \rho) = X^{explt}(S^n) + \varepsilon(\rho)\]

ここで$\varepsilon(\rho) \sim N(0,\rho^2)$である。この方策において、$\rho$は方策における探索量を制御する調整可能なパラメータである。これが小さすぎると、探索が十分でない可能性がある。これが大きすぎると、最適から遠く離れた入札額を選択することになり、学習からの恩恵を得られない可能性がある。

情報価値方策

純粋活用方策と刺激方策は、いずれも比較的単純なものであった。ここでは、将来における情報の価値を最大化する方策を検討する。これは合理的な考え方に思えるが、現在の情報が将来行うかもしれない決定にどのように影響するかを考える必要があり、これは少し難しくなる。

我々の活用方策は、$n$回の実験後の推定パラメータ$\theta^n$を正しい値であると仮定し、この推定値に基づいて入札を選択する。ここで、$x^n=x$を入札し、$K^{n+1}$と$\Rhat^{n+1}$を観測し、この情報を用いて$\theta^{n+1}$および$\Rbar^{n+1}$の更新された推定値を得るとしよう。これらの更新された推定値を用いて、より良い決定を下すことができる。我々は、決定からの情報の価値の改善が最大となる入札$x$を選びたいが、実際に入札を行うまで$W^{n+1} = (\Rhat^{n+1},K^{n+1})$の結果は分からないことを認識しておく必要がある。

$x^n=x$を入札し$W^{n+1} = (\Rhat^{n+1},K^{n+1})$を観測すると仮定した場合の、$\theta$の更新された推定値を$\theta^{n+1}(x^n,W^{n+1})$とする。これは確率変数である。なぜなら、我々は第$n+1$回目のオークションに対して入札$x^n=x$を行うことを考えているが、まだ入札を行っておらず、したがってまだ$W^{n+1}$を観測していないからである。

分析を簡略化するため、確率変数は確率$P^{click}(\theta,x)$で$K^{n+1} = 1$、確率$1-P^{click}(\theta,x)$で$K^{n+1} = 0$であると仮定する。次に、広告クリックから得られる収益の推定値は安定しており、$\Rbar^{n+1} \approx \Rbar^n$であると仮定する。

これは近似先読みモデルと考えることができ、この場合$\Rbar^n$は変化しない。この先読みモデルにおける外生情報を次のように書くことができる。

\[\Wtilde^{n,n+1}=\Ktilde^{n,n+1},\]

ここで二重上付き文字$(n,n+1)$は、時刻$n$に作成された先読みモデルにおいて、時刻$n+1$に何が起こるかを見ていることを表している。確率変数$\Ktilde^{n,n+1}$は、実際に誰かが広告をクリックしたかどうかの観測ではなく、我々の先読みモデルの中でシミュレートしている「起こるかもしれない」広告クリックである。先読みモデル内の変数にはすべてチルダを付けること、そしてこれらの変数は$n$（先読みモデルを開始する時刻）と$n+1$（先読みモデルにおいて1時間期先を見ているため）でインデックス付けされることを覚えておいてほしい。

次に、確率$p^n_k = Prob[\theta=\theta_k\vert H^n]$に対する更新式$\eqref{eq:adclicktransition2}$を用いる。これらの更新された確率は、$\Ktilde^{n,n+1}$への依存性を捉えるために$\ptilde^{n,n+1}_k(\Ktilde^{n,n+1})$と書くことができる（式$\eqref{eq:adclicktransition2}$は$\Ktilde^{n,n+1}=1$について書かれている）。$\Ktilde^{n,n+1}$は2つの結果（0または1）を取り得るため、$\ptilde^{n,n+1}_k(\Ktilde^{n,n+1})$には2つの可能な値が存在することになる。

ここで、上で説明した純粋活用方策$X^{explt}(S^n\vert \theta^n)$を実行するが、これを近似先読みモデルの中で行うとする（ここで$\Rbar^n$の変化を無視する）。先読みモデルにおける我々の状態を$\Stilde^{n,n+1}$とし、次のように与えられるとする。

\[\Stilde^{n,n+1}(\Ktilde^{n,n+1}) = (\Rbar^n, \ptilde^{n,n+1}(\Ktilde^{n,n+1})).\]

注意してほしいのは、$\Ktilde^{n,n+1}$は確率変数であるため（我々はまだ時刻$n$にいる）、$\Stilde^{n,n+1}(\Ktilde^{n,n+1})$もまた確率変数であり、そのため結果$\Ktilde^{n,n+1}$への明示的な依存性を書いているということである。

この先読みモデルの考え方は、チェスのようなゲームをプレイしていると想像するとよい。ある手（我々の場合は入札$x^n$）を考え、その手を実際に指す前に、将来何が起こり得るかを考えるのである。この問題では、我々の将来には2つの結果しかない（顧客が広告をクリックするかどうか）ため、$\Stilde^{n,n+1}$には2つの可能な値があり、これが2組の更新された確率$\ptilde^{n,n+1}(K^{n+1})$を生み出す。

最後に、これは最適な近視眼的入札（純粋活用方策を用いた場合）$X^{explt}(\Stilde^{n,n+1})$にも2つの値が存在することを意味する。我々が将来得るであろう期待貢献は、$\Ctilde(\Stilde^{n,n+1},\xtilde^{n,n+1})$によって与えられ、ここで$\xtilde^{n,n+1}$（これは我々が将来行おうと考えている決定である）は次のように与えられる。

\[\xtilde^{n,n+1} = X^{explt}(\Stilde^{n,n+1}).\]

これは、最適な決定が2通り存在し得ることを意味し、したがって期待貢献$\Ctilde(\Stilde^{n,n+1},X^{explt}(\Stilde^{n,n+1}))$にも2つの異なる値が存在することになる。簡潔にするため、これらを（$\Ktilde^{n,n+1} = 1$の場合）$\Ctilde^{n,n+1}(1)$、（$\Ktilde^{n,n+1} = 0$の場合）$\Ctilde^{n,n+1}(0)$と呼ぶことにする。これらは、現在我々が知っている情報を前提として将来起こり得る期待貢献であると考えてほしい。最後に、$\Ktilde^{n,n+1}$について期待値を取ることで、今まさに入札$x^n=x$を行うことの期待貢献を得ることができ、これは次式で計算できる。

\[\Cbar^n(x) = \sum_{k=1}^K \big(P^{click}(\theta=\theta_k,x) \Ctilde^{n,n+1}(1) + (1-P^{click}(\theta=\theta_k,x)) \Ctilde^{n,n+1}(0)\big) p^n_k.\]

したがって我々の方策は、$\Cbar^n(x)$を最大化する入札$x$を選ぶことである。入札を集合$\Xcal = \lbrace x_1, \ldots, x_M\rbrace $に離散化すると仮定しよう。我々の情報価値方策は次のように書くことができる。

\[X^{VoI}(S^n) = \argmax_{x\in\Xcal} \Cbar^n(x).\]

これは直接先読み近似（DLA）クラスの方策であることに注意されたい。

情報価値方策は非常に強力である。計算はより難しくなるが、調整可能なパラメータは一切持たない。例えば、結果が2つより多い場合にこの計算を行うことを想像してみてほしい。例えば、$\Rbar^n$を一定に保つという簡略化を行っていなければ、この状態変数もまた変化していることを認識しなければならなかっただろう。

参考までに触れておくと、我々はさまざまな学習方策の比較を数多く行ってきたが、1ステップ先読みの情報価値はしばしば非常にうまく機能する。ここでこの設定を使用したのは、導出が大幅に簡単になるためである。

ここで一つ注意が必要である。結果が0か1かである学習問題は、単一の実験が非常に少ない情報しか提供しない問題である。むしろ、決定を行う（すなわち入札を設定する）と、それを例えば$M$回のオークションにわたって観測すると仮定する方がよい。これは、$\Ktilde^{n,n+1}$が0から$M$の間の数になり得ることを意味する。数$M$は調整可能なパラメータとなり、計算は少し複雑になる（2つの実現値ではなく$M+1$個の実現値について和を取らなければならない）が、このアプローチは非常にうまく機能し得る。

拡張：単純な属性を持つ顧客

顧客の所在地を地域または最寄りの主要都市まで把握しているとし、これを$L$で表すとする。各地域の挙動が異なると考えるならば、顧客が場所$L=\ell$出身である場合、$\theta$を$\theta_\ell$でインデックス付けすることができる。これは、場所が1,000ある場合、1,000個のモデルを推定しなければならないことを意味し、すなわち$\theta = (\theta^{const},\theta^{bid})$の値が1,000個必要になるということである。

代替的なアプローチとして、次の形式のモデルを指定することが考えられる。

\[Prob^n[K^{n+1}=1\vert \theta] = \frac{e^{U(x,L\vert \theta)}}{1+e^{U(x,L\vert \theta)}}.\]

ここでは、効用関数として次を用いる。

\[U(x,L\vert \theta) = \theta^{const} + \theta^{bid}x + \sum_{\ell=1}^L \theta^{loc}_\ell I_{\ell=L}.\]

これはより簡潔なモデルである。なぜなら、ここでは定数項$\theta^{const}$と入札係数$\theta^{bid}$が場所に依存しないと仮定しているからである。代わりに、単にシフト$\theta^{loc}_\ell$を加えているだけである。したがって、依然として1,000個のパラメータ（場所係数）を推定する必要があるが、以前は各場所$\ell \in \lbrace 1, \ldots, L\rbrace $について$\theta^{const}_\ell$と$\theta^{bid}_\ell$の合計2,000個のパラメータを推定する必要があった。

何を学んだか

これも純粋な学習問題である（第4章の糖尿病問題も純粋な学習問題であった）が、今回は非線形信念モデルを用いており、価格への反応を決定する未知パラメータ$\theta$についてはサンプリングモデルを用いている。
遷移関数には、未知パラメータ$\theta$が特定の値$\theta_k$に等しいという確率$p^n_k$に関する信念のベイズ更新が含まれる。
不確実性には3つの形態がある。すなわち、入札価格に対して誰かが広告をクリックするかどうか、広告をクリックしたことから得られる収益（例えば、顧客が製品を購入したかどうか）、そして未知パラメータ$\theta$によって捉えられる市場反応に関する不確実性である。
我々は、純粋活用方策、（活用方策からの推奨価格を単にランダム化する）刺激方策、そして情報の価値を最大化するナレッジグラディエント方策を例示する。

演習問題

復習問題

顧客が広告をクリックしたかどうかを与える確率変数$K^n$に対して、どのような確率モデルが仮定されているか。
未知の（したがって不確実な）パラメータベクトル$\theta$に対して、どのような確率モデルを仮定したか。
顧客が広告をクリックした際に得られる収益$\Rhat^{n+1}$に対して、どのような確率分布を仮定したか。
遷移関数を構成する式の式番号を挙げよ。
初期状態$S^0$にはどのような確率的情報が含まれているか。
刺激方策を作るためにノイズ項$\varepsilon(\rho)$を加えることで何が達成されるか。これは特にどのパラメータを特定するのに役立つか。
情報価値方策の背後にある論理を言葉で説明せよ。顧客が広告をクリックするかどうかを学習することが、我々が行う予定の入札を変化させない場合、その価値はどうなるか。

問題解決演習

推薦システムその1 - 信念モデル - あなたは、顧客がウェブサイトをスクロールしている際に宣伝する商品を推薦する推薦システムの設計を手伝うことになった。顧客はサインインする必要があるため、$n$番目の顧客を、以下を含む属性ベクトル$a=a^n$によって識別することができる。

$a_1$	性別（2種類）。
$a_2$	年齢層 $(0$–$10, 11$–$20, \ldots, 70$–$100)$（8種類）。
$a_3$	デバイスの種類（スマートフォン、ノートパソコン、タブレット）（3種類）。
$a_4$	地域（200）。
$a_5$	一意のID（メールアドレス）（1億）。

テキスト記事を推薦していると想像してほしい。$n$番目の顧客に対して推薦する記事が、以下を含む属性$b=b^n$を持つと仮定する。

$b_1$	ニュース、スポーツ、芸術、ビジネス、料理、不動産（6種類）。
$b_2$	サブカテゴリ：ニュースの場合は国際、国内（国別）、地域（国内の地域）；スポーツの場合はスポーツ種目別、さらにチーム（または選手）別；以下同様（合計500）。
$b_3$	ソース（ウェブサイト、新聞、...）（5つのソース）。
$b_4$	著者（2,000）。
$b_5$	記事の一意のID（600万）。

我々が推定したいのは次のものである。

$P(b^n\vert a^n)$ = 属性$a^n$を持つ$n$番目の顧客が、属性$b^n$を持つ記事のリンクをクリックする確率。

顧客$a^n$が到着したとき、我々は集合$\Bcal^n$（$n$番目の顧客が到着した時点で利用可能な記事の集合であり、この集合は時間とともに変化する）からニュース記事を選ばなければならないと仮定する。我々は、この顧客が当該ニュース記事をクリックする確率を最大化する属性$b\in\Bcal^n$を持つ記事を選びたい。我々の方策は、属性$b^n$を持つ特定の記事を選ばなければならない。

理想的には、ユーザー$a^n_5$が記事$b^n_5$を選択する確率である$P(b^n_5\vert a^n_5)$を求めたいところだが、ユーザーと記事が多すぎて、この確率について妥当な推定を得ることができない。要素$a_1, a_2, a_3$と$a_4$のみを考慮した場合でも、9,600通りの組み合わせが存在し、これら最初の4つの要素それぞれについて平均でおよそ10,000人が該当することになる。以下では、$a_1$と$a_2$のみを使用すると仮定し、これは16種類の人物を意味する。

我々は、検討したい$a$と$b$の要素から構成される特徴量の集合$\Fcal$を作成する。ここでは要素$\lbrace a_1,a_2,b_1,b_2,b_3\rbrace $のみを使用し、これから特徴変数の集合$\phi_f(a,b),~f\in\Fcal$を構成する。これら5つの要素はすべてカテゴリカルであるため、最も基本的な特徴量は指示変数である。例えば、性別属性$a_1$については2つの性別があり、そこから次の2つの特徴量を作成する。

$$ \phi_{male}(a) = \begin{cases} 1 & \text{if } a_1 = male, \\ 0 & \text{otherwise.} \end{cases} \qquad \phi_{female}(a) = \begin{cases} 1 & \text{if } a_1 = female, \\ 0 & \text{otherwise.} \end{cases} $$

この基本的な特徴量に限定すると、属性$a_1,a_2,b_1,b_2,b_3$の各要素の取り得る値ごとに1つの特徴量を持つことになる。

我々のプロセスは、最初の顧客が属性ベクトル$a^1$でログインした時点から始まり、その時点で、このユーザーに表示する記事の属性$b^1$を決定し、その後$Y^1$を観測する必要がある。ここで、顧客が記事をクリックすれば$Y^1 = 1$、そうでなければ0である。この情報は、更新された状態$S^1$を作成するために使用され、その後顧客$a^2$を観測する。

もし$a^n$が$n$番目の顧客の属性であるならば、我々の決定は、我々が$S^n$と表す既知の情報を用いて$b^n$を選択することである。我々の目標は、この問題をモデル化し、$b^n$を決定する方策$B^\pi(S^n)$を設計することである。

最初の課題は、信念モデルを構築することである。

属性$\lbrace a_1,a_2, b_1,b_2,b_3\rbrace $を用いて$P(b\vert a)$に対するルックアップテーブル信念モデルを使用する場合、推定しようとしているパラメータの数はいくつか?
代わりに、ロジスティック回帰の使用を検討しよう。まず効用関数を次のように定義する $$ U(a,b\vert \theta) = \sum_{f\in\Fcal} \theta_f \phi_f(b\vert a), $$ ここで$\Fcal$は要素$\lbrace a_1,a_2,b_1,b_2,b_3\rbrace $から構築できる基本的な特徴量の集合である。次に、次式を用いて記事をクリックする確率に対するロジスティック回帰モデルを作成する $$ P(Y=1\vert a,b,\theta) = \frac{e^{U(a,b\vert \theta)}}{1+e^{U(a,b\vert \theta)}}. $$ 基本的な指示変数のみを使用すると仮定した場合、ベクトル$\theta$の次元数はいくらか?
(b)のパラメトリックモデルにおけるパラメータの数が、(a)のルックアップテーブルモデルにおけるパラメータの数よりもはるかに少ないことを認識した上で、なぜロジスティック回帰のようなパラメトリックモデルの代わりにルックアップテーブル信念モデルを使う人がいるのだろうか?各タイプの信念モデルの長所と短所を論じよ。
ここで我々は$\theta$を推定する必要がある。ベクトル$\theta$の取り得る値のサンプルを生成し、それを$\lbrace \theta_1, \ldots, \theta_k, \ldots, \theta_K\rbrace $として表すとする。ここで各$\theta_k$は要素$\theta_{kf},~f\in\Fcal$を持つベクトルである。事前確率$p^0_k = 1/K$から始める。次に、最初の顧客の属性$a^1$を観測し、その後属性$b^1$を持つ記事を表示するという決定を行う(これが我々の決定変数である)と仮定する。$p^n_k$を知っているものとして、属性$a^{n+1}$を持つ顧客を観測し、属性$b^{n+1}$を持つ記事を選択した後に結果$Y^{n+1} = 1$を観測した後の$p^{n+1}_k$を計算するベイズの定理を書き出しなさい。

推薦システムその2 - システムモデル - ここでは問題を構成する5つの要素すべてをモデル化する。
1. 決定前状態$S^n$と決定後状態$S^{b,n}$の要素を示せ。
2. この過程には2種類の外生情報が存在する。それらは何か?
3. 時刻0で知っている情報から始めて、3番目の顧客の到着まで(それは含まない)の状態(決定前・決定後)、決定、および各種の外生情報の系列を書き出せ。それらが発生する順序で、適切な添字を付けて書くこと(例えば$n$と$n+1$の区別)。
4. 遷移関数を表す方程式を書き出せ。
5. (方策の種類を specify せずに)最良の方策$B^\pi(S^n)$を求めるための目的関数を書き出せ。
推薦システムその3 - 方策設計 - 最後に、方策の設計を試みる。$\theta$の取り得る値が$K=20$個あると仮定する。
1. まず、$\theta = \theta_k$を知っているものとする。$\theta = \theta_k$が与えられたとき、選ばれる確率を最大化する属性$b\in\Bcal^n$を選択する純粋な活用(exploitation)方策を書き出せ。
2. 次に、$\theta=\theta_k$を知らないものとする。代わりに、確率$p^n_k$で$\theta=\theta_k$であるとする。$\theta$を確率変数として扱わなければならない(a)の方策を書き直しなさい。どこかに期待値を挿入する必要がある。
3. (b)の方策は計算コストが高すぎると見なされるかもしれない。確率変数$\theta$をその期待値 $$ \thetabar^n = \E^n \theta_k = \sum_{k=1}^K \theta_k p^n_k. $$ で置き換えることで、これを簡略化できる。この点推定値を用いて(b)の方策を書き直せ。記事をクリックする確率が0.5より大きい記事のみを見ていると仮定する。(c)の点推定値を用いて計算した記事のクリック確率は、(b)の期待値を用いて得られる推定値とどのように比較されると考えられるか?
4. 区間推定方策では、例えば、選択の価値の推定値の95パーセンタイルを用いる。$\rho$を目的のパーセンタイルとし、それは0.05単位に丸める必要があると仮定する($\theta$に対して$K=20$個の取り得る値を選んでいるため)。点推定値ではなく$\rho$番目のパーセンタイルの確率を最大化する属性ベクトル$b$を選択する方策を設計する方法を示し、広告クリックの総数を最大化するための最適な$\rho$の値を求める目的関数を与えよ。