BPR, Bayesian Personalized Ranking from Implicit feedback, Rendle

사전에 알아야하는것

1. MF

2. KNN

3. 조건부확률

 

IDEA

단순히 Item의 순위를 매겨서 일괄적으로 추천해주는것보다.

개인화된 Item을 개인별로 추천해주는것이 효과가 더 좋지않을까? 라는 생각에서 출발

 

Data ( Implicit or Explicit )

e.g. 온라인쇼핑

Implicit feedback data : 제품을 검색하고, 상세설명을 확인하는 등등의 '간접적인' 행위

Explicit feedback data : 제품을 구매한 이후에 제품의 평가를 매기는 등등의 '직접적인'행위

⇒ 온라인 쇼핑에서는 Implicit종류의 data가 explicit종류의 data보다 월등히 많기때문에

Implicit data를 사용하는 추천알고리즘을 사용해야함

 

Why not MF, KNN

Implicit Data를 기존 MF, KNN에 사용하지 못하는 이유

1. 개인화 추천 알고리즘에 사용가능한것은 맞으나
2. Ranking을 고려하지않는 방식임

⇒ Bayeisan기반으로 진행하는 추천알고리즘이 BPR 이다.

 

 

BPR : Bayesian Personalized Ranking

BPR-OPT

• 베이지안 추론에 기반한 Optimization 기법
• Ranking기반

LEARNBPR

• BPR-OPT를 최대화 하기 위한 전용 알고리즘

 

Implicit Data

Implicit Data의 주요특징

• Implicit Data는 Positive형으로만 나타남 → Data가 매우 적음…

Implicit Data가 Positive인 이유

• Implicit Data는 일단 ‘유저가 봤거나, 검색했거나, 눌렀거나‘ 하는 Data임 그말인즉슨, 관심이없거나 싫어하는 Data는 missing data라는것임

문제점 :

Data에 대한 User의 반응을 긍정, 무응답, 부정 으로 나눈다면

Implicit Data에서 관측되는 내용은 모두 긍정 이지만 Implicit Data에서 관측되지않는 내용(missing data)은 무응답, 부정이 섞여있음 ⇒ Missing data에서 무응답,부정을 구분할수 있어야함

 

해결방안

Implicit Data에 긍정으로 값이 존재한다 (User가 어떤방식으로든 영향이 있었다.)

→ User가 선택한 Item 값은 긍정이다.

→ 비슷한 Items중에서 User는 해당Item을 더 좋게 판단했으니, 선택했을것이고 그래서 긍정값이 관측되었을것이다.

⇒ 긍정값이없는 Items는 모두 부정이다.

라는 방식으로 긍정값만 존재하는 Implicit Data에서 부정값을 생성함

e.g. Item A, item B, item C중에서 User가 itemB를 보았다 (ItemB의 Implicit feedback이 긍정인 경우)

→ item B가 item A와 item C보다 좋다 ⇒ item B가 긍정이라면, item A와 item C를 부정으로 생각할수 있음

 

기호설명

U : 모든 user의 set I : 모든 item의 set S : implicit feeback (dataset)

 

>u : 유저의 선호도 순위비교

>u ⊂ I^2 : Perosnalized total ranking

 

e.g. Item set이 I1, I2, I3, I4일때, User가 I2, I3, I1, I4순으로 좋아하면

I2 >u I3 >u I1 >u I4 로 표현할수 있는거고

I2 >u I3 이나, I2>u I4는 >u ⊂ I^2 의 사례가되는것

 

∀ : all

∨ : or

∧ : and

 

주요규칙

1속성 : ∀i,j∈I : i≠j⇒I >u j ∨ j>u i  (totality)

i와 j가 서로 다른 Item이면

⇒ User는 i와 j중 둘중 하나를 더 선호한다

 

2속성 : ∀I,j∈I : I >u j ∧ j >u I ⇒ i=j  (antisymmetry)

i를 j보다 더 선호하고 AND j 를 i 보다 더 선호하면

⇒ i와 j는 같은 Item이다

 

3속성 : ∀I,j,k ∈I : i>u j ∧ j >u k ⇒ i>u k  (transitivity)

i를 j보다 더 선호하고 AND j를 k보다 더 선호하면

⇒ i를 k보다 더 선호한다

 

Figure1

User u와 Item의 i의 Matrix

관측된 Implicit data : + → 1

관측안된 Implicit data : ? → 0

User-item Matrix에서 원래는 +의 수치가 서로 다를것임 (e.g. User가 판단했을때 보통/보통이상/좋음/매우좋음... 선호수치가 다를것)

그러나 이를 0과 1의 이진값으로 변환함

문제점

향후 user가 선호할지도 모르는 item이 0으로 표기됨 → 속성123을 기반으로 디테일하게 표현해서 이 문제를 해결하려고함

 

Figure2

User u 와 Item i의 Matrix → User 1명 : Item i의 Matrix

주요가정

(A1) user는 관측된 item을 관측되지 않은 모든 item보다 더 선호한다.

(A2) 관측된 item들에 대해서는 선호강도를 추론할 수 없다.

→ 어떤 item을 더 선호하는지 알 수없음

(A3) 관측되지 않은 item들에 대해서도 선호강도를 추론할 수 없다.

→ 즉 어떤 item을 더 비선호하는지 알 수없음

 

주요전제 : i와 j는 서로다른아이템이고, 기본적으로 j보다 i를 더 선호함

 

 

User1 의 Matrix (User-item matrix)

0 : 속성0에 의해서 서로다른아이템은 호불호가없음

1 : 원래 1행은 ?++?이지만 주대각선에 의해서 없음

2 : 관측된 +

3 : 2의 동치에 의한– (가정A1)

4 : 관측안된 ? (가정A3)

5 : 4의 동치에 의한 ?

6 : i2와 i3은 공통되어 관측된값(가정A2)

7 : i2,i3는 +로 관측이되었지만, i1,i4는 관측되지않은값(상대적으로) - (가정1)

8 : 7의 동치에 의한 +

 

해당방식의 장점

1. 관측되지 않은 Item에도 정보를 매길수있음 + ? ⇒ + - ?
2. 정보를 얻음으로써 Ranking을 매기는데 더 효과적임

 

MAP(사후확률추정. Maximize a Posterior Probablity)

User1~User I 까지의 Matrix를 기반으로 BPR을 구함

→ 이때 사후확률을 최대화 하는 parameter (θ)를 구하기 위함

사후확률 → likelihood * 사전확률의 곱 p(Θ|>u)∝p(>u|Θ) p(Θ)

 

likelihood function

주된가정 : 모든 user는 서로 독립이다 -> iid를 만족한다

likelihood = p^x * (1-p)^(1-x) p : j보다 i를 더 좋아할 확률 x : u,i,j가 Ds에 속할확률

모든 user에 대한 likelihood의 곱 = p^x * (1-p)^(1-x) 의 곱

 

 

BRR-OPT

P(Θ)는 평균이0, 분산이 ΣΘ 인 정규 분포를 따른다. 이때 ΣΘ를 λΘ * I 로 치환함

이유: UnknownParameter를 제거하기위해서 → BPR-OPT

수학적 기호로는

p(Θ) ∼ N(0, ΣΘ) == p(Θ) ∼ N(0, λΘI )

 

LEARN BPR

Ranking문제 → item scoreing ⇒ item 줄세우기

이때 사용하는 score을 Maximize하기위해서 Gradient Descent Based algorithm을 사용

LEARNBPR : bootstrap에 기반한 확률적 경사하강법

*Gradient 종류는 2가지'

Full gradient descent : 전체데이터사용 Stochostic gradient descent : 랜덤하게 추출한 일부데이터를 사용

 

Stochasitc gradient(확률적 경사하강법)

Dataset(관측된 집단과, 관측되지않은 집단 비율의 비대칭성존재) → full gradient로할경우 관측되지않은 집단의 비율이 절대적으로 크기때문에 관측된 집단변수가 모델의 경사도에 매우 큰 영향을 줌 ⇒ stochastic gradient로 할경우 관측된집단,관측되지않은집단의 비율의(데이터비율) 문제가해소될것이라는 판단

 

Gradient

Full Gradient

Stochastic Gradient