BM25: 30년 된 알고리즘이 아직도 강력한 이유

"임베딩이면 다 되는 거 아니야? 왜 옛날 알고리즘을 배워?"

BM25(Best Matching 25)는 1994년에 만들어졌다. 30년이 지났지만 정확한 키워드 매칭에서는 여전히 최고다.

Elasticsearch, Lucene, Solr... 모든 검색 엔진의 기본이 BM25다.

BM25 공식 해부

Score(D, Q) = Σ IDF(qi) × (f(qi,D) × (k1+1)) / (f(qi,D) + k1 × (1-b + b × |D|/avgdl))

복잡해 보이지만, 세 가지 요소의 곱이다:

1. IDF (역문서 빈도): "희귀한 단어일수록 중요"

IDF(qi) = log((N - n(qi) + 0.5) / (n(qi) + 0.5) + 1)

N = 전체 문서 수
n(qi) = 단어 qi가 등장하는 문서 수

제조 예시:

"설비" -> 거의 모든 문서에 등장 -> IDF 낮음 (0.1)
"OEE"  -> 일부 문서에만 등장 -> IDF 높음 (2.3)
"E-4521" -> 특정 매뉴얼에만 등장 -> IDF 매우 높음 (5.1)

"설비"를 검색해도 별 도움이 안 되지만, "E-4521"은 딱 그 문서를 찾아준다. IDF 덕분이다.

2. TF (단어 빈도): "많이 나올수록 관련 있다"

TF 기여 = (f(qi,D) × (k1+1)) / (f(qi,D) + k1 × ...)

f(qi,D) = 단어 qi의 문서 D 내 출현 횟수
k1 = TF 포화 파라미터 (기본값: 1.2)

k1의 역할:

k1 = 0: TF를 무시 (출현 여부만)
k1 = 1.2 (기본): 적당한 포화 곡선
k1 = 3.0: TF를 더 많이 반영

TF 기여를 k1=1.2 로 실제 계산하면 (f x 2.2) / (f + 1.2):
출현 1회  -> 1.00
출현 2회  -> 1.38  (2배가 아니라 1.38배)
출현 5회  -> 1.77  (거의 포화)
출현 10회 -> 1.96  (포화, 상한은 k1+1 = 2.2)

상한이 k1+1 이라는 점을 기억하라. 아무리 많이 나와도 TF 기여는 2.2 를 넘지 못한다.

"OEE"가 10번 나오는 문서가 1번 나오는 문서보다 관련성이 높지만, 10배 더 좋진 않다. 이것이 "포화(saturation)" 효과다.

3. 문서 길이 정규화: "긴 문서에 불이익"

정규화 = 1 - b + b × (|D| / avgdl)

|D| = 현재 문서 길이 (단어 수)
avgdl = 평균 문서 길이
b = 길이 정규화 강도 (기본값: 0.75)

b의 역할:

b = 0: 길이 무시 (짧은 문서나 긴 문서나 동등)
b = 0.75 (기본): 적당한 길이 페널티
b = 1.0: 최대 길이 페널티

예시 (avgdl = 500):
문서 A (100단어): 정규화 = 0.25 + 0.75 × 0.2 = 0.40 -> 유리
문서 B (500단어): 정규화 = 0.25 + 0.75 × 1.0 = 1.00 -> 기준
문서 C (2000단어): 정규화 = 0.25 + 0.75 × 4.0 = 3.25 -> 불리

제조 문서 최적화 파라미터

왜 b=0.5인가?

여기서 인과를 조심해야 한다. 「길이 편차가 크니까 정규화를 약하게」는 말이 뒤집힌 것이다. 편차가 크다는 것은 길이 정규화가 더 필요한 근거이지 덜 필요한 근거가 아니다.

b 를 낮추는 진짜 이유는 이 코퍼스에서 문서 길이가 관련성을 거의 말해 주지 않기 때문이다. 장비 매뉴얼이 10,000단어인 것은 그 장비를 깊이 다루기 때문이지 주제에서 벗어나서가 아니다. b=0.75 를 그대로 쓰면 긴 매뉴얼이 길다는 이유만으로 점수를 잃고, 50단어짜리 도면 설명이 짧다는 이유만으로 상위에 온다.

즉 긴 매뉴얼이 길다는 이유만으로 덜 관련있는 것이 아니므로 길이 페널티를 완화한다. b 를 정하는 기준은 「길이가 얼마나 흩어져 있는가」가 아니라 「이 코퍼스에서 길이가 관련성을 얼마나 말해 주는가」다.

한국어 + 제조 용어 토크나이징 전략

BM25의 핵심은 토크나이저다. 한영 혼합이 많은 제조 문서에서는 주의가 필요하다.

# 잘못된 토크나이징 1: 어절 통째로
text = "베어링의 교체 주기와 베어링을 점검"
tokens = text.split()
# ['베어링의', '교체', '주기와', '베어링을', '점검']
# 문제: '베어링의'와 '베어링을'이 서로 다른 낱말이 된다

# 잘못된 토크나이징 2: 중복 제거
return list(set(tokens))
# 문제: 문서 안에서 몇 번 나왔는지가 사라진다.
#       모든 낱말의 TF 가 1 이 되므로 위에서 본 k1 포화 곡선이 통째로 죽는다.
#       set 은 순서까지 흩뜨린다.

# 좋은 토크나이징 — pip install kiwipiepy
import re
from kiwipiepy import Kiwi

kiwi = Kiwi()
PRESERVE = re.compile(r'[a-z]+-[a-z0-9]+|iso\s*\d+|ks\s*[a-z]\s*\d+')
CONTENT_TAGS = ('NNG','NNP','NNB','NR','SL','SN','SH','VV','VA','MAG','XR')

def manufacturing_tokenize(text: str) -> list[str]:
    """제조 도메인 토크나이저"""
    low = text.lower()

    # 1. 형태소 분석기가 쪼개면 안 되는 것을 먼저 떼어낸다
    #    (CNC-M500, E-4521, ISO 9001, KS B 1234)
    preserved = []
    def pick(m):
        preserved.append(re.sub(r'\s+', '', m.group(0)))
        return ' '
    masked = PRESERVE.sub(pick, low)

    # 2. 나머지는 형태소로 나누고 내용어만 남긴다 (조사·어미가 여기서 빠진다)
    morphs = [t.form for t in kiwi.tokenize(masked) if t.tag in CONTENT_TAGS]

    # 3. 중복을 제거하지 않는다 — 빈도가 BM25 의 TF 항이다
    return [t for t in preserved + morphs if len(t) > 1]

# ['베어링', '교체', '주기', '베어링', '점검'] — '베어링'이 두 번 남는다

BM25 vs Semantic 정리