[논문 리뷰] BPR : bayesian personalized ranking from implicit feedback

논문 : https://arxiv.org/abs/1205.2618

오역, 오류 등은 댓글로 말씀 부탁드립니다!

---

문제 상황

• 상품 추천 : 선호도 기반 사용자 맞춤형 ranking 계산
  • 선호도 : 과거 구매 기록 및 열람 기록을 통해 계산
• 현업에서 대부분의 feedback은 implicit feedback
  • implicit feedback : 클릭 및 조회 등
    
    • 수집 쉬움
  • explicit feedback : 평점
• 목적 : 사용자 맞춤형 순위 학습 모델을 위한 일반적인 방법 제시

이전 연구

• collaborative model
  • KNN - CF : 가장 유명한 모델
    • 휴리스틱하게 유사도 계산
    • 최근에는 유사도 matrix를 모델 파라미터로 사용하여 task에 맞게 학습시켰다
  • SVD : feature 학습에 사용
    • MF에 사용 시 overfitting 문제 발생
      • 정규화를 통해 overfitting 해결
        1. WR-MF : negative의 영향력을 줄이기 위해 case weight 사용
        2. probabilistic latent semantic model
        3. 다중 분류로 문제를 변경하여 이진 분류 모델 사용
      • 모델 파라미터를 순위에 맞게 최적화시키지 않고, 아이템 선택 여부를 예측하는데 최적화
  • 논문에서는 MF와 KNN의 학습 방법을 변경함으로써 성능을 높이기 위함
    • 오프라인 학습을 통해 파라미터 계산
    • 온라인 학습 방법 적용 가능
• non collaborative model : 개인화된 순위X
  • 경사하강법을 이용한 신경망 모델
  • permutation 분포를 모델링
• 개인화하지 않은 경우보다 개인화한 경우의 성능이 높다

Personalized Ranking

= item recommendation

• 암묵적 feedback : positive만 관측 가능
  • 미관측된 경우
    • negative
    • 모르는 경우

Analysis of the problem setting

negative data를 0으로 filling

• 미관측치를 무시할 경우 : 학습 데이터에 활용 불가
• 기존의 item recommendation
  • 과정
    1. 각 item에 대해 개인화된 점수 예측
       • 점수 : item에 대한 사용자의 선호도
    2. 점수 기반 정렬
    3. 모델링
  • 학습 데이터
    • postivie class label에 해당하는 user-item 쌍
    • 미관측값은 전부 negative
  • 문제
    • 모델이 순위를 계산해야하는 모든 요소 : negative로 학습된다
      • 충분한 표현력을 가진 모델은 0만 예측한다(=순위를 계산하지 못한다)
      • 모델이 순위를 예측할 수 있는 이유는 overfitting 방지 방법 때문

Desing matrix

• 미관측 item을 학습 데이터로 사용하기 위해 논문에서 제시한 방법 
• item 쌍을 학습 data로 사용 → item 쌍의 순위에 최적화
  • 개별 item을 학습 data로 사용하지 않음
  • item 쌍 간 사용자 맞춤 pairwise 선호도 생성
• 가정 : 관측 item 선호도 > 미관측 item 선호도
  • 둘다 관측 item인 경우 파악 불가능
  • 둘다 미관측 item인 경우 평가 data
    • 추후 순위를 계산해야함
    • → 학습 및 평가 data는 disjoint
• 장점
  • 학습 데이터에는 긍정-부정 item쌍과 미관측값이 모두 포함된다
  • 학습 데이터가 실제 목적(순위)에 맞게 생성
• 미관측치를 negative로 변경하여 학습하는 것보다 높은 성능을 보인다

BPR : byesian personalized ranking

배경 지식

• prior probability : 사전 정보 없이 알 수 있는 확률
• posterior probabiliy : 사전 정보가 있어야 알 수 있는 확률. 사후확률
• totality : 전체성
  • R이 특정 관계일 때, aRb 혹은 bRa가 성립하는 것
  • e.g : R이 ≥ 라면 1R2은 전체성을 가진다
• antisymmetry : 비대칭성
  • R이 특정 관계일 때, aRb과 bRa가 성립하면 a와 b는 같은 요소이다
  • e.g : R이 ≥ 라면 aRb와 bRa 성립 시 a=b이다
• transitivity : 전이성
  • R의 연속성과 일관성
  • R이 특정 관계일 때, aRb와 bRc 성립 시, aRc도 성립한다
• MAP : Maximun A posteriori Estimation. 최대 사후 확률 추정
  • posterior를 최대로 하는 $ \theta $
• MLE : Maximun likelihood Estimator
• traverse data : data의 모든 요소가 방문

BPR optimization criterion

• 가정
  • 사용자 간 행동은 독립적
  • 특정 사용자에 대한 각 item쌍 정렬은 독립적
• 사용자 맞춤형 순위 : posterior probability $ P(\theta | >_u) $를 최대화함(MAP)으로써 정확성을 높임
  • $\theta$ : 임의의 모델 class의 파라미터 벡터
  • $ >_u $ : 사용자 u에 대한 latent preference structure
• $ P(\theta | >_u) $ : 사용자 맞춤형 likelihood 함수
  • 개별 밀도 간의 product로 이해할 수 있다
  • 모든 사용자에 대해 combine할 수 있다
  • 개인화된 전체 순위가 되기 위해선 totality, antisymmetry, transitivity가 있어야 한다
    • 이를 위해 사용자가 j보다 i를 선호할 확률을 아래와 같이 정의한다
    • $ P(\theta | >u) := $ $ \sigma(\hat x{uij}(\theta)) $
    • $ \sigma $ : 로지스틱 시그모이드
    • $ \hat x_{uij}(\theta) $ : $ \theta $ 에 대한 임의의 실제 값 함수
    • $ \theta $ : 사용자 u, 아이템 i와 j 간의 관계 capute
• $ P(\theta) $ : 사전확률
  • 평균이 0이고 분산이 $ \sum_ \theta $인 정규분포를 따른다
• $ \sum_ \theta = \lambda_\theta I $ : 모르는 하이퍼 파라미터 개수를 줄이기 위해 설정
  • 이로 인해 개인화된 순위를 최적화하는 MAP 추정치를 공식화할 수 있음
  • $ \lambda_\theta $ : 정규화 파라미터
• 특징
  • 프레임워크가 u, i, j 간 관계를 모델링하지 않는다
    • 모델링은 MF, KNN 등이 $ \hat x_{uij}(\theta) $ 을 추정하며 수행
  • 대신 사용자 맞춤형 전체 순서 모델링
• Analogies to AUC optimization
  • AUC(u)와 BPR 간 차이 : 손실함수
    • AUC(u) : $ \delta $ 사용
      • H(x)와 동일
      • 고정됨
    • BPR : $ ln \sigma (x) $ 사용
      • 가변적
      • MLE로 추정
      • AUC 최적화 시 H(x) 대신 자주 사용
      • H(x) 대신 사용할 함수 : 휴리스틱하게 설정
        • $ \sigma (x) $ 주로 사용

BPR Learning Algorithm

• BPR 최대화를 위해 경사하강법 기반 알고리즘 사용
  • 기본형은 부적합
  • 붓스트랩 샘플링 기반 SGD, 즉 LearnBPR 사용

• LearnBPR 과정 
  • $ \theta $ 초기화
  • $ \theta $ 업데이트 : 수렴할 때까지
  • $ \theta $ return
• $ \frac{\partial BPR-Opt}{\partial \theta} $ : 모든 BPR-Opt의 기울기에 대한 파라미터
• 경사하강법
  • full algorithm : 각 단계에서 전체 기울기를 계산하고 파라미터를 업데이트한다
    • 일반적으로 느리게 수렴된다
    • BPR에 적용 시 학습쌍 간의 편향성으로 인해 수렴이 어렵다
      • 편향성 : positive item i에 의존하는 파라미터의 경사가 커진다 = 아주 작은 학습률이 필요하다
    • 기울기가 다양하기 때문에 정규화 어려움
  • SGD : 일반적으로 편향성 문제 해결
    • 단, 학습쌍 탐색 순서가 중요하다
    • 일반적으로 item wise, user wise로 탐색 : 수렴이 어렵다
      • 같은 u, i 쌍에 대해 연속적으로 업데이트되기 때문
  • u, i, j를 동일 확률 & 무작위로 선택하는 SGD
    • 연속적인 업데이트 과정에서 같은 u, i 쌍이 선택될 가능성이 낮아짐
    • 어느 단계에서든 중단하기 위해 붓스트랩 복원 추출
      • 예시가 많고 full cycle의 일부만으로도 수렴 가능
      • 관측된 positive feedack 개수에 따라 단계 수 선택
    • LearnBPR : user-wise SGD보다 빠르게 수렴된다

Learning models with BPR

• MF, KNN : 사용자의 숨겨진 선호 모델링
  • MF, KNN 외에도 $ \hat x_{ui} $를 예측하는 모든 collaborative filtering 적용 가능
  • $ \hat x_{ui} $ 예측 : X matix를 추정하는 task
    • $ \hat X := W H^t $
    • W의 각 행 : 사용자 u에 대한 feature 벡터
    • H의 각 행 : 아이템 i에 대한 feature 벡터
  • ranking task에 맞게 최적화하는 것이 중요
    • ranking task : 개별 값을 예측하는 것이 아니라 예측값 간의 차이를 분류하는 task
• Matrix Factorization
  • 파라미터 $ \theta $ : (W, H)
    • 미관측 사용자 및 아이템의 특성을 모델링하는 잠재 변수로 해석 가능
  • 가장 좋은 X 추정 방법 : 최소제곱법
    • SVD의 성능이 높지만, overfitting으로 MF를 사용한다
    • MF : 정규화된 최소제곱을 최적화, non negative Factorization, 최대 마진 Factorization 등
  • LearnBPR로 BRP-Opt에 맞게 최적화 시 더 좋은 성능
    • 정규화 방법
      1. $ \lambda_w $ : 사용자 feature w에 대한 정규화 상수
      2. $ \lambda_{H+} $ : 아이템에 대한 positive 업데이트
      3. $ \lambda_{H-} $ : 아이템에 대한 negative 업데이트
• Adaptive K-Nearest-Neighbor
  • item 간 or user 간 유사도 측정 기반
    • item / user 성능은 비슷하다
  • user u와 item i에 대한 예측 : 사용자가 과거에 본 다른 item과 i 간의 유사도에 기반
    • 아이템 간 유사도를 기반으로 사용자가 과거에 본 모든 item과 i 비교 가능
  • 파라미터 $ \theta $ : C
    • C : 아이템 간 상관관계 or 유사도 matrix
    • 코사인 유사도 등 휴리스틱한 방법으로 C 선택
      • 학습을 이용할 경우 성능 개선
        1. C를 바로 파라미터로 사용 : 논문에서 사용
        2. 아이템이 너무 많을 경우 $ HH^t $ factorization 학습
  • LearnBPR로 BRP-Opt에 맞게 최적화
    • 정규화 상수
      1. $ \lambda_{H+} : C_{il} $ 업데이트
      2. $ \lambda_{H-} $ : $ C_{jl} $ 업데이트

Relations to other methods

Weighted Regularized Matrix Factorization(WR-MF)

• BPR과의 차이 : 최적화 및 학습 방법
  • WR-MF : SVD를 이용하며 잔차 제곱을 최소화하는 방식으로 최적화
• extension : overfitting 방지를 위한 정규화
• 손실 함수의 가중치 : postivie feedback의 영향을 줄이기 위함
• 이전 연구 : $ c_{ui} $는 모델 파라미터가 아닌 (u, i)에 대한 가중치
  • positive feedback에 대한 $ c_{ui} $ 추정을 위한 추가적인 data 사용
    • postivie feedback이 아닌 경우에 대해서는 $ c_{ui} =1 $로 설정
  • positive feedback에 대해 $ c_{ui} =1 $로 설정하고 나머지는 낮은 상수로 설정
• 이전의 최적화 방식
  • 인스턴스(1개의 item) 수준에서 최적화
    • BPR : 2개 item, 즉 쌍 수준에서 최적화
  • 정규 분포를 따르는 랜덤 변수에 MLE 적용하여 최소 제곱 적용
    • item 예측 task는 분류 task이므로 로지스틱이 더 적합
• 장점 : positive가 아닌 경우에 대해 $ c_{ui} $가 상수이므로 학습 가능
• LearnBPR : u, i, j쌍이 남아있더라도 $ m |s| $ 업데이트 단계의 subsample 이후 수렴

Maximun Margin Matrix Factorization(MMMF)

• 순위에 대한 명시적 feedback이 있는 경우에 사용
• 미관측 item의 평점을 0으로, 관측 item의 평점을 1로 매핑하여 암묵적 feedback에 적용 가능
  • 매핑 시 최적화 기준을 최소화할 경우, MF에 적용되는 BPR과 유사하다
  • 단, 손실함수가 다르다
    • BPR : 힌지손실 사용
      • smooth
      • MLE로 유도
      • 다양한 모델에 적용 가능
    • MMMF : MF에만 적용 가능
  • 학습 방법의 차이
    • MMMF : 명시적 feedback의 sparse data 사용
      • 암묵적 feedback보다 item쌍이 적다
      • 암묵적 feedback에 적용 시 밀집되어야 함
      • 학습쌍의 개수 $ D_s = O(|s| |I|) $
    • BPR : 밀집도 문제 해결

Experiment

• 비교 대상
  • MF
    • 학습 방법
      1. SVD - MF
      2. WR - MF
      3. BPR - MF
  • KNN
    • BPR로 최적화한 경우와 그렇지 않은 경우 간의 코사인 유사도 비교
  • baseline : 각 item와 user의 가중치가 독립적이다
  • 개인화되지 않은 방법 적용 시의 AUC
• Data
  • 거래 데이터
    • 사용자별 다음에 구매할 item 예측
    • 암묵적 feedback만 사용하기 위해 평점 미사용
  • 영상 시청 데이터
    • 한 사용자에 대해 무작위로 하나의 action 삭제 : 이를 통해 학습, 평가 data 간 disjoint
• Setting
  • 평균 AUC로 평가
  • 하이퍼 파라미터 : 첫 번째 학습 시 grid search로 튜닝
    • 이후 학습 과정에서 고정
• 결과
  • 예측 모델이 같더라도 BPR로 최적화한 경우 성능이 높다
  • SVD-MF : overfitting 으로 인해 차원이 높아질수록 성능이 낮아진다
  • WR-MF : 정규화로 인해 차원이 높아질수록 성능이 높아진다
    • 단 BPR - MF보다는 성능이 낮다
  • 간단한 개인화 추천 방식의 성능 > 개인화되지 않은 추천 방식의 성능

Conclusion

• 일반적인 최적화 방법 BPR-Opt 제시
  • 베이지안 기반 MAP estimator
• 개인화된 순위를 위한 학습 알고리즘 LearnBPR 제시
  • 붓스트랩 샘플링에 기반한 SGD
• 예측 성능 : 모델 뿐만 아니라 최적화 방법에도 영향을 받는다