본 논문은 그래프 기반의 text summarization 방법론인 TextRank에 대하여 소개하고 있습니다.
TextRank는 대표적인 그래프 기반 랭킹 알고리즘인 PageRank에 기반하여 문서 내의 키워드 추출을 가능하게 합니다.
Graph
그래프는 vertex와 edge로 구성된 유한한 자료구조 입니다. vertex는 정점, edge는 정점과 정점을 연결하는 간선을 의미합니다.
그래프 구조는 edge의 방향 유무에 따라 undirected graph(무방향 그래프)와 directed graph(유향 그래프)로 나뉩니다.
또한 엣지를 동일한 값으로 가정하는 unweighted graph와 가중치를 갖도록 하는 weighted graph(가중 그래프)가 존재합니다.
Graph-based ranking
그래프 기반의 랭킹 알고리즘은 자료구조의 한 종류인 그래프를 기반으로 합니다.
이 알고리즘은 vertex(정점)의 local한 정보만을 반영하지 않고, 전체 그래프의 global information을 재귀적으로 반영하여 vertex(정점)의 중요도를 결정하는 방법론 입니다.
그래프 기반의 랭킹 모델은 쉽게 설명하면 "voting" 혹은 "recommendation"과 같습니다.
그래프의 vertex가 다른 vertex와 연결되어 있다면, 이는 서로에게 "voting"했음을 의미합니다. 더 많은 연결은 갖는 vertex는 많은 "voting"을 받은 것으로 간주할 수 있습니다.
또한 "voting"자체의 중요도는 "voting"을 행사하는 vertex의 중요도에 의해 결정됩니다.
따라서 vertex의 중요도는 "얼마나 중요한 vertex들로 부터 voting을 받았는가"로 부터 판단이 가능합니다.
그리고 이러한 중요도는 vertex의 랭킹을 결정할 수 있는 요소가 됩니다.
PageRank
구글의 PageRank 알고리즘은 대표적인 그래프 기반의 랭킹 알고리즘 입니다.
PageRank는 directed graph \(G = (V,E)\)로 부터 아래와 같은 식을 통해 vetex \(V_i\)의 중요도를 계산합니다.
$$S(V_i) = (1-d) + d*\sum_{j \in {In(V_{i})}} {1\over |Out(V_j)|} S(V_j)$$
\(In(V_i)\)는 vertex \(V_i\) 를 가르키는 vertex의 집합을 의미하며,
\(Out(V_i\)는 vertex \(V_i\) 가 가르키는 vertex의 집합을 의미합니다.
따라서 기본적으로 vertex \(V_i\)의 중요도는 인접한 vertex의 집합인 \(In(V_i)\)에 속하는 vertex 들의 중요도를 더하여 구한다고 말할 수 있습니다.
수식을 보시면 \(S(V_j)\)에 추가적으로 \({1\over |Out(V_j)|}\)를 곱하여 \(\sum_{j \in {In(V_{i})}} {1\over |Out(V_j)|} S(V_j)\)를 계산하는 것을 확인할 수 있습니다.
이는 \(V_i\)와 인접한 vertex \(V_j\)의 edge가 많을수록 \(V_j\)의 개별 "voting" 에 대한 중요도가 희석됨을 고려하기 위함입니다.
마지막으로 \(d\)는 damping factor를 의미합니다.
PageRank는 기본적으로 웹 페이지의 중요도를 고려하기 위해 만들어진 모델입니다. edge는 웹 페이지 내의 링크를 통한 인접한 웹 페이지로의 이동을 의미합니다.
damping factor \(d\)는 edge를 통해 주어진 그래프에서 인접한 다른 vertex로 이동할 확률을 모델링하여 줍니다.
웹 서핑을 할 때에는 기존에 고려하지 않은 새로운 페이지로의 이동 확률 또한 존재합니다.
수식의 \(1-d\)는 이러한 "random surfing" 확률을 모델링 한 것 입니다. d는 확률값으로 0~1의 값을 가질 수 있는데, PageRank에서는 0.85를 damping factor로 사용하였습니다.
PageRank의 학습은 임의의 Vertex 중요도값에서 시작하여 기준치를 달성할 때 까지 재귀적으로 진행됩니다.
iteration \(k\)에서의 Error 는 \(S^{k+1}(V_i) - S^k(V_i)\)로 계산할 수 있습니다.
이 때 그래프의 수렴은 중요도의 초기값에는 영향을 받지 않고, 오로지 반복 횟수에만 영향을 받게 됩니다.
directed/undirected, weighted/unweighted를 모두 고려한 다음 4가지 모델의 결과가 이러한 사실을 잘 보여주고 있습니다.
1.TextRank
TextRank 알고리즘은 PageRank를 Text 데이터에 적용하기 위한 variation 구조라고 할 수 있습니다.
본 논문에서는 Keyword Extraction과 Sentence Extraction을 위한 두개의 TextRank 방법론을 제시하고 있습니다.
Model architecture
PageRank는 기본적으로 unweighted, directed graph를 구성하여 vertex의 중요도를 계산합니다.
$$S(V_i) = (1-d) + d*\sum_{j \in {In(V_{i})}} {1\over |Out(V_j)|} S(V_j)$$
반면에 TextRank는 weighted graph와 undirected graph 또한 중요도를 계산할 수 있도록 개념을 확장하였습니다.
이는 윕 페이지에 비해 상호 복잡한 연관관계를 갖는 text data의 특성을 반영하기 위한 것입니다.
따라서 TextRank의 그래프를 구성할 때에는 directed/undirected, weighted/unweighted의 형태 중 자유롭게 선택이 가능합니다.
weighted graph를 고려한다면, vertex \(V_i\)에 대한 중요도는 다음의 가중합 과정을 통해 계산할 수 있을 것 입니다.
$$WS(V_i) = (1-d) + d*\sum_{V_j \in {In(V_{i})}} \frac{w_{ji}}{\sum_{V_k\in{Out}(V_j)} w_{jk}} WS(V_j)$$
각각 vertex 사이 edge에 대한 가중치는 Keyword Extraction과 Sentence Extraction 방법에 따라 각각 다르게 계산 됩니다. 이는 이후의 과정에서 자세히 설명드리도록 하겠습니다.
TextRank를 text data에 적용하기 위해서는 그래프에 추가한 text의 형태에 상관없이 다음의 네가지 단계를 따르면 됩니다.
1) task에 맞는 가장 적당한 text units을 정의하여 그래프에 vertex로 추가합니다.
2) text unit 사이의 관계를 정의하고, vertex 사이에 edge로서 추가합니다. 이 때, edge는 앞서 설명드린대로 directed/undirected, weighted/unweighted의 형태 중 자유롭게 선택 가능합니다.
3) 그래프가 수렴할때까지 랭킹 알고리즘을 반복합니다.
4) 최종적으로 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 알고리즘은 다음과 같이 비 지도형태로 진행됩니다.
1) Text를 토큰화 하고, 필터링을 위해 POS 태깅을 진행합니다.
2) 필터링을 진행한 vertex를 그래프에 추가하고, Co-occurrence를 고려하여 edge 또한 추가합니다.
$$WS(V_i) = (1-d) + d*\sum_{V_j \in {In(V_{i})}} \frac{w_{ji}}{\sum_{V_k\in{Out}(V_j)} w_{jk}} WS(V_j)$$
3) 초기 vertex 중요도를 1로 설정하고 수렴할때가지 알고리즘을 반복합니다.
4) 최종적으로 얻은 중요도를 정렬하여 Top-N개의 vertex를 문장의 keyword로 정의합니다.
본 논문에서는 그래프가 너무 커지는 것을 방지하기 위하여 n-gram이 아닌 개별 단어들만을 vertex로 추가하였습니다.
하지만 개별 키워드들을 합치는 post-processing 작업을 통해 multi-word keyword로의 변환 또한 가능하다고 합니다.
TextRank for Sentence Extraction
TextRank 알고리즘은 Sentence를 vertex로하는 그래프에 대해서도 적용이 가능합니다.
하지만 문장에 대해서는 일일이 동시출현을 고려할 수가 없습니다.
따라서 다음과 같이 문장 \(S_i = w_1^i, w_2^i, \ldots, w_{N_i}^i\), \(S_j = w_1^j, w_2^j, \ldots, w_{N_j}^j\) 사이에서 동시에 출현하는 단어의 개수를 고려하여 edge를 정의합니다.
$$Similarity( S_i, S_j) = \frac{|\{ w_k | w_k \in S_i\ \And \ w_k \in S_j \} |}{\log(| S_i |) + \log(|S_j|) }.$$
따라서 Sentence Extraction을 위한 TextRank는 문장에 중요도를 부여하는 과정과 같습니다.
정리해 보면, Sentence Extraction 과정은 다음과 같이 진행됩니다.
1) 각 문장에 대한 인덱스를 지정합니다.
2) 그래프에 문장을 vertex로 추가하고, 주어진 수식을 이용하여 vertex 사이의 edge또한 정의합니다.
$$Similarity( S_i, S_j) = \frac{|\{ w_k | w_k \in S_i\ \And \ w_k \in S_j \} |}{\log(| S_i |) + \log(|S_j|) }.$$
3) Vertex의 중요도를 초기화하고 수렴할때까지 알고리즘을 반복합니다.
4) 최종적으로 정렬을 통해 중요도가 높은 문장들을 사용하여 문서에 대한 요약을 생성합니다.
2.Results
result 1.
TextRank의 Keyword Extraction에 대한 검증 결과입니다. 결과를 통하여 다음의 사실들을 알 수 있었습니다.
1) TextRank가 가장 뛰어난 F-1 score를 보였음.
2) window size를 늘리는 것은 역효과를 불러옴
3) 같은 조건에서 비교해 봤을 때, Undiriected 그래프를 활용한 모델이 directed 그래프를 활용한 모델보다 성능이 좋지 못했음
4) 명사, 형용사를 vertex로 사용하였을 때, 가장 성능이 좋았음.
result 2.
두번째는 Sentence Extraction에 대한 실험 결과입니다.
비교를 위한 지표로는 ROUGE score가 사용되었습니다. ROUGE score에 대한 자세한 설명은 아래의 글을 참고 부탁드립니다.
[자연어처리][Metric] ROUGE score : Recall-Oriented Understudy for Gisting Evaluation
ROUGE ROUGE(Recall-Oriented Understudy for Gisting Evaluation)는 text summarization, machine translation과 같은 generation task를 평가하기 위해 사용되는 대표적인 Metric입니다. 본 글의 내용은 ROUGE s..
supkoon.tistory.com
결과를 통해 TextRank를 사용한 Sentence Extraction(Document summarization)이 가장 좋은 성능을 보이지는 못했지만, 꽤나 좋은 성능을 보였다는 사실을 알 수 있습니다.
또한 정답을 학습하는 기존의 지도학습 모델들과 다르게, TextRank는 비지도 학습만을 필요로 한다는 장점이 존재하였습니다. 또한 TextRank는 문장 사이의 유사도와 중요도 순위를 동시에 얻을 수 있다는 점에서 우수한 모델임을 알 수 있었습니다.
마무리
TextRank는 그래프 기반의 랭킹 알고리즘으로 PageRank 알고리즘을 Text Data에 적용한 Variation 구조라고 할 수 있습니다.
TextRank는 TextData를 활용하여 그래프를 구성하였으며, 비지도 학습만으로 keyword extraction과 sentence extraction에서 매우 좋은 성능을 보여주었습니다. 논문이 전체적으로 어렵지 않았으며, 읽는 과정에서도 TextRank가 데이터에 간편하게 적용될 수 있을 것 같다는 생각이 들었습니다. 그래프 기반의 방법을 처음 리뷰해보면서 새로 배우게 되는 부분이 많았던 것 같습니다. 감사합니다.