[논문 리딩] Automatically Building a Stopword List for an Information Retrieval System

Automatically Building a Stopword List for an Information Retrieval System
2005, RTW Lo, B He, I Ounis

 

ABSTRACT

문서에서 자주 등장하지만 정보 전달 면에서 가치가 없는 단어를 stopwords(불용어) 라고 한다.

불용어는 맥락이나 정보에 영향을 끼치지 않으므로 삭제되어야 하지만, 하나의 고정된 불용어 리스트를 여러 문서 집합에 적용하는 것은 정보 전달의 관점에서 바람직하지 않을 수 있다.

이 논문에서는 네 개의 서로 다른 TREC(Text Retrieval Conference) 문서 집합을 이용해 주어진 문서 집합에 대해 불용어를 자동적으로 생성하는 방법들을 소개하고, 그 결과를 평가한다.

특히, term-based random sampling 이라고 하는 새로운 방법은 Kullback-Leibler divergence measure 을 기반으로 했다.

term-based random sampling은 Zipf의 법칙으로부터 유도된 다양한 베이스라인과 비교된다.

Zipf의 법칙으로부터 유도된 불용어는 믿을만하나 수행하는 데 드는 가격이 비싸고, 새로운 방법으로 유도한 불용어는 기존과 비교할 만한 성능을 가진 반면 계산 복잡도는 매우 작다.

마지막으로, 저자들은 전통적인 방식으로 유도한 불용어와 논문에서 제안된 방식으로 유도한 불용어를 합쳐 더욱 효과적인 불용어 리스트를 구성할 수 있다는 것을 보인다.

 

2. Baseline Approach

Zipf의 법칙은 어떤 문서의 단어들을 사용 빈도 순으로 순위를 매겼을 때, 단어의 사용 빈도는 단어의 순위에 반비례한다는 것이다.

($\alpha \approx 1$, $C \approx 0.1$)

$F(r) = \frac{C}{r^\alpha}$

 

본 논문에서는 아래 네 가지 방법을 통해 불용어 리스트를 계산한다. 

 

• Term frequency (TF): 문서 집합에서 단어의 등장 빈도
• Normalized term frequency:
  • $v$:사전에 포함된 단어의 개수
  • $TF_{Norm} = - \log(\frac{TF}{v})$
• Inverse Document Frequency (IDF):
  • $NDoc$: 말뭉치 안의 문서의 개수, $D_k$: 단어 $k$를 포함한 단어의 개수 
  • $idf_k =\log(\frac{NDoc}{D_k})$
• Normalized IDF
  • $idf_{k Norm} = \log(\frac{(NDoc - D_k) + 0.5}{D_k+0.5})$

위의 방법중 어떤 방법이 최선인지 알 수 없기 때문에, 아래의 알고리즘에 각 점수 산정 방식을 바꾸어 가면서 서로 다른 불용어 리스트를 생성한다.

각 단어마다 말뭉치에 기반해 (TF, NTF, IDF, NIDF) 점수를 산정
내림차순으로 점수를 정렬
	단어의 점수에 기반해 순위를 산정 (가장 높은 점수를 가진 단어일 경우 rank=1)
    점수 vs 랭크의 그래프를 그림 (Zipf의 법칙을 따르게 됨)
점수가 임계치를 초과하면 불용어로 정하도록 임계치를 산정
불용어를 제거
불용어를 제거한 후 검색 시스템을 측정해 평균 정확도를 측정

Table1. 베이스라인 방식을 위한 알고리즘

 

Table1 에서 보여지듯이 불용어 산출을 위해 임계치를 결정할 필요가 있다.

임계치 결정의 목적은 가장 높은 정확도를 달성하는 것이므로 임의 결정은 바람직하지 않다.

임계치를 결정하기 위해서는 두 연속하는 순위들($r, r+1$) 간의 단어 등장 빈도($F(r), F(r+1)$) 차이에 주목해야 한다.

$F(r)-F(r+1)$

위 값이 매우 커지면, 즉 $r$번째 랭크의 단어가 $r+1$번째 랭크의 단어보다 등장 빈도가 매우 많다고 하면 $r$을 임계치로서 결정할 수 있다.

즉, $F(r)$보다 등장 빈도가 많은 단어들을 불용어로 생각할 수 있다.

 

3. The term-based random sampling approach

이 논문에서는 특정 단어가 얼마나 정보를 담고 있는지에 기반해 term-based random sampling 방법을 제시한다.

즉 단어가 덜 중요할수록 단어가 불용어일 확률이 높아진다.

단어의 중요성은 Kullback-Leibler(KL) divergence measure를 사용해 측정할 수 있다.

본 논문에서 제시하는 아이디어는 query expansion과 유사하다.

query expansion은 처음에 고른 단어에 대해 그것을 대체할 수 있는 단어들을 찾는 것에 기반한다. 

본 논문에서 제시하는 아이디어는 query expansion에 조금의 변형을 가한 아이디어이다.

여기에서는 주어진 단어와 비슷하거나 같은 의미를 가진 단어를 찾는 대신, 해당 단어를 포함하는 모든 문서를 찾아 이를 샘플 문서로 사용한다.

그리고, 주어진 문서와 전체 문서에서의 단어 분포를 통해 가장 정보를 적게 가진 단어들을 추출한다.

또, 각 단어의 중요도를 평가하기 위해 KL divergence measure를 적용한다.

 

KL measure를 사용하면, 단어 $t$의 가중치는 다음과 같이 산정된다.

$w(t) = P_x \dot \log_{2}\frac{P_x}{P_c}$

• $P_x = t\frac{f_x}{l_x}$, $P_c = \frac{F}{token_c}$
• $tf_x$: 샘플 문서 집합에서 단어 $t$의 빈도
• $l_x$:샘플 문서 집합에 속한 각 문서의 길이의 총합
• $F$: 전체 문서 집합에서 단어 $t$의 빈도
• $token_c$: 전체 문서 집합에 속한 단어의 개수

Y번 반복: 
  단어 사전에서 임의로 단어 w_random을 선정
  w_random을 포함하는 모든 문서를 선택
  KL measure을 사용해 선택된 문서들에 속하는 모든 단어에 대한 가중치 산정
  각 단어의 가중치를 선택된 문서들에 속하는 모든 단어에 대한 최대 가중치로 나눔
  각 단어를 정규화된 가중치에 대해 오름차순으로 정렬
  상위 X개의 단어 선정
  
X*Y 크기의 단어와 가중치로 이루어진 결과 행렬 획득
같은 단어들의 가중치를 평균을 내는 방법을 통해 결과 행렬 축소
결과 행렬을 각 단어의 가중치에 대해 오름차순으로 정렬
최종 상위 L개의 단어 선정

 

전체 단어 집합에서 임의의 단어를 선정하는 방식을 택했을 때, 매우 드문 단어를 선정하게 됨으로서 해당 단어를 포함하는 단 하나의 문서만 선택하게 될 가능성이 있다. 이 문제는 단어 선정을 Y번 반복함으로써 해결가능하다.

이론적으로, 우리가 선택 과정을 여러 번 반복하면 더 나은 샘플을 얻을 수 있고, 그에 따라 단어의 분포와 중요도에 대한 더 유의미한 정보를 얻을 수 있다.

이 방법을 취했을 경우 모든 과정이 자동화되기 때문에 baseline 방식보다 훨씬 효율적으로 수행할 수 있다.