A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem
때문에 본인도 딱히 의문을 품어본 적이 없었는데, 얼마전 연구실 세미나에서 measure에 따라 결과값에 영향이 있겠냐는 박사님 지적에 해당 논문을 찾아보게 되었다.
2008년에 출판된 논문이라 제법 오래된 논문이지만, 여러 measure 별로 성능 비교를 해둔 논문이기도 하고, 새로운 similarity를 제안했기 때문에 여러 논문에서 인용을 한 듯 하여 선택하게 되었다.
아직 논문 리뷰를 잘하는 편이 아니기 때문에, 리뷰 방식은 해오던 습관대로 각 절마다 그 내용을 소개하는 것으로 한다.
Abstract
논문이 써진 당시인 2008년에는 netflix prize에서 우승한 collaborative filtering(CF)이 추천시스템에서 갖게 된 위상이 매우 높았다. 저자는 CF가 갖고있는 위상을 소개하면서 동시에, CF의 주요한 특성인 similarity measure가 Pearson correlation이나 cosine 유사도에 머물러있음을 지적한다. 따라서 본 논문에서는 새롭게 heuristic similarity measure를 제안한 것이 학술적인 contribution이라할 것이고, 새로운 measure를 이용한 실험 결과 CF가 갖고있는 고질적인 문제인 cold-start problem을 가진 데이터셋에서 좀 더 나은 퍼포먼스를 보인다고 한다.
1. Introduction
저자는 e-commerce에서 CF가 갖는 위력에 대해 우선적으로 소개하고 있다. 추후 CF에 대해서만 포스팅을 하나 해야겠다.
간단히 CF에 대해서 공부했던 바를 정리해보면, CF는 기본적으로 취향이 비슷한 User의 집단이 존재한다고 가정한다. 추천의 대상이 되는 어떤 user가 있으면, 취향이 비슷한 neighbor가 존재할 것이고 이들이 공통적으로 긍정적인 rating을 한 item을 타겟이 되는 user에게 추천하는 방식이 기본적인 아이디어이다. 때문에 CF에서는 neighbor를 찾기위해 유사도 행렬을 이용한다는 점 정도만 짚고 넘어가면 될 것 같다.
다시 돌아와서, 이 논문에서도 CF의 위력은 similarity에 있음을 이야기하고 있고, Pearson 상관계수와 같은 전통적인 벡터 similarity measure가 주로 사용되고 있어 CF의 한계인 cold start problem에서 자유롭지 못함을 지적한다.
저자는 이러한 문제의식을 드러내며 본 논문의 취지를 밝히고 있으며 그 취지는 heuristic similarity measure의 제안으로 이어진다. 전형적이고 기본적인 골조지만 앞으로 논문 작성 시에 이러한 프레임워크를 적용한다면 좀 더 쉽게 작성할 수 있지 않을까 하는 감상이 든다. 저자는 새로 제안된 방식이 user의 item에 대한 co-ratings에 더욱 세밀하게 집중한 방식이므로, cold-start 문제를 가진 데이터에 대해 더욱 효과적인 measure가 될 수 있다고 주장한다.
2. Literature review
2절에서는 추천시스템 전반에 대한 overview와 CF에 대한 리뷰를 제공한다. 논문이 출판된지 제법 오래되었기 때문에 overview는 큰 의미 없으리라 생각하고, CF에서 사용되고 있는(또는 사용되었던) similarity measure를 정리하는 표(Table 1) 정도만 확인하고 넘어가면 될 것 같다.
Table 1의 measure들은 이후 4절의 experiment에서 비교 실험을 위해 사용된다. 본 논문은 기본적으로 cold start가 있는 신규 user의 진입 상황을 가정하므로, user-item matrix에 대해서 Table 1의 measure들은 다음의 식에 사용된다. :
\[\overline{r_{u_a}}+\frac{\sum_{h=1}^{m'}\mathrm{sim}(u_a, u_h)(r_{u_h,i_a}-\overline{r_{u_h}})}{\sum_{h=1}^{m'}|\mathrm{sim}(u_a,u_h)|}\]
저자에 따르면 당시에 존재하던 hybrid 방식의 추천시스템들은 기본적으로 cold start problem을 우회하기 위해 content information과 ratings data를 결합하여 사용했다. 즉, 새로 진입한 user나 item에 대해서는 rating-based의 measure는 계산할 수 없기 때문에 당시의 hybrid 추천시스템들은 그러한 방식을 채택했다는 것이다.
그런데 이러한 당시의 연구 목적과 달리 본 논문에서는 rating record가 '적은' 상황을 가정한 것이며, hybrid RS에서처럼 추가적인 information을 요구하지 않는다. 따라서 기존의 CF에 대해 measure만 변경하여 모델링하면 되기 때문에 저자는 이러한 효율적인 연구목표를 설정한 듯 하다.
3. A new similarity measure
3.1 Diagnosis of the limitations of existing similarity measure
새로운 제안에 앞서, 우선 저자는 기존 measure들이 갖고 있는 문제점을 지적한다. 우선 COR(Pearson's)과 COS(Cosine similarity)는 근본적으로 cold-start에 취약할 수 밖에 없음을 지적한다.
예컨대 데이터셋의 sparsity level이 0.90이라면, 그러니까 현존하는 <user-item> rating matrix R에 10% 수준의 rating만이 존재한다고 했을때 + 타겟 user가 고작 5개의 item만을 구매했다고하면(이 부분이 정확한지는 모르겠다. 단순히 a user라고 지칭하고 있는데, 아마도 추천을 타겟팅할 user를 이야기하는 것 같다.), COR이나 COS를 계산하는 것이 거의 불가능한 상황이 된다.
이러한 상황을 간략히 정리해보면 다음과 같다. :
(1) Sparse matrix에서는 co-ratings을 계산하는 것이 매우 제한적이다.
(2) user-user간에 co-rating한 item이 단지 1개에 불과하다면, 기본적으로 COR은 계산될수조차 없고, COS는 co-rating이 어떤 값을 취하든 1의 값을 갖는다.
(3) user에 의해 주어진 rating이 item 별로 모두 같은 경우(논문에서는 flat이라고 표현했음) COR은 계산될 수 없고, 그 외의 correlation formula들은 0으로 계산된다.
(4) 각 user-item rating vector가 평행한 경우(e.g. <2,2> and <3,3>) COS는 1의 값을 갖는다.
(5) 결론적으로 COR과 COS 모두 서로 성향이 완전히 다른 user를 neighbor로 잘못 계산할 수 있다.
또한 (1)~(5)의 문제점들은 dataset이 sparse할수록 더 심각한 문제를 야기한다. 개인적으로 이러한 COR과 COS에 대한 문제점을 단순한 plot(Fig. 1.)으로 표현하여 직관성을 높인 부분이 배울 점이라고 생각한다.
이후의 내용은 실험에 사용될 dataset들이 이러한 문제에 취약하다는 점을 지적하는 내용이므로, 리뷰에서는 생략한다.
3.2 A new similarity measure for CF systems : PIP measure
3.1절에서 COS, COR의 문제점을 짚었으므로, 본 논문이 제안하는 PIP measure는 다음의 목적을 만족할 수 있도록 설계되었다. :
(A) 제안된 measure는 cold-start recommendation 상황에서 data가 갖는 domain specific meanings를 단순히 전통적인 measure를 사용하는 것에 비해 더욱 잘 이용할 수 있어야 한다.
(B) 실용성을 위해, 제안된 measure는 쉽게 현존하는 CF system에 plug-in할 수 있어야 한다.
(C) 제안된 measure는 cold-start condition에 있는 new user에서만 향상된 결과를 보일 뿐 아니라, non-cold-start condition에 대해서도 기존의 measure에 대비하여 쓸만한 성능을 보여야 한다.
위와 같은 목적으로 제안된 PIP measure는 Proximity, Impact, Popularity 의 세가지 요소로 이루어지게 되었다.
PIP measure는 user \(i\)와 user \(j\)에 대한 similarity를 다음과 같이 계산한다. :
\[\mathrm{sim}(u_i,u_j) = \sum_{k\in C_{i,j}} \mathrm{PIP}(r_{ik}, r_{jk})\]
수식에서 \(r_{ik}\)는 user \(i\)의 item \(k\)에 대한 rating이고, \(C_{i,j}\)는 user 간의 co-rated item set이다.
이때, \(\mathrm{PIP}(r_1, r_2)=proximity(r_1, r_2) \times Impact(r_1, r_2) \times Polularity(r_1, r_2)\) 으로 계산된다.
각각의 요소를 Fig. 3.과 Table2에서 description 하고 있다. 결과적으로는 user가 item에 부여한 각각의 rating을 경우에 따라 penalization 하거나 advantage를 부여함으로써 similarity를 입체적으로 계산한다는 감상을 받게 되었다. 이런 점에서 제안된 PIP measure가 heuristic measure라고 저자는 주장하는 듯하다.
댓글 없음:
댓글 쓰기