[Coursera] Text Retrieval and Search Engines (MODULE 3)

Module 3

1) Vector Space Model - Improved Instantiation

간단한 벡터 공간 모델에는 다음과 같은 문제점이 있었다. 첫째, 단어의 빈도수를 고려하지 못한다. 즉, 쿼리에 있는 단어가 문서에 여러 번 등장해도 한 번 등장한 것과 동일하게 유사도를 계산한다. 둘째, 중요하지 않은 단어에 페널티를 주지 못한다. 즉, "a", "the", "about" 등 전혀 중요하지 않은 단어와 핵심 단어가 동등한 가중치를 지닌다. 이를 해결하기 위해서 TF(Term Frequency)와 IDF(Inverse Document Frequency)를 고려한 TF-IDF 기법을 적용한다. 자세한 수식은 대학원에서 들었던 수업을 정리한 문서(https://koppie.tistory.com/5)를 참조하자. 그러나 TF-IDF 기법을 사용하더라도 여전히 발생하는 문제가 있다....

 

2) TF Transformation

q: "post traumatic stress disorder"와 d1: "post traumatic stress disorder" 및 d2: "post post post post"가 있다고 하자. IDF가 동일하다는 가정하에 q와 d1의 유사도는 q와 d2의 유사도와 동일하다. 해당 예시에서 쿼리에 있는 한 단어가 문서에서 여러 번 등장하는 것이 그렇게 큰 가치를 지니지 않는다는 점을 경험적으로 파악할 수 있다. 따라서 단어의 빈도수를 세는 TF(Term Frequency)에 페널티를 줄 필요가 있다. 로그를 포함한 다양한 페널티를 실험해 본 결과 BM25(Best Matching 25) Transformation이 가장 효과적이었다. 이 방법을 수식으로 나타내면 다음과 같다. $y = {(k+1)x \over k + x}$, where $k = hyper-parameter$. 한편, 로그 페널티를 사용한다면 수식은 다음과 같다. $y = ln(1+ln(1+x))$.

 

3) Length Normalization

문서가 길면 쿼리에 포함된 단어가 문서에 등장할 확률이 올라간다. 따라서 문서 길이가 길다면 페널티를, 문서 길이가 짧다면 보상을 주어야 한다. 이를 위해 다음과 같은 수식이 개발되었다. $normalizer = 1 - b + b{d \over avdl}$, where b = hyper-parameter, d = length of document, avdl = average document length. 따라서 로그 페널티를 사용하는 Pivoted Length Penalization과 BM25/Okapi의 최종 수식은 다음과 같다. 

 

Pivoted Length Penalization

BM25/Okapi

한편, BM25를 개량한 BM25F와 BM25+도 있으니 추후 참고할 만하다. 간략하게 설명하자면 BM25F는 다양한 필드에 BM25를 적용하고 싶을 때 사용하는 방법이고, BM25+는 BM25에 상수항 델타를 더함으로 성능을 높이고자 한 방법이다.

 

4) Implementation of TR System

이제 계산을 위한 최적의 식을 갖게 되었다. 그러나 여전히 "속도"가 문제가 된다. 매번 쿼리가 들어올 때마다 모든 문서와의 유사도를 계산하는 것은 매우 비효율적이기 때문이다. 효율성을 높이기 위해 "Indexing"을 사용한다. 특히 "Inverted Indexing"이 가장 자주 사용된다. 이 방법은 (Term, Document Frequency, Term Frequency)를 기록하는 Dictionary와 (Document ID, Frequency, Term Position)을 기록하는 Postings로 구성된다. 즉, 각 단어(Term)가 몇 개의 문서에서 등장하는지(Document Frequency), 전체 문서에서 몇 번 등장하는지(Term Frequency)를 미리 계산하여 Dictionary에 저장하고, 해당 단어(Term)가 특정 문서(Document ID)에서 몇 번 등장하는지(Frequency), 순서는 어떻게 되는지(Position)도 미리 계산하여 Postings에 저장하는 것이다. 이때, 쿼리가 A & B라면 벡터 공간의 교집합을 A || B라면 벡터 공간의 합집합을 이용한다. 이를 통해 속도를 현저히 높일 수 있다. 한편, Dictionary는 적당한 크기로 빠른 무작위 접근이 필요하므로 Hash Table이나 B-Tree 형태로 메모리에서, Postings는 큰 크기로 순차적인 접근이 필요하므로 압축된 형태로 디스크에서 계산된다.

 

추가적으로 단어의 빈도와 랭크는 다음과 같은 관계를 가진다. Rank * Frequency ≈  Constant. 즉, 빈도가 높은 단어는 주로 랭크가 낮고 빈도가 낮은 단어는 주로 랭크가 높다. 이를 Zipf's Law라고 부른다.

 

5) System Implementation - Inverted Index Compression

Postings는 압축된 형태로 디스크에서 계산된다고 방금 언급했다. 그렇다면 어떻게 압축하는 것일까? 압축은 하나의 가정에서 출발한다. "짧은 단어는 여러 번 등장하는 경향이 있다." 즉, 여러 번 등장하는 짧은 단어에는 작은 비트 값을 할당하고, 가끔 등장하는 긴 단어에는 큰 비트 값을 할당하는 방식으로 압축할 수 있다. 이를 위해 사용하는 기법으로는 Unary Code, Gamma Code, Delta Code 변환 기법이 있다. 자세한 설명이 필요하다면 UIUC MCS-DS CS410을 수강하신 분의 설명을 읽어보자. 

 

6) System Implementation - Fast Search

Fast Search는 Indexing된 값을 이용하여 각 단어와 그 단어가 포함된 문서에 대한 유사도를 계산하고 계산된 값을 합적재하는 방식으로 진행된다. TF가 낮은 단어부터 계산한다거나, 순위가 높은 문서에 대해서만 계산을 진행하는 방식으로 속도를 더욱 높일 수 있다. 마지막으로 교수님께서 유용한 Toolkit(Lucene, Lemur/Indri, Terrier, MeTa)를 소개해 주셨다.