[ODQA] 4. Passage Retrieval - Sparse Embedding

1. Introduction to Passage Retrieval
2. Passage Embedding & Sparse Embedding
3. TF-IDF

 

문서 검색(Passage retrieval)을 하기 위해서는 문서를 embedding의 형태로 변환해 줘야 하는데, 이를 passage embedding 이라고 한다.

이번 글에서는 passage embedding이 무엇인지 알아보는 동시에, 단어 기반으로 만들어진 passage embedding인 sparse embedding, 그 중에서도 자주 쓰이는 TF-IDF에 대해 정리하였다.

 

1. Introduction to Passage Retrieval

▮ Passage Retrieval

• 질문(Query)에 맞는 문서(Passage)를 찾는 것

 

• Passage Retrieval과 MRC를 연결하면 Open-domain Question Answering을 할 수 있다.
  • Open-Domain Question Answering
    : 대규모의 문서 중에서 질문에 대한 답 찾기
  • Passage Retrieval과 MRC를 이어서 2 stage로 만들 수 있다.
    1. Passage Retrieval 모델은 질문에 관련된 지문을 찾아 MRC 모델에 넘겨준다.
    2. MRC 모델은 그 지문에서 질문에 대한 답을 출력

 

▮ Overview of Passage Retrieval

• Query와 Passage를 임베딩한 뒤 유사도로 랭킹을 매기고, 유사도가 가장 높은 Passage를 선택한다.

• Passage 임베딩을 미리 다 해둠으로써 효율성을 극대화한다.

 

 

2. Passage Embedding and Sparse Embedding

▮ Passage Embedding Space

• Passage Embedding의 벡터 공간
• 벡터화된 Passage를 이용해 Passage 간 유사도 등을 알고리즘으로 계산할 수 있다.
• 즉, Passage를 Vector Space에 맵핑하는 것이다.

 

 

▮ Sparse Embedding

• Bag-of-Words (BoW)
  • 문서가 주어졌을 때 문서를 Embedding space로 맵핑하기 위해 각 문서에 존재하는 단어들을 존재하면 1, 존재하지 않으면 0으로 표현하는 방법이다.
  • 각각의 dimension은 하나의 단어에 해당하며 특정 단어가 존재하는지 존재하지 않는지로 표현을 하다보니 Vector의 길이는 Vocabulary의 size와 동일하다. 
    

 

1. BoW를 구성하는 방법 → n-gram
   • unigram (1-gram) : 한 단어씩 끊어서 보는 방법
   • bigram (2-gram) : 두 단어씩 끊어서 보는 방법
   • n이 늘어날 수록 기하급수적으로 vocab size가 커지므로 n이 클수록 좋은 것은 아니다.
2. Term Value를 결정하는 방법
   • Term이 document에 등장하는지 (Binary) : BoW
   • Term이 몇 번 등장하는지 (term frequency) : TF-IDF

 

• Sparse Embedding 특징
  • Dimension of embedding vector = # of terms
    : 등장하는 단어가 많을 수록 / N-gram의 n이 커질수록 증가한다.
  • 장점
    : Term overlap을 정확히 잡아내야 할 때 유용하다. 즉, 검색 단어가 실제 문서에 포함되어 있는지 찾을 때 유용하다.
  • 단점
    : 의미가 비슷하지만 다른 단어인 경우 비교가 불가능하다. → Dense Embedding

 

3. TF-IDF

해당 문서에 포함되어 있는 특정 단어가 다른 문서에는 포함되어있지 않다면 해당 문서에서 그 단어는 중요한 단어일 것이다.

 

▮ Term Frequency (TF)

• 해당 문서 내 단어의 등장 빈도
• 계산 방법
  1. 특정 단어가 해당 문서에서 몇 번 나오는지를 count한다.
     BoW는 존재 유무를 확인하기 때문에 0 또는 1이었지만 TF는 빈도수를 사용한다.
  2. 그 횟수를 Normalize 해준다.

 

▮ Inverse Document Frequency (IDF)

• 단어가 제공하는 정보의 양

• 많은 문서에 등장할 수록 점수는 낮아진다.
  문서 100개가 있는데 이 문서에 'The' 같은 단어는 100개의 모든 문서에 등장할 것이다.
  그러면 $ log( \frac{100}{100} ) = log(1) = 0 $ 이므로 IDF Score는 0점이 된다.
• TF와 달리 IDF는 문서와는 무관하고 Term에만 특정된다.
  즉, 같은 term이면 어떤 문서에 등장하건 항상 값이 동일하다.

 

 

▮ Combine TF & IDF

• ‘a’, ‘the’ 등 관사 → Low TF-IDF
  • TF 는 높을 수 있지만, IDF 가 0에 가까울 것
    거의 모든 document 에 등장  
• 자주 등장하지 않는 고유 명사 (ex. 사람 이름, 지명 등) → High TF-IDF
  • IDF가 커지면서 전체적인 TF-IDF 값이 증가

 

 

▮ BM25

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

 

 

Query에 있는 용어가 각각의 문서에 얼마나 자주 등장하는지를 평가한다.

키워드 $ q_{1}, ... , q_{n} $ 을 포함하는 쿼리 Q가 주어질 때 문서 D에 대한 BM25 점수를 아래 공식을 이용해 구한다.

 

• $ q_{i} $ : 쿼리 Q에서의 i번째 토큰
• $ IDF(q_{i}) $ : 쿼리 i 번째 토큰에 대한 Inverse Document Frequency
  • IDF 값이 곱해진다는 것은 자주 등장하지 않는 단어에 더 큰 가중치를 둔다는 것을 의미 
  • Lucene에서의 IDF 계산식

 

• $ \frac{|D|}{avgdl}  $ : 문서의 길이에 대한 부분
  • 해당 문서가 평균적인 문서 길이에 비해 얼마나 긴지를 고려
  • 열 페이지가 넘는 문서에서 특정 단어가 한 번 나오는 것과, 짧은 문장에서 단어가 한 번 나오는 것 중에서는 두번 째 경우가 더 의미있다고 본다.
• $ b $ : 일반적으로 0.75 값을 사용
  • b가 커지면 평균 문서 길이 대비 문서의 길이에 대한 항의 중요도가 커진다.
  • 0에 가까워지면 문서의 길이는 고려되지 않음
• $ f(q_{i}, D) $ : 쿼리의 i번 째 토큰이 문서 D에 얼마나 자주 나타나는가 → TF
  • 해당 토큰이 문서에 자주 나타나면 점수 상승
• $ k1 $ : 일반적으로 1.2 ~ 2.0 값을 사용
  • 하나의 쿼리 토큰이 점수에 끼치는 영향을 설정 
  • 어떤 토큰의 TF가 k1보다 작거나 같으면 TF가 점수에 주는 영향이 빠르게 증가하는데, k1번 등장하기 전 까지는 해당 키워드가 문서에 더 등장하게 되면 문서의 BM25 스코어를 빠르게 증가시킨다.
  • 반대로 토큰의 TF가 k1보다 크면 TF가 점수에 주는 영향이 천천히 증가하고, 해당 키워드가 더 많이 등장해도 스코어에 주는 영향이 크지 않게된다.
  • 즉, k1의 존재로 인해 BM25에서 term frequency는 어느정도 이상부터는 점수에 주는 영향이 거의 증가하지 않는다.