BM25

#자료구조/알고리즘

BM25는 텍스트, 자연어 검색에 사용되는 주요 알고리즘 중 하나다. BM은 Best Matching의 축약이며, 여러 변종이 존재한다.

최초의 알고리즘은 80년대, 런던 시립 대학교에서 진행된 연구인 Okapi 프로젝트에서 시작되었다고 한다. 그래서 OKApi BM25라고도 부른다.

기본 개념

BM25의 기본적인 접근 방식은 각 텍스트에 점수를 매기고 단어를 기준으로 일종의 랭킹을 수행하는 것이다.
그래서 일단 형태소 분석 등을 통해 "단어" 단위가 구분되어야 한다는 전제가 있다.

그리고 BM25는 여러개의 점수 기준을 사용해서 좋은 품질을 뽑아내는 것을 중점으로 두는데, 점수에 사용되는 기준값을 정리하면 다음과 같다.

단어의 등장 빈도(Term Frequency): 동일한 단어가 많이 등장할 수록 높은 점수가 부여된다.
IDF (Inverse Document Frequency) - 희귀한 단어에 대해서 높은 점수를 주고, 흔한 단어에 대해서 낮은 점수를 준다. 이를 위해 특정 단어가 전체 데이터에서 얼마나 희귀한지를 측정해둬야 한다.
Document Length Normalization: 동일하게 단어가 포함되더라도, 텍스트가 길 경우 더 낮은 점수를 주고, 텍스트가 짧다면 높은 점수를 준다. 텍스트가 많다면 확률적으로 더 많은 단어를 포함할 수 있기 때문이다.

이를 통해 고품질의 문서 검색을 가능케 하는 것이다.

단어의 빈도 등을 고려해서 검색을 하기 때문에, 무식한 단순 포함 검색에 비하면 합리적이고 납득 가능한 수준의 검색 결과를 기대할 수 있다는 장점이 있다.

그리고 요즘에는 Vector Search와 비교를 많이 하는데, BM25의 가장 강력한 부분은 규칙 기반으로 동작하는 엄격한 단어 포함 검색이라는 것이다. Vector Search처럼 생뚱맞은 값이 나올 일은 없다.

하지만 규칙 기반의 엄격한 알고리즘이기 때문에, 유연성은 많이 부족하다.
문맥을 고려하지 못하며, 동의어 등을 자연스럽게 처리하기 힘들다. 이런건 모델에 기반한 Vector Search가 더 잘하는 영역이다.

BM25의 대표적인 사용 사례는 Lucene/Elasticsearch다.
Elasticsearch는 텍스트 검색에 대한 기본 알고리즘으로 BM25를 사용한다.

그 외에도 텍스트 검색이 필요한 경우에는 지배적으로 쓰인다고 보면 된다.
비슷한 검색엔진인 Apache Solr, Meilisearch 또한 BM25를 사용하며, 검색 로직을 직접 구현할 때도 사용한다.