1. BM25 검색의 기본 원리
RAG(Retrieval-Augmented Generation) 시스템에서 가장 널리 사용되는 키워드 기반 검색 알고리즘 중 하나가 BM25(Best Matching 25)입니다. BM25는 TF-IDF(Term Frequency-Inverse Document Frequency)를 개선한 알고리즘으로, 문서 길이를 고려하여 더욱 정교한 키워드 매칭을 가능하게 합니다.
BM25의 주요 특징
- TF-IDF를 기반으로 한 향상된 키워드 검색 성능
- 문서 길이에 따른 정규화 지원
여기서 각 파라미터의 의미는: - IDF(qi): 역문서 빈도
- f(qi,D): 문서 D에서 단어 qi의 출현 빈도
- |D|: 문서 D의 길이
- avgdl: 평균 문서 길이
- k1: 항 빈도에 대한 가중치 (일반적으로 1.2~2.0)
- b: 문서 길이 정규화 계수 (일반적으로 0.75)
구현 방식의 차이
일반적으로 Langchain이나 LlamaIndex 같은 프레임워크에서는 실시간으로 코퍼스를 기반으로 BM25를 계산합니다. 하지만 실제 프로덕션 환경에서는 이러한 접근 방식은 효율적이지 않습니다. 대신, 미리 계산된 sparse 임베딩을 벡터 데이터베이스에 저장하는 것이 바람직합니다.
2. 실제 서비스를 위한 BM25 구현 예시
sparse 임베딩 구축하는 방법을 상세히 알아보겠습니다. (간단하게 하기 위해 띄어쓰기 기준으로 토크나이징)
- 문서1: "맛있는 김치찌개 레시피 소개" -> ["맛있는", "김치찌개", "레시피", "소개"]
- 문서2: "김치찌개 된장찌개 비교" -> ["김치찌개", "된장찌개", "비교"]
- 문서3: "김치 일정 온도 유지" -> ["김치", "일정", "온도", "유지"]
쿼리: "맛있는 김치찌개 끓이는 방법" -> ["맛있는", "김치찌개", "끓이는", "방법"]
BM25 점수 계산 과정
- 평균 문서 길이(avgdl): (4 + 3 + 4) / 3 = 3.67
- IDF:
맛있는: log((3-1+0.5)/(1+0.5)) = 0.847
김치찌개: log((3-2+0.5)/(2+0.5)) = 0.182
끓이는: log((3-0+0.5)/(0+0.5)) = 1.946
방법: log((3-0+0.5)/(0+0.5)) = 1.946
쿼리-문서1 점수:
맛있는:
- f(qi,D) = 1
- 정규화 항 = (1.2 + 1) / (1 + 1.2 * (1 - 0.75 + 0.75 * 4/3.67)) = 0.870
점수 = 0.847 * 1 * 0.870 = 0.737
김치찌개:
- f(qi,D) = 1
- 정규화 항 = 0.870
점수 = 0.182 * 1 * 0.870 = 0.158
문서1 최종 점수: 0.895
쿼리-문서2 점수:
김치찌개:
- f(qi,D) = 1
- 정규화 항 = (1.2 + 1) / (1 + 1.2 * (1 - 0.75 + 0.75 * 3/3.67)) = 0.902
점수 = 0.182 * 1 * 0.902 = 0.164
문서2 최종 점수: 0.164
쿼리-문서3 점수:
쿼리 단어와 매칭되는 토큰이 없음
문서3 최종 점수: 0
위와 같은 과정을 통해 점수가 가장 높은 문서1을 검색하게 됩니다. 하지만 문서가 많아질수록 위와 같이 검색을 할 수 없으니 모든 문서를 미리 벡터화하여 저장해야 합니다. 즉, 문서를 미리 벡터화하여 저장해두고, 쿼리도 같은 방식으로 벡터화하여 벡터 간 유사도를 계산하는 것입니다.
1. 전체 어휘 사전(Vocabulary) 구축
- 모든 문서의 고유 토큰을 인덱싱:
vocabulary = {
'맛있는': 0,
'김치찌개': 1,
'레시피': 2,
'소개': 3,
'된장찌개': 4,
'비교': 5,
'김치': 6,
'일정': 7,
'온도': 8,
'유지': 9
}
2. IDF 계산
맛있는: log((3-1+0.5)/(1+0.5)) = 0.847
김치찌개: log((3-2+0.5)/(2+0.5)) = 0.182
레시피: log((3-1+0.5)/(1+0.5)) = 0.847
소개: log((3-1+0.5)/(1+0.5)) = 0.847
된장찌개: log((3-1+0.5)/(1+0.5)) = 0.847
비교: log((3-1+0.5)/(1+0.5)) = 0.847
김치: log((3-1+0.5)/(1+0.5)) = 0.847
일정: log((3-1+0.5)/(1+0.5)) = 0.847
온도: log((3-1+0.5)/(1+0.5)) = 0.847
유지: log((3-1+0.5)/(1+0.5)) = 0.847
3. 각 문서의 Sparse 벡터 생성
- 문서1:
{
0: 0.847, # '맛있는'
1: 0.182, # '김치찌개'
2: 0.847, # '레시피'
3: 0.847 # '소개'
} - 문서2:
{
1: 0.182, # '김치찌개'
4: 0.847, # '된장찌개'
5: 0.847 # '비교'
} - 문서3:
{
6: 0.847, # '김치'
7: 0.847, # '일정'
8: 0.847, # '온도'
9: 0.847 # '유지'
}
4. 쿼리 "맛있는 김치찌개 끓이는 방법"을 같은 방식으로 벡터화:
{
0: 0.847, # '맛있는'
1: 0.182 # '김치찌개'
}
5. 내적(IP) 연산 계산
- 문서1과 쿼리 벡터의 내적
공통 인덱스: - 인덱스 0 ('맛있는'): 0.847 × 0.847 = 0.717
- 인덱스 1 ('김치찌개'): 0.182 × 0.182 = 0.033
최종 유사도 = 0.717 + 0.033 = 0.750
- 문서2와 쿼리 벡터의 내적
공통 인덱스: - 인덱스 1 ('김치찌개'): 0.182 × 0.182 = 0.033
최종 유사도 = 0.033
- 문서3과 쿼리 벡터의 내적
공통 인덱스: 없음
최종 유사도 = 0
위와 같은 방식으로 문서를 미리 벡터화하여 저장하고 검색 시에는 단순 내적 연산만 수행하여 대규모 문서에서도 빠른 검색이 가능합니다.
kiwi 토크나이저를 적용한 코드는 아래 링크에서 확인할 수 있습니다
https://github.com/KeonwooChoi/kiwi-bm25-embedding