[논문 리뷰] Logistic Matrix Factorization for Implicit Feedback Data

Recommender System

본 논문은 2014년에 음악 스트리밍 서비스사 Spotify에서 발표한 논문이다. 해당 논문에서는 클릭과 같은 implicit 데이터를 사용해 user에게 특정 artist를 추천하는데 Logistic Matrix Factorization을 이용한다. 이번 포스팅을 통해 각자의 문제에 어떻게 적용할 수 있을지 고민해보자.

Abstract

Collaborative Filtering(CF)이란, 비슷한 사람들끼리는 비슷한 상품을 좋아할 것이란 철학 하에 user와 item간의 interaction을 분석하는 방법이다. Matrix Factorization(MF)은 이를 위한 한가지 방법이다. 그 중 Logistic Matrix Factorization(LMF)은 확률 모델로, 기존의 MF와 달리 user가 특정 item을 좋아할 확률을 모델링 하는 것이 핵심이다.

1. Problem setup and notation

Collaborative Filtering의 목표는 user의 과거 행동이력을 분석해서 미래의 관심사를 예측하는 것이다. 이때 행동 이력으로 클릭, 페이지뷰수 등의 implicit 정보를 사용할 수 있다. 먼저 user, item, rating을 아래와 같이 정의하자.

\[\begin{align*} &\bullet \ \ U = (u_{1},...,u_{n}): \text{a group of $n$ users} \\ &\bullet \ \ I = (i_{1},...,i_{m}): \text{a group of $m$ items} \\ &\bullet \ \ R = (r_{ui})_{n \times m}: \text{a user-item observation matrix where $r_{ui} \ge 0$ } \\ \\ \end{align*}\]

여기서 rating $r_{ui}$는 user $u$가 item $i$와 interaction(클릭, 스트리밍 등)한 횟수로, non-negative하다. 이때 중요한 점은 $r$이 반드시 정수일 필요는 없다는 것이다. 예를 들어 user의 최근 스트리밍에 더 큰 가중치를 줄 경우 정수가 되지 않을 수도 있다.

또 $r_{ui}=0$은 user $u$가 item $i$에 iteraction이 없다는 것을 의미한다. 이때 주의할 점은 0이라해서 user가 해당 item을 비선호 한다는 것은 아니란 것이다. 왜냐하면 어떤 item을 좋아할 수도 있는데 아직 모를 경우에도 0이 되기 때문이다. 마찬가지로 $r_{ui}$가 크다고 해서 반드시 선호를 의미하지도 않는다. 따라서 논문은 이런 데이터의 confidence를 판단할 수 있는 방법에 대해 고민하며, 이는 implicit feedback 문제에서 중요한 이슈라고 할 수 있다.

2. Logistic MF

지금부터 앞서 이야기한 데이터의 confidence를 어떻게 정의하고 모델링하는지 살펴보겠다.

Confidence definition

implicit feedback 데이터의 confidence는 $r_{ui}$를 얼마나 신뢰할 수 있을지에 대한 문제다. 예를 들어 user $u$가 해당 item $i$를 그닥 좋아하지도 않는데 실수로 여러번 눌렀을 수도 있고, 또 반대의 경우도 있을 것이다. 이런 상황을 고려할 때 $r_{ui}$에 대한 confidence는 다음과 같이 정의한다.

\[\begin{align*} c_{ui} := \alpha r_{ui} \end{align*}\] \[\begin{align*} \alpha \uparrow \ \ &\Leftrightarrow \text{weighting on positive feedback} \\ \alpha \downarrow \ \ &\Leftrightarrow \text{weighting on negative feedback} \end{align*} \\\]

여기서 $\alpha$는 튜닝 파라미터로 이 값이 클수록 positive feedback($r_{ui}>0$)에 더 큰 가중치를 주고, 작을수록 negative feedback($r_{ui}=0$)에 가중치를 더 주게 된다. 이때 $\alpha$와 $r_{ui}$가 클수록 confidence가 커지는데, 이는 당연히 interaction이 크다는 것은 어느정도 관심이 있음을 나타내기 때문이다.

Confidence modelling

이어 confidence를 모델링하기 위해 확률변수 하나를 정의해보겠다. user $u$의 item $i$에 대한 선호를 $l_{ui}$라고 하고, 다음과 같이 표현한다. 즉 이 값이 1이면 선호를, 0이면 비선호를 나타낸다. 이때 $p(l_{ui})$는 user $u$가 item $i$를 선호할 확률이라고 할 수 있다.

\[\begin{align*} l_{ui} = \begin{cases} 1& \text{postive} \\ 0& \text{negative} \end{cases} \end{align*}\]

이때 $l_{ui}$는 $r_{ui}$에 depend하여 결정되기 때문에, $l_{ui}$의 분포를 정의하는 것은 결국 $c_{ui}(=\alpha r_{ui})$의 분포를 정의하는 것과 동일하다. 따라서 다음과 같은 관계가 성립한다.

\[\begin{align*} l_{ui}=1 \ \ &\Leftrightarrow \ \ c_{ui}(=\alpha r_{ui})>0 \ \ \rightarrow \ p(l_{ui}) \\ l_{ui}=0 \ \ &\Leftrightarrow \ \ c_{ui}(=\alpha r_{ui}) = 0 \ \ \rightarrow \ 1-p(l_{ui}) \end{align*}\]

즉 여기서 $c_{ui}>0$ 가 될 확률은 $p(l_{ui})$이고, \(c_{ui} = 0\) 이 될 확률은 $1-p(l_{ui})$ 일 때, $c_{ui}(= \alpha r_{ui})$는 다음과 같은 베르누이 분포를 따른다고 볼 수 있다.

\[\begin{align*} \alpha r_{ui} &\sim Ber(p(l_{ui})) \\ \end{align*}\]

Confidence modelling with logistic probability

논문의 제목에서도 드러나듯, 여기에서는 위의 $p(l_{ui})$를 다음과 같이 logistic 확률로 정의한다.

\[\begin{align*} p(l_{ui}|\mathbf{x}_{u}, \mathbf{y}_{i}, \beta_{u}, \beta_{i}) = \frac{\exp(\mathbf{x}_{u} \mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})}{1+\exp(\mathbf{x}_{u} \mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})} \end{align*} \\\]

이때 \(\mathbf{x}, \mathbf{y}\) 는 아래와 같이 user-item matrix $R$을저차원 행렬 2개로 분해하여 얻은 결과로, 이를 matrix factorization라 한다.

\[\begin{align*} where \ \ \mathbf{x}_{u} &= \text{latent vector of user $u$} \ \ (1 \times f) \\ \ \ \mathbf{y}_{i} &= \text{latent vector of item $i$} \ \ (1 \times f) \\ \ \ \beta_{u} &= \text{user $u$ bias} \ \ (1 \times 1) \\ \ \beta_{i} &= \text{item $i$ bias} \ \ (1 \times 1)\\ \end{align*}\]

여기서 bias를 고려하는 이유는 어떤 사람은 다양한 상품을 좋아하는 반면 어떤 사람은 그렇지 않고, 또 어떤 상품은 인기가 많은 반면 어떤 상품은 인기가 없을 수도 있기 때문이다. 이처럼 $\beta_{u}$는 user의 성향 편차, $\beta_{i}$는 item의 인기도 편차를 상쇄시키는 역할을 한다.

Parameter estimation by MAP

앞서 $\alpha r_{ui}$는 베르누이 분포를 따른다고 했으므로, likelihood를 다음과 같이 정의할 수 있다.

\[\begin{align*} L(R|X,Y,\beta) = \prod_{u,i}&p(l_{ui}|\mathbf{x}_{u}, \mathbf{y}_{i}, \beta_{u}, \beta_{i})^{\alpha r_{ui}}(1-p(l_{ui}|\mathbf{x}_{u}, \mathbf{y}_{i}, \beta_{u}, \beta_{i}))^{1-l_{ui}} \end{align*}\]

이어 이를 바탕으로 파라미터를 추정하기위해, 추가적으로 latent vector \(\mathbf{x}_{u}\) 와 \(\mathbf{y}_{i}\) 에 대한 사전확률을 다음과 같이 정의하도록 한다.

\[\begin{align*} p(X|\sigma^{2}) &= \prod_{u}N(\mathbf{x}_{u}| \mathbf{0}, \sigma_{u}^{2}I) \\ p(Y|\sigma^{2}) &= \prod_{i}N(\mathbf{y}_{i}| \mathbf{0}, \sigma_{i}^{2}I) \\ \end{align*}\]

likelihood와 사전확률이 정의되었다면, 아래와 같은 베이즈 정리를 이용하여 파라미터를 추정할 수 있다. 여기서 우리가 추정해야할 파라미터는 \(\Theta= \{ X,Y, \beta_u , \beta_i \}\) 다. $X,Y$는 모델(MF) 파라미터, $ \beta_u , \beta_i$는 편차에 대한 파라미터다.

\[\begin{align*} \\ p(X,Y, \beta_u , \beta_i|R) &\propto p(R|X,Y, \beta_u , \beta_i)p(X)p(Y) \\ \end{align*}\]

위 식은 아래와 동치며 이것이 우리의 objective function이다.

\[\begin{align*} \\ &\log p(X,Y, \beta_u , \beta_i|R) \\ \propto \ &\log p(R|X,Y, \beta_u , \beta_i) + \log p(X) + \log p(Y) \\ = \ & \sum_{u,i}\{ \alpha r_{ui} \log p(l_{ui} | \mathbf{x}_{u}, \mathbf{y}_{i}, \beta_{u}, \beta_{i}) + \log (1-p(l_{ui} | \mathbf{x}_{u}, \mathbf{y}_{i}, \beta_{u}, \beta_{i})) \} \ + \\ &\sum_{u}\log N(\mathbf{x}_{u}|\mathbf{0}, \sigma^{2}_{u}I) + \sum_{i}\log N(\mathbf{y}_{i}|\mathbf{0}, \sigma^{2}_{i}I) \\ = &\sum_{u,i} \alpha r_{ui}(\mathbf{x}_{u}\mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i}) - (1+\alpha r_{ui}) \log(1+\exp(\mathbf{x}_{u}\mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})) \\ &- \frac{\lambda}{2} \lVert \mathbf{x}_{u} \rVert^{2} - \frac{\lambda}{2} \lVert \mathbf{y}_{i} \rVert^{2} \\ \\ \end{align*}\]

마지막으로 이 objective function을 파라미터에 대해 미분해서 추정값을 구해야 된다. 이때, Alternating Least Squares (ALS) 알고리즘을 사용한다. ALS는 user 파라미터 \(\mathbf{x}_{u}, \beta_{u}\) 와, item 파라미터 \(\mathbf{y}_{i}, \beta_{i}\)를 번갈아 가면서 추정하는 방식이다. 이 방식은 spare 데이터에 robust하다고 알려져있다.

\[\begin{align*} \\ &\text{(i) Fix the item vectors} \ \mathbf{y}_{i} \ \text{and biaes} \ \beta_{i} \ ( \bar{y}_{i}, \bar{\beta}_{i}) \\ \\ &\bullet \ \frac{\partial \log p(X,Y,\beta|R)}{\partial \mathbf{x}_{u}} = \sum_{i} \alpha r_{ui}\mathbf{y}_{i} - \frac{\mathbf{y}_{i}(1+\alpha r_{ui})\exp(\mathbf{x}_{u}\mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})}{1+\exp(\mathbf{x}_{u}\mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})} - \lambda \mathbf{x}_{u} \\ &\bullet \ \frac{\partial}{\partial \beta_{u}} = \sum_{i} \alpha r_{ui} - \frac{(1+\alpha r_{ui})\exp(\mathbf{x}_{u}\mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})}{1+\exp(\mathbf{x}_{u}\mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})} \\ \\ \\ &\text{(ii) Fix the user vectors} \ \mathbf{x}_{u} \ \text{and biaes} \ \beta_{u} \ ( \bar{x}_{u}, \bar{\beta}_{u}) \\ \\ &\bullet \ \frac{\partial \log p(X,Y,\beta|R)}{\partial \mathbf{y}_{i}} = \sum_{u} \alpha r_{ui} \mathbf{x}_{u} - \frac{\mathbf{x}_{u} (1+\alpha r_{ui})\exp(\mathbf{x}_{u}\mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})}{1+\exp(\mathbf{x}_{u}\mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})} - \lambda \mathbf{y}_{i} \\ &\bullet \ \frac{\partial}{\partial \beta_{i}} = \sum_{u} \alpha r_{ui} - \frac{(1+\alpha r_{ui})\exp(\mathbf{x}_{u}\mathbf{y}_{i}^{T} + \beta_{u}+\beta_{i})}{1+\exp(\mathbf{x}_{u}\mathbf{y}_{i}^{T}+ \beta_{u}+\beta_{i})} \\ \\ \\ \end{align*}\]

3. Experimental study

여기에서는 논문에서 사용한 평가 metric만 간단하게 살펴보겠다. 논문에서는 아래와 같은 Mean Percentile Ranking(MPR)을 사용하였다.

\[\begin{align*} MPR = \frac{\sum_{ui} r_{ui}^{t} \ rank_{ui}}{\sum_{ui} r_{ui}^{t}} \\ \\ \end{align*}\]

여기서 $r_{ui}^{t}$는 test데이터의 관측값이고, $rank_{ui}$는 예측된 percentile ranking이다. 따라서 $rank_{ui}=0 \%$이면 가장 높은 순위로 예측된 것이고, $rank_{ui}=100 \%$ 이면 가장 낮은 순위로 예측된 것이 된다. 학습이 잘 되었을 경우(case1)와, 그렇지 않은 경우(case2)를 예로 들어 위 meric이 어떻게 반응하는지 살펴보겠다. item이 2개밖에 없다고 가정해보자.

\[\begin{align*} \bullet \text{case1} : (r_{u1}^{t} , \ rank_{u1})=(100,0), \ \ (r_{u2}^{t} &, \ rank_{u2})=(0,100) \\ \\ MPR = \frac{(100 \times 0) + (0 \times 100)}{100+0} & = 0 \end{align*}\] \[\begin{align*} \bullet \text{case2} : (r_{u1}^{t} , \ rank_{u1})=(100,100), \ \ (r_{u2}^{t} &, \ rank_{u2})=(0,0) \\ \\ MPR = \frac{(100 \times 100) + (0 \times 0)}{100+0} & = 100 \\ \\ \end{align*}\]

먼저 학습이 잘된 case1의 경우 $MPR=0$이다. 즉 MPR이 낮을 수록 학습이 제대로 이뤄진 것이다. 이는 실제로 interaction이 많은 item이 높은 순위로 예측됐다는 것을 의미한다. 반면 학습이 제대로 안 된 case2의 경우 $MPR=100$이다. 즉 MPR이 높을 수록 학습이 제대로 안된 것이다. 이는 실제로 interaction이 많은 item이 낮은 순위로 예측된 것을 의미한다. 정리하자면 $MPR$은 interaction이 높은 item이 실제로 높은 등수로 예측됐는지를 측정하는 것이다.

4. Conclusion

정리하자면 Logistic Matrix Factorization(LMF)란, item에 대한 user의 선호를 확률적으로 모델링한 것이 특징이다.
이는 MF에 logistic 함수를 도입해 가능했다. MF는 간단하지만 powerful한 모델로 다양한 분야에서 여전히 많이 사용 중이다.

Code

Logistic Matrix Factorization 구현 코드