[2307.01212] Of Spiky SVDs and Music Recommendation
概要
-
推薦システムにおいて, Truncated SVD (Singular Value Decomposition) は類似アイテムの検索やアイテムの埋め込みに広く使用される
-
推薦データセットで自然に生じる「スパイク構造」について調査
- スパイクの強さを定量化するメトリックの提案
-
スパイクがコミュニティを表し, ノルムがコミュニティ内の相対的な重要度を表すっぽい
- 新たに発見された理論的理解を基に, データの追加に伴う音楽埋め込みのトップ \(k\) の類似アイテムの変化を推定するユースケースを提案
Intro: SVD とそのスパイク
SVD は推薦システムのための埋込表現を得る手段として便利に使われている. でもよく分かってないことが多い.
-
\(M \approx U \Sigma V^\ast\) と分解した場合に
-
埋め込み表現として \(U\) を使うか \(U \Sigma\) を使うか, はたまた \(U \Sigma^p\) を使うか
-
距離/類似度として
実用上は実験してみて最も良いものを使うわけだが, そこに理論的な裏付けは見つかってない.
SVD によるベクトルはスパイクと呼ばれる幾何学的構造が観測されやすい (Fig 1). これは原点を通る直線上の周りにベクトルが集まって self-organize する傾向があることを示している.
Truncated SVD の詳細
データセットを表現する行列 \(M\) を \(\hat{M} = U \Sigma V^\ast\) で近似することを考える ( \(\cdot ^\ast\) は随伴行列).
-
次元数
-
\(M \in \mathbb{R}^{n \times m}\) に対して,
- \(U \in \mathbb{R}^{n \times f}\)
-
\(V \in \mathbb{R}^{m \times f}\)
-
制約
-
\(U, V\) は直交行列
- \(U^\ast U = V^\ast V = I_f\)
- \(\Sigma\) は対角行列
この下で \(\| M - \hat{M} \|\) を最小化する. SVD 分解した結果, 普通使うのは \(U\) または \(U \Sigma\) だけで, \(V\) は気にしない.
- この最適化の中で特異値を大きいものから \(f\) 個だけ残すようなものを Truncated SVD という
-
\(M \in \mathbb{R}^{n \times m}\) の代わりに, \(M M^\ast \in \mathbb{R}^{n \times n}\) を考えても同じ
-
特異ベクトル, 特異値の代わりに固有ベクトル, 固有値を考えることになる
- close-form に解いた場合は同じ \(U\) が得られる
-
特に \(M M^\ast\) は対称行列で都合が良いので, \(M\) の代わりに対称行列 \(M M^\ast\) に置き換えて考える.
- このあと \(M\) と出てきたら暗に 対称行列 としてる.
インタラクション行列についてのグラム行列を考えてる. 下の \(M\) が item x user 行列のときグラム行列 \(M M^\ast\) は item x item 行列になってて, これの SVD 分解をすることでアイテムの特徴量を得る. 得られる \(\Sigma\) は変わるはずだけど, そんなに本質的に変わらないから気にしない... ということかな.
Spikeness
SVD 分解によってベクトルの集合 \(E\) が得られたとき, これについてのスパイクの度合いを表す指標 Spk を定義する.
ざっくりいうと,
-
得られたベクトル集合 \(E\) をクラスタリングする
-
ノルムが大きいベクトルをスパイクの代表点にする
- コサイン類似度が近いベクトルを同じスパイクに属するとしてクラスタリングしてく
- 貪欲に取ってく
-
スパイクの個数の割合を Spk として定める
- \(|E|\) に対して \(K\) 個のクラスタが得られたら \(\mathrm{Spk} = K/|E|\)
詳細
アルゴリズムを詳細に書くと次の通り
-
Input:
-
閾値 \(\theta, \rho\)
- \(\theta = 0.9\)
- \(\rho = 50\%\)
- ベクトルの集合 \(E\)
-
初期値
- \(n \leftarrow |E|\) , はじめに与えられた点の個数
- \(K \leftarrow 0\) , クラスタの個数
-
While \(|E| \gt (1 - \rho) \times n\)
-
ノルムが最も大きいものを選ぶ
-
\(C \leftarrow \{ e \mid e \in E, \cos(e^\ast, e) > \cos \theta \}\)
-
クラスタリング済みの点を \(E\) から取り除く
- \(E \leftarrow E \setminus C\)
- \(K \leftarrow K + 1\)
-
Output:
この値が小さいほどスパイク状に分布してると言える. [Fig 1] でいうと Deezer と Spotify がこれ.
グラフモデル
今見てきたスパイク構造に対応するようなグラフモデルを考える.
Stochastic Block Model (SBM)
「コミュニティ」のグラフ表現
-
\(n\) 頂点
- \([n] = \{1,2,\ldots,n\}\)
-
\(K\) コミュニティ
- \([K] = \{1,2,\ldots,K\}\)
-
頂点はコミュニティに属している
- \(C \colon [n] \to [K]\)
- 頂点 \(i (1 \leq i \leq n)\) はコミュニティ \(C_i (1 \leq C_i \leq K)\) に属する
-
コミュニティ間のエッジ
- コミュニティ同士が確率的にエッジで結ばれる
-
隣接行列 \(B\)
- \(B \in [0,1]^{K \times K}\)
- \(B_{ij} = B_{ji}\) がコミュニティ \(i,j\) がエッジで結ばれる 確率
-
頂点間のエッジ
- 頂点が属するコミュニティ \(\times B\) からのサンプリングでエッジを決める
-
\(A \in \{0,1\}^{n \times n}\)
- \(A_{ij} = A_{ji} \sim B_{C_i, C_j}\) (ベルヌーイ試行)
Degree-Corrected SBM (DCBM)
SBM に更にパラメータを追加する
-
頂点 \(i\) にパラメータ \(\alpha_i \in [0,1]\) を追加
-
行列 \(A\) の値にはこれが更に掛け算される
- \(A_{ij} = A_{ji} \sim \alpha_i \alpha_j B_{C_i, C_j}\)
Spike と DCBM の対応
SVD の Spike から DCBM の構築
- インタラクション行列（のグラム行列）による \(\hat{M} = U\Sigma V^\ast\)
-
\(E = U \Sigma\)
- 各行 \(e_i\) が item の embedding
-
\(\{ e_1, e_2, \ldots \}\) をスパイクにクラスタリングする
- \(K\) のスパイクが見つかったとする
- 各スパイクの代表を \(\{ s_1, s_2, \ldots, s_K \}\) とする
グラフを構築する
-
\(n\) 頂点
-
\(K\) コミュニティ
-
アイテム \(i\) は \(C_i\) に属する
-
\(\alpha\) を決める
-
\(e_i \approx \alpha_i s_c\)
- \(0 \leq \alpha_i \leq 1\)
- ただし \(s_{C_i}\) はアイテム \(i\) が属するクラスタの代表
- \(B_{ij} = \langle s_i , s_j \rangle\)
以下を得る
-
アイテム \(i,j\) の関連度
- \((M M^\ast)_{ij}\)
- \(= (U\Sigma V^\ast V \Sigma^\ast U^\ast)_ij\)
- \(= (U \Sigma \Sigma^\ast V^\ast)_ij\)
- \(= \langle e_i,e_j \rangle\)
- \(= \alpha_i \alpha_j \langle s_{C_i} s_{C_j} \rangle\)
- \(= \alpha_i \alpha_j B_{{C_i} , {C_j}}\)
知見
コサイン類似度を使うか内積を使うか
コサイン類似度を使うことはパラメータ \(\alpha\) を無視することに等しい. 発見性 (serendipity) を重視したい場合にはそちらのほうが良い.
コミュニティ間の距離を正しく測りたい場合は内積を使わないといけない.
\(f\) のチューニング
Spk を指標にして \(f\) のチューニングが出来る. \(f\) が小さい間は Spk はおおよそ正比例する. (つまり \(f\) を大きくするに従ってスパイクの個数が増える.)
あるときから Spk が急激に大きくなる (ここでスパイク構造が壊れたと考える). その直前の \(f\) が良いもの