Machine learning 스터디 (17-1) Recommendation System with Implicit Feedback

March 6, 2016

들어가며

이전 글[1]에서 다룬 recommendation system은 사용자가 점수를 정확하게 매긴 경우에 대해, 즉 explicit feedback에 대해서만 문제를 푸는 방식이다. 그러나 실제로는 사용자가 점수를 직접 매기는 대신에 단순히 클릭했거나, 조회, 구매한 간접적인 정보, 즉 implicit feedback에만 의존하게 되는 경우도 빈번하게 발생하게 된다. 이 글에서는 그런 implicit feedback만 존재하는 상황에서 어떻게 matrix completion 문제를 디자인하고 해결하는지에 대해 총 세 개의 논문을 들어 설명할 것이다.

이 글의 맨 앞은 implicit feedback이 정확히 무엇이고, 어떤 상황의 문제들이 있는지에 대해 설명할 것이다. 그리고 총 세 개의 논문에서 어떤 방법으로 문제를 접근하는가 설명하도록 할 것이다. 소개할 논문은 Collaborative Filtering for Implicit Feedback Datasets [2], Logistic Matrix Factorization for Implicit Feedback Data [3], Bayesian Personalized Ranking for Non-Uniformly Sampled Items [4] 총 세가지이다.

Explicit Feedback and Implicit Feedback

본격적으로 논문들이 제안한 방법론을 살펴보기 전에, explicit feedback과 implicit feedback의 차이점에 대해 논해보도록 하겠다. 먼저 explicit feedback은 사용자가 정확하게 본인이 얼마나 이 item에 호감이 있는지를 수치로 feedback을 주는 것이다. 예를 들어서 Netflix problem의 별점 데이터는 정확하게 1점부터 5점 사이의 well-define된 범위를 가진다. 그러나 실제로는 사용자의 item에 대한 정확한 호감도를 요구하는 것이 어려울 때가 있다. 아마존의 상품 추천을 예로 들어보자. 아마존이 가질 수 있는 데이터는 사용자가 어떤 상품들을 조회하였는지와, 어떤 상품들을 구매하였는지 정도의 정보 밖에 가질 수 없다. 이 경우 사용자가 살펴본 물건들이 사용자가 정말 매력있게 느껴서 살펴본 것인지, 만약 그렇다면 얼마만큼의 호감도가 있는지 판별하는 것이 매우 어려울 것이다. 이런 종류의 데이터를 사용자가 직접적인 점수를 주는 대신 간접적인 정보만을 제공한다고 하여 implicit feedback이라 부른다. 이외에도 sound cloud나 youTube 등에서 사용자가 재생한 재생목록이나 반복하여 청취 혹은 시청한 횟수 등의 데이터도 마찬가지로 implicit feedback의 대표적인 예가 될 수 있다.

Implicit feedback에서 관측 값은 click이나 재생 횟수 (0 혹은 0보다 큰 정수) 일 수도 있고, 음악 등의 item을 재생한 총 시간 (0 이상의 실수) 일 수도 있다. 한 가지 주의할 점은, explicit feedback처럼 사용자가 구체적으로 item에 대한 preference를 제공하지 않기 떄문에 사용자가 선호하지 않아서 선택하지 않은 item과 아직 관측하지 않은, 그러나 잠재적으로 흥미가 있는 item 모두 값이 0일 것이라는 점이다. 보통 사용자들이 item을 굉장히 조금만 click하거나 (뉴스) 사용하거나 (음악, 동영상) 구매하기 때문에 (쇼핑) 실제로는 matrix의 거의 대부분이 비어있고 아주 일부분의 데이터만 관측되기 때문에, negative observation이 positive observation의 수를 압도한게 되고, 때문에 이런 점을 고려하지 않고 모델을 설계하게 되면 아주 일부분의 positive 데이터와 거의 대부분의 negative observation (값이 0인 observation)들에의해 model이 overfitting된다. 또한, implicit feedback은 굉장히 노이즈가 많기 때문에 주어진 데이터를 얼마나 믿을 수 있을지 알 수 없다는 것이다. 예를 들어서 사용자가 물건을 하나 구매하였더라도, 이 물건에 대해 반드시 긍정적으로 생각할 것이라 기대할 수는 없을 것이다. 가끔은 구매한 물건이 아주 불만족스럽고 다시는 비슷한 물건을 구매하고 싶지 않을 수도 있지 않은가? 이런 두 가지 이슈 (negative observation, confidence)는 recommendation model이 implicit feedback을 처리하기 위해 반드시 고려되어야 할 이슈가 된다.

Recall: Matrix Factorization with Explicit Feedback

이전 글 [1]에서 다뤘던 objective function은 다음과 같다.

$min_{X, Y} \sum_{u, i \in κ} (r_{u i} - x_{u}^{⊤} y_{i})^{2} + λ (‖ x_{u} ‖_{2}^{2} + ‖ y_{i} ‖_{2}^{2}) .$

이전 글에서는 x,y 대신 p,q noataion을 사용했으나 이 글에서는 전부 x, y notation으로 통일하도록 하겠다. 이 objective에 대해서는 이전 글을 참고하면서 읽으면 좋을 것 같다. 원래는 bias term까지 포함해야하지만, 이 글에서는 편의상 bias term은 생략하도록 하겠다. 이 문제는 SGD (Stochastic Gradient Descent), ALS (Alternating Least Square) 등의 solver를 사용해 풀 수 있으며 이 글에서는 자세한 설명을 생략하도록 하겠다.

Collaborative Filtering for Implicit Feedback Datasets [2]

Implicit feedback을 처리하는 가장 기본적인 접근법을 소개해보자. 이 논문은 user u가 item i를 선호하는지 하지 않는지 여부를 가르키는 preference vector $p_{u i}$ 를 정의한다. $p_{u i}$ 의 값은 $s i g n (r_{u i})$ 으로 정의할 수 있다. sign 함수는 input 값의 'sign'을 return하는 함수로, 즉 input이 negative value면 -1, positive value면 1을 return한다. 따라서 perference의 값은 rating r이 0보다 크다면 1이고, r이 0이라면 p도 0이 되는 것이다.

앞서 설명한 것 처럼, preference vector의 값을 항상 신뢰할 수 있는 것은 아니다. 때문에, 이 논문에서는 confience level $c_{u i}$ 라는 것을 정의하게 된다. 우리가 한 가지 가정할 수 있는 것은 만약 $r_{u i}$ 의 값이 크다면, 예를 들어 한 사용자가 한 항목을 엄청 많이 재구매했다거나 한다면, u는 i를 아주 높은 확률로 prefer한다는 사실을 가정할 수 있다. 따라서 confidence level은 r에 대한 increasing function으로 정의하는 것이 타당하다고 할 수 있다. 이 논문에서는 confidence level $c_{u i}$ 를 다양한 방식으로 정의할 수 있다고 언급하고 있으며, 실제 실험에서는 가장 직관적이고 단순한 increasing function은 linear function을 사용한다. 따라서 이 논문에서는 다음과 같은 confidence를 사용한다.

$c_{u i} = 1 + α r_{u i} .$

혹은 $c_{u i} = 1 + α \log (1 + r_{u i} / ε)$ 등의 confidence도 대안으로 제안하기는 하지만, 기본적으로 위에서 설명한 linear confidence를 사용하는 듯하다. 한 가지 짚고 넘어가야할 점은, $c_{u i}$ 는 실제 데이터 $r_{u i}$ 와 hyper-parameter $α$ 에 의해서만 정의되므로 optimize해야 할 parameter가 아니라 한 번 confidence를 정의하기만하면 고정되는 constant라는 점이다. 따라서 confidence의 값을 어떻게 정의하더라도 전체 알고리즘의 로직을 바꾸거나 하지는 않는다.

c를 정의하는 것에는 또 하나의 이점이 있다. Parameter $α$ 가 positive observation과 negative observation의 중요도를 조절하는 역할을 하게 되면서, negative feedback에 대한 중요도를 조절할 수 있는 것이다. 예를 들어 $α$ 의 크기가 작다면, positive와 negative observation의 confidence 차이가 큰 $α$ 를 가질 때 보다 상대적으로 작을 것이라는 것을 기대할 수 있게 된다.

이제 objective를 정의할 차례이다. Explicit feedback에서는 복원한 rating ${\hat{r}}_{u i}$ 와 관측한 데이터 $r_{u i}$ 의 RMSE를 바로 계산하였으나, 앞서 말한대로 이 값을 그대로 계산하기에는 confidence의 문제가 있다. 이 논문에서는 앞서 정의한 confidence를 고려하여 objective function은 다음과 같이 정의한다.

$min_{X, Y} \sum_{u, i \in κ} c_{u i} (p_{u i} - x_{u}^{⊤} y_{i})^{2} + λ (‖ x_{u} ‖_{2}^{2} + ‖ y_{i} ‖_{2}^{2}) .$

맨 처음 objective와 달라진 점은, rating vector r (0 이상의 real value) 이 preference vector p (0 또는 1) 로 바뀌었다는 점과, 각각의 u,i pair에 대해 confidence $c_{u i}$ 가 곱해진다는 점이다. 이때, $c_{u i}$ 는 optimization parameter와는 상관없이 맨 처음 정해지고 변하지 않는 값이므로, 이렇게 바뀐 objective function을 풀기 위해서 이전 문제와 마찬가지로 살짝 변형된 SGD나 ALS 등을 사용할 수 있다. 논문에서는 조금 더 scalability를 고려한 방법론을 제안하는데, matrix product를 조금 더 효율적으로 하도록 matrix들을 decompose하여 조금 더 order가 낮은 연산을 하는 방법을 사용한다. 자세한 알고리즘은 논문을 참고하면 좋을 것 같다.

정리하자면 이 논문은 rating vector r을 preference vector p로 변환하고, confidence level c를 정의한 후, p와 c를 사용해 RMSE objective function을 optimize하는 work인 것이다. 그리고 앞서 설명했던 두 가지 문제는 confidence level c를 정의하는 방법에 의해 해결할 수 있다.

Logistic Matrix Factorization for Implicit Feedback Data [3]

앞선 논문 [2]에서는 RMSE를 minimize하는 objective를 설계하였지만, RMSE가 아닌 다른 형태의 objective를 optimize하는 것도 가능하다. 앞선 논문에서 RMSE를 minimize함으로써 얻을 수 있는 효과는 관측한 preference $p_{u i}$ 와 복원한 preference ${\hat{p}}_{u i}$ 가 서로 (RMSE의 관점에서) 최대한 비슷한 값을 가지도록 optimization이 된다는 것이다. 이 논문은 perference의 RMSE를 minimize하는 문제 대신, 관측 값 $r$ 과 optimization parameter $Θ = (x, y, b)$ 등의 posteriori를 maximization하는 방식을 취한다. 참고로 이 논문은 Spotify에서 발표한 논문으로, 실제 음악 추천에서 응용하고 있는 듯 하다.

계속 강조하듯, 여기에서 실제 유저가 선호하는 것과 유저의 implicit feedback 결과는 다를 수 있다. 그렇기 때문에 이 논문은 u가 i를 좋아할 확률을 logistic function으로 확률적으로 정의한 후, 관측한 데이터로부터 posteriori를 maximize하는 방향으로 학습을 하게 된다. 그러기위해 이 논문은 $ℓ_{u i}$ 이라는 새로운 notation을 introduce하고 이를 사용자 u가 item i를 선호하는 'event'로 정의한다. 어렵게 설명했지만, 그냥 'user u가 음악 i를 좋아한다 좋아하지 않는다'에 대한 0, 1 값이다. 이 논문은 주어진 $Θ (x, y, b)$ 에 대해 $ℓ$ 이 1이 될 확률 $p r_{u i}$ 를 다음과 같이 logistic form으로 정의한다.

$p r_{u i} := P r [ℓ_{u i} = 1 | Θ] = \frac{\exp (x_{u}^{⊤} y_{i} + b_{u} + b_{i})}{1 + \exp (x_{u}^{⊤} y_{i} + b_{u} + b_{i})} .$

직관적으로 생각해보았을 때, 앞선 논문 [2]은 r의 값이 0보다 크기만 하면 항상 u가 i를 좋아한다고 생각하지만, 이 논문에서는 그것이 r의 값에 대한 확률로 나타난다는 점을 알 수 있다. Reconstructed rating $\hat{r}$ 을 ${\hat{r}}_{u i} = x_{u}^{⊤} y_{i}$ 이라고 했을 때, 위의 함수는 ${\hat{r}}_{u i}$ 에 대한 증가함수이므로 ( ${\hat{r}}_{u i}$ 의 값이 $- \infty$ 가 되면 함수값이 0이고, ${\hat{r}}_{u i}$ 값이 $\infty$ 가 되면 함수값이 1이 된다), 위의 식은 rating 값이 더 크면 호감을 가질 확률이 더 높아지는 형태의 확률 함수가 된다.

따라서 이 모델의 likelihood는 positive observation u,i의 set을 $S$ 라 하였을 때 다음과 같이 쓸 수 있다.

$L_{n a i v e} (R | Θ) = \prod_{u, i \in S} p r_{u i} \prod_{u, i \notin S} (1 - p r_{u i})$

그러나 앞선 논문 [2]에서도 언급되었듯, negative feedback은 '싫어한다'와 다른 의미를 가지고 있기 때문에, 이 논문에서도 confidence라는 것을 정의하게 된다. [2]와의 차이점이라면 RMSE 관점이 아니라 앞에서 살펴본 likelihood function의 관점에서 정의를 한다는 점이다. 여기에서 $c_{u i}$ 는 $α r_{u i}$ 로 사용하는데, 만약 hyper-parameter $α$ 의 값이 크면 positive observation에 더 큰 비중을 두고, $α$ 의 값이 작다면 negative observation에 더 큰 비중을 두는 식으로 다음과 같이 정의를 하게 된다.

$L (R | Θ) = \prod_{u, i} P r [ℓ_{u i} | Θ]^{α r_{u i}} (1 - P r [ℓ_{u i} | Θ]) .$

위의 식에서 negative feedback에 대한 (즉, 만약 관측값 $r_{u i}$ 가 0이라면) likelihood 값은 $L (r_{u i} | Θ) = 1 - p r_{u i}$ 가 되므로 앞에서 계산한 naive한 likelihood function과 일치한다. 그러나 positive feedback에 대한 likelihood는 $p r_{u i}^{α r_{u i}} (1 - p r_{u i})$ 가 되므로, $α$ 의 값을 조절함에 따라 앞에서 계산한 값과 차이가 있다.

개인적인 생각으로는 여기에서 저자가 증명을 잘못한 것이 아닐까 생각된다. 만약 Positive feedback의 likelihood에 weight를 주기위해 exponent c를 추가한다고 했을 때, likelihood 식은 다음과 같이 된다.

$L = \prod_{u, i \in S} (p_{u i}^{ℓ_{u i}} (1 - p_{u i})^{1 - ℓ_{u i}})^{α r_{u i}} \prod_{u, i \notin S} p_{u i}^{ℓ_{u i}} (1 - p_{u i})^{1 - ℓ_{u i}} .$

이때, $r_{u i} > 0$ 일 때 $ℓ = 1$ 이고, 혹은 둘 다 0이라는 특성을 잘 사용하면 이 식은 다음과 같이 표현이 된다.

$L = \prod_{u, i} p_{u i}^{α r_{u i}} (1 - p_{u i})^{1 - ℓ_{u i}} .$

즉, 만약 저자가 의도한대로 positive feedback의 likelihood에 exponent로 weight를 주고 싶었다면, positive feedback의 likelihood function에서 1-p 부분이 없어야한다는 점이다. 이 부분은 저자가 실수를 했거나 혹은 내가 이해를 잘못했을 가능성이 있다. 혹시 몰라서 논문을 좀 찾아봤는데, 약 한 달 전쯤 나온 논문에서 증명한 결과가 내가 증명한 결과와 같은걸 보면, 저자가 틀린게 맞는 것 같다.

그리고 또 다른 문제는 $p r_{u i}$ 는 언제나 값이 0에서 1사이이기 때문에 $c_{u i} = α r_{u i}$ 의 값이 크면 클수록 $p r_{u i}$ 의 값은 오히려 감소하게 된다는 것이다. 그래서 논문의 설명과는 반대로 $α$ 의 값을 키우는 것이 오히려 positive observation의 weight를 낮추는 것이 아닌가하는 생각이 드는데, 논문을 여러 번 다시 읽어보고 계산을 해봐도 아직 아리송하다. 오히려 이렇게 하고 싶었다면, 최종 objective가 완전히 바뀌기는 하지만, 관측된 데이터 $S$ 에 대해서 likelihood를 $(1 + α_{u i}) p r_{u i}$ 와 같은 형태로 정의하는 편이 훨씬 좋지 않을까? 왜 base가 1보다 작은데, weight term을 exponent으로 올렸는지 이해가 되질 않는다. 이 부분은 혹시 나중에 이해가 완전히 되면 내용을 추가하도록 하겠다.

다시 본문으로 돌아오자. Likelihood를 계산했으니, prior만 있다면 posteriori를 계산할 수 있게 된다. 이 논문은 $x, y$ 의 prior를 전부 0 mean Normal distribution으로 정의한다. 이렇게 정의할 경우, 나중에 log MAP 문제를 풀게 될 때, L2 regularization과 같은 형태의 식 $\frac{λ}{2} (‖ x ‖^{2} + ‖ y ‖^{2})$ 을 얻을 수 있다. 자세한 증명은 생략한다. Prior를 정했으니 이제 posteriori를 구해서 다음과 같이 log MAP 문제를 정의할 수 있다. (논문에서 증명한 결과로, 내가 증명한 결과와는 차이가 있다)

$\log P r [Θ | P] = \sum_{u, i} c_{u i} {\hat{r}}_{u i} - (1 + c_{u i}) \log (1 + \exp {\hat{r}}_{u i}) - \frac{λ}{2} (‖ x_{u} ‖^{2} + ‖ y_{i} ‖^{2}) .$

이 문제 역시 다른 문제들 처럼 한 번에 update하기가 어렵기 떄문에 alternative하게 update를 하게 된다. 정확히는 coordinate gradient method를 사용한다 (maximize문제이므로 ascent가 될 것이다). 여기에서 한 가지 문제가 발생하는데, 앞에 붙어있는 summation term이 모.든. (u,i) pair에 대한 summation이기 때문에 한 번 gradient를 계산하는 비용이 어마어마해진다는 것이다. 정확히는 아이템의 개수 I와 유저의 숫자 U에 대해 linear한 비용이 필요하다. 보통 그 둘의 값은 몇 백만, 몇 천만이 될 정도로 크기 때문에 scalability 이슈가 굉장히 중요해진다. 이 논문은 그런 문제를 해결하기 위하여 (속도가 느리다는 문제) AdaGradient를 사용하라거나, 전체에 대해 summation을 하는 대신, 전체 positive pair (u,i)와 일부 negative pair (u,i)만 사용해서 문제를 해결하라고 언급되어있다.

정리하자면 이 논문은 Matrix Factorization을 RMSE minimization 문제가 아닌 MAP 문제로 해결하려는 시도를 한 논문으로, MAP로 바꾸기 위하여 confidence가 포함된 likelihood function을 정의한다. (개인적으로는 이 likelihood function이 왜 이런 꼴을 하고 있는지 이해하지 못하였다) 알고리즘은 coordinate ascent를 사용하지만, 각각의 gradient 값이 아이템과 유저의 개수에 linear하기 때문에 실제 데이터에서 practical하지 못하다는 문제가 발생한다. 이런 문제를 해결하기 위하여 이 논문은 전체 matrix의 거의 대부분을 차지하는 negative observation을 전체 다 사용하는 대신, 일부만 sample하여 사용하는 방식을 제안하고 있다.

Bayesian Personalized Ranking for Non-Uniformly Sampled Items [4]

앞의 두 논문은 같은 문제의 objective function만 RMSE와 MAP로 서로 다르게 잡은 경우이지만, 이 논문은 앞의 방법들과 다소 다른 접근 방식을 취하고 있다. 이 논문은 먼저 선행 연구[5]를 조금 발전 시킨 논문인데, 선행 연구에서는 partially observed pair-wise competition 문제를 푸는 Baysian Personalized Ranking (BPR) optimization과 그것을 푸는 알고리즘을 제안하고, 그것을 MF로 확장하고있다. 그리고 그 다음 논문 [4]에서는 원래 논문이 가지는 단점을 negative observation을 adaptive하게 sample하는 방식으로 개선하고 있다.

먼저 핵심 notation들을 정의해보자. 관측된 (u,i) pair는 $S$ 라는 set으로 정의된다. 여기에서 새로운 notation $I_{u}^{+}$ 와 $U_{i}^{+}$ 2개가 introduce된다. $I_{u}^{+}$ 는 user u가 관측한 적 있는 item의 set이고, $U_{i}^{+}$ 는 item i를 관측한 적 있는 user u의 set이다. 그러면 이 set들을 통해 $D_{S}$ 라는 triplet을 다음과 같이 정의할 수 있다.

$D_{S} := {(u, i, j) | i \in I_{u}^{+} and j \notin I_{u}^{+}} .$

즉, user u, user u가 관측한 item i와 관측하지 못한 item j 이렇게 셋의 triplet인 것이다.

이제 이 논문의 핵심아이디어인 pair-wise ranking에 대해 살펴보자. 이 논문은 먼저 각각의 user u에게 item i와 item j간의 pair-wise ranking이 존재한다고 가정한다. 이 논문에서는 user u가 item i를 j보다 높은 order를 가질 때 $i >_{u} j$ 의 꼴로 표현한다. 이 pair-wise ranking은 (혹은 order는) totality, antisymmetry, transitivity를 만족하는 order로 정의된다. 자세한 수식은 논문에 있으니 생략한다.

이 논문은 user u가 item i를 item j보다 더 높게 평가할 확률을 다음과 같이 가정하고 있다.

$P r (i >_{u} j | Θ) = σ ({\hat{r}}_{u i j} (Θ)) .$

여기에서 ${\hat{r}}_{u i j} := {\hat{r}}_{u i} - {\hat{r}}_{u j}$ 로 정의되는 값이고, $σ$ 는 sigmoid function으로, $σ (x) = \frac{1}{1 + \exp (- x)}$ 의 꼴로 정의된다. 각각의 user에 대해 pair-wise ranking에 대한 확률을 정의했고, 또한 실제 관측값도 있기 때문에, 우리는 ranking에 대한 likelihood를 정의할 수 있고, prior를 가정하게 되면 posteriori역시 계산할 수 있다. 먼저 likelihood $\prod_{u} p (>_{u} | Θ)$ 부터 계산해보자. (이전과 마찬가지로 user들은 전부 independent하다고 가정했기 때문에 곱으로 표현된다)

$\prod_{u} p (>_{u} | Θ) = \prod_{u, i, j} \prod_{u} p (i >_{u} j | Θ)^{I_{(u, i, j) \in D_{S}}} (1 - p (i >_{u} j | Θ))^{I_{(u, i, j) \notin D_{S}}}$

$I_{x}$ 는 x가 true면 1이고 false면 0인 indicator function이다. 여기에서 order를 정의할 때 totality와 antisymmetry를 가정하였기 때문에, 위 식을 잘 건개하면 아래와 같은 간단한 식으로 표현하는 것이 가능하다고 한다.

$\prod_{u} p (>_{u} | Θ) = \prod_{(u, i, j) \in D_{S}} p (i >_{u} j | Θ) .$

[3]과 같이 prior를 zero mean normal distribution으로 정의하게 되면, log posteriori는 다음과 같이 표현된다.

$max \ln P r (Θ | >_{u}) = max \sum_{(u, i, j) \in D_{S}} \ln σ ({\hat{x}}_{u i j}) - λ ‖ Θ ‖^{2} .$

이 문제는 stochastic gradient descent로 푸는 것이 가능하다. 자세한 미분 값은 논문에 있으니 생략한다. 참고로 이 논문은 이 문제를 optimization했을 때 얻을 수 있는 solution이 AUC (area under the ROC curve, ROC curve는 wiki 참고)를 maximization하는 것과 비슷한 문제라는 것을 따로 증명해두었으니 관심이 있다면 한 번쯤 읽어보면 좋을 것 같다.

[4]에서 제안한 BPR (baysian personalized ranking) problem을 풀기 위해서 SGD를 사용한다는 언급을 했는데, 문제가 하나 있다. 바로 triplet $D_{S}$ 의 개수가 너무 많아서 전부 uniform하게 뽑기에는 데이터가 너무너무 많다는 것이다. 그래서 [5]에서는 adapted sampling 방식을 제안하고 있다.

$max \sum_{(u, i, j) \in D_{S}} w_{u} w_{i} w_{j} \ln σ ({\hat{x}}_{u i j}) - λ ‖ Θ ‖^{2} .$

이때 $w_{u} = 1 / | I_{u}^{+} |$ , $w_{i} = 1$ 로 정의가 된다. 즉, 관측한 아이템이 더 많은 유저는 적게 뽑고, 모든 positivie item은 uniform하게 뽑는다. 마지막으로 $w_{j} = \frac{1}{| U | | I |} \sum_{u} I_{j \in I_{u}^{+}}$ 으로 취하게 되는데, 더 많이 사용자들이 관측한, 혹은 좋아한 데이터 위주로 sample을 뽑는 방식이다.

정리해보면, BPR은 다른 논문들처럼 reconstructed error를 바로 measure하는 것이 아니라, pair-wise ranking을 정의하고, 복원된 rating ${\hat{r}}_{u i}$ 에 대해 user가 item i보다 j를 좋아할 확률을 sigmoid로 정의한다. 이 확률을 사용해 MAP문제를 정의하는데, 이 문제는 ROC curve의 넓이를 구하는 것과 비슷한 문제가 된다. 이때, sigmoid function을 step function으로 바꾸면 완전히 ROC curve의 넓이를 구하는 것과 같은 문제가 된다. Sigmoid가 step function의 가장 popular한 differentiable approximation 중 하나이기 때문에 sigmoid로 정의하게 되는 것이다. Algorithm은 SGD를 사용하는데, 데이터 셋이 user u가 관측한 item i와 관측하지 않은 item j의 triplet이기 때문에 uniform sampling을 하게 되면 결과가 좋지 않을 수 있다. 때문에 adaptive하게 (u,i,j)에서 j 고를 때, popular한 j를 더 고르도록 sample을 하여 성능을 개선하고 있다.

정리

이 글에서는 Implicit feedback에 대해 recommendation을 어떻게 할 수 있을지 서로 다른 세 가지 접근방법을 소개했다. 첫 번째는 가장 기본적인 방법으로, confidence level $c_{u i}$ 를 정의하고, real value variable인 $r_{u i}$ 를 binary variable인 $p_{u i}$ 로 바꾼 다음 optimization을 푸는 방법에 대해 소개했다. 두 번째로는 RMSE를 optimization하는 대신, u가 i를 좋아할 확률을 모델링하고, 주어진 데이터에 대해 MAP를 푸는 방법에 대해 소개했다. 마지막으로는 각각의 user별로 item들끼리의 personalized pair-wise ranking을 정의하고, 역시 마찬가지로 u가 i보다 j를 좋아할 확률을 모델링하고 이것의 MAP를 구하는 방법에 대해 소개했다. 알고리즘은 SGD로 해결할 수 있지만, 조금 더 smart하게 item을 뽑는 adaptive sampling을 사용할 경우 성능이 더 올라간다고 한다.

References

변경 이력

2016년 3월 6일: 글 등록

다른 machine learning study 글 보러가기