Sparse Passage Retrieval

Passage Retrieval (문서 검색)

Passage Retrieval은 질의(Query)에 맞는 문서(Passage)를 찾는 과정을 의미한다.

위의 그림을 간단하게 설명하면, Query와 Passage를 각각 임베딩하여 유사도를 측정하고, 유사도가 가장 높은 Passage를 선택하는 방식이다.

Sparse Embedding

Passage를 임베딩하는 방식은 Sparse embedding, Dense embedding으로 2가지가 있다. 각 문서(Passage)를 임베딩하여 벡터화시키고, 이를 벡터 공간 상에서 거리가 가까운 것 (즉, 유사도가 높은 것)을 찾을 수 있다. 이 때, 벡터화된 Passage는 단어의 개수만큼 고차원의 벡터 공간을 가지게 된다.

만약 10만 개의 단어로 구성된 단어를 가지고 있다면, 이를 포함하고 있는 모든 문서가 10만 크기의 벡터 공간으로 매핑할 수 있다. 이를 BoW(Bag-of-Words)라고 한다.

BoW를 구성하는 방법은 n-gram을 이용할 수 있다. 예시 문장으로 "I feel more comfortable at home"으로 살펴보자.

• unigram (1-gram)
  ex) I, feel, more, comfortable, at, home
• bigram (2-gram)
  ex) I feel, feel more, more comfortable, comfortable at, at home

unigram을 사용하면 vocabulary의 크기가 passage의 단어 개수와 동일하다. 그러나 bigram을 사용하면 2단어씩 묶어서 vocabulary을 구성하기 때문에 vocabulary의 크기가 passage 단어의 제곱이 된다. 즉, n-gram이 커질수록 vocab의 사이즈가 기하급수적으로 늘어나기 때문에 무작정 n을 높이는 것은 좋지 않은 방식이다. 보통 bigram까지 사용한다고 한다.

다음으로 Term value를 결정하는 방법이다. Term이 문서에 등장하는지, 안하는지에 따라 분류할 수도 있으며, 몇번 등장하는지 빈도수를 이용하여 결정할 수도 있다.

Sparse embedding의 특징은 다음과 같다.

• 등장하는 단어가 많아질수록 벡터공간 상의 차원이 증가한다.
• n-gram의 n이 커질수록 벡터공간 상의 차원이 제곱되어 기하급수적으로 증가한다.
• Term overlap을 정확하게 잡아낼 때 유용하다.
• 의미(semantic)가 유사하지만 다른 단어인 경우, 즉 동의어나 paraphrase된 경우에는 비교할 수 없다. (다르다고 처리함)

TF-IDF (Term Frequency - Inverse Document Frequency)

단어가 특정 문서 내에서는 등장 빈도 수가 많지만, 전체 문서에서는 등장 빈도 수가 적다면, 해당 단어는 중요한 단어로서 TF-IDF가 높게 측정될 것이다. 반대로, 특정 문서와 전체 문서에서 모두 많이 등장하는 단어라면, 중요도가 떨어져 TF-IDF가 낮게 측정될 것이다.

Term Frequency (TF)
: 해당 문서 내 단어의 등장 빈도

• Raw count
• Adjusted for doc length: raw count / num words (TF)
• Other variants: binary, log normalization, etc.
  

Inverse Document Frequency (IDF)
: 단어가 제공하는 정보의 양

$IDF(t) = log{N \over DF(t)}$

• DF : Term t가 등장한 document의 개수
• N : 총 document의 개수
  

"It was the best of times"로 예를 들어보자.
해당 문장에서 It, was, the, of와 같은 단어들은 문서 상에서 자주 등장하지만, 제공하는 정보량이 적다. 반면, best, times와 같은 단어는 등장빈도 수는 적지만 좀 더 많은 정보를 제공한다.

BM25

TF-IDF의 개념을 바탕으로, document의 길이까지 고려하여 점수를 매기는 좀 더 개선된 방식이다.

• TF 값에 한계를 지정해두어 일정한 범위를 유지하도록 한다.
• 평균적인 문서의 길이보다 더 작은 문서에서 단어가 매칭된 경우, 그 문서에 대해 가중치를 부여한다.
• 실제 검색엔진, 추천시스템 등에서 아직까지도 많이 사용되는 알고리즘이다.
  

• 본 포스팅은 KAIST 서민준 교수님의 강의를 바탕으로 작성되었습니다.

-작성중-