BM25 algorithm

BM25는 Elasticsearch의 키워드 검색랭킹 알고리즘으로 유명하다. 어떤 의도로 개발된 방법이고 어떻게 계산되는지 간단하게 알아보자.

BM25의 수식은 아래와 같다. IDF부분과 TF부분을 곱하여 계산한다.

먼저 간단하게 TF, IDF의 개념에 대해 알아보자.

q: 질의(query), D: 문서(document), t:질의에 포함된 단어(term), k: TF 조절 하이퍼파라미터, b: 문서길이 보정 하이퍼파라미터, avgD: 전체 문서의 평균길이, ❘D❘: 문서 D의 길이(단어 수)

TF(Term Frequency)는 문서에서 단어(term)의 빈도를 뜻한다.

문서A: "He is a good boy. She is a bad girl. I am a handsome guy."
TF("is", Document(A)) = 2/15 
TF("He", Document(A)) = 1/15

문서A에서 15개의 단어 중 is이라는 단어는 2번 등장하였다. TF를 기준으로 한번씩 등장한 He나 She보다 더 중요하다고 여겨진다. 그러나 관점을 바꾸면 많이 등장하는 단어가 중요한 단어가 아닐 수도 있다.

위 문서에서 is는 두번 등장하지만 He, She, I 보다 문서에서 의미를 갖는다고 여기기 어렵다. 이러한 단점을 보완하기 위해 IDF가 등장한다.

IDF(Inverse Document Frequency)는 단어 t의 역문서 빈도를 구하는 방법이다. 전체 문서에서 단어의 희귀도를 측정한다. 자주 등장하는 단어는 낮은 가중치를 받고 드물게 등장하는 단어는 높은 가중치를 받는다. 

문서A에서 단어 is는 두 번 등장해 TF 관점에서는 높은 점수를 얻겠지만 IDF는 각각 한번씩 등장한 He, She, I 보다 낮은 점수를 얻는다. 문장A에서 is보다 He, She, I가 의미를 갖는데 더 큰 가치가 있기 때문이다. IDF는 기본적으로 아래와 같이 구한다.

N: 전체 문서의 수, n_t: 단어 t가 등장한 문서의 수

문서A를 문장 단위로 쪼개 A-1, A-2, A-3으로 만들어 몇 개 단어에 대해 IDF를 구해보자.

A-1: "He is a good boy."
A-2: "She is a bad girl."
A-3: "I am a handsome guy."

IDF("He") = 3/1, IDF("She") = 3/1, IDF("is") = 3/2로 문서에서 덜 반복하는 He, She가 is보다 더 점수가 높다.

Elasticsearch 블로그의 "BM25와 변수" 글에서는 IDF를 다음과 같이 설명한다.

Elastic 수식의 IDF 구성 요소는 모든 문서에서 어떤 단어가 출현하는 빈도를 측정하고 일반적인 단어에 "페널티를 적용"합니다.

IDF 수식 by elasticsearch 공식블로그

위의 수식을 보면 전체 문서(docCount)에서 단어의 빈도 f(q)로 나누는 것이 식의 핵심임을 알 수 있는데, 빈도가 높아질 수록 스코어가 낮아지는 것을 알 수 있다. 

TF와 IDF를 함께 사용하면 특정 문서에서 중요하면서도 문서 집합 전체에서는 드물게 나타나는 희귀한 단어를 강조할 수 있다.

Elasticsearch에서는 TF-IDF를 보완해 랭킹알고리즘으로 사용한다. 어떤 방식으로 보완하는지 알아보자.

다시 BM25 수식을 보자. $|D|/avgD$를 통해 문서의 길이에 대해 페널티를 부여한다. 문서의 길이에 대한 중요도를 강조하려면 b의 크기를 크게 설정하면 된다(default 0.75 사용). 하이퍼파라미터 k를 통해서는 전체 점수에서 TF에 대한 비중을 조절한다. 예를들어 k가 0에 가깝다면 TF의 값이 전체 스코어에 미치는 영향은 미비하다. 반대로 k값이 무한대에 가깝다면 k에 비례해서 커지게 된다(default 1.2). k값은 최대 2까지 사용하여 TF의 값이 전체 스코어에 미치는 영향을 조절한다.

q: 질의(query), D: 문서(document), t:질의에 포함된 단어(term), k: TF 조절 하이퍼파라미터, b: 문서길이 보정 하이퍼파라미터, avgD: 전체 문서의 평균길이, ❘D❘: 문서 D의 길이(단어 수)

 

Reference
https://www.elastic.co/kr/blog/practical-bm25-part-2-the-bm25-algorithm-and-its-variables