[추천시스템] Alternative Least Square(ALS) algorithm Explanation

ALS input data 설명

기본적인 ALS 알고리즘에서 우리의 목적은, user by item 으로 표현된 매트릭스 형태의 데이터를 user by latent factors 인 $X$ 매트릭스, item by latent factors 인 $Y$ 매트릭스로 분해하는 것이다. 각 유저들이 각 아이템들에 대한 rating (영화 평점, 물품 선호도 등)을 입력한 매트릭스 $R$은 다음과 같은 형태를 갖는다. 이번 예시에서 우리는 $n$ 명의 user, $m$ 개의 item을 갖고 있다고 가정한다. 따라서, Rating matrix 는 아래와 같은 $m \times n$ 형태의 매트릭스이다.

$$ R = \begin{bmatrix} \mid & \mid & &\mid \\ R_1 & R_2 &\cdots & R_m \\ \mid & \mid & & \mid\end{bmatrix}, \ R \in \mathbb{R}^{m \times n} $$

column vector $R_1$ 은 모든 유저 $X$의 아이템 1에 대한 평점들을 의미한다. 이제 이 rating 매트릭스 $R$ 을 user by latent matrix $X$, item by latent matrix $Y$ 두 행렬로 분해할 것이다. $k$ 개의 latent factor로 분해시 $X$와 $Y$는 다음과 같은 행렬식으로 표현된다.

$$ X = \begin{bmatrix} \mid & \mid & &\mid \\ X_1 & X_2 &\cdots & X_n \\ \mid & \mid & & \mid\end{bmatrix}, \ R \in \mathbb{R}^{k \times n} $$ $$ Y = \begin{bmatrix} \mid & \mid & &\mid \\ Y_1 & Y_2 &\cdots & Y_m \\ \mid & \mid & & \mid\end{bmatrix}, \ R \in \mathbb{R}^{k \times m} $$

만약 우리가 latent factor의 수를 8개로 잡았다면, 1번 유저에 대한 vector는 다음과 같이 표현된다.

$$ X_1 = \begin{bmatrix} x_{11} \\ x_{21} \\ \vdots \\ x_{71} \\ x_{81} \end{bmatrix} $$

유저 1의 2번 아이템에 대한 예측 점수는 두 벡터 $X_1, Y_2$ 의 내적 ($X_1^T Y_2$ or $X_1Y_2^T$)으로 구한다. 즉, 유저 $u$ 의 아이템 $i$에 대한 예측 점수는 다음과 같이 표현한다.

$$ r_{ui} = X_u^T\cdot Y_i = X_u\cdot Y_i^T$$

위와 같이 특정 상품 $i$에 대한 유저 $u$의 선호도가 아니라, 모든 상품들에 대한 특정 유저 $u$의 선호도를 알고싶다면, 다음과 같이 전체 상품 행렬에 대해 내적을 진행하면 된다.

$$r_u = \sum_i X_u^T\cdot Y_i = X_u^T \cdot Y$$

거꾸로, 특정 상품 $i$에 대한 모든 유저들의 선호도 $r_i$는 다음과 같이 구한다.

$$ r_i^T = \sum_u X_u^T\cdot Y_i = Y_i^T \cdot X$$

$r_i$ 는 기본적으로 column 벡터인데, 위의 식에서 굳이 row 벡터 $r_i^T$로 표현한 것은, rating matrix $R$ 에서 이 벡터는 원래 각 열을 이루는 벡터이기 때문이다. 표현의 방식은 자유이지만, rating vector는 왠만하면 row vector 표현하는 것이 좋을 것 같아 이렇게 표현했다.

ALS loss function

위에서 우리는 각 행렬, 벡터들의 곱 및 표현 방식에 대해서 이해를 했다. 우리가 최종적으로 얻은 $X, Y$를 내적하게 되면 얻게되는 predicted rating 행렬을 $\hat{R}$로 표현하자. 우리의 목적은 actual rating matrix ($R$) 와 predicted matrix ($\hat{R}$) 간의 cell 값들의 차이를 최소화하는 latent matrix $X$, $Y$를 찾는 것이다.

$$\text{argmin}_{X,Y} ||R-\hat{R}||$$

위의 $||R-\hat{R}||$ 에 regularization term 을 추가해 미분 가능한 형태로 loss function $L$을 표현하면 다음과 같다.

$$L = \sum_{u,i} (r_{ui} - X_u^T\cdot Y_i)^2 + \lambda_u \|X_u\|^2 + \lambda_i\|Y_i\|^2 $$

Fixed Derivatives

ALS 의 핵심 개념은, $X_u$, $Y_i$를 한 번씩 고정(fix)해 놓고, 번갈아가며 미분을 진행하는 것이다. 이는 SGD(Stochastic Gradient Descent)와는 조금 다른 방식이며, 편미분을 활용해 조금 더 직관적으로 미분을 진행할 수 있다.
첫번째로 $Y_i$는 고정해놓은 채로, $X_u$에 대한 미분을 진행해보자.

$${\partial L \over \partial X_u} = -2 \sum_i (r_{ui} - X_u^T\cdot Y_i)\cdot Y_i^T + 2\lambda_u\cdot X_u^T $$ $$ = -2(r_u - X_u^T\cdot Y)\cdot Y^T + 2\lambda_u\cdot X_u^T \space \cdots \ (1)$$ $$\because \sum_i X_u^T\cdot Y_i = X_u^T\cdot Y \space\space and\space \space X_u^T\cdot Y = X_uY^T $$

위의 식은 최종적으로, 유저 $u$의 모든 아이템 (m개) 에 대한 rating을 벡터 형태로 표현한다. $ = [r_{u1}\ r_{u2} \cdots r_{um}]$ 또한 이 미분 값이 0이 되는 지점에서 해당 손실 함수는 최솟값을 가지므로, (1) 식이 0이 되는 지점을 찾도록 한다.

$$-2(r_u - X_u^T\cdot Y)\cdot Y^T + 2\lambda_u\cdot X_u^T = 0$$ $$ \longrightarrow \lambda_u\cdot X_u^T = (r_u - X_u^TY)\cdot Y^T$$ $$ \longrightarrow X_u^T(\lambda_u I + YY^T) = r_uY^T$$ $$\therefore X_u^T = r_uY^T(\lambda_uI + YY^T)^{-1}$$

이렇게 첫번째 partial derivative를 마무리했고, 이 편미분의 결과는 결국 $r_u$ 벡터, $Y$ 행렬의 곱으로 간단히 나타낼 수 있다는 걸 알았다. 두번 째 편미분을 진행하기 위해 loss function을 다시 정리한다.

$$ L = \sum_{u,i} (r_{ui} - X_u^T\cdot Y_i) + \lambda_u\|X_u\|^2 + \lambda_i\|Y_i\|^2$$ $$ = \sum_u (r_{ui} - X_u^T\cdot Y_i)^2 + \lambda_u\|X_u\|^2 + \lambda_i \|Y_i\|^2$$ $$ = (r_i - X^T\cdot Y_i)^2 + \lambda_u \|X_u\|^2 + \lambda_i \|Y_i\|^2$$

여기서 $\sum_{u}r_{ui} = r_i,\space \sum_uX_u^T\cdot Y_i = X^T\cdot Y_i$ 임을 이해하고 넘어가자. 이제 미분을 진행한다.

$$ {\partial L \over \partial Y_i} = -2(r_i - X^T\cdot Y_i)\cdot X^T + 2\lambda_i Y_i^T \cdots \ (2)$$

위의 (2)식을 0으로 만들고, 첫번째 항에는 $Y_i$, 두번째 항에는 $Y_i^T$가 있는 것이 매우 ‘불편’하다. 동일하게 바꿔주도록 하자.

$$\lambda_iY_i^T = (r_i - X^TY_i)X^T$$ $$ = (r_i^T - Y_i^TX)X^T,\space \because X^TY_i = Y_i^TX$$ $$\lambda_iY_i^T = r_i^TX^T - Y_i^TXX^T$$ $$Y_i^T(\lambda_i I + XX^T) = r_i^TX^T$$ $$\therefore Y_i^T = r_i^TX^T(\lambda_i I + XX^T)^{-1}$$

이상으로, 두번째 편미분을 마쳤다. 첫번째 미분 결과와 두번째 미분결과를 비교해보면 상당히 비슷한 형태임을 알 수 있다. (편-안)

정리

ALS 알고리즘은 두개 중 하나의 행렬은 고정하고 한 행렬에 대한 미분을 교차적으로 진행해가며 손실함수를 최소화하는 두 행렬을 찾는다. 각 편미분 결과, 두 손실함수를 최소화하는 각 행렬 $X_u^T$와 $Y_i^T$는 아래와 같으며, 단순 행렬들의 곱에 지나지 않는다.

$$X_u^T = r_uY^T(\lambda_uI + YY^T)^{-1}$$ $$Y_i^T = r_i^TX^T(\lambda_i I + XX^T)^{-1}$$

위의 미분 결과를 활용하여 $X, Y$를 업데이트하는 알고리즘의 pseudo-code는 다음과 같다. numpy, random 정도만 import하여 간단히 구현할 수 있다.

def ALS_pseudo(R,lambda):
X = random(k, n)
Y = random(k, m)

for u in (1,2,...,n)
  update X_u using r_u, lambda_u, Y
for i in (1,2,...,m)
  update Y_i using r_i, lambda_i, X

until convergence

PREVIOUS [머신러닝] Inequality betwen RMSE and MAE