Debiased Offline Evaluation of Recommender Systems: A Weighted-Sampling Approach

[nogawanogawa]

論文URL

https://cora.ucc.ie/bitstream/handle/10468/10209/Carraro_Bridge_CORA.pdf?sequence=1&isAllowed=y

著者

Carraro, Diego; Bridge, Derek G.

会議

SAC '20

背景

推薦システムのオフライン評価には、MNAR（Missing Not At Random）なデータを使用する事による一定のバイアスが発生しており、これによって推薦の正しい性能の測定が阻害されている。

一般的なアプローチとして、MNARテストデータで使用するために、新たな超不偏的な性能推定器を設計することであるが、バイアスの影響全てに対応できるわけではない可能性が高く、また、データが特定の前提条件を満たさなければならない場合があり、必ずしも有効とは言えない。

これとは別の方法としてMNARなデータからサンプリング戦略によってMAR（Missing At Random）なテストデータセットを作成することが考えられる。

目的

population biasに対応するために、MNAR (missing not at random) からMAR (missing at random)なテストデータセットを作成する

アプローチ

• 介入データを生成するためのSKEWサンプリング戦略に代わる新たな手法の使用
  • MNARデータにおけるユーザとアイテムの分布と，それらに対応するターゲットMAR分布との間の乖離を考慮して重みを計算する，重み付きサンプリング戦略

[nogawanogawa]

背景

推薦システムのオフライン評価には、MNAR（Missing Not At Random）なデータを使用する事によるバイアスが発生し、それによって本来不偏であるはずの性能の測定が阻害されている。

例えば、画面のどこにアイテムが表示されていたかによってポジションバイアスが発生したり、ユーザーとアイテムのインタラクションによってフィードバックループによって偏ったアイテムが優先して表示されるようになっていたり、特定のユーザーとアイテムの関係が別のアイテムとの関係に対して影響を与えることもある。

これらは観測したデータセットが、完全な状態のインタラクションデータから偏ってデータが欠けている(MNAR)ことを意味する。

この問題に対するアプローチは大きく3つあって

1. 評価のためにMARなデータを取得する
2. MNARなデータからバイアスを補う推定量を作成する
   • 特定の条件を満たす場合には有効
   • ATOP推定量など
3. MNARなデータからサンプリングを行うことでMARなデータを作成する
   • SKEW（著者の言うこの時点でのSOTAらしい）など
     • population biasを考慮したサンプリング
     • アイテムの人気に反比例してサンプリングを行う

というアプローチがある。

[nogawanogawa]

目的

population biasに対応するために、MNAR (missing not at random) からMAR (missing at random) なテストデータセットを作成する

アプローチ

• 介入データを生成するためのSKEWサンプリング戦略に代わる新たな手法の使用
  • MNARデータにおけるユーザとアイテムの分布と，それらに対応するターゲットMAR分布との間の乖離を考慮して重みを計算する，重み付きサンプリング戦略

[nogawanogawa]

MCAR/MAR/MNAR

観測データの欠損に関する分類について確認する。 この論文ではMARとMNARを下記のような定義とは異なる使い方をしている（らしい）ので、そこだけ確認する。

• MNAR
  • user-itemのインタラクションの欠損は、データ自体が持つ交錯因子によって影響を受ける、偏りがある状態
• MAR
  • user-itemのインタラクションの欠損は、データ自体が持つ交錯因子によって影響を受けない、偏りがない状態

一般的な解釈

### MCAR (Missing Completely At Random) MCARは、user-item間のインタラクションは、推薦システムによるレーティング等の出力に依存しないことを意味する。 - MCARなインタラクション - 観測されたインタラクションに依存しない - 欠損したインタラクションに依存しない ### MAR (Missing At Random) MARは、user-item間のインタラクションは、観測されたインタラクション値には依存するが、欠損しているインタラクション値には依存しないことを意味する。 - MARなインタラクション - 観測されたインタラクションに依存する - 欠損したインタラクションに依存しない ### MNAR (Missing Not At Random) MNARは、user-item間のインタラクションは、観測されたインタラクション値にも、欠損しているインタラクションにも依存する。 - MNARなインタラクション - 観測されたインタラクションに依存する - 欠損したインタラクションに依存する

[nogawanogawa]

数式の定義

• U：user
• I : Item
• D : U × I の観測データセット、OとYからなる
  • O : U × I の{0,1}のバイナリデータセット。サンプリングされたかどうかを表す。相互作用が観測されたら1, 観測されていなければ0を示す
  • Y : Oで観測された対応する項目の実際の度合い、実数で示される
  • ここでYは一般性をもたせることができ、クリック数やレーティング、ビュー数、リスニング頻度などを表すことができる

[nogawanogawa]

生成過程について考える

※多分イメージこんな感じ

MARのモデリング

MARでは、user-itemインタラクションは交錯因子に影響を受けないと仮定している。 Yが必ず得られると仮定するならば、確率分布Pmarは下記のように記述できる。

ここで、ユーザー、アイテムについても独立と考えているため、下記も成立すると考えている。

MNARのモデリング

MNARは交錯因子の影響を受けるため、MARのようにサンプリング分布Pmnarがインタラクション値Yと独立しているとは言えない。

このままではMNARをMARに変換することはできない。

[nogawanogawa]

サンプリングアプローチ

我々のアプローチを紹介するにあたり、MNARデータ𝑂𝑚𝑛𝑎𝑟に加えて、いくつかのMAR的なデータ𝑂𝑚𝑎𝑟が利用可能であることを仮定して始めます。実際には、MARデータがない場合でも、我々のアプローチが使えることを4.3節で説明します。 我々の主なアイデアは、サンプリングされた𝑂𝑆における各ユーザーとアイテムのペアの事後確率分布、すなわち、以下のようにすることです。𝑃 (𝑢, 𝑖|S)は、𝑂𝑚𝑎𝑟 、すなわち𝑃 (𝑢, 𝑖 |O)で対応するユーザーとアイテムのペアで観測される事後確率分布とほぼ同じである。つまり、𝑂𝑆を、その事後確率の観点から𝑂𝑚𝑎𝑟と類似させたいのです。これを式で書くと、次のようになります。 この近似を得るために、サンプリング空間𝑂𝑚𝑛𝑎𝑟 、すなわち𝑃𝑚𝑛𝑎𝑟 (𝑢, 𝑖 |O)を、ユーザー項目の重み𝑤 = (𝑤𝑢𝑖 )𝑢 ∈𝑈 ,𝑖∈𝐼を用いて調整する（[19]と同様である）。修正された重み付きMNARの事後評価を𝑃𝑚𝑛𝑎𝑟 (𝑢,𝑖|O,𝑤)と表す。目標は以下のように重み𝑤を見つけることである。 典型的なMARデータセットがユーザーとアイテムに一様に分布していることから、式3の独立性を利用して、式8の右辺を書き換えて求める。 ユーザーとアイテムのMNAR後値を考慮した式6と同様に、ユーザーとアイテムの重み付きMNAR後値は、一般的には独立ではありません。しかし、ここでは独立であるかのように扱い、次のように求めます。 式10は一般的には真ではありませんが、セクション6で経験的に示して正当化します。セクション6で経験的に示して正当化します。 さて、10を使うと、式9を次の2つの式に分けることができます。 の式に分けることができます。 重み付きMNAR事後分布に関する式11、12の結果として、ユーザー・アイテム固有の重みの代わりに、ユーザー固有の重み𝑤 = (𝑢 𝑤 )𝑢 ∈𝑈とアイテム固有の重み𝑤 = (𝑖 𝑤 )𝑖 ∈𝐼を定義し、計算することができる1。 我々は、重み付きMNAR後値をモデル化するために、最も分かりやすい解を提案する。すなわち、𝑃𝑚𝑛𝑎𝑟 (.|O,𝑤) = 𝑤.𝑃𝑛𝑎𝑟 (.|O) である。これを式11と式12に差し込むと、各ユーザーとアイテムの加重分布について、それぞれ 𝑤𝑢𝑃𝑚𝑛𝑎𝑟 (𝑢|O) = 𝑃𝑚𝑎𝑟 (𝑢|O), 𝑤𝑖𝑃𝑛𝑚𝑎𝑟 (𝑖|O) = 𝑃𝑚𝑎𝑟 (𝑖|O) が得られます。この最後の2つの式を単純に逆にすると、重みを計算する式ができあがります。 算出された重みは、サンプリング空間のMNAR分布と目標とするMAR分布との乖離を測る量と考えることができます。特定の重みは対応するMNAR分布を調整するため、重みを直接使用してサンプリング分布をモデル化します、すなわち、𝑃𝑆 (S|𝑢, 𝑖) = 𝑤𝑢𝑤𝑖 。サンプリング中、重みの効果は、MNARサンプリング空間におけるユーザーとアイテムの事後確率がMAR分布に対してどれだけ発散しているかに応じて、特定のユーザーとアイテムのペアがサンプリングされる確率を増加または減少させることである。 実際、予備実験に基づいて、我々は代わりに𝑃𝑢 (S|𝑢, 𝑖) = 𝑤𝑢 (𝑤𝑖 )2を使用しています。この変形（本稿の残りの部分ではWTDと表記）は、ユーザーの重みに対するアイテムの重みの重要性を高める。具体的には、(𝑤𝑖 )2は、𝑤𝑖が1より大きい場合には、𝑤𝑖より大きくなり、(𝑤𝑖 )2は、𝑤𝑖が1より小さい場合には、𝑤𝑖より小さくなる。この選択は、MNARデータにおいてアイテムの人気度が最も影響力のある交絡因子の1つであるとする文献で報告された先行研究[21, 24]に照らしても理にかなっている。

ここまでは、近似する必要のある事後分布を得るために、MARのようなデータがあることを前提にしていました。しかし、MAR的なデータは、先ほどの「強制評価アプローチ」の際に説明したように、収集するにはコストがかかりますし、不可能です。しかし、MARのようなデータがあれば、それをそのまま不偏のテストセットとして使うことができます。このデータを使って重みを計算し、MNARデータに介入してよりMARらしいテストセットを作ることは、無意味なことです。 実際には、MAR的なデータがない場合でも、我々のアプローチを使うことができます。 私たちのアプローチを使うことができます。我々は、MARデータの事後確率分布 forMARdataisuniform(𝑃 (𝑢|O)=1/|𝑈|,𝑃 (𝑖|O)=1/|𝐼|), 𝑚𝑎𝑟 𝑚𝑎𝑟 となり、これだけでサンプリング手法が可能になります。したがって、重みを計算する際にこの仮説分布を使えば、MARのようなデータセットを必要としません。この戦略をWTD_H（Hは "hypothesized "の略）と呼びます。

[nogawanogawa]

主なアプローチ

• サンプリングされたOの事後確率分布を観測された事後確率分布を近似させる

MNARの状況とMARを補正するために、下記のような重み係数を考える。

サンプリング中、この重みの効果は、MNARサンプリング空間におけるユーザーとアイテムの事後確率がMAR分布に対してどれだけ発散しているかに応じて、特定のユーザーとアイテムのペアがサンプリングされる確率を増加または減少させることである。

ここで、（多少雑ではあるが）MAR分布を

のようにして考えることで、簡易的にMAR分布を仮定し、それによって、MNARからMARにサンプリングする際の重み係数を計算し、これを用いてサンプリングする。

[nogawanogawa]

評価

• データセット
  • CoatShopping (ファッション)
  • Webscope R3 (音楽)
  • これらはMARで作成されたデータセットのため、実験ではこれらから前処理でMNARを作成している

上記のデータセットを使用して、ホールド・アウト法を使用して評価することを考える。

MARのデータセットを使用して学習した結果とMNARからサンプリング戦略を使用した介入データセットを使用して学習したときの結果が似ていることを「良い」としている。

サンプリング

• FULL : すべてサンプリング
• REG：テストセットの逆数の確率に従ってサンプリング
• SKEW
• WTD, WTD_H : 提案手法と現実的な提案手法

結果

スコアが良いのではなく、MARのデータセットを使用したときとサンプリングをしたときで結果が似ているほど優れているものとする。

WTD_H(現実的な提案手法)であっても、他のサンプリング手法と比べてMARのデータセットと比べて誤差が小さくなっているので、良さそうに見える。

[nogawanogawa]

よくわからないポイント

• スパースなデータセットのときもうまくワークするんだろうか？
  • 結構スパースなデータセットで実験しているけど、うまいことワークする理由がいまいちわからない。