Week 11 (4) Passage Retrieval - Sparse Embedding

1. Introduction to Passage Retrieval

1) Passage Retrieval

• 질문(query)에 맞는 문서(passage)를 찾는 것
• 질문이 들어왔을 때 웹 또는 위키피디아 상에서 관련된 문서를 가져오는 시스템 

2) Passage Retrieval with MRC

• MRC에서 지문이 주어졌다고 가정 후 지문 내에서 답변을 찾는 형태의 모델을 만들 때, 지문을 주는 모델도 필요함.
• Open-domain Question Answering: 대규모의 문서 중에서 질문에 대한 답을 찾기
  • Passage Retrieval과 MRC를 이어서 2-Stage로 만들 수 있음
  • Passage Retrieval은 질문, 질문에 대한 답, 질문과 관련된 내용을 포함할 것 같은 지문을 MRC 모델에 넘김.
  • MRC는 그 지문을 보고 정확한 답변을 냄.

3) Overview of Passage Retrieval 

• Query와 Passage를 임베딩한 뒤 유사도로 랭킹을 매기고, 유사도가 가장 높은 Passage를 선택함
• Passage는 미리 임베딩 해둬 효율성 도모
• Similarity score를 재는 방법으로 nearest neighbor, inner product 등이 있음
• 모든 passage에 대해 유사도를 계산하고, 가장 높은 score를 갖는 순서대로 내보냄

2. Passage Embedding and Sparse Embedding

1) Passage Embedding

• 구절(Passage)을 벡터로 변환하는 것
• Passage Embedding space : Passage Embedding의 벡터 공간.
• 벡터화된 Passage를 이용하여 Passage 간 유사도 등을 알고리즘으로 계산할 수 있음.

2) Sparse Embedding

• Sparse (<-> Dense) : 0이 아닌 숫자가 적게 있음을 의미
• Bag-of-Words(BoW)
  • 문서를 embedding space로 매핑하기 위해 문서에 존재하는 단어들을 1이나 0으로 표현하여 긴 vector로 표현
  • 특정 단어의 존재 유무를 표현하기 때문에 vector의 길이는 전체 vocab의 사이즈와 동일
• BoW를 구성하는 방법 -> n-gram
  • unigram(1-gram) : It was the best of times => It, was, the, best, of, times (벡터 크기 = vocab size)
  • bigram (2-gram): It was the best of times => It was, was the, the best, best of, of times
  • n이 늘어날수록 vocab 사이즈가 기하급수적으로 늘어남. 보통 bi, tri까지 사용
• Term value 를 결정하는 방법 (가장 바닐라한 BoW)
  • Term이 document에 등장하는지 (binary)
  • Term이 몇번 등장하는지 (term frequency), 등. (e.g. TF-IDF)

3) Sparse Embedding 특징

1. Dimension of embedding vector = number of terms
   • 등장하는 단어가 많아질수록 증가
   • N-gram의 n이 커질수록 증가
2. Term overlap을 정확하게 잡아 내야 할 때 유용.
3. 반면, 의미(semantic)가 비슷하지만 다른 단어인 경우 비교가 불가 -> dense embedding 활용

3. TF-IDF

BoW는 단순하게 특정 단어가 문서에 존재하는지를 0 or 1로 벡터화하는 것

1) TF-IDF (Term Frequency – Inverse Document Frequency) 소개

• Term Frequency (TF): 특정 term의 단어의 등장빈도
• Inverse Document Frequency (IDF): 단어가 제공하는 정보의 양 (단어가 얼마나 덜 등장하는지)
• TF x IDF 로 최종 수치를 잼 (어떤 문서 내에 단어가 많이 등장했는데, 전체 문서 내에는 그 단어가 별로 없다 -> 더 높은 점수를 받을 수 있음)
• ex) It was the best of times
  -> It, was, the, of : 자주 등장하지만 제공하는 정보량이 적음
  -> best, times : 좀 더 많은 정보를 제공

2) Term Frequenct (TF)

• 해당 문서 내 단어의 등장 빈도
• BoW는 0 or 1로 표현했지만 TF는 등장 횟수 표현 가능
• 해당 문서에서의 단어의 중요도를 나타냄
• 1. Raw count
  2. Adjusted for doc length : raw count / num words (TF)
  3. Other variants : binary, log normalization, etc.

3) Inverse Document Frequency (IDF)

• 단어가 제공하는 정보의 양
• 모든 문서에 등장하는 단어는 IDF 값이 0이 됨 (e.g. N=100, DF(t)=100)
• 해당 단어의 문서 전체에서의 중요도를 나타냄

 

Document Frequency (DF) = Term t가 등장한 document의 개수
N: 총 document의 개수

 

• TF와 달리 IDF는 각 term에 특정되고 문서에는 무관함
• 자주 출현한 단어들은 IDF 값이 낮음
• IDF 값은 문서에 상관없이 항상 일정한 값을 가짐

4) Combine TF & IDF

 

TF-IDF(t, d) : TF-IDF for term t in document d

 

• ‘a’, ‘the’ 등 관사 ⇒ Low TF-IDF
  • TF는 높을 수 있지만, IDF가 0에 가까울 것 (거의 모든 document에 등장 ⇒ N ≈ DF(t) ⇒ log(N/DF) ≈ 0)
• 자주 등장하지 않는 고유 명사 (ex. 사람 이름, 지명 등) ⇒ High TF-IDF
  • IDF가 커지면서 전체적인 TF-IDF 값이 증가
• 질의 TF-IDF 계산 후 가장 관련있는 문서 찾기
  1. 사용자가 입력한 질의 토큰화
  2. 기존 vocab에 없는 토큰 제외
  3. 질의를 하나의 문서로 생각하고, 이에 대한 TF-IDF 계산
  4. 질의 TF-IDF 값과 각 문서별 TF-IDF 값을 곱해 유사도 점수 계산
  5. 가장 높은 점수를 가지는 문서 선택

5) BM25

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

BM25에서 직접 변경 가능한 파라미터

• k1 : Term Frequency의 saciling을 조절
  • 0 : binary model : 문서에 단어 존재 유무
  • 숫자가 커지면, 실제 term frequency를 사용하겠다는 의미
  • 일반적으로 1.2에서 2.0 사이
• b : 문서 길이 normalization
  • 0 : no normalization
  • 1 : full length normalization
  • 일반적으로 0.75를 사용