BM25

검색엔진에서 가장 일반적으로 사용되는 스코어링 알고리즘은 TF-IDF와 BM25가 있음.

최근 버전에서는 디폴트로 BM25 알고리즘을 사용한다.

루씬을 코어로 사용하고있는 솔라와 엘라스틱 서치도 최근 버전에서 BM25가 기본으로 채택되었음.

 

루씬의 TF-IDF에서 등장하는 용어

 

TF : 단어 빈도

TF는 단어빈도로, 많이 등장할수록 문서의 검색 점수는 당연히 높아진다.

 

IDF : 역문서 빈도

IDF는 corpus에서 단어가 얼마나 많이 나오는가를 보는 수치이다. 여러 문서에 등장할수록 IDF는 낮아진다.

 

norm : 문서길이 가중치

norm은 문서길이 가중치로, 단어가 등장하는 문서의 길이에 대한 가중치로, 문서의 길이가 길수록 검색 점수가 낮아진다.

 

BM25 스코어를 계산하는 수식

 

$ N = 문서의\,수 $

$ df_{t} = 단어를\,포함하고\,있는\,문서의\,수 $

$ f_{t,d} = 문서에\,포함된\,단어의\,빈도 $

 

$$ bm25(d) = \sum_{t \in q , f_{t,d} {>} 0 }{log(1+ \frac{N-df_{t}+0.5}{df_{t}+0.5})} \times \frac{f_{t,d}}{f_{t,d} + k \times (1-b+b \frac{l(d)}{avgdl})} $$

 

bm25의 검색 점수를 계산하는 수식은 위와 같은데, bm25에서는 각각의 파라메터들의 영향력이 어떻게 변화하는지 아래에서 확인할 수 있다.

 

$$ score_{q,d}=norm(q) \times \sum_{t\,in\,q}{ \textcolor {red}{ \sqrt{tf_{t,d}} } \times \textcolor {blue}{idf^2_{t}}  \times \textcolor {orange}{norm(d, field)} \times boost(t) } $$

$$ bm25(d) = \sum_{t \in q , f_{t,d} {>} 0 }{ \textcolor {blue}{log(1+ \frac{N-df_{t}+0.5}{df_{t}+0.5})}} \times \frac{ \textcolor {red} {f_{t,d}}} { \textcolor {red}{f_{t,d} + k} \times \textcolor {orange}{(1-b+b \frac{l(d)}{avgdl})} } $$

 

IDF의 영향력 증가

BM25에서는 TF-IDF와 다르게 IDF 에서의 영향력이 강해진다.

문서빈도(DF)가 높아지면 검색 점수가 0으로 수렴한다. 즉, 불용어가 검색 점수에 영향을 덜 미치게 된다.

(을, 를, 이, 가 등은 어느 문서에나 등장할 수 있다, 문서빈도가 높을 수 있다)

 

TF의 영향력 감소

TF-IDF에서는 단어 빈도(TF)가 높아 질 수록 검색 점수도 높아지는데, BM25에서는 특정 점수로 수렴한다.

 

norm 문서 길이 가중치의 영향력 감소

BM25에서는 문서의 평균길이 (avgdl)를 사용하여 문서의 길이가 검색 점수에 영향을 덜 미치게 된다.

참고자료