CF의 MF 기법은 Gradient descent update를 이용하여 user와 item 의 latent vector를 찾아내는데, 이러한 최적화 과정은 너무 느리고 많은 반복이 필요하다.
동시에 user와 item의 latent vector를 찾아가는 MF 기법과 달리, ALS (Alternative Least Square)는 user 와 item의 latent factor를 한번씩 번갈아 가면서 학습시킨다. 즉, ALS는 둘 중 하나의 latent factor를 상수로 놓고, 다른 하나를 학습시키는 알고리즘이다.
ALS의 cost function은 다음과 같다.
$$ \min {x{\star}, y_{\star}} \sum_{u, i} c_{u i}\left(p_{u i}-x_{u}^{T} y_{i}\right)^{2}+\lambda\left(\sum_{u}\left\|x_{u}\right\|^{2}+\sum_{i}\left\|y_{i}\right\|^{2}\right) $$
$x_{u} \in \mathbb{R}^{f}$ 는 각 사용자 $u$ 에 대한 latent vector, 그리고 $y_{i} \in \mathbb{R}^{f}$ 는 각 아이템 $i$에 대한 latent vector를 의미한다.
$p_{u i}$ 는 binary variables로, 사용자 $u$가 아이템 $i$에 대한 선호 지표를 나타낸다. 즉, $u$ 가 $i$ 를 이용한 경우 ($r_{ui} > 0$), $u$ 는 $i$ 를 선호한 것으로 판단한다 ($p_{ui} = 1$). 반대로, 한 번도 $i$ 를 이용한적 없다면 ($r_{ui}=0$), $u$ 는 $i$ 를 선호하지 않은 것으로 판단한다 ($p_{ui} = 0$)
$$ p_{u i}=\left\{\begin{array}{ll}1 & r_{u i}>0 \\0 & r_{u i}=0\end{array}\right. $$
ALS 는 $p_{u i}$ 의 문제점을 보완하기 위해 $c_{u i}$ 를 cost function에 사용한다. 이 값은 $p_{u i}$ 에 대한 신뢰도 지수(confidence level)을 나타내는 것으로, 사용자가 아이템을 선호한다는 확신이 있을수록 높은 값을 나타낸다.
$$ c_{u i}=1+\alpha r_{u i} $$
이제 cost function에 대한 설명을 마쳤으니, 이 cost function을 최적화 하는 방법에 대해 알아보자. MF에서는 cost function을 최적화하기 위해서 SGD 를 사용했다. 하지만, implicit feedback datasets은 사용자 $m$ 명, 아이템 $n$ 개 에 대한 계산을 필요로 하므로, 매우 느리다.
하지만 위 cost function에서 사용자 또는 아이템에 대한 latent vector를 상수로 고정시킨다면, cost function은 quadratic이 되므로 global minimum을 찾기가 상대적으로 쉬워진다. 그래서 한쪽을 고정시키고 다른 한쪽을 최적화 한다음, 다시 반대로 최적화를 반복하면서 cost function의 값을 낮춘다.
이러한 방식을 alternating least squares 방식으로 논문에서는 말하는데, ALS 은 explicit feedback datasets 에서도 사용되었던 방식이다. 그러나, explicit 에서는 평가되지 않은 데이터를 missing 데이터로 처리하므로, sparse matrix의 문제가 있다.
1️⃣ 첫번째로, cost function을 최적화하는 사용자 $u$ 의 latent vector $x_u$ 를 찾는 것부터 시작한다. 하지만 그 전에, 미리 계산해놓고 정의해놓을 것들이 몇개 있다.