[2021] Revisiting the Performance of iALS on Item Recommendation Benchmarks

[2021] Revisiting the Performance of iALS on Item Recommendation Benchmarks

Steffen Rendle, Walid Krichene, Li Zhang, Yehuda Koren

 

본문의 논문은 ACM RecSys paper로, 링크를 확인해 주세요.

 

 

 Abtract

 

 google에서 낸 논문으로, 추천 시스템의 트릭을 발견하여 조금 더 잘 적용해보았다고 한다.

 기존의 SOTA모델과 경쟁이 될 정도로 성능이 좋은 편은 아니지만, 기존의 것을 사용한 update된 논문 정도로 생각하면 좋을 듯하다.

 

 

 

 

 Introduction

 

 iALS (implicit Alternating Least Square)는 implicit 피드백을 통해 top-n 아이템 추천을 목적으로 하는 MF모델을 학습하는 알고리즘이다. 다른 대표적인 추천 모델들은 대부분 이전에 본 영화, 또는 이전에 산 물품 등과 같은 과거의 행적을 보고 추천해 주는데, iALS는 과거 10년의 기록을 가져와 사용하는 흔한 방법을 사용한다. 이는 단순하고 연산 효율성이 있지만, 예측 퀄리티가 아주 좋은 편은 아니다. 이전의  reproducibility에 중점을 맞춘 iALS의 낮은 성능에 비해, 본 논문은 같은 벤치마크에서 같은 평가방법을 활용하여 높은 질의 결과를 만들어내었다는 결과를 보여준다. 

 

 

 

 

 Implicit Alternating Least Squares (iALS)

 

Model and Loss

 

•   scoring function

$\hat{y}(u,i):=<{\mathbf{w}}_u,{\mathbf{h}}_i>,W\in {\mathbb{R}}^{U\times d},H\in {\mathbb{R}}^{I\times d}$

  

 - ${\mathbf{w}}_u\in {\mathbb{R}}^d$ 는 d차원의 user embedding 벡터

 - ${\mathbf{h}}_i\in {\mathbb{R}}^d$ 는 d차원의 item embedding 벡터

 

 

• iALS loss $L(W,H)$

 

 - $L_s$ : $S\subseteq U\times I$ 관측치 쌍에 대해 정의되어 있고, 관측 label (여기서는 1) 과 예측 score가 얼마나 다른 지에 대한 값이다.

 - $L_I$ : 위와 반대로 0과 얼마나 다른 지에 대한 값

 - $R(W,H)$ : L2 regularization

 

 

Training Algorithm

 

 alternating minimization을 하여 user embedding $W$와 item embedding $H$를 최적화하는 것이 목적이다. iALS는 $H$를 수정할 때, $W$를 최적화하거나, 그 반대를 수행하는, alternate하는 것이다. 다시 말해, $H$가 수정될 때, 해당 user의 선형 회귀 문제를 해결하는 것과 동일하다고 보는 것이다. 이 알고리즘의 핵심은 implicit loss $L_I$에서 충분한 연산이 모든 user들과 공유되는 점이다. iALS의 연산 복잡도는 $\mathcal{O}(d^2|S|+d^3(|U|+|I|))$로 user와 item 의 수에 따라 결정된다.

 runtime의 복잡도를 줄이기 위해 좌표의 다양성을 줄이는 것을 사용했는데 ($\mathcal{O}(d|S|+d^2(|U|+|I|))$), 이론적 복잡도를 줄일 때는, 현 하드웨어가 벡터 연산을 최적화하고, scalar treatment가 지워지게 한다.

 

 

Frequency-based Regularization Scaling

 

 SGD를 통해 업데이트되며, 다음과 같이 최적화된다.

 

 

 또한 기존 ALS 정규화에서 $\nu$를 이용하여 frequency-based reg.를 수정하였다.

 

 

 $\nu$=0이면 기존 ALS 정규화와 같고, 1이면 SGD의 frequency-based 가중치가 적용된다.

 최종적으로 다음과 같은 iALS 가중치 정규화가 되는 것이다.

 

 

 

 

 

 Hyperparameter

 

 

 

 

 

 Data & Evaluation

 

 

Benchmarks

 

 

Results1

 

Result2