BM25

주어진 쿼리에 대해 문서와의 연관성을 평가하는 ranking 알고리즘. TF-IDF 계열의 대표적인 sparse retrieval 방법으로, term frequency saturation과 document length normalization을 도입하여 TF-IDF의 한계를 개선했다.

B) Score 계산

BM25 는 bag of words 개념을 사용하여 쿼리에 있는 용어가 각 문서에 얼마나 자주 등장하는지 평가한다.

키워드 $q_1,\dots ,q_n$ 을 포함하는 쿼리 $Q$ 가 주어질 때, 문서 $D$ 에 대한 BM25 점수는 아래와 같다.

$$\mathrm{score}(D,Q)=\sum _{i=1}^n\mathrm{IDF}\left(q_i\right)\cdot \frac{f\left(q_i,D\right)\cdot \left(k_1+1\right)}{f\left(q_i,D\right)+k_1\cdot \left(1-b+b\cdot \frac{|D|}{\text{avgdl}}\right)}$$

B.1) Notation

기호	의미	비고
$q_i$	쿼리의 $i$ 번째 토큰
$f(q_i,D)$	토큰 $q_i$ 가 문서 $D$ 에 나타나는 빈도 (TF)	자주 나타날수록 점수 증가
$\Vert D\Vert$	문서 $D$ 의 길이 (토큰 수)
$\text{avgdl}$	문서 집합의 평균 문서 길이
$k_1$	TF saturation 파라미터	보통 1.2 ~ 2.0
$b$	문서 길이 보정 파라미터	보통 0.75, 0이면 길이 무시
$\mathrm{IDF}(q_i)$	Inverse Document Frequency	희귀 단어일수록 높은 값

B.2) IDF 계산

$$\mathrm{IDF}\left(q_i\right)=\ln \left(\frac{N-n\left(q_i\right)+0.5}{n\left(q_i\right)+0.5}+1\right)$$

여기서:

• $N$: 전체 문서 개수
• $n(q_i)$: 토큰 $q_i$ 를 포함하는 문서의 수

C) Vs. TF-IDF

	TF-IDF	BM25
TF 반영	선형 증가 (TF가 높을수록 비례 증가)	비선형 포화 ($k_1$ 이후 수렴)
문서 길이	고려하지 않음	$b$ 파라미터로 정규화
결과	긴 문서에 유리, TF 과대 반영	공정한 비교 가능

C.1) Term Frequency Saturation

TF-IDF는 단어 빈도가 증가하면 점수도 선형으로 계속 증가한다. 예를 들어 ‘계약’이 10번 나온 문서는 1번 나온 문서보다 10배 높은 점수를 받는다. 하지만 실제로는 일정 횟수 이상 반복되면 추가 등장의 정보량은 크지 않다.

BM25는 $k_1$ 파라미터로 이를 제어한다. TF가 $k_1$ 을 넘어가면 점수 증가폭이 급격히 줄어들어 포화(saturation)된다.

• $d_w$: TF (Term Frequency)

C.2) Document Length Normalization

TF-IDF는 문서 길이를 고려하지 않으므로, 긴 문서는 자연스럽게 단어가 더 많이 등장하여 부당하게 높은 점수를 받을 수 있다.

BM25는 $\frac{|D|}{\text{avgdl}}$ 비율로 문서 길이를 정규화한다. 평균보다 짧은 문서에서 단어가 등장하면 더 높은 가중치를, 긴 문서에서는 낮은 가중치를 부여한다. 파라미터 $b$ 가 이 보정의 강도를 조절한다.

D) 한계점

• 개별 단어의 빈도만 기반으로 하므로, 단어나 구문의 의미나 맥락을 이해하지 못한다 (어휘 불일치 문제)
• 동의어, 유의어 관계를 포착할 수 없다 (e.g. “자동차” 검색 시 “차량”이 포함된 문서를 놓침)
• 이를 보완하기 위해 SPLADE 같은 learned sparse retrieval이나, dense retrieval과의 hybrid 방식이 사용된다
• 스코어가 unbounded이고 query/corpus dependent하여, vector similarity 등 다른 시그널과 직접 결합이 어렵다 → Bayesian BM25로 calibrated probability 변환 가능

E) References

• Okapi BM25 - Wikipedia