Collaborative Filtering for Implicit Feedback Datasets (ICDM'08)

먼저 Alternative Least Squares(ALS)를 이해하기 위해서는 Matrix Factorization(MF)에 대해 어느정도 알고 있어야 가능하다. ALS는 MF와 같이 하나의 모델이 아니라 최적화하는 알고리즘 중 하나다. 우리의 목표는 Latent Factor Matrix를 찾는 것이며, 이를 위해 Loss Function 혹은 Cost Function이라는 하나의 '지표'를 선정한 후 최적화하는 방식으로 접근한다. 이때 최적화를 하는 방법은 Gradient Descent(GD), ALS 등 다양한 알고리즘이 존재하지만 여기에서는 ALS에 대해서만 다룰 것이다. 

 

ALS를 제시한 논문에 따르면 분산처리 환경에서 GD보다 더욱 효과적이고, sparse matrix에 robust하면서, Implicit feedback Datasets에 특화된 알고리즘이라고 한다. ALS는 두 행렬을 한꺼번에 최적화시키는 것은 어렵기 때문에 둘 중 하나의 행렬을 상수로 설정한 후 나머지 하나의 행렬을 학습하고 번갈아가며 학습하는 형태이다. user matrix $X$와 item matrix $Y$를 번갈아가며 학습시키는 방식이기 때문에 분산처리 환경에서 속도가 빠르다. 이처럼 행렬을 하나씩 고정하면서 진행하는 방식이기에 기존의 MF와는 Loss function이 살짝 다르다. 

 

$$\underset{x,y}{min}\sum _{u,i}{c}_{ui}(p_{ui}-x_u^T{y}_i{)}^2+\lambda (\sum _u||x_u|{|}^2+\sum _i||y_i|{|}^2)$$

$$p_{ui}=\{\begin{array}{l}1\text{if}{r}_{ui}>0\\ 0\text{if}{r}_{ui}=0\end{array}$$

$$c_{ui}=1+\alpha r_{ui}$$

기존의 Explicit Data의 loss function에서는 $r_{ui}$를 통해 값을 계산하였다. 그러나 ALS의 loss function에서는 $c_{ui},p_{ui}$를 사용한다. 먼저 $p_{ui}$에 대해서 알아보자. $p_{ui}$는 선호를 나타내며 Implicit Dataset의 경우 선호와 비선호에 대해 알 수 없기에 평점 데이터가 존재할 경우에는 1, 존재하지 않을 경우에는 0으로 표기한다. $c_{ui}$는 confidence를 의미하며 본 논문에서는 confidence라는 변수를 도입해 confidence가 낮은, 0으로 표기된 데이터에 대한 예측 값도 고려한다는 것이다. $c_{ui}$는 control 변수인 $\alpha$를 가지고 있는데, 본 연구에서는 $\alpha =40$일 때 가장 좋은 결과를 도출한다고 언급한다.  

 

우리가 실제로 접하는 데이터는 대부분의 경우 sparse matrix이며, sparse matrix라는 것은 matrix 대부분의 값이 0이라는 것을 의미한다. ALS의 loss function은 변수가 두 개 존재하기에 각각의 편미분에 대해서 계산한 후 두 값을 통해 loss function을 최적화 한다. 먼저 사용자 행렬를 기준으로 설정한 후 loss function을 미분해보자. 

 

$$\frac{\partial \text{L}(x_u)}{\partial x_u}=-2\sum _i{c}_{ui}\times (p_{ui}-x_u^T{y}_i)\times y_i+2\lambda x_u$$

$$-2\sum _i{c}_{ui}\times (p_{ui}-x_u^T{y}_i)\times y_i+2\lambda x_u=0$$

$$-2\sum _i{c}_{ui}\times p_{ui}\times y_i+2\sum _i{c}_{ui}\times (x_u^T{y}_i)\times y_i+2\lambda x_u=0$$

$$\sum _i{c}_{ui}\times (x_u^T{y}_i)\times y_i+\lambda x_u=\sum _i{c}_{ui}\times p_{ui}\times y_i$$

$$\sum _i{c}_{ui}\times (y_i^T{x}_u)\times y_i+\lambda x_u=\sum _i{c}_{ui}\times p_{ui}\times y_i$$

$$\sum _i{c}_{ui}\times y_i^T\times y_i\times x_u+\lambda x_u=\sum _i{c}_{ui}\times p_{ui}\times y_i$$

$$\sum _i(c_{ui}\times y_i^T\times y_i+\lambda \text{I})x_u=\sum _i{c}_{ui}(p_{ui})\times y_i$$ 

 

$y\in {\mathbb{R}}^f$이라고 하면 행렬 연산을 통해 산출되는 값은 스칼라 값을 가지게 된다. 이와 같이 $x_u^T{y}_i$역시 스칼라 값을 가지기에 $y_i{x}_u^T$로 전치해주어도 동일한 결과값을 도출한다. 추가적으로 논문에서 ${\hat{r}}_{ui}=x_u^T{y}_i$라고 명시했기에 스칼라 값을 가지는 것을 알 수 있다. 

 

- $y\in {\mathbb{R}}^f$

- $x\in {\mathbb{R}}^f$ 

- $C_{ii}^u=c_{ui}$

- $p(u)\in {\mathbb{R}}^n$ 

 

여기서 우리는 $\mathrm{\Sigma }$를 행렬 연산으로 변형하게되면 간단하게 계산할 수 있다. 예를 들어 $\mathrm{\Sigma }(y-\hat{y}{)}^2=(y-\hat{y})(y-\hat{y}{)}^T$ 인 것과 같은 방식으로 간단하게 표현할 수 있다. 본 논문에서는 각 변수의 차원을 위와 같이 표현하였으며, 이 변수들의 차원을 기반으로 수식을 행렬로 변환하면 다음과 같다. 

$$(Y^T{C}^{u}Y+\lambda \text{I})x_u=Y^T{C}^{u}p(u)$$

우리가 궁금한 것은 $x_u$ 사용자 행렬에 대한 것이기에 $x_u$에 대한 식으로 변형해보자. 

$$x_u=(Y^T{C}^{u}Y+\lambda \text{I}{)}^{-1}{Y}^T{C}^{u}p(u)$$ 

지금까지 사용자 행렬에 대한 편미분에 대해서 계산해보았다. 사용자 행렬 뿐만 아니라 아이템 행렬에 대해서도 동일하게 적용이 가능하며 수식은 다음과 같다. 

$$y_i=(X^T{C}^{i}X+\lambda \text{I}{)}^{-1}{X}^T{C}^{i}p(i)$$

이 과정을 반복해 최적의 $X,Y$를 찾아내는 방식으로 접근하는데, 이 과정을 10번에서 15번 정도 반복하는 형태로 진행하여 최적의 $X,Y$를 찾아낸다. 10회 혹은 15회가 정해진 수치가 아니라 데이터의 Sparse 정도에 따라 hyper parameter로 설정하여 분석을 수행하면 보다 좋은 결과를 도출할 수 있을 것이다. 

 

ALS 구현은 여기를 참고!