[Paper Review] (2015, ACM) Context-Aware Event Recommendation in Event-based Social Networks

Context-Aware Event Recommendation in Event-based Social Networks (2015, ACM)

작성자 : 이혜린, 장아연

---

0. ABSTRUCT

Event recommendation은 Cold Start 문제를 직면해왔습니다. 이러한 한계를 극복하기 위해 논문에서는 Event-based social network(EBSNs)에서 RSVPs로 사용자에서 파생된 collaborative signals와 event의 description 기반의 Content Based Signal 이외로 Contextual Signal에 해당하는 social signals, location signals, temporal signals을 수집합니다. 최종적으로 다음의 signals을 조합해 event에 대해 learn to rank를 진행해 Personalized Recommedation을 제시합니다.

1. Introduction

1) Cold Start

많은 양의 가능성이 있는 Event는 때때로 User가 그들의 흥미에 딱 맞는 event를 찾는 것을 방해하기도 합니다. 이런 과도한 정보량에서 Recommender system이 관련있는 정보를 제시해 준다는 점에서 문제 상황을 극복하는 솔루션이라고 생각되기도 하지만, 책과 영화 같은 classic한 Recommender scenarios와 달리 event recommender는 새로운 event에 대해 Cold Start 문제를 가집니다. EBSNs의 Event의 다음과 같은 특성 때문에 Cold Start 발생이 불가피하다고 할 수 있습니다.

• 주로 short lived
• always in future

즉, EBSNs의 Event는 이전의 과거 행적과 연관성이 매우 적어 전통적인 Recommender approach로는 EBSN User에게 만족감을 주기 어렵습니다.

2) Contextual Signal 수집

RSVPs (불어로 "Please Respond"라는 뜻의 문장의 약어)로 사용자에서 파생된 collaborative signals와 event의 description 기반의 Content Based Signal 이외 Contextual Signal을 도입함. 수집한 Contextual Signal에는 다음과 같은 것들이 있습니다.

• social signals : group memberships 기반
• location signals : users’ geographical preferences : user의 home과 각 event 발생지까지 거리 기반
• temporal signals : users’ time preferences 기반

이런 Contextual signal은 User의 Event 참석 여부 결정을 추정하는데 도움이 될 것이라고 가정합니다.

3) 더 정확한 Recommender System을 위한 Contributions

• EBSNs에서 발생 가능한 multiple contextual signal을 바탕으로 specialized된 event recommendation model들 비교
• learning to rank event를 위한 feature로서 multiple context-aware recommendation model 이용해 hybrid recommendation approach 제안
• state of the art recommender와 대조하며 효율성을 비교하고 Meetup.com 크롤링 한 것을 통해 철저하게 approach 평가

2. Problem Setting

1) Cold Start Problem

전통적인 recommendation system은 주로 2개의 entity 간의 interaction에 대한 modeling이 진행됨. 그러나 Context-aware recommender는 interaction을 정의하는데 도움이 되는 additional signal까지 사용함. EBNS에서 Additional Signal 사용이 불가피한 이유는 다음과 같습니다.

• Event는 항상 미래에 발생되기 때문에 EBNS에서의 User와 후보가 되는 Event 사이의 interaction 없음
• User-Event attendance의 경향성에 대한 RSVP의 data를 사용해도 여전히 대부분의 event에 대한 정보가 누락됨

따라서 이런 Cold Start 문제를 해결하기 위해 EBNS에서 풍부한 contextual evidence를 이용하기를 제안합니다.

2) Major Problem : Which of available events are more likely to be attended by user?

결국 이 논문에서는 주어진 target user와 contextual signal을 이용해 다음의 문제를 해결하기 위해 다음과 같이 formalizing problem setting 진행합니다.

• RSVP data를 time-stamp $\theta$ 전후를 기준으로 분할
  • training partition: $\theta$ 전으로 발생한 (user, event) 쌍
  • test partition: $\theta$ 후로 발생한 (user, event) 쌍
• $U$ : the set of users
• $E$ : the set of events
• $T$ : contextual signals users’ temporal preferences
• $G$ : set of groups that users can join
• $D$ : users’ geographic distance preferences
• $C$ : the textual content of events

Implicit data : content, User, time, event, group, distance 간의 relation :
Task : find scoring function : 후보 Event에 대한 preference score 배정
Top -n recommendation :

• $n$ : number of events to be recommended
• $E_{u}$ : 과거 User가 참석했던 Event의 set

Minimize a ranking loss function :

• 위 함수는 $\hat{s}$ $\in$ $\mathbb{R}^{E}$ 에 의해 생성된 추천리스트와 training할 동안 실제 event에 대해 무지 상태였던 test user에 대한 $\mathcal{P}$의 부분 집합으로서 actual list 사이에서의 misfit을 측정합니다.

Context-aware recommender의 Relevance Score :

• Context - Aware recommender가 context $X$에서 $u$$\in$$U$와 $e$$\in$$E$ 간의 Relevence score를 계산한 것을 다음과 같이 표현했습니다.

3.Contextual Model

1) Social-Aware

EBNS에서 User는 다른 User와 online/offline으로 만나며 interaction을 가짐. 따라서 두가지의 소통 형태에 대해 각각 Model을 제안합니다.

a. Group Frequency Model

User가 Group에서 더 많은 Event에 참여할수록, 계속해서 해당 group의 event에 참여할 가능성은 높습니다.

Target User $u$ $\in$ $U$에 대해 해당 Event의 Relevance Score

• $g_{e}$ : 후보 event $e$와 연관된 group
• $E_{u}$ : User $u$가 참여한 모든 event 집합
• $E_{u,g_{e}}$ : Group $G$ $\in$ $g_{e}$에 의해서 형성된 event 중 User u가 참석한 모든 event
• $S_{1}$ : 이 recommender가 표현하는 social context

b. Multi-Relational Model

Group Frequency Model에서는 다음의 2가지 관계가 고려되지 않았습니다.

• User와 그들과 친밀한 모든 group간의 관계
• Group과 그 Group에서 진행된 Event

User가 친밀하게 여기는 group과 동일/유사한 group에 의해 진행되는 event는 참여할 가능성이 높기 때문에 다음의 관계는 반드시 고려되어야하고 더 나아가 추천 시스템에서의 cold start 문제를 해결할 수 있습니다.

본 논문의 저자는 Multi-Relational Factorization with Bayesian Personalized Ranking (MRBPR)을 이용해 위의 interaction을 모델링합니다.

Target Relation

$R_{UG}$ $\subseteq$ $U$ X $G$와 $R_{GE}$ $\subseteq$ $G$ X $E$의 친밀한 관계를 포함한 joint factorization approach를 진행합니다.

Parameter

• 각 고려하는 entity와 관련된 $U$, $E$, $G$의 latent matrices
  즉, user 집합인 $U$는 $U$$\in$ $\mathbb{R}^{|U|* k}$ 와 관련되어 있습니다.
  ($k$ : 고려 대상이 되는 entity에 대한 latent factor의 갯수)

Objective Function

• $L$ : Loss Function
• $\alpha$, $\beta$, $\gamma$ : 고려하고 있는 relation에 대한 weight
• $\lambda_{U}$, $\lambda_{G}$, $\lambda_{E}$ : regularization parameter

Stochastic Gradient Descent
SGD를 통한 parameter learning이 이루어집니다.

Predict Relevance score

• $\vec{u}$ : user $u$에 대한 latent vector
• $\vec{e}$ : event $u$에 대한 latent vector

기존의 single relation에서 이루어진 standard matrix factorization과 다른 점은 latent factor인 $u$와 $e$ 모두 user가 미래의 event 참여 여부 결정에 영향을 미치는 group aspect을 포함합니다.

2) Content-Aware

Content base filtering이 EBNS에서 유망한 접근법인 이유는 다음과 같음.

• 유사한 특징을 보이는 event 찾아냅니다.
• 유사한 context 속에서 발생한 event에 대한 recurrent event를 찾습니다.

event에 대한 text 설명은 classic bag-of-words model이 진행됩니다. 과거 user가 참석했던 event에서 뽑아낸 단어 대한 TF-IDF vector는 각 user를 대표합니다. 각 event는 추천 인스턴스에 대해 time distance로 weighted됩니다. (Time value of money decay function : a measure of the rate of decline in the value of an events contract due to the passage of time과 비슷한 맥락)

Profile of target user

• $\vec{e}$ : event description에서 나온 term에 대한 TF-IDF 표현
• $\alpha$ : time decay factor
• $\tau(e)$ : 추천하는 순간과 event $e$에 대한 RSVP 사이 날짜

Rank Candiate Event

각 user의 입장에서 Cosine similarity를 바탕으로 한 후보 event에 대한 순위 제시하고 있습니다.

3) Location-Aware

한 도시 내에서 유저의 이동 패턴은 모두 다양합니다.

• User1 : 한 지역 내에 이벤트가 집중되어 있고, 다른 지역에서는 때때로 발생
• User2 : 2개의 지역에 이벤트가 집중되어 있음

이처럼 이벤트의 발생 패턴은 공간적 정보에 따라 상이하다는 것을 확인할 수 있으며, 이를 추천을 위한 하나의 feature로 사용하기 위해 저자는 다음과 같은 approach를 제안합니다.

Kernel-based density estimation approach

Kernel-based density estimation을 통해 유저의 이동패턴을 발생한 이벤트 간의 기하학적 거리의 분포로 모델링하고자 합니다. 이는 새로운 이벤트는 유저가 과거에 일으켰던 이벤트들의 지역들 중 하나에서 발생할 가능성(aggregated likelihood)을 바탕으로 발생하기 때문입니다.

$L_{u}$ 가 unknown distribution $f$를 따른다고 할 때, kernel density function $\hat{f}$ 은 다음과 같이 정의됩니다.

• $L_{u} = \bigcup_{e\in E_{u}}l_{e}$
  • $L_{u}$ : 타겟 유저가 과거에 참가했던 이벤트들의 위경도 sample
  • $l_{e}$ : 이벤트 $e\in E_{u}$ 의 위경도
• $K_{H}(·)$ : Bivariate Gaussian Kernel
  • $K_{H}(X) = {1 \over \sqrt{2\pi \vert H \vert}}\epsilon^{-{XX^{T} \over 2\sqrt{H}}}$
  • $H$ : bandwidth를 표현하는 행렬

유저의 지리적 선호도는 $l_{e}$에 centered된 가우시안 분포의 합으로 표현됩니다.
후보 이벤트들은 과거에 타겟유저가 참여했던 이벤트들과의 거리를 바탕으로 평가되며, 그것을 수식으로 표현한 결과는 다음과 같습니다.

4) Time-Aware

유저가 A이벤트에 참여할지를 결정하는 중요한 요인 중 하나는 이벤트가 언제 발생하는지입니다. 논문의 저자들은 유저들이 선호하는 특정 요일, 혹은 특정 시간대가 존재할 것이라고 가정합니다.

위 그림에서 첫번째 유저는 매일, 그리고 주로 밤에 이벤트가 발생했으며 두번째 유저는 일주일 중 2번, 그리고 오직 오후에 이벤트가 발생한 것을 알 수 있습니다.

이 인사이트를 공식화하기 위해, 각각의 이벤트 $e$를 24x7-dimension 벡터인 $\vec{e}$로 표현합니다.

• $\vec{e}$는 일주일 동안의 매 시간들을 의미하기 때문에 특정한 날, 특정한 시간에 이벤트가 발생한다면 해당 위치의 원소는 1의 값을 갖게 됩니다.
• 따라서, 각각의 유저는 그들이 과거에 참가했던 이벤트들을 centroid $\vec{u}$로 표현하게 됩니다.

마지막으로 유저 $u$와 이벤트 $e$ 간의 score는 두 벡터의 코사인 값으로 표현됩니다.

5) Learning to Rank Events with Contextual Features

Event recommender의 효율성을 높이기 위해 (특히 cold start), 앞서 생성한 recommenders($=s$)를 이벤트의 순위를 매기기 위한 학습의 feature로 사용합니다.

• $\mathcal{D} = \{ (x_{1},y_{1}), ..., (x_{n}, y_{n}) \}$
• $x_{i} = (\hat{s_{1}}(u,e), ..., \hat{s_{m}}(u,e), \vert U_{e} \vert )$
  • training set
  • $\hat{s}$ : user $u$와 과거에 발생했던 이벤트 $e$ 사이에서 생성된 정규스코어($z-value$)로 구성된 feature vector
  • $\vert U_{e} \vert$ : 이벤트의 sparsity
• $y_{i} = \{0,1\}$
  • 유저 $u$가 이벤트 $e$에 참석했으면 1, 아니면 0
  • rank setting 학습을 위해, classes are ordinal (i.e. 0 < 1)

Multi-Contextual Learning to Rank Events (MCLRE)

그리고 다음과 같은 학습 인스턴스 $(x_{i}, y_{i}), (x_{j}, y_{j})$ 의 관계를 반영할 수 있게끔 $h(x)$를 학습시킵니다. $h(x)$는 최종 추천 리스트를 생성해내는 함수이며, 이 method가 MCLRE 입니다.

또한 $h(x)$는 Coordinate Ascent방식으로 학습되었습니다.

Coordinate Ascent

• rank approach mathod
• 타겟 랭킹 평가 metric을 직접적으로 최적화
• NDCG@10을 평가 metric으로 사용
  

위 그림은 coordinate descent에 관한 그림입니다. coordinate descent가 목적함수를 minimize하는 방식이라면, 위 논문에서는 metric인 $NDCG@10$를(높을수록 좋은 metric) maximize하는 방식으로 훈련을 시킨다고 생각하시면 될 것 같습니다.
또한 coordinate descent는 gradient descent와 굉장히 유사해 보이지만, gradient descent는 학습 과정에서 한번에 모든 파라미터를 update한다면 coordinate descent(ascent)는 한번에 하나의 파라미터를 update하는 방법이라는 차이가 있습니다.

4. Evaluation

1) Experimental

a) Event dataset

• Meetup.com 데이터 크롤링
• Meetup : 내 주변 이벤트 찾기
  • 나의 관심사에 맞는 이벤트를 추천받고, 참가하도록 연결해주는 서비스
  • 매우 Sparse한 데이터셋 (sparse data 비율이 99.99% 이상)

b) Evaluation Protocol

• sliding training window 이용
• Timestamp 기준 이전 6개월 데이터 : Training
• Timestamp 기준 이후 6개월 데이터 : Test (해당 유저의 이벤트 발생여부를 예측하기 위한 데이터로 사용됨)
  

c) Recommendation Baseline

• MP : Positive response(yes) 순으로 정렬한 뒤 상위 10개 선택

• BPR-MF : Bayesian Personalized Ranking (with Matrix Factorization) / 사후 확률 최대화

• BPR-NET : BPR-MF 모델의 regularization term으로 2개의 social network를 사용 (the social network from the shared groups of users, the social network inferred from the co-attended events)

2) Results

Q1. How effective is MCLRE for event recommendation?

baseline 모델과 비교했을 때 MCLRE의 성능이 모든 지역(chicago, phoenix, san jose)에서 좋습니다.

Q2. How robust is MCLRE to sparsity in the RSVP data?

baseline 모델들은 sparsity level이 높아질수록 NDCG@10이 감소하는 편에 속하나, MCLRE는 event sparsity와 user sparsity 모두에서 꾸준히 좋은 성능을 보여줄 수 있음을 알 수 있습니다.

Q3. Which contextual features are effective recommenders?

• $MP$ : Positive response(yes) 순으로 정렬한 뒤 상위 10개 선택
• $T$ : contextual signals users’ temporal preferences
• $D$ : users’ geographicdistance preferences
• $C$ : the textual content of events
• $S1$ : the social context represented by Group Frequency Model (in Social-Aware)
• $S2$ : the social context represented by Multi-Relational Model (in Social-Aware)
• $MCLRE$ : Context feature를 함수 $h(x_{i})$를 통해 결합하여 사용한 모델

우리의 MCLRE 모델의 성능이 가장 좋았습니다.

5. Related Works

(생략)

6. Conclusions and Outlook

본 논문은 여러개의 context-aware recommender를 input feature로 사용하는 Rank Approach를 학습시키는 Event Recommendation Problem을 다뤘습니다.

각 사건들에 대한 설명을 바탕으로 한 content-based signal과 RSVP에서 비롯된 collaborative signal로부터 social, geographic, 그리고 temporal signal들을 도출했습니다.

또한 NDCG@10을 직접적으로 최적화함으로써 각각의 context-aware recommender의 output score로부터 개별적인 랭킹을 학습하는 랭킹 알고리즘인 Coordinate Ascent를 사용했습니다.

본 모델을 Meet-up.com 데이터를 통해 평가했을 때, 성능이 향상되었음을 알 수 있었습니다.

저자들은 향후 다음과 같은 태스크를 추가적으로 실행할 것이라고 얘기하며 논문을 마무리 합니다.

• 본 논문의 경우 미국이라는 한 나라에 있는 여러 도시에 대해 실험을 진행했는데, 다양한 나라에 있는 여러 도시에 대해 본 과정을 반복할 예정
• 다른 contexts와 접근법을 탐구할 예정
• 페이스북 이벤트 같은 다른 종류의 Event-based Social Networks에 대해서도 연구할 예정

참고 문헌

• https://dl.acm.org/doi/pdf/10.1145/2792838.2800187
• https://www.investopedia.com/terms/t/timedecay.asp
• https://soobarkbar.tistory.com/147