[IR] TF-IDF와 BM25검색 알고리즘과 엘라스틱서치(elasticsearch)

벡터임베딩을 통해 유사한 문서들을 검색하고 LLM를 통해 답변을 내놓는 방법인 RAG는 간혹 문서에 없는 말을 지어내는 현상이 발생하고 있습니다. 이 문제는 검색 시스템을 만드는 입장에서 참으로 골치덩이입니다.

"RAG 사용해도 법률 AI 도구 환각 33% 이상 발생" < 산업일반 < 산업 < 기사본문 - AI타임스 (aitimes.com)

아직도 전통적인 키워드기반 검색 방식이 결과의 신뢰성 부분에서 더 나은 선택이 되는 경우도 많이 있다고 생각됩니다.

그런데 최근에 엘라스틱서치가 벡터임베딩과 RAG까지 지원하면서 LLM의 치명적인 환각현상을 전통적인 시스템과 함께 보완해서 개선할 수 있도록 내놓고 있는 것 같습니다.

TF-IDF란?

TF-IDF(Term Frequency-Inverse Document Frequency)는 정보 검색 및 텍스트 마이닝에서 키워드의 중요성을 평가하기 위한 통계적 수치입니다. 문서 내에서 단어의 중요도를 계산하여, 특정 단어가 문서 전체에 얼마나 중요한지를 나타내는 방법입니다. TF-IDF는 문서 검색, 정보 검색, 그리고 자연어 처리에서 사용됩니다. BM25 이전에 검색엔진에서 사용되던 방식입니다.

TF-IDF는 두 가지 요소로 구성됩니다:

• TF (Term Frequency): 특정 단어가 문서 내에서 얼마나 자주 등장 하는지를 측정합니다. 용어 빈도가 높을수록 해당 단어는 문서에 더 중요한 것으로 간주됩니다.

  
  

• IDF (Inverse Document Frequency): 특정 단어가 전체 문서 집합에서 얼마나 흔한지를 측정합니다. 자주 등장하지 않는 단어는 정보량이 더 많다고 간주되며, 높은 가중치를 받습니다.

• TF-IDF : TF와 IDF의 곱으로 정의되며, 문서 내 단어의 중요도를 전체 문서 집합에서의 희소성과 결합하여 평가합니다.

  
  

BM25 알고리즘이란?

BM25는 키워드기반 텍스트 검색 엔진에서 널리 사용되며, Lucene, Elasticsearch, Solr 와 같은 검색엔진에서 사용됩니다. 엘라스틱서치는 5.0 버전부터 디폴트로 사용되고 있습니다.

BM25 (Best Matching 25)는 정보 검색(IR) 분야에서 문서와 질의(Query) 간의 관련성을 측정하는 가중치 기반의 점수 모델입니다. 주로 문서 검색 시스템에서 사용되며, 특히 특정 쿼리에 대해 가장 관련성 높은 문서를 찾아내는 데 활용됩니다. BM25는 TF-IDF(Term Frequency-Inverse Document Frequency) 모델의 발전된 형태로 간주될 수 있습니다.

정리

• 용어 빈도 (Term Frequency, TF): 특정 문서에서 주어진 용어가 나타나는 빈도. TF는 문서 내 용어의 중요도를 나타냅니다.

• 역 문서 빈도 (Inverse Document Frequency, IDF): 특정 용어가 전체 문서 집합에서 얼마나 흔한지를 측정합니다. 자주 등장하지 않는 용어일수록 더 높은 가중치를 받습니다.

• 문서 길이 정규화: BM25는 문서의 길이에 따라 용어 빈도를 조정합니다. 일반적으로, 긴 문서에서는 특정 용어가 더 자주 나타날 가능성이 높기 때문에, 이를 보정하기 위해 문서 길이를 고려합니다.

• BM25 스코어 계산방법

• f(q𝑖​ ,D)는 문서 D에서 용어 𝑞𝑖 ​ 의 빈도입니다.

• avgdl은 전체 문서 집합의 평균 문서 길이입니다.

• k1과 b는 조정 가능한 매개변수입니다.

• IDF(𝑞𝑖)는 용어𝑞𝑖의 역 문서 빈도로, 다음과 같이 정의됩니다. ( TF-IDF 의 IDF수식과는 좀 차이가 있습니다.)

  
  

매개변수

k1 : 단어 빈도 포화 특성을 결정하는데 영향을 끼치는 매개변수 입니다.

b : 평균길이 대비 문서 길이의 효과를 결정하는데 영향을 끼치는 매개변수 입니다.

• 엘라스틱서치 에서 b의 기본값은 0.75입니다.

TF-IDF와의 차이점 및 비교

문서 길이 정규화:

• TF-IDF: 문서 길이를 고려하지 않음.

• BM25: 문서 길이를 고려하여, 긴 문서와 짧은 문서를 공정하게 비교할 수 있도록 조정함.

조정 가능한 매개변수:

• TF-IDF: 매개변수가 없음.

• BM25: 조정 가능한 매개변수를 통해 모델을 튜닝할 수 있음.

점수 계산 방식:

• TF-IDF: 중요도를 평가.

• BM25: TF의 포화효과와 문서 길이 정규화를 고려한 복잡한 계산 방식을 사용.

희소한 단어에 대한 처리:

• TF-IDF: 흔하지 않은 단어에 높은 가중치를 부여하지만, 그 값이 매우 높을 수 있음.

• BM25: 흔하지 않은 단어에 가중치를 부여하지만, 특정 범위 내에서 값을 제한함.

  
  

엘라스틱서치 검색 알고리즘

엘라스틱 서치에서는 기본설정인 BM25 이외에 다양한 문서 스코어링/랭킹 모듈을 제공하고 있습니다.

종류

• BM25 (Best Matching 25)

  BM25는 엘라스틱서치 5.0 이후 기본 검색 알고리즘입니다. 이 알고리즘은 문서와 쿼리 간의 관련성을 평가하는 데 사용되며, TF-IDF 모델의 확장형으로 간주됩니다. BM25는 문서 길이 정규화와 용어 빈도, 역 문서 빈도를 고려하여 검색 성능을 최적화합니다.

• TF-IDF (Term Frequency-Inverse Document Frequency)

  TF-IDF는 각 단어의 중요성을 계산하여 문서의 관련성을 평가합니다. 이는 특정 단어가 문서 내에서 얼마나 자주 등장하는지(TF)와 전체 문서 집합에서 얼마나 흔하지 않은지(IDF)를 기반으로 합니다. 필요에 따라 TF-IDF를 사용할 수도 있습니다.

• DFR (Divergence from Randomness)

  DFR은 문서와 쿼리 간의 관련성을 확률적으로 평가하는 모델입니다. 이 알고리즘은 단어의 발생 확률이 무작위적이라는 가정과 실제 발생 확률 간의 차이를 측정합니다.

• DFI (Divergence from Independence)

  DFI는 단어의 발생이 독립적이라는 가정하에, 실제 발생 빈도와 이 가정 간의 차이를 측정하여 관련성을 평가합니다.

• IB (Information-Based)

  IB 모델은 텍스트가 문서 내에서 발생하는 확률을 기반으로 하며, 정보 기반 접근 방식을 사용하여 관련성을 평가합니다.

• LM (Language Models)

  언어 모델을 사용하여 문서와 쿼리의 관련성을 평가합니다. 확률적 언어 모델은 문서의 언어적 특성을 고려하여 검색 성능을 향상시킵니다.

인덱스 설정

• BM25

PUT /my_index
{
  "settings": {
    "index": {
      "similarity": {
        "default": {
          "type": "BM25",
          "k1": 1.5,
          "b": 0.75
        }
      }
    }
  }
}

• DFR

PUT /my_index
{
  "settings": {
    "index": {
      "similarity": {
        "default": {
          "type": "DFR",
          "basic_model": "be",  // 기본 모델 (e.g., "be" for Bose-Einstein)
          "after_effect": "l",  // 후가중치 모델 (e.g., "l" for Laplace)
          "normalization": "h2",  // 정규화 방법 (e.g., "h2")
          "normalization.h2.c": "3.0"  // 정규화 매개변수
        }
      }
    }
  }
}

• DFI

PUT /my_index
{
  "settings": {
    "index": {
      "similarity": {
        "default": {
          "type": "DFI",
          "independence_measure": "standardized"  // 독립성 측정 방법 (e.g., "standardized", "saturated", "chisquared")
        }
      }
    }
  }
}

• IB

PUT /my_index
{
  "settings": {
    "index": {
      "similarity": {
        "default": {
          "type": "IB",
          "distribution": "ll",  // 분포 모델 (e.g., "ll" for Log-logistic)
          "lambda": "df",  // 람다 파라미터 (e.g., "df" for document frequency)
          "normalization": "h2"  // 정규화 방법 (e.g., "h2")
        }
      }
    }
  }
}