最近業務でレコメンドエンジンをオフラインで評価する機会があり、評価手法を調査していた際にOff-Policy-Evaluation（OPE）に出会ったので、その一部を学習記録として残しておきます。

Off-Policy-Evaluation（OPE）とは？

現在運用している既存のレコメンドエンジンから新しいレコメンドエンジンへ移行する際に、新しいレコメンドエンジンを評価するためにA/Bテストを実施するのが一般的です。

ここでのA/Bテストは、簡単に説明すると、実際に既存のエンジンが動作している運用環境へ新しいエンジンを仮導入・運用し、どちらのエンジンが優秀かオンラインにてCTR（クリック率：どれだけクリックされたか）などを指標に比較検証することを意味します。

例えば、無作為に選ばれたユーザ1000人へ既存のエンジンでレコメンドされた結果と、同じく無作為に選ばれたユーザ1000人へ新しいエンジンでレコメンドされた結果が以下であるとします。

エンジン	ユーザ数	CTR
既存	1000	1.0 %
新規	1000	2.0 %

上記では新しいエンジンが優秀であると判断され、新しいエンジンへと移行することができます。
しかし、以下のような結果となった場合、残念ながら新しいエンジンの方がCTRが低いため導入に至らないという結末になります。

エンジン	ユーザ数	CTR
既存	1000	1.0%
新規	1000	0.5%

このように必ずしも新しいエンジンの方が優秀であるという保証がないため、A/Bテストは以下のようなリスクが伴います。

コストの無駄使い（実際には知見や結果は得らるので無駄は言い過ぎですが。。）
- 新しいエンジンの評価が既存エンジンより低く不採用となった場合、A/Bテストの準備・運用コストが無駄になる。
エンジンのチューニング効率が悪い
- 新しいエンジンの評価が芳しくない場合チューニングが必要となる可能性がある。チューニングを行った後再度A/Bテストによる評価を行うこため、さらに一定の評価期間が必要になる。
機会損失
- 新しいエンジンの評価が芳しくない場合、既存エンジンであればコンバージョンへと繋がっていたユーザが、新しいエンジンによりレコメンドされたためコンバージョンとならず機会損失となる可能性がある。

このようなリスクを軽減するために、A/Bテストの前に新しいエンジンが使えるものなのかオフラインで評価したいというモチベーションが生まれます。
これを実現するのが Off-Policy-Evaluation（OPE） です。

なぜ新しいエンジンをオフラインで評価できるのか

OPEでは新しいエンジンをオフライン評価するための推定量が存在し、この推定量が性能評価値となります。

推定量はいくつか存在しますが、その中の１つであるInverse Propensity Score（IPS） を例に、なぜOPEは新しいエンジンを評価できるのか説明します。

新しいエンジンを評価するのに何もない状態では当然評価できません。
そこで必要となるのが以下の情報です。

実際に運用で出力された既存エンジンのログデータ
- ユーザに何のアイテムがレコメンドされ、その結果ユーザはクリックしたか。
- ユーザにアイテムがレコメンドされる確率　※なぜ確率が必要なのかは後述
新しいエンジンの推論結果
- 既存エンジンのログデータと同一ユーザで推論した結果、何のアイテムが推論（レコメンド）されたか。

例えば以下のようなデータになります。

ユーザ	既存エンジンのレコメンドアイテム	クリック有無	新エンジンの推論アイテム
001	A	1	A
002	B	0	A
003	A	0	C
004	C	0	C
005	B	1	B

ここで注目する点として、ユーザ002や003は既存エンジンのレコメンドアイテムと新しいエンジンの推論アイテムが一致してないということです。

例えば、ユーザ002はアイテムBがレコメンドされた結果クリックされなかったということが観測されています。
しかし、新エンジンで推論されたアイテムAは実際にレコメンドされていないため、クリックされるか否かが未知です。
アイテムAがレコメンドされていたら実はクリックされていたかもしれません。

このような状況から既存エンジンのレコメンドアイテムと新しいエンジンの推論アイテムが一致しているデータを利用し評価するという手法が考えられます。
これを前提に新しいエンジンを以下のように評価します。

\frac{\{ﾕｰｻﾞ001のｸﾘｯｸ有無\} + \{ﾕｰｻﾞ004のｸﾘｯｸ有無\} + \{ﾕｰｻﾞ005のｸﾘｯｸ有無\}}{ユーザ数}

上記は、「新しいエンジンは、実際にクリックされたアイテムをどれだけ推論できているか？」という観点で性能評価が行えます。

実際に数値を入れると以下になります。

\frac{1+0+1}{3} \approx 0.67

尚、この推定量は以下のように定義できます。

\hat{J}_{naive}(\pi_\phi;D) = \frac{1}{N}\sum_{i=1}^{N}\mathbb{I}\{\pi_\phi(X_i)=A_i\}・Y_i

ここで、$N$はデータ数、$Y_i$は実際にユーザがクリックしたか否かを表します。

また、$\pi_\phi(X_i)$は、新しいエンジンによるユーザ$X_i$の推論アイテムを、$A_i$は同ユーザの既存エンジンによるレコメンドアイテムを表しています。
$\mathbb{I}｛\pi_\phi(X_i)=A_i｝$は指示関数で、$\pi_\phi(X_i)$と$A_i$が一致したときに$1$、一致しないときに$0$を返します。

したがって、既存エンジンのレコメンドアイテムと新しいエンジンの推論アイテムが一致している$Y_i$の平均値を算出していることになります。
ここでは、結果の値が大きいほど（新しいエンジンが推論したアイテムがクリックされているほど）良い性能であるといえます。

さて、上記の推定量で本当に性能は評価できているのでしょうか？
単純すぎてこれでいいのか？という感じがします。

この推定量が性能を評価できているか確認するため、推定量が不偏推定量であるかを確認します。

まず、真の目的関数を考えます。
新しいエンジンでレコメンドされたアイテムがクリックされているほど良い性能という定義から以下のように考えられます。

J(\pi_\phi)=E_X[Y(\pi_\phi(X))]

ここで$Y(\pi_\phi(X))$はユーザがクリックしたか否か（$1$ または $0$）を表します。

したがって、クリックされているほど値が大きくなります。

推定量が、この目的関数値の不偏推定量であるかを確認します。

\begin{align}
E_{(X,A)}[\hat{J}_{naive}(\pi_\phi;D)]=E_{(X,A)}[\frac{1}{N}\sum_{i=1}^{N}\mathbb{I}\{\pi_\phi(X_i)=A_i\}・Y_i] \\
=\frac{1}{N}\sum_{i=1}^N E_X[\pi_b(A_i|X_i)・Y_i(\pi_\phi(X_i))]
\end{align}

途中式をかなり省略していますが、上記のようになります。

結果を真の目的関数と比べると$\pi_b(A_i|X_i)$で重みづけられてしまっていることがわかります。
$\pi_b(A_i|X_i)$は、既存エンジンがユーザ$X$へアイテム$a$をレコメンドする確率になります。

したがって、この推定量は既存エンジンが選択しやすいアイテムの価値を過大に見積もってしてしまっています。

既に算出した推定量は正しく性能評価できないことがわかりました。
正しく性能評価できるようにするため、推定量に以下のような工夫をします。

\begin{align}
\hat{J}_{IPS}(\pi_\phi;D) = \frac{1}{N}\sum_{i=1}^N \frac{\mathbb{I}\{\pi_\phi(X_i)=A_i\}}{\pi_b(A_i|X_i)}・Y_i

\end{align}

$\hat{J}_{naive}$に対して、余計に重みづけされていた$\pi_b(A_i|X_i)$の逆数で重みづけしています。
これにより真の目的関数値の不偏推定量となり、新しいエンジンを性能評価する推定量として利用できます。

この推定量$\hat{J}_{IPS}$が、Inverse Propensity Score（IPS） になります。

推定量を利用する際の注意点

IPSを利用する際は、既存エンジンのログデータに注意する必要があります。
$\hat{J}_{IPS}$では$\pi_b(A_i|X_i)$の逆数で重みづけしているという点です。

これは、既存エンジンがユーザ$X$へアイテム$a$をレコメンドする確率が必要ということになります。
したがって、既存エンジンが確率的なレコメンドエンジンではない場合は利用が厳しくなります。

また、IPS以外にDRという推定量がありますが、こちらも既存エンジンが確率的なレコメンドエンジンであることが前提となっています。

昨今、確率的ではないレコメンドエンジンにおいても、新しいエンジンの性能評価を行う手法は研究されているようです。
また、IPSやDR以外にも推定量があるので、ご興味があれば調べてみてだくさい。

A/Bテストは必要です！

OPEを使えばA/Bテストはやらなくて大丈夫！
というわけにはいかないようです。

OPEは、ある程度の精度で新しいエンジンの性能評価が推定できるという話なので、別途オンラインA/Bテストを実施して真の評価を知る必要はあります。

ただ、オフライン評価にて新しいエンジンの性能が良くないないだろうということが予測できれば、A/Bテストを実施する前に導入を止めるという判断ができます。
またチューニングにおいても、推定量を指標にオフラインで行うことでより良いチューニングができる可能性があります。

今後研究が進んで、A/Bテストの実施自体が必要ないくらいオフライン評価の精度が上がると最高ですね。

OpenBanditPipeline

バンディットアルゴリズムやOPEの性能評価のためのPythonパッケージで、ZOZOのオープンソースになります。

実装方法などはここでは説明しませんが、このライブラリを利用すると上記のIPSなどを簡単に実装できます。

まとめ

OPEはまだまだ研究中の分野であり、既存エンジンのログがある程度整っていないと利用が難しい点などがありますが、ここをクリアすれば非常に活用できる技術だと思います。

既存エンジンが確率的ではない場合は、まずは確率的なエンジンに変更することでログを整備し、OPEを活用していけるようにする手段もとられているようです。

OPEとはまた別な観点でオフライン評価する手法なども研究されており、こちらはまた別の機会でご紹介できればと思います。

参考文献

施策デザインのための機械学習入門
齋藤優太 + 安井翔太, 株式会社ホクソエム（監修）