[RecSys] MF : Matrix Facotrization

mincheol2·2022년 3월 12일
0

RecSys

목록 보기
11/23

이 글은 부스트캠프 AI Tech 3기 강의를 듣고 정리한 글입니다.

요약

  • Model-based CF의 뿌리 개념이 되는 SVD를 알아보고
  • SVD의 한계에 따른 MF의 등장과 한스텝씩 고도화 시킨다.
  • MF 모델의 학습에서 사용하는 optimizer SGD, ALS를 알아보고
  • Implicit Feedback에 MF를 수식적으로 적용해 본다.(그동안은 Explicit Feedback에 대한 모델을 정리)

SVD

SVD는 선형대수학에서 차원축소 기법으로 쓰이는 것으로 추천시스템에서는 Rating Matrix에 대해 유저와 아이템의 잠재요인을 포함할 수 있는 행렬로 분해한다.

SVD 종류와 방법
대표값을 모두 사용
Full SVD : R=UVTR = U\sum V^T

대표값으로 사용될 K개의 특이치만 사용하여 가장 중요한 정보로 요약
Truncated SVD : RU^VT^=RR \approx \hat U\sum \hat{V^T} = R

  • 유저의 Latent Factor 행렬 UU : 각 열벡터는 R의 left singular vector
  • 아이템 잠재 요인 행렬 VV : 각 열벡터는 R의 right singular vector
  • 잠재요인 대각 행렬 \sum : RRTRR^T을 고유값 분해해서 얻은 직사각 대각행렬로 R의 singular value로 구성됨 Latent Factor의 중요도


SVD의 한계
분해(Decomposition)하려는 행렬의 정보가 불완전할 때 정의되지 않음

  • 실제 데이터는 Sparsity가 높기 때문에 어려움

따라서 결측치를 모두 채워 형식상 Dense Matrix를 만들어 SVD 수행
(결측치 0으로 대체 or 평균값으로 대체)

  • 이러한 결측치 대체는 데이터의 양을 상당히 증가시키기 때문에 cost 증가

이러한 Null값 대체는 정확하지 않기 때문에 데이터를 왜곡시키고 예측 성능을 떨어뜨림

MF

SVD의 한계점을 해결하기 위해 SVD의 원리는 차용하되 다른 접근이 필요했다.
그때 등장한 개념이 MF(Matrix Factorization)이다.

MF는 User-item Matrix를 저차원의 User와 Item의 Latent Factor 행렬의 곱으로 분해하는 방법이다. SVD와 개념이 유사하지만, 관측된 평점만 모델링에 사용 하고 관측되지 않은 평점을 예측하는 일반적인 모델을 만드는 것이 목표이다.

수식으로 보면 다음과 같다.

RP QT=R^R \approx P \ Q^T = \hat R

즉 Rating Matrix 를 P와 Q로 분해하여 R과 최대한 유사한 R^\hat R을 추론 하는 것이다.

기본 MF 모델

MF는 RRR^\hat R이 최대한 유사하도록 모델을 학습하는 과정으로
먼저 RRR^\hat R 그리고 유저의 Latent Matrix PP, 아이템의 Latent Matrix UU 를 정의한다.

RP×QT=R^R \approx P \times Q^{T}=\hat{R}

  • PU×kP \rightarrow|U| \times k : 유저수 x K(Latent Feature 수)
  • QI×kQ \rightarrow|I| \times k : 아이템수 x K(Latent Feature 수)

그리고 Objective Function을 정의하고 정의한 RRR^\hat R을 이용해서 최적화 문제를 푸는것이다.

ObjectiveFunction:minP,Qobserved ru,i(ru,ipuTqi)2Objective Function : \min _{P, Q} \sum_{\text {observed } r_{u, i}} \left(r_{u, i}-p_{u}^{T} q_{i}\right)^{2}

  • true rating: ru,i\text{true rating: } r_{u, i}

  • predicted rating : r^u,i=puTqi\text {predicted rating : } \hat r_{u, i} = p_u^Tq_i

여기에서 λ\lambda배 한 penalty term(L2-정규화)를 추가하여 최종 Objective Function을 정의 한다.

minP,Qobserved ru,i(ru,ipuTqi)2+λ(pu22+qi22)\min _{P, Q} \sum_{\text {observed }} r_{u, i}\left(r_{u, i}-p_{u}^{T} q_{i}\right)^{2}+\lambda\left(\left\|p_{u}\right\|_{2}^{2}+\left\|q_{i}\right\|_{2}^{2}\right)
  • L2-Norm 항인 λ(pu22+qi22)\lambda\left(\left\|p_{u}\right\|_{2}^{2}+\left\|q_{i}\right\|_{2}^{2}\right)는 weight가 너무 커지지 않도록 제한을 하여 overfitting을 방지해준다. 이때 λ\lambda가 너무 크면 weight가 제대로 변하지 않아 underfitting이 일어나게 된다.

MF에서 중요한 점은 실제 관측된 데이터만 사용한다는 점이다.(SVD는 결측치를 채우고 행렬분해)


이제 학습이 어떤 방식으로 진행되는지 알아보자.
기본 MF의 학습은 SGD(확률적 경사 하강법)으로 진행된다.

Loss:L=(ru,ipuTqi)2+λ(pu22+qi22)Loss: L=\sum\left(r_{u, i}-p_{u}^{T} q_{i}\right)^{2}+\lambda\left(\left\|p_{u}\right\|_{2}^{2}+\left\|q_{i}\right\|_{2}^{2}\right) \quad

로 정의된 Loss식을 각각 pup_uqiq_i로 미분을 하여 Gradient 를 구한다.

이때 Error를 다음과 같이 정의해두자.

Error:eui=ruipuTqiError: e_{u i}=r_{u i}-p_{u}^{T} q_{i}

Loss식을 pup_u로 미분하고 Error로 정리를 하면 다음과 같은 식이 나온다.

Gradient: Lpu=(ruipuTqi)2pu+λpu22pu=2(ruipuTqi)qi+2λpu=2(euiqiλpu)\frac{\partial L}{\partial p_{u}}=\frac{\partial\left(r_{u i}-p_{u}^{T} q_{i}\right)^{2}}{\partial p_{u}}+\frac{\partial \lambda\left\|p_{u}\right\|_{2}^{2}}{\partial p_{u}}=-2\left(r_{u i}-p_{u}^{T} q_{i}\right) q_{i}+2 \lambda p_{u}=-2\left(e_{u i} q_{i}-\lambda p_{u}\right)


이제 Gradient의 반대방향으로 pu,qip_{u}, q_{i} 를 업데이트 진행하여 학습시킨다.

pupu+η(euiqiλpu)p_{u} \leftarrow p_{u}+\eta \cdot\left(e_{u i} q_{i}-\lambda p_{u}\right)
qiqi+η(euipuλqi)q_{i} \leftarrow q_{i}+\eta \cdot\left(e_{u i} p_{u}-\lambda q_{i}\right)
  • η\eta 는 learning rate



MF + α\alpha

이 부분은 MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEMS 논문을 설명하는 파트이다.

자세한 내용은 MF논문리뷰를 참조하도록 하자.

여기서는 간단히 기본 MF에서 어떤 것을 추가하였는지 간단히 알아보겠다.

  • bias 추가
    : 전체 평균(global bglobal \ b) , 유저 편향(bib_i) , 아이템 편향(bib_i) 를 추가하여 예측 성능을 높임

  • confidence level 추가 (Implicit feedback에서 사용)
    : 모든 평점이 동일한 신뢰도를 갖지 않기 때문에 ruir_{ui}에 대한 신뢰도를 의미하는 cuic_{ui}추가
    특정 아이템이 많이 노출되어 클릭되는 경우, 평점이 정확하지 않은 경우 생기는 신뢰도 문제 해결

  • 시간 변화(Temporal Dynamics) 추가
    : 학습파라미터가 시간을 반영하도록 모델을 설계
    시간에 따라 유저,아이템의 특성이 변할 수 있음

MF for Implicit Feedback

ALS (Alternative Least Square)

ALS는 Loss식을 Update하기 위한 방법으로 SGD 대신 사용하게 된다.


유저와 아이템 매트릭스를 번갈아가면서 업데이트하게 되는데,
pup_u, qiq_i 두 매트릭스 중 하나를 상수로 고정해 놓고 나머지 매트릭스를 업데이트한다.
(least-square문제 푸는 것)

이때 초기 고정은 랜덤하게 진행되며 학습을 통해 최적해에 수렴하게 된다.

ALS는 대용량 데이터를 병렬처리하여 SGD보다 빠르게 학습이 가능하고, Sparse한 데이터에 대해 더 Robust한 특성이 있다.

ALS는 Loss식을 P,Q 번갈아 가면서 업데이트한다.

minP,Qobserved ru,i(ru,ipuTqi)2+λ(pu22+qi22)\min _{P, Q} \sum_{\text {observed }} r_{u, i}\left(r_{u, i}-p_{u}^{T} q_{i}\right)^{2}+\lambda\left(\left\|p_{u}\right\|_{2}^{2}+\left\|q_{i}\right\|_{2}^{2}\right)
pu=(QTQ+λI)1QTruqi=(PTP+λI)1PTri\begin{aligned} &p_{u}=\left(Q^{T} Q+\lambda I\right)^{-1} Q^{T} r_{u} \\ &q_{i}=\left(P^{T} P+\lambda I\right)^{-1} P^{T} r_{i} \end{aligned}

※ 업데이트 하는 식을 보면 역행렬term (QTQ+λI)1(Q^{T} Q + \lambda I)^{-1}) 과 QTruQ^{T} r_{u}은 같은 차원을 공유하고 있기 때문에 역행렬을 직접 구하는 것 대신 연립방정식을 푸는 방식으로 연산량을 줄일 수 있다.


Implicit Feedback 적용

Implicit Feedback 은 불완전한 선호도를 나타내기 때문에 Preference, confidence로 나누어 MF 모델에 넣게 된다.


Preference: 유저u 가 아이템i 를 선호하는지 여부를 binary로 표현

fui={1rui>00rui=0f_{u i}= \begin{cases}1 & r_{u i}>0 \\ 0 & r_{u i}=0\end{cases}

Confidence : 유저u 가 아이템 i 를 선호하는 정도를 나타내는 Increasing function

cui=1+αruic_{u i}=1+\alpha \cdot r_{u i}
  • α\alpha 는 positive feedback과 negative feedback 간의 상대적인 중요도를 조정하는 하이퍼 파라미터

새로운 목적함수 :Rating 대신 Preference와 Confidence를 적용

minP,Qobserved fu,i(cu,i(fu,i)puTqi)2+λ(upu22+iqi22)\min _{P, Q} \sum_{\text {observed } f_{u, i}}\left(c_{u, i}\left(f_{u, i}\right)-p_{u}^{T} q_{i}\right)^{2}+\lambda\left(\sum_{u}\left\|p_{u}\right\|_{2}^{2}+\sum_{i}\left\|q_{i}\right\|_{2}^{2}\right)
pu=(QTCuQ+λI)1QTCuruqi=(PTCiP+λI)1PTCiri\begin{aligned} &p_{u}=\left(Q^{T}C^u Q+\lambda I\right)^{-1} Q^{T} C^ur_{u} \\ &q_{i}=\left(P^{T}C^i P+\lambda I\right)^{-1} P^{T} C^ir_{i} \end{aligned}

※ SGD, ALS 모두 동일하게 사용 가능하다.

profile
옹오옹오오오옹ㅇㅇ

0개의 댓글