Netflix 論文 Negative Interactions for Improved Collaborative Filtering の一つ前に当たるモデル. \(\def\diag{\mathrm{diag}}\)
新しい線形の top-N 推薦モデルを提案する. 最適化は解析的に厳密に行い, アイテム数 \(I\) に対して \(O(I^3)\) で完了する（前処理を除く）. 元になったモデルとして SLIM (2011) があるのだが, 罰則項にあった L1 正則化を無くし, 制約も減らした. これによって最適化が高速に終わるようになった.
制約は行列 \(B\) の対角成分がゼロであることを言っている. これには \(B = I\) という自明解を完全に除去する意図がある.
上の最小化問題はラグランジュの未定乗数法を使って解ける.
列ベクトル \(\gamma = (\gamma_1, \ldots, \gamma_I) \in \mathbb R^I\) を導入して,
\[L(B,\gamma) = \| X - XB\|^2_F + \lambda \|B\|^2_F + 2 \gamma \cdot \diag(B)\]これを最小化することを考える.
これを \(B\) で注意深く微分すると,
\[\frac{\partial L}{\partial B}(B,\gamma) = -2X^t (X-XB) + 2\lambda B + 2 \diag(\gamma)\]ここで \(\diag\) は行列の対角成分のこと, またはそのベクトルを対角成分に持つ行列のこと. 今の式では後者の意味.
最小を取るときはこの微分値がゼロなので, そこから
\[B = (X^t X + \lambda I)^{-1} (X^t X - \diag(\gamma))\]を得る.
\(G = X^tX\) と定める. この行列には グラム行列 (Gram matrix) という名前がついてる.
\[B = (G + \lambda I)^{-1} (G - \diag(\gamma)) = I - (G + \lambda I)^{-1} (\diag(\gamma) + \lambda I)\]さて, 制約 \(\diag(B) = 0\) を思い出す. 上の式の対角成分を取り出すと,
\[0 = 1 - \hat{g}_{ii} (\gamma_i + \lambda)\]から,
\[\gamma_i = \hat{g}_{ii}^{-1} - \lambda\]ここで \(\hat{g}_{ii}\) は \((G + \lambda I)^{-1}\) の \((i,i)\) （対角）成分のこと.
この \(\gamma\) をさっきの \(B\) の式に代入すると, 制約付きでの解が求まって,
\[B = I - (G+\lambda I)^{-1} (\hat{g}_{ii}^{-1})\]この行列は確かに対角成分はゼロになっていて, 非対角成分は,
\[(B)_{ij} = \hat{g}_{ij} / \hat{g}_{jj}\]で決まる.
念のためにいうと \((\hat{g}_{ij})\) は行列 \((X^t X + \lambda I)^{-1}\) のこと.
頻出した \(G = X^t X\) はグラム行列と呼ばれる重要な行列. \(X\) が \({0,1}\) の行列なら, \(G_{ij}\) はアイテム同士が共起したかを表している. ポアソン分布を仮定すれば \(\sqrt{G_{ij}}\) がその分散になる. さて実は, \(G\) の成分和が大きくなるほど, \(B\) によってより精度良く推定することが可能になる. 成分和を大きくする要因は2つあって, 一つは \(X\) がより密な行列になること. もう一つは単に \(X\) のユーザー方向が大きくなること. すなわち, ユーザーがよりアクティブであってくれて, ユーザー数が多くなるにつれて, 精度が良くなる.
ユーザー方向に大きくあればいいので, これは \(B\) を大きくする必要はなく, 計算量的にはお得.
ベクトル \((x_k)_{k \in I}\) から \(x_i\) だけを除いたものを \(x_{-i}\) と書こう.
個のモデルは \(x_{-i}\) から \(x_i\) を推定する確率になってるのは間違い. ガウス分布だとしたら, 平均は
\[\mathbb E(x_i \mid x_{-i}) = x_{-i} B_{-i, i}\]で, 分散は \(1/\hat{g}_{ii}\) .
グラム行列を計算するのに \(U \times I\) 行列同士の掛け算として素直にやれば \(O(U \times I^2)\) .
アルゴリズムとしては計算済みの \(G\) が与えられて \(B\) を求める. これには逆行列を計算するところが一番大変で, これは \(O(I^3)\) . ここでユーザー数やインタラクション数に依存しないのが嬉しい. なぜなら精度を上げるにはここを増やす必要があるが, 計算量はこれとは独立だからだ.
じゃあグラム行列の計算が重たくなるわけだけどね.
ディープラーニング 協調レコメンダは長らく行列分解モデルによるものだったが, 最近になってディープラーニングモデルが台頭してきた. 特に AutoEncoder 系が協調レコメンダとして使える. それらと比較すると EASE はただ一層からなる浅い AutoEncoder と見ることが出来る.
SLIM など EASE は SLIM, 2011 が元になっていて, 定式化もほとんど同じ. 違いは SLIM は, 今回でいう \(B\) に相当する行列が非負である範囲で解いてるところ. そしてそっちでは解析的に解く方法を教えてくれなかったのが一番大きな違いだ. 逆に言えば SLIM は最適化に関して自由なので, logistic loss など使う余地があるが, EASE は一貫して L2 誤差だけ使ってるのでその点で不利になる可能性もある. 非負の制約を取り除いたことは精度の向上に貢献したと考えられている. また L1 正則化を失くしたことは得られる \(B\) が密になることにも貢献したと考えられる
近傍探索系 グラム行列 \(G\) はアイテム対アイテムの類似度行列と思えるし, これを使って近いアイテムを推薦しているとも見れる. 特にグラム行列 \(G\) 自体は共起行列なわけだが, これの逆行列が真の類似度であることを示唆している.
SLIM, WMF (Weighted Matrix Factorization), CDAE (Collaborative Denoising AutoEncoder), Mult-DAE, Mult-VAE と比較. はじめの2つが線形モデルで残りが AutoEncoder 系.
データセットは
| name | #users | #items | #interactions |
|---|---|---|---|
| Movie Lense (ML-20M) | 136,677 | 20,108 | 10M |
| Netflix Prize | 463,435 | 17,769 | 57M |
| Million Song Data (MSD) | 571,355 | 41,140 | 34M |
SLIM と比較して非負の制約を取り除いてある. そこで EASE においても非負にするとどうなるかが EASE \(\geq 0\) としてある. 結果として性能は落ちた. 落ちた結果, SLIM と同程度になったように見える.
Figure 2 は Netflix データセットで学習した \(B\) の各成分をヒストグラムにしたもの. 見ると \(0\) （より少し小さい値）をピークにして正負どちらにも広がった分布になってる. およそ 60% 程度が負の重みを持っていたそう. すなわちネガティブなインタラクション関係を学習できていると言っていいだろう.
パラメータ \(\lambda\) の値について. ML-20M データセットでは \(500\) 程度. Netflix データセットで \(1000\) 程度. MSD で \(200\) 程度. 行列が大きくなるに比例して \(\lambda\) もめちゃでかいことに注意.
実験環境. AWS で 64GB RAM/16 vCPU なインスタンス一つ借りて動かした. 一回の学習は Netflix なら2分程度, MSD が 20 分程度. パラメータサーチは \(\lambda\) 一個についてやるだけなので容易い.
Table 1. ML-20M では Mult-VAE が強いが, その他のデータセットでは EASE で十分勝ってる.
近傍系との比較. EASE が一番良いという結論. 詳細省略.