Causal Embeddingsの解説と追試 - Counterfactualを知りたい

はじめに

前回は, ログデータの観測確率が一様ではない場合に傾向スコアで補正した損失関数を用いるPropensity Matrix Factorizationを紹介しました. しかし, 2018年のRecsysにてBest Paper Awardを受賞したCausal Embeddings for Recommendation [Bonner+ 2018]で, Propensity MFを実験的に上回る手法が提案されました. 本記事では人工データを用いて, その提案手法の追試を行います.

定式化のおさらい

推薦アルゴリズムの学習の定式化をおさらいします. しかし, ここでは[Bonner+ 2018]のモデル化に合わせるため, 前回記事とは少し異なる部分があることに注意してください.

各ユーザーを $u \in \{1, ..., U \} = \mathcal{U}$ , 各アイテムを $i \in \{ 1, ...., I \} = \mathcal{I}$ とします. また, $P_{u,i}$ をユーザー $u$ がアイテム $i$ に対して有する真のPreferenceとします. $P_{u,i}$ はユーザーとアイテムの組み合わせにのみ依存して決定的な値を取るとします. 推薦アルゴリズムの学習によって達成したいのは, 次のように定義される真の損失関数 $\mathcal{L}$ を最小化するような予測値集合 $\hat{P} = \{ \hat{P}_{u, i} \}_{(u,i) \in \mathcal{U} \times \mathcal{I}}$ を得ることです.

$\begin{aligned} \mathcal{L} \left( \hat{P} \right) = \frac{1}{U \cdot I} \sum_{u,i} \delta \left( P_{u,i}, \hat{P}_{u,i} \right) \end{aligned}$

ここで, $\delta (\cdot, \cdot): \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$ は真のRatingとそれに対する予測値を入力とする関数でした.

さらに, 自分たちが観測できるPreferenceと観測できないそれを区別するために, Recommendationの頭文字をとって新たな確率変数 $R$ を導入します. この $R$ は2値確率変数であり各ユーザーとアイテムのペアに対応して独立に存在します. $R_{u,i} = 1$ ならば, 過去にユーザー $u$ にアイテム $i$ が推薦されたことを意味し, そのペアについてのPreferenceが観測されることを意味します. [Bonner+ 2018]では, 観測されるPreferenceを $Y_{u,i}^{obs}$ とした時, 次のようなモデルを想定しています.

$\begin{aligned} Y_{u,i}^{obs} = P_{u,i} \cdot R_{u,i} \end{aligned}$

このモデル化では, 過去に推薦が発生したペア（ $R_{u,i} = 1$ ）については, $Y^{obs}_{u,i} = P_{u,i}$ となり真のPreferenceが観測されますが, それ以外のペアについては $Y_{u,i}^{obs} = 0$ となりPreferenceが観測されないということになります.（ユーザーとアイテムのMatrixを考えた時に, Preferenceが観測されず欠損となってしまっている部分を0で表しているというイメージです.）

以降, 推薦有無を表す確率変数 $R_{u,i}$ は議論の中で重要な役割を担うので, その期待値にnotationを用意しておきましょう.

$\begin{aligned} \mathbb{E} \left [ R_{u,i} \right ] = \pi_c (u,i) \end{aligned}$

$\pi_c (u,i)$ はログデータが集められた際に走っていた推薦方策を表し, logging policyと呼びます. これを用いると私たちが学習の際に用いることができる（真の損失関数の推定に用いることができる）学習データセット $\mathcal{S}$ を次のように表すことができます.

$\begin{aligned} \mathcal{S} = \left\{ \left( u, i, Y_{u,i}^{obs} \right): R_{u,i} = 1 \right\} \end{aligned}$

Radomized Policy下でのNaive Loss

前章で定義した真の損失関数 $\mathcal{L}$ を知ることができるならばそれ最適化するパラメータを得れば良いのですが, それは不可能です. よって手元にあるログデータ $\mathcal{S}$ から損失関数を推定して, それを信じた上で, 最適化を実行する必要があります.

まずNaiveな損失関数 $\hat{\mathcal{L}}_{naive} \left( \hat{P} \right)$ は次のように定義されます. これは, 過去に推薦が発生したデータについての損失を単純に平均するという非常に単純な推定量です.

$\begin{aligned} \hat{\mathcal{L}}_{naive} \left( \hat{P} \right) = \frac{1}{ | \mathcal{S} | } \sum_{(u,i) \in \mathcal{S}} \delta \left( Y^{obs}_{u,i}, \hat{P}_{u,i} \right) \end{aligned}$

[Bonner+ 2018]は, このNaive推定量 $\hat{\mathcal{L}}_{naive}$ がある条件下で望ましい性質を満たすことに注目します. まず, ある条件とは次のようなものです.

$\begin{aligned} \pi_c (u,i) = \pi_{rand} = \frac{C \cdot | \mathcal{S} |}{U \cdot I} \quad (constant) \end{aligned}$

つまり, logging policyがユーザーとアイテムに非依存で, 一様な定数であるという要求です. このようなlogging policyを特にrandomized policyと呼ぶことにし, $\pi_{rand}$ で表します. 定数部分は実はなんでも良いのですが, ここでは後の式変形が綺麗な形になる定数を置いています. さて, このlogging policyがrandomized policyであるという仮定が成り立っているときに, Naive推定量 $\hat{\mathcal{L}}_{naive}$ の期待値をとってみましょう.

$\begin{aligned} \mathbb{E}_R \left[ \hat{\mathcal{L}}_{naive} \left( \hat{P} \right) \right ] & = \mathbb{E}_R \left[ \frac{1}{ | \mathcal{S} | } \sum_{(u,i) \in \mathcal{S}} \delta \left( Y^{obs}_{u,i}, \hat{P}_{u,i} \right) \right] \\ & = \mathbb{E}_R \left[ \frac{1}{ | \mathcal{S} | } \sum_{(u,i) \in \mathcal{U} \times \mathcal{I} } R_{u,i} \cdot \delta \left( P_{u,i}, \hat{P}_{u,i} \right) \right] \\ & = \frac{1}{ | \mathcal{S} | } \sum_{(u,i) \in \mathcal{U} \times \mathcal{I}} \mathbb{E}_{R_{u,i}} \left[ R_{u,i} \right] \cdot \delta \left( P_{u,i}, \hat{P}_{u,i} \right)\\ & = \frac{1}{ | \mathcal{S} | } \sum_{(u,i) \in \mathcal{U} \times \mathcal{I}} \pi_{rand} \cdot \delta \left( P_{u,i}, \hat{P}_{u,i} \right) \\ & = \frac{1}{ | \mathcal{S} | } \sum_{(u,i) \in \mathcal{U} \times \mathcal{I}} \left( \frac{C \cdot | \mathcal{S} |}{U \cdot I} \right) \cdot \delta \left( P_{u,i}, \hat{P}_{u,i} \right) \\ & = C \left( \frac{1}{U \cdot I} \sum_{u,i} \delta \left( P_{u,i}, \hat{P}_{u,i} \right) \right) \\ & = C \cdot \mathcal{L} \left( \hat{P} \right) \\ & \propto \mathcal{L} \left( \hat{P} \right) \end{aligned}$

これにより, randomized policyで集められたログデータを用いて計算されるNaiveな損失関数は真の損失関数に比例します. よって, $\hat{\mathcal{L}}_{naive}$ を最適化するような学習は妥当であると言えそうです.

Causal Embeddings (CausE)

[Bonner+ 2018]の提案手法であるCausEは, 前章で紹介したNaive推定量の性質を活用します. CausEは学習データが次のように表せることを要求します.

$\begin{aligned} \mathcal{S} = \mathcal{S}_t \cup \mathcal{S}_c \end{aligned}$

ここで, $\mathcal{S}_t$ はrandomized policyによって集められた学習データで, $\mathcal{S}_c$ は $u$ と $i$ に依存するlogging policyによって集められた学習データを表します. ただし, $\mathcal{S}_t$ は $\mathcal{S}_c$ よりも要素数の少ない集合で良いです. また, それぞれ異なるembeddingsによって構成される2つの予測値集合 $\hat{P}_t = \{ \theta_{u, t}^{\top} \beta_{i, t} \}_{ (u,i) \in \mathcal{U} \times \mathcal{I} }$ , $\hat{P}_c = \{ \theta_{u, c}^{\top} \beta_{i, c} \}_{ (u,i) \in \mathcal{U} \times \mathcal{I} }$ を用いた次の損失関数をCausEは最適化します.

$\begin{aligned} \hat{\mathcal{L}}_{CausE} & = \underbrace{ \frac{1}{| \mathcal{S}_t |} \sum_{ (u, i) \in S_t } \delta \left( P_{u,i}, \theta_{u, t}^{\top} \beta_{i, t} \right) }_{(1)} + \underbrace{ \frac{1}{| \mathcal{S}_c |} \sum_{ (u, i) \in S_c } \delta \left( P_{u,i}, \theta_{u, c}^{\top} \beta_{i, c} \right) }_{(2)} \\ & + \underbrace{ \lambda \left( \sum_{u \in \mathcal{U}} \| \theta_{u, t} - \theta_{u, c} \|_p + \sum_{i \in \mathcal{I}} \| \beta_{i, t} - \beta_{i, c} \|_p \right)}_{(1)} \end{aligned}$

(1)はrandomized policyによって構成された $\mathcal{S}_t$ に対するNaiveな損失（Biasなし）, (2)はlogging policyによって構成された $\mathcal{S}_c$ に対するNaiveな損失（Biasあり）, (3)は(2)によって得られるembeddings ( $\theta_{u, c}, \beta_{i, c}$ ) が望ましい損失である(1)から得られるembeddings ( $\theta_{u, t}, \beta_{i, t}$ ) と乖離することに対してかける正則化で, $\lambda$ はその強さを調節するハイパーパラメータです. （ $\theta_{u, c}, \beta_{i, c}$ を更新するときのみ, (3)の正則化を考慮に入れるアルゴリズムになっています.）

確かにこの損失関数からは, Biasがあるが考慮できるデータが多い損失(2)から得られたembeddingsが, Biasのない損失(1)から得られたembeddingsと離れないようにしようというお気持ちが読み取れます. しかし, この正則化について理論的な考察が論文でなされているわけではなく, どこかもどかしい気もします.

さて, 最終的な予測値集合は次のように作ります.（これが実験的に最も良かったらしいです.）

$\begin{aligned} \hat{P}_{CausE} = \{ \theta_{u, c}^{\top} \beta_{i, c} \}_{ (u,i) \in \mathcal{U} \times \mathcal{I} } \end{aligned}$

簡易実験

CausEとPropensity Matrix Factorizationの性能を同様の人工データを用いて比較します.

実験設定

設定に関しては前回の実験と同じです.

しかし, 前回記事ではあえて書いていなかったのですが学習データの約3%はrandomized policy ( $\pi_{rand}$ ) によって生成されています. CausEは, この少量の $\mathcal{S}_t$ を明示的に活用することで精度向上を目指します.

また, 各手法について, Optimizerはエポック数1024のMini-batch Momentum, 学習率には初期値を0.1としたexponential decayを施しています. CausEの $\mathcal{S}_t$ と $\mathcal{S}_c$ で得られたembeddingsの乖離に対してかける正則化はL1 normを用いました（L2 normよりも若干良かった）.

実験結果

評価方法は前回と同様で, 各手法の25,000エポックの内, validation dataの評価が最も良かったエポックのtest dataに対するMSEの相対改善度を性能評価として用います. ただし, test dataのratingの平均で全埋めしたときのMSEを相対改善度のベースラインとしています. （[Bonner+ 2018]と同じような評価方法です.）

validation時の評価指標は, NaiveなMatix FactorizationはNaiveな評価指標を, Propensity Matrix FactorizatioはUnbiasedな評価指標をそれぞれ対応する指標として用いました. CausEに関しては, validationの際も少量の $S_t$ を用いています.

結果は次の通りです. Best on Valはvalidation dataの評価指標が最も良かったときのエポックのtest dataに対する性能で, Best on Testは, test dataを対する真の性能が最も良かったときのエポックのtest dataに対する性能です. この2つの差が大きい場合, validationに使っていた評価指標が信頼できるものではなかった, ということです.

	Best on Val	Best on Test
Naive MF	- 66.05 %	18.71 %
Propensity MF	16.22 %	19.31 %
Causal Embeddings (CausE)	23.02 %	23.11 %

Naive MFとPropensity MFは, 前回記事と同様の結果を掲載しています. CausEは, 少量の $\mathcal{S}_t$ を明示的に活用することで精度を向上できていることがわかります. CausEの学習の様子は次のようになりました. 青い線は $\mathcal{S}_t$ に対するNaiveな損失ですが, 学習データの3%ほどから計算しているのでエポック間でのブレが大きくなっています.

f:id:usaito:20190416073151p:plain — CausEのlearning curve

さいごに

これまではexplicit feedback recommendationのBias除去の話題について触れてきました. これからはimplicit feedback recommendationに関する同様の話題についても触れていきたいです.

参考

[Bonner+ 2019] Stephen Bonner and Flavian Vasile. Causal embeddings for recommendation: An Extended Abstract. arXiv:1904.05165. 2019.
[Bonner+ 2018] Stephen Bonner and Flavian Vasile. Causal embeddings for recommendation. In Proceedings of the 12th ACM Conference on Recommender Systems, pages 104– 112. ACM, 2018.
[Schnabel+ 2016] Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. Recommendations as treatments: Debiasing learning and evaluation. In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48, ICML’16, pages 1670–1679, 2016.