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은 다음과 같다.
이전 글에서는 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
앞서 설명한 것 처럼, preference vector의 값을 항상 신뢰할 수 있는 것은 아니다. 때문에, 이 논문에서는 confience level
혹은
c를 정의하는 것에는 또 하나의 이점이 있다. Parameter
이제 objective를 정의할 차례이다. Explicit feedback에서는 복원한 rating
맨 처음 objective와 달라진 점은, rating vector r (0 이상의 real value) 이 preference vector p (0 또는 1) 로 바뀌었다는 점과, 각각의 u,i pair에 대해 confidence
정리하자면 이 논문은 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
계속 강조하듯, 여기에서 실제 유저가 선호하는 것과 유저의 implicit feedback 결과는 다를 수 있다. 그렇기 때문에 이 논문은 u가 i를 좋아할 확률을 logistic function으로 확률적으로 정의한 후, 관측한 데이터로부터 posteriori를 maximize하는 방향으로 학습을 하게 된다. 그러기위해 이 논문은
직관적으로 생각해보았을 때, 앞선 논문 [2]은 r의 값이 0보다 크기만 하면 항상 u가 i를 좋아한다고 생각하지만, 이 논문에서는 그것이 r의 값에 대한 확률로 나타난다는 점을 알 수 있다. Reconstructed rating
따라서 이 모델의 likelihood는 positive observation u,i의 set을
그러나 앞선 논문 [2]에서도 언급되었듯, negative feedback은 '싫어한다'와 다른 의미를 가지고 있기 때문에, 이 논문에서도 confidence라는 것을 정의하게 된다. [2]와의 차이점이라면 RMSE 관점이 아니라 앞에서 살펴본 likelihood function의 관점에서 정의를 한다는 점이다. 여기에서
위의 식에서 negative feedback에 대한 (즉, 만약 관측값
개인적인 생각으로는 여기에서 저자가 증명을 잘못한 것이 아닐까 생각된다. 만약 Positive feedback의 likelihood에 weight를 주기위해 exponent c를 추가한다고 했을 때, likelihood 식은 다음과 같이 된다.
이때,
즉, 만약 저자가 의도한대로 positive feedback의 likelihood에 exponent로 weight를 주고 싶었다면, positive feedback의 likelihood function에서 1-p 부분이 없어야한다는 점이다. 이 부분은 저자가 실수를 했거나 혹은 내가 이해를 잘못했을 가능성이 있다. 혹시 몰라서 논문을 좀 찾아봤는데, 약 한 달 전쯤 나온 논문에서 증명한 결과가 내가 증명한 결과와 같은걸 보면, 저자가 틀린게 맞는 것 같다.
그리고 또 다른 문제는
다시 본문으로 돌아오자. Likelihood를 계산했으니, prior만 있다면 posteriori를 계산할 수 있게 된다. 이 논문은
이 문제 역시 다른 문제들 처럼 한 번에 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는
즉, 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를 가질 때
이 논문은 user u가 item i를 item j보다 더 높게 평가할 확률을 다음과 같이 가정하고 있다.
여기에서
[3]과 같이 prior를 zero mean normal distribution으로 정의하게 되면, log posteriori는 다음과 같이 표현된다.
이 문제는 stochastic gradient descent로 푸는 것이 가능하다. 자세한 미분 값은 논문에 있으니 생략한다. 참고로 이 논문은 이 문제를 optimization했을 때 얻을 수 있는 solution이 AUC (area under the ROC curve, ROC curve는 wiki 참고)를 maximization하는 것과 비슷한 문제라는 것을 따로 증명해두었으니 관심이 있다면 한 번쯤 읽어보면 좋을 것 같다.
[4]에서 제안한 BPR (baysian personalized ranking) problem을 풀기 위해서 SGD를 사용한다는 언급을 했는데, 문제가 하나 있다. 바로 triplet
이때
정리해보면, BPR은 다른 논문들처럼 reconstructed error를 바로 measure하는 것이 아니라, pair-wise ranking을 정의하고, 복원된 rating
정리
이 글에서는 Implicit feedback에 대해 recommendation을 어떻게 할 수 있을지 서로 다른 세 가지 접근방법을 소개했다. 첫 번째는 가장 기본적인 방법으로, confidence level
References
- Recommendation System (Matrix Completion)
- Hu, Yifan, Yehuda Koren, and Chris Volinsky. "Collaborative filtering for implicit feedback datasets.", 2008
- Johnson, Christopher C. "Logistic matrix factorization for implicit feedback data.", 2014
- Gantner, Zeno, et al. "Bayesian personalized ranking for non-uniformly sampled items.", 2012
- Rendle, Steffen, et al. "BPR: Bayesian personalized ranking from implicit feedback.", 2009
변경 이력
- 2016년 3월 6일: 글 등록