ElasticSearch - BM25에 대해서 알아보자

개요

• ES에는 search를 위해서 다양한 scoring function들을 지원한다.
• 이에 대해서 자세히 살펴 보도록 하자

TF-IDF

• 먼저 검색의 기초가되는 TF, IDF에 대해서 이해해야한다.
• 필자도 수알못이긴 하지만 이번 기회에 한 번 천천히 살펴서 적어보려고 한다.

시작하기 전에

몇가지 상황을 가정하면서 이해를 도우려고 한다.

• 내가 만약 아이폰12 케이스를 찾는다고, 가정하자. (실제로 찾고 있다.)
• 이 때, 우리는 검색을 "아이폰12 케이스"로 찾을 것이다.
• 이 때, 검색 쿼리는 "아이폰12", "케이스"로 찾게 될 것이다. (실제로 tokenize, filter하는 내용 및 자연어 처리 부분은 좀 더 복잡하지만 개략적으로 이해해보자.)
• 이제 검색엔진에서는 inverted index로 document가 저장되어 있고, 이를 scoring할 것이다.
• 하지만 "아이폰12"와 "케이스" 중에서는 "아이폰12"라는 단어가 상대적으로 더 중요할 것이다.
• 그렇다면 "아이폰12"에 대한 내용이 담긴 문서들에 어떻게 더 가중치를 부여할 것인가??

IDF (Inverse Document Frequency)

• 많은 문서에 term이 포함되어 있다면 해당 term은 중요하지 않을 가능성이 높다. ( 예를 들어, "나", "너", "우리" )
• 따라서 희귀한 term일 수록 높은 가중치를 부여해야 한다.
• 해당 term(단어)이 전체 문서에서 얼마나 자주 등장하는지에 대한 invert 값이다.
• 몇가지 수식이 있지만, log scale을 많이 사용한다.

# docFreq: 해당 term이 포함된 document 갯수
# docCount: 전체 document 갯수
IDF = log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5))

TF (Term Frequency)

• 만약에 해당 term이 해당 문서에서 자주 등장한다면, 해당 문서는 관련도가 높다고 가정한다.
• 해당 term(간단하게 단어라고 이해하면 좋다.)이 해당 문서에서 얼마나 자주 발생하는지 나타낸 것이다.
• 아래는 log scale의 수식이다.

# termFreq: 해당 문서에서 term이 나타난 빈도
TF = log(1 + termFreq)

TF * IDF

• 결국 scoring은 IDF(문서 집합 전체에서 term의 중요도) * TF(문서내의 term 빈도) 표현할 수 있다.
• 기존의 ES에서는 해당 TF-IDF에 몇 가지 factor를 조절해 사용하고 있었다 ( lucene )

BM25 ( OkAPI BM25)

• TF-IDF의 variation이다.
• ES5 이후로 BM25를 기본 scoring algorithm으로 채택되어 사용되고 있다고 한다.
• 기본 TF * IDF에 몇 가지 파라미터가 추가되었다.

k_1 = 1.2 # 단어의 빈도수가 얼마만큼의 가중치를 둘 것인지를 결정하는 요소
b = 0.75 # 평균 대비 문서길이에 대한 weight 가중치
docLength = 10 # 해당 document의 length
avgDocLength = 30 # 일반 document의 length

IDF = log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5))

norm = termFreq * (k_1 + 1)
denorm = termFreq + k_1 * (1 - b + (b * docLength / avgDocLength))
TF = log(norm / denorm)

BM25 = IDF * TF

TF-IDF의 문제점 및 BM25의 차이점

• 기존의 TF-IDF에서는 문서내에 term의 빈도에 따라서 scoring값이 지속적으로 증가하게 된다.
• 이를 조정하기 위해서 k_1값을 통해서, 한 문서 내에서 같은 term이 많이 발견되더라도 일정 수준보다 높아지면 유사한 score에 수렴하게 한다.

K factor를 조정한 내용과 기존 TF-IDF

• b의 경우에는 문서 길이에 대한 가중치를 조정한다. 문서의 길이가 길어질수록 scoring이 낮아지는데, 이에 대한 보정값이다.

결론

• 자세하게 알 필요는 없겠지만 각각의 scoring factor들을 ES에서 조정가능하므로 개념들을 알아놓는 것이 좋을 것 같다.
• 이외에도 몇가지 similarity module이 존재하는데, 필요할 때마다 한가지씩 봐두는 것도 좋을 것 같다.

출처

• TF-IDF wiki
• Okapi BM25 wiki
• ES-BM25
• bm25-elasticsearch-5-0에서-검색하는-새로운-방법
• littlefox님 블로그