[ELASTIC] BM25 - Elastic searching algorithm

Elasticsearch의 Relevance

relevance는 elasticsearch의 query의 score값입니다. 즉 쿼리에 맞는 가장 비슷한 값에 점수를 메겨 랭크를 도출할 수 있습니다. 가장 많이 사용되는 오픈소스 검색엔진인 lucene을 사용하는 elasticsearch는 최근에 lucene의 바뀐 알고리즘으로 인해 기존 TFIDF 살짝 변형된 알고리즘에서 BM25 알고리즘을 사용하고 있습니다.

우선 BM25 알고리즘이 무엇인지 아래 그림으로 먼저 살펴봅시다.

Kibana에서 쿼리 수행

식으로만 봐서는 무슨 말인지 잘 모르겠습니다. kibana에서 데이터를 구성하고 query를 주어 score값을 확인하고 “explain”: true를 통하여 어떻게 계산되는지 확인해 봅시다.

POST library/books/_bulk
{"index":{"_id":1}}
{"title":"The quick brow fox",
{"index":{"_id":2}}
{"title":"The quick brow fox jumps over the lazy dog",
{"index":{"_id":3}}
{"title":"The quick brow fox jumps over the quick dog",
{"index":{"_id":4}}
{"title":"brow fox brown dog",
{"index":{"_id":5}}
{"title":"Lazy dog"}

POST를 통해 비슷한 단어로 구성된 5개의 document(row)를 library index(DB) books type(table)에 저장합니다. ‘bulk’는 한번에 많은 document를 Insert할 때 필요한 쿼리 API입니다. (price와 colors Field도 존재했지만 코드가 길어져 생략했습니다.)

 GET library/_search
{
  "query": {
    "match": {
      "title": "fox jumps"
    }
  },
  "explain": true
}

GET 명령어를 통해 title field : “fox jumps” 안에있는 “fox”, “jumps”라는 단어가 들어가 있는 문자열을 통해서 모든 Docs(1~5 sentences)과의 score값을 계산, 비교하여 순위를 정합니다.

Score 계산

Score 결과값은 크게 아래와 같은 방식으로 구합니다.

1. “fox”와 “jumps”의 weight을 따로 계산
2. 각각의 weight는 TF, IDF, boost의 곱
3. boost = k1 + 1 = 1.2 고정값입니다.
4. IDF = log(1 + (N-m+0.5)/(n+0.5))
5. TF = freq / (freq + k1 * (1 - b + b * (dl / avgdl)))
6. weight를 더해줌

위에서 부터 천천히 결과를 해석하면서 계산해봅시다.(필요없는 부분은 임의로 삭제했습니다.)

"max_score" : 0.9317306
"_score" : 0.9317306
"description" : "sum of:",
"title": "The quick brow fox jumps over the lazy dog"

max score가 0.9317306 값으로 나온 문장은 “The quick brow fox jumps over the lazy dog”입니다. description에 “sum of”라고 나오는데 어떤 것을 더하는 건가 봅니다. 어떤 것을 더하는지 indent를 통해 살펴본 결과 fox와 jumps의 weight를 따로 구해 더했습니다.

"value" : 0.23044494,
"description" : "score(freq=1.0), product of:",
"description" : "weight(title:fox in 1) [PerFieldSimilarity], result of:",

"value" : 0.7012857,
"description" : "score(freq=1.0), product of:",
"description" : "weight(title:jumps in 1) [PerFieldSimilarity], result of:",

두 값을 더하니 정확히 0.9317306이 나옵니다. 여기서 알 수 있는건 jumps의 score이 높고 fox의 socre가 낮다는 것입니다. 이는 jumps의 과점에서 jumps가 target 문장에서 많이 존재하여 tf에서 점수를 많이 얻었거나 아니면 모든 docs(sentences 1~5) jumps라는 단어의 수가 별로 없어 idf에서 높은 점수를 얻었을 수 있습니다. 반면 fox라는 단어의 score가 낮게 나온것은 target 문장에서 fox 단어의 빈도수가 적거나 아니면 모든 docs(sentences 1~5)에서 전체적으로 fox라는 단어가 많이 존재하여 idf에서 낮은 점수를 받았음을 의미할 수 있습니다. 또한 description에서 두 단어 모두 “freq=1.0”이고 어떤 값들의 “product of”임을 알 수 있습니다.

fox의 score를 계산해 보기 위해 어떤 값들이 product of 안에 존재하는지 확인 해봅시다.

위에서 설명한 것과 같이 각 weight는 boost, TF, IDF의 곱입니다.

• boost

"value" : 2.2,
"description" : "boost",

• idf

"value" : 0.2876821,
"description" : "idf, computed as log(1 + (N - n + 0.5) / (n + 0.5)) from:",
"details" : [
  {
    "value" : 4,
    "description" : "n, number of documents containing term",
  },
  {
    "value" : 5,
    "description" : "N, total number of documents with field",
  }

• tf

"value" : 0.36410922,
"description" : "tf, computed as freq / (freq + k1 * (1 - b + b * dl / avgdl)) from:",
"details" : [
  {
    "value" : 1.0,
    "description" : "freq, occurrences of term within document",
  },
  {
    "value" : 1.2,
    "description" : "k1, term saturation parameter",
  },
  {
    "value" : 0.75,
    "description" : "b, length normalization parameter",
  },
  {
    "value" : 9.0,
    "description" : "dl, length of field",
  },
  {
    "value" : 5.6,
    "description" : "avgdl, average length of field",
  }

위 계산 결과에서 boost(k1+1), TF, IDF를 확인할 수 있었고 모두 곱하면 처음 살펴 본 fox의 score = 0.23044494를 구할 수 있습니다. 마찬가지로 jumps의 score값도 이와 동일하게 구할 수 있습니다. 여기서 default로 정해진 파라미터는 아래와 같고 description을 참조하면 k1은 tf에 주는 가중치 b는 field(docs)에 주는 normalization으로 생각하면 될 것 같습니다. 쿼리로 요청할 때

• k1 = 1.2
• b = 0.75

쿼리로 요청시 Boost값에 임의값을 지정해줄 수 있어 찾고자 하는 단어에 가중치를 늘려주거나 줄여줄 수 있다.