Published on

[論文メモ] Doubly Robust Joint Learning for Recommendation on Data Missing Not at Random

Authors

はじめに

Explicit feedbackに基づく推薦システムにおいてバイアス除去を試みた論文を読んだので部分的にメモを紹介します。Explicit feedbackに基づく推薦システムのバイアス除去については前回の記事も参照してみてください。

  • タイトル：Doubly Robust Joint Learning for Recommendation on Data Missing Not at Random
  • 著者：Xiaojie Wang, Rui Zhang, Yu Sun, Jianzhong Qi
  • 所属：University of Melbourne, Twitter
  • 発表会議：ICML 2019

[link]

概要

推薦システムを学習、評価するためのデータセットの多くは推薦システムの過去の推薦方策やユーザーの自己選択による選択バイアス(selection bias)の影響を受けている。 本研究ではそういった選択バイアスに対処するための因果推論に基づく手法を提案する。

導入

Notation

  • ユーザー：U={u1,…,uN}\mathcal{U}=\left\{u_{1}, \dots, u_{N}\right\}
  • アイテム：I={i1,…,iM}\mathcal{I}=\left\{i_{1}, \dots, i_{M}\right\}
  • 全ユーザー×全アイテムの組み合わせの集合：D=U×I\mathcal{D}=\mathcal{U} \times \mathcal{I}
  • 真の評価値の行列：R∈RN×M\mathbf{R} \in \mathbb{R}^{N \times M}
    • ユーザー uu のアイテム ii に対する評価値：ru,ir_{u,i}
  • 予測した評価値の行列：R^∈RN×M\hat{\mathbf{R}} \in \mathbb{R}^{N \times M}
    • ユーザー uu のアイテム ii に対する評価値の予測値：r^u,i\hat{r}_{u, i}

Preliminaries

もし、すべてのユーザー×アイテムの真の評価値の行列 Rf\mathbf{R}^f を観測できたなら、モデルの予測の不正確さ(prediction inaccuracy) P\mathcal{P} は

P=P(R^,Rf)=1∣D∣∑u,i∈Deu,i\mathcal{P}=\mathcal{P}\left(\hat{\mathbf{R}}, \mathbf{R}^{f}\right)=\frac{1}{|\mathcal{D}|} \sum_{u, i \in \mathcal{D}} e_{u, i}

と表現できる。eu,ie_{u,i} はMAEなら eu,i=∣r^u,i−ru,i∣e_{u, i}=\left|\hat{r}_{u, i}-r_{u, i}\right|、MSEなら eu,i=(r^u,i−ru,i)2e_{u, i}=\left(\hat{r}_{u, i}-r_{u, i}\right)^{2} で表現できる。

ここで O∈{0,1}N×M\mathbf{O} \in \{0,1\}^{N \times M} をindicator matrixとして定義し、エントリ ou,i=1o_{u,i}=1 なら ru,ir_{u,i} が観測され、ou,i=0o_{u,i}=0 なら ru,ir_{u,i} が観測されていない(missing)ことを意味する。R\mathbf{R} のうち観測されたものを Ro\mathbf{R}^o、観測されなかったものを Rm\mathbf{R}^m と置く。

ナイーブな推定量

EN=EN(R^,Ro)=1∣O∣∑u,i∈Oeu,i\mathcal{E}_{\mathrm{N}}=\mathcal{E}_{\mathrm{N}}\left(\hat{\mathbf{R}}, \mathbf{R}^{o}\right)=\frac{1}{|\mathcal{O}|} \sum_{u, i \in \mathcal{O}} e_{u, i}

where O={(u,i)∣u,i∈D,ou,i=1}\mathcal{O}=\left\{(u, i) | u, i \in \mathcal{D}, o_{u, i}=1\right\}

しかし観測されているデータはMNARなため ∣P−EO[EN]∣≫0\left|\mathcal{P}-\mathbb{E}_{\mathbf{O}}\left[\mathcal{E}_{\mathrm{N}}\right]\right| \gg 0 となりバイアスがある。

EIB推定量

ヒューリスティックな方法としてEIB推定量(error-imputation-based estimator)が提案されている。 これは、観測されていないエントリに対してimputed errorと呼ばれる e^u,i=ω∣r^u,i−γ∣\hat{e}_{u, i}=\omega\left|\hat{r}_{u, i}-\gamma\right| (for MAE)あるいは e^u,i=ω(r^u,i−γ)2\hat{e}_{u, i}=\omega\left(\hat{r}_{u, i}-\gamma\right)^{2} (for MSE)を計算するというもので、ω\omega や γ\gamma はハイパーパラメータである。

EEIB=EEIB(R^,Ro)=1∣D∣∑u,i∈D(ou,ieu,i+(1−ou,i)e^u,i)\mathcal{E}_{\mathrm{EIB}}=\mathcal{E}_{\mathrm{EIB}}\left(\hat{\mathbf{R}}, \mathbf{R}^{o}\right)=\frac{1}{|\mathcal{D}|} \sum_{u, i \in \mathcal{D}}\left(o_{u, i} e_{u, i}+\left(1-o_{u, i}\right) \hat{e}_{u, i}\right)

δu,i=eu,i−e^u,i\delta_{u,i} = e_{u,i} - \hat{e}_{u,i} をerror diviationといい、imputed errorが正確である場合(i.e., δu,i=0\delta_{u,i} = 0)にEIB推定量は不偏推定量となる。

IPS推定量

IPS推定量は前回紹介した推定量で、観測されやすさであるPropensity pu,i=P(ou,i=1)p_{u, i}=P\left(o_{u, i}=1\right) の逆数をかける(Inverse-Propensity-Scoring)方法。Propensityの予測値を p^u,i\hat{p}_{u, i} とすると

EIPS=EIPS(R^,Ro)=1∣D∣∑u,i∈Dou,ieu,ip^u,i\mathcal{E}_{\mathrm{IPS}}=\mathcal{E}_{\mathrm{IPS}}\left(\hat{\mathbf{R}}, \mathbf{R}^{o}\right)=\frac{1}{|\mathcal{D}|} \sum_{u, i \in \mathcal{D}} \frac{o_{u, i} e_{u, i}}{\hat{p}_{u, i}}

と表される。 IPS推定量はPropensityの予測値 p^u,i\hat{p}_{u,i} が正確である場合(i.e., Δu,i=p^u,i−pu,ip^u,i=0\Delta_{u,i} = \frac{\hat{p}_{u, i}-p_{u, i}}{\hat{p}_{u, i}}=0)に不偏推定量となる。

SNIPS推定量

こちらも前回紹介した通り、IPS推定量の分散を抑えるために下記のようなSNIPS推定量が提案されている。

ESNIPS=ESNIPS(R^,Ro)=(∑u,i∈Dou,ip^u,i)−1∑u,i∈Dou,ieu,ip^u,i\mathcal{E}_{\mathrm{SNIPS}}=\mathcal{E}_{\mathrm{SNIPS}}\left(\hat{\mathbf{R}}, \mathbf{R}^{o}\right)= \left( \sum_{u, i \in \mathcal{D}} \frac{o_{u, i}}{\hat{p}_{u, i}} \right)^{-1} \sum_{u, i \in \mathcal{D}} \frac{o_{u, i} e_{u, i}}{\hat{p}_{u, i}}

提案手法=二重にロバストな推定量(Doubly Robust estimator)

キーとなるアイディアは観測されたエントリについてerror diviation δu,i\delta_{u,i} を補正し、その補正値にPropensityの逆数をかけることでMNARを考慮する。

EDR=EDR(R^,Ro)=1∣D∣∑u,i∈D(e^u,i+ou,iδu,ip^u,i)=1∣D∣∑u,i∈D(ou,ip^u,ieu,i+(1−ou,ip^u,i)e^u,i)\begin{aligned} \mathcal{E}_{\mathrm{DR}}=\mathcal{E}_{\mathrm{DR}}\left(\hat{\mathbf{R}}, \mathbf{R}^{o}\right) & = \frac{1}{|\mathcal{D}|} \sum_{u, i \in \mathcal{D}}\left( \hat{e}_{u,i} + \frac{o_{u,i}\delta_{u,i}}{\hat{p}_{u,i}} \right)\\ & = \frac{1}{|\mathcal{D}|} \sum_{u, i \in \mathcal{D}}\left( \frac{o_{u,i}}{\hat{p}_{u,i}} e_{u,i} + \left(1 - \frac{o_{u,i}}{\hat{p}_{u,i}} \right) \hat{e}_{u,i} \right) \end{aligned}

p^u,i\hat{p}_{u,i}、ou,io_{u,i} が変化したときのlossのイメージは

ou,i=0o_{u,i}=0ou,i=1o_{u,i}=1
p^u,i\hat{p}_{u,i}e^u,i\hat{e}_{u,i}eu,i−e^u,ip^u,i+e^u,i\frac{{e}_{u,i}-\hat{e}_{u,i}}{\hat{p}_{u,i}}+ \hat{e}_{u,i}
p^u,i→1\hat{p}_{u,i} \rightarrow 1e^u,i\hat{e}_{u,i}eu,i{e}_{u,i}
p^u,i→0\hat{p}_{u,i} \rightarrow 0e^u,i\hat{e}_{u,i}≈e^u,i\approx \hat{e}_{u,i}

のとおりとなる。

モデルと学習アルゴリズム

prediction model fθ(xu,i)f_{\theta}(\boldsymbol{x}_{u,i}) とimputation model gϕ(xu,i)g_{\phi}(\boldsymbol{x}_{u,i}) の2つのモデルを同時に学習する方法を提案。

prediction modelは パラメータ θ\theta を持ち、特徴量ベクトル xu,i\boldsymbol{x}_{u,i} から真のrating ru,ir_{u,i} の予測精度を高めることを目的として学習を行う。具体的なlossは下記。

Lr(θ,ϕ)=∑u,i∈D(e^u,i+ou,i(eu,i−e^u,i)p^u,i)+v∥θ∥F2\mathcal{L}_{\mathrm{r}}(\theta, \phi)=\sum_{u, i \in \mathcal{D}}\left(\hat{e}_{u, i}+\frac{o_{u, i}\left(e_{u, i}-\hat{e}_{u, i}\right)}{\hat{p}_{u, i}}\right)+v\|\theta\|_{F}^{2}

where

  • eu,i=(fθ(xu,i)⏟r^u,i−ru,i)2e_{u,i} = ( \underbrace{f_{\theta}(\boldsymbol{x}_{u,i})}_{\hat{r}_{u, i}} - r_{u,i} )^2
  • e^u,i=(fθ(xu,i)−gϕ(xu,i)−⊥(fθ(xu,i)))2\hat{e}_{u,i} = (f_{\theta}(\boldsymbol{x}_{u,i})-\left.g_{\phi}\left(\boldsymbol{x}_{u, i}\right)-\perp\left(f_{\theta}\left(\boldsymbol{x}_{u, i}\right)\right)\right)^{2}

一方imputation modelは パラメータ ϕ\phi を持ち、特徴量ベクトル xu,i\boldsymbol{x}_{u,i} から予測誤差 eu,ie_{u,i} の推定精度を高めることを目的として学習を行う。具体的なlossは下記。

Le(θ,ϕ)=∑u,i∈O(e^u,i−eu,i)2p^u,i+ν∥ϕ∥F2\mathcal{L}_{\mathrm{e}}(\theta, \phi)=\sum_{u, i \in \mathcal{O}} \frac{\left(\hat{e}_{u, i}-e_{u, i}\right)^{2}}{\hat{p}_{u, i}}+\nu\|\phi\|_{F}^{2}

where

  • eu,i=ru,i−fθ(xu,i)e_{u,i} = r_{u,i} - f_{\theta}(\boldsymbol{x}_{u,i})
  • e^u,i=gϕ(xu,i)\hat{e}_{u,i} = g_{\phi}(\boldsymbol{x}_{u,i})

学習アルゴリズムは上記のモデルを交互に学習する方法を採用。詳細は下記を参照。

実験

MARとMNARの両方で収集したデータを含むCOAT[Schnabel et al., 2016]とYAHOO[Marlin & Zemel, 2009]で検証。前回同様Propensityの推定にMARなデータ、つまりテストデータを使っている。。。
結果は下記の通りで、先行研究のMF-IPSよりも良くなっていることを示している。

おわりに

一旦上記の実験結果を再現できるか実装していますが、残念ながら現時点で再現できていないです。。。再現できたらその段階で公開したいです。