EXCELSIOR

[논문 리뷰] LexRank: Graph-based Lexical Centrality as Salience in Text Summarization 본문

개인연구/Text Summarization

[논문 리뷰] LexRank: Graph-based Lexical Centrality as Salience in Text Summarization

Excelsior-JH 2019. 11. 29. 02:20

LEXRANK: GRAPH-BASED LEXICAL CENTRALITY AS SALIENCE IN TEXT SUMMARIZATION

본 논문에서 제안한 LexRank는 Graph-based Extractive Summarization에 해당한다.

LexRank는 문서 내 문장을 하나의 노드(node)로하는 그래프 표현하고, 한 문장의 중요도를 고유벡터 중심성(eigenvector centrality)를 이용하여 계산한다.

1. INTRODUCTION

  • Summary는 두 가지 종류로 나눌 수 있다.

    • Topic-oriented summaries : 사용자가 설정한 특정 주제(topic)를 중심으로 요약하는 방법

    • generic summaries: 원본 텍스트가 포함하고 있는 전반적인 내용을 요약하는 방법 → 일반적인 요약

  • 본 논문에서는 multi-document extractive generic text summarization을 중점으로 다룬다.

  • 본 논문에서 제안하는 summarization 방법은 클러스터 내 각 문장의 중심성(centrality)을 평가하고 요약에 포함할 문장을 추출하는 것이다.


2. SENTENCE CENTRALITY AND CENTROID-BASED SUMMARIZATION

  • 원본 텍스트에서 중요 문장을 추출하는 방법인 Extractive summarization을 클러스터에서 가장 central한 문장을 식별하는 작업으로 볼 수 있다.

  • 문장의 중심성(centrality)은 대체로 각 문장이 포함하고 있는 단어의 중심성을 문장의 중심성으로 정의한다.

  • 단어의 중심성을 평가하는 일반적인 방법은 벡터 공간(vector space)에서 문서 클러스터의 중심(centroid)을 구하는 것이다.(?)

  • 클러스터의 중심은 사전에 정의한 임계값(threshold)을 넘는 tf-idf 점수를 가지는 단어로 구성된 문장(pseudo-document)이다.


3. CENTRALITY-BASED SENTENCE SALIENCE

  • LexRank는 소셜 네트워크(social network)에서 사용되는 개념인 prestige를 기반으로 한다.

    • "prestige""centrality"는 개념은 서로 동일하지만 전자의 경우 방향 그래프(directed graph)에서 사용되고, 후자의 경우 무방향 그래프(undirected graph)에서 사용된다.

  • 문서 클러스터는 서로 연관되어 있는 문장의 네트워크로 볼 수 있다.

    • 서로 관련이 있는 문장들은 비슷할 것이며, 관련이 적은 문장들은 비슷한 정도가 낮을 것이다.

  • 본 논문에서는 다른 많은 문장들과 유사한 문장이 문서 클러스터의 중심(central or salient)에 위치한다고 가정한다.

  • 중심성(centrality)에 대한 정의는 다음 두 가지를 따른다.

    • 먼저, 두 문장간의 유사도(similarity)를 어떻게 정의할 것인가.

    • 둘 째, 유사도가 정의된 후 중심성을 어떻게 구할 것인가.

  • 두 문장간의 유사도를 계산하기 위해 BoW(Bag-of-Words) 모델을 이용해 각 문장을 -차원의 벡터로 표현한다. 여기서 -차원은 코퍼스(corpus)내의 단어 수(vocabulary size)이다.

  • 각 문장은 아래의 그림과 같이 STM(Sentence Term Matrix)형태로 표현되며 각 문장의 단어는 tf-idf로 표현된다.



  • 두 문장간의 유사도는 코사인 유사도(cosine-similarity)로 정의된다. 본 논문에서는 이 코사인 유사도를 idf-modified-cosine이라고 정의한다.

    • 아래의 식에서 는 문장 에 나타난 단어 term frequency를 의미한다.


3.1 Degree Centrality

  • 식 (1)을 사용하여 각 문장들 사이의 유사도를 계산할 수 있으며, 아래의 표와 같이 유사도에 대한 임계값(threshold)을 조정하여 Degree(해당 노드에 연결된 엣지 수)를 조정할 수 있다.

  • 본 논문에서는 degree centrality를 각 노드의 degree로 정의한다.



  • 위의 표에서 확인할 수 있듯이 임계값에 따라 각 노드의 degree가 영향을 많이 받는 것을 알 수 있다. 예를 들어 d4s1의 문장은 임계값이 0.3이 될 때 degree가 1로 급격하게 줄어든다.


3.2 Eigenvector Centrality and LexRank

  • 각 노드(문장)의 중심성을 계산할 때 단순히 degree를 가지고 구하는 것은 합리적이지 못하다. 예를 들어, 소셜네트워크(SNS) 상에서 팔로우 수 뿐만 아니라 누가 팔로우 하고 있는지에 따라 그 사람의 유명한 정도가 정해진다. 이와 마찬가지로 문장에 대해서도 동일한 아이디어를 적용할 수 있다.

  • 본 논문에서는,

    • degree를 이용한 중심성 계산

    • PageRank를 적용한 중심성 계산

    • LexRank를 이용한 중심성 계산

  • 이렇게 총 3가지 단계에 걸쳐서 설명하고 있다.

  • 각 단계별로 예제와 같이 하나하나 살펴보도록 하자.

Degree를 이용한 Centrality 계산

  • 우선, degree를 사용하여 각 노드의 중심성에 대해 알아보도록 하자.

  • 각 노드의 degree를 사용하여 centrality를 계산하는 식은 다음과 같다.

  • 위의 식 (3)에서 는 노드 에 대한 centrality를 의미하고, 는 노드 와 연결되어 있는 노드들의 집합을 의미한다. 그리고 는 노드 에 대한 degree를 나타낸다.

  • 위의 식 (3)을 행렬 형태로 나타내면 다음과 같이 나타낼 수 있다.

  • 는 유사도 그래프에 대한 인접 행렬(adjacent matrix, )을 이용해 아래의 식과 같이 구할 수 있다.

  • 행렬 의 행의 합은 각 노드의 degree를 의미한다.

  • 위의 식들을 예제를 통해 알아보도록 하자.




    • 위의 예제에서 undirected graph를 선정한 이유는 문장과 문장간의 연결에는 방향성이 없기 때문에 undirected graph로 선정하였다. 이러한 undirected graph를 directed graph로 나타낸 것이 오른쪽 그래프이다.

    • 위의 directed graph에 대한 인접 행렬 는 다음과 같다.

    • 위의 인접 행렬 를 이용하여 식 (3)의 각 노드에 대한 centrality를 계산 해보자. 이를 계산하기 위해서는 각 노드에 대한 초기값 가 필요한데, 여기서는 로 설정하였다.

    • 위의 과정을 식(5)와 같이 행렬 형태로 나타내면 다음과 같다.

  • 위의 식 (5)을 고유값(eigenvalue)이 1이고, left-고유벡터(eigenvector) 로 이루어진 식이라고 볼 수 있다.

  • 이러한 고유벡터가 존재하기 위해서는 몇 가지 수학적 지식이 필요하다.


Markov Chain

  • 위의 식(5)가 성립하기 위해서 필요한 수학적 지식이 바로 마코프 체인(Markov Chain)이다.

  • 마코프 체인에서의 확률 행렬(Stochastic Matrix) 는 전이 행렬(Transition Matrix)이라고 한다.

  • 확률 행렬의 원소 는 마코프 체인에서의 상태(state, 노드에 해당) 에서 로 전이할() 확률을 의미한다.

  • 번의 전이에 대해 로 전이할 확률을 의미하며, 마코프 체인에서의 확률 행렬 는 다음과 같이 수렴하게 된다. 아래의 식에서 을 의미하며, Stationary distribution(고정된 확률분포?)에 해당한다.

  • Perron-Frobenius 정리에 따르면, irreducible하고 aperiodic한 마코프 체인은 위의 식(7)과 같이 확률 행렬 가 수렴(convergence)하는 것이 보장된다.

    • irreducible: 두 state 간에 이동할 수 있는 경로가 있고, 더 이상 그래프를 나눌 수 없는 마코프 체인을 의미한다. 즉 전이 행렬 에 대해 이어야 한다(자세한 설명은 여기 참고).

    • aperiodic: 어떤 state 에 대해 인 마코프 체인을 의미한다. 즉, state 로 돌아오는 주기들의 최대공약수(gcd, greatest common divisor)가 1인 마코프 체인을 말한다(자세한 설명은 여기 참고).

  • 따라서, 위의 식(6)에 대한 행렬 를 마코프 체인의 전이 행렬(Transition Matrix) 또는 확률 행렬(Stochastic Matrix)이라고 볼 수 있다.

  • 하지만, 행렬 가 반드시 irreducible하고 aperiodic한다고 보장할 수는 없다.

  • 이를 해결하기 위해, Page et al.(1998)은 그래프 내에서 임의의 노드로 이동(점프)할 수 있도록 하는 PageRank라는 알고리즘을 제안했다. 이 PageRank에서 제안한 damping factor가 바로 이러한 역할을 한다.

  • PageRank를 통해 periodic하고 reducible한 그래프가 irreducible하고 aperiodic하게 만들어 줄 수 있다.


PageRank를 적용한 Centrality 계산

  • 위에서 살펴본 PageRank를 반영한 centrality 계산식은 다음과 같다.

  • 위의 식(8)에서 은 그래프 안의 전체 노드 개수를 의미하고, 는 다른 노드로 이동할 "damping factor"를 말한다. 본 논문에서는 로 설정하였다.

  • 위의 식(8)을 행렬 형태로 나타내면 다음과 같이 나타낼 수 있다.

  • 위의 식 (9)에서 행렬 는 정방 행렬(square matrix)로 대각부분이 인 대각행렬(diagonal matrix)이다.

  • 위의 식 (9)에서 부분이 마코프 체인의 전이 행렬이 된다.

  • 마코프 체인에서 랜덤 워커(random walker)는 확률로 인접 상태(adjacent state) 중 하나를 선택하거나, 의 확률로 다른 상태로 점프하게 된다.

  • 위에서 살펴본 예제를 PageRank를 이용해 centrality를 계산하면 다음과 같다. 초기값 가 필요한데, 여기서는 로 설정하였다.

  • 위의 과정을 행렬 형태로 나타내면 다음과 같다.


LexRank를 적용한 Centrality 계산

  • 기존의 PageRank는 인터넷 상에서의 웹 페이지에 대한 링크를 directed graph로 나타내어 적용한 알고리즘이다.

  • 본 논문에서는 문장의 경우 문장간의 유사도를 계산하기 하여 그래프를 그리기 위해 식 (1)을 사용한다. 문장 간의 유사도는 방향이 없는 undirected graph 로 나타나기 때문에, 이를 위해 새로운 stationary distribution을 가지는 전이 행렬이 필요하다.

  • 본 논문에서는 이를 적용한 알고리즘인 lexical PageRank 즉, LexRank를 다음과 같이 제안 했다.

  • 본 논문에서는 LexRank를 두 가지로 나누는데,

    • 먼저, threshold 값을 통해 노드의 연결을 제한하는 LexRank

    • 그리고, threshold값이 없고, 모든 노드들이 idf-modified-cosine의 유사도로 연결되어 있는 노드에 대한 LexRank가 있다. 이 때의 Lexrank를 Continuous LexRank라고 한다.

  • 위에서 살펴본 예제를 LexRank를 이용해 centrality를 계산하면 다음과 같다. 두 문장(노드) 간의 idf-modified-cosine(imc)은 임의로 아래의 그림과 같이 설정하였고, 초기값 또한 로 설정하였다.



  • 위의 과정을 행렬 형태로 나타내면 다음과 같다.