'PageRank'에 해당되는 글 2건

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

요약을 추출하기 위해 많은 알고리즘들은 언어 지식에 의지를 많이 하고 있으며, 특히, 다른 언어로 이루어진 문서에 대해서는 상당히 많은 수정을 해야한다.
게다가 성능을 측정하기 위해서 다듬어진 데이터 셋을 통해 자신만의 편리성을 추구하는 경우도 많다.
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

정보검색 개요를 작성한지 한참 만에 벡터 스페이스 모델에 대해서 정리를 했습니다.

벡터 스페이스 모델은 불리언 모델, 확률 모델과 더불어 검색 모델에 있어서 아주 중요한 부분입니다.

Term vector model이라고도 불리우며 정보 필터링, 정보검색, 색인과 유사도를 계산하기 위한 대수 모델입니다.
이 모델은 SMART Information Retrieval System에서 가장 먼저 언급이 되었으며,
무료 검색엔진인 루씬에서 이 모델을 기본적으로 사용하고 있습니다.


벡터공간 모델 상에서 각 도큐먼트들과 질문자들은 n차원 공간 속의 벡터들로 취급되며,
이때 각 차원들은 색인용어들로 표현된다.
이 기법에 의한 검색 절차는 다음과 같다.
1) 용어의 가중치는 정규화된 도큐먼트내의 빈도(TF)와 이의 역빈도수(IDF)를 조합하여 게산
2) "낮은 식별치(poor discrimination value)의 값을 지닌 용어들은 시소러스내의 저 빈도용어들로 대치되며
   구의 경우 고빈도 용어들로 대체된다.
3) 각 도큐먼트들은 이용자 질문에 대해서 그 유사성의 순위별로 출력되며, 이러한 과정은 코사인 상관도에
   의해 계산된다. (벡터 공간 내에서 이용자의 질의에 가장 근접해 있는 도큐먼트들을 직관적으로 검색해낸다.)


자세한 내용은 다운받아 보시길...

1. Definition
2. Applications
3. Examples
4. Limitations
5. Reference
6. Models based on and extending the vector space model