SingleRank

Single Document Keyphrase Extraction Using Neighborhood Knowledge (Xiaojun Wan and Jianguo Xiao, 2008)를 간단하게 정리해보도록 하자. 이 논문은 문서에서 핵심문구를 추출하는 방법에 대해 소개하고 있다. 핵심문구를 추출하고싶은 문서 뿐만 아니라 주면 문서까지 사용하며, graph-based ranking alogorithm을 통해 문구에 대한 점수를 계산한다. SingleRank는 크게 두 단계로 이루어져 있다.

1. Neighborhood Construction
   핵심문구를 추출하고싶은 문서를 $d_0$라고 하며 이를 문서 set $D = \{d_0, d_1, \ldots, d_k\}$으로 확장시킨다. $d_1, \ldots,d_k$는 neighbor document로 similarity search technique를 이용해 얻을 수 있다.
   예를들어 100개의 문서가 있고 1번 문서에서 핵심문구를 추출하고 싶은 경우 나머지 99개의 문서 중 1번 문서와 유사한 문서 k개를 선택
   
2. Keyphrase Extraction
   document set $D$가 주어졌을 때 $d_0$에서 핵심문구 추출을 위해 neighborhood-level word evaluation(global information)과 document-level keyphrase extraction(local informaion)을 수행한다.

---

위의 두 단계를 조금 더 자세히 살펴보자.

1. Neighborhood Construction

• $d_0$: specified document
• $d_1, d_2, \ldots, d_k$: $k$ neighbor documents
• $D = \{d_0, d_1, \ldots, d_k \}$: expanded document set for $d_0$

문서 $d_i$와 $d_j$의 유사도는 각 문서를 term vector로 나타낸 뒤 코사인 유사도를 이용하여 구할 수 있다. term vecotr는 tf-idf를 이용해서 구한다.

여기서는 $d_0$와 다른 문서들 간의 유사도를 측정하여 큰 값을 갖는 $k$개의 문서를 neighborhood로 선택한다.

2. Keyphrase Extraction

a) neighborhood-Level Word Evaluation

$D$를 고려하여 핵심 문구에 대한 평가를 하기 위해 graph-based ranking algorithm을 사용한다. 이를 위해 graph construction 방법부터 살펴보자.

• 노드
  각 노드는 $D$ 전체에서의 후보 단어(candidate word)이다. 전체 문서에서 POS tagging(품사 태깅)을 거친 JJ(형용사), NN(단수명사), NNS(복수명사), NNP(고유단수명사), NNPS(고유복수명사)로 이루어져 있다.
• 엣지
  엣지의 연결 유무는 window size w(2~20)내에 단어들의 co-occurance가 결정한다. 즉, 노드에 해당하는 단어들이 window size 내에서 co-occurance가 발생하면 두 노드를 이어주고 co-occurance가 없는 경우 연결하지 않는다.
  단어 $v_i$와 $v_j$사이의 연결 강도인 affinity weight는 아래와 같이 계산할 수 있다.
  $aff(v_i, v_j) = \sum_{d_p \in D} sim_{doc}(d_0, d_p) \times count_{d_p}(v_i, v_j)$
  여기서 $count_{d_p}(v_i, v_j)$는 문서 $d_p$내에서 단어 $v_i$와 $v_j$의 공동 발생 횟수를 나타내고 $sim_{doc}(d_0, d_p)$는 문서 $d_0$를 기준으로 문서 $d_p ~(0 \leq p \leq k)$가 얼마나 유사한지를 나타내는 요소이다.

$D$를 사용하여 graph G를 만든 후에 이에 대한 affinity matrix M은 다음과 같고

각 행의 합이 1이 되도록 정규화 한 행렬은 다음과 같다.

위의 방법으로 $D$를 이용하여 graph를 만들고 각 노드의 점수는 PageRank algorithm을 이용하여 계산된다.

논문에서 나오는 matrix form과 Markov chain은 생략했음. stationary distribution은 Markov chain의 정리를 참고($\pi = \pi P$)

b) Document-Level Keyphrase Extraction

모든 후보 단어에 대한 점수가 계산되고 나면 대상 문서 $d_0$에서 핵심문구 추출 단계를 거치게 된다.
예를 들어 'Mad cow disease has killed 10,000 cattle'이라는 문장이 있을 때 POS tagging을 거쳐 'Mad/JJ cow/NN disease/NN has/VBZ killed/VBZ 10,000/CD cattle/NNS'를 생성하게 된다.
노드를 구성하는 단계에서 JJ, NN, NNS, NNP, NNPS의 단어만 사용하기로 했으니 'Mad cow disease'와 'cattle'이 후보 문구로 선택되며 각 후보 문구에 대한 점수가 아래 식을 이용하여 계산된다.

즉, 'Mad cow disease'의 점수는 $WordScore(\text{Mad}) + WordScore(\text{cow}) + WordScore(\text{disease})$가 된다.
문서 $d_0$의 후보 문구들의 점수를 순서대로 나열한 후 상위 $m (1 \leq m \leq 20)$개를 핵심문구로 선택한다.