[CS246] RecSys (4) - Latent Factor Models (Matrix Factorization, MF, UV decomposition)

이번 포스팅은 2006년에 넷플릭스 대회를 통해 실제 추천시스템 대회에서 utility matrix의 형태와 평가기준(evaluation criterion)에 대해 살펴본다.

그리고 넷플릭스 utitlity matrix를 채우는 방법으로 UV decomposition을 소개하고, 이를 이용한 모델을 설명한다.

 

※ Matrix Factorization (MF)은 종종 UV decomposition 등으로 불린다.

※ MF로 얻는 두 행렬은 Google에서는 U와 V, wiki에서는 H와 W로 표기한다. 여기서는 CS246의 표기(P와 Q)를 따른다.

The Netflix Prize

Training data

100M개의 ratings (1-5의 평점을 가짐)

user 수: 480K

movie 수: 18K

Test data

각 user별 약간의 최신 평점들, 전체 2.8M

evaluation: root mean square error(RMSE)

기존 넷플릭스 시스템의 RMSE: 0.9514 

\[ RMSE = \sqrt{ \cfrac{1}{|R|} \sum_{(i, x) \in R} (\hat{r}_{xi} - r_{xi})^2 } \]

$r_{xi}$는 user $x$가 item(movie) $i$에 준 true rating이다.

 

기존 넷플릭스 시스템보다 10%이상 향상하면 $1M의 상금이 주어진다.

 

Competition Structure

The Netflix Utility Matrix $R$ (Stanford CS246)

참고로 test dataset이 저렇게 되는 이유는 다음과 같다.

• 예를 들어, 앞의 100명의 유저의 모든 movie를 추출한 $R[1:100, :]$을 test dataset라고 하자. 그러면 이 100명의 user는 training  dataset에서는 없었으므로 new user로 간주되고, cold-start 문제가 발생한다.
• 예를 들어, 앞의 50개의 movie의 모든 user를 추출한 $R[:, 1:50]$을 test dataset이라 하자. 그러면 training dataset에서 이 50개의 movie는 없었으므로 new movie로 간주되고, cold-start 문제가 발생한다.

여기서 기존 data mining과 competition의 차이가 있다.

data mining은 가지고 있는 데이터에서 패턴을 찾는 것이 목표다. 그러나 competition에서는 관찰하지 않은 데이터(unseed data)에 대해서도 일반화(generalizing)에 성공해야한다. 이 경우 scaling이나 running time보다는 performance(높은 accuracy, 낮은 RMSE 등)이 더 목표가 되는 경우가 많다. 대부분의 machinen learning은 이 문제를 해결하기위해 발전해왔다.

 

Latent Factor Models

Objective function: 다음을 만족하는 두 행렬 $P$와 $Q$를 찾는다.

\[ \underset{P, Q}{\min} \sum_{(i, x) \in R} (r_{xi} - q_i \cdot p_x)^2 \]

Latent Factor Models (Stanford CS246)

Matrix Factorizatioin as Latent Factor Model (developers.google)

Goal: test dataset에서 SSE 값을 최소화 (혹은 RMSE값을 최소화)

Idea: training dataset에서 SSE (혹은 RMSE) 값을 최소화한다.

latent factor의 개수를 $k$라 할 때, $k$의 값이 클 수록 잘 포착할 것이라 기대할 수 있다.

 

utility matrix $R$을 $P$와 $Q$로 분해하는 방법은 나중에 설명하고, 우선 잘 분해하여 $P$와 $Q$를 얻었다고 가정하자.

Regularization

$k$가 커지면 그만큼 학습하는 파라미터도 커지게 되어 overfitting 위험이 커진다. 이를 방지하기 위해 정규화를 진행한다.

$p$와 $q$에 각각 적용하는 정규화 상수를 $\lambda_1$, $\lambda_2$라 하면 objective function은 다음과 같다.

\[ J(P, Q) = \underset{P,Q}{\min} \sum_{D_{\text{train}}}(r_{xi} - q_i p_x)^2 + \lambda_1 \sum_x \|p_x\|^2 + \lambda_2 \sum_i \|q_i\|^2 \]

$P$ and $Q$ with $k$ latent factors (Stanford CS246)

Gradient Descent (GD): Find $P$ and $Q$

missing rating을 $0$으로 간주하고, SVD를 통해 $P$와 $Q$의 초기값을 구한다. ($U$와 $V$라 부르는 이유)

위에서 설정한 objective function $J(P, Q)$에 대하여 gradient descent를 이용하여 $P$와 $Q$를 업데이트한다.

• $P \leftarrow P - \eta \cdot \nabla_P J$
• $Q \leftarrow Q - \eta \cdot \nabla_Q J$
• $\eta$는 hyperparameter이며, step size 또는 learning rate로 불린다.

$P$와 $Q$는 행렬이기 때문에, 각 update step마다 모든 entry에 독립적으로 적용한다.

$Q$의 $i$번째 row, $c$번째 column이라 할 때

\[ q_{ic} \leftarrow q_{ic} - \eta \nabla_{q_{ic}}J \]

이때 $\nabla_{q_{ic}}J(P, Q) = \sum_{x:(x,i) \in train} - 2(r_{xi} - q_ip_x)p_{xc} + 2 \lambda_2 q_{ic}$ 이다.

 

Observation: Gradient descent 계산은 너무 느리다!

 

Stochastic Gradient Descent (SGD): faster convergence

Gradient 역시 다음과 같이 분해(decompose)가 가능하다.

\begin{align} \nabla_{q_{ic}}J(P, Q) &= \sum_{x:(x,i) \in train} - 2(r_{xi} - q_ip_x)p_{xc} + 2 \lambda_2 q_{ic} \\ &= \sum_{x:(x, i) \in train} \nabla Q(r_{xi}) \end{align}

모든 rating에 대하여 gradient를 구하지 않고, 대신에 하나의 rating에 대하여 gradient descent를 적용한다.

• GD: $Q \leftarrow Q -\eta [\sum_{r_{xi}} \nabla Q(r_{xi})]$
• SGD: $Q \leftarrow Q -\eta \nabla Q(r_{xi})$

GD vs. SGD (Stanford CS246)

GD는 훨씬 적은 step으로도 수렴할 수 있지만, 각 step마다 소요되는 시간이 너무 길다.

SGD는 GD에 비해 다소 noisy하게 값이 나아지고 더 많은 step이 필요하지만 각 step별 소요되는 시간은 적다.

 

SGD를 이용하여 $R=PQ$로 분해하는 방법은 다음과 같다.

SVD를 이용하여 $P$와 $Q$의 초기값을 구한다.
for each $r_{xi}$:
    (Compute gradient, do a step)
    $\epsilon_{xi} = 2(r_{xi} - p_x^\top q_i)$ (derivative of the error)
    $q_i \leftarrow q_i + \eta_1(\epsilon_{xi}p_x - 2\lambda_2 q_i)$
    $p_x \leftarrow p_x + \eta_2 (\epsilon_{xi}q_i - 2\lambda_1 p_x)$

Including Biases

우리는 유저 $x$가 영화 $i$에 어떤 태도(attitude)를 지니고 있는지 몰라도, $x$가 $i$에 대한 rating의 기댓값을 구할 수 있다. 

 

이러한 요소들을 다 고려하여 rating을 예측해보면 다음과 같다.

\[ \hat{r}_{xi} = \mu + b_x + b_i + p_x^\top q_i \]

이때 $\mu$는 전체 rating의 평균이고, $b_x$는 user x의 bias, $b_i$는 movie(item) $i$의 bias이다.

Putting it all together (Stanford CS246)

 

따라서 새로운 objective function(regularization 역시 적용)은 다음과 같다.

\begin{align} J(P, Q, B_{\text{user}}, B_{\text{item}}) &= \underset{P, Q, B_{\text{user}}, B_{\text{item}}}{\min} \sum_{(x, i) \in R} (r_{xi} - (\mu + b_x + b_i + p_x^\top q_i))^2 \\ &+ \lambda_1 \sum_i \|q_i\|^2 + \lambda_2 \sum_x \|p_x\|^2 \\ &+ \lambda_3 \sum_x \|b_x\|^2 + \lambda_4 \sum_i \|b_i\|^2  \end{align}

 

예를 들어, 평균 rating이 3.7이면 $\mu=+3.7$, user $x$가 critical reviewer라면 $b_x=-1$, 영화 스타워즈는 전체 영화 평점 평균보다 0.5가 높다면 $b_i = +0.5$이라 하자. 그러면 final score는 $3.7-1+0.5+p_x^\top q_i=3.2 + p_x^\top q_i$이다. ($p_x$와 $q_i$는 위에서 언급한 matrix factorization으로 구한다.)

 

Netflix 대회에서, 이렇게 bias를 추가한 모델을 fitting하면 RMSE=0.89를 얻는다고 한다.