BM25 in Elasticsearch

Elasticsearch(이하 ES)에서는 쿼리 서칭 알고리즘으로 BM25를 사용하고 있다. BM25는 TFIDF와 수식적으로 상당히 유사하며, TFIDF에 약간의 변형을 가한 정도이다.

BM25의 스코어 식은 아주 간단하게 아래와 같이 나타낼 수 있다. 크게 보면 TFIDF와 마찬가지로 TF * IDF의 값으로 이루어지지만 Normalized TF를 사용한다는 다른 점이 있다.

$$score(D, Q) = \Sigma (IDF(q_i) \times NormTF(q_i))$$

각각의 term을 좀 더 자세히 써보면 아래와 같다.

$$score(D, q_i) = log(1+ \frac{docCount - docFreq + 0.5}{docFreq + 0.5}) \times \frac{f(q_i, D)(k_1+1)}{f(q_i, D) + k_1(1-b+b \frac {|D|}{avgdl})}$$

$$score(D, Q) = \Sigma IDF(q_i) \times \frac{f(q_i, D)(k_1+1)}{f(q_i, D) + k_1(1-b+b \frac {|D|}{avgdl})}$$

(where D = document, Q = input document, q = token in document, docCount = 전체 문서 갯수, docFreq = q가 등장한 문서의 갯수)

ES는 문서를 총 5개의 shad에 분리해서 넣으며, 따로 옵션을 주지 않을 경우 bm25는 그 문서가 존재하는 shad 내에서만 점수를 계산한다. 전체 문서를 대상으로 점수를 계산하고 싶다면 search 쿼리의 옵션으로 search_type=dfs_query_then_fetch를 사용하자(자세한 내용은 https://github.com/elastic/elasticsearch/issues/24429 참고)

BM25 이론적 배경

Improved Text Scoring with BM25(presentation): https://www.elastic.co/kr/elasticon/conf/2016/sf/improved-text-scoring-with-bm25

The Probabilistic Relevance Framework: BM25 and Beyond(paper): http://sci-hub.tw/https://www.nowpublishers.com/article/Details/INR-019