BM25

개요

BM25(Best Matching 25)는 확률적 언어 모델 계열의 전통적인 순위 결정 함수로, 질의와 문서 간 관련도를 계산하여 검색 결과를 정렬하는 데 사용된다. Okapi 프로젝트에서 발전한 BM 계열 순위 함수의 다섯 번째 버전으로, 실무 검색 엔진과 학술 평가에서 사실상의 표준 기준점으로 자리 잡았다.

배경과 역사

• 1970~80년대 런던 시티 대학교의 정보 검색 연구 그룹이 확률적 검색 모델을 발전시키면서 Okapi 시스템이 등장했다.
• BM25는 Robertson, Walker 등이 1990년대 중반 발표한 Okapi BM25 공식을 통해 대중화되었으며, 이후 TREC 벤치마크 대회에서 기준 모델로 널리 활용되었다.
• 현재도 Elasticsearch, Lucene, Vespa, OpenSearch 등 주요 검색 엔진이 기본 점수 함수로 채택하고 있다.

기본 수식

질의 $q$와 문서 $d$ 사이의 BM25 점수는 다음과 같다.

$$BM25(q,d)=\sum _{t\in q}\mathrm{IDF}(t)\cdot \frac{f(t,d)\cdot (k_1+1)}{f(t,d)+k_1\left(1-b+b\cdot \frac{|d|}{\text{avgdl}}\right)}$$

여기서 사용되는 역문헌빈도는 보통 아래와 같은 스무딩 형태를 취한다.

$$\mathrm{IDF}(t)=\log \left(\frac{N-n_t+0.5}{n_t+0.5}+1\right)$$

• $f(t,d)$: 용어 $t$의 문서 내 등장 횟수(term frequency)
• $|d|$: 문서 길이(토큰 수)
• $\text{avgdl}$: 말뭉치 전체 문서 길이의 평균
• $N$: 전체 문서 수, $n_t$: 용어 $t$가 등장한 문서 수
• $k_1$, $b$: 조정 파라미터 (보통 $k_1\in [1.2,2.0],b\in [0.5,0.9]$)

구성 요소 해설

• 용어 빈도 보정: 분자 $f(t,d)\cdot (k_1+1)$는 반복 출현을 강조하되, 분모의 $k_1$ 덕분에 포화 곡선 형태로 기여도가 제한된다.
• 문서 길이 정규화: $b$와 $|d|/\text{avgdl}$ 항은 문서가 평균보다 길 때 과도한 점수를 방지하며, $b=0$이면 길이 정규화를 무시한다.
• IDF 스무딩: $+0.5$는 극단값에 대한 안정성을 제공하며, 용어가 거의 모든 문서에 등장하면 IDF가 0에 가까워져 영향력이 줄어든다.

파라미터 선택 가이드

• $k_1$ (term saturation): 값이 클수록 용어 빈도의 영향이 강해진다. 뉴스, 위키처럼 긴 문서에는 1.5~1.9 범위가 자주 사용된다.
• $b$ (length normalization): 0.7~0.8이 기본값으로 쓰인다. 문서 길이 편차가 큰 경우(예: 블로그, 논문)에는 높은 값을, 짧은 쿼리-짧은 문서 환경(예: FAQ)에서는 낮은 값을 고려한다.
• 데이터 기반 튜닝: 학습 데이터가 있다면 MAP, nDCG, Recall 등 평가 지표를 기준으로 그리드 서치나 베이지안 최적화를 수행한다.

BM25와 TF-IDF 비교

관점	TF-IDF	BM25
용어 빈도 처리	선형 증가	포화 형태로 증가, 과도한 빈도 완화
문서 길이 보정	명시적 요소 없음	$b$ 파라미터로 조절
파라미터	없음 (또는 TF 스케일링만)	$k_1$, $b$ 두 개
구현 난이도	매우 단순	약간 복잡하지만 표준 라이브러리 존재
성능	베이스라인 수준	대부분의 말뭉치에서 TF-IDF 대비 우수

변형 모델

• BM25+: 극도로 짧은 문서에서 점수가 0으로 수렴하는 문제를 해결하기 위해 상수 $\delta$를 추가한 버전.
• BM25L: 문서 길이 정규화를 선형으로 보정하여 길이 편차가 큰 말뭉치에서 안정성을 높인다.
• BM25F: 여러 필드(제목, 본문, 앵커 텍스트 등)를 서로 다른 가중치로 결합하는 확장.
• PL2, DFR 계열과의 결합: 확률적 언어 모델의 다른 변형과 결합하여 세분화된 스무딩 전략을 적용하기도 한다.

구현 시 고려 사항

• 토크나이징: 형태소 분석 또는 띄어쓰기 기반 토크나이징 결과에 따라 문서 길이와 용어 빈도가 크게 달라지므로, 검색 대상 언어에 맞는 전처리가 중요하다.
• 불용어(stopword) 처리: 불용어가 제거되면 IDF가 더 뚜렷하게 작동한다. 다만 도메인 특성상 의미 있는 빈출어가 있다면 화이트리스트를 유지한다.
• 정규화 일관성: 학습 시점과 서비스 시점의 평균 문서 길이($\text{avgdl}$)가 달라지면 점수 분포가 흔들릴 수 있으므로, 주기적으로 재계산하거나 온라인 통계를 사용한다.
• 효율성: 역색인(index)을 구성할 때 문서 길이, 용어 빈도를 함께 저장하면 BM25 계산 비용을 줄일 수 있다.
• 실험 문화: 파라미터 튜닝 외에도 리랭킹 모델(예: 학습 기반 랭킹 모듈)과 결합하여 성능을 끌어올리는 방식이 일반적이다.

참고 자료

• Stephen Robertson, Karen Sparck Jones, “Relevance weighting of search terms,” 1976
• Stephen E. Robertson, Steve Walker 등, “Okapi at TREC-3,” 1996
• Christopher D. Manning 외, Introduction to Information Retrieval, Chapter 11: Probabilistic Information Retrieval
• Elasticsearch 문서: BM25 Similarity 설정 및 튜닝 가이드