反実仮想機械学習について良いオーバービューを提供してくれているトーク "Counterfactual Learning and Evaluation for Recommender Systems (RecSys2021)"を見ました。3.5時間に及び、内容も盛りだくさん。せっかくなので備忘録も兼ねてまとめを書きました。見る時間が無い方にとっても、エッセンスが伝わればいいなと思っています。
https://www.youtube.com/watch?v=HMo9fQMVB4w

事例

まず反実仮想機械学習という分野で取り扱う問題の例を見てみましょう。このトークでは、具体例として「心不全の患者に対する治療法選択」を挙げています。「過去で選ばれなかった選択肢をもし採っていたら・・・」という反実仮想の本質がよく分かる良い例えなのかなと思います。
具体的には、以下のような問題設定です。

心不全の患者それぞれに、「バイパス」「ステント」「投薬」の3つの治療を行いました。この治療法の選択は、医師が患者の状態を見ながら一定のルールに則って選んだものです。その結果奏効して回復した人もいれば、残念ながらそうでなかった人もいました。
このような過去のデータが手元にある前提で、治療法の選択ルールを見直そうと思います。過去に戻って治療をやり直すことはもちろんできません。あくまで手元にあるデータだけを使って、よりよい治療法のルールを見つけ出してください。

例えば、過去の治療の結果は以下の図のような形で記録されています。患者が11名行方向に並べられていて、治療法としてどれを選択したか列方向に3つ。そしてその結果が0(回復しなかった) or 1(回復した)で記録されています。このデータだけが手元にあるときに、では高齢の患者さんに投薬治療を優先したらどうなるだろう、などを検討するのが反実仮想の問題設定です。

同様の問題設定は、我々の身の回りでも多く発生します。例えば、

ある動画配信サービスでゴールデンウィーク最終日の夕方にサラリーマンのAさんに全12話のドラマをリコメンドしたところ、クリックされなかった。
もし、その日中に見られる2時間映画をおすすめしていたら果たしてクリックされていたのだろうか？

なども、現実的に考えうる問題です。

ちなみに、「リコメンド」と呼ばれる行為は昔から行われていたものですし、性能改善に向けた多くの試行錯誤がありました。その中ではいわゆる"A/Bテスト"を行い、パフォーマンスを検証していました。ただ最近では、以下のような理由でA/Bテストを行うことが難しくなってきています。

• A/Bテストを行うにはユーザーの反応を集めるためある程度の期間が必要。リコメンドアルゴリズムをどんどん改良したくとも、年間に実施できる評価回数の制約を受けてしまい改善サイクルを回しづらい
• A/Bテストはユーザーを巻き込んで行うものなのでProduction環境で行うことになる。そうすると実際の事業にも影響が出てしまい、売上を毀損してしまうかもしれない
• いわゆるユーザーセグメントを区切ってその中で別の選択肢を提示するようなA/Bテストは、リコメンドのパーソナライズ化によってやりづらくなってきている。つまり、「20代男性」ではなく、「特定のAさんのGW最終日の夕方」はほぼ唯一の機会であるため、選択肢を出し分けることができない

特に最後の項目のせいで上の心不全の例と同様、再トライができない状況が生まれており、反実仮想の問題として取り扱う必要がでてきます。

問題の設定

上の例では、「過去に戻って別の選択肢を提示していたらどういう反応だったか？」というニュアンスのことを口走りました。ただ、実際の反実仮想機械学習の枠組みではそこまで個別の推定問題に取り組むのではなく、もう少し幅広い問題設定に取り組みます。つまり、

過去にすでに一定のルールに則って記録されたログデータが手元にある。そのデータを用いて、新しく決めたルールがより優れているかどうかを、A/Bテストを新たに行うことなしにオフラインで判断したい

ここでいうルールは、心不全の例であれば患者の状態に応じた治療法選択のルールになりますし、リコメンドであればユーザーの状態に応じて何をリコメンドするのかというアルゴリズムになります。
親しみやすく「ルール」という表現を使いましたが、数学的な表現では「ポリシー」という用語が使われます。ユーザーや天候などの入力情報ベクトル $x$ があって、治療法選択やリコメンド対象の選定など取りうるアクション $a$ の選択肢があったときに、どの$a$を選択するかの確率をポリシー $\pi (a|x)$ として定義します。
以下で議論する枠組みでは、ポリシーは大きく2つ現れます。ログデータ取得期間で用いられていたポリシー$\pi_0$と、新しく評価をしたいポリシー$\pi_e$です。

ログデータは、以下のような形で記録をしておきます。

No.	$x$: 入力情報ベクトル	$a$: アクション	$p$: アクション選択確率	$r$: 結果
1	20代男性, 5/8 15:00	動画1を推薦	0.8	1.0 (クリックされた)
2	30代女性, 5/9 5:00	動画6を推薦	0.9	0.0 (クリックされなかった)
3	50代男性, 5/10 14:00	動画3を推薦	0.7	0.0 (クリックされなかった)
4	60代男性, 5/11 22:00	動画9を推薦	0.6	1.0 (クリックされた)

結果に対応する$r$は"リワード"と呼ばれます。
また、ログデータ取得期間では、何らかのリコメンドアルゴリズムに従ってアクション選択確率を決め、その確率に従ってアクション$a$をランダムに選択します。選ばれたアクション$a$に対応する選択確率 $p$を"Propensity (プロペンシティ)"と呼びます。つまり、$p_i=\pi_0 (a_i|x_i)$と表記します。
このPropensityの計算には、ログデータを取得した際のポリシー$\pi_0$が必要です。ポリシー$\pi_0$のモデルやルールをきちんと覚えていればいつでも計算できますが、わざわざ後から計算しなくともこの時点で計算して記録しておいたほうが楽なので、ログデータの中に保存をしておきます。

大事なポイントなので改めて書き下しますが、ログデータ取得期間には以下の2点を行うことが重要です:

• あるポリシー$\pi_0 (a_i|x_i)$の確率に従ってアクション$a_i$を選定すること
• そのときのPropensity $p_i=\pi_0 (a_i|x_i)$を記録しておくこと

反実仮想機械学習における2つの問題

さて、反実仮想機械学習の分野では、以下の2つの問題を区別して取り扱います:

• 過去に記録されたログデータの上で、新しいポリシー $\pi_e$ がどのくらい優れているかを評価したい (Off-Policy Evaluation; OPE)
• 過去に記録されたログデータの上で、より優れたポリシー $\pi_e$ を学習させたい (Off-Policy Learning; OPL)

この2つを混同しながらトークを聞くと道に迷いますので、きちんと区別するよう注意が必要です。

補足ですが、"Off-Policy"というのは、ログ取得時のポリシー $\pi_0$と、これから評価をしたいポリシー $\pi_e$が異なっていることを意味する表現です。

ログデータを用いたポリシーの評価 (OPE)

新しいポリシーの良し悪しを評価する方法には大きく2つのアプローチがあり、それぞれ紹介をしていきます。2つを組み合わせたDoubly Robust推定量も紹介されていますが、説明は他の記事に譲ります。

Model-based estimator (Direct Method) による評価

下の図のように、過去のログデータの空欄を何らかの機械学習モデル$\hat{r} (x,a)$ですべて埋めた疑似データを作ります。その疑似データの上で、新しいポリシー $\pi_e$ を評価する考え方です。
疑似データを作るための機械学習モデル$\hat{r}$は、ポリシー$\pi$とは別に準備する必要があるという点に注意が必要です。この機械学習モデル$\hat{r}$は通常シンプルな回帰モデルなどを用い、ログに記録された入力情報ベクトルとアクション $(x,a)$ に対してリワード$r$を推定するよう学習を行います。
当然ですが、この機械学習モデル$\hat{r}$が過去の未観測リワードを正しく予測し、適切な疑似データを補完する保証はどこにもありません。正しくない疑似データの上で評価されるのであれば、新しいポリシー$\pi_e$の性能評価は疑似データの間違いによってバイアスを受けます。そのため、Model-based estimator (Direct Method) で最適と判断されたポリシーが実運用でも最適である保証はなく、むしろ一般的には正しくないことも多いのが課題です。

その弱点は認めつつ、Model-based estimator (Direct Method) によるポリシーの評価は、下図の下段の式として与えられます。つまり、右側の表のすべてのセルに対して、新しいポリシーが提案する選択確率 $\pi_e (a|x)$と、機械学習モデル$\hat{r}$によって補完されたリワード$\hat{r} (x,a)$を掛けて平均をとったものになります。$\pi_e$は1に規格化されているため、結局$\hat{V}_\text{DM}$はリワードの期待値として解釈できます。

Model-free Estimator (Inverse Propensity Score; IPS) による評価

この評価手法においては、疑似データは用いず、過去に観測されたログデータだけを用いて評価します。そのため、疑似データの誤りによるバイアスの影響を受けずに評価を行うことができます。
Model-based estimator (Direct Method) と同様にリワードの期待値を計算しますが、あくまで過去のログデータから抽出した$(x_i,a_i,r_i)$のみを使って計算を行います。
ただし、ログデータ取得期間におけるPropensity、つまり選択確率$\pi_0 (a|x)$が大きいデータの組については、ログデータ取得期間中、頻繁にユーザーに提案されており、ログデータにも数多く記録されています。ログデータの出現頻度が偏っていると、上記画像の一番下の式で定義されるリワード期待値を計算する際にそこに重み付けられて計算されてしまいます。ログ取得時のポリシー$\pi_0$が、新しいポリシー$\pi_e$の評価に影響を与えるのはおかしいですので、$\pi_0$のPropensity $p_i=\pi_0 (a|x)$で割る補正を行うことで出現頻度の偏りの影響を軽減します。
これによって、新しいポリシー $\pi_e$　の性能評価を行ってあげるのが、Inverse Propensity Scoreによる評価の考え方です。

この手法はModel-based estimator (Direct Method) とは異なり、ログデータ量が十分なときにバイアス無く評価を行うことができます。ただし、ログデータの数が不十分な場合には評価結果の分散が大きく評価結果がばらつくことが弱点です。
また、この手の確率の割り算を含んだ計算によくある話として、$\pi_0$のPropensityが極端に小さかった場合、重み$\pi_e(a|x)/\pi_0(a|x)$が大きくなって実用上使いづらいといった問題も発生します。それを防ぐための手法として、正則化する修正を加えたCLIPS EstimatorやSNIPS Estimatorなどがトークの中で紹介されています。

ログデータを用いたポリシーの学習 (OPL)

基本的な考え方

前の項では、ログデータを用いたポリシーの評価手法について見てきました。良いポリシーを定量的に選べるようになれば、それを目的関数としてポリシーのパラメータを調整することで学習を行うことも可能です。
トークの中では、Inverse Propensity Scoreを学習のときの目的関数にしています。疑似データを作るための機械学習モデル$\hat{r}$を新規に導入する必要が無く、余分な仮定を導入する必要が無いためです。あとは、新しいポリシー$\pi_e(a_i|x_i)$のパラメータを動かしながら、目的関数を最大化/最小化するだけです。

下図がその考えを数式で表現したものです。IPSの評価関数に$argmax$がついただけです (注: トークの中では、ここからリワードの正負を逆にしているので分かりづらくなっています。この記事の中では、$argmin$を$argmax$と読み替えて、これまでの記述と整合を取ります)。
一点、分母が$\pi_0 (a_i|x_i)$からPropensity $p_i$に変わっています。これはログデータ取得時の$\pi_0 (a_i|x_i)$が、そもそもすでにログデータのカラムとして記録されているので、それに置き換えたものです。

新しいポリシー$\pi_e$を、深層学習モデルで構築したのがBanditNetで、下の図で表現される形で定義されています。仕組みは単純。入力情報ベクトル$x$を入力として受け、アクション$a$を取りうる確率を出力する深層学習モデルとして構成されています。$\exp(...)/Z(x)$と書かれていますが、これはSoftmax関数を意味しています。$w$は深層学習モデルのウェイトです。この深層学習モデルのアクション$a$に対する出力確率を$f_a(x)$と書いて上記式に入れると、全体像は以下のような形になります。

$\underset{f}{argmax} \left( \Sigma_i \Sigma_{a'} [ δ(a', a_i) \cdot r_i \cdot f_{a'}(x) \cdot 1 / p_i ] \right)$
ここで、$i$はログデータのインデックス、$a'$は取りうるアクションであり、$δ(a', a_i)$は$a'=a_i$のときに1、それ以外で0になる関数です。

比較のために、softmax-cross-entropyをロス関数とする分類器について、最適化問題を定式化すると以下のようになります。
$\underset{f}{argmin} \left( - \Sigma_i \Sigma_{a'} [ δ(a', a_i) \cdot \log{ f_{a'}(x) } ] \right)$

後者に対して、前者は、

• 最小化問題ではなく、最大化問題になっている (リワードの期待値値を最大化する目的のため)
• Softmax出力に対して、$\log$を掛けておらず確率のまま計算している。リワード$r_i$を掛けているので、結果としてリワードの期待値となる
• $\pi_0$によるバイアスを除くためPropensity $p_i$で割る形になっている

差分はこのくらいですので、一般的な深層学習の分類器に少し手を入れることで学習の仕組みを実装できることが分かります。

必要な正則化

このようにシンプルな学習則の導出できましたが、安定した学習を行うためにはもう一息工夫をしなくてはなりません。2つほど正則化を入れる必要があります。

1つ目は、「新しいポリシー$\pi_e$が、極端にログデータ取得時のポリシー$\pi_0$から乖離していないことを要求する」正則化。この解釈は動画の中では言及されておらず、直感的な理解に困っていたところ、Adith.S, Thorsten.J, "The Self-Normalized Estimator for Counterfactual Learning" にて以下のように説明されていたのを引用しています:

以下の図の$\lambda_1$の項です。$\pi_e(a_i|x_i)/p_i = \pi_e(a_i|x_i)/\pi_0(a_i|x_i)$が暴れるとこの項が大きくなりますが、これは2つのポリシーが取る値が大きく異なる場合に発生します。
結局、ログデータ取得時の状況と大きく異なると、評価の不定性はどうしても大きくなるため、そのような状況で偶然良い値を叩き出したポリシーが採用されないようにするための正則化です。

2つ目は、「ログデータの中でたまたまPropensity $p_i$が小さかったアクションが選ばれたとき、新しいポリシー$\pi_e$がそれにオーバーフィットしてしまうこと(Propensity overfitting)を防ぐ」正則化。下図の$\hat{S}(\pi)$の形を見ると、Propensity $p_i$が小さいデータに対して、新しいポリシー$\pi(a_i|x_i)$が大きな値を取りに行くと、そもそもこの分数は大きな値を取れることが分かります。この性質が学習のときに変に利用されてしまうと、Propensity $p_i$が小さいデータに対して大きな確率を出力するような単純なポリシー$\pi(a_i|x_i)$が学習されてしまいます。これはデータに対するオーバーフィットであり、本来行いたいリワード期待値を最大化するポリシーの探索からは外れます。これを防ぐために、一番下の行のように$\hat{V}(\pi)/\hat{S}(\pi)$という形の正則化を導入します。Model-free estimatorの章で説明を端折ってしまったSNIPS Estimatorですが、まさにPropensity overfittingを解消するためのアプローチであり、同じ式になりますので、以下の図でも$\hat{V}^{SNIPS}$と書かれています。

まとめ

トークを見終わっての感想ですが、反実仮想機械学習という学問は、数式も比較的シンプルにまとめられており、やるべきことも明確に定義されていてエンジニアが使いやすい実践的な学問だと改めて感じました。課題設定も現実に発生しうるシチュエーションを良く捉えていますし、何よりこれをベースにして作られるリコメンドシステムは、ユーザーへのベネフィットの提供はもちろんのこと、企業にとっても(A/Bテストで発生するような)売上毀損リスクを軽減することができ、実装のやりやすさと楽しさの観点で開発者も幸せという三方良しを実現しうるものだと思いました。すばらしい。

最後に、会社の紹介をさせてください。ニューラルポケットでは、人々が便利で幸せな生活を送れるスマートシティの実現に向け、深層学習モデルや最適化アルゴリズムの開発を進めています。知的好奇心に溢れたメンバーが、ホワイトボードに色々書きながら議論を深めていく文化です。少しでも興味を持っていただけた方は、ぜひ以下のページからご連絡をいただけますと幸いです。
https://hrmos.co/pages/neuralpocket/jobs/1725841606893461509