먼저 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이 살짝 다르다.
\[ \min_{x,y} \sum_{u,i} c_{ui}(p_{ui} - x^T_uy_i)^2 + \lambda ( \sum_u ||x_u||^2 + \sum_i ||y_i||^2) \]
\[ p_{ui} = \begin{cases} 1 \ \text{if} \ r_{ui} > 0 \\ 0 \ \text{if} \ r_{ui} = 0 \end{cases} \]
\[ 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^T_u 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^T_i x_u) \times y_i + \lambda x_u = \sum_i c_{ui} \times p_{ui} \times y_i \]
\[ \sum_i c_{ui} \times y^T_i \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^T_i \times y_i + \lambda \text{I})x_u = \sum_i c_{ui}(p_{ui}) \times y_i \]
$y \in \mathbb{R}^f$이라고 하면 행렬 연산을 통해 산출되는 값은 스칼라 값을 가지게 된다. 이와 같이 $x^T_u y_i$역시 스칼라 값을 가지기에 $y_i x^T_u$로 전치해주어도 동일한 결과값을 도출한다. 추가적으로 논문에서 $\hat{r}_{ui} = x^T_u y_i$라고 명시했기에 스칼라 값을 가지는 것을 알 수 있다.
- $ y \in \mathbb{R}^f $
- $ x \in \mathbb{R}^f $
- $ C^u_{ii} = c_{ui} $
- $ p(u) \in \mathbb{R}^n $
여기서 우리는 $\Sigma$를 행렬 연산으로 변형하게되면 간단하게 계산할 수 있다. 예를 들어 $\Sigma (y-\hat{y})^2 = (y-\hat{y})(y-\hat{y})^T$ 인 것과 같은 방식으로 간단하게 표현할 수 있다. 본 논문에서는 각 변수의 차원을 위와 같이 표현하였으며, 이 변수들의 차원을 기반으로 수식을 행렬로 변환하면 다음과 같다.
\[ (Y^TC^uY + \lambda \text{I})x_u = Y^TC^u p(u) \]
우리가 궁금한 것은 $x_u$ 사용자 행렬에 대한 것이기에 $x_u$에 대한 식으로 변형해보자.
\[ x_u = (Y^TC^u Y + \lambda \text{I})^{-1} Y^TC^u p(u)\]
지금까지 사용자 행렬에 대한 편미분에 대해서 계산해보았다. 사용자 행렬 뿐만 아니라 아이템 행렬에 대해서도 동일하게 적용이 가능하며 수식은 다음과 같다.
\[ y_i = (X^TC^i X + \lambda \text{I})^{-1} X^TC^i p(i)\]
이 과정을 반복해 최적의 $X, Y$를 찾아내는 방식으로 접근하는데, 이 과정을 10번에서 15번 정도 반복하는 형태로 진행하여 최적의 $X, Y$를 찾아낸다. 10회 혹은 15회가 정해진 수치가 아니라 데이터의 Sparse 정도에 따라 hyper parameter로 설정하여 분석을 수행하면 보다 좋은 결과를 도출할 수 있을 것이다.
ALS 구현은 여기를 참고!