Matrix Factorization : MF
유저-아이템 행렬을 저차원의 user와 item의 latent factor 행렬의 곱으로 분해하는 방법
SVD와 달리 관측한 선호도만 모델링에 활용한다.
목표 : 관측되지 않은 선호도를 예측하는 일반적인 모델을 만드는 것
$$R \approx P \times Q^{T} = \widehat{R}$$
- $P$ : User Matrix
- $Q$ : Item Matrix
- $|U|$ : user의 수
- $|I|$ : item의 수
- k : latent vector 수
- $\widehat{r_{u,i}}$ : true rating = 유저가 매긴 실제 rating값
- $p_{u}$ : 유저u의 latent vector
- $q_{i}$ : 아이템i의 latent vector
$P \times Q^{T}$가 최대한 $R$과 유사하도록 $\widehat{R}$을 추론한다.
P와 Q안의 유저 벡터와 아이템 벡터들은 학습 파라미터가 된다. 원래 우리가 가지고 있던 데이터는 R뿐이고 P와 Q의 파라미터들을 최적화하는 것이다.
$$\widehat{r_{u,i}} = p_{u}^{T}q_{i}$$
두 벡터 $p_{u}^{T}$와 $q_{i}$를 내적(dot product)하면 하나의 값인 추론한 rating이 나오게 된다.
그래서 추론한 $\widehat{r_{u,i}}$과 원래 rating값을 $\widehat{r_{u,i}}$을 뺀 차이를 줄인다.
두 차이를 MSE로 정의하고 줄어들게 최적화하면 $p_{u}^{T}$와 $q_{i}$가 학습된다.
$$\min_{P,Q} \displaystyle\sum_{observed\,r_{u,i}}(r_{u,i}-p_{u}^{T}q_{i})^{2}$$
Objective Function
$$\min_{P,Q} \displaystyle\sum_{observed\,r_{u,i}}(r_{u,i}-p_{u}^{T}q_{i})^{2} + \lambda(\parallel p_{u}\parallel^{2}_{2}+ \parallel q_{i}\parallel^{2}_{2})$$
이 식은 위의 식에서 regularization term $\parallel p_{u}\parallel^{2}_{2}+ \parallel q_{i}\parallel^{2}_{2}$
을 더해서 overfitting되지 않게 한다. L2 norm을 적용해서 $p_{u}$와 $q_{i}$가 너무 커지지 않게 한다.
밑에 써있듯이 observed여서 실제 관측된 데이터만 사용한다.
정규화(Regularization)이란? ↓
weight를 loss function에 넣어주어 weight가 너무 커지지 않게 제한하는 방법
값이 극히 커지면 그 데이터를 자세하게 표현하는 경향이 있다.
regularization term에 곱해지는 $\lambda$의 크기에 따라 강도가 영향을 받는다.
$\lambda$가 너무 크면 weight가 제대로 변하지 않아서 underfitting이 일어나고,
작으면 정규화 효과가 별로 없다.
확률적 경사하강법 : Stochastic Gradient Descent : SGD
파라미터를 업데이트하는 방법
gradient를 계산하기 위해서 loss function을 편미분한다.
Gradient
$$\frac{\partial L}{\partial p_{u}} = \frac{\partial( r_{u,i}-p_{u}^{T}q_{i})^{2}}{\partial p_{u}} + \frac{\partial\lambda\parallel p_{u}\parallel^{2}_{2}}{\partial p_{u}} = -2(r_{u,i}- p_{u}^{T}q_{i})q_{i} + 2\lambda p_{u}$$
로 gradient를 정리할 수 있다.
error term
$$e_{u,i} = r_{u,i}-p_{u}^{T}q_{i}$$
을 대입하면
$$-2(e_{u,i}q_{i}-\lambda p_{u})$$
와 같은 식을 결과적으로 얻을 수 있다.
gradient의 반대방향으로 update해야하기 때문에 계산한 gradient에 -를 붙혀 업데이트한다.
$$p_u\leftarrow p_u+\eta \cdot(e_{ui}q_i-\lambda p_u)$$
$$q_i\leftarrow q_i+\eta \cdot(e_{ui}p_u-\lambda q_i)$$
※ $\eta$ = learning rate
추가적인 테크닉
Biases
유저별로 rating을 전체적으로 높게 줄 수도, 낮게 줄 수도 있다. 아이템도 이렇게 편향이 생길 수 있다.
그래서 matrix factorization model에 편향을 반영할 수 있는 파라미터를 추가하여서 예측성능을 높힐 수 있다.
$$\underset{P,Q}{\min}\sum_{\text{observed }r_{u,i}}(r_{u,i}-\mu - b_u-b_i-p_u^Tq_i)^2+\lambda(\|p_u\|_2^2+\|q_i\|_2^2+b_u^2+b_i^2)$$
- $\mu$ : global 평균 : 학습하는 파라미터 아님
- $b_u$ : 개별 유저의 편향을 학습할 수 있는 파라미터
- $b_i$ : 개별 아이템의 편향을 학습할 수 있는 파라미터
regularization term에도 편향이 추가된다.
기존의 $p_u$와 $q_i$뿐만아니라 bias도 추가해서 업데이트 한다.
$$b_u \leftarrow b_u+\gamma \cdot (e_{ui}-\lambda b_u)\\b_i \leftarrow b_i+\gamma \cdot (e_{ui}-\lambda b_i)\\p_u \leftarrow p_u+\gamma \cdot (e_{ui}q_i-\lambda p_u)\\q_i \leftarrow q_i+\gamma \cdot (e_{ui}p_u-\lambda q_i)$$
※$\gamma$ = learning rate
Confidence level
데이터 하나하나에 대해서 동일한 기준과 비율로 학습하게 된다. 하지만 모든 데이터가 동일하게 중요거나 신뢰할 수 없기 때문에, 특정 데이터만 더 많이 모델에 반영할 수 있게 confidence를 추가한다.
$$\underset{P,Q}{\min}\sum_{\text{observed }r_{u,i}} c_{u,i}(r_{u,i}-\mu - b_u-b_i-p_u^Tq_i)^2+\lambda(\|p_u\|_2^2+\|q_i\|_2^2+b_u^2+b_i^2)$$
$c_{u,i}$ 라는 신뢰도 값을 실측값과 예측값의 차에 곱해주어 confidence가 높으면 더 많이 loss function에 반영되어 더 많이 학습하게 될 것이다.
Temporal Dynamics
학습 파라미터가 시간에 따른 변화를 반영한다.
ex) 아이템은 초반에는 인기가 많지만 나중에는 떨어질수도 있고, 시간이 지남에 따라 유저가 rating을 후하게 주는 성격으로 변할 수도 있다.
원래는 t와는 독립적인 관계였는데, t를 추가하여 시간에 따라 증가하거나 감소할 수 있게 한다.
$$\widehat{r_{u,i}(t)}=\mu+b_u(t)+b_i(t)+p_u^Tq_i(t)$$
ALS : Alternative Least Square
P와 Q를 동시에 업데이트 하지 않고, 한 번은 Q를 상수로 보고 P를 업데이트, 다른 한 번은 P를 상수로 보고 Q를 업데이트한다. 이렇게 번갈아 가며 $p_u$나 $q_i$를 상수로 고정하면 목적함수가 quadratic form 이 되어 convex하기 때문에 다른 하나로 least-square(최소제곱법) 수식를 푸는 것과 같아진다.
sparse한 데이터에 대해 더 robust하게 학습할 수 있고, 대용량 데이터를 병렬처리해서 빠르게 학습할 수 있다.
Objective Function
$$\min_{P,Q} \displaystyle\sum_{observed\,r_{u,i}}(r_{u,i}-p_{u}^{T}q_{i})^{2} + \lambda(\parallel p_{u}\parallel^{2}_{2}+ \parallel q_{i}\parallel^{2}_{2})$$
수식은 MF와 동일한데, ALS는 P와 Q를 번갈아 상수로 지정하며 업데이트 한다.
하나가 상수가 되면 quadratic form이 되므로 해를 deterministic하게 구할 수 있다
= 수식 계산 한 번으로 구할 수 있다
- $p_u$를 고정할 때
$q_i$만 업데이트
$$q_i=(P^TP+\lambda I)^{-1}P^Tr_i$$
이 행렬 연산 한번으로 $q_i$를 구할 수 있다 - $q_i$를 고정할 때
$p_u$만 업데이트
$$p_u=(Q^TQ+\lambda I)^{-1}Q^Tr_u$$
Implicit Feedback을 고려한 MF
기존 MF는 rating만 고려했다면 이제 rating을 2개로 나누어서 고려한다.
- Preference
유저가 아이템을 선호하는지 여부
MF의 $p_u$, $q_i$의 내적은 f(preference)를 예측하게 된다.
- $f_{ui}$ =1 ($r_{ri} > 0$)
선호한다 - $f_{ui}$ =0 ($r_{ri} = 0$)
선호하지 않는다
- $f_{ui}$ =1 ($r_{ri} > 0$)
- Confidence
유저가 아이템을 얼마나 선호하는지 나타내는 증가 함수
$$c_{ui}=1+\alpha\cdot r_{ui}$$
$alpha$를 크게하는 경우 긍정 feedback과 부정 feedback의 상대적인 중요도를 크게 둘 수 있다. 작게 두면 rating값에 많이 영향을 받지 않게 학습하게 된다.
Objective Function
$$\underset{P,Q}{\min}\sum_{\text{ovserved }r_{u,i}}c_{u,i}(f_{u,i}-p_u^Tq_i)^2+\lambda(\displaystyle\sum_{u}\|p_u\|_2^2+\displaystyle\sum_{i}\|q_i\|_2^2)$$
$p_u^Tq_i$을 가지고 원래는 rating을 바로 예측했지만 implicit feedback을 고려하면 preference를 예측하게 된다. 예측값과 실제값의 차이를 얼마나 반영할 confidence를 곱해준다.
Solution
$$p_u=(Q^TC^uQ+\lambda I)^{-1}Q^TC^uf_u$$
$$q_i=(P^TC^iP+\lambda I)^{-1}P^TC^if_i$$
Confidence 행렬과 preference 벡터를 포함된 해로 표현된다.
역시 해가 deterministic하게 구해져서 한 번에 업데이트할 수 있다.
