[paper review] TextRank: Bringing Order into Text

date

Oct 10, 2023

slug

textrank

author

status

Public

Introduction

TextRank 알고리즘은 앞서 정리한 PageRank를 Text 데이터에 적용하기 위한 variation이라고 할 수 있습니다.

본 논문에서는 Keyword Extraction과 Sentence Extraction을 위한 두개의 TextRank 방법론을 제시하고 있습니다.

Proposed approach

PageRank는 기본적으로 unweighted, directed graph 를 구성하여 vertex의 중요도를 계산합니다.

반면에 TextRank는 weighted graph와 undirected graph 또한 중요도를 계산할 수 있도록 개념을 확장하였습니다.

이는 웹 페이지에 비해 상호 복잡한 연관관계를 갖는 text data의 특성을 반영하기 위함 입니다.

따라서 TextRank의 그래프를 구성할 때에는 directed/undirected, weighted/unweighted의 형태 중 자유롭게 선택이 가능합니다.

따라서

weighted graph에서의 vertex 에 대한 중요도는 다음의 가중합 과정을 통해 계산할 수 있습니다.

각각 vertex 사이 edge에 대한 가중치는 Keyword Extraction과 Sentence Extraction 방법에 따라 각각 다르게 계산 됩니다.

TextRank를 text data에 적용하기 위해서는 그래프에 추가한 text의 형태에 상관없이 다음의 네가지 단계를 따르면 됩니다.

task에 맞는 가장 적당한 text units을 정의하여 그래프에 vertex로 추가합니다.

text unit 사이의 관계를 정의하고, vertex 사이에 edge로서 추가합니다. 이 때, edge는 앞서 설명드린대로 directed/undirected, weighted/unweighted의 형태 중 자유롭게 선택 가능합니다.

그래프가 수렴할때까지 랭킹 알고리즘을 반복합니다.

최종적으로 vertex의 중요도를 기반으로 정렬하여 ranking/selection에 사용합니다.

TextRank for Keyword Extraction

TextRank를 Keyword Extraction을 위해 사용한다면, 주어진 Text data에 대한 최종 결과는 단어 혹은 구문의 집합이 될 것입니다.

따라서 하나 이상의 어휘(lexical units)로 구성된 시퀀스(1~n gram)를 Vertex로 사용하고, Vertex 사이에 유의미한 edge를 정의하여 Keyword Extraction을 위한 중요도를 판단해야 합니다.

본 논문에서는 어휘 단위(lexical units)의 co-occurrence를 통해 TextRank 그래프의 edge를 정의하였습니다.

co-occurrence는 Window size N 이내의 동시에 출현을 고려하여 Vertex를 연결시켜 줍니다.

필터링을 통하여 원하는 조건에 맞는 단어만을 Vertex에 추가하는 방법 또한 존재합니다. 예를 들면, 오직 명사와 동사만을 vertex로 추가 하여 그래프릉 생성할 수 있을 것 입니다.

이후 과정에서 최적의 필터링 조합을 찾기 위한 실험을 진행한 결과, 명사와 형용사만을 그래프에 추가하였을 때 가장 좋은 결과를 보였다고 합니다.

정리해 보면, TextRank의 keyword extraction 알고리즘은 다음과 같이 비 지도형태로 진행됩니다.

Text를 토큰화 하고, 필터링을 위해 POS 태깅을 진행합니다.

필터링을 진행한 vertex를 그래프에 추가하고, Co-occurrence를 고려하여 edge 또한 추가합니다.

초기 vertex 중요도를 1로 설정하고 수렴할때가지 알고리즘을 반복합니다.

최종적으로 얻은 중요도를 정렬하여 Top-N개의 vertex를 문장의 keyword로 정의합니다.

본 논문에서는 그래프가 너무 커지는 것을 방지하기 위하여 n-gram이 아닌 개별 단어들만을 vertex로 추가하였습니다.

하지만 개별 키워드들을 합치는 post-processing 작업을 통해 multi-word keyword로의 변환 또한 가능하다고 합니다.

TextRank for Sentence Extraction

TextRank 알고리즘은 Sentence를 vertex로하는 그래프에 대해서도 적용이 가능합니다.

하지만 문장에 대해서는 일일이 동시출현을 고려할 수가 없습니다.

따라서 다음과 같이 두 문장 와 사이에서 동시에 출현하는 단어의 개수를 고려하여 edge를 정의합니다.

따라서 Sentence Extraction을 위한 TextRank는 문장에 중요도를 부여하는 과정과 같습니다.

정리해 보면, Sentence Extraction 과정은 다음과 같이 진행됩니다.

각 문장에 대한 인덱스를 지정합니다.

그래프에 문장을 vertex로 추가하고, 주어진 수식을 이용하여 vertex 사이의 edge 또한 정의합니다.

Vertex의 중요도를 초기화하고 수렴할때까지 알고리즘을 반복합니다.

최종적으로 정렬을 통해 중요도가 높은 문장들을 사용하여 문서에 대한 요약을 생성합니다.

Experiments

TextRank의 Keyword Extraction에 대한 검증 결과입니다. 결과를 통하여 다음의 사실들을 알 수 있었습니다.

당시 TextRank가 가장 뛰어난 F-1 score를 보였음.

window size를 늘리는 것은 역효과를 불러옴

같은 조건에서 비교해 봤을 때, directed 그래프를 활용한 모델이 Undiriected 그래프를 활용한 모델보다 성능이 좋았음.

명사, 형용사를 vertex로 사용하였을 때, 가장 성능이 좋았음.

Conclusion

TextRank는 문장 사이의 유사도와 중요도 순위를 동시에 얻을 수 있습니다.

지도학습을 위해 요약본을 얻는 것은 매우 큰 노동력이 필요합니다. 따라서 TextRank는 비지도 학습 모델이라는 장점또한 존재합니다.