[논문 리뷰] Neural Collaborative Filtering

Recommender System

본 논문은 2017년에 International World Wide Web Conference(IWWWC)에 실린 논문이다. 해당 논문은 Collaborative Filtering에 기반한 대표적인 방법중 하나인 Matrix Factorization(MF)의 한계를 지적한다. 이번 포스팅에서는 MF의 문제점과, Neural Collaborative Filtering이 어떻게 이런 문제를 해결하고 있는지 살펴보겠다.

Abstract

Matrix Factorization(MF)은 추천시스템에서 널리 사용되는 방법이다. 이는 user와 item의 상호작용을 학습하는 한 방법으로, user-item 공간의 latent feature들의 inner product를 통해 두 관계를 표현하게 된다. 본 논문은 user와 item간의 관계를 학습함에 있어 기존의 liner 방식에 기반한 MF의 한계를 지적한다. 이에 대해 Neural Net 기반의 architecture인 Neural Collaborative Filtering(NCF)를 제시함으로써, 보다 유연한 방식으로 두 관계를 표현할 수 있는 일반화된 MF 모델을 제안한다.

1. Introduction

일반적으로 MF은 linear한 방식이므로 user와 item간의 복잡한 관계를 표현하는데 한계가 있다. 반면 Deep Neural Network(DNN)의 multi- layer구조는 non -linear하기 때문에 보다 복잡한 구조를 표현하는데 용이하다. 따라서 논문은 이런 특징에 기반해 MF의 한계를 지적하며, DNN이 어떻게 user와 item간의 관계를 표현해낼 수 있는지 보이고 있다. 논문의 contribution은 다음과 같다.

contribution

• DNN에 기반한 Collaborative Filtering 방법 제시(NCF)
• MF는 NCF의 특별한 케이스가 됨을 증명
• 다양한 실험을 통한 NCF의 효율성 증명

2. Preliminaries

Learning from implicit data

$M$ 과 $N$ 이 각각 user와 item 개수라고 할 때 user-item 행렬 $Y$ 는 아래와 같다. 여기서 $y_{u,i}=1$은 user $u$ 와 item $i$ 간의 상호작용이 있음을 나타낸다. 상호작용이란 user가 item을 열람했거나, 구매했거나 등의 암시적인(implicit) 정보를 의미하며, 주의할 점은 이것이 명시적인(explicit) 선호를 뜻하진 않는다는 것이다. 따라서 $y_{u,i}=0$은 상호작용이 없는 것이지, 해당 item을 비선호 한다는 의미는 아니다.

\[Y_{m,n} = \begin{pmatrix} y_{1,1} & y_{1,2} & \cdots & y_{1,n} \\ y_{2,1} & y_{2,2} & \cdots & y_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ y_{m,1} & y_{m,2} & \cdots & y_{m,n} \end{pmatrix}\] \[\begin{align*} where, \ \ \ y_{u,i} = \begin{cases}1, \ \text{if interaction(user $u$, item $i$) is observed} \cr 0, \ \text{otherwise} \cr\end{cases} \end{align*} \\\]

위처럼 user와 item간의 implicit한 정보를 담고있는 데이터의 문제는 user의 선호를 분명하게 정의할 수 없다는 것에 있다. 예를 들어 user가 특정 item을 좋아할 수 있지만 해당 item을 모를 경우에도 $y_{u,i}=0$이 되기 때문이다. 따라서 이런 경우, 추천은 $y_{u,i}$가 $1$이 될 확률( user $u$와 item $i$의 관련 정도)을 예측하는 문제로 귀결되며 이는 다음과 같이 표현될 수 있다.

\[\hat{y}_{u,i} = f(u,i|\Theta),\ \\ where \ f \ \ \text{is interaction function}, \Theta \ \text{is model parameters} \\\]

이런 문제를 풀때 흔히 사용하는 loss function은 크게 두 가지가 있다.

\[\begin{align*} \ L_{1} &= min \ \dfrac{1}{2}(\hat{y}_{u,i} - y_{u,i})^{2} \\ L_{2} &= max(0, f(y_{unobs})-f(y_{obs})+\alpha) \ \ s.t \ \ rank(y_{obs}) >rank(y_{unobs}) \end{align*} \\\]

먼저 $L_{1}$은 point wise loss function으로, regression문제에 많이 사용되며 실제값과 예측값의 차이를 최소화 한다. 이와 달리 $L_{2}$는 pairwise loss function으로, 관측값($y_{obs}$)이 관측되지 않은 값($y_{unobs}$)보다는 큰 값을 갖도록 하여 두 값의 마진을 최대화한다. 논문에 따르면, NCF는 Interaction function $f$에 Deep Neural Network를 사용하는 것으로, 이 경우 자연스럽게 $L_{1}$ 과 $L_{2}$ 모두를 이용할 수 있다고 한다.

Matrix Factorization

행렬 $Y$의 $y_{u,i}$를 예측하는 한 가지 방법은 MF을 이용하는 것이다. MF란 아래와 같이 $Y$를 보다 저차원 $(k<n)$ 의 행렬 2개($P$, $Q$)로 분해하여 표현하는 방법이다.

\[\begin{array}{c} Y(user-item)\\ \left[\begin{array}{ccc} y_{1,1} & \cdots & y_{1,n}\\ \vdots & \ddots & \vdots\\ y_{m,1} & \cdots & y_{m,n}\\ \end{array}\right]\\ m\times n \end{array} = \begin{array}{c} P(user)\\ \begin{bmatrix} p_{11} & \cdots & p_{1k}\\ \vdots & \ddots & \vdots\\ p_{m1} & \cdots & p_{mk}\\ \end{bmatrix}\\ m\times k \end{array} \begin{array}{c} Q(item)\\ \begin{bmatrix} q_{11} & \cdots & q_{1n}\\ \vdots & \ddots & \vdots\\ q_{k1} & \cdots & q_{kn}\\ \end{bmatrix}\\ k\times n \end{array}\] \[\begin{align*} where\ \ \mathbf{p}_{u}=[p_{u1}, \ldots ,p_{uk}], \ \ \ \mathbf{q}_{i}=[q_{1i}, \ldots ,q_{ki}] \end{align*} \\\]

이때, MF는 $y_{u,i}$ 를 아래와 같이 \(\mathbf{p}_{u}\)와 \(\mathbf{q}_{i}\)의 내적으로 추정하게 된다.

\[\begin{align*} \hat{y}_{u,i}= f(u,i|\mathbf{p}_{u}, \mathbf{q}_{i}) = \mathbf{p}_{u} \mathbf{q}_{i}^{T}= \sum_{k=1}^K p_{uk} q_{ki} \end{align*}\]

The limitation of Matrix Factorization

저자는 내적과 같은 linear 모델은 user와 item 간의 복잡한 관계를 표현하는데 한계가 있음을 지적한다.

예를 들어 위의 왼쪽 그림(a)과 같은 user-item 행렬이 있다고 할때, $s_{ij}$는 user $i$ 와 $j$의 유사도를 나타낸다고 하자. 그럼 다음과 같은 관계가 성립한다고 볼 수 있다.

\[\begin{align*} s_{23}(0.66) > s_{12}(0.50) > s_{13}(0.40) \end{align*} \\\]

즉 user 2와 3이 가장 비슷하고, user 1과 3이 가장 덜 비슷하다는 뜻이다. 위의 오른쪽 그림(b)은 이런 관계를 기하학적으로 보여주고 있다. b를 보면 user 2와 user 3이 가장 가까이 위치하며 1과 3은 가장 멀리 위치하고 있다. linear space의 한계는 새로운 user 4가 등장했을 때 발생한다. 그림 a에 따르면, user 4는 나머지 유저와 아래와 같은 관계를 갖고 있다.

\[\begin{align*} s_{41}(0.60) > s_{43}(0.40) > s_{42}(0.20) \end{align*} \\\]

하지만 그림 b가 보여주듯, user 1,2,3 이 만든 공간에 새로운 user 4를 나타낼 때, 절대 위의 식같은 관계를 표현할 수 없다. 즉 4와 1을 가장 가깝게 하는 동시에 4와 2를 가장 멀게하는 $p_{4}$벡터를 찾을 수 없는 것이다.

이런 한계는 user와 item간의 복잡한 관계를 저차원의 단순한 공간에 표현 하는데서 기인한다. (또한 linear space 는 고정된(fixed) 특징이 있기 때문에 새로운 관계를 표현하는데 유연하지 못함) 따라서 저자는 DNN을 이용해 이런 문제를 해결하고 있다.

3. Neural Collaborative Filtering

General Framework

아래 그림은 저자가 제시한 NCF의 general framework다.

• Input Layer (sparse)

  user와 item의 one-hot encoding 벡터가 input으로 사용된다.

• Embedding Layer

  embedding layer란 input 단계의 sparse 벡터를 dense 벡터로 맵핑하는 단계를 의미한다. 보통 dense 벡터를 얻기 위해 임의로 가중치를 초기화 하지만, 별도의 fully connected neural network를 사용할 수 도 있다. 예를 들어 아래 그림은 user dense 벡터를 얻기 위한 모델이다. 아래의 모델을 통해 가중치 행렬 $P$ 를 얻게 되는데, 이때 $P$는 $m$ 차원의 sparse 벡터를 $k(<m)$ 차원의 공간에 projection하는 변환 행렬으로도 볼 수 있다. 따라서 이 $P$ 행렬의 각 row는 각 user를 표현하는 저차원의 dense 벡터가 되고 이를 user latent vector로 사용하게 된다.

• Neural CF Layers

  user latent vector 와 item latent vector를 concatenation한 벡터를 input으로 받아 deep neural network 통과하는 단계다.

  • user latent vector = $P^{T}v_{u}^{U}$ (이때, $v_{u}^{U}$는 user $u$를 나타내는 one-hot 벡터)

  • item latent vector = $Q^{T}v_{i}^{I}$ (이때, $v_{i}^{I}$는 item $i$를 나타내는 one-hot 벡터)

  • deep neural network = $\phi_{X}(…\phi_{2}(\phi_{1}(P^{T}v_{u}^{U}, Q^{T}v_{i}^{I}))…)$ , $ where \ \ \phi_{x}(.) = x$번째 neural network

• Output Layers

  $y_{u,i}$의 추정치인 \(\hat{y}_{u,i}\)를 구하는 단계다. 여기서 \(\hat{y}_{u,i}\)는 user $u$와 item $i$가 얼마나 관련 있는지를 나타내며 그 값은 0과 1 사이가 된다. 이때 $\phi_{out}$ 에는 logistic 함수나 probit 함수를 사용한다.

\[\hat{y}_{u,i}= f(P^{T}v_{u}^{U}, Q^{T}v_{i}^{I}|P,Q,\Theta_{f}) = \phi_{out}(\phi_{X}(...\phi_{2}(\phi_{1}(P^{T}v_{u}^{U}, Q^{T}v_{i}^{I}))...)), \ \ \ 0 \leqq \hat{y}_{u,i} \leqq 1 \\\]

• Learning NCF

  위와 같은 모델을 학습하기 위해서는 loss function을 정의해야 한다. NCF는 0과 1사이의 예측값을 갖고, 데이터는 $y_{u,i}=1 \ or \ 0$ 과 같은 이진 데이터로 이뤄져 있다. 일반적으로 이런 분포를 모델링 할 때는 bernoulli distribution을 이용한다. 즉 $\mathcal{Y}$가 $y_{u,i}=1$인 관측치 집단, $\mathcal{Y}^{-}$가 $y_{u,i}=0$ 인 관측치 집단을 나타낼 때, likelihood function은 다음과 같다.

  \[p(\mathcal{Y}, \mathcal{Y}^{-}|P,Q,\Theta_{f})= \prod_{(u,i) \in \mathcal{Y} }{\hat{y}_{u,i}}^{y_{u,i}} \prod_{(u,j) \in \mathcal{Y}^{-}} ({1-\hat{y}_{u,j}})^{1-y_{u,i}}\]

  이어 loss function은 아래와 같다. (이는 binary cross entropy loss와 동일) 모델은 이 $L$을 최소화 하는 파라미터를 찾게 된다.

\[\begin{align*} L &= -log \ p(\mathcal{Y}, \mathcal{Y}^{-} | P,Q,\Theta_{f}) \\ \\ &= -\sum_{(u,i) \in \mathcal{Y}} y_{u,i}\ log \ \hat{y}_{u,i} - (\sum_{(u,j) \ in \mathcal{Y}^{-}} (1- y_{u,i}) \ log \ (1-\hat{y}_{u,j}) ) \\ \\ &= -(\sum_{(u,i) \in \mathcal{Y} \cup \mathcal{Y}^{-} } ( y_{u,i}\ log \ \hat{y}_{u,i} + (1- y_{u,i}) \ log \ (1-\hat{y}_{u,i}))) \end{align*} \\\]

binary cross entropy loss 해석

하나의 관측치에 대한 loss가 아래와 같다고 할 때,

\[L_{1} = -(y_{u,i}\ log \ \hat{y}_{u,i} + (1- y_{u,i}) \ log \ (1-\hat{y}_{u,i}))\]

만약 실제값이 $y_{u,i}=1$ 인데 예측값이 \(\hat{y}_{u,i}=0\)이라면, \(L_{1} = \infty\) 이 될 것이며, 반대로 실제값이 $y_{u,i}=1$ 인데 예측값이 \(\hat{y}_{u,i}=1\)이라면, \(L_{1} = 0\)이 될 것이다.

Generalized Matrix Factorization (GMF)

저자는 MF는 NCF의 특별한 케이스가 됨을 보여주며 이를 GMF로 명명한다. 만약 $\hat{y}_{u,i}$를 아래와 같이 파라미터라이징 한다면 이는 MF가 된다.

\[\begin{align*} \hat{y}_{u,i} &= a_{out}(h^{T}\phi_{1}(P^{T}v_{u}^{U}, Q^{T}v_{i}^{I})) \\ where \ \ a_{out} &= \text{identity function} \\ h^{T}&=[1,...,1]_{\text{1 x k}} \\ \phi_{1} &= P^{T}v_{u}^{U} \odot Q^{T}v_{i}^{I} \\ \end{align*}\]

GMF란 $a_{out}$ 과 $h^{T}$를 아래와 같이 두어 MF를 일반화한 모델이다.

\[\begin{align*} a_{out}=1/(1 + e^{-x}), \ \ h^{T}=[h_{1},...,h_{k}] \end{align*} \\\]

이때, $a_{out}$에는 시그모이드 함수를 사용했으며, $h^{T}$에는 non uniform 값을 주어 내적할 때, 각 텀에 각기 다른 가중치를 줄 수 있도록 하였다. 이는 latent 벡터의 중요도를 조절하는 역할을 하게 된다.

Multi-Layer Perceptron (MLP)

저자에 따르면 GMF는 linear하고 fixed한 특징으로 인해 user 와 item간의 복잡한 관계를 표현하지 못하는 반면 MLP는 non-linear하고 flexible 하기 때문에 보다 복잡한 관계를 표현할 수 있다고 한다. 이에 따르면 MLP는 다음과 같이 파라미터라이징 된다.

\[\begin{align*} z_{1} &= \phi_{1}(P^{T}v_{u}^{U}, Q^{T}v_{i}^{I}) = \begin{bmatrix} P^{T}v_{u}^{U} \\ Q^{T}v_{i}^{I} \end{bmatrix} \\ z_{2} &= \phi_{2}(z_{1}) = a_{2}(W_{2}^{T}z_{1} + b_{2}) \\ \cdots \\ z_{L} &= \phi_{L}(z_{L-1}) = a_{L}(W_{L}^{T}z_{L-1} + b_{L}) \\ \hat{y}_{u,i} &= \sigma(h^{T}\phi_{L}(z_{L-1})) \end{align*} \\\]

이때 $\phi_{1}$은 user와 item의 latent vector를 concatenation하는 함수이며, $\phi_{l}\ (l \ge 2)$은 Neural Net 함수로 $W$와 $b$는 각각 가중치 행렬과 편향 벡터를 나타낸다. 마지막 식은 GMF의 구조와 동일하다. 이때 차이점은 GMF는 $\phi_{1}(.)$ 가 linear구조인 반면, MLP는 $\phi_{L}(.)$ 가 non-linear 구조란 것이다.

Fusion of GMF and MLP

저자는 아래 그림과 같이 GMF와 MLP를 통합한 모델을 제시한다. 이는 각자가 가진 장점을 살릴 수 있는 반면 단점은 서로 보완할 수 있다고 한다.

통합 프레임워크의 가장 큰 특징은 각 모델별로 서로 다른 embedding layer를 사용한다는 것이다. 아래 식은 이 모델이 어떻게 파라미터라이징 되는지 보여준다.

\[\begin{align*} \phi^{GMF} &= p_{u}^{G} \odot q_{i}^{G} \\ \phi^{MLP} &= a_{L}(W_{L}^{T}(a_{L-1}(...a_{2}(W_{2}^{T} \begin{bmatrix} p_{u}^{M} \\ q_{i}^{M} \end{bmatrix}+b_{2})...))+b_{L}) \\ \hat{y}_{u,i} &= \sigma(h^{T} \begin{bmatrix} \phi^{GMF} \\ \phi^{MLP} \end{bmatrix}) \end{align*}\]

여기서 $p_{u}^{G}, \ \ p_{u}^{M}$은 각각 GMF와 MLP의 user latent vector다. 서로 다른 embedding layer를 사용한다는 의미는 두 벡터의 차원이 다를 수 있다는 것이다. 마찬가지로 $q_{i}^{G}, \ \ q_{i}^{M}$ 도 각각 GMF와 MLP의 item latent vector를 나타낸다. $\hat{y}_{u,i}$를 구할 때는, 각 모델에서 나온 output인 $\phi^{GMF}$와 $\phi^{MLP}$를 concatenation하여 $h$로 가중치를 줘 최종추정치를 구하게 된다.

이 모델은 user-item간의 상호 관계를 표현하기 위해 MF의 linearity 와 MLP의 non-linearity를 결합한 것이 특징이며 저자는 이 모델을 일컬어 neural matrix factorization 라고 하였다.

4. Conclusion

(이 부분은 논문의 결론이 아닌 제가 정리한 결론임을 미리 말씀드립니다. )

NeuMF (neural matrix factorization)은 GMF와 MLP를 결합한 모델이다. GMF는 MF를 일반화한 모델, MLP는 DNN(deep neural network) 모델로, 둘 모두 논문에서 제시된 NCF(neural collaborative framework)로 표현 가능했다.

저자에 따르면, NeuMF은 collaborative filtering의 핵심 가치(user와 item의 상호작용 모델링)를 놓치 않으면서 성능은 높인, 그런 방법이다. 이것이 가능한 이유는 linear space에 기반한 기존 모델들이 갖는 한계를 DNN을 도입해 해결할 수 있었기 때문이다. 나아가 DNN에만 의존한 것이 아닌 두 모델을 통합함으로써 더 큰 성능 향상을 보일 수 있었다.

이 방법은 기존의 여러 모델들(Neural Tensor Network, Wide & Deep learning)과 아이디어는 비슷하지만 collaborative filtering의 아이디어를 실현한다는 점에서 가장 큰 contribution을 갖는다.

Code

Neural Collaborative Filtering 구현 코드