Ch 06-4. SGD, ALS로 Matrix Factorization 완벽 이해

Yeonghyeon·2022년 7월 30일
0

Recommender System

목록 보기
16/33

본 포스팅은 Fastcampus 강의를 수강하며 일부 내용을 정리한 글임을 밝힙니다. 보다 자세한 내용은 아래 강의를 통해 확인해주세요.
참고 : Fastcampus 딥러닝을 활용한 추천시스템 구현 올인원 패키지 Online


Ch 06. Model-based Collaborative Filtering


Matrix Factorization

matrix factorziation에 대해 더 deep-down해서 들어가보자

  • RR(원래 rating matrix)와 RR^*(예측 matrix)이 서로 유사하도록 학습하는 과정

    • 관측된 data만 사용
  • (true-rating - predicted rating)으로 근사값으로 추론하는 문제

    • rui^\hat{r_{ui}}(예측된 rating)=XuT×yi=X^T_u\times y_i
  • predicted rating을 이용한 matrix completion 문제

  • (Stochastic) Grandient Descent, Alterning Least Square 등 사용

    • Loss function 최적화를 위해 사용
  • 정보 추가하여 모델링 가능 (또 다른 특징)

    • Explicit과 Impicit feedback을 Matrix Factorization 녹여냄
    • ex) Explicit feedback: 사용자가 이 영화의 평점은 몇 점이다라고 자신의 취향 들어냄
    • ex) Impicit feedback: 꼭 평점을 매기는 것이 아닌 간접적인 신호

Matrix Factorization - Objective Function

min(u,iT)(ruixuTyi)2+λ(xu2+yi2)min \sum_{(u,i∈T)} (r_{ui}-x^T_uy_i)^2 + λ(||x_u||^2+||y_i||^2)

  • (u,iT)(u,i∈T): user, item in Training Set

  • xuTyix^T_uy_i: user와 item latent vector

  • ruir_{ui}: user uu가 item ii에 부여한 실제 rating 값

  • rui^=xuTyi\hat{r_{ui}} = x^T_uy_i: user uu가 item ii에 대해서 줄 예측 rating 값

  • λ(xu2+yi2)λ(||x_u||^2+||y_i||^2): 정규화(regularization)

    • 제한적인 학습데이터에 의존하는 overfitting을 피하기 위한 error term 사용
    • 즉, 대부분 matrix factorization 문제 풀때 dense가 아닌 sparse matrix를 풀기 때문에 error term을 사용하여 관측된 rating에만 집중하지 않고 조금 더 일반적으로(general하게) latent factor를 학습하기 위함
    • 일부러 오차를 부여한 것

Matrix Factorization - Optimization

Objective Function을 어떻게하면 최소화할 수 있을지 ➡️ 최적화 알고리즘 2가지

Stochastic Gradient Descent (경사하강법; SGD)

  • 학습데이터의 모든 rating을 다 훑음
  • Error term
    • 실제 평점과 예측 평점의 차이를 error 항으로 정의
    • eui=ruiXiTyue_{ui}=r_{ui}-X^T_iy_u
  • 현재에서 gradient의 반대 방향으로 xu,yix_u,y_i를 업데이트 (이 과정 속에서 위 최적화 함수를 minimize 하는 것)
    • xuxu+γ(euiyiλxu)x_u←x_u+γ(e_{ui}·y_i - λ·x_u)
    • yiyi+γ(euixuλyi)y_i←y_i+γ(e_{ui}·x_u - λ·y_i)
    • ex) 그 다음 xux_u를 구할 때 이전 값보다 더 작아졌다면 그 방향으로 움직이는 것
  • 구현이 쉽고 계산 빠름

Alternating Least Square(ALS)

  • 일반적으로 xux_uyiy_i를 둘 다 알 수 없는 경우가 더 많이 존재
  • 그렇다면 loss function이 convex하지 않음 ➡️ 최적해 찾기 어렵다!
    • Convex 하다 = 최적해를 좀 더 빠르고 정확하게 찾기 가능

이를 방지하기 위해,

  • xux_uyiy_i 둘 중 하나를 고정하고 식을 quadratic(2차)식으로 변경하여 최적화 문제 풀기 가능
  • xux_uyiy_i를 번갈아 고정시키면서, least-square(최소제곱) 문제 풀게 됨
  • 병렬처리에 용이
    • xux_uyiy_i를 독립적으로 계산(하나는 무시하기에)하기 때문에 병렬화하는데 장점이 있음
  • Implicit feedback 처리에 유용
    • Explication data에 비해 dense하기 때문에 연산량 많아짐 ➡️ 병렬 처리가 더 유리
    • Explication data는 일반적으로 비어있는 sparse data인 경우가 많음 (user가 모든 item에 대해 다 평가를 하지 않기때문)

More on Matrix Factorization

1. Adding Bias

  • bias를 추가함으로써 모델이 현재 데이터에 조금 더 반영할 수 있도록 만들어 줌

  • rui^=xuT×yi\hat{r_{ui}} = x^T_u\times y_i ➡️ buib_{ui}(bias) =μ+bi+bu=μ+b_i+b_u ➡️ rui^=μ+bi+bu+xuTyi\hat{r_{ui}} = μ+b_i+b_u+x^T_uy_i

  • User u와 Item i의 상호관계 파악 (기존 방법): u가 i에 대해 어떻게 생각하는지에 대한 내용만 포함

  • User u와 Item i의 개별 특성을 함께 표현하기 위해 bias term을 추가

min(u,iT)(ruiμbibuxuTyi)2+λ(xu2+yi2+bi2+bu2)min \sum_{(u,i∈T)} (r_{ui}-μ-b_i-b_u-x^T_uy_i)^2 + λ(||x_u||^2+||y_i||^2 + b^2_i+b^2_u)

  • μμ: 모든 item의 평균(e.g. 영화 ➡️ 모든 평점 평균)
  • bi2b^2_i: 전체 item 평균에 대한 item i의 편차 (전체 평균에서 얼만큼 떨어져있는지)
  • bu2b^2_u: 전체 user 평균에 대한 user u의 편차

2. Additional Input Sources

  • Behavior Information(행동 정보) 등 추가 정보를 활용한 모델링 가능
  • iN(u)yi\sum_{i∈N(u)}y_i: User u의 Item i에 대한 implicit feedback
    • N(u)N(u): 전체 Item에 대한 User u의 implicit feedback
  • aA(a)xa\sum_{a∈A(a)}x_a: User u의 personal or non-item related information
    - 성별, 나이, 주소(우편번호) 등
    • 영화(예시)와 전혀 관련없는 정보들도 데이터화해서 넣어줌

rui^=μ+bi+bu+xuT[yi+N(u)0.5aA(a)xa]\hat{r_{ui}} = μ+b_i+b_u+x^T_u[y_i + |N(u)|^{-0.5} \sum_{a∈A(a)}x_a]

3. Temporal Dynamics(시간의 변화)

  • 데이터를 시간의 변화에 따라 동적(dynamic)으로 반영하는 모델링
  • tt: 시간의 변화

rui(t)^=μ+bi(t)+bu(t)+xuTyi(t)\hat{r_{ui}(t)} = μ+b_i(t)+b_u(t)+x^T_uy_i(t)

  • bi(t)b_i(t): Item i의 인기도가 시간의 흐름에 따라 변화하는 경우

    • ex) 영화 타이타닉이 10년 전에는 엄청 인기를 끌었는데, 10년이 흐른 현재는 다른 영화때문에 인기도가 하락하는 것을 반영
  • bu(t)b_u(t): User u가 시간이 흐르면서 baseline rating을 변경한 경우

    • ex) 보통 4점을 줬으나, 최근에는 3점을 주기 시작
  • xuTyi(t)x^T_uy_i(t): 시간이 흐르면서 선호도(취향) 변화

4. Inputs with Varying Confidence Levels

  • 데이터(e.g. 평점)가 동일한 가중치 또는 신뢰도가 아닌 상황을 모델링
  • 대규모 광고에 영향을 받은 item이 자주 선택되는 경우
  • Implicit feedback 데이터에서 user가 실제로 선호하는지 판단하기 어려운 경우에도 적용 가능
    • 몇 번 지속적으로 tv를 시청했는지, 몇 번 구매가 이루어졌는지 등을 바탕으로 실제 데이터(평점)이 정말로 동일한 가중치를 받아야하는지 고려

min(u,iT)cui(ruiμbibuxuTyi)2+λ(xu2+yi2+bi2+bu2)min \sum_{(u,i∈T)} c_{ui}(r_{ui}-μ-b_i-b_u-x^T_uy_i)^2 + λ(||x_u||^2+||y_i||^2 + b^2_i+b^2_u)

  • cuic_{ui}: ruir_{ui}에 대한 신뢰도(또는 가중치)를 부여하여 최적화

Additional Information for Latent Factor Model

  • 결국 Matrix Factorization(=Latent Factor Model)의 중요한 장점 중 하나는, Implicit feedback을 반영할 수 있고 Implicit feedback으로 Additional Information을 얻어 Latent Factor Model을 만듦 ➡️ 콘텐츠기반, 이웃기반 협업필터링에 비해 조금 더 성능 향상 가능

  • Collaborative Filtering for Implicit Feedback Datasets

    • Implicit feedback을 가지고 Collaborative Filtering을 푸는데, 이때 Model-based Collaborative Filtering으로 matrix factorzation을 적용하면서 ALS 사용하는 것까지 논문에서 소개
      1. 실제 상황에서는 implicit feedback 데이터를 활용해야 하는 경우가 더 많음
      1. Implicit feedback을 활용하는 latent factor model과 그에 대한 학습 방법 제시하는 논문

Appendix

  • Yifan Hu, et al. Collaborative Filtering for Implicit Feedback Datasets
  • Korean, Y,m et al. (2009). Matrix factorization techniques for recommender systems. Computer, 42(8), 30-37

0개의 댓글