[추천시스템] 6. Top-K Recommendation

Rating Prediction

> Explicit feedback의 단점

Latent factor model은 보통 rating prediction 태스크에 집중되었다.

유저의 명시적인 선호도 점수(explicit preference rating)는 user-item 매트릭스로 표현된다.

하지만, 실제 시나리오(real-world scenarios)에서 명시적인 피드백 데이터는 얻기 어렵다는 단점이 있다..

 

때문에 MC를 내재적 피드백 매트릭스로 확장하는 방법에 대한 연구가 이뤄졌다.

내재적 피드백(implicit feedback)의 종류로는 클릭이나 조회 여부가 있고, 메트릭스에서 이진값(0/1) 로 표현된다.

 

이진 메트릭스에 대한 objective function

> 한계점

일반적인 MC의 objective function을 사용하게 되면 모든 unobserved entries (아직 유저의 피드백이 없는 아이템)들은 1로 예측하게 된다.

즉, entry reconsturction을 위한 지도는 내재적인 피드백을 학습하기에 충분하지 않다.

 

이를 해결하기 위해 내재적 피드백에 가중치를 더하는 방안이 제시되었다.

 

 

Implicit Feedback을 위한 Weighted MF

IDEA 1. Observed / Unobserved entries를 분리해서 weighting 하기

Non-negative weight matrix \( W \in \mathbb{R}^{m \times n} \) : Entries들의 신뢰도(confidence)

  - \(W_{ij} = 1 \) 높은 신뢰도 : Observed positive entry (\(R_{ij} = 1 \))

  - \(0 \leq W_{ij}  \leq 1 \) 낮은 신뢰도 : Unobserved negative entry (\(R_{ij} = 0 \))

  - 단점 1 : 이진 메트릭스 \(\Rightarrow\) class 불균형 문제

  - 단점 2 : 유저가 정말 선호하지 않는 것인지 no response 인지 알기 어려움

 

Reconstruction Error 부분에 observed 여부에 따라 가중치를 부여한다.

유저 메트릭스 U와 아이템 메트릭스 V 간의 objective func.

 

IDEA 2 : Unobserved entries를 샘플링하기

Negative entries는 positive에 비해 상당히 많기 때문에 R의 모든 entires에 대해 모델을 학습 시키는 것은 비용이 많이 들고 반드시 필요하지 않다.

그래서 샘플링 확률 메트릭스 \(\hat{P}\)와 negative sample size q를 통해, R에서 negative example sampling을 통해 훈련시킬 데이터를 뽑는다. 

Uniform random samling : 모든 missing 데이터는 동일한 확률로 negative example로 샘플링이 됨

 

User-oriented sampling : 많은 아이템들을 조회한 유저의 경우, 그 유저가 조회하지 않은 아이템은 더 높은 확률로 negative가 된다.

 

Item-oriented sampling : 조회가 적은 아이템은, 아직 그 아이템을 조회하지 않은 유저들도 앞으로 그 아이템을 조회하지 않을 확률이 높을 것이므로 더 높은 확률로 negative가 된다. 

 

 

  - 장점 1 : class imbalance(클래스 불균형) 문제를 해결

  - 장점 2 : 계산적 비용을 감소

 

Pan et al., One-Class Collaborative Filtering, ICDM 2008

Hu et al., Collaborative Filtering for Implicit Feedback Datasets, ICDM 2008

 

 

Top-K Recommendation

Score prediction \( \Rightarrow \) Score Ranking prediction

내재적 피드백의 경우, 정확하게 점수를 예측할 필요가 없다.

대신, 예측한 점수들을 통해 Top-K 아이템 리스트를 사용한다.

 

목표 : 각 유저에 대한 아이템 순위를 예측하기

더 나은 점수 예측(RMSE)이 항상 더 나은 순위를(NDCG) 예측하는 것은 아니다.

Scoring func. \(s: \mathcal{U} \times \mathcal{I} \rightarrow \mathbb{R} \) 을 바로 최적화 해서 순위 리스트를 만든다.

 

 

이 모델은 주어진 유저에 대한 최적의 아이템 순위를 매기기 위한 scoring function을 학습한다.

 

Pointwise Learning : 절대적인 관련성(absolute relevance)를 예측

 

Pairwise Learning : 아이템 쌍에서 어느 아이템의 순위가 더 높은지 예측하여 비교

  - 상대적인 순서를 예측하는 것이 absolute relevance를 예측하는 것보다 nature of ranking에 가깝다.

  - 예시) RankNet, LambdaRank, LambdaMART

 

Listwise Learning : 아이템 리스트의 순위를 예측

  - IR measures에 대한 direct 최적화 (NDCG, SoftRank, AdaRank)

  - ranking의 종류에 따른 고유한 속성의 이해에 기반하여 정의된 손실함수를 최소화 (ListNet, ListMLE)

좌) Pairwise 우) Listwise

---

BPR(Bayesian Personalized Ranking)

Rendle et al., BPR: Bayesian Personalized Ranking from Implicit Feedback, UAI 2009

 

목표 : 유저의 내재적 행동(구매, 클릭...)을 통해 순위를 추론하는 것

즉, 잠재적인 확률을 잘 찾아 분류하는 것이 challenge이다.

Pairwise ranking의 이진 분류를 통해 score function을 최적화한다.

 

Step 1. 훈련 triples (u, i, j)를 생성

Step 2. 유저 u가 아이템 i를 아이템 j 보다 선호한다는 individual probability를 모델링

    logistic regression의 개념을 활용한다.

    Parametric modeling을 위한 가장 일반적인 선택은 MF(matrix factorization)이다. (BPR-MF)

 

 

Triple (u, i, j)의 likelihood :

Triple (u, i, j)의 likelihood

- \( \Theta \) : Gaussian prior 

 

 

최대 posterior estimator :

BPR의 posterior distribution

이 objective는 stochastic gradient aescent를 통해 쉽게 최적화 할 수 있다.

 

(참고) 🔗[이전글] PMF의 Log posterior distribution 

PMF의 Log posterior distribution

 

 

 

BPR과 AUC의 유사성

AUC (Area Under the Curve)   

threshold 에 따른 분류 모델의 성능의 변화를 표현하는 ROC(Reciever Operating Characteristics) 곡선의 아래 영역의 넓이를 구한 값. 0~1 사이의 값을 갖는다. 값이 높을 수록 더 좋은 분류 성능을 의미한다. [1]

 

 

BPR과 AUC의 유사성

유저 u에 대한 AUC

BPR의 objective func.

유저에 따른 AUC는 BPR에서 사용되는 \(D_s\) 로 표현 할 수 있다. 

다만, AUC는 미분불가한 loss δ (x>0) 을 사용하고, BPR은 미분 가능한 loss lnσ(x)를 사용한다.

 

---

CML (Collaborative Metric Learning)

Hsieh et al., Collaborative Metric Learning, WWW 2017

 

MF 같은 Inner product-based scoring은 삼각 부등식(triangle inequality) 을 강제하지 않는다.

삼각 부등식 : 어떠한 삼각형에 대해 임의의 두 변의 합이 나머지 한 변보다 커야 함을 말하는 것. [2]

 

그래서 "x는 y, z 둘 다와 비슷하다." 라는 정보가 주어졌을 때, 학습된 metric은 언급된 두 쌍 (x, y)와 (x, z)를 가까이 놓기만 하는 것이 아니라 남은 쌍 (y, z)도 가까이 놓아야 하는데 MF는 이를 잘 수행하지 못한다.

이 단점을 해결하기 위해 CML이 제안되었다.

metric learning의 label 정보는 pairwise constraint 형태로 지정된다.

 

목표

DML(Distance Metric Learning)은 Mahalanobis distance metric을 학습하는 것을 목표로 한다.

Mahalanobis distance (마할라노비스 거리) : 평균과의 거리가 표준편차의 몇 배인지를 나타내는 값. 어떤 값이 얼마나 일어나기 힘든 값인지를 수치화하는 한 방법.[3]

Preference score : 유저와 아이템 사이의 유클리디안 거리로 정의

Euclidean distance

주어진 observed user-item 쌍의 집합을 통해 gradient를 생성한다.

 

이 그라디언트는...

1. positive 아이템을 유저와 가깝게 끌어놓고

2. 침범하는 가짜 아이템 (intruding imposter items)들을 밀어놓는다.

margin m과 hinge loss를 통해 positive 한 아이템은 margin 안으로, imposter 한 아이템은 margin 밖으로 밀어놓는다.

 

 

 

 

 

[참고자료]

[1] https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nilsine11202&logNo=221893136636 

[머신러닝] ROC curve와 AUC - 분류모델 평가지표

[2] https://ko.wikipedia.org/wiki/%EC%82%BC%EA%B0%81_%EB%B6%80%EB%93%B1%EC%8B%9D

삼각 부등식 - 위키백과, 우리 모두의 백과사전

[3] https://darkpgmr.tistory.com/41

평균, 표준편차, 분산, 그리고 Mahalanobis 거리