n週連続推薦システム系論文読んだシリーズ 18週目
morinota
推薦システムのオフライン評価には、ユーザ-アイテム間のinteraction(ex. クリック, 購入, 評価, etc.)の観測データを用いる.しかし様々な交絡因子(Confounding factor)によってbias(選択bias)が含まれる. (因果推論の用語だが、推薦の文脈で言えば、“interactionの観測” -> “ユーザのアイテムへの嗜好度合い” の因果関係の観測に影響を与えうる第三の因子.)
これにより観測データにて欠損したinteractionはMNAR(Missing Not At Random)となる. (このような観測データをMNARデータと呼ぶ…!)
本論文は、3つ目のアプローチに焦点を当てている.
本論文では3つ目のアプローチに焦点を当てている.
MCAR(Missing Completely At Random)とMAR(Missing At Random)は区別される事がある. (ただし本論文ではよりシンプルに、)
この区別は、欠損データ分析理論(missing data analysis theory)に基づいており、最初に[16]によって提案され、後に[18]によって推薦者システムの文献に紹介された.
この方法は通常、“forced rating approach”(強制格付けアプローチ)と呼ばれる方法によって実施される.
多くの文献は、MNARテストデータにおける真の性能に対して不偏な新しい推定量(i.e. 評価metricや損失関数)を設計することを提案している.
“intervention approach(介入アプローチ)”とも呼ばれる.
MARとMNARのデータセットの特性を分析するための確率的フレームワークを定義する. このセクションで定義した両データセットの特性を利用して、unbiasedなオフライン評価の為のアプローチを提案する.
\(D_{mar}\) の生成過程を述べる.(既存手法のforced ratings approachを想定.)
生成過程を U×I空間上で定義される確率分布\(P_{mar}(\mathcal{O}|u,i)\) を利用して導出する.
このような手法で収集されたデータセット \(D_{mar}\) を想定すると、ユーザとアイテムの事後確率の経験的な推定値は (ほぼ)一様に分布している はずである:
\[ P_{mar}(u|\mathcal{O}) = \frac{|O_{u}^{mar}|}{O^{mar}} \sim \frac{1}{|U|}, \forall u \in U \tag{1} \]
\[ P_{mar}(i|\mathcal{O}) = \frac{|O_{i}^{mar}|}{O^{mar}} \sim \frac{1}{|I|}, \forall i \in I \tag{2} \]
ここで、\(O^{mar}_{u}\)と\(O^{mar}_{i}\)はそれぞれ、ユーザuとアイテムiの\(O^{mar}\)で観測されたInteractionである.
また、観測されるユーザとアイテムは独立のはずなので、(u,i)の事後分布も独立であることがわかり、以下のように書ける:
\[ P_{mar}(u,i|Q) = P_{mar}(u|Q) \cdot P_{mar}(i|Q) \in \frac{1}{|U||I|}, \forall(u,i) \in U \times I \tag{3} \]
ここで、\(P_{mar}(u,i|Q)\)は、特定のユーザとアイテムのペアの同時事後分布(=事後分布の同時分布、みたいな?)を表す。 よって、MARデータ \(D_{mar}\) の特性として、式(3)の性質を満たしているはずである.
同様に、MNARデータセット \(D_{mnar} = {O^{mnar},Y^{mnar}}\) の生成過程をモデル化する.
MNARデータセット \(D_{mnar}\) が収集されている場合、MARデータセットで行ったように、 \(O^{mnar}\) のユーザとアイテムの事後確率を推定する事ができる. 今度は一般的に、以下の性質があるはず. (ここでいう事後確率は、O=1のinteractionをランダムに取得した時に、それがユーザuのinteractionである確率、みたいなイメージ…!)
\[ P_{mnar}(u|\mathcal{O}) = \frac{|O^{mnar}_{u}|}{O^{mnar}} \neq \frac{1}{|U|}, \forall u \in U \tag{4} \]
\[ P_{mnar}(i|\mathcal{O}) = \frac{|O^{mnar}_{u}|}{O^{mnar}} \neq \frac{1}{|U|}, \forall u \in U \tag{5} \]
一般に、ユーザとアイテムは一様に分布しているわけではないので、特定のエントリーが観測された場合、すなわち\(\mathcal{O} = 1\)の場合、同時事後確率 \(P_{mnar}(u,i|\mathcal{O})\) に対してユーザとアイテムの事後独立性は仮定できない. よって…
\[ P_{mnar}(u,i|Q) \neq P_{mnar}(u|Q) \cdot P_{mnar}(i|Q), \forall (u,i) \in U \times I \tag{6} \]
本セクションで示した定式化(式(3)と式(6))を使って、次のセクションでdebiasの為のサンプリング戦略を設計する. (なるほど…?これらの事後確率の定式化をサンプリング戦略で使うのか!) (このセクションは、MARデータやMNARデータの性質はかくあるべき、というような話…!!)
偏ったデータから偏りのない評価を行うために、伝統的なランダム hold-out テストセットの代わりに、介入テストセット(Intervened test set)を生成して使用する. 本論文では、WTD と WTD_H の2つのサンプリング戦略を提案している.
数式で表すと以下:
\[ P_S(u,i|\mathcal{S}) \approx P_{mar}(u,i|\mathcal{O}), \forall(u,i) \in O^S \tag{7} \]
\[ P_S(u,i|\mathcal{S}) \approx P_{mar}(u,i|\mathcal{O}), \forall(u,i) \in O^S \tag{7} \]
この近似を得るために,ユーザアイテムの重み \(w = (w_{ui})_{u \in U ,i \in I}\) を用いて,サンプリング空間 \(O^{mnar}\) の事後分布,すなわち \(P_{mnar}(u,i|\mathcal{O})\) を調整する. 調整された重み付けMNAR事後分布を \(P_{mnar}(u,i|\mathcal{O},w)\) と表記する. つまり、以下の等式を満たせるような重みwを見つけたい:
\[ P_{mnar}(u,i|\mathcal{O},w) = P_{mar}(u,i|\mathcal{O}), \forall(u,i) \in O^{mnar} \tag{8} \]
MARデータセットがユーザとアイテムに一様に分布している事から、式(3)の独立性を利用して式(8)の右辺を書き換える:
\[ P_{mnar}(u,i|\mathcal{O},w) = P_{mar}(i|\mathcal{O}) \times P_{mar}(u|\mathcal{O}) \tag{9} \]
ユーザとアイテムのMNAR事後分布を検討した式(6)と同様に、重み付けMNAR事後分布においても ユーザとアイテムは一般に独立ではない. しかし、ここではユーザとアイテムを独立したものとして扱い、次のように求める:
\[ P_{mnar}(u,i|\mathcal{O},w) = P_{mnar}(i|\mathcal{O},w) \times P_{mnar}(u|\mathcal{O},w) \\ , \forall(u,i) \in O^{mnar} \tag{10} \]
式10は一般的には正しくないが、第6節で経験的に良い結果が得られることを示し、これを正当化する.(理論的には不当な式変形だけど、経験的に効果あるから採用!って話…!)
さて、式(10)を使って、式(9)を次の2つの式に分割することができる:
\[ P_{mnar}(u|\mathcal{O},w) = P_{mar}(u|\mathcal{O}) \tag{11} \]
\[ P_{mnar}(i|\mathcal{O},w) = P_{mar}(i|\mathcal{O}) \tag{12} \]
重み付き MNAR 事後分布に関する式(11)と式(12)の結果として、ユーザ-アイテムペアでユニークな重みの代わりに、ユーザ固有の重み \(w = (w_{u})_{u \in U}\) とアイテム固有の重み \(w = (w_i)_{i \in I}\) を定義して計算できる.
(ユーザとアイテムの重みが独立していることは、スケーラビリティの面でも有利. \(|U \times I|\)の代わりに、\(|U| + |I|\)の重みだけを計算すればよいから. そして推薦システムの領域では\(|U \times I| > |U|+|I|\) となるので…!)
本論文では、重み付けMNAR事後分布をモデル化する最も簡単な解決策として, \(P_{mnar}(.|\mathcal{O},w) = w_{.} \cdot P_{mnar}(.|\mathcal{O})\) を提案している (元々の事後確率を重み付けする…!シンプルな作戦!). これを式(11)及び式(12)に当てはめると、各ユーザ及びアイテムの重み付け分布について、それぞれ\(w_u \cdot P_{mnar}(u|\mathcal{O})=P_{mar}(u|\mathcal{O})\) と \(w_i \cdot P_{mnar}(i|\mathcal{O})=P_{mar}(i|\mathcal{O})\) が得られる.
この2つの式を逆にすれば、重み\(w\)の計算式ができあがる:
\[ w_{u} = \frac{P_{mar}(u|\mathcal{O})}{P_{mnar}(u|\mathcal{O})}, \forall u \in U \tag{13} \]
\[ w_{i} = \frac{P_{mar}(i|\mathcal{O})}{P_{mnar}(i|\mathcal{O})}, \forall i \in I \tag{14} \]
算出された重みは、サンプリング空間のMNAR分布と目標のMAR分布との乖離を測る量と考えることができる.
特定の重み\(w_u, w_i\)が対応するユーザorアイテムのMNAR分布を調整するため、ウェイトを直接使用してサンプリング確率分布をモデル化する. すなわち…
\[ P_S(\mathcal{S}|u,i) = w_u \cdot w_i \]
サンプリングにおける重みの効果は、MAR分布に対するMNARサンプリング空間のユーザとアイテムの事後確率がどれだけ乖離しているかによって、特定のユーザとアイテムのペアがサンプリングされる確率が増減すること.
本サンプリング戦略をWTDと呼び、実際には上式の代わりに、\(P_S(\mathcal{S}|u,i) = w_u \cdot (w_i)^2\) を採用する.(アイテムのbias対処により重きを置いた方が経験的に結果が良かったみたい…)
(この変形は、MNARデータにおいてアイテムの人気が最も影響力のある交絡因子の1つであるとする文献で報告された先行研究[21, 24]に照らして理にかなっている.)(popularity biasが最も影響のある交絡因子の一つなのか…!)
WTDでは、近似に必要な事後分布(=\(P_{mar}(u,i|\mathcal{O})\))を与えるために、MAR-likeデータを必要としていた. しかし“forced rating approach”の説明の際に述べたように、MARデータは高価であったり、収集不可能だったりする. さらに、手元にそれなりの量のMARのようなデータがある場合には、そもそもそのままunbiasedなテストセットとして使用すれば良い.
本論文では、WTDを MAR-likeデータが無い場合でも適用できる様に拡張した.
MARデータの事後確率分布はユーザ & アイテムに対して一様である(i.e. \(P_{mar}(u|\mathcal{O}) = 1/|U|, P_{mar}(i|\mathcal{O}) = 1/|I|\))ことが分かっており、この情報が本サンプリングアプローチに必要なすべてである(うんうん!やっぱり!). そのため、重み\(w_u, w_i\)を計算する際にこの仮説のMAR事後分布を利用することで、MAR-likeデータセットが不要になる.
このWTDをMARデータ不要ver.に拡張したサンプリング戦略を、WTD_H(Hは “hypothesized”の略)と命名する.
MNARデータから介入テストセットを作成する様々なサンプリング戦略の良し悪しを評価し、本論文で提案された WTD と WTD_H の活用可能性を探る為に、オフライン実験を行った.
実験において5種の推薦モデルを学習させ、全てのモデルが推薦アイテムのランク付けリストを生成する.
各戦略はサンプリング確率分布 \(P_{S}(\mathcal{S}|u,i)\) を定義し、元のMNARテストセット \(O^{he}\) (i.e. \(Y^{he}\))から介在テストセット \(O^{S}\) (i.e. \(Y^{S}\))をサンプリングする.
table2は、各推薦モデルに関するモデル精度指標(Recall@10)のground-truth(=MARテストセット \(Y^gt\) による評価結果)と、各サンプリング戦略による介在テストセットを使った推定値のpercentage difference.
table3は、2種類のデータセットに対する5種のMNARサンプリング戦略によるモデルの順位付け結果の、ground-truthとの類似度の結果.
table4は、MFモデルを順位付け対象から除いたver.の結果.F
提案手法の利点: