執筆背景
反実仮想機械学習〜機械学習と因果推論の融合技術の理論と実践という本を読んで、オフ方策評価が非常に興味深いと感じた。
https://gihyo.jp/book/2024/978-4-297-14029-8
一方で、オフ方策評価の様々な推定量を理解するには数式を理解できる必要がありそうであった。私はあまり数式が得意でないがこの本を読んでいて、具体的な例を自分で考え推定量がどんな風に計算されるかシミュレーションすると理解しやすいのではないかと感じた。そこで、それを実践してみることとした。
将来どのようなシミュレーションを行い、どんな風に理解を深めることができたかすぐに思い出せるようその内容をここに残す。
この記事の図の作成に利用したエクセルファイルは以下から閲覧できます。
https://docs.google.com/spreadsheets/d/1s9nwGrWbn9JcS4r9PYjkcjRRjIZU09JRldoKIH-ejjc/edit?gid=0#gid=0
問題設定
EC サイトにおいて、各会員にクーポンを配信することで CVR が上がるかどうかを知りたいとする。これまでに、ある方策に従って各会員にクーポンを配信したログデータが蓄積されており、このログデータをもとに別の方策に従って配信したときの CVR を出来るだけ正確に推定したいとする。
これが例えばどんな状況か例を上げる。これまで10代の会員にはあまりクーポンを配信していなかったが、 サイト内のデータ分析から10代によりクーポンを配信した方が良いかもしれないと仮説を立てたとする。このとき、AB テストを行う前に本当に CVR が上がりそうか、上がるとしてどの程度かをこれまでの AB テストなどのログデータから推定したいという状況である。
会員は u \in \mathcal{U}=\{1, 2, 3, 4, \dots, n\} と表す。各会員の特徴量は x_u で表す。クーポン配信のパターンは配信しないまたは配信するの2つとし、 a \in \mathcal{A} = \{a0, a1\} と表す。各会員が購入したかどうかを報酬とし r=\{0, 1\} と表す。これまでの方策は \pi_0 、これから実施予定の方策は \pi と表す。推定したいのは報酬の期待値(直感的には CVR と解釈できる)であり、これは以下のように表せる。
\begin{equation}
\begin{split}
V(\pi) &= \frac{1}{n} \sum_{u \in \mathcal{U}} \mathbb{E}_{\pi(a_u | x_u) p(r_u | x_u, a_u)} [r_u] \\
&= \frac{1}{n} \sum_{u \in \mathcal{U}} \mathbb{E}_{\pi(a_u | x_u)} \left[ q(x_u, a_u) \right]
\end{split}
\end{equation}
ここで、 q(x_u, a_u) = \mathbb{E}_{p(r_u | x_u, a_u)} [r_u] は期待報酬関数である。
また、これまでの方策 \pi_0 により得られたログデータを以下のように表す。
\mathcal{D} = \{x_u, a_u, r_u\}_{u \in \mathcal{U}} \sim \prod_{u \in \mathcal{U}} \pi_0(a_u | x_u) p(r_u | x_u, a_u)
ここまで登場した数式の理解を深めるために、この推定したい CVR がどんな風に計算されるかシミュレーションしてみる。ここで、4人の会員のログデータが得られたとし、それぞれ異なる特徴量 x1, x2, x3, x4 を持つと仮定する。これは例えば特徴量を年代として、それぞれ10, 20, 30, 40代と考えることができる。a=a0 をクーポンを配信しない、a=a1 を配信すると対応付ける。4人の会員について真の期待報酬関数を以下のように仮定する。

この表が意味することは、例えば特徴量 x_u=x1 の会員 u=1 はクーポンを配信されてもされなくても購入確率は変わらず 0.1 であり、特徴量 x_u=x2 の会員 u=2 はクーポンを配信されないと購入確率は 0.3 だが配信されると 0.9 になるということである。実際にはこの値は分からないものであるため、オフ方策評価を使ってこれまでの方策でのログデータ \mathcal{D} から、これから実施予定の方策の性能を推定する。
また、これまでとこれから実施予定の方策の行動選択確率について、以下の値を仮定する。

これが意味するところは、例えばこれまでの方策 \pi_0 では特徴量 x_u=x1 の会員には 0.1 の確率でクーポンを配信しており、実施予定の方策 \pi ではその確率を 0.9 とするということである。なお、ここでは簡単のために x_u=x1 以外の会員には方策を変えないこととする。今回の場合は真の期待報酬を知っているため、\pi_0 と \pi それぞれの真の方策性能を計算すると、新しい方策に変更しても報酬の期待値は変わらないことが分かる。

DM(Direct Method) 推定量
DM 推定量では、先程述べた真の期待報酬関数を直接予測することで、方策 \pi の性能を推定する。具体的には、期待報酬関数の予測値 \hat{q}(x_u, a_u) を何らかの方法で得た上で以下により方策性能を推定する。
\begin{equation}
\begin{split}
\hat{V}_{\text{DM}}(\pi; \hat{q}) &= \frac{1}{n} \sum_{u \in \mathcal{U}} \mathbb{E}_{\pi(a_u | x_u)} \hat{q}(x_u, a_u) \\
&= \frac{1}{n} \sum_{u \in \mathcal{U}} \sum_{a \in \mathcal{A}} \pi(a_u | x_u) \hat{q}(x_u, a_u)
\end{split}
\end{equation}
期待報酬関数の予測値 \hat{q}(x_u, a_u) を得る方法は自由であり、単純に過去の方策の統計量としても良いし、何らかの機械学習モデルで予測しても良い。ここで、仮に以下の表に示す期待報酬関数の予測値が得られたと仮定する。

なお、簡単なため特徴量 x_u=x1 以外の特徴量では完璧に期待報酬関数を予測できたと仮定した。一方で、特徴量 x_u=x1 の場合の予測値は 0.8 と真の値よりも高く予測してしまったと仮定した。表の値をもとに DM 推定量を計算すると以下のようになる。

もし、この推定値により新方策の是非を判断する場合、CVR は上がりそうだから採用しようとなるかもしれないが、そうしたとしても真の期待報酬から実際は CVR は変わらない可能性が高い。
この例からも分かるように DM 推定量は期待報酬関数の予測誤差に伴うバイアスが発生してしまう。一般に真の期待報酬関数を正確に予測することは難しく(今回の例で言えばクーポン有無での会員ごとの CV の期待値を予測する必要がある)、直感的に分かりやすいもののバイアスに気をつける必要がある推定量であることが理解できた。
IPS (Inverse Propensity Score) 推定量
IPS 推定量は DM 推定量のように真の期待報酬関数の予測を必要としない推定量であり、以下のように表される。
\begin{equation}
\begin{split}
\hat{V}_{\text{IPS}}(\pi; \mathcal{D}) &= \frac{1}{n} \sum_{u \in \mathcal{U}} \frac{\pi(a_u | x_u)}{\pi_0(a_u | x_u)} r_u \\
&= \frac{1}{n} \sum_{u \in \mathcal{U}} w(x_u, a_u) r_u
\end{split}
\end{equation}
ここで、 w(x_u, a_u) = \frac{\pi(a_u | x_u)}{\pi_0(a_u | x_u)} であり、重要度重みと呼ばれる。
IPS 推定量の嬉しい特性として、真の方策性能に対するバイアスがないことがある。言い換えると、過去のログデータに対する IPS 推定量の期待値を計算すると、真の方策性能に一致するということである。これは、直感的には過去のログデータを集めれば集めるほど、真の方策性能に近づくということである(ただし、分散がログデータ量の増加に従い小さくなればであり、IPS 推定量の分散はそれを満たす)。
このことをより理解するために、シミュレーションをしてみる。先程得た4人と同じ特徴量を持つ会員4人のログデータをさらに得たとする。そのログデータを以下に示す。

このログデータが意味するのは、例えば会員 u=1 は特徴量 x_u = x1 を持ち、クーポンを配信しなかった( a_u = a0 )ところ、購入しなかった( r_u = 0 )ということである。
ここで、特徴的 x_u = x1 を持つ会員にはクーポンを配信するしない両方の行動をした場合が観測されているとする。なお、会員 u = 5 のように行動がクーポンを配信する a_u = a1 でかつ観測された報酬が r_u = 1 というのは発生確率が低いが発生し得ることである。
ここまでのログデータで IPS 推定量を計算すると、1.625 とかなり大きな誤差があることが分かる。会員 u = 5 の重要度重みが大きな値になっていることが大きな誤差を生んでいる。また、重要度重みにより旧方策では起こりづらいが、新方策では起こりやすい行動の報酬を高く評価するように重みづけていることが分かる。

さらに先頭4人と同じパターンのログデータを8回分得たとする。なお、ここでは簡単のため x_u = x1 以外の会員は全く同じパターンの行動、報酬の組み合わせが観測されたと仮定する。本来は確率的であるため非現実的であるが、今回のシミュレーションで体感したいことを実現する上では問題ないと判断した。ログデータの IPS 推定量を 4人ごとに計算すると徐々に真の方策性能に近付いていることが分かる。

8人のログデータでは特徴量 x_u = x1 の会員にクーポンを配信するという \pi_0(a1 | x1) = 0.1 の確率で発生するログが含まれていたが、 旧方策で特徴量 x_u = x1 の会員にクーポンを配信するという行動の選択確率は \pi_0(a1 | x1) = 0.1 であり、確率的には10回に1回しか発生しないため、40人分のログデータを集めると先ほどの重要度重みが大きくなったことによる誤差の影響が小さくなる可能性が高いことが分かる。
さらに、ここまでの40人分と同じパターンのログデータを得たとする。ここで、x_u=x1 の会員に対してクーポンを配る行動確率は 0.1 であるため、x_u=x1 の会員には10人に1人の割合でクーポンを配信する行動 a_u=a1 を観測したと仮定する。ただし、簡単のために報酬は常に r_u=0 が観測されたとする。また、これまでと同様に x_u=x1 以外の会員は全く同じパターンの行動、報酬の組み合わせが観測されたと仮定する。このときの IPS 推定量を4人ごとに計算するとさらに真の方策性能に近づいていることがわかる。

この操作を繰り返し続け、400人分のログデータまでの IPS 推定量の変化を以下に示す。

ログデータが増加するにつれて真の方策性能に近づいていることがわかる。400人分のログデータを得たときの IPS 推定量の値は約 0.52 であり、先程の DM 推定量よりも精度が良いことがわかる。
DR(Doubly Robust) 推定量
DR 推定量は DM 推定量と IPS 推定量を組み合わせたような推定量であり、以下のように表される。
\begin{equation}
\begin{split}
\hat{V}_{\text{DR}}(\pi; \hat{q}) &= \sum_{u \in \mathcal{U}} \left\{ \hat{q}(x_u, \pi) + w(x_u, a_u) (r_u - \hat{q}(x_u, a_u)) \right\} \\
&= \hat{V}_{\text{DM}}(\pi; \hat{q}) + \sum_{u \in \mathcal{U}} w(x_u, a_u) (r_u - \hat{q}(x_u, a_u))
\end{split}
\end{equation}
DR 推定量の嬉しい特性として、IPS 推定量と同様に真の方策性能に対するバイアスがないことがある。また、 IPS 推定量よりもバリアンスが低い傾向にある。言い換えると、先程のようにログデータを増加させていったときに、早く真の方策性能に近づく可能性が高いということでもある。
先程の IPS 推定量と同様に8人分のログデータが得られた時点でDR 推定量を計算すると以下のようになる(これ以降 IPS 推定量と比較できるように両方の値を示す)。

これを見ると、 DR 推定量では重要度重みにかける値を観測報酬と期待報酬関数の予測値の差 r_u - \hat{q}(x_u, a_u) としたことにより、会員 u = 5 のような旧方策では発生確率が低いが新方策ではそれが高い場合に推定量の誤差が大きくなることを抑制できていることが分かる。
40人分のログデータが得られた時点まで見ると、 IPS 推定量と同様にログデータが増加するにつれて真の方策性能に近づいていることがわかる。

また、 DR 推定量の特徴として80人分のログデータが得られた時点まで見ると、再度 x_u = x1, a_u = a1 が観測されたときに、推定量の誤差が大きく減少していることがわかる。これは、観測報酬と期待報酬関数の予測値の差 r_u - \hat{q}(x_u, a_u) が負の値になり、これまでに生じた DM 推定量の予測誤差が相殺されたためであることがわかる。

これまでの DR 推定量の変化から、重要度重みにかける値を観測報酬と期待報酬関数の予測値の差 r_u - \hat{q}(x_u, a_u) としてバリアンスを抑えつつも、 期待報酬関数の予測誤差によるバイアスを DM 推定量の値を足すことで抑えていることが直感的に理解できた。
400人分のログデータまでの IPS 推定量と DR 推定量の変化を以下に示す。

DR 推定量は IPS 推定量と同様にログデータを増加させると真の方策性能に近づいていくことに加え、IPS 推定量よりも同じログデータ量で見たときに精度が良いことが分かる。400人分のログデータを得たときの DR 推定量の値は約 0.5 であり、IPS 推定量よりも真の方策性能に近い値であることが分かる。 DR 推定量で利用している期待報酬関数の推定値は誤差が 0.7 もあるにも関わらず、ログデータを増加させていけば真の方策性能に近づいていくこともわかった。
Discussion