[Recommender System / Paper review] #06 Factorization meets the neighborhood: a multifaceted collaborative filtering model

• 논문링크(4056회 인용)

Summary

• 추천시스템 분야에서 CF는 크게 neighborhood-based models과 latent factor models로 나뉜다.
  • neighborhood models은 local preference을, latent factor models는 global preference을 잘 잡아낸다.
• 본 논문은 이 두 모형을 합침으로써 두 모형의 장점을 취하고자 한다.
• 또한, netflix에서 제공하는 사용자의 explicit feedback뿐만 아니라 사용자가 프로덕트를 사용하면서 남긴 implicit feedback도 모형에 반영함으로써 성능도 높이고 좀 더 현실적인 상황에서 유저의 취향을 모델링 할 수 있는 방법을 제안한다.
• 최종적으로 neighborhood models과 latent factor models에서 implicit feedback을 반영하도록 모델을 수정하여 최종 integrated models을 제안한다.

Motivation

• neighrborhood models의 장/단점
  • localized relationships을 잡아내는데 효과적이다. $r_{ij}$을 예측하고자할 때, 모든 아이템을 사용하는 것이 아니라 $j$ 아이템과 연관있는 $k$개의 아이템에 대한 ratings을 사용하기 때문이다.
  • 이는 모든 유저의 점수에 포함되어 있는 신호를 잡아내지 못한다.
• latent factor models의 장/단점
  • 대부분, 또는 모든 아이템과 연관된 전체적인 구조를 estimate하는데 효과적이다.
  • 하지만 적은 수의 연관된 아이템 사이의 관계성을 파악하는데는 좋은 성능을 내지 못한다.
• neighborhood models과 latent factor models을 합쳐서 둘의 장점을 모두 갖춘 모형을 개발하는 것이 목적이다.

Approach

notation

• user $u,v$
• item $i,j$
• $u$ 유저의 $i$번째 아이템에 대한 rating:  $r_{ui}$
• predicted ratings: $\hat{r}_{ui}$
• $r_{ui}$가 알려진 $(u,i)$의 세트를 $\mathcal{K} = \{ (u,i) | r_{ui} \text{ is known} \}$
• $\lambda_1, \lambda_2, \cdots$: regularization을 조절하는 상수

Baseline estimates

• $\mu$: overall average rating
• unknown rating $r_{ui}$에 대한 baseline estimate을 $b_{ui}$라고 하자.
• $b_u$: 유저 $u$의 baseline estimate
• $b_i$: 아이템 $i$의 baseline estimate

$b_u,b_i$의 추정치는 아래의 sum of squared distances을 최소화하여 구한다.

Neighborhood models

여기서는 아이템간의 유사도를 아래의 shrunk correlation coefficient로 계산한다.

이를 사용하여 unknown $r_{ui}$에 대한 prediction을 아래와 같의 정의하자.

• $n_{ij}$: 아이템 $i,j$를 모두 평가한 유저의 수
• $S^{k}(i;u)$: 유저 $u$에 의해 rating된 아이템 중  아이템 $i$와 가장 가까운 $k$개의 아이템
• $\hat{r}_{ui}$는 baseline estimate인 $b_{ui}$가 조정된 채로 $s_{ij}$을 weighted average하여 구한다.

위의 similarity measure은 두 아이템간의 관계를 반영하지, 전체 아이템의 관계를 반영하기 힘들다는 단점이 있다. 이런 점 때문에 interpolation weights인 $\{ \theta^u_{ij} | j \in S^k(i;u) \}$을 따로 정의하여 아래와 같이 prediction rule을 변경한다.

Latent factor models

• $p_u \in \mathbf{R}^f$: 유저 u에 대한 user-factor vector
• $q_i \in \mathbf{R}^f$: 아이템 i에 대한 item-factor vector

prediction rule은 아래와 같다.

\[ \hat{r}_{ui} = b_{ui} + p^T_u q_i \]

SVD을 cf에 바로 적용하면, 유저x아이템 행렬에 빈 값이 많기 때문에 여러 어려운 점이 있다. 이에 대한 대안으로 관측된 값에 대해서만 SVD을 하거나 빈 값을 채워서 SVD을 진행하는 방법이 있다. 그러나 이 둘은 과적합되거나 prediction 값이 정확하지 못하다. 이러한 이유로 아래와 같이 regularization term도 같이 넣어서 gradient descent을 진행한다.

여기서는 유저를 explicit하게 $p_u$ 벡터로 모델링하는데, paterek이 제안한 NSVD 방법은 유저 벡터를 그들이 소비한 아이템 벡터로 표현하는 것을 제안한다. 즉, $p_u$ 대신에 $\sum_{j \in R(u)} x_j / \sqrt{|R(u)|}$로 대체하는 것이며 본 논문에서도 이 방법을 사용한다.

Implicit feedback

넷플릭스에서 제공한 데이터는 유저 u가 아이템 i에 대해 어떤 평점을 내렸는지 환산된 점수가 제시된다. 이를 explicit feedback이라고 한다. 하지만 현실에서는 이렇게 평점을 주는 일이 많지 않다. 대신, 유저가 특정 컨텐츠에 들어갔는지, 들어갔다면 얼마나 많은 시간을 체류했는지, 관련된 다른 컨텐츠를 소비했는지 등의 데이터는 존재한다. 이를 implicit feedback이라고 한다. 본 논문에서는 넷플릭스 데이터에서 유저 u가 아이템 i에 대해 평점을 내렸으면 1, 그렇지 않다면 0으로 행렬을 재구성하여 implicit feedback을 도출하여 모델링에 사용한다.

A neighborhood model

이전의 neighborhood model은 user-specific weights을 가정했기 때문에 이를 대체하여 specific user에 독립적인 global weights을 제안하고자 한다.

• $w_{ij}$: weights가 아니라 baseline estimates로부터 offset을 의미한다. 데이터로부터 학습될 파라미터
• $r_{uj} - b_{ui}$: offset에 곱해지는 계수
• 만약에 유저 u가 j에 대해 높게 평가한다면, $r_{uj} - b_{ui}$가 높아질 것이고 baseline estimate인 $b_{ui}$에 더해지는 값도 커질 것이다.
• 만약에 baseline만큼 유저 u가 j에 대해 평가했다면, $r_{uj} - b_{ui}$는 0에 가까워질 것이고 baseline에서 크게 벗어나지 않을 것이다.
• implicit feedback을 $c_{ij}$을 통해 반영한다. 유저 u의 아이템 j에 대한 implicit preference은 $c_{ij}$만큼 $r_{ui}$에 대한 예측값을 변화시킬 것이다.
• $w_{ij}$을 global offsets으로 사용하는 것은 missing rates의 중요성을 강조하는 역할을 한다.

위 모형을 자세히 보면, $R(u), N(u)$의 원소가 많을 수록 예측 값이 커지는 것을 확인할 수 있다. 즉, 활발하게 평점을 주거나 기록을 남긴 유저에 대해서는 좀 더 도전적인 추천을 해준다고 해석할 수 있다. 반대로 평점을 덜 매기는 소극적인 유저에게는 평균적인 유저에게 가까운 추천을 해줄 것이다. 이는 추천 시스템에서 알맞은 형태이긴한데, 위와 같이 prediction rule을 정했을 때 그 차이가 더 커지는 것을 확인하여, 아래와 같이 normalize하여 prediction rule을 재구성한다.

위 식에서 summation part을 아이템 j와 가장 유사한 k개의 아이템만 뽑아서 합하여 계산 시간을 줄일 수 있다. 

• $R^k(i;u) = R(u) \cap S^k(i)$
• $N^k(i;u) = N(u) \cap S^k(i)$

최종 optimizaiton 식은 아래와 같다.

• 이전 neighborhood model에서 부족했던 global optimization이 통합된 모습이다.

이에 대한 gradient descent update 식은 아래와 같다.

Latent factor models revisited

SVD와 같은 lower rank decomposition 방법은 유저벡터 $p_u \in \mathbf{R}^f$와 아이템 벡터 $q_i \in \mathbf{R}^f$을 사용하여 아래의 prediction rule을 정의한다.

본 논문에서는 여기에 implicit information을 고려한 모델을 제안한다.

여기서 유저를 explicit parameterization가 아닌, 그들이 선호하는 아이템을 사용하여 가정한 것이 하나의 특징이다. 이 모델을 asymmetric-SVD라고 하자. 이 모델의 장점은 아래와 같다.

• fewer parameters: 유저의 수가 아이템 수보다 훨씬 많기 때문에, 유저 수만큼 파라미터를 설정하지 않음으로써 모델의 complexity을 줄인다.
• new users: 유저별로 별도의 벡터를 생성하는 것이 아니기 때문에 새로운 유저가 유입되어도 그들의 취향에 기반한 유저 벡터를 생성할 수 있다.
• explainability: 유저들에게 상품을 추천할 때, 그 근거를 설명해줄 수 있다.
• efficient integration of implicit feedback: $x_j, y_j$에 따라서 explicit & implicit feedback을 통합할 수 있다.

objective function은 아래와 같다.

asymmetric-SVD과는 다르게 SVD++은 아래와 같이 implicit feedback을 통합한다.

asymmetric-SVD은 SVD++에 비해 정확도는 떨어지지만 유저의 수만큼 파라미터가 필요하지 않으므로 모델의 complexity가 훨씬 줄어든다. 반면에, SVD++은 여전히 유저수만큼 파라미터($p_u$)를 가정하지만 정확도에서만큼은 asymmetric-SVD보다 우위에 있다.

An integrated model

논문에서 제안한, 약간 변형된 neighborhood model과 SVD++ 모델을 합친 것이 이 논문에서 최종적으로 제안하는, integrated model이다.

위 모델은 3티어의 추천을 제공한다.

• $\mu + b_u + b_i$: 유저와 아이템간의 일반적인 특징을 모델링한다.이때 유저와 아이템간의 상호관계는 제외한다.
• $q_i^T (p_u + |N(u)|^{-1/2} \sum_{j \in N(u)} y_j)$: 유저벡터와 아이템벡터간의 내적으로, 이 둘의 상호관계를 모델링한다.
• neighborhood tier: 유저가 관련된 다른 아이템에 평가한 정보를 반영한다.

아래의 gradient descent update을 통해서 파라미터를 업데이트한다.

Results

Evaluation method

기본적으로 논문에서 제안한 integrated model은 넷플릭스 데이터 세트에 대해 가장 낮은 RMSE인 0.8870의 성능을 보였다. 그러나 이 논문은 단순히 RMSE가 낮은 것이 좋은 품질의 추천인가? 라는 질문을 던진다. 이에 대한 대답을 찾아가는 과정으로, 논문에서는 아래의 평가 방법을 소개한다.

• top K 추천에 대한 평가 방법을 제안한다.
• 유저 u에 의해 5점 만점으로 평가된 아이템 i를 뽑는다.
• 랜덤으로 이외 1000개의 아이템을 뽑는다.
• 1001개의 아이템에 대한 유저 u의 predicted values을 도출한다.
• 5점 만점으로 평가된 아이템의 predicted values가 가장 상위에 있으면 best case, 가장 나중에 있으면 worst case이다.

• rank가 0%일 때 cumulative distribution 비교
  • integrated method: 0.067
  • integrated method가 전체 1000개의 아이템 중 5점 만점을 받은 아이템을 가장 상위에 둘 확률이 0.067이라는 뜻이다.
  • 이는 correlation based neighborhood method에 비해 2.8배 나은 수치
  • weighted based neighborhood와 SVD는 0.043정도
• rank가 0.2%이하일 때 cumulative distribution 비교
  • integrated method: 0.157
  • weighted based neighborhood와 SVD: 0.107, 0.115
  • correlation based neighborhood: 0.065
• integrated method가 RMSE도 가장 낮고, top k 추천 품질 비교에서도 가장 좋은 성능을 보였다.

Conclusion

• 본 논문은 cf의 두 축인 neighborhood model과 latent factor model을 적절히 섞은 integrated model을 제안하였다.
• 그냥 섞은 것이 아니라, 두 방법에 implicit feedback을 결합하여 더 좋은 성능을 냈다.
• 인상적인 것은, 단순히 RMSE만을 비교하는 것이 아니라 top k 추천 품질까지 비교했다는 것이었다.