TextRank_Original_Paper

Posted on | In |

TextRank, Original Paper

Abstraction

TextRank - Graph-based ranking model를 소개할 것이며, Text 속에서 키워드와 문장을 추출해내는 비지도적 기법에 대하여 논할 것이다.

1. Introduction

  • Kleinberg’s HITS algorithm
  • Google’s PageRank 와 같은 그래프 기반 랭킹 알고리즘은 다양한 부문의 구조를 파악하는데에 기여를 하였다. 개별 Webpage에 대하여 일일이 내용에 대한 분석을 하는 대신 웹 구조를 통한 랭킹 시스템을 구축할 수 있게 되었다. 즉, 그래프 기반 랭킹 알고리즘은 global 그래프 정보를 재귀적으로 계산하여 그래프 Vertex의 중요도를 나타낼 수 있게 되었다.

위와 같은 논리로 자연어 문서에 적용하여, 문서에서 추출된 정보에 대한 순위를 매길 수 있을 것이다. 이로써,

  • Automated extraction of keyphrases
  • Extractive summarization
  • Word sense disambiguation 등을 처리할 수 있을 것이다.

본 논문에서는 “자연어 텍스트의 그래프로부터 그래프 기반 랭킹 모델, TextRank” 를 소개하고자 한다. 특히,

  • (Unsupervised) Keyword extraction
  • (Unsupervised) Sentence extraction 을 살펴볼 것이다.

2. The TextRank Model

Basic Idea

그래프 기반 랭킹 알고리즘는 전체 그래프의 전역 정보를 재귀적으로 취급하여 Vertex의 중요도를 결정하는 기법이다. 이 기법의 가장 기본적인 아이디어는 Voting 또는 Recommendation이다. 하나의 Vertex가 다른 것에 연결이 된다면, 기본적으로 vote를 하는 것이다. 이렇게 표가 많이 쌓이면 해당 Vertex는 중요도가 높아지는 것이다. 또한 단순히 투표를 하는 것이 중요한 것이 아니라, 투표를 하는 Vertex에 따라 중요도가 결정이 된다. 예를 들어, 본인이 어느날, 인스타그램의 게시물을 올렸는데 갑자기 유재석이 자신의 게시물에 좋아요를 눌렀다고 생각해보자. 해당 좋아요는 당신의 동네친구들이 눌러주는 좋아요보다 큰 의미를 가질 것이다.

Vertex Score Influenced by

즉, Vertex의 점수는,

  1. 받은 투표의 갯수
  2. 투표를 한 Vertex의 영향력 으로 결정된다.
Graph, In and Out

$G = (V, E)$를 방향성 그래프로 놓고, $V$를 Vertex 집합, $E$를 Edge 집합으로 설정한다. 그리고 $E$는 $V * V$의 subset이다. $V_i$를 예시로 들면, In($V_i$) = $V_i$’를’ 향하는 Vertex들 (predecessors) Out($V_i$) = $V_i$’가’ 향하는 Vertex들 (successors) 로 생각할 수 있다.

Vertex Score Formula

PageRank의 이론에 따르면 Vertex $V_i$의 점수는 다음과 같다.

Damping factor, d

d는 damping factor로서 0~1의 값을 갖는다. 이의 의미는 하나의 Vertex에서 다른 Vertex로 이동해버리는 확률을 말한다. 웹 서핑의 관점에서, 이 그래프 기반 랭킹 알고리즘은 “Random surfer model”을 적용하며,

  • d = 유저가 link들을 random으로 클릭할 확률
  • 1-d = 새로운 페이지로 jump할 확률 이다. d는 보통 0.85(Brin and Page, 1998)로 세팅이 되며, 본 논문에서도 그렇게 진행한다.

처음에 이 표현이 되게 와닿지 않았던 것이, “다른페이지로 이동할 확률 = 하나의 vertex에서 다른 vertex로 이동할 확률 = 링크를 클릭할 확률”이라고 생각했기에 1-d가 d랑 무슨 차이가 있는지 모르겠었다. 이 개념은 가볍게 지나쳤던 “Random Surfer Model”을 알고 있어야 이해할 수 있다.

그래프 각 노드에 임의의 값을 할당하는 것으로 시작되어, 계산 iteration이 convergence가 기준 threshold 아래에 있을 때 멈추게 된다. 알고리즘 후에 각 vertex의 점수가 산출되고 이는 vertex의 중요도를 의미하게 된다. TextRank의 결과값은 initial value에 의해서 변하기보다는 convergence에 도달하는 iteration에 의해 결정된다.

비록 본 논문의 TextRank는 Google의 PageRank로부터 기원하지만, HITS나 Positional Function 또한 TextRank model에 융합될 수 있다.

2.1 Undirected Graphs

비록 전통적으로는 방향성 그래프에 적용이 되었지만, 무방향성에서도 가능하며, 이때는 In과 Out의 value가 같게 된다. 노드와 엣지의 숫자가 거의 비슷한 ‘느슨한 그래프’와 같은 경우에는 무방향성을 사용했을 때 convergence가 좋을 수 있다. Figure 1은 랜덤 생성된 250개의 vertex와 edge를 담은 그래프의 convergence 그래프를 나타낸 것이다 (convergence threshold 0.0001). 그래프의 연결성이 높아질수록(edge가 많아질수록) convergence는 몇번만의 반복으로 달성이 되고 방향성과 비방향성 그래프의 수렴 커브는 비슷하다.

2.2 Weighted Graphs

웹서핑 관점에서는 다른 웹사이트에 대해서 다중 링크, 부분 링크를 달아놓는 경우가 없다. 다른 웹사이트에 대한 링크를 걸어두면 한개만 걸어두지 반복적으로 여러개를 걸어두는 일은 없지 않는가? 따라서, PageRank 정의에서는 unweighted graph를 산정한다. 하지만 우리의 모델은 자연어에 기반하므로, vertex간의 다중링크, 부분링크들이 존재할 수 있다. 따라서 모델에 “strength” 개념을 포함시켜서 두 Vertex $V_i$, $V_j$의 연결을 표현하고 이를 $w_{ij}$로 나타낸다.

결과적으로 우리는 그래프에서 간선의 가중치를 포함하는 그래프 기반 랭킹 시스템 공식을 소개하고자 한다.

[Figure 1]에서 section 2.1에서 사용된 같은 convergence curve를 그리며, 0-10의 random weight를 갖는다. Unweighted 그래

2.3 Text as a Graph

자연어에 그래프 기반 랭킹 알고리즘을 적용하기 위하여, 자연어를 표현하는 그래프를 만들어야 하고, 이는 단어와 자연어들을 의미있는 관계로 연결해야 한다. 적용 방식에 따라서, text의 단위는 단어, 연어, 문장 전체 등 다양하게 정의될 수 있따. 비슷하게, 관계의 단위 역시 lexical, semantic, contextual 등 다양하게 구성할 수 있다.

그래프에 더해지는 요소들의 타입에 관계없이, 자연어 문서에 적용되는 그래프 기반 랭킹 알고리즘은 다음의 세 개의 주요 단계를 거친다:

  1. 목적을 가장 잘 반영하는 text unit을 정의하고 그래프의 vertex로 담는다.
  2. text unit을 연결하는 relation을 정의하여 vertex들의 edge로 만든다. Edge는 방향성, 무방향성, 가중, 비가중으로 만들 수 있다.
  3. Convergence까지 그래프 기반 랭킹 알고리즘을 돌린다.
  4. Vertex를 최종 점수로 정렬한다.

이를 통해 우리는, (1) Keyword extraction task: 텍스트의 주요 단어를 추출 (2) Sentence extraction task: 주요 문장을 추출하여, 추출 요약으로서 활용

3. Keyword Extraction

키워드 추출은 문서를 가장 잘 표현하는 핵심 키워드를 자동적으로 나타내는 방법이다. 이런 키워드들은 문서 집합들의 index, 간결한 요약 등 다양한 역할을 띌 수 있다. 또한 전문용어 추출이나 도메인 사전을 구축하는데에도 사용될 수 있다. 사실 가장 간단한 방법은 가장 많이 나타난 단어를 대표 단어로 사용하는 ‘빈도적’ 관점을 생각해볼 수 있다. 하지만 이는 결과가 안 좋았기에 다른 방식으로 넘어간 것이다. 이 분야의 SOTA는 현재 supervised learning 기법으로서, lexical과 syntatic 특징을 통해 키워드를 알아내고자 한다(물론 이 논문이 매우 옛날에 나온 논문이라 무시해도 된다).

3.1 TextRank for Keyword extraction

TextRank의 예상 결과는 주어진 text에 대하여 대표적인 단어나 구를 내뱉는 것이다. 따라서 랭킹 매겨지는 단위는 단어 하나 또는 여러개의 sequence이며, 이들은 vertex로서 표현되어 text graph에 더해진다. 또한 두 lexical unit 사이의 관계는 edge로서 표현될 것이다. 우리는 co-occurrence relation을 사용하여 두 단어가 일정 거리 내에서 함께 나타나는 것을 표현할 것이다. 두 vertex가 연결되어 있다면 최대 N 단어 window에서 함께 등장하는 것이며, N은 2~10개의 단어로 나타낸다.

Vertex들은 syntactic filter로 그래프에 제한적으로 들어오게 된다. 필터를 통해 특정 언어 요소들만 포함하는데 예를 들면 명사만, 동사만 출입 가능하게 만들 수 있다.

TextRank Keyword extraction algorithm Process: 1) 텍스트가 토크나이징 된 후에 POS 태깅을 진행한다(synthetic filter). 2) 그래프 사이즈의 지나친 성장을 막기 위하여 하나의 단어만을 Vertex로 사용한다(N-gram 사용 x / Multi word keyword는 post-processing). 3) Lexical Unit, Syntactic Filter 적용 –> Graph Vertex 4) N개 단어 window에 대하여 edge 설정 5) Vertex Score는 1로 초기화 6) TextRank 알고리즘을 적용하고 보통 20-30 반복 / 0.0001 threshold

3.2 Evaluation

Discussion

4. Sentence extraction

TextRank의 다른 적용은 자동요약을 위한 문장 추출이다. 이는 사실 키워드 추출과 비슷한 문제를 갖는 것이, 텍스트 내에서 가장 대표적인 연속체를 찾고자 하는 것이기 때문이다. 키워드 추출에서는 단어나 구를 포함하고 있지만 문장 추출은 전체 문장을 다루고 있다. TextRank는 이런 문제에 굉장히 능한것이 “전체” text에서 가져온 정보들을 토대로 랭킹을 따지기 때문이다.

4.1 TextRank for Sentence Extraction

TextRank를 구성하기 위해선 그래프의 vertex가 순위가 매겨져야 하는 unit이다. 문장 추출을 위해선 해당 노드들이 문장으로 구성되어야 한다. 하지만 keyword 추출에 사용되었던 co-occurence relation은 문장에서는 사용이 불가한데 애초에 길이 자체가 매우 크기 때문이다. 대신에 다른 관계를 구축해야 하는데 이를 “similarity”로 나타낸다. 이 similarity는 두 문장의 overlap으로 표현한다. 이런 두 문장의 관계를 “Recommendation”이라고 하며 한 개념을 다루는 하나의 문장을 만났을 때, 같은 내용을 다루는 다른 문장은 같은 개념을 다룰 것이라는 가정 때문에 추천이라고 부르게 되었다.

두 문장의 overlap은 단순히 두 문장이 공유하고 있는 어휘 표현의 수로 나타낼 수도 있다. 또는 syntatic filter를 통해 명사, 동사 등 원하는 속성만을 대상으로 할 수도 있다. 그리고 긴 문장에 대한 영향을 피하기 위해 정규화를 진행하며 두 문장의 overlap을 두 문장의 길이로 나눈다.

공식으로 보면, $N_i$ 단어로 이루어진 $S_i$와 $S_j$ 두 문장이 있을 때, 다음과 같이 표현할 수 있다. 수식만 봤을 때는 $S_i$의 절대값을 씌운 것이 왜 나왔나 싶었는데, 절대값이 아니라 길이였던 것이다…