Scoring Algorithm

Scoring Algorithm (a.k.a Similarity Algorithm)이란, 입력한 쿼리에 가장 적합한 도큐먼트를 찾아내기 위해 점수를 매기는 알고리즘을 말합니다. 예를 들어 '알고리즘'이라는 단어가 포함된 게시글을 검색한다고 가정해봅시다. 분명 검색을 하는 사람의 의도는 알고리즘과 관련된 게시글을 찾는 것일 것입니다.

하지만 누군가 '알고리즘'이라는 단어만 1000번 반복하여 게시글을 작성한다면 어떻게 될까요? 아무런 장치가 없다면 의미없이 단어를 반복한 게시글의 점수가 가장 높을 것이고, 검색결과로 출력될 것입니다. 또, '알고리즘'이라는 단어가 세번 나온 장편소설보다 두번 나온 짧은 뉴스 기사가 더 알고리즘과 관련이 높아야 할 것입니다. 이렇게 여러 조건을 고려하며 가장 쿼리에 가까운 내용의 도큐먼트를 찾아내는 것이 바로 유사도 알고리즘입니다.

엘라스틱서치가 유사도 점수를 계산하기 위해 사용하는 알고리즘은 여러가지가 있습니다. 엘라스틱서치 2.4버전 까지는 TF-IDF 알고리즘을, 5.0버전부터 Okapi BM25 알고리즘을 기본 유사도 알고리즘으로 채택하여 사용하고 있습니다. 그 외에도 DFR, DFI 등 직접 지정 가능한 여러 알고리즘이 있으나, 본 포스팅에서는 공식 Default 알고리즘으로 채택되었던 TF-IDF와 Okapi BM25에 대해 알아보며 두 알고리즘의 차이점을 기술할 예정입니다.

Note : 엘라스틱서치는 키바나, 로그스태시와 같은 엘라스틱 스택과 버전을 통일하기 위해 2.4버전 이후 바로 5.0 버전으로 업그레이드 되었습니다.

TF-IDF는 'Term Frequency - Inverse Document Frequency'의 약자로, 가장 대중적으로 오래동안 사용되어진 알고리즘이다. TF-IDF의 TF는 문서 내에서 단어가 얼마나 많이 반복되었는지를 뜻하며, IDF는 단어가 포함된 도큐먼트가 얼마나 많은지를 뜻합니다. 단어의 반복이 많아야 유사도가 높기 때문에 점수가 높을 것이며, 단어가 포함된 다른 도큐먼트가 적어야 희소성이 높기에 점수가 높을 것입니다. 엘라스틱서치는 기본 TF-IDF 알고리즘에 Query normalizer, Coordination factor, Boost, Field length normalizer를 추가하여 점수계산의 정확도를 향상시키고 비교에 최적화시켰습니다. 엘라스틱서치의 TF-IDF 점수 계산 방식은 아래와 같은 과정으로 이루어 집니다.

순서대로 천천히, 최대한 자세하고 쉽게 설명해보겠습니다.

Query Normalization Factor(queryNorm)은 쿼리 결과로 나올 점수를 표준화 하기 위해 사용됩니다. 이해를 돕기 위해 좀 더 쉽게 표현해보겠습니다. 사용자가 던진 쿼리들의 결과로 나온 점수끼리 서로 비교하기 위해서는, 점수가 천차만별인 것 보다는 표준화된 것이 비교하기 편리합니다. 극단적으로 같은 검색범위에 여러가지 쿼리를 던졌을 때 나온 결과값 중 어떤 것은 100만점이고, 어떤 것은 1000점이고, 어떤 것은 1점이라면 이들을 비교하는 것이 쉽지 않을 것입니다. (물론 이렇게 극단적인 점수 결과가 나오지는 않습니다.) queryNorm은 바로 이것을 해결하기 위한 방안으로 설계된 공식입니다.

공식문서의 설명에 따르면 queryNorm은 계산식의 시작 부분에 있으나, 실제 계산은 IDF 가중치 계산이 끝나야 가능합니다. 요소로 IDF 가중치를 사용하기 때문입니다. 수식에서 t는 term을 의미하며, 분모로 총 n개의 term에 대한 IDF 가중치 w를 각각 제곱하여 합산한 결과를 사용합니다. 그 결과를 1에서 나눈 것이 바로 Query Normalization Factor 입니다.

아이러니하게도 공식문서에 따르면 queryNorm의 설계 의도가 서로 다른 쿼리 결과를 비교하기 위한 것이지만, 지금은 단일 쿼리 내에서 여러 term의 결과 정렬을 위한 표준화 인수로만 사용되고 있다고 합니다. 유사도 점수인 '_score'가 오직 현재 쿼리의 결과를 정렬하는 데에만 쓰이고 있기 때문이라네요. 

엘라스틱서치에도 데이터노드를 조율하기 위한 coordination 노드가 있듯, 유사도 점수 계산식에도 가중치를 조율하기 위한 coordination factor가 있습니다. 예를 들어 '달콤한 사과 젤리'라는 쿼리문이 있고, 각각의 term에 대한 가중치가 2라고 가정해봅시다. 만약 '달콤한'이라는 term이 포함된 도큐먼트는 가중치가 2x1로 2가 됩니다. '달콤한 사과'라면 가중치가 2x2=4, '달콤한 사과 젤리'라면 2x3=6입니다. 이 계산방식대로라면 쿼리의 모든 term이 일치하는 도큐먼트와, 일부만 일치하는 도큐먼트간의 가중치 차이가 크지 않습니다. 

이것을 해결하기 위한 방안이 바로 coordination factor입니다. coordination factor의 의도는 '쿼리에 포함된 term의 비율이 높을수록 더 높은 가중치를 부여하는 것' 입니다. 이를 위해 기존 가중치 계산법에 term 개수만큼 나누고, 도큐먼트에 포함된 term 개수만큼 곱하는 과정을 거칩니다. 즉 '달콤한'만 포함된 도큐먼트는 가중치가 2x1x(1/3)으로 계산하여 0.67이 됩니다. '달콤한 사과'는 2x2x(2/3)으로 계산하여 2.7, '달콤한 사과 젤리'는 2x3x(3/3)로 6이 됩니다. 더 많은 단어를 포함하는 도큐먼트의 점수가 그렇지 않은 도큐먼트의 점수보다 확연히 높습니다.

coordination factor 계산이 필요하지 않은 경우도 있습니다. 바로 동의어나 유사한 의미를 가진 용어들을 검색할 때 인데요, 예를들어 'jump', 'hop', 'leap'와 같이 비슷한 의미의 용어를 함께 검색할 때 입니다. 엘라스틱서치는 주요한 Synonyms들의 경우 자동으로 coordination factor 계산을 disable 하며, disable_coord 필드에 true 값을 주는 것으로 수동 disable도 가능합니다.

term의 개수만큼 반복하여 ⑤~⑧번을 계산한 결과로 나온 가중치의 총합입니다.

Term Frequency란 도큐먼트 내에서 term의 빈도수를 의미합니다. 계산식은 도큐먼트 내 term의 개수를 Square root하는 것으로 구성되어 있습니다. 도큐먼트 내의 term 개수가 많을 수록 값이 증가하는데, 이 때문에 term이 너무 많으면 그에 따라 증가하는 유사도 점수로 인해 부정확한 결과가 도출됩니다.

이를 완화하기 위해 빈도수에 Square root를 해주는 것입니다. 단순히 term 개수를 그대로 사용하면 term의 증가에 따라 가중치가 비례해서 그대로 오르지만, square root의 경우에는 root 그래프 함수의 모양을 따라 상승 폭이 줄어들기 때문입니다. 즉, 표준화 효과라고 볼 수 있습니다. 

그럼에도 불구하고 값이 수렴하지 않고 발산하기 때문에, 용어가 굉장히 많이 반복되는 경우 값이 너무 커진다는 단점이 있습니다. 엘라스틱서치가 TF-IDF에서 Okapi BM25 알고리즘으로 전환하게 된 이유 중 하나입니다.

Inverse document frequency란, 쿼리의 term이 얼마나 많은 도큐먼트에 존재하는지를 뜻합니다. 예를 들어 'the'나 'a' 같은 단어는 대부분의 도큐먼트에 존재하므로 'sunmin'과 같은 사람의 이름보다 중요도가 낮을 것입니다. 다시 말해, 일부 또는 하나의 도큐먼트에만 집중된 term이 term과 관련되었을 가능성이 높으므로 더 많은 가중치가 부여되어야 한다는 것입니다.

IDF 공식을 살펴보겠습니다. 전체 도큐먼트의 수(numDocs)를 term이 포함된 도큐먼트의 수(docFreq)에 1을 더한 값으로 나눕니다. 여기서 1을 더하는 이유는, term을 포함하고 있는 도큐먼트의 수가 0일 수 도 있기 때문에 분모가 0이 되는 것을 방지하기 위해서입니다. 그리고 그 결과에 log를 해줌으로서 표준화를 시켜주는데, 이는 TF의 square root 처럼 값의 상승폭을 억제하는 효과가 있습니다.

엘라스틱서치에서 유사도 점수를 계산 할 때 추가적으로 점수 가중치를 부여할 수 있는데, Indexing Time에 부여하는 방식과, Query Time에 부여하는 방식 두 가지로 나뉩니다. 그 중 첫 번째인 Indexing Time에 부여하는 방식으로, search API 사용시에 특정 인덱스를 지정하여 가중치를 부여하는 Index Time Boosting이 있습니다. 

예를 들어, 위의 예시처럼 최근에 생성된 인덱스에 더 높은 가중치를 부여하고 싶은 경우에 Index Time Boosting을 사용할 수 있습니다. 조금 더 정확하게 말하자면, 최근 사용된 term일 수 록 더 중요도를 부여하고 싶을 때 사용한다는 것입니다. 쉬운 예시를 하나 들어 보겠습니다. 전세계적으로 'Cold'라는 단어가 'Covid'라는 단어보다 먼저 사용되어왔고, 사용된 빈도수도 절대적으로 많을 것입니다. 단어의 생성시기를 고려하지 않고 점수를 부여한다면 당연히 'Covid'라는 term의 유사도 점수가 'Cold'대비 현저히 낮을 것입니다.

Index Time Boost는 추후 설명할 Field-length norm 값과 합쳐져 저장되는데, 이 부분은 ⑧번에서 조금 더 자세히 살펴보겠습니다.

두번째로, 인덱스 뿐 아니라 필드 자체에도 부스팅 점수를 부여할 수 있습니다. 예를 들어 '달콤한 사과 젤리'라는 문장을 제목 필드 뿐 아니라 내용필드에서도 찾고 싶은 경우에는 두개의 쿼리가 필요할 것입니다. 이 중 제목 필드가 중요하다면 이 제목 필드에 해당하는 쿼리에 부스팅 점수를 부여할 수 있습니다. 예를 들어 위와 같이 제목과 내용으로 구성된 인덱스 'book'을 생성해보겠습니다.

그리고 제목과 내용에 각각 '달콤한 사과 젤리' 라는 쿼리를 부스팅 점수 없이 주어보겠습니다. 이 경우 제목이 일치하고 내용도 가장 비슷한 도큐먼트 1번은 2.58점, 그 다음으로 비슷한 도큐먼트 2번은 0.7점, 그리고 도큐먼트 3번은 0.29점이라는 점수가 도출되었습니다. 도큐먼트 1번과 3번의 점수 차이는 약 8.6배 정도입니다.

이제 제목에 부스팅 점수 10을 추가해보겠습니다. 그러자 도큐먼트 1번은 16.1, 2번은 5.87, 3번은 1.63의 점수가 도출되었고, 1번과 3번의 점수 차이는 약 10배 정도로 부스팅 점수가 없을 때 보다 더 벌어졌습니다.

위의 부스팅 예제에서는 제목 필드가 내용 필드보다 더 중요하다는 이유로 부스팅 점수를 부여하였지만, 실제 사용할 때에는 테스트 과정이 필요합니다. 왜냐하면 일반적으로 제목은 필드의 길이가 짧고 내용은 필드의 길이가 긴데, 엘라스틱서치는 길이가 짧은 필드에 자동으로 가중치를 부여하기 때문입니다. 이미 길이에 따른 가중치가 부여되고 있기 때문에 필드 자체에 가중치를 부여하는데에는 테스트 과정을 통해 더 나은 점수치가 나오는지 확인해보는 것을 추천합니다. 

계산식은 필드의 총 단어 개수를 Square root한 값을 1에서 나눈 값입니다. 앞선 Term Frequency 설명에서도 나왔듯 표준화를 위해 Square root를 사용하였습니다.

만약 필드 길이에 따른 normalizing을 원하지 않는다면, 필드 매핑 설정에서 norms필드의 enabled 옵션을 false로 설정하는 방법도 사용할 수 있습니다.

이에 더불어 엘라스틱서치에서는 저장 공간의 효율을 위해 ⑦에서 설명한 Index Time Boosting 가중치를 Field length normalizer와 함께 저장합니다. 이 두 요소는 합쳐져 string 타입의 필드 하나당 1바이트의 공간만을 차지합니다. 1비트, 1바이트라도 공간 절약을 하려는 엘라스틱서치의 노고가 느껴지는 부분입니다.

일반적인 Okapi BM25 알고리즘의 구조는 위와 같습니다. 각 변수들에 대한 자세한 설명은 아래 엘라스틱서치의 BM25 알고리즘과 함께 기술하겠습니다. 

Okapi 알고리즘에 대해 자세히 알고 싶으신 분이 계시다면 논문 'Okapi BM25 단어 가중치법 적용을 통한 문서 범주화의 성능 향상, 이용훈, et al'을 읽어보시는 것을 추천드립니다. Okapi BM25 알고리즘 뿐 아니라 TF-IDF(역빈도 가중치법), TF-ICF(역범주 가중치법), TF-ISF(역문장 가중치법) 4가지로 진행한 범주화 실험 결과를 알 수 있습니다. 짧은 요약을 원하시는 분에게 결론을 말씀드리자면, SVM과 KNN알고리즘 두가지로 나누어 실험한 측정률 값에서 Okapi BM25의 측정률이 가장 높게 도출되었습니다.

논문링크 : [논문]Okapi BM25 단어 가중치법 적용을 통한 문서 범주화의 성능 향상 (kisti.re.kr) 

엘라스틱서치가 사용하는 Okapi BM25 알고리즘은 일반적인 Okapi BM25와 크게 다르지 않습니다. TF 부분에서 분자의 k1이 없다는 것 정도의 차이만 존재하는데, 엘라스틱서치는 여기에 부스팅 가중치를 더해 최종 유사도 점수를 계산하고 있습니다. 단, 엘라스틱서치의 TF-IDF의 공식과 Okapi BM25의 공식간에는 상당한 차이가 있습니다.

Okapi BM25 알고리즘은 기본적으로 TF와 IDF의 곱으로 이루어지는 것이 2.4버전의 TF-IDF와 비슷합니다만, 공식에 많은 변화가 있습니다. 지금부터 키바나가 기본으로 제공하는 'kibana_sample_data_flights' 샘플 인덱스에서, explain 옵션과 함께 search API를 사용하여 유사도 계산결과를 출력해보겠습니다. 그리고 각 공식의 변수들과 계산과정을 상세히 따라가보겠습니다.

공식 문서 및 공식 블로그의 정리에 따르면, IDF란 모든 도큐먼트 내에서 term이 얼마나 많이 발생하였는지를 뜻하며 일반적으로 사용되는 용어들을 '패널화' 하여 높은 가중치가 할당되지 않게 방지하여 줍니다. 'The'나 'a' 같은 단어가 여기에 해당됩니다.

BM25의 IDF 계산식은 Binary Independence Model(이진 독립 모델)로부터 파생되었는데, 기존 2.4버전 TF-IDF의 IDF 계산식과는 달라진 부분이 있습니다. N은 샤드 내에서 필드에 값이 존재하는 전체 도큐먼트의 수 입니다. 여기서 샤드란 search API가 동작하는 인덱스의 샤드를 의미합니다. n은 쿼리의 term을 포함하는 도큐먼트의 개수입니다.

위의 사진은 샘플 인덱스에서의 유사도 계산결과 중 IDF 계산 과정입니다. 이렇게 엘라스틱서치는 explain 필드를 사용하면 계산과정과 각 변수의 값, 의미들을 상세히 출력해줍니다. 여기서 주의할점은 일반적으로 log에 밑을 쓰지 않으면 밑이 10인 로그를 가정하는데, 엘라스틱서치의 IDF계산에서는 자연로그 ln으로 계산해야 한다는 것입니다.

2. TF

Term Frequency의 경우 IDF보다 더 많은 차이가 있습니다. 기존 TF-IDF의 계산식은 term 발생빈도에 square root를 한 결과지만, Okapi BM25의 경우 term의 발생빈도 뿐만 아니라 문서 길이에 대한 가중치와 단어 자체에 대한 가중치를 함께 포함하여 계산합니다. 조금 헷갈릴 수 있는 부분인데, 공식을 보며 하나하나 뜯어보겠습니다.

freq는 도큐먼트 내에서 얼마나 쿼리의 term이 많은지를 의미합니다. 간단하게 도큐먼트에 term이 많으면 점수가 높다는 것입니다. 

공식문서에 따르면 k1은 '비선형적인 term의 빈도에 대한 정규화'라고 합니다. 너무 어려운 표현이라 아주 쉽게 말하자면, 'term의 빈도 수가 점수에 미치는 영향'을 의미합니다. 예를 들어 '사과'라는 term이 반복되는 도큐먼트가 있습니다. '사과' term 하나당 점수가 1점씩 오른다고 했을 때, 아무런 제한이 없다면 term이 하나 더 추가 될 때 마다 유사도 점수가 1점씩 계속 오를것입니다. 빈도 수가 증가할 수 록, 다음번에 출현하는 term의 점수는 낮아야합니다. 엘라스틱서치는 이를 Term frequency saturation characteristics(단어 빈도 포화 특성)이라고 표현합니다.

기존의 TF/IDF는 이 '단어 포화'를 해결해주지 못했습니다. 단어가 많이 등장할수록, 점수는 계속 증가했습니다. 그러나 BM25는 k1 변수를 사용하여 단어가 많이 등장하여도 일정한 값으로 수렴하게끔 조정하였습니다.

기본적으로 k1의 값이 높으면 추가적인 term에 대한 점수가 높은 것이며, k1이 낮으면 추가적인 term은 점점 점수가 낮아질 것입니다. 기본 k1값은 1.2이며, 사용자가 직접 지정하여 변경할 수 있습니다.

b는 '문서 길이가 tf 값을 정규화하는 정도' 라고 하는데, 다시 표현하자면 '긴 문서에 얼마나 점수를 낮게 줄까요?' 입니다. 만약 b가 0이라고 가정해봅시다. 위 식에서 avgdl 및 dl은 모두 문서의 길이에 대한 변수인데, b가 0이라면 아무런 영향도 주지 못할 것입니다. 예를 들어 제품의 설명서라던가 논문 같은 경우에는 어차피 한 주제에 대해 구체적으로 설명하는 경우이기 때문에 길이 자체와 term의 영향관계가 적습니다. 이럴 경우에는 b가 낮아야 할 것입니다.

반대로, 주제가 다양한 뉴스라던가 사용자 리뷰 같은 경우에는 관련이 없는 주제의 점수를 떨어트리기 위해 b를 높게 설정할 수 있습니다. 문서의 길이 중요도를 높이는 것입니다. '평균 문서길이에 비해 긴 문서에는 점수를 별로 주지 않겠다!'라는 것입니다. 기본 b 값은 0.75이며, 이 역시 사용자가 직접 지정하여 변경할 수 있습니다.

dl은 도큐먼트의 길이이며, avgdl은 평균 도큐먼트의 길이입니다. 말 그대로 이 문서의 길이가 평균적으로 얼마나 긴지를 의미합니다. dl/avgdl 값이 낮을 수록, 즉 길이가 짧을 수록 점수는 높습니다.

결과적으로 Okapi BM25 알고리즘은 문서의 길이, 단어의 빈도수, 단어의 포화 정도, 전체 문서의 수 등을 종합적으로 고려하여, TF-IDF 보다 유사성의 구분이 용이하게 설계한 스코어링 알고리즘이라 할 수 있습니다.

Elasticsearch는 검색 엔진입니다. 우리가 검색 엔진을 공부하고 싶다면 어떤 기준으로 검색 점수를 도출하는지에 대해서 대략적으로라도 알고 있어야 할 것입니다. 간단하게 결론만 알아도 상관 없지만, 혹시나 탐구심이 있을 분들을 위해 논문과 공식문서, 블로그 링크를 남기며 글을 마칩니다.

논문링크 : [논문]Okapi BM25 단어 가중치법 적용을 통한 문서 범주화의 성능 향상 (kisti.re.kr)
논문링크 : (PDF) Term-Recency for TF-IDF, BM25 and USE Term Weighting | Divyanshu Marwah - Academia.edu
공식문서 : Similarity module | Elasticsearch Guide [5.0] | Elastic
공식문서 : Lucene’s Practical Scoring Function | Elasticsearch: The Definitive Guide [2.x] | Elastic
공식문서 : Theory Behind Relevance Scoring | Elasticsearch: The Definitive Guide [2.x] | Elastic
공식문서 : Query-Time Boosting | Elasticsearch: The Definitive Guide [2.x] | Elastic
공식블로그 : Practical BM25 - Part 1: How Shards Affect Relevance Scoring in Elasticsearch | Elastic Blog
공식블로그 : Practical BM25 - Part 2: The BM25 Algorithm and its Variables | Elastic Blog
공식블로그 : Practical BM25 - Part 3: Considerations for Picking b and k1 in Elasticsearch | Elastic Blog