- 논문 링크(11329회 인용)
Summary
- 넷플릭스에서 주최한 대회에서 neighborhood 기반 모델보다 matrix factorization 기반 모델의 결과가 월등히 좋았다.
- 본 논문에서는 기본적인 matrix factorization부터, bias을 더한 형태, 추가적인 input을 더한 형태, temporal effect을 더한 형태, implicit feedback을 더한 형태까지 단계적으로 각 모형을 살펴본다.
Motivation
- neighborhood 기반 모델에 비해 matrix factorization 기반 모델이 좋은 이유는 아래와 같다.
- 다양한 형태의 모델을 가정할 수 있다. cost function에 목적에 맞는 항을 추가함으로써 결과를 향상시킬 수 있다.
- 또한 파라미터에 대한 학습도 효과적으로 할 수 있다.
Approach
Notation
- $q_i \in \mathbf{R}^f$: 아이템 i와 관련된 벡터
- $p_u \in \mathbf{R}^f$: 유저 u와 관련된 벡터
- $\hat{r}_{ui} = q_i^T p_u$: 아이템 i와 유저 u간의 interaction
A basic matrix factorization model
SVD는 matrix factorization을 사용하여 유저와 아이템에 대한 latent feature을 찾는 대표적인 방법이다. 그런데 추천 시스템에서 분해하고자 하는 행렬은 유저x아이템 행렬로, 대부분의 행렬값이 결측치인, 매우 sparse한 행렬이다. SVD는 이런 결측치가 포함된 행렬에 적용할 수 없다.
대안으로 유저x아이템 행렬에서 관측된 값에 대해서만 SVD을 진행하는 방법이 있으나, 이는 overfitting의 위험성이 있다. 또는 결측치를 임의로 채워두고 SVD을 하는 방법이 있으나, 이는 부정확한 결과를 가져온다는 연구 결과가 있다. 이러한 이유로, 관측된 값에 대해서 SVD을 적용하되 latent vector에 대해 penalty을 부여하여 overfitting을 막는 방법이 일반적으로 사용된다. cost function은 아래와 같다.
\[ \min_{q*, p*} \sum_{(i,j) \in \mathcal{K}} (r_{ui} - q_i^T p_u)^2 + \lambda (|| q_i ||^2 + || p_u ||^2) \]
여기서 $\lambda$는 regularization parameter인데, cross-validation을 통해서 정하거나 확률론적으로 정할 수도 있다.
Learning algorithm
Stochastic gradient descent
위 cost function에서 $q_i, p_u$에 대해 편미분을 해보면 아래의 gradient update descent 식을 얻을 수 있다.
- $e_{ui} = r_{ui} - q^T_i p_u$로 정의하자.
- $q_i \leftarrow q_i + \gamma (e_{ui} \cdot p_u - \lambda \cdot q_i)$
- $p_u \leftarrow p_u + \gamma (e_{ui} \cdot q_i - \lambda \cdot p_u)$
Alternating least squares
SGD는 데이터의 수가 많다면 시간이 오래 걸린다. 대안으로, ALS가 있다. 위 cost function은 하나의 파라미터를 고정시키면, quadratic function이 된다. 예를 들어서 $p_u$ 파라미터를 고정한다면, $q_i$에 대한 quadratic function이 되어 closed form으로 해를 구할 수 있다. 이렇게 번갈아가면서 각 파라미터에 대한 optimization을 진행한다.
Adding biases
평점 값에서 관찰된 대부분의 variation은 유저와 아이템간의 interaction에 의해서라기보다, biase 또는 intercept로 알려진 유저나 아이템 그 자체와 연관된 효과 때문인 경우가 많다. 예를 들어, 어떤 유저는 다른 유저에 비해 높은 평점을 매기는 경향이 있고 그에 따라서 어떤 아이템은 다른 아이템에 비해 더 좋은 평점을 받는다. 이는 유저와 아이템간의 interaction보다는, 그 유저 자체의 특성 때문에 발생한 결과라고 볼 수 있다.
이러한 이유로 $r_{ui}$을 유저 bias, 아이템 bias, 그리고 이를 제외한 순수한 interaction으로 모델링하는 것이 좀 더 나은 방법이다.
\[ \hat{r}_{ui} = b_{ui} + q^T_i p_u = \mu + b_i + b_u + q^T_i p_u\]
cost function은 아래와 같이 정의한다.
\[ \min_{q*, p*, b*} \sum_{(i,j) \in \mathcal{K}} (r_{ui} - \mu - b_i - b_u - q^T_i p_u)^2 + \lambda (|| q_i ||^2 + || p_u ||^2 + b^2_u + b^2_i) \]
Additional input sources
추천 시스템은 매우 적은 평점을 매긴 유저들에게 추천을 해야할 때 cold start 문제를 해결해야 한다. 이를 해결하기 위해서는 유저의 정보를 더 통합하는 방법이 있다.
먼저 유저의 implicit feedback을 모형에 통합하는 방법에 대해 생각해보자. $N(u)$을 유저 u가 boolean implicit feedback(유저의 행동을 0과 1의 boolean으로 표현한 것을 의미하는 듯)을 표현한 아이템 집합으로, $x_i \in \mathbf{R}^f$을 아이템 i와 관련된 새로운 아이템 벡터로 정의하자. $N(u)$에 implicit feedback을 표현한 유저는 $\sum_{i \in N(u)} x_i$로 표현할 수 있다.
또 다른 방법으로, 유저의 인구학적 특성을 boolean으로 바꿔서 유저를 표현하는 벡터에 추가할 수 있다. $A(u)$을 유저의 성별, 연령대, 사는 곳 등을 표현한 집합이라고 하자. 유저와 관련된 특징은 $\sum_{a \in A(u)} y_a$로 표현할 수 있다. 이 두 벡터를 유저 벡터과 결합하여 아래의 prediction rule을 정의한다.
\[ \hat{r}_{ui} = \mu + b_i + b_u + q^T_i (p_u + |N(u)|^{-0.5} \sum_{i \in N(u)} x_i + \sum_{a \in A(u)} y_a) \]
Temporal dynamics
아이템간의 관계나 유저의 취향은 시간에 따라 변한다고 가정하는 것이 합리적이다. 이렇게 시간에 따라 변화하는 데이터를 가정하는 prediction rule은 아래와 같다.
\[ \hat{r}_{ui}(t) = \mu + b_i(t) + b_u(t) + q_i^T p_u(t) \]
Inputs with varying confidence levels
어떤 상황에서는 모든 관측된 값들이 동일한 weight 또는 confidence을 가질 필요는 없다. 몇몇 noisy한 평점이 끼어 있을 수 있기 때문이다. 이런 배경 때문에 평점이 얼마나 valuable한지, 그 confidence scores을 추정된 preference에 포함하는 방법이 제안되었다.
\[ \min_{q*, p*, b*} \sum_{(i,j) \in \mathcal{K}} c_{ui}(r_{ui} - \mu - b_i - b_u - q^T_i p_u)^2 + \lambda (|| q_i ||^2 + || p_u ||^2 + b^2_u + b^2_i) \]
좀더 자세한 내용은 이전 포스팅을 참조하자.
Results
- 본 논문은 matrix factorization 방법에 대해 소개하는 논문으로, 따로 진행한 실험은 없다.
Conclusion
- matrix factorization이라는 큰 틀 아래, 여러 정보를 통합시켜 이전 모델의 단점을 보완하는 과정이 인상적이었다.
- 다만, 아직도 confidence level을 모형에 포함시키는 정확한 이유와 과정이 100% 이해가 가질 않는다. 해당 부분은 구현 부분을 보며 차차 이해해야할 듯 싶다.
댓글