n週連続推薦システム系論文読んだシリーズ 17週目
morinota
映画の例で、選択バイアスが従来の評価に与える悲惨な影響について考えてみる. \(u \in {1,...,U}\)をユーザidx、\(i \in {1,...,I}\) を映画idxとする.
このデータについて、以下の二つのタスクの評価を考えてみる.
タスク1では,これらの予測された評価行列 \(\hat{Y}\)が,真の評価行列\(Y\)をどれだけ反映(予測)できたかを推定(評価)したい…!
標準的なaccuracy metricの場合、次のように書くことができる.
\[ R(\hat{Y}) = \frac{1}{U \cdot I} \sum_{u=1}^{U} \sum_{i=1}^{I} \delta_{u,i}(Y, \hat{Y}) \tag{1} \]
ここで、\(\delta_{u,i}(Y, \hat{Y})\) は真の値と予測値の差を表し、具体的な \(\delta()\) 関数は採用するmetricによって異なる.
しかし実環境では真の評価行列\(Y\)は一部の要素しか観測されない為、従来は以下の様に、観測済みエントリ{u,i}のみを用いて\(R(\hat{Y})\)を推定する.
\[ \hat{R}_{naive}(\hat{Y}) = \frac{1}{|{(u,i):O_{u,i} = 1}|} \sum_{(u,i):O_{u,i}=1} \delta_{u,i}(Y,\hat{Y}) \tag{5} \]
これを、誤差関数 \(R(\hat{Y})\) のnaive推定量と呼ぶ. このnaiveさが、図1の\(\hat{Y}_1\)、\(\hat{Y}_2\)に対する重大な誤判定を招いてしまう.
図1の例を見ると、\(\hat{Y}_1\) の方が \(\hat{Y}_2\) よりも予測精度が優れているはず. しかしnaive推定量\(\hat{R}_{naive}(\hat{Y})\)は、\(\hat{Y}_2\)の方が予測誤差が小さいと判断してしまう… これは選択バイアスによるものであり、1点の評価は観測されにくい為、誤差関数のnaive推定量では過小評価される。 より一般的に言えば、選択バイアス(MNARデータ)下では、naive推定量は真の誤差関数の不偏推定量ではない(Steck, 2013). すなわち:
\[ E_{O}[\hat{R}_{naive}(\hat{Y})] \neq R(\hat{Y}) \tag{6} \]
タスク2では、予測評価値の精度ではなく、より直感的に推薦するか否かの意思決定の精度を評価する. この為に\(\hat{Y}\)を再定義し、図1 右下の \(\hat{Y}_3\) では、\(O\) に類似したbinary行列として推薦結果を符号化している. ここで、\([\hat{Y}_{u,i} = 1]\) ⇔ [i が u に推薦される]とし、1ユーザあたりk件のみ推薦する.
推薦の精度を評価するmetricsとして一般的なのは、ユーザが推薦された映画から得るCumulative Gain(累積利益, CG). 図1の例では、推薦映画リストの平均評価として定義する. 以下の \(delta()\) を用いて、再び式(1)の誤差関数を定義する事ができる.
\[ CG: \delta_{u,i}(Y, \hat{Y}) = (I/k) \hat{Y} \cdot Y_{u,i} \tag{7} \]
タスク1と同様に式(5)のnaive推定量を用いる方法もあるが、タスク2においてもnaive推定量は\(R(\hat{Y})\)の不偏推定量ではない.
\(Y\)の観測値が欠損している状況で推薦システムの性能の不偏推定値を得る為に、本論文では、因果推論のaverage treatment effectsの推定方法を活用するアプローチを採用する.
推薦タスクを、ある薬で患者を治療するような介入(intervention)と同様に考えると、新しい治療方針(ex. 女性には薬Aを、男性には薬Bを与える = 新しい推薦結果\(\hat{Y}\)) の効果を推定したい.
どちらの場合も、ある患者(i.e. ユーザ)がある治療(i.e. 映画)からどれだけ恩恵を受けたかについては部分的な知識しかなく(すなわち、\(O_{u,i} = 1\)の \(Y_{u,i}\)のみ…!)、\(Y\)における潜在的な結果の大部分は未観測である、という課題がある.
選択バイアスを処理する鍵は、Observed Matrix \(O\)の観察パターンを生成するプロセスを理解することにある. このプロセスは、一般的に因果推論におけるAssignment Mechanism、欠損データ分析におけるMissing Data Mechanismと呼ばれる.
論文では”観察パターン生成プロセス”を理解する為に、以下の2つの設定を区別して考える.
(observational settingに必要な) propensity \(P\)の推定の議論は後回しとし、まずはexperimental setting(\(P\)が明らかになっているケース)に焦点を当てる.
推薦タスクや予測タスクにも適用されるInverse-Propensity-Scoring (IPS)推定量 (Thompson, 2012; Little & Rubin, 2002; Imbens & Rubin, 2015) は、次のように定義される(名前通り、propensityの逆数を乗じてscoringしてる…!):
\[ \hat{R}_{IPS}(\hat{Y}|P) = \frac{1}{U \cdot I} \sum_{(u,i):O_{u,i} = 1} \frac{\delta_{u,i}(Y, \hat{Y})}{P_{u,i}} \\ = \frac{1}{U \cdot I} \sum_{u} \sum_{i} \frac{\delta_{u,i}(Y, \hat{Y})}{P_{u,i}} \cdot O_{u,i} \\ \because O_{u,i} \text{は観察されたか否かのbinary変数なので...!} \tag{10} \]
naive推定量 \(\hat{R(\hat{Y})}_{naive}\) とは異なり、IPS推定量はあらゆる確率的な”観察パターン生成プロセス”において不偏推定量である. (正しい \(P\)さえ分かっていれば…!) experimental settingの場合は真の\(P\)が分かるので、IPS推定量を活用できる.
IPS推定量は周辺確率\(P_{u,i}\)のみを必要とし、その不偏性は 実際の観測結果 \(O\) には影響されない.
(証明)\(O\)に対するIPS推定量の期待値を算出してみる.
\[ E_{O}[\hat{R}_{IPS}(\hat{Y}|P)] = \frac{1}{U\cdot I} \sum_{u} \sum_{i} E_{O_{u,i}}[\frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}} O_{u,i}] \\ = \frac{1}{U\cdot I} \sum_{u} \sum_{i} \delta_{u,i}(Y,\hat{Y}) \\ \because \text{propensityの定義より...} P_{u,i} = E_{O_{u,i}}[O_{u,i}] \\ = R(\hat{Y}) \tag{10.5} \]
IPS推定量のばらつきを抑える手法として、制御変量(control variates)の利用がある(Owen, 2013). IPS推定量に適用すると、\(E_{O}[\sum_{(u,i):O_{u,i}=1} \frac{1}{P_{u,i}}]= U \cdot I\) となることがわかる.(これを使うと、IPS推定量の分散を低減できる…??) これにより、以下のSNIPS(Self Normalized Inverse Propensity Scoring)推定量が得られる:
\[ \hat{R}_{SNIPS}(\hat{Y}|P) = \frac{ \sum_{(u,i):O_{u,i} = 1} \frac{\delta_{u,i}(Y, \hat{Y})}{P_{u,i}} % 分子=元のIPS推定量の式. }{ \sum_{(u,i):O_{u,i}=1} \frac{1}{P_{u,i}} % 制御変量? } \tag{11} \]
分子は元のIPS推定量の式. 分母は制御変量?
SNIPS推定量はIPS推定量よりも分散が小さいことが多いが、小さいバイアスを持っている.
Observational Settingの場合、前述した通り、propensity \(P\) の推定から始める必要がある. (\(P\)を推定した後は、experimental settingと同様にIPS推定量やSNIPS推定量を使える.)
ここで重要なのは、我々は \(P\) を完璧に推定する必要はない、という事である. なぜなら我々は、\(P\)が一様であるという仮説に基づくnaive推定量よりも”良い(マシな)“\(P\)を推定できれば良いのである…!
真の評価行列\(Y\)の各要素を観測する周辺確率を\(P\)とし、すべてのu, iに対して\(\hat{P}_{u,i} > 0\)となるようなpropensity推定量を\(\hat{P}\)とする.
\(\hat{P}\) を用いたIPS推定量(10)のバイアスは、以下:
\[ bias(\hat{R}_{IPS}(\hat{Y}|\hat{P})) = \sum_{u,i} \frac{\delta_{u,i}(Y, \hat{Y})}{UI} [1 - \frac{P_{u,i}}{\hat{P}_{u,i}}] \tag{15} \]
復習だが、ここでの我々の目的は、ユーザ\(u\)とアイテム\(i\)の評価値が観測される確率\(P_{u,i}\)を推定する事.
一般にpropensityは以下に依存している可能性がある.
式にするとこう:
\[ P_{u,i} = P(O_{u,i} = 1| X, X^{hid}, Y) \tag{17} \]
続いて、2つのシンプルなpropensity推定モデルをざっと紹介するが、ドメイン固有のニーズに対応できる技法も幅広く存在する(例:McCaffrey et al, 2004)
この方法では、\(P_{u,i}\) と \(X\)、\(X^{hid}\) との間の依存関係が無視できると仮定することで、\(P(O_{u,i}|X, Xhid, Y)\) を推定する.(かなりラフな推定…!)
この仮定により、以下のnaive bayes推定量が得られる:
\[ P(O_{u,i} = 1|Y_{u,i} = r) = \frac{P(Y=r|O=1)P(O=1)}{P(Y=r)} \tag{18} \]
\[ P_{u,i} = \sigma(w^T X_{u,i} + \beta_{i} + \gamma_{u}) \]
合成データを用いて、experimental setting と observational setting の両方で提案手法の経験的性能とロバスト性を探る.
また、実世界のデータセットにおいて、MNAR(Missing Not At Random)データに対する最先端の共同尤度法(Hernandez- ´ Lobato et al, 2014)と比較した.
表1は、\(\alpha = 0.25\) (=結構MNARなデータ)の場合のMAEとDCG@50の推定値の結果.
図2は、各推定量が”真のMSEとDCGをそれぞれどの程度正確に推定できたか”をRMSEを用いて表したもの.
次に、このような誤差関数(=モデルの性能)の推定精度の向上が、ERMによる学習効果の向上につながるかどうかを、再びExperimental Setting で検証してみた.
図3 左図は、MF-IPSとMF-naiveの真の予測性能(真の評価行列\(Y\)に対する誤差関数)をMSEで算出した結果. MF-IPSは従来のMF-naiveを常に上回る.
図4は、propensity推定が必要なObservational Settingにおいて、propensity 推定の不正確さが推薦モデルの検証にどのような影響を与えるかを示したもの. (propensity推定にはナイーブベイズを採用)
また図3 右図は、propensity が不正確な場合に推薦モデルの学習にどのような影響があるかを示している. propensitiyを推定したMF-IPS-NBのMSE予測誤差を、propensityが既知のMF-NaiveとMF-IPSと比較したもの.
ここでも、MF-IPS-NBは、著しく劣化した(MCARの観測データ数が少ない為…!)propensity推定値においてもMF-Naiveを上回り、本アプローチのロバスト性を実証している. (そもそもMF-naiveが超絶劣化したpropensity推定と見なせるから…!)
MCARデータとMNARデータの両方を含んだベンチマークデータセットを用いて性能を評価(オンライン実験をした訳では無い). MF-IPSにおいてpropensity推定はロジスティック回帰を用いた.
表2は、各推薦モデルのMCARテストセットに対する評価値の予測精度を評価したもの. MF-IPSは、MF-naiveやHL-MNARやHL-MARを大幅に上回った. 更にMF-IPSの性能は、YahooデータセットのSOTAに近い結果だったとの事.