Chat HoPT 5

[Paper Review] Sequences of Sets (KDD 2018) 본문

Paper Review/Graph Mining

[Paper Review] Sequences of Sets (KDD 2018)

thisis05 2024. 4. 28. 15:32
논문 링크  : https://www.cs.cornell.edu/~arb/papers/sequences-of-sets-KDD-2018.pdf

1. Introduction

 

본 논문은 데이터 마이닝과 머신러닝에서 인간 행동을 모델링하는 연구의 중요성을 강조한다. 특히, 사용자가 특정 항목을 반복적으로 소비하는 행동을 예측하는 데 초점을 맞추고 있다.

이전 연구들은 주로 어떤 하나의 아이템에 대한 반복적인 connection에 중점을 두었지만, 이 논문은 여러 항목과 동시에 connection하는, 즉 집합 측면에서 repetition에 주목한다. 예를 들어, 이메일은 여러 수신자에게 발송될 수 있고, 학술 논문은 여러 공동 저자와 함께 작성되는 것처럼, 부분적 혹은 완전한 집합의 반복이 이뤄지기 마련이다.

본 논문은 특정 Sets들의 sequence K개가 주어졌을 때, K+1 time에 Set에 들어갈 성분 중에서도 novel이 아닌 repeated items들을 예측하는 데 주목하고 있다. 또한 이러한 예측을 위해 dataset의 특징을 고려한 모델인 Correlated Repeated Unions (CRU)를 소개하고 있다.

2. Data Analysis

본 논문에선 sets이 sequential 하게 나타나는, 즉 ordered sequence set data가 존재하는 총 4개 domain의 8개 dataset을 사용한다.

또한 분석의 통일화를 위해 한 set의 size는 5개 이하로 통일한다. (tag data가 set에 최대 5개만 들어갈 수 있음) 이 경우 data의 loss가 어느정도 일어나는 지 확인해봤을 때, set size가 5개를 넘어가는 경우는 data의 극히 일부에 불과하기 때문에 거의 없다고 볼 수 있다. 또한 sequence에 set이 적어도 10개이상 존재하는 경우를 고려한다.

 

(1) Repeat behavior

 

Sequence 내에선 위와 같은 노드의 등장이 나타날 수 있다.

  • (1) set 전체가 정확하게 반복
  • (2) set 중 일부가 반복
  • (3) prior set을 포함하는 super set이 나타나는 경우
  • (4) 전체 다 새로운 item이 나타나는 경우

먼저 (4)의 경우의 fraction, 즉 새로운 Set이 등장할 때 전체 다 새로운 노드로 구성되어 있는 경우는 많이 없다고 볼 수 있다. Figure B 또한 set size가 커질 때마다 이러한 비율은 줄어든다.

Figure A, C를 통해 모든 new set은 거의 exactly repeat이거나 일부 repeat일 경우가 많다는 것을 알 수 있다. 즉, Figure D처럼 sequence 상에서 등장하는 set들은 이전 set의 super set일 경우가 많다는 것을 의미하게 된다.

즉 본 연구에서는 시간에 따라 repeat elements의 분포가 어떠한 지를 살펴본다.

(2) Subset correlation

 

어떤 set에 repeated elements가 존재할 때, repeated elements의 수의 분포

 

두 번째로 볼 것은, 단순 element가 반복되는 것이 아니라, subset이 함께 반복되는 경우가 많다는 것이다. 즉, 어떤 set 내의 원소들은 서로 연관이 있으므로 반복될 때도 같이 반복되는 경향이 있다는 것이다.

다음과 같이 현재 j번째까지 나타난 집합들의 부분집합의 개수를 세고 평균을 내보면 아래와 같은 결과가 나타난다.

 

 

즉, size 2 or size 3의 subset이 함께 중복되어서 나타나는 경우가 많다는 것이다. null model의 경우 sequence 내의 sets의 size는 동일하게 유지하면서 elements들을 랜덤하게 섞을 경우의 sequence이다. 즉, 이렇게 할 경우 단순 element들이 반복하여 등장하는 것인지, 아니면 set 내에서의 어떤 element들끼리의 correlation이 존재하고 이를 기반으로 반복되는 것이지를 평가할 수 있다. 위 table에서 나온 것처럼 일종의 correlation이 존재한다고 볼 수 있다.

즉 이러한 분석을 통해서, 어떤 element가 반복되는 지 따로따로 보기보다는 sets 내의 어떤 subset이 반복되고 있는지를 기반으로 보려고 한다.

(3) Recency bias

또한 분석을 통해 확인한 결과 repeat set은 최근 set의 정보를 좀 더 반영하여 repeat하는 것으로 확인되었다. 즉 recency bias가 존재하는 것이다.

위와 같이 Jacard Index를 이전 set들과 계산한 결과 가장 최근의 set가 가장 유사한 것으로 나타났다.

 

따라서 다음 set의 repeat elements를 예측할 때 위를 고려하여 예측이 진행되어야 할 것으로 보인다.

3. The Correlated Repeated Unions Model (CRU)

본 연구에서는 (2) Subset correlation을 고려하여 시퀀스 내에서 이전 Set인 $S_i$에서 각 element들이 뽑힐 확률을 $p$로 설정하고, (3) Recency bias를 고려하여 $S_i$를 뽑을 확률을 $w_i$ : recency bias weight로 설정한다. recency bias의 경우 가장 최근 set을 더 많이 가중하여 뽑을 수 있도록 weight를 조정한다. 우리는 최종적으로 시퀀스 상 다음 set에 올 repeat elements를 예측하고 이를 기반으로 w, p를 조정하여 최적 파라미터를 찾아내는 것을 기본 구조로 한다.

(1) Algorithm 설명

그러면 위 세가지 요소를 반영하여 repeat consumption을 modeling 해보자.

 

일단은 기본적으로 하고자 하는 건 $S_{k+1}$에 나타나는 Repeat elements $R_{k+1}$에 대한 probability distribution을 구하는 것이다.

  1. 먼저 recency weight (가장 최근의 sequence일수록 weight가 높음)를 기반으로 $S_i$를 선택한다.
  2. 그 후 probability p를 기반으로 각 원소를 뽑을지 말지 정해서 subset $T$를 정한다.
  3. 이전 step을 통해 모아진 R과 T를 합집합 연산했을 때 원소의 개수가 N개를 넘어간다면, T를 너무 크게 뽑는 것이므로 T에서 random하게 일부 원소를 빼면서 R에 합집합 연산을 해준다. 이 과정은 크기가 N보다 작아질 때 까지 반복한다.
  4. R의 크기가 목표 repeat set size인 r이 될 때 반복을 멈춘다.

이런 알고리즘을 통해서 뽑힌 R은 step에 따라 어떤 order에 의해 뽑히게 될 것이다. 즉, 매 step 뽑는 T \ R을 ordered partition이라고 생각할 수 있는 것이다. 따라서 우리는 $\mathcal{P}(X)$를 어떤 X의 ordered partitions set이라고 하면, X = {a, b} → {({a}, {b}), ({b}, {a}), ({a, b})} 이라고 생각할 수 있다.

또한 $E_{r,k}$를 S1 - Sk 까지의 합집합 중에서 모든 r- size subset의 집합이라 할 때, 우리는 $E \in E_{r,k}$에 속하는 E를 결국 만들어 내는 것이고, 이 E에 대해서 각 step 당 뽑는 순서를 고려하면 $\mathcal{P}(E)$가 되는 것이다.

결국 우리가 하고자 하는 것은 어떤 기준에 의해 repetition 되는 지 알아보기 위해 Likelihood of $R_{k+1}$을 최대화하는 w, p를 구하는 것이므로 아래와 같이 식을 세울 수 있다.

 

즉 R_k+1의 Likelihood는 이를 구성하는 orderd partition X의 확률의 합으로 나타내지는 것이다.

그렇다면 이 확률을 어떻게 구할 수 있을까?

(2) Evaluation of Probability $R_{k+1}$

두 가지 가정을 해보자

(1) X : a ordered partition

(2) B : 다음 step에 추가될 order, but last order는 아님

현재까지 추가된 R과 다음 step의 T도 있다고 했을 때, X를 성공적으로 완성해나가기 위해선 다음 step에 두가지 경우가 발생할 수 있다.

 

 

만약 (1)이라면 완전히 R에 이미 있는 것이기 때문에 order가 추가되지 않는다. 따라서 계속 반복해야 한다. 만약 (2)라면 R에 없는 것도 T에 포함되어 있기 때문에 성공적인 order가 추가된다. 따라서 한 스텝에서의 확률은 아래와 같이 구성된다.

 

(1)의 확률을 q_r, (2)의 확률을 q_s라 하면 위와 같이 표현할 수 있다. 그러면 q_r, q_s를 좀 더 표현해보면 아래와 같다.

 

Ind는 일단 이 집합에 속하는지 아닌지를 1, 0으로 나타내주는 Indicator function이다. $P_{T,S} = p^t(1-p)^{s-t}$로, 우리가 S_i의 원소 s개중에서 |T| = t를 선택할 확률을 쭉 구한것이다. 직관적으로 이해가 가능하다. 따라서 위의 수식을 아래와 같이 직관적으로 표현할 수 있다.

$q_r =$ 모든 $S_i$에 대해서 : $S_i$를 뽑을 확률 x (1)의 case에 해당하는 경우의 확률의 합

$q_s =$ 모든 $S_i$에 대해서 : $S_i$를 뽑을 확률 x (2)의 case에 해당하는 경우의 확률의 합

 

따라서 (1)과 (2)는 disjoint하고 합집합 연산 시 모든 가능성을 포함하게 되므로 위와 같이 확률이 계산된다.

 

지금까지는 B가 last order가 아닌 경우를 구한 것이다. 그렇다면 B가 last order일 경우는 어떻게 되는가? 이 경우 Equation (5)만 바뀌게 된다.

우리의 알고리즘이 마지막 time에 완성되기 위해선 다음과 같은 조건을 따라야한다.

$|T \backslash (R \cup B)| >= |R\cup B|$

즉, 여기서의 B는 order partition set에서 마지막 원소를 의미하는데, 이 때 T에서 더 많이 R에 없는 것들을 뽑아내버리면 이를 덜어내는 작업을 해야하는 것이다. (Algorithm 1의 second if statement)

즉 C = T \ (R U B) 에 해당하는 원소들을 뽑아내기 위해선 알고리즘 상에서 뽑히는 y가 C에 있지 않은 것부터 뽑여야 한다. 따라서 아래와 같이 B를 적절히 capture하는 확률이 나타난다.

 

순서를 고려하여 전체 배치 중에서 B에 해당하는 것들이 먼저 배치되는 확률을 나타낸다고 보면된다. 이때, B, C 모두에 해당하지 않는, 즉 T에서 이미 R에 있는 것들은 고려할 필요가 없다.

따라서 이를 고려하여 마지막 B를 뽑는 확률 q_s를 따로 지정해준다.

 

따라서 모든 order partition의 set X = (B1, B2, … Bt)라고 했을 때, 최종적으로 우리가 R_{k+1}을 구성하게 되는 X 하나를 뽑는 확률은 아래와 같다.

 

이 때 우리는 어떤 S_i에서 뽑았는지를 모두 고려하여 일종의 가중합을 하기 위해 W = \sum_{i=1}^k w_i weight normalization을 곱해준다.

 

즉 위 파트는

 

를 의미하게 된다.

 

최종적으로 Log Likelihood function을 설정하고, W에 대한 gradient를 구하여 computing 하기 위해 아래와 같이 식을 완성한다.

 

 

따라서 이 Log likelihood의 w에 대한 gradient function을 조정해가면서 어떤 W에서 어떤 결과가 나오는지를 확인해보자.

4. EXPERIMENTAL RESULTS

(1) Likelihood and performance

먼저, 계산된 Likelihood를 N (sequences 전체에서 repeat이 존재하는 set의 개수)으로 나눠주어 $e^{LL_p/N}$ : mean per-set likelihood를 구해준다. p가 변함에 따라 이 평균 우도가 어떻게 변하는지 도메인 데이터셋 별로 살펴본다. 이 때 baseline과 비교하여 살펴볼 것인데, 이 baseline model은 set structure를 고려하지 않은 모델이라고 생각하면 된다. 즉, 우리는 recency weight라고 하여 각 set에 대해서 가중치를 고려했다면 이 baseline은 element 하나하나를 고려하여 weight를 부여한 것이다. 따라서 set sturcture를 고려하지 않기때문에 p가 존재하지 않고, 하나의 mean per-set likelihood가 존재하게 된다.

 

 

보이는 것과 같이, 일반적으로 domain 내에서는 최적 p가 비슷한 것으로 나타난다. 즉, 같은 domain내에 있는 dataset들은 이전 set에서 뽑아내는 element의 수가 비슷하다는 것이다.

email에서는 한 사람이 이전 mail을 보냈던 사람들에게 재차 메일을 보내는 경우가 허다하므로 p가 1근방에 위치하는 것으로 볼 수 있다.

tag 데이터에서는 0.5-0.6 정도로 나타나는데, 이는 상위 레벨의 tag를 이전 set에서 가져오고 specific한 tag를 새로 가져오는 느낌이라고 볼 수 있다.

이처럼 각 domain datset의 p를 분석함으로써 각 network의 구조나 형태를 파악해볼 수 있다.

(2) Learned recency weights

 

또한 각 index별, 즉 가장 가까운 set이 1로 시작하여 현재 set과 점점 거리에 따라 index 값이 커질 때 recency weight가 어떻게 달라지는 지를 나타내보면 위와 같다. 눈 여겨볼 점은 2가지이다.

첫 번째로 coauth dataset에서 꺾이는 지점이 발견되는 것이다. 지금까지의 기조대로라면, w는 index가 커지면서 감소하는 게 정설이지만, coauth의 경우 일정 index를 지나가면 오히려 weight가 증가하는 형태로 최적화된 것을 볼 수 있다. 이건 prolific authors, 즉 어느정도 productive한 author들이 long term connection을 지니고 있기때문이라고 볼 수 있다. 이 author들은 오랜 기간동안 수많은 paper들을 써왔기 때문에 최근이 아닌 예전 author들과도 상호작용하는 경우가 많기때문에 weight가 증가하는 형태로 나타날 수 있다는 것이다.

두 번째로 contact-high school과 tags - mathoverflow의 경우 p가 달라지면서 weight distribution이 달지거나, 아예 똑같이 움직이는 연관성도 보인다. 이에 대해선 추가적인 Mining 작업이 필요할 수 있다.

5. Asymptotic Tipping Behavior

그렇다면 위 Model을 통해 다음 timestamp의 set을 예측할 때 고려해야하는 점은 무엇이 있을까?

본 논문에서는 특정 sequence가 특정 set이후에 반복적으로 똑같은 set을 갖게 될 위험성을 확률로 증명하고 있다. 이 특정 set이 나타나는 경우를 Tipping Event라고 정의한다.

결론만 따지자면 $W_\infty=\sum_{i=1}^\infty w_i$가 $< \infty$, 즉 어떤 점으로 수렴하는 Bounded일 경우 위와같은 Tipping Behavior가 발생하는 반면, 발산할 경우에는 발생하지 않는다는 것을 증명하였다.

즉, 우리가 이 모델을 이용하여 예측하고자 할 때, 우리의 데이터셋의 W의 bounded 여부에 주의하여 모델을 사용해야 함을 말하고 있다.