BM25

Okapi BM25; BM25
질의 단어가 문서에 얼마나 자주, 얼마나 드물게, 얼마나 짧은 문서에 나오는지로 관련도 점수를 매기는 확률적 순위 함수

BM25(Best Matching 25, Okapi BM25)는 질의와 문서의 관련도를 단어 빈도(TF), 역문서 빈도(IDF), 문서 길이로 계산하는 순위 함수다. 1990년대 런던 시티 대학의 Okapi 검색 시스템에서 나온 확률적 관련성 모형의 한 형태로, 1994년 TREC-3 참가 보고서에서 소개되었다.^[1] 루씬, 엘라스틱서치, OpenSearch, Solr 같은 검색 엔진의 기본 점수 함수이며, 신경망 검색 연구에서도 반드시 비교하는 기준선이다.

TF-IDF의 문제(단어가 반복될수록 점수가 끝없이 오르고, 긴 문서가 유리함)를 두 개의 매개변수 $k_{1}$ , $b$ 로 다듬은 것이라고 보면 이해가 쉽다. RAG에서는 밀집 벡터 검색과 함께 쓰는 하이브리드 검색의 희소 검색 쪽을 맡는다.

수식

질의 $Q = (q_{1}, \dots, q_{n})$ 와 문서 $D$ 의 점수는

$s c o r e (D, Q) = \sum_{i = 1}^{n} I D F (q_{i}) \cdot \frac{f (q_{i}, D) \cdot (k_{1} + 1)}{f (q_{i}, D) + k_{1} \cdot (1 - b + b \cdot \frac{| D |}{a v g d l})}$

이다.

$f (q_{i}, D)$ : 문서 D에서 단어 $q_{i}$ 가 나온 횟수
$| D |$ : 문서 길이(단어 수), $a v g d l$ : 전체 문서의 평균 길이
$k_{1}$ : 단어 빈도 포화 정도, $b$ : 문서 길이 정규화 정도
$I D F (q_{i})$ : 단어가 드물수록 큰 가중치

IDF는 여러 형태가 쓰인다. 고전적인 로버트슨-스파크 존스 형태는 $\log \frac{N - n (q_{i}) + 0.5}{n (q_{i}) + 0.5}$ (N은 전체 문서 수, $n (q_{i})$ 는 단어를 포함한 문서 수)인데, 절반이 넘는 문서에 나오는 단어는 음수가 된다. 문서 1,000개에서 900개에 나오는 단어의 IDF는 -2.19가 되어, 그 단어가 있는 문서의 점수를 오히려 깎는다. 그래서 0 아래를 잘라 내거나,^[2] 루씬처럼 1을 더해 항상 양수가 되게 한다.

${I D F}_{Lucene} (q_{i}) = \log (1 + \frac{N - n (q_{i}) + 0.5}{n (q_{i}) + 0.5})$ ^[1]

같은 예에서 루씬식 IDF는 0.106으로, 작지만 양수다.

매개변수의 의미

k1: 빈도 포화

$b = 0$ 이거나 문서 길이가 평균일 때 TF 항은 $\frac{f (k_{1} + 1)}{f + k_{1}}$ 이 된다. f가 커질수록 $k_{1} + 1$ 에 다가가며 포화한다. TF-IDF처럼 빈도에 비례해 끝없이 오르지 않으므로, 같은 단어를 100번 반복한 문서가 독점하지 못한다.

k1	f=1	f=2	f=3	f=5	f=10	f=100	상한
0.5	1.000	1.200	1.286	1.364	1.429	1.493	1.5
1.2	1.000	1.375	1.571	1.774	1.964	2.174	2.2
2.0	1.000	1.500	1.800	2.143	2.500	2.941	3.0

$k_{1} = 0$ 이면 빈도를 무시하고 "있다/없다"만 보며, $k_{1}$ 이 클수록 원래 빈도에 가깝게 반응한다.

b: 길이 정규화

분모의 $1 - b + b \cdot | D | / a v g d l$ 은 평균보다 긴 문서의 빈도를 깎는다. 긴 문서는 주제와 무관하게 단어가 우연히 많이 나오기 때문이다. $b = 1$ 이면 길이에 완전히 비례해 정규화하고, $b = 0$ 이면 길이를 무시한다. 두 극단은 각각 BM11( $b = 1$ ), BM15( $b = 0$ )라는 이름의 이전 공식에 해당한다.^[3]

기본값

교과서 권장: 따로 튜닝하지 않을 때 $k_{1}$ 은 1.2~2.0, $b = 0.75$ 가 합리적이라는 실험 결과가 있다.^[2]
루씬: $k_{1} = 1.2$ , $b = 0.75$ .^[1] 루씬 6.0.0에서 IndexSearcher의 기본 유사도가 기존 벡터 공간 모형(ClassicSimilarity)에서 BM25Similarity로 바뀌었다.^[4]
엘라스틱서치: 5.0부터 BM25가 기본 유사도이며,^[5] 기본값은 k1 1.2, b 0.75, discount_overlaps true다.^[6]

문서가 제목처럼 짧고 길이가 고르면 b를 낮추고, 같은 단어 반복이 관련성을 잘 나타내는 긴 기술 문서라면 k1을 올려 보는 식으로 조정한다. 바꾼 뒤에는 실제 질의 묶음으로 nDCG나 재현율을 재서 확인한다.

질의 쪽 빈도

긴 질의에서 같은 단어가 여러 번 나오면 질의 단어 빈도 $q t f$ 에도 $\frac{(k_{3} + 1) q t f}{k_{3} + q t f}$ 포화를 걸 수 있다. 교과서는 문단 길이 질의에 적합하고 짧은 질의에는 불필요하다고 설명한다.^[2] 루씬 최신 소스에는 $k_{3}$ 매개변수가 있으며 음수(기본)이면 꺼져 있다.^[1]

구현상의 세부

루씬의 실제 점수는 분자에서 $(k_{1} + 1)$ 을 뺀 $I D F \cdot \frac{f}{f + k_{1} (1 - b + b \cdot d l / a v g d l)}$ 형태다. 모든 문서에 같은 상수를 곱하지 않는 것뿐이라 순위는 같지만 점수의 절대 크기는 교과서 공식과 다르다. 또 문서 길이는 색인 크기를 줄이려고 1바이트로 근사해 저장하고, 256가지 길이에 대한 정규화 값을 미리 계산해 둔다.^[1] 다른 라이브러리와 점수를 비교하거나 하이브리드 검색에서 점수를 정규화할 때 이런 차이를 고려해야 한다.

엘라스틱서치는 IDF와 avgdl을 샤드별 통계로 계산하므로, 문서 수가 적거나 샤드 간 문서 분포가 고르지 않으면 같은 문서라도 샤드에 따라 점수가 달라질 수 있다.^[5]

TF-IDF와 비교

항목	TF-IDF(고전 벡터 공간)	BM25
단어 빈도	빈도(또는 로그 빈도)에 비례해 계속 증가	$k_{1} + 1$ 로 포화
문서 길이	코사인 정규화 등 별도 처리	$b$ 로 평균 길이 대비 정규화
이론적 근거	경험적 가중치	확률적 관련성 모형(2-포아송 근사)
조정 손잡이	거의 없음	$k_{1}$ , $b$
현재 쓰임	특징 추출, 키워드 추출	검색 엔진 기본 점수, 신경망 검색의 기준선

변형

BM25F: 제목, 본문, 앵커 텍스트처럼 필드가 여러 개일 때 필드별 가중치와 길이 정규화를 따로 두고 빈도를 합친 뒤 포화를 건다.^[7] 필드마다 BM25를 따로 계산해 더하면 포화가 필드마다 걸려 반복 단어가 과대평가되는 문제를 피한다.
BM25+: 긴 문서가 질의 단어를 포함하는데도 포함하지 않는 짧은 문서와 비슷한 점수를 받는 문제를 막기 위해 TF 항에 하한 $δ$ 를 더한다.^[8]
학습된 희소 표현: SPLADE는 언어 모델로 단어별 가중치와 확장 단어를 학습해, 역색인 구조를 그대로 쓰면서 BM25보다 나은 1차 검색을 노린다.^[9] BGE-M3처럼 한 모델이 밀집 벡터와 단어 가중치(희소 벡터)를 함께 내는 경우도 있다(문장 임베딩 참고).

신경망 시대의 BM25

2020년 DPR은 학습한 밀집 검색기가 루씬 BM25보다 상위 20개 문단 검색 정확도에서 9~19%포인트 높다고 보고했다.^[10]
그러나 2021년 BEIR 벤치마크는 학습 데이터와 다른 분야 18개 데이터셋에서 BM25가 강건한 기준선이며, 밀집 검색 모델은 분야가 바뀌면 자주 BM25에 못 미친다는 것을 보였다.^[11] 이후 Contriever(비지도 학습으로 BEIR 15개 중 11개 데이터셋의 Recall@100에서 BM25를 앞섬), E5(레이블 없이 BEIR에서 BM25를 처음 앞섰다고 보고) 같은 후속 연구가 BM25와의 비교를 주요 결과로 내세웠다.^[12]^[13]
BM25는 학습이 필요 없고, 색인과 검색이 빠르고, 왜 그 문서가 나왔는지 설명할 수 있으며, 제품 번호·오류 코드·법 조항처럼 정확히 일치해야 하는 질의에 강하다. 반대로 "자동차 고장"으로 "차량 수리" 문서를 찾는 것 같은 동의어·의역에는 약하다. 이 보완 관계 때문에 밀집 검색과 함께 쓰는 하이브리드 검색이 일반화되었다.

한국어에서의 주의점

BM25의 품질은 문서를 무엇으로 자르느냐(토큰화)에 크게 좌우된다. 공백 단위로 자르면 "학교에서"와 "학교"가 다른 단어가 되어 일치하지 않는다. 그래서 형태소 분석기로 조사·어미를 떼거나(엘라스틱서치 nori 등), 글자 n-gram으로 색인한다. 형태소 분석기의 사전에 없는 신조어·제품명은 잘못 쪼개져 검색이 안 될 수 있어 사용자 사전을 관리한다.

코드

파이썬 최소 구현

import math
from collections import Counter

class BM25:
    def __init__(self, docs, k1=1.2, b=0.75):
        self.k1, self.b = k1, b
        self.tf = [Counter(d) for d in docs]
        self.dl = [len(d) for d in docs]
        self.avgdl = sum(self.dl) / len(docs)
        N = len(docs)
        df = Counter(t for d in docs for t in set(d))
        self.idf = {t: math.log(1 + (N - n + 0.5) / (n + 0.5)) for t, n in df.items()}

    def score(self, query, i):
        s, tf = 0.0, self.tf[i]
        norm = self.k1 * (1 - self.b + self.b * self.dl[i] / self.avgdl)
        for t in query:
            f = tf.get(t, 0)
            if f:
                s += self.idf[t] * f * (self.k1 + 1) / (f + norm)
        return s

    def search(self, query, k=3):
        return sorted(((self.score(query, i), i) for i in range(len(self.tf))), reverse=True)[:k]

docs = ["벡터 검색 은 임베딩 의 거리 로 문서 를 찾는다",
        "BM25 는 단어 빈도 와 문서 길이 로 점수 를 낸다",
        "오류 코드 E1234 는 전원 문제 를 뜻한다",
        "하이브리드 검색 은 BM25 와 벡터 검색 을 합친다"]
bm25 = BM25([d.split() for d in docs])      # 예시라 공백으로 자름. 실제로는 형태소 분석
print(bm25.search(["E1234"]))               # [(1.287..., 2), (0.0, 3), (0.0, 1)]

실제 서비스에서는 직접 구현하기보다 루씬 계열 엔진이나 파이썬 rank_bm25 같은 라이브러리를 쓰고, 역색인으로 질의 단어가 들어 있는 문서만 점수를 계산한다.

엘라스틱서치에서 매개변수 바꾸기

{
  "settings": {
    "index": {
      "similarity": {
        "my_bm25": { "type": "BM25", "k1": 1.5, "b": 0.6 }
      }
    }
  },
  "mappings": {
    "properties": {
      "title": { "type": "text", "similarity": "my_bm25" }
    }
  }
}

유사도는 필드 단위로 지정한다.^[6]

같이 보기

각주

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 Apache Lucene, BM25Similarity.java (주석에 Robertson 외, "Okapi at TREC-3", 1994를 출전으로 밝힘)
↑ ^2.0 ^2.1 ^2.2 Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze, 《Introduction to Information Retrieval》, Cambridge University Press, 2008, 11.4.3절. 온라인판
↑ Xapian, The BM25 Weighting Scheme
↑ Apache Lucene CHANGES.txt, LUCENE-6789 항목(6.0.0)
↑ ^5.0 ^5.1 Elastic 블로그, Practical BM25 Part 1, 2018-04-19
↑ ^6.0 ^6.1 Elasticsearch 문서, Similarity settings
↑ Stephen Robertson, Hugo Zaragoza, 〈The Probabilistic Relevance Framework: BM25 and Beyond〉, Foundations and Trends in Information Retrieval 3(4), 2009. DOI
↑ Yuanhua Lv, ChengXiang Zhai, 〈Lower-bounding term frequency normalization〉, CIKM 2011. DOI
↑ Thibault Formal, Benjamin Piwowarski, Stéphane Clinchant, 〈SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking〉, SIGIR 2021. arXiv:2107.05720
↑ Vladimir Karpukhin 외, 〈Dense Passage Retrieval for Open-Domain Question Answering〉, EMNLP 2020. arXiv:2004.04906
↑ Nandan Thakur 외, 〈BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models〉, NeurIPS 2021. arXiv:2104.08663
↑ Gautier Izacard 외, 〈Unsupervised Dense Information Retrieval with Contrastive Learning〉, 2021. arXiv:2112.09118
↑ Liang Wang 외, 〈Text Embeddings by Weakly-Supervised Contrastive Pre-training〉, 2022. arXiv:2212.03533

참고 문헌

[lucenesrc-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 Apache Lucene, BM25Similarity.java (주석에 Robertson 외, "Okapi at TREC-3", 1994를 출전으로 밝힘)

[irbook-2] 2.0 ^2.1 ^2.2 Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze, 《Introduction to Information Retrieval》, Cambridge University Press, 2008, 11.4.3절. 온라인판

[xapian-3] Xapian, The BM25 Weighting Scheme

[lucenechanges-4] Apache Lucene CHANGES.txt, LUCENE-6789 항목(6.0.0)

[esblog-5] 5.0 ^5.1 Elastic 블로그, Practical BM25 Part 1, 2018-04-19

[essim-6] 6.0 ^6.1 Elasticsearch 문서, Similarity settings

[robertson2009-7] Stephen Robertson, Hugo Zaragoza, 〈The Probabilistic Relevance Framework: BM25 and Beyond〉, Foundations and Trends in Information Retrieval 3(4), 2009. DOI

[bm25plus-8] Yuanhua Lv, ChengXiang Zhai, 〈Lower-bounding term frequency normalization〉, CIKM 2011. DOI

[splade-9] Thibault Formal, Benjamin Piwowarski, Stéphane Clinchant, 〈SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking〉, SIGIR 2021. arXiv:2107.05720

[dpr-10] Vladimir Karpukhin 외, 〈Dense Passage Retrieval for Open-Domain Question Answering〉, EMNLP 2020. arXiv:2004.04906

[beir-11] Nandan Thakur 외, 〈BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models〉, NeurIPS 2021. arXiv:2104.08663

[contriever-12] Gautier Izacard 외, 〈Unsupervised Dense Information Retrieval with Contrastive Learning〉, 2021. arXiv:2112.09118

[e5-13] Liang Wang 외, 〈Text Embeddings by Weakly-Supervised Contrastive Pre-training〉, 2022. arXiv:2212.03533

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]