SLIM

prior research

• k-NN Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., & Riedl, J. (1994). GroupLens: An Open Architecture for Collaborative Filtering of Netnews. CSCW 1994.
  • 최근접 이웃 기반 협업 필터링(k-Nearest Neighborhood based Collaborative Filtering)은 유사도 기반 휴리스틱 함수(Heuristic Function)를 통해 예측을 수행하므로 계산 효율성은 높지만, 해당 함수가 데이터로부터 학습되어 적합된 함수가 아니기 때문에 개인화 추천 정확도가 낮음
• MF Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factorization techniques for recommender systems. Computer, 42(8), 30-37.
  • 잠재요인 모형(Latent Factor Model)은 사용자와 아이템의 관계를 데이터로부터 학습하여 적합된 함수(표현 학습, 매칭 함수 학습)를 통해 예측을 수행하므로 개인화 추천 정확도는 높지만, 계산 비용이 발생하여 실시간 추천에는 비효율적임

idea

• SLIM(Sparse LInear Methods): 아이템 간 유사도를 선형 회귀계수 행렬로 학습하고 이를 기반으로 예측을 수행하는 선형 회귀 모형(아이템 기반 협업 필터링 모형)

notation

• $u=1,2,\cdots,M$: user idx
• $i=1,2,\cdots,N$: item idx
• $\mathbf{Y} \in \mathbb{R}^{M \times N}$: user-item interaction matrix
• $\mathbf{W} \in \mathbb{R}^{N \times N}$: sparse aggregation coefficient matrix
• $\hat{y}_{u,i}$: interaction probability of user $u$ and item $i$

function

• linear regression:

  \[\begin{aligned} \hat{y}_{u,i} &= \mathbf{W}_{i} \cdot \mathbf{Y}_{u*}\\ &= \sum_{j}{w_{i,j} \cdot y_{u,j}},\quad j \in \mathcal{R}_{u}^{+} \setminus \{i\} \end{aligned}\]

• objective function:

  \[\begin{gathered} \hat{\mathbf{W}} = \text{arg} \min{\frac{1}{2} \Vert \mathbf{Y} - \mathbf{Y}\mathbf{W}\Vert_{F}^{2} + \frac{\beta}{2} \Vert \mathbf{W} \Vert_{F}^{2} + \lambda \Vert \mathbf{W} \Vert_{1}}\\ \\ \text{subject to} \quad \begin{aligned} \mathbf{W} &\ge 0\\ \text{diag}(\mathbf{W})&=0 \end{aligned} \end{gathered}\]
  • \(\Vert \mathbf{Y} - \mathbf{Y}\mathbf{W}\Vert_{F}^{2}\): reconstruction loss
  • \(\Vert \mathbf{W} \Vert_{F}^{2}\): l2 norm regulation to prevent overfitting
  • \(\Vert \mathbf{W} \Vert_{1}\): l1 Norm regulation to induce sparsity