이전 포스팅에서 time complexity을 개선한 행렬 분해에 대해서 알아보았다.
https://steady-programming.tistory.com/57
[Recommender System / Paper review] #19 Fast Matrix Factorization for Online Recommendation with Implicit Feedback
논문 링크(967회 인용) Summary 기존의 방법과는 다르게, 본 논문에서 제안하고자 하는 mf는 implicit feedback을 이용하되 관측되지 않은 feedback은 서로 다른 weight을 준다. 이는 item popularity을 반영한 weigh
steady-programming.tistory.com
이 논문은 implicit feedback을 사용하여 행렬 분해를 할 때, 넷플릭스 대회에서 1등을 차지한 방법 (이 포스팅 참조)을 기본으로 하여 elementwise하게 파라미터를 업데이트하여 시간 복잡도를 개선하는 것이 핵심 내용이다.
논문 중간에 기본이 되는 implicit feedback CF의 파라미터에 대한 업데이트 식이 살짝 유도되고 결과만 나온다. 본 포스팅은 중간에 내용이 일부 빠지고 결과가 나오는 것이 아쉬워서 식을 직접 유도하여 어떻게 업데이트 식이 나오는지에 대한 내용이다.
누군가는 굳이? 이렇게까지 식을 유도해야하나.. 라고 생각할 수 있다. 만약에 여러 패키지에 있는 als을 가져다 쓰기만 할 것이라면 이렇게까지 유도할 필요는 없다고 생각된다. 그러나 논문의 내용이 어떻게 코드로 바뀌는지 궁금하거나 여러 변형된 als을 구현하고 싶다면, 기본 골자가 되는, koren이 제시한 implicit feedback CF의 파라미터 업데이트 식은 유도해볼만한 가치가 있다고 생각된다. 이제 본격적으로 유도를 해보자.
MF method for implicit feedback
- $\mathbf{R} \in \mathbb{R}^{M \times N}$
- M명의 유저, N개의 아이템
- $\mathcal{R}$: non-zero인 (유저,아이템) pair
- $\mathbf{p}_u, \mathbf{q}_i$: 유저 u, 아이템 i에 대한 latent vector
- $\mathcal{R}_u$: 유저 u와 interaction이 있는 아이템들의 집합
- $\mathcal{R}_i$: 아이템 i와 interaction이 있는 유저들의 집합
mf는 $\mathbf{R}$의 $r_{ui}$을 유저와 아이템간의 내적, 유저/아이템의 bias term으로 예측하고자 한다.
모델 파라미터를 학습하기 위해 아래의 loss을 최소화한다.
- implicit feedback을 활용하기 때문에 모든 데이터 (summation이 M,N에 대해서 있음)에 대한 term이 있다.
- $w_{ui}$: 유저, 아이템별로 다르게 부여되는 weight이다. 보통 interactions의 횟수에 대한 function으로 정의되는데 confidence라고 불린다.
- $\mathbf{p}_u = [ \mathbf{p}^B_u, b_u, 1 ]$
- $\mathbf{q}_i = [ \mathbf{q}^B_i, 1, b_i ]$
- $\hat{r}_{ui} = \mathbf{p}^T_u \mathbf{q}_i$로 다시 쓸 수 있다.
Optimization by ALS
두 종류의 모델 파라미터, $\mathbf{p}_u, \mathbf{q}_i$가 있다. 이를 동시에 푸는게 아니라, 하나를 고정해두고 다른 하나에 대한 최적화를 번갈아가면서 진행하는 것이 ALS의 핵심 아이디어이다. 먼저, $\mathbf{p}_u$에 대한 최적화를 진행하기 위해 아래와 같이 $\mathbf{p}_u$와 관련된 항만 남겨둔다.
논문에서는 식이 위와 같이 되어있는데, 사실 이는 틀린 형태이고 아래의 형태가 맞다. (엄청 오래 쳐다봐서 알게된 사실 ㅠ)
업데이트 식을 쉽게 유도하기 위해서 위와 같이 벡터&행렬 형태로 나타낸다. 어떻게 위와 같은 형태가 나왔는지는, 아래와 같이 유도하면 된다.
잘 보면, weighted ridge regression 형태이다. 즉, $|| \mathbf{W} ( \mathbf{y} - \mathbf{X \beta} ) ||^2 + \lambda || \mathbf{\beta} ||^2$로 바꿔서 생각해보면 이에 대한 해를 아래와 같이 유도하면 된다.
$\mathbf{p}_u$의 업데이트 식을 살펴보았다. $\mathbf{q}_i$에 대한 업데이트도 동일하게 유도하면 된다.
Conclusion
- implicit feedback CF는 결국 weighted ridge regression의 해와 동일함을 보였다.
- 식은 복잡해보였는데.. 하나하나 까보니까 결국 비슷하게 유도되는 듯한 느낌이 들었다.
- 중요한 것은.. 가장 기본적인 als는 이렇게 closed form으로 유도가 되는데, 변형된 als는 꼼짝없이 gradient descent을 해야한다는 것이다.
- 결국 computation이 문제인데.. 이걸 감수할만큼의 성능 향상이 있을지 확인해봐야할 것 같다는 생각이 들었다. (모델 정확도 vs 빠른 연산)
댓글