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

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)은 임의로 아래의 그림과 같이 설정하였고, 초기값 ​또한 ​로 설정하였다.

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

LexRank Algorithm

• LexRank의 전체 알고리즘은 아래와 같다.

  • 먼저, 문장 간의 idf-modified-cosine을 구한 뒤 이를 이용하여 그래프를 구성한다.

  • 그런 다음, 마코프 체인에서 stationary distribution을 구하는 방법 중 하나인 power method를 이용해 LexRank score를 계산한다.

4. EXPERIMENT

• 본 논문에서 실험에 사용한 데이터 셋은 DUC 2003 과 DUC 2004 데이터 셋을 사용하였다.

• [Task 2]에는 뉴스 클러스터에 대한 일반적인 요약이 포함되어 있다.

  • DUC 2003은 30개의 뉴스 클러스터로 구성되어 있으며, DUC 2004는 50개의 뉴스 클러스터로 구성 되어 있다.

• [Task 4]에서는 두 개의 언어(cross-lingual)에 대한 요약이 포함되어 있다.

  • [Task 4a]는 Arabic-to-English에 대한 기계 번역이 이루어진 24개의 뉴스 클러스터로 구성되어 있다.

  • [Task 4b]는 동일한 Arabic-to-English에 대해 사람이 번역한 데이터 셋이다.

• LexRank의 성능을 평가하기 위한 척도로는 ROUGE score를 사용했다.

5. RESULTS

• 아래의 [Table 3]은 Degree를 이용한 Centrality 를 계산한 것과 LexRank, 그리고 Continuous LexRank에 대해 Task 2, Task 4에 대한 결과를 나타낸 표이다.

• 전반적으로 LexRank 및 Cont. LexRank의 ROUGE score가 높은 것을 확인할 수 있다.

• 본 논문에서는 추가적으로 Noise 데이터에 대한 실험을 진행하였다. 아래의 [Table 6]은 각 뉴스 클러스터에 랜덤한 2개의 뉴스가 포함 되었을 때의 성능을 비교한 표이다.

• 마찬가지로, LexRank 및 Cont. LexRank의 ROUGE score가 전반적으로 높은 것을 확인할 수 있다.