> ## Content Index
> Fetch the complete content index at: https://www.popit.kr/llms.txt
> Use this file to discover other available public pages before exploring further.

# BM25 - Elasticsearch 5.0에서 검색하는 새로운 방법
- URL: https://www.popit.kr/bm25-new-search-in-elasticsearch-5/
- Published: 2016-11-07T15:09:39.000Z
- Updated: 2016-11-07T15:12:06.000Z
- Author: 송 준이
- Tags: #소프트웨어, elasticsearch, bm25, tf/idf, 검색엔진

지난 10월 26일, [Elasticsearch 5.0.0 GA 버전이 공개](https://www.elastic.co/blog/elasticsearch-5-0-0-released?ref=popit.kr)되었다. 주요 내용으로는 block KD 트리 구조를 적용한 검색 및 색인 성능 향상, 인제스트 노드(Ingest Node) 추가, Painless 스크립트 언어 추가 등이 있다. 자세한 내용은 "[내가 본 Elasticsearch 5.0.0 신규 기능 몇 가지들](https://www.popit.kr/look-at-new-features-elasticsearch-5/)"에서도 확인할 수 있다. 개인적으로 가장 관심이 가는 변경사항은 검색 scoring 기본 알고리즘을 TF/IDF에서 BM25로 변경한 부분이다. 이 글에서는 BM25를 사용하면검색 점수(score)가 TF/IDF와 어떻게 차이가 나는지 잠깐 살펴보려고 한다. 

## 검색 점수

검색이란 사용자가 입력한 검색 쿼리(query)에 대해 관련있는 문서를 매칭한 후, 관련성에 따라 정렬하는 과정이다. 관련성(relevance)은 주어진 쿼리와 매칭되는 문서를 관련된 정도에 따라 수치화 한 값으로, 검색 점수(score)라고 부른다. 또한 쿼리는 "[최순실](https://namu.wiki/w/%EC%B5%9C%EC%88%9C%EC%8B%A4?ref=popit.kr)", "[통일교](https://namu.wiki/w/%EC%84%B8%EA%B3%84%ED%8F%89%ED%99%94%ED%86%B5%EC%9D%BC%EA%B0%80%EC%A0%95%EC%97%B0%ED%95%A9?ref=popit.kr)"와 같이 한단어 일수도 있지만, "[최순실 게이트](https://namu.wiki/w/%EC%B5%9C%EC%88%9C%EC%8B%A4%20%EA%B2%8C%EC%9D%B4%ED%8A%B8?ref=popit.kr)"과 같이 여러 단어일수도 있다. 이 경우 "최순실", "게이트"에 대한 각 단어의 검색 점수를 합해야 하며, 이러한 각 단어를 텀(term)이라고 부른다.

![bm25_document_score](https://www.popit.kr/content/images/wp/2016/11/bm25_document_score.png)

그림. 쿼리에 대한 문서의 검색 점수 계산

우리가 익히 알고 있는 TF/IDF 알고리즘은 이러한 검색 점수를 계산하기 위한 가장 일반적인 방법이다. 

## TF/IDF

루씬의 TF/IDF 알고리즘은 아래와 같다.

![bm25_lucene_tf_idf_algorithm](https://www.popit.kr/content/images/wp/2016/11/bm25_lucene_tf_idf_algorithm-1024x87.png)

그림. 루씬 TF/IDF 수식(출처: [Real-time Analytics & Anomaly detection using Hadoop, Elasticsearch and Storm](http://www.slideshare.net/Hadoop%5FSummit/t-435p212leauv2?ref=popit.kr))

수식은 복잡하지만 그 의미는 직관적이다.

**TF(Term Frequency): 단어 빈도** 텀(term)이 문서에 등장하는 횟수로, 많이 등장할수록 문서의 검색 점수는 당연히 높아진다.

![bm25_tfidf_tf](https://www.popit.kr/content/images/wp/2016/11/bm25_tfidf_tf.png)

그림. TF가 높아질수록 점수가 높아진다(출처: [Elasticsearch, Improved Text Scoring with BM25](https://www.elastic.co/elasticon/conf/2016/sf/improved-text-scoring-with-bm25?ref=popit.kr))

**IDF(Inverse Document Frequency): 문서 역빈도** 문서 빈도(DF: Document Frequency)는 텀(term)이 등장하는 문서 개수로, 여러 문서에 등장할수록 문서의 검색 점수가 낮아진다. IDF는 1/DF다.

![bm25_tfidf_idf](https://www.popit.kr/content/images/wp/2016/11/bm25_tfidf_idf.png)

그림. DF가 높아질수록 점수가 낮아진다(출처: [Elasticsearch, Improved Text Scoring with BM25](https://www.elastic.co/elasticon/conf/2016/sf/improved-text-scoring-with-bm25?ref=popit.kr))

 "the", "a", "is"와 같이 문장에서 거의 항상 등장하는 텀(term)은 검색 결과에 영향을 미치지 않게 하기 위한 것으로, 이러한 단어들은 불용어(stop word)라고 부른다. **norm: 문서 길이 가중치** 텀(term)이 등장하는 문서의 길이에 대한 가중치로, 문서 길이가 길수록 검색 점수가 낮아진다.

![bm25_tfidf_norm](https://www.popit.kr/content/images/wp/2016/11/bm25_tfidf_norm.png)

그림. 문서 길이가 길수록 점수가 낮아진다(출처: [Elasticsearch, Improved Text Scoring with BM25](https://www.elastic.co/elasticon/conf/2016/sf/improved-text-scoring-with-bm25?ref=popit.kr))

"철수의 취미는 축구다"와 "영희의 취미는 축구와 야구다"와 같은 문장이 있을 때 "축구"로 검색한 경우, "철수의 취미는 축구다"라는 문서의 검색 점수가 더 높다. 직관적으로 보더라도, 여가생활에 철수는 "축구"만 하고, 영희는 "축구"와 "야구"를 섞어서 할 것이므로, 철수는 영희보다 "축구"를 더 좋아할 가능성이 높을 것이다. **나머지들** 수식의 첫번째 항목인 쿼리 norm과 마지막 항목인 텀 부스트(boost)는 이 글에서는 크게 신경쓰지 않아도 된다. 

## BM25

BM25를의 검색 점수를 계산하는 수식은 다음과 같다.

![bm25_formula](https://www.popit.kr/content/images/wp/2016/11/bm25_formula-1.png)

그림. BM25 수식(출처: [Elasticsearch, Improved Text Scoring with BM25](https://www.elastic.co/elasticon/conf/2016/sf/improved-text-scoring-with-bm25?ref=popit.kr))

수식을 수학적으로 이해하는 것도 중요하겠지만, TF/IDF와 비교하여 검색 결과에 어떤 영향을 주는지를 느낄 수만 있다면 충분하다.

![bm_25_tfidf_vs_bm25](https://www.popit.kr/content/images/wp/2016/11/bm_25_tfidf_vs_bm25-1024x464.png)

그림. 항목별 TF/IDF와 BM25 비교(출처: [Elasticsearch, Improved Text Scoring with BM25](https://www.elastic.co/elasticon/conf/2016/sf/improved-text-scoring-with-bm25?ref=popit.kr))

**TF(Term Frequency): 단어 빈도** TF의 영향이 줄어든다. TF에서는 단어 빈도가 높아질수록 검색 점수도 지속적으로 높아지는 반면, BM25에서는 특정 값으로 수렴한다. **IDF(Inverse Document Frequency): 문서 역빈도** IDF의 영향이 커진다. BM25에서는 DF가 높아지면 검색 점수가 0으로 급격히 수렴하므로, 불용어가 검색 점수에 영향을 덜 미친다. **norm: 문서 길이 가중치** 문서 길이의 영향이 줄어든다. BM25에서는 문서의 평균 길이(avgdl)를 계산에 사용하며, 문서의 길이가 검색 점수에 영향을 덜 미친다. 

## 추가로

**Coordination Factor** 루씬 TF/IDF 알고리즘에는 coordination 항목도 검색 점수에 영향을 미친다. coordination 요소란 쿼리에 포함된 텀(term)을 더 많이 가진 문서에 대해 더 많은 점수 가중치를 부여하는 요소다.

![bm_25_tfidf_coord_factor](https://www.popit.kr/content/images/wp/2016/11/bm_25_tfidf_coord_factor.png)

그림. "holiday, china"로 검색한 경우 두 문서의 검색 점수(출처: [Elasticsearch, Improved Text Scoring with BM25](https://www.elastic.co/elasticon/conf/2016/sf/improved-text-scoring-with-bm25?ref=popit.kr))

예를 들어 "holiday, china"로 검색한 경우, 첫 번째 문서는 "holiday"와 "china" 단어를 모두 가지며 최종 점수는 9점이다. 반면 두 번째 문서는 "china" 단어만 등장하며, 최종 점수는 15점이다. 단순히 TF로만 계산한다면, 두 번째 문서가 더 검색점수가 높지만, 실제로 관련성이 더 높은 문서는 첫 번째 문서다. coordination 항목은 이러한 불린(boolean) 쿼리에서 쿼리에 포함된 여러 텀(term)이 문서에 동시에 나타나는 경우 더 높은 가중치를 부여한다. 자세한 내용은 [The Definitive Guide \[2.x\] > Lucene's Practical Scoring Function](https://www.elastic.co/guide/en/elasticsearch/guide/current/practical-scoring-function.html?ref=popit.kr)에서 찾아볼 수 있다. BM25 알고리즘에서 coordination 항목이 없으며, 활성화할 필요가 없다. **BM25 알고리즘 사용하기** 5.0.0 이전 버전에서 기본 검색 알고리즘인 TF/IDF 대신 BM25를 사용하려면, 전역으로 설정하거나 각 필드별로 설정할 수 있다. 전역 설정은 elasticsearch.yml 파일의 index.similarity.default.type 항목을 BM25로 설정한다.

```
index.similarity.default.type: BM25
```

인덱스의 각 필드별로 설정할 수도 있다.

```
PUT /my_index
{
  "mappings": {
    "doc": {
      "properties": {
        "title": {
          "type":       "string",
          "similarity": "BM25" 
        },
        "body": {
          "type":       "string",
          "similarity": "default" 
        }
      }
  }
}
```

## 왜 BM25가 왜 더 나은가

BM25가 TF/IDF보다 더 나은 이유는 "Elasticsearch가 그렇게 하기 때문이다". [Elasticsearch, Improved Text Scoring with BM25](https://www.elastic.co/elasticon/conf/2016/sf/improved-text-scoring-with-bm25?ref=popit.kr)에서 이야기하는 그 이유를 여기에 번역해 둔다.

- 논문에서 그렇다고 한다.
- TREC 등의 챌린지에서 그렇다고 한다.
- 사용자들이 그렇다고 한다
- 루씬 개발자도 그렇다고 한다
- Konard Beiske도 [BM25 vs Lucene Default Similarity](https://www.elastic.co/blog/found-bm-vs-lucene-default-similarity?ref=popit.kr)에서 그렇다고 한다.

## 참고자료

- [Elasticsearch 5.0.0 released](https://www.elastic.co/blog/elasticsearch-5-0-0-released?ref=popit.kr)
- [Popit, 내가 본 Elasticsearch 5.0.0 신규 기능 몇 가지들](https://www.popit.kr/look-at-new-features-elasticsearch-5/)
- [Real-time Analytics & Anomaly detection using Hadoop, Elasticsearch and Storm](http://www.slideshare.net/Hadoop%5FSummit/t-435p212leauv2?ref=popit.kr)
- [Elasticsearch, Improved Text Scoring with BM25](https://www.elastic.co/elasticon/conf/2016/sf/improved-text-scoring-with-bm25?ref=popit.kr)
- [Elasticsearch, BM25 vs Lucene Default Similarity](https://www.elastic.co/blog/found-bm-vs-lucene-default-similarity?ref=popit.kr)
- [Elasticsearch: The Definitive Guide \[2.x\] > Theory Behind Relevance Scoring](https://www.elastic.co/guide/en/elasticsearch/guide/current/scoring-theory.html?ref=popit.kr)
- [Elasticsearch: The Definitive Guide \[2.x\] > Lucene's Practical Scoring Function](https://www.elastic.co/guide/en/elasticsearch/guide/current/practical-scoring-function.html?ref=popit.kr)
- [Elasticsearch Reference \[2.4\] > Similarity Module](https://www.elastic.co/guide/en/elasticsearch/reference/2.4/index-modules-similarity.html?ref=popit.kr)
- [Elasticsearch: The Definitive Guide \[2.x\] > Changing Similarities](https://www.elastic.co/guide/en/elasticsearch/guide/2.x/changing-similarities.html?ref=popit.kr)

######