- 논문 링크(967회 인용)
Summary
- 기존의 방법과는 다르게, 본 논문에서 제안하고자 하는 mf는 implicit feedback을 이용하되 관측되지 않은 feedback은 서로 다른 weight을 준다. 이는 item popularity을 반영한 weight이다.
- 또한 기존의 시간 복잡도 측면에서 기존의 ALS 방법을 개선하여, online recommendation이 가능하도록 eALS을 제안한다. 기존 방법에 비해 K배만큼의 복잡도가 개선됨을 보인다.
- online recommendation을 목표로 하기 때문에, 실시간으로 유저와 아이템간의 interaction 데이터가 들어왔을 때 어떤 식으로 업데이트할지에 대한 방법을 제시한다.
Motivation
- implicit feedback을 이용한 mf는 보통 유저x아이템 행렬의 모든 값을 사용하되, 결측치에 동일한 weight을 부여한다.
- 하지만 이런 모델 가정은 현실과는 조금 맞지 않는다. 왜냐하면, 관측되지 않은 interaction이 모두 동일한 가중치를 가지고 있지 않기 때문이다. 그 중 어느 아이템은 인기가 굉장히 많은데 유저에 의해 발견되지 않았을 뿐이고, 다른 아이템은 인기가 없어서 사람들이 피하는 것일 수도 있다.
- 이런 현실적인 가정을 반영하기 위해, 본 논문에서는 implicit feedback을 이용한 mf를 할 때, 결측치에 서로 다른 weight을 가정한다. 이때 item-popularity을 사용한다.
- 또한, implicit feedback을 사용하면, 모든 데이터를 학습에 활용한다. 매우 많은 연산량을 요구하는 SGD을 대체하여 ALS가 제안되었지만, 여전히 시간이 오래 걸린다. 이를 해결하기 위해 기존의 mf에 비해 K배 빠른 eALS을 제안한다.
Approach
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라고 불린다.
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{q}_i에 대한 식도 동일하게 유도하면 된다.
ALS는 $K \times K$ 행렬의 역행렬을 구해야하므로 $O(K^3)$의 시간이 필요하다. 또한 $\mathbf{Q}^T \mathbf{W}^u$의 행렬은 $K \times N$과 $K \times K$의 행렬곱이므로 $O(NK^2)$의 시간이 필요하다. 종합하면 한 유저에 대한 파라미터를 업데이트하는데 발생하는 시간 복잡도는 $O(K^3 + NK^2)$이다. M명의 유저에 대해서는 $O(M(K^3 + NK^2))$, N명의 유저에 대해서는 $O(N(K^3 + MK^2))$이므로 이를 합하면 $O((M+N)K^3 + MNK^2)$이다. 데이터의 크기가 크다면, 분명한 burden이 될 것이다.
Speed-up with uniform weighting
높은 시간 복잡도를 줄이기 위해 결측치에 대해 동일한 가중치인 $w_0$을 두는 것이 제안됐다. 이를 사용하면 아래와 같이 식을 간단히 할 수 있다.
- $w_0 \mathbf{Q}^T \mathbf{Q}$: u에 의존하지 않으므로 미리 계산할 수 있다.
- $\mathbf{W}^u - \mathbf{W}^0$: $N \times N$이지만 $|\mathcal{R}_u|$개만큼 non-zero entries을 가지므로 실질적으로 계산에 사용되는 항의 갯수는 $|\mathcal{R}_u|$개이다. 여기서 주목해야할 점은 $N >> |\mathcal{R}_u|$이라는 점이다.
- $\mathbf{Q} \in N \times K$이므로 $\mathbf{Q}^T (\mathbf{W}^u - \mathbf{W}^0) \mathbf{Q}$에서는 $O(K^2N)$가 아니라 $O(K^2|\mathcal{R}_u|)$의 시간 복잡도를 가진다. $N >> |\mathcal{R}_u|$이기 때문이다.
- M명의 유저와 N개의 아이템에 대한 iteration을 모두 돌면 시간 복잡도는 $O((M+N)K^3 + |\mathcal{R}| K^2)$ 이다.
- 이는 여전히 큰 데이터에 ALS을 적용하기는 어려운 시간 복잡도이다. 또한, 동일한 가중치를 준다는 것 자체가 현실과 동떨어진 가정이다.
Generic element-wise ALS learner
ALS의 solution은 bottleneck이 여러개 있었는데 그 중 하나는 inverse matrix을 계산하는 것이었다. 이는 파라미터를 벡터 단위로 업데이트하기 때문에 발생하는 것이기 때문에 본 논문에서는 파라미터를 element-wise 단위로 업데이트 해본다. $p_{uf}$에 대한 derivative을 아래와 같이 유도해보자.
$\hat{r}^f_{ui} = \hat{r}_{ui} - p_{uf} q_{if}$이다. 이제 이를 0으로 두고 closed solution을 구해보자.
$q_{if}$도 비슷하게 구하면 된다.
시간 복잡도를 계산해보자. 한번 iteration 돌 때마다 raw implementation은 $O(MNK^2)$의 복잡도를 가진다. 그 이유는 아래와 같다.
- $\hat{r}^f_{ui} = \hat{r}_{ui} - p_{uf} q_{if}$이고 $\hat{r}_{ui} = b_u + b_i + \sum_f p_{uf}q_{if}$이다. 따라서 여기서 발생하는 시간 복잡도는 $O(K)$이다. 만약에 $\hat{r}_{ui}$을 미리 계산할 수 있다면 시간 복잡도를 $O(1)$로 줄일 수 있다.
- 분자는 N개의 항을 더하기 때문에 시간 복잡도는 $O(N)$이고 분모도 마찬가지이다.
- 따라서 $p_{uf}$ 하나를 계산하는데 걸리는 시간 복잡도는 최선으로 $O(N)$이다.
- 잘 생각해보면, $p_{uf}$는 총 K개의 factor가 있고 M명의 유저가 있다. 따라서 전체 element-wise latent factor을 계산하는데 걸리는 시간 복잡도는 $O(MNK)$이다.
- $q_{if}$에 대한 시간 복잡도도 동일하게 $O(MNK)$로 나오므로, 전체 시간 복잡도는 $O(MNK)$이다.
- matrix inversion을 하지 않기 때문에 시간이 상당히 줄었고, $\hat{r}_{ui}$을 미리 계산하여 시간을 더 줄일 수 있다.
Propsed implicit method: Item oriented weighting on missing data
논문에서는 implicit feedback의 결측값에 동일한 가중치를 주는 것이 비현실적인 가정이라고 지적하며 아래의 objective function을 제안한다.
- 가중치 $w_{ui}$는 관측된 implicit feedback $\mathcal{R}$에 대해서만 부여한다.
- 유저별로 결측치인 데이터 ($i \notin \mathcal{R}_u$)에 대해서는 item-oriented 가중치 $c_i$을 부여한다.
- 두번째 term인 $\sum_u \sum_{i \notin \mathcal{R}_u} c_i \hat{r}^2_{ui}$가 implicit feedback을 모델링하는데 필수적으로 해결해야하는 항이다.
Populairty-aware weighting strategy
아이템이 유저에 의해 선택되지 않았지만, 그 아이템이 인기가 있다면 추후에 유저에 의해 선택될 가능성이 높다. 이 아이디어를 반영한 가중치는 아래와 같다.
- $f_i$: 아이템 i의 인기도, popularity로써 $|\mathcal{R}_i| / \sum_{j=1}^N \mathcal{R}_j$로 계산한다.
- $c_0$: 결측치의 전체적인 가중치이다.
- $\alpha$: 인기있는 아이템과 인기 없는 아이템간의 정도를 조절하는 파라미터이다.
Fast eALS learning algorithm
eALS을 통한 $p_{uf}$는 아래와 같이 업데이트 된다.
여기서 bottleneck은 $\sum_{i \notin \mathcal{R}_u}$ 관련 부분인데, negative samples을 모두 돌아야하기 때문이다. 먼저 분자부분을 살펴보자.
- notation을 주의하자. $\mathbf{p}_u = [ \mathbf{p}^B_u, b_u, 1 ]^T$이고 $\mathbf{q}_i = [ \mathbf{q}^B_i, 1, b_i ]^T$이다. 따라서 $p_{uk}$에는 bias term이 모두 포함되어 있다.
- 이렇게 식을 전개해보면 bottleneck이 되는 부분은 $\sum^N_{i=1} c_i q_{if} q_{ik}$임을 알 수 있다.
- 본 논문에서는 이를 $\mathbf{S}^q = \sum^N_{i=1} c_i \mathbf{q}_i \mathbf{q}^T_i$로 memoization하여 computation을 줄이고자 한다.
이는 $O(K + |\mathcal{R}_u|)$의 시간 복잡도로 계산된다. 비슷하게, 분모도 cahe를 아래와 같이 적용한다.
이를 종합하면, $p_{uf}$에 대한 update는 아래와 같이 진행할 수 있으며 time complexity는 $O(K + |\mathcal{R}_u|)$로, 기존 implicit feedback 방법인 $O(MNK)$보다 대폭 향상됨을 알 수 있다.
Analysis of time complexity
- ALS vs eALS: eALS가 K배만큼 더 빠르다
- ii-SVD vs eALS: eALS가 더 빠르다
- RCD vs eALS: time complexity는 동일하지만 RCD는 learning rate을 튜닝해야한다.
- BPR vs eALS: BPR의 시간 복잡도가 더 낮지만 BPR은 positive feedback만 사용하고 결측치는 사용하지 않는다는 단점이 있다.
Results
Offline protocol
- Figure 1
- 두 데이터 세트에서 최적의 $c_0, \alpha$를 찾기 위한 실험이다.
- $\alpha$는 공통적으로 0.4 부근이 최적점으로 판단됐고 $c_0$는 서로 달랐다
- Figure 2
- eALS vs RCD vs ALS 실험 결과이다.
- iteration에 상관없이 eALS가 지속적으로 더 높은 성능을 보임을 알 수 있다.
- factors의 수에 따른 평가지표의 변화에 대한 실험이다.
- factors의 수가 많아질수록 일반화가 잘 되어서 성능이 좋아짐을 확인할 수 있다.
- analytical하게 계산했을 때, eALS와 RCD의 시간 복잡도는 유사했고 ALS의 시간 복잡도가 K배만큼 더 큼을 보였다.
- 행렬 곱셈이 구현된 라이브러리가 시간 복잡도를 최적화하여 K배만큼은 아니지만, factors의 수가 늘어날수록 ALS는 학습하는데 시간이 매우 많이 걸림을 알 수 있다.
- 이는 데이터 수가 많은 상황에서 일반화가 중요한데, 일반화를 모델이 잘 하기 위해서는 K를 과적합하지 않는 방향에서 늘려야 한다. 이런 세팅에서 K가 클 때 학습이 오래 걸린다는 점은 치명적일 수 있으므로, eALS가 가지는 장점을 다시 한번 확인할 수 있다.
Online protocol
- online iteration 횟수에 따른 성능 비교 실험이다.
- 적은 횟수의 iteration만으로도 빠르게 성능이 수렴함을 확인할 수 있다.
- 테스트 데이터 수에 따른 online 학습 성능 비교 실험이다.
- eALS가 테스트 수가 적든 많든 다른 모델에 비해 좋은 성능을 보임을 알 수 있다.
Conclusion
- MF에 대해 찐하게 배울 수 있었던 논문이었다. 특히나 이 논문은 16년도에 나온 논문인데, MF에 feature을 넣는 것은 많이 연구된 것 같고, 빠르게 학습하는 알고리즘에 대한 니즈가 있었던 것 같다.
- 이를 위해, time complexity을 분석하는 것이 필수적인데, eALS는 기존의 ALS보다 무려 K배나 빠른 알고리즘이다.
- 데이터 수가 많아진다면 K를 키우는 것이 일반화에 유리하고, 따라서 K배만큼 알고리즘이 빠르다는 것은 대용량 데이터를 일반화하는 모형을 학습할 때에 좋을 것 같다는 생각이 들었다.
- MF를 계속 공부하다보니, 시간 복잡도에 따른 영향도가 실제로 어떻게 느껴질지 실험을 해보고 싶다는 생각이 들기도 했다.
댓글