ALS 알고리즘

해당 Alternative Least Squares 알고리즘은 Collaborative Filtering for Implicit Feedback Datasets 논문을 기반으로 설명을 드리도록 하겠습니다.

 

ALS알고리즘은 MF(matrix factorization)을 통해 나온 user-latent matrix와 item-latent matrix를 번갈아가면서 학습시키는 것입니다. 두 행렬을 한꺼번에 최적화하는것은 어렵고 시간이 오래걸리기때문에 user-latent matrix를 update할때에는 item-latent matrix를 상수로 놓고 학습을 하고 반대로 item-latent matrix를 update할때에는 user-latent matrix를 상수로놓고 학습을 진행하는 것입니다.

 

---

• SVD(Singular Value Decomposition)

Loss Function

기존 특이값 분해의 Loss function이다. r_ui의 경우 기존의 user-item matrix의 특정 user u에 대한 특정 item i의 평점값이 된다. x_u는 user-latent matrix이고 y_i는 item-latent matrix이다. 둘 사이의 내적을 원본 행렬과 차이를 최소화 시키는 방향으로 SGD를 통해 update하는것이다. 자세한 내용은 저의 블로그 SGD를 이용한 matrix factorization을 참고해주세요! 뒤에는 regularization term을 이용해 과적합을 방지해주었다.

 

• ALS(Alternative Least Sqaures)

먼저 ALS에서는 0과 1의 값을 가지는 이진변수인 P_ui를 도입했다. P_ui는 user u가 item i를 선호하는것을 나타내는것이다. 이 값은 한 user가 해당 item에 대해서 소비한적이 존재한다면 1로 표시하고 한번도 소비한적이 없었다면 0으로 나타내는 것이다. 

 

그러나 paper에서는 이 값을 negative sample로 생각하지 않았다. 신뢰도 개념을 도입해서 낮은 신뢰도로 보았다. 왜냐하면 해당 item을 아예 인식조차 하지 못했거나 값이 비싸거나 이용에 제한이 생겨서 이용을 못할수도 있었다고 생각했기 때문이다.

신뢰도 같은 경우 기본 1의 값을 가지고 긍정적인 즉, 평점이 매겨져있는 item에 대해서는 a라는 값을 통해 조절해주면서 점차 증가하게 만들었다. 해당 논문에서는 실험결과 a는 40일때가 가장 성능이 좋았다고 적혀있다.

 

해당 논문에서 사용한 ALS 알고리즘은 결국 관찰된 아이템에 의해서만 Loss function에 영향을 주는 것이 아니라 관찰되지 않은 아이템에 대해서도 Loss function에 영향을 주게 만들었다. 결국 제안하는 Loss function은 아래와 같다.

 

x_u는 user-latent matrix이고 y_i는 item-latent matrix이다. 뒤에 regularization term도 과적합 방지를 위해서 넣어주었다. user-item matrix같은 경우는 sparse하기 때문에 m(유저의 수) x n(아이템의 수)를 곱하게 되면 숫자가 어마어마하게 커진다. 그러기 때문에 SGD같은 방식으로 값을 update하기에 적절한 기법이아니다. 

해당 논문에서는 둘중 하나를 상수로 고정시키게되면 2차함수로 변환되기 때문에 global minimum에 도달할 수 있다고 적혀있다. 

---

수식을 통해서 user-latent matrix를 update하는 과정을 하나하나씩 살펴보겠습니다!