'content overlap'에 해당되는 글 1건

요약을 추출하는 알고리즘은 전형적으로 구문 추출에 대한 기술에 기반을 둔다. 그리고, 그러한 구문 셋을 인식하고자 하는 시도는 주어진 하나의 문서에 대한 이해에 있어서 굉장히 중요하다. 

요약을 추출하기 위해 많은 알고리즘들은 언어 지식에 의지를 많이 하고 있으며, 특히, 다른 언어로 이루어진 문서에 대해서는 상당히 많은 수정을 해야한다.
게다가 성능을 측정하기 위해서 다듬어진 데이터 셋을 통해 자신만의 편리성을 추구하는 경우도 많다.
TextRank는 이러한 제약에서 자유롭다고 볼 수 있다.
특징은 다음과 같다.

일반 랭킹 알고리즘은 각 문서들을 하나의 정점(Vertex)로 바라보지만, TextRank는 하나의 문서에서 각 sentence를 하나의 정점(Vertex)으로 인식을 한다.
또한, incoming, outgoing의 의미도 incoming은 다른 sentence에 현재 sentence에 존재하는 word가 있는지를 체크하고, outgoing도 마찬가지로 현재 sentence에서 다른 sentence에 word가 존재하는지를 체크한다. 이것을 content overlap이라 표현한다.

이 과정에서 몇가지 선행이 되어져야 한다. punctation 문자라든지, stopwords(불용어)에 대한 처리를 미리해야 된다. 굳이 의미없는 word는 삭제하겠다는 의미이다.

일단, 여러 랭킹 알고리즘 가운데 PageRank와 HITS에 포커스를 맞춰 살펴본다.

PageRank는 아마도 가장 유명한 알고리즘 중 하나이며, Web-link 분석에 대한 방법으로서 디자인되어졌다. 다른 그래프 랭킹 알고리즘과 달리 PageRank는 하나의 싱글 모델에 incoming과 outgoing 링크의 impact를 통합한다. 따라서, Score는 하나의 셋만 도출한다.

Out(Vj)는 그래프의 j번째 정점(Vj)에서 outgoing되는 edge의 개수.

이 결과에 d는 0과 1사이로 셋팅하는 파라메터이며, random walking model내에 random jump에 대한 임무를 지녔다. d는 일반적으로 0.85로 셋팅하는 걸로 되어 있다.

위 PageRank 식을 TextRank에 적용하면 다음과 같다.

이 등식 중 이 부분의  의미는 Vi로 outgoing하는 Vj에 incoming하는 정점의 weight들의 합계를 Vj의 pagerank의 값을 나눈 값에 weight를 곱한 것이다.
등식을 이해하는 것에 별 어려움이 없어 보인다.

HITS는 authority의 정도에 따라 Web Page를 랭킹하고자 디자인된 반복적인 알고리즘이다. HITS 알고리즘은 authority와 hubs를 구분한다.
"authority"는 incoming 링크를 가진 페이지로, "hubs"는 outgoing 링크를 가진 페이지로 정의한다.
각 정점에 대해서, HITS는 "authority" score와 "hubs" score라는 2개의 셋을 산출한다.

위 HITS 식을 TextRank에 적용하면 다음과 같다.
HITS 알고리즘은 incoming 랭킹 값이 우선시 되고, incoming 랭킹 값이 같을 경우 outgoing 랭킹 값을 비교한다.

그런데, PageRank나 HITS 알고리즘에서 기존 정점에 대한 랭킹은 어떻게 알까?
즉, 등식을 보더라도 PR(Vj)와 HITS(Vj) 값을 이용하게 된다. 그렇다면 이 값은 어떻게 알아내는 것일까?
답은 쉽다. 초기값을 0에서 1사이의 값으로 임의의 배정을 한 후 위 식들을 대입하되, 벡터간의 거리가 threshold 값에 근접(convergence)할 때까지 반복한다. 단, HITS는 쉽게 convergence가 되지 않는 경우도 발생하므로, 최대 10~20까지만 반복하는 조건이 필요하다.
일반적으로 threshold는 0.01 내지 0.001를 사용한다.

유사성(similarity)는 content overlap을 통해 획득하게 되는데, abusing 데이터를 처리하기 위해 normalization을 하게 된다.

분모에서 log 함수를 사용하는 것은 abusing 데이터를 처리하기 위한 normalization 작업이며, Wk는 두 sentence에 모두 존재하는 word이며 분자는 그런 word들의 개수가 된다.

이 정도만 알고 있다면, TextRank에 대한 구현은 어려운 문제는 아니다.
Matrix를 작성하고, 각 (i, j)의 값에 랭킹(PR(Vi), HITS(Vi), HITS(Vj))를 구하고, threshold값에 근접할 때까지 반복하기만 하면 된다. 단, 주의 사항은 PageRank에 대한 TextRank 등식을 보면 루프 구문을 3번 돌아야 한다. 한 문서에 1,000개의 구문이 존재한다면, 1,000 X 1,000 X 1,000 번의 루프를 돌아야 하는 비효율적이나, 등식을 잘 보면 1,000 X 1,000 + 1,000으로 변경할 수 있다.

다음은 TextRank를 구하기 위한 전체적인 알고리즘 diagram이다.


많은 연구 결과에서 요약에 대한 결과는 만족스러운 수준으로 나왔고, 사람의 눈으로 확인한 결과만큼이나 괜찮은 결과를 획득했다고 했다.

나 또한, 직접 프로그래밍을 한 후 그 결과를 확인해보고 깜짝 놀랄 말했다. 영어 문서이든 한글 문서이든 상당한 결과를 볼 수 있었다.

** 관련 글 **
http://www.aclweb.org/anthology-new/P/P05/P05-3013.pdf
http://www.aclweb.org/anthology-new/P/P04/P04-3020.pdf
http://www.icmc.usp.br/~taspardo/NAACL07-LeiteEtAl.pdf
http://users.dsic.upv.es/~dpinto/miniproject/ProjectTextRank.pdf