텍스트 요약
문서를 요약하는 방법으로는 크게 두 가지로 나뉘어진다.
1. 추출적 요약(Extractive Summarization)
: 기존 문서에서 중요도가 높은 문장 그대로 추출하여 요약하는 방식으로, 새로운 단어나 문장이 생성되지 않는다.
2. 추상적 요약(Abstractive Summarization)
: 새로운 단어나 문장을 생성하여 요약을 하는 방식으로 조금 더 사람이 요약하는 방법에 가깝다고 할 수 있다.
TextRank(텍스트랭크)
TextRank는 텍스트 요약 방법 중, 추출적 요약에 속하는 대표적인 알고리즘이다. TextRank는 문서 집합을 요약하는 방법으로 키워드와 핵심문장을 선택하는 방법이다. 2004년에 제안되었으며, 구글의 검색엔진의 핵심인 RageRank(1998)를 기반으로 한 알고리즘이다.
PageRank
TextRank를 보기 전에 PageRank 알고리즘을 알아보자. PageRank는 세르게이 브린과 래리 페이지가 쓴 PageRank논문(1998)-The Anatomy of a Large-Scale Hepertextual Web Search Engine 에서 처음 소개되며 구글이라는 회사의 시초가 되었다. 현재까지도 구글 검색엔진의 핵심으로 사용된다.
검색결과로 더 의미있는 페이지를 보여주는 것이 필요했고, 이 둘은 웹페이지 사이의 연결 관계가 유용한 정보를 제공해줄 수 있다는 점에 집중했다. 구글은 바로 이러한 링크 구조와 링크가 달린 텍스트를 이용했다.
학술문헌의 경우, 특정 페이지에 대한 인용 수를 세는 방식으로 그 페이지의 중요도를 추청하는데, PageRank는 모든 페이지의 링크를 동일하게 계산하기보다 페이지의 링크 수로 정규화하여 사용한다.
수식은 아래와 같다.
PR(A)는 'A'라는 웹페이지의 페이지 랭크를 의미한다. T1, T2, .. Tn은 그 페이지를 가리키는 다른 페이지들을 의미한다. C(T1)은 T1 페이지가 가지고 있는 링크의 총 개수를 의미한다. d는 Damping Factor라고 한다.
d =1 이라 가정하고 보면, 위 수식은 'A의 페이지 랭크는 그 페이지를 인용하고 있는 다른 페이지 T1, T2, .. Tn이 가진 페이지 랭크를 정규화시킨 값' 을 의미한다. 즉, A의 페이지 랭크는 A페이지를 가리키는 다른 페이지의 페이지 랭크 값이 높을수록 더 높아진다.
여기에서 '정규화시킨다'는 의미는 페이지 랭크의 단순 합산이 아닌, T1에서 만약 페이지 랭크가 높더라도, 그 페이지에서 링크를 엄청 많이 달았다면
(=C(T1)값이 높다면)그 페이지가 기여하는 비중은 낮아진다는 의미다.
d=0 이라 하면, 모든 페이지의 PageRank값은 1이 되어 아무런 의미가 없다. d(Damping Factor)는 0에서 1 사이의 값을 가지며, 어떤 사람이 마구잡이로 웹서핑을 하여 한 페이지에 만족을 못 하고 다른 페이지로 가는 링크를 클릭할 확률로, 이어지는 페이지를 무한히 클릭한다는 것이다. 논문에서는 실험을 통해 0.85로 설정했다고 했다. d = 0.85이면, 85%확률로 다른 페이지를 클릭할 것이라는 것이다.
한 페이지의 PageRank를 구하기 위해 다른 PageRank값이 필요하고, 그 값을 구하기 위해 또 다른 PageRank값이 필요한, 즉 'recursive(재귀적)'한 성질을 가진다. 제한조건을 걸어 언젠가 계산이 끝내게 만든다고 한다.
논문에 따르면, 모든 웹페이지의 페이지랭크값을 합산하면 1이 된다고 했지만, 수식을 보면 d=0 이면 PR(A)=1, 페이지가 N개가 있을때 모든 웹페이지의 페이지랭크 합은 N이 된다.
위키피디아에 따르면 세르게이와 래리가 논문을 쓸 때 실수한 것 같다며, 올바른 수식은 아래와 같다.
구글의 검색엔진은 어떤 사람이 검색어를 입력하는 순간, 검색어가 포함된 페이지들의 PageRank 순위에 따라 나열하게 된다.
위 사진에서 B는 여러 페이지에서 링크를 걸고 있어 PR값이 크고, C는 B에서 링크를 걸었다는 것만으로 PR이 높게 측정된 모습이다. '영향력 있는 페이지가 인용할수록 PageRank가 올라간다'는 걸 보여준다.
PageRank 공식 유도
(추후정리할 예정)
TextRank
TextRank는 PageRank의 알고리즘을 활용한 것으로, 페이지를 단어로 바꾼 것이다. 즉, 텍스트로 이루어진 글에서 특정 단어가 다른 문장과 얼마나 관계를 맺고 있는지를 계산한다.
TextRank에서 키워드 추출 방법
하나 이상의 단어로 구성된 시퀀스(n gram, 키워드 후보)을 페이지로 생각한다. 그리고 이 키워드 후보들 사이에 co-occurrence를 통해 중요도를 정의한다. 정리하면 다음과 같은 비지도형태의 알고리즘이 나온다.
1) 텍스트를 토큰화하고, 필터링을 위해 POS태깅을 진행
: 필터링을 통해 원하는 조건에 맞는 단어만을 키워드 후보에 추가하는 방법으로 예를 들면, 명사 또는 동사만을 추가하는 방법이 있다.
2) 후보 키워드(노드)를 그래프에 추가하고, co-occurrence를 고려해 노드에 추가한다.
3) 초기 노드중요도를 1로 설정하고 수렴할때까지 알고리즘을 반복한다.
4) 최종적으로 얻은 중요도를 정렬하여 Top N개의 후보 키워드를 최종 추출 키워드로 정의한다.
TextRank 파이썬 실습
(추후 정리할 예정)
Reference
PageRank
TextRank
잘 읽었습니다. 좋은 정보 감사드립니다.