ML&DL/Graph algorithm

[Paper review] Improving Diversity in Ranking using Absorbing Random Walks

거북이주인장 2024. 1. 16. 18:35

Summary

  • 본 논문에서 제안하는 GRASSHOPPER 알고리즘은 absorbing markov chain random walks의 아이디어를 사용하여 centrality / diversity / prior을 모델에 녹여낸다.
  • 우선, 가장 상위 노드는 pagerank을 돌려서 나오는 최상위 점수의 노드로 정한다. 그리고 이 최상위 점수의 노드를 absorbing state로 만든다.
  • 다음으로, 나머지 노드들간의 expected visits을 구하여, 가장 많은 expected visits을 가지는 노드를 두번째 노드로 구하고 다시 이 노드를 absorbing state로 만든다.
  • absorbing state로 만듦으로써 해당 노드와 유사한 노드는 상대적으로 적은 expected visits을 가지게 되고 이를 통해 pagerank 결과에 다양성을 부여한다.

Motivation

  • pagerank 알고리즘은 가장 주요한 노드를 찾는데는 요긴하게 사용될 수 있으나, 그 주요한 노드와 유사한 노드들도 상위 노드로 뽑히는 문제점이 있다.
  • 그에 따라서 상위 n개의 노드를 뽑을 때, 서로 유사한 노드들이 뽑혀서 결과에 다양성이 떨어지는 단점이 있다.
  • 이에 대한 문제 의식을 가지고 랭킹에 있어서 다양성을 주기 위해, 다양한 방법들이 제안되었다.
    • maximum marginal relevance (MMR)
    • cross sentence informational subsumption
    • mixture models
    • subtopic diversity
  • 그러나 이 방법들은 centrality ranking과 diversity ranking을 구분하고, 때로 휴리스틱한 절차가 필요하다.
  • 본 논문에서는 이런 한계점을 극복하기 위해 Graph Random-walk with Absorbinb States that Hops among Peaks for Ranking (GRASSHOPPER)을 제안한다.

Approach

The input

  • $W \in \mathbb{R}^{n \times n}$: weight matrix으로, $w_{ij}$는 노드 i에서 노드 j로 edge의 weight
  • $\mathbf{r} = (r_1, \cdots, r_n)^{T} \; s.t. \; r_i \geq 0, \sum^n_{i=1} r_i = 1$: n개의 문장에 대해 유저가 미리 정하는 prior. 보통 문서를 요약하는 상황에서는 처음 몇번째 문장이 중요하기 때문에 이 문장들의 중요도를 높게 주는 경우가 많다.
    • 만약 prior가 없다면 $\mathbf{r} = (1/n ,\cdots, 1/n)^T$로 준다.

Finding the first item

pagerank을 사용하여 첫번째 노드를 찾는다.

  • i번째 상태에서 어떤 노드에 도착하면 edge weights에 따라 이웃하는 노드로 가기도 하고, 일정 확률에 의해서 다른 노드로 랜덤하게 텔레포트 하기도 한다.
    • 이때 edge weights는 위의 weight matrix에서 정의하고, 다른 노드로 랜덤하게 텔레포트할 확률은 prior인 $\mathbf{r}$로 정한다.
  • 이 과정을 반복하다보면 mild condition하에서 random walk의 stationary distribution은 노드의 방문 확률을 정의하고 큰 확률을 가지는 노드가 전체 노드에서 주요한 노드로 간주된다.

위 과정을 수식으로 나타내면 아래와 같다.

  • $P = \lambda \hat{P} + (1-\lambda) \mathbf{1r}^T$
    • $\hat{P}_{ij} = w_{ij} / \sum^n_{k=1} w_{ik}$: walker가 i에서 j로 옮겨갈 확률
    • prior인 $\mathbf{r}$과 함께 이웃하는 노드로 갈지, 랜덤하게 다른 노드로 갈지, random walk인 $P$를 계산한다.
  • $P$는 아래의 조건을 만족하기 때문에 유일한 stationary distribution을 가진다.
    • irreducible (possible to go to go go any state from any state by teleporting)
      • $\lambda < 1$이고 $\mathbf{r}$은 0이 아닌 값을 가진다.
    • aperiodic (the walk can return to a state after any number of steps)
    • erogodic (the expected return time to any state is finite)
  • 유일한 stationary distribution을 가지기 때문에 $\pi = P^T \pi$로 치환해서 생각할 수 있고, eigen vector 문제로 생각해서 $\pi$를 구하면 된다.
  • 최종적으로, 첫번째 아이템은 $g_1 = argmax^n_{i=1} \pi_i $로 구해진다.

  • 2차원의 입력값을 가지는 300개의 데이터를 생성하고 (b)와 같이 3차원에 그림을 그려보면, 가장 확률 값이 높은 $g_1$이 첫번째 아이템으로 뽑힌다.

Ranking the remaining items

GRASSHOPPER의 핵심 아이디어는 ranked items을 absorbing state로 만드는 것이다.

  • $g_1$을 absorbing state로 만든다. 즉, $g_1$에 walker가 도착하면 그곳에서 나올 수 없는 것이다.
  • 이렇게 되면 aperiodic 조건을 충족하지 않기 때문에 더이상 stationary distribution을 가지지 않게 된다.
  • 하지만, absorption 이전에 각 노드의 기대 방문 횟수를 계산하는 것은 의미가 있다.
    • 직관적으로, $g_1$와 유사한 노드들은 $g_1$을 많이 방문하게 될 것인데, $g_1$은 absorbing state이므로 더이상 다른 노드를 방문하지 못하게 된다. 자연스럽게 $g_1$의 방문 횟수도 줄어들고 $g_1$과 유사한 노드들의 방문 횟수도 줄어든다.
    • 반면에, $g_1$과 멀리 떨어진 노드들은 그들끼리 방문을 하게 되므로 방문 횟수가 상대적으로 늘어난다.이제 (c)에서 y축은 확률이 아닌, 기대 방문 횟수로 바뀐다.
    • $g_1$을 absorbing state로 만들면, 그 주변에 있는 노드의 기대 방문 횟수는 줄어들고 다른 집단의 기대 방문 횟수는 늘어난다.
  • $g_2$가 absorbing state가 되면, 다른 집단의 $g_3$의 기대 방문 횟수가 크게 나타난다.
    • 이때, (d)에서 y축의 스케일이 더 줄어들었다. absorbing state가 늘어났기 때문이다.

Algorithm details

따라서 markov chain이 absorbing되기 전에, 기대 방문 횟수를 계산하는 것이 중요하다. 이를 아래와 같이 생각해보자.

  • $G$: set of items ranked so far
  • $g \in G$인 노드를 $P_{gg} = 1, P_{gi} = 0, \forall i \neq g$을 통해 absorbing state로 만든다.

랭크된 아이템과 랭크되지 않은 아이템을 재배열하여 transition matrix을 아래와 같이 적을 수 있다.

  • $\mathbf{I}_G$: $G$에 대한 identity matrix
  • $R, Q$: 랭킹되지 않은 아이템에 대한 row matrix

absorging random walk에서 기대 방문 횟수인 fundamental matrix은 아래와 같이 계산됨이 알려져 있다. (Doyle and Snell, 1984)

$N_{ij}$는 absorption 전에 i에서 j로의 기대 방문 횟수를 의미한다. 이제, 모든 시작 지점에서 j로 기대 방문 횟수의 평균을 아래와 같이 구해보자.

여기서 $|G|$는 G의 크기이다. $\mathbf{v}$을 구했으면, 다음 랭크될 아이템은 가장 큰 기대 방문 횟수를 가지는 노드로 정한다.

GRASSHOPPER의 전체적인 알고리즘은 아래와 같다.

Some discussion about time complexity

알고리즘 중간에 $(n - |G|) \times (n - |G|)$ 차원의 역행렬을 계산하는 부분이 있다.

여기서 시간이 오래걸릴 수 있는데, 이터레이션마다 $Q$는 하나의 행과 열을 없애는 방식이고 이런 상황에서는 matrix inversion lemma을 사용하여 시간 복잡도를 줄일 수 있다. (sherman morrison woodbury formula)

Experiments

Experimental setup

  • Dataset
    • 매년 꾸준히 열렸던 summarization 대회인 DUC의 데이터세트를 사용했다.
  • Input
    • $w_{ij} = \begin{cases} 1 & \text{if } \dfrac{s^T_i s_j}{ ||s_i|| \cdot ||s_j|| } \\ 0 & o.w. \end{cases}$
    • prior distribution: $r \propto p^{-\alpha}$, $\alpha$는 하이퍼 파라미터, p는 문장의 위치
  • Hyperparameter tuning
    • $\alpha=0.25, \lambda=0.5$

Results

  • GRASSHOPPER을 DUC 데이터세트에 넣어서 돌려본 결과이다.
  • 대회에 참여했다고 가정하면, 상당히 높은 순위를 차지함을 알 수 있다.

Conclusion

  • pagerank에 다양성을 부여하는 시도로 GRASSHOPPER 알고리즘을 살펴보았다.
  • 논문을 통해 fundamental matrix에 대한 개념을 새로 알았고, 특정한 상황에서 역행렬을 구하는 시간을 줄여주는 matrix inversion lemma도 알게 되었다.
  • 본 논문의 핵심 아이디어인 absorbing state을 만드는 과정은 꽤나 신선했다. 문서 하나를 가져와서 기존의 pagerank 결과랑 GRASSHOPPER 결과가 어떻게 다른지 정성적으로 비교해보면 알고리즘이 더 와닿을 것 같다.
  • 다만, pagerank의 알고리즘을 공부함에 있어서 markov chain에 대한 이해는 필수적으로 있어야할 것 같으니, 해당 부분을 이론적으로 더 심도있게 공부해야겠다는 생각이 들었다.