검색엔진에서 가장 일반적으로 사용되는 스코어 알고리즘에는 TF-IDF와 BM25가 있습니다.
가장 널리 사용되는 오픈소스 검색엔진인 lucene은 기존에 TF-IDF를 조금 변형한 형태의 스코어 알고리즘을 사용하고 있었으나 최근 버전에서는 default를 BM25알고리즘으로 변경하였습니다. 따라서 lucene을 core로 사용중인 solr와 elasticsearch도 최근 버전에서는 모두 BM25알고리즘을 기본 스코어로 사용하고 있습니다.
따라서!! BM25알고리즘이 어떤 공식인지 파헤쳐 보도록 하겠습니다.
위키피디아의 BM25 공식을 한 번 봐보도록 하겠습니다.
어..흠..예..그렇군요.흠흠….
하..뭔지 1도 모르겠다…
공식을 보고 잘 이해하시는 똑똑님들도 계시겠지만 저는 이전글에 적었던대로 수학은 예전에 고이접어 나빌레라한 쌈마이 개발자기 때문에 이 공식만 보고 스코어가 대체 어떻게 예측되는건지 알기가 힘들었습니다.
따라서 실제로 데이터를 색인을 해보고 검색을 해서 BM25는 어떤식으로 계산이 되고 있는지 한 번 살펴보도록 하겠습니다.
Elasticsearch Explain
elastic에 검색을 할때 explain:true를 명시하면 내부에서 스코어를 어떤식으로 처리하고 있는지 확인이 가능합니다.
이는 RDB의 explain명령어처럼 중요한 정보들을 담고있기 때문에 elasticsearch를 사용하고 있다면 꼭 아셔야 하는 정보입니다.
다음은 제가 실제로 검색을 해서 나온 explain정보입니다. fulltext는 매우 길기 때문에 bm25에 해당하는 알고리즘만 따로 빼겠습니다.
{
"value": 11.153388,
"description": "weight(cards.desc:운세 in 1851) [PerFieldSimilarity], result of:",
"details": [{
"value": 11.153388,
"description": "score(doc=1851,freq=3.0 = termFreq=3.0\n), product of:",
"details": [{
"value": 6.0515165,
"description": "idf, computed as log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5)) from:",
"details": [{
"value": 18.0,
"description": "docFreq",
"details": []
}, {
"value": 7857.0,
"description": "docCount",
"details": []
}]
}, {
"value": 1.8430732,
"description": "tfNorm, computed as (freq * (k1 + 1)) / (freq + k1 * (1 - b + b * fieldLength / avgFieldLength)) from:",
"details": [{
"value": 3.0,
"description": "termFreq=3.0",
"details": []
}, {
"value": 1.2,
"description": "parameter k1",
"details": []
}, {
"value": 0.75,
"description": "parameter b",
"details": []
}, {
"value": 364.4447,
"description": "avgFieldLength",
"details": []
}, {
"value": 113.77778,
"description": "fieldLength",
"details": []
}]
}]
}]
}
제가 “운세” 라는 키워드를 cards.desc필드에 검색을 했고 그 결과에 대한 bm25스코어 내용입니다.
bm25부분만 떼고 봐도 상당히 길긴 한데요, 그냥 천천히 살펴보면 그리 복잡하지 않습니다.
우선 숫자는 지워버리고 가장 안쪽의 description만 천천히 살펴보겠습니다.
"details": [{
"description": "idf, computed as log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5)) from:"
},
{
"description": "tfNorm, computed as (freq * (k1 + 1)) / (freq + k1 * (1 - b + b * fieldLength / avgFieldLength)) from:"
}]
details array안쪽의 큰 description을 보면 idf와 tfNorm이라고 명시되어 있네요.
이걸 보면 BM25의 알고리즘은 크게 2꼭지로 나눠지며 결국 이 BM25 공식도 idf와 tf로 이루어진다는것을 알 수 있습니다.
위키피디아의 수학공식 이미지를 다시 한 번 봐보겠습니다.
요렇게 반토막 내어놓으니 그나마 한 결 보기 편한거 같네요. 다시 천천히 조금씩 풀어나가 봅시다.
IDF
IDF (Inverse Document Frequency)는 문서에 자주 등장하는 단어일수록 낮은 가중치를 준다는 공식입니다.
똑같이 1번씩 검색이 되었다 하더라도 문서에 자주 등장한 단어가 매칭된 키워드일수록 낮은 가중치를 먹게 되는 것입니다.
왜? 문서에 많이 나오는게 좋은게 아닌가? 하고 생각할 수 있겠지만 문서에 공통적으로 많이 등장하는 단어는 실제 우리가 쓰는 단어로 살펴본다면 “은”, “는”, “다”처럼 형용사, 부사등이 되며 이는 실제로 큰 의미를 가지지 않는 단어일 확률이 높습니다.
공식을 다시 봐보겠습니다. description에 잘 풀어서 설명 되어 있습니다. 이것 때문에 explain을 본것입니다!
log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5)) 이 공식을 보면 docCount와 docFreq라는 변수를 대입 하는데 여기서 docCount가 전체 문서의 개수고 docFreq가 문서에 나타난 키워드 개수입니다. 다시 한번 idf를 제가 검색한 스코어와 같이 봐보겠습니다.
"details": [{
"value": 6.0515165,
"description": "idf, computed as log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5)) from:",
"details": [{
"value": 18.0,
"description": "docFreq",
"details": []
}, {
"value": 7857.0,
"description": "docCount",
"details": []
}]
전체문서(docCount)는 총 7857개이고 이중에서 제가 검색한 “운세” 라는 단어는 문서중에 총 18번 등장(docFreq)한것을 확인할 수 있습니다. 직접 계산해보죠.
>>> log(1 + (7857 - 18 + 0.5) / (18 + 0.5))
6.051516668034126
제가 검색한 단어의 idf는 6.05점을 먹었습니다. 7857개의 문서중 18번밖에 없는 그리 많이 등장하지 않은 단어여서 비교적 높은 점수를 먹은거 같네요.
TF
TF (Term Frequency)는 문서내에서 같은 단어가 여러번 등장한다면 그 단어에 높은 가중치를 주는 방법입니다.
description의 tf 공식을 봐보도록 하겠습니다.
(freq * (k1 + 1)) / (freq + k1 * (1 - b + b * fieldLength / avgFieldLength)) 수학기호로 봤을때 한없이 복잡해 보였는데 프로그래밍 방식으로 풀어쓰니 훨씬 쉬워 보이네요. 위키 피디아 이미지랑 한 번 비교 해보겠습니다.
어떤가요. 좀 이해가 한결 쉽지 않나요?
보면 bm25의 tf는 총 5개의 변수를 사용한다는 것을 알 수 있습니다.
freq, k1, b, fieldLength, avgFieldLength인데요,
explain하고 비교해보겠습니다.
"details": [{
"value": 3.0,
"description": "termFreq=3.0",
"details": []
}, {
"value": 1.2,
"description": "parameter k1",
"details": []
}, {
"value": 0.75,
"description": "parameter b",
"details": []
}, {
"value": 364.4447,
"description": "avgFieldLength",
"details": []
}, {
"value": 113.77778,
"description": "fieldLength",
"details": []
}]
freq = 문서에 매칭된 키워드 수
k1 = elasticsearch default는 1.2. 보통 1.2 혹은 2.0을 사용합니다.
b = elasticsearch default는 0.75
avgFieldLength = 평균 필드의 길이를 의미합니다.
fieldLength = 실제 문서가 검색된 문서의 길이를 얘기합니다.
k1, b는 elasticsearch에 설정된 상수입니다. 고정된 값이며 자세히 보면 k1은 freq하고만 연산하고 b는 field에 관련된 값하고만 연산되는걸 확인할 수 있습니다.
k1은 tf를 위한 가중치, b는 field를 위한 가중치구나! 하고 알고 계시면 될것 같습니다.
추가로 필드의 평균길이에 대한 연산을 하는데 평균 문서길이보다 더 작은 필드에서 매칭된 경우 더 높은 점수를 얻습니다. 위의 케이스에서는 평균보다 작으니 더 좋은 점수를 먹겠네요.
여기서는 제가 검색한 “운세”라는 단어가 문서에 총 3번 나타났고 현재 평균 필드 길이인 364보다 적은 113의 길이를 가진 필드에 매칭된것을 확인 가능합니다.
값이 전부 있으니 그럼 실제로 한 번 계산해보도록 하겠습니다. 제가 explain을 가지고 설명하는 이유입니다. 수학공식만 보고 있다고 그 수치의 성질을 판단하기는 많이 어려우니깐요.
>>> (3 * (1.2 +1)) / (3 + 1.2 * (1 - 0.75 + 0.75 * 113.77778 / 364.4447))
1.8430732493783817
idf는 6.0515165 tf는 1.8430732 가 나오고 이 두 숫자를 곱하면
>>> 6.0515165 * 1.8430732
11.1533878805078
실제로 우리가 봤던 최종 스코어인 11.153388가 나오는 것을 확인 가능하네요.
여기서 간략하게 알 수 있는건 우리가 검색했던 단어는 문서에 3번이나 등장한 나쁘지 않게 많이 등장한 단어임에도 불구하고 최종스코어 11.153388중에서 tf가 차지하는 스코어는 5.1018715로 idf보다 낮은 점수를 차지 했다는것을 알 수 있습니다.
즉 bm25는 tf보다 idf가 상대적으로 비중이 크다는 것을 알 수 있습니다. multiply연산이기 때문에 tf가 더 높은 점수 비중을 가지려면 2보다 높은 수여야 한다는것을 알 수있습니다.
사실 tf가 실데이터 세계에서는 살짝 애매하긴 합니다. 예를들어 홍진호 게시물엔 항상 같은 글이 두 번써지는데 그걸 더 중요하다고 하긴 좀(아 아닙니다..)
실제 상품 제목같은경우에 판매자가 많이 검색에 노출되고싶어 “[닥쑤]닥쑤핸드백/지갑/닥쑤남성지갑” 이런식으로 반복된 단어를 나열하는게 비일비재하여 tf에 큰 가중치를 주기가 애매합니다.
오히려 idf에 더 높은 스코어를 받는게 유리할 수 있죠.
물론 이것은 검색될 document의 성질에 따라 다른 부분이긴 합니다만 어느정도는 일반케이스이지 않나 싶습니다. 없으면 안되지만 높은 가중치를 주긴 왠지 아까운 tf입니다.
BM25에 대한 공식 설명은 어느정도 설명된거 같으니 다음 포스팅에는 수치를 직접 변경 해보면서 BM25가 가진 성질을 파악하는 시간을 가지도록 하겠습니다.
