SGD vs ALS in MF

Matrix Factorization

User-Item Matrix를 User Latent Vector와 Item Latent Vector로 분해한 뒤 내적을 통해 결측치를 메꾸는 방법을 Matrix Factorization이라고 합니다.

이 때 User-Item Matrix를 복원하는 과정에는 여러 가지 방법이 있는데 크게 SGD와 ALS 방법론이 존재합니다.

SGD(Stochastic Gradient Descent)

Loss를 줄여나가는 방식으로 사용되는 방식으로 머신러닝, 딥러닝에서 사용되는 대표적인 방법론입니다.

$\mathcal{L}(U,V) = \sum_{u,i}(R_{u,i} - v_uv_i^T)^2$

최적화를 위해 다음과 같은 미분 가능한 함수에서 최솟값을 찾습니다.

ALS(Alternating Least Squares)

SGD 방법에서 시간이 오래 걸리는 단점을 극복하기 위해 도입된 방법입니다.

$\mathcal{L}(U,V)$를 줄이기 위해 기울기를 구하면 다음과 같습니다.

${\partial \over \partial v_u}\mathcal{L}(U,V) = 2\sum(R_{u,i} - v_uv_i^T)(-v_i)$

항상 최솟값을 갖는 2차 함수이기 때문에 미분값이 0이 되는 지점에서의 $U,V$가 최적의 값입니다. 여기서 ALS는 변수 하나를 고정시켜 빠르게 해를 구할 수 있다는 아이디어에서 출발했습니다.

$V$를 고정시킨 뒤 편미분을 통해 ${\partial \over \partial v_u}\mathcal{L}(U,V) = 0$을 만족하는 $v_u$를 찾으면 됩니다.

$2\sum({R_{u,i}} - v_uv_i^T)(-v_i)$

→ $v_u(\sum v_i^Tv_i = \sum R_{u,i}v_i)$

→ $v_u = (\sum R_{u,i}v_i)(\sum v_i^Tv_i)^{-1}$

→ $(\sum v_i^Tv_i)v_u = (\sum R_{u,i} v_i)$

$Ax = b$ 꼴의 Linear Equation Problem

또한 $v_{u1}$과 $v_{u2}$를 업데이트할 때 서로 겹치지 않으므로 병렬 처리 또한 쉽다는 사실을 알 수 있습니다.

마찬가지로 $v_i$ 또한 $v_u$와 같은 방식으로 구할 수 있습니다.

$2(-v_u^T)\sum({R_{u,i}} - v_uv_i^T)$

→ $(\sum v_u^Tv_u = \sum v_u^TR_{u,i})v_i^T$

→ $v_i^T = (\sum v_u^T R_{u,i})(\sum v_u^Tv_u)^{-1}$

→ $v_i = (\sum v_u^Tv_u)^{-1}(\sum v_uR_{u,i})$

$(\sum v_u^Tv_u)v_i = (\sum v_uR_{u,i} )$

Spark MLlib에 Matrix Factorization 라이브러리가 존재하는데 이 때 ALS 방식을 활용하고 있습니다.