시작하면서..
저번의 content-based methods에 이어서 similar user를 찾는 Collaborative Methods에 대해 이야기 해보겠습니다.
Collaborative Methods
Collaborative recommender systems (or collaborative filtering systems : CF)는 특정 user의 item utility를 이전에 다른 users의 rating을 기반으로 predict 하려 합니다.
Formally,
user \(c\)에 대한 item \(s\)의 utility \(u(c,s)\)는 utilites \(u(c_j,s)\)에 의해 측정됩니다. 이때 \(c_j\)는 user \(c\)와 similar한 user들의 set인 \(C\)의 \(c_j \in C\)입니다.
이전 포스트에서의 Content-based method에서는 \(u(c,s_j)\)로 표현했는데, 이에 대해 생각을 해보면 CF 방법이 User의 관점에서 생각하고 있음을 알 수 있습니다.
참고로, 논문에서는 Similar users를 "peers"로 표현하고 있습니다.
이 다음에는 개인의 제한된 정보에서의 user based model mechanism인 stereotype으로 제안된 최초의 추천 시스템 "Grundy system"을 언급하며 추천 시스템의 발전을 말하고 있습니다.
그냥 오래 전부터 유용하게 쓰여왔다는 것을 파악하고 넘어가시면 될 것 같습니다.
Memory-based and Model-based
Collaborative recommendations는 memory-baesd(heuristic-based)와 model-based의 두 classes로 나뉠 수 있습니다.
우선 Memory-based algorithms에 대해 알아보겠습니다.
Memory-based algorithms는 이전에 users가 이미 rating한 전체를 바탕으로 rating prediction을 진행 하는 것 입니다.
formally, 아래처럼 나타낼 수 있습니다.
$$
r_{c,s} = aggr ~ r_{c^\prime,s},~c^\prime \in \hat C
$$
\(\hat C\)은 user \(c\)와 가장 비슷한 N명의 set 입니다.
위의 \(aggr\) 에는 여러 방법이 있습니다.
$$
(a)~ r_{c,s} = {1 \above 1pt N}\sum_{c^\prime\in \hat C}r_{c^\prime,s}
$$
$$
(b)~ r_{c,s}=k\sum_{c^\prime\in \hat C}sim(c,c^\prime)\times r_{c^\prime,s}\
$$
$$
(c)~ r_{c,s}=\bar r_c +k\sum_{c^\prime\in \hat C}sim(c,c^\prime)\times (r_{c^\prime,s}-\bar r_c)
$$
대부분의 aggregation은 (b)를 사용합니다.
$$
k = {1 \above 1pt \sum_{c^\prime\in \hat C}|sim(c,c^\prime)|}
$$
\(sim(c,c^\prime)\)은 \(c\)와 \(c^\prime\)가 비슷할수록 \(r_{c^\prime,s}\)는 \(r_{c,s}\) 예측에 포함 됩니다.
하지만 Similarity measure에 대해서 문제가 있습니다.
Weighted sum 사용 시 user마다 rating scale이 다를 수 있다는 사실을 고려하지 못합니다. 이 문제를 다루는 널리 퍼진 방법은 adjusted weight sum (c)입니다. 이는 average rating에 대한 편차를 사용합니다. 그리고 또 다른 방법은 preference based filter가 있습니다.
One common strategy : all user similarlity를 계산하고 user의 recommendation 요청이 있는 언제든지 효율적인 rating calculate 진행. (precompute)
위를 oneline-offline 전략이라 부르기도 합니다.
model based에서는 coleection of ratings를 통해 모델을 학습시킵니다.
예를들어, unknown ratings를 아래와 같이 계산 할 수 있습니다.
$$
r_{c,s} = E(r_{c,s})=\sum^n_{i=0}i\times Pr(r_{c,s}=i|r_{c,s^\prime},s^\prime\in S_c)
$$
위 식의 중요한 부분인 probability를 측정하기 위해 two alternative probabilistic models를 제안합니다.
Two alternative probabilistic models : Cluster model, Bayesian network
- Cluster model
: like-minded(similar) users는 classes로 cluster 됩니다. 주어진 user's class membership에서 user ratings는 독립적이라 여겨집니다.(나이브 베이즈) 그리고 class의 수와 파라밑들은 data로부터 학습됩니다. - Bayesian Network : each items를 node로써 표현하고, each node의 states는 each items의 possible rating value에 대응합니다.
위의 두 structure 모두 data로부터 훈련됩니다.
하지만 cluster model에서 단점이 하나 있는데, 그건 몇몇 recommendation applications는 여러 categories로 나누는게 더 좋을 수 있는데도, 한 user 당 single cluster로만 cluster 될 수 있다는 점 입니다.
CF에서의 model based와 heuristic의 차이
CF에서 model based와 heuristic(memory based) 사이의 가장 큰 차이는, model based는 heuristic rules에 기반한 것이 아닌 data에 대한 model 훈련을 기반으로하는 utility(rating) prediction이라는 것 입니다.
이걸 좀 더 쉽게 말하면, memory based 방식은 그냥 식 자체를 통로로 삼아서 계산해내는 그런 느낌이고, model based 방식은 데이터를 통해 모델이 학습되면서 식이 변하는 느낌의 차이라고 생각하시면 될 것 같습니다:)
이런 차이점을 가진 두 방식을 섞어 사용하면 (model-based와 memory-based를 결합) 단일 방법 사용보다 더 나은 성능을 보일 수 있다고 합니다.
Limitation
New User Problem
초기에 user의 선호에 대한 학습이 필요합니다. (CF는 데이터 수에 굉장히 민감합니다. 어느정도 데이터 수가 궤도에 올라줘야 괜찮을 성능을 보일 수 있습니다.)
이에 대해 가장 많이 사용되는 해결 방안 중 하나로 hybrid methods가 있습니다.
또 다른 approach로는 (new user에 대해 최선이라 생각되는 item을 찾는 방법) item popularity, item entropy, user personalization 등을 이용한 techniques들이 있습니다.
New Item Problem
CF에서는 어떤 item에 대해서 상당한 수의 user에게 rate 되지 않는다면 system이 추천을 해줄 수 없습니다. 이런 한계를 다루는 방법으로 위와 같이 hybrid methods 가 있습니다.
Sparsity (희소)
rating된 item에 비해 rating prediction 해야 할 item의 수가 훨씬 많습니다. 그래서 적은 수의 rating에 의한 효과적인 prediction이 필요합니다. 이 뿐만 아니라 부족한 user에게도 잘 작동을 해야합니다.
이에 대한 해결책으로 여러 가지가 제시되어 있는데,
- User similarity 측정 시 user profile information을 사용. 이는 rating 정보 뿐만이 나닌 인구 통계학적인 부분을 고려한다는 뜻입니다. (gender, ...) 이를 demographic filtering이라 부릅니다.
- 이 논문 Reference [49] "Applying associative retrieval techniques ..."
- dimentionality reduction technique(SVD)를 사용하는 방법이 있습니다.
데이터가 sparse 하면 user와 item의 정보가 같이 들어있는 matrix가 굉장히 밀도가 떨어집니다. 그래서 SVD를 통해 user, item 행렬 정보를 분리시켜줍니다. 이를 통해 분리된 행렬 각각을 따로 학습 후 곱하면, 성능이 더 잘나온다고 합니다.
마치면서..
이번 포스트는 이 서베이 논문에서 힘을 주고 있는 부분인 Collaborative methods(CF)에 대해서 이야기해봤습니다. 이 논문에서 CF 부분에 대해 소개할 때 CF의 예시들을 주로 제시해서, 이런 포스트로 정리하기가 좀 어려웠습니다. (그래서 좀 뭔가 자연스럽지 않은 느낌..)
이제 다음 포스트는 이 서베이 논문은 마지막 부분인데, 이 논문 리뷰가 끝나고 나서는 원서를 공부하고 공부한 내용에 대해 게시 할 생각입니다.
