[ASAC 0704] WWH3 : [논문 리뷰] TextRank

 

TextRank란?

• 문서 집합을 요약하는 방법으로 키워드와 핵심 문장을 선택하는 extractive methods를 이용할 수 있다.
• TextRank는 word graph나 sentence graph를 구축한 뒤, Graph ranking 알고리즘인 PageRank를 이용하여 키워드와 핵심 문장을 선택한다.
• Unsupervised approach의 방법으로 텍스트의 도메인 영역, 언어에 구애받지 않고 적용할 수 있는 알고리즘이다.
• 성능 대비 간편하여 키워드 및 핵심 문장 추출에 있어서 공부할 가치가 있는 알고리즘

 

기본 개념 : 그래프 이론(directed, weighted)

TextRank 알고리즘은 Page-rank라는 그래프 기반 랭킹 알고리즘을 텍스트에 적용한 일종의 page-rank 알고리즘의 variation이다.

그래프 이론에 바탕하여 점수를 측정하기 때문에, 간단한 개념 몇 가지를 짚고 넘어간다.

 

 

그래프의 기본적인 구조는 노드와 이를 연결하는 엣지로 이루어짐.

Page-rank에서는 노드가 웹페이지가 되고 엣지는 참조링크(하이퍼링크)의 유무가 된다. TextRank에서는 단어 혹은 문장이 노드, 둘 간의 연결도(co-occurrance 혹은 similarity)로 엣지를 형성한다.

그래프의 종류는 다음의 개념에 따라 나눠진다.

1. Directed, Undirected : 방향 유무
2. Weighted, Unweighted : 가중치 유무

방향 /무방향 그래프인지, 가중치가 있는지 없는지에 따라 점수 산정이 달라진다.

TextRank의 경우 그래프의 종류에 상관없이 모두 적용 가능하다. 예를 들어 무방향(Undirected) 그래프의 경우 연결 하나를 서로에 대한 방향 엣지(Edge) 2개를 가지는 방향(directed) 그래프로 변환이 가능하기 때문이다. 또한, 가중치(weighted)의 경우 존재하는지 않는지에 따라 각각 키워드 추출, 핵심 문장 추출에 따로 적용할 수 있다.

 

1. TextRank 알고리즘

1-1. 키워드 추출

단일 문서의 키워드 추출(keyword extraction)을 위해 텍스트를 Undirected, Unweighted(혹은 빈도에 따른 weighted)그래프로 바꾼다. 이를 위한 과정은 간단하게 표현하여 다음의 3단계로 이뤄진다.

1. 단일 문서 텍스트를 토큰화하고 품사 부착을 하는 전처리 과정
2. 각 토큰은 그래프의 노드가 된다. 이와 동시에 노드 간 엣지는 노드의 co-occurance(공기) 빈도에 따라 엣지가 추가되고, 가중치가 매겨진다. (논문에서의 공기의 기준은 window에 따라 2~10 gram 사이다)
3. 만들어진 그래프에 기반하여 page-rank 수식을 반복적으로 적용해 점수를 수렴시킨다.

이렇게 해서 산출된 점수를 기반으로, 상위 키워드를 선택하여 추출이 완료된다.

 

이 이미지는 page-rank의 기본 적인 수식이다.

 

이 이미지는 page-rank를 weight가 추가된 그래프에 활용한, text-rank 논문에서 제시된 수식이다.

 

1번 수식부터 살펴보면, 연겨된 주변 노드들(Vj)의 점수가, 점수를 계산하고자 하는 노드(Vi)의 점수를 산정한다. 즉 재귀적(recursive)적으로 점수를 산정한다. 이때 d는 damping factor로, 주변 노드의 점수가 해당 노드의 점수에 미치는 영향을 조절하는 계수이다.

 

page-rank는 기본적으로 웹 사이의 관계를 표현하므로 이는 random surfe model 관점에서 주변 웹사이트에서 해당 웹사이트로 건너갈 확률을 나타낸다. (1-d)는 다른 웹사이트로 가버릴 확률을 나타낸다. 즉, TextRank 과점에서는 웹사이트가 단어로 바뀐 것 뿐, 크게 다른 의미가 없다. 일반적으로 .85의 값을 설정하며, 논문에서도 동일한 값을 사용하였다.

 

주변 노드의 점수는 주변 노드가 계산하고자 하는 노드(Vi)말고도 다른 노드로 빠져나가는 계수로 나누어져 더해진다. 이를 통해 특정한 주변 노드(Vj)가 점수를 계산하고자 하는 노드(Vi)를 얼마나 중요하게 여기는지 고려할 수 있게 된다.

 

2번 수식은 가중치가 포함된 것을 제외하면 동일하다. 만약 키워드 추출 과정에서 공기어의 빈도를 가중치로 두고 계산하게 된다면, w에 각 노드 간 공기 빈도가 들어가면 된다. 

 

추가적으로 본 논문에서는 일반적으로 20~30번 정도의 반복적인 수식적용이면 점수의 연속적인 변화가 임계치(threshold)1e-4보다 작게 떨어지며 수렴한다고 본다. (networkx의 page-rank 힘수는max-iteration이 100이다.)

 

만약, 공기어 빈도를 가중치로 두지 않은, 무방향(Undirected)그래프라면 초기 가중치를 1로 두고 수식을 적용한다. 이는 곧 수식 1과 다름이없다.

04년 기준 키워드 추출 알고리즘 SOTA인 Supervised learning 알고리즘보다 Precision과 F-measure의 값이 잘 나온다는 것을 확인할 수 있다.

 

주목할 점은, TextRank 알고리즘은 Unsupervised approach라는 점이다.

 

 

1-2. 핵심 문장 추출

적용되는 수식은 키워드 추출과 동일하다. 단, 문장의 경우 오로지 방향 그래프로 제작된 후 랭크가 매겨진다. 재밌는 것은 문장 간의 연결인 엣지(edge)를 무엇으로 표현하는가 인데, 단어의 공기어(co-occurance)는 문장의 경우 적용하기에는 문장과 같은 비교적 큰 단위의 텍스트 간 관계를 잘 표현한다고 보기 어렵다. 따라서 문장 간 유사도(similarity)가 엣지값을 이룬다.

따라서 텍스트의 모든 문장은 노드가 되고, 각 문장들의 유사도가 엣지의 가중치값이 된, 일종의 fully-connected 그래프 된다.

1-2-1. 문장 간 유사도(similarity)의 이해

 

 

두 문장 Si,Sj의 유사도는 두 문장에 공통으로 등장하는 토큰(단어)의 갯수를, 두 문장의 길이의 합으로 나눈 값으로 비교적 단순하게 계산된다. 논문에서는 이외에도 Strin kernels, Cosine similarity, longest common subsequent 등이 유사도 계산에 사용될 수 있음을 언급한다.

 

1-2-2. 평가

비지도 접근임에도 불구, 해당 연도 기준 ROUGE 점수가 basic부터 stemmed, stemmed no-stopwords 모두 baseline 점수를 초과했고 다른 상위 시스템 점수와 비교했을 때도 크게 밀리지 않는다.

Document Understanding Evaluations 2002 (DUC, 2002)라는 태스크에 참여한 다른 상위 5개의 시스템(알고리즘)과 DUC에서 제공한 baseline과 비교한 테이블

 

 

1-3. 의의

TextRank 알고리즘은 주어진 텍스트를 기반으로 그래프를 자체적으로 형성하여 점수를 측정하는 비지도 접근방식으로, 텍스트의 로컬리티에 구애받지 않는다는 장점이 있다. 간단한 수식과 재귀적인 반복 적용으로 단어나 문장의 중요도를 계산한다는 점에서 가볍고도 준수한 성능의 알고리즘이다. 물론, 텍스트 응집력에 기반한 노드 간 연결이, 실제적인 인간의 담화(텍스트) 이해 모델에 근사할 것이라는 가정 하에, TextRank 알고리즘을 통한 중요도 산출은 의미를 실제적인 의미를 가진다.

 

다시 말해서 위 가정 하에서, TextRank는 깊은 언어적 지식이나 특정 도메인의 언어자료를 필요로 하지 않는, 간편하고도 준수한 성능의 키워드/핵심문장 추출 알고리즘이라 할 수 있다.