Probabilistic Matrix Factorization (알고리즘)

안녕하세요. 이번 시간엔 추천시스템에서 Matrix Factorization의 일종인 Probabilistic Matrix Factorization(PMF)에 대해 보도록 하겠습니다.

 

참고한 자료는 다음과 같습니다.

 

Mnih, A., & Salakhutdinov, R. R. (2008). Probabilistic matrix factorization. In Advances in neural information processing systems (pp. 1257-1264).

papers.nips.cc/paper/2007/file/d7322ed717dedf1eb4e6e52a37ea7bcd-Paper.pdf

Probabilistic Matrix Factorization 코드

 

github.com/fuhailin/Probabilistic-Matrix-Factorization/blob/master/ProbabilisticMatrixFactorization.py

fuhailin/Probabilistic-Matrix-Factorization

Probabilistic Matrix Factorization의 목적식 증명

http://resources.mpi-inf.mpg.de/d5/teaching/ss13/dmm/slides/12-pmf-handout.pdf

모델에 대한 설명

우리가 모델을 만들 때 여러 기준으로 나눌 수 있지만 크게 데이터의 분포를 가정한 모델과 가정하지 않은 모델로 나눌 수 있습니다.(parametric 모델 vs non-parametric 모델, 나누는 기준에 따라 데이터 분포 외에 다른 것도 고려하는 경우도 있긴합니다만 여기선 데이터 분포만 기준으로 하겠습니다.) 추천시스템에 적용한다면 점수값이 Gaussian, Poisson 등의 분포를 따른다고 가정하는 경우 parametric 모델이 되는 것입니다.

 

이번 시간에 볼 모델은 user가 item에 주는 점수값은 Gaussian 분포를 가진다고 가정한 모델입니다. 우선 논문에서 점수에 대해 다음과 같은 가정을 합니다.

 

$p(R|U,V,\sigma^{2}) = \prod_{i=1}^{N} \prod_{j=1}^{M}[\mathcal{N}(R_{ij}|U_{i}^{T}V_{j}, \sigma^{2})]^{l_{ij}}$

- $U$ : User latent Matrix ($U \in R^{D x N}$)

- $V$ : Item latent Matrix ($V \in R^{D x M}$)

- $\sigma^{2}$ : 분산값 (Hyperparameter)

- $R_{ij}$ : user i의 item j에 대한 점수

- $U_{i}^{T}$ : User i의 latent vector 

- $V_{j}$ : item j의 latent vector

- $I_{ij}$ : user i가 item j에 점수가 있으면 1, 없으면 0

- $N$ : user 개수

- $M$ : item 개수

- $D$ : latent 변수 개수

 

위의 식이 의미하는 바는 다음과 같습니다. 우리가 가진 데이터에서 점수 집합 R이 나올 확률은 각 user와 item의 latent vector를 곱한 값을 평균으로, $\sigma^{2}$를 분산값으로 가진 정규분포들의 곱으로 구성된다는 것입니다. 여기서 U와 V 또한 gaussian 분포를 따르는 matrix로 가정하고 있습니다.

 

$p(U|\sigma_{U}^{2}) = \prod_{i=1}^{N} \mathcal{N}(U_{i}|0,\sigma_{U}^{2}\textbf{I})$

$p(V|\sigma_{V}^{2}) = \prod_{j=1}^{M} \mathcal{N}(V_{j}|0,\sigma_{V}^{2}\textbf{I})$

 

이를 정리하면 다음과 같습니다.

  - 점수값들은 user와 item latent vector의 내적을 평균값으로, 분산값으로 $\sigma^{2}$를 가진 Gaussian 분포(정규분포)로 구성

  - 각 user와 item latent matrix는 평균이 0, 분산이 $\sigma_{U}^{2}$, $\sigma_{V}^{2}$인 정규분포로 구성

 

이러한 분포들과 Bayesian rule을 활용하면 다음과 같은 식이 됩니다. (증명 부분은 위의 참고자료인 'Probabilistic Matrix Factorization의 목적식 증명'을 참고하세요)

$p(U,V|R,\sigma^{2},\sigma_{V}^{2},\sigma_{U}^{2}) \, \propto \, p(R|U,V,\sigma^{2})p(U|\sigma_{U}^{2})p(V|\sigma_{V}^{2})$

 

좌변식은 우리가 모델 파라미터를 구할 때 활용했던 MAP(Maximum a Posterior) Estimation에서 볼 수 있는 식입니다. $U, V$를 구하고자 하는 파라미터로 보고 $R, \sigma^{2}, \sigma_{V}^{2}, \sigma_{U}^{2}$를 주어진 값으로 보면 $p(\theta|X,Y)$와 유사한 구조가 됩니다.

(MAP Estimation에 대해 모르신다면 공부를 하고 보시는 것을 추천드립니다)

 

우변은 우리가 위에서 본 식들로 구성되어 있습니다. 즉, 우리가 가진 식들을 활용한다면 좌변 부분을 만들 수 있습니다. 이를 활용해 log 목적함수(손실 함수)을 만들면 다음과 같은 구조로 됩니다.

$p(U,V|R,\sigma^{2},\sigma_{V}^{2},\sigma_{U}^{2})$

$\propto \, p(R|U,V,\sigma^{2})p(U|\sigma_{U}^{2})p(V|\sigma_{V}^{2})$

(log 넣으면)

$\propto \, p(R|U,V,\sigma^{2}) + p(U|\sigma_{U}^{2}) + p(V|\sigma_{V}^{2})$

$\propto \, \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{M}I_{ij}(R_{ij} - U_{i}^{T} V_{j})^{2} + \frac{\lambda_{U}}{2}\sum_{i=1}^{N} ||U_{i}||_{Fro}^{2} + \frac{\lambda_{V}}{2}||V_{j}||_{Fro}^{2}$

$= E$

($\propto$의 경우 상수 term 등 식에 영향을 주지 않는 부분은 빼거나 변형된 식입니다. 과정이 많이 생략되긴 했는데, 논문하고 위의 참고자료를 보시면 될 것 같습니다. 이해가 안되시면 질문 주셔도 됩니다!)

 

이제 목적함수인 $E$가 완성되었습니다. $R, \sigma^{2}, \sigma_{V}^{2}, \sigma_{U}^{2}$ 등은 이미 주어진 값이며 학습이 가능한 값은 $U, V$입니다. 그렇기 때문에 두 값을 활용해 이 목적함수 값을 최소화 시키는 값을 찾아야합니다. 식이 2차식이라 $U, V$를 미분했을 때 최적값이 나오므로 이를 활용해 Gradient를 구합니다.

$\frac{\partial E}{\partial U_{i}} = \sum_{j=1}^{M} (I_{ij}(R_{ij} - U_{i}^{T} V_{j}))V_{j} + \lambda_{U} U_{i}$

  - $\lambda_{U} = \frac{\sigma^{2}}{\sigma_{U}^{2}}$

$\frac{\partial E}{\partial V_{i}} = \sum_{i=1}^{N} (I_{ij}(R_{ij} - U_{i}^{T} V_{j}))U_{i} + \lambda_{V} V_{j}$

  - $\lambda_{V} = \frac{\sigma^{2}}{\sigma_{V}^{2}}$

 

이를 활용해 모델을 학습시키게 됩니다.

 

그리고 논문 아래에 보면 $g(U^{T}V)$가 있는데 이건 $U^{T}V$ 값을 sigmoid에 넣은 값입니다. 즉, feature space를 변환시킨 것으로 위의 식에서 sigmoid 부분만 반영해 넣어주시면 됩니다.

알고리즘

알고리즘은 다음과 같습니다.

1. $U, V$에 대한 값 초기화 : 각각 $N x D$, $M x D$ 크기로 랜덤 정규분포 값을 할당합니다. 위에서 보면 평균값은 0, 분산값은 $\sigma_{U}^{2}, \sigm_{V}^{2}$로 되어 있으므로 임의의 값으로 주면 됩니다.

2. $U, V$ 값을 곱하여 예측값을 구합니다.

3. 오차값을 활용해 $U$, $V$에 해당하는 Gradient 값을 구합니다.

4. Gradient를 $U, V$에 반영합니다.

5. 2~4를 정한 횟수만큼 반복합니다.

 

여기까지가 Probabilistic Matrix Factorization에 대한 설명이었습니다. 궁금하시거나 수정할 부분 있으시면 말씀해주세요. 감사합니다!