[2208.09864] Towards Principled User-side Recommender Systems

• original paper: https://arxiv.org/abs/2208.09864

• GitHub - joisino/consul: Code for "Towards Principled User-side Recommender Systems" (CIKM 2022)

前回の Private Walk の続編.

概要

伝統的には推薦システムとは開発側が開発側の為に開発するものだったが, 近年では User-side Recommender System という概念が提唱され始めた(!). 提供されてるレコメンドがフェアでないと思ったユーザーに開かれたシステム. ユーザーはシステムのデータを使えないからログデータ等なしで推薦システムを構築することになる.

この論文ではシステムの推薦から隠されたアイテムの特徴ベクトルが復元できること, これを使って推薦システムが構築できることを見ていく. 理論上可能だがその通りに実装することを効率的ではない. 実用的に 健全な (sound) 推薦システムの実装も見てく. ここで満たすべき3つの性質を提唱する.

記法

• $[n]$ , 集合 $\{1,2,\dots ,n\}$ のこと
• グラフ $G=(V,E)$
• アイテム集合 $\mathcal{I}=[n]$
• protected group の集合 $\mathcal{A}$
  • アイテム $i$ の protected 属性 $a_i\in \mathcal{A}$
• インタラクションしたアイテムの集合 $\mathcal{H}\subset \mathcal{I}$
• システムが提供しているレコメンダ ${\mathcal{P}}_{\mathit{prov}}$
• レコメンドリストの長さ $K\in {\mathbb{Z}}_{+}$
• minimal requirement of fairness $\tau \in {\mathbb{Z}}_{\le 0}$
• num of dimentions of embeddings $d\in {\mathbb{Z}}_{+}$

問題設定

Service Provider's Official Recommendation System

システムの推薦システムとして item-to-item があるとする. これを ${\mathcal{P}}_{\mathit{prov}}$ と書く. アイテム $i$ があったとき, 推薦システムは $K$ 個のアイテム列を返す.

この $k$ 番目を ${\mathcal{P}}_{\mathit{prov}}(i{)}_k\in \mathcal{I}$ と書こう ( $k=1,2,\dots ,K)$ .

ユーザーから見て ${\mathcal{P}}_{\mathit{prov}}$ の中身は完全にブラックボックスであるのが普通だ. これを fair かつ white-box にするのが目的.

Embedding Assumptions

${\mathcal{P}}_{\mathit{prov}}$ の中身が次のようだと仮定する.

• アイテム $i$ には特徴ベクトル $x_i\in {\mathbb{R}}^d$ が割り当てられている
• ${\mathcal{P}}_{\mathit{prov}}$ は k-近傍を取ってくる操作である

$x$ 自体はユーザーからは絶対に見えない. で, やりたいことは ${\mathcal{P}}_{\mathit{prov}}$ の入出力のサンプルから $x$ を復元すること.

Sensitive Attributes

アイテム $i$ には何か具体的なセンシティブな属性 $a_i\in \mathcal{A}$ があるとする. 例えば性別や人種が考えられる. ここではユーザーから観測可能なものだけを取り扱う.

Misc Assumptions

ユーザーは既に何らのアイテム $\mathcal{H}\subset \mathcal{I}$ についてはインタラクションをしてきていて, それらについては知っていることとする. 例えば購入履歴である. テクニカルな仮定として, ${\mathcal{P}}_{\mathit{prov}}$ は $H$ のアイテムをレコメンドすることはないこととする.

提案される方法では $\mathcal{H}$ は空集合であっても機能する.

特徴量の復元

次のような推薦グラフ $G=(V,E)$ を考える

• 頂点集合 $V$ はアイテム集合 $\mathcal{I}$ ,
• $E$ は有向辺の集合であって,
  • アイテム $i$ について ${\mathcal{P}}_{\mathit{prov}}$ がオススメするものの中に $j$ があったとき,
  • 辺 $i\to j$
    • そのランクで重み等は考えない

実際に ${\mathcal{P}}_{\mathit{prov}}$ を用いることは出来るから, ユーザーから見て $G$ は観測可能な対象である. ひたすらページをクローリングしてく.

ランクまで考慮することでアイテムの類似度やスコアまで推定することは理論上可能だろうが, 話が難しくなりすぎるのでここでは考慮しない.

特徴ベクトルの復元を考える. ここで距離を保存する変換（平行移動, 回転, 拡大縮小）は無視して考える. それらは kNN の結果を変えないので.

Hashimoto らではこのグラフの上を Random Walk してくことで, 任意の誤差未満で復元できることを示している. （なんか色々条件付きで.）

Alamgir & von Luxburg は, グラフに適切に重みを割り当ててくことで, グラフ上の最短距離が特徴ベクトル間の距離と一致するように出来ることを示した. これを使うことで, グラフ $G$ を与えてアイテム同士（その特徴ベクトル）の距離行列

得られる.

Terada & von Luxburg は, 重みなし k-NN グラフに彼らの提案する Local Oridinal Embeddings (LOE) を割り当てることで復元できたことを示した. ことを示した. これも実際にはなんやかんや条件があるらしいが, ともかく本論文の実験では LOE を使ったそう.

色々言ったがともかく, 推薦グラフ $G$ が手に入ったらアイテムの特徴ベクトルは復元できる. そしてらこれを元にまた推薦システムを構築できるし, fair な推薦をするために後処理を施すこともできる (ETP; Estimate-then-postprocessing).

実験

Figure 1. 二次元のでトイデータから kNN グラフを作って復元する実験. 完璧じゃないけどほぼほぼ復元できてる.

Design Principles

これから User-side Recommendation, $Q$ を設計する. パラメータとして, 非負整数 $\tau$ を持たせる. これは fairness と preformance をトレードオフに調整する.

Consistency

${\mathcal{P}}_{\mathit{prov}}$ と比較したときに性能がほとんど劣化してないその度合いを指す. 特に $\tau =0$ のときに, ${\mathcal{P}}_{\mathit{prov}}$ と nDCG が下がってないときに consistent であるという. (全く同じ結果が出せるようになっていれば consistent だ.)

Soundness

どのレコメンド結果 $Q(i)\in I^K$ についても, 各属性 $a\in \mathcal{A}$ に属するアイテムが $\tau$ 個以上あること.

Locality

グラフ $G$ の部分だけからでも復元できること. 全てのアイテムについて集めてきてフルな $G$ を作れば復元できるのは良いけど, それだと実用上は大変なので, 一部のアイテムについてだけでもグラフを作って, そのアイテムの分だけでも特徴量ベクトルが復元できると便利.

提案手法, Consul

• 必要なデータ
  • ${\mathcal{P}}_{\mathit{prov}},\{a_i\mid i\in \mathcal{I}\},\tau ,\mathcal{H}$
  • 探索の上限 $L$
  • ソースとなるアイテム $i\in \mathcal{I}$
• 初期化
  • レコメンド結果, $R\leftarrow ()$
  • $p\leftarrow i$
  • 訪れたことのあるアイテム $V=\{\}$
  • 各属性を用いた回数, $c(a)\leftarrow 0,\mathrm{\forall }a\in A$
  • スタック, $S\leftarrow ()$
• 以下を $L$ 回繰り返す
  • $p\leftarrow$ スタック $S$ から $V$ に属さないものをポップ
    • そのようなものがなければループを抜ける
  • For $k=1,2,\dots ,K$
    • $j\leftarrow {\mathcal{P}}_{\mathit{prov}}(p{)}_k$
    • If $j\notin R\cup H$ and $\sum _{a\ne a_j}max(0,\tau -c(a))\le K-|R|-1$
      • $R\leftarrow R+(j)$
      • $c(a_j)\leftarrow c(a_j)+1$
    • If $|R|=K$
      • Return $R$ を返して終了
• あとは足りなかったアイテムを埋める処理
  • 省略

Consul は consistent で sound で local であることが示されている.

実験

Table 3. Oracle ( ${\mathcal{P}}_{\mathit{prov}}$ ) をそのまま使うのに比べて Consul を使うと Accuracy/nDCG がどのくらい変わるか. もちろん下がるがその下がり幅が小さいことが大事. また Access では Oracle を何回使うかだが, たいてい 10 回未満で済んでいる.

感想

Consul 自体は, まあそう, といった感じ. 提供されてる item-to-item レコメンダがあって, これを多段で叩くことでバリエーションが増やせるようになる（だからこそ fair なものが作れる）というのはノウハウとしてはなるほど. 特徴量ベクトルが復元できる話は結局, フェアなレコメンドを作りたい話とは関係なかった. それ自体は知識として有用だけど, LOE 単体のレポートな気がする, それは.