Elasticsearch: Reciprocal rank fusion

이 글은 Elasticsearch의 Reciprocal Rank Fusion (RRF) 기능에 대해 다룸.

 

RRF 현재 기술 상태:

• 프리뷰 단계에 있음. 그래서 향후 릴리스에서 변경되거나 제거될 수 있으며, GA(General Availability) 전에 문법이 변경될 가능성이 있다.

 

RRF 정의:

• 서로 다른 관련성 지표를 가지고 검색된 결과 집합들을 단일 결과 집합으로 결합하는 방법임.

 

RRF 점수 계산 공식:

• results(q): 쿼리에 대한 결과 집합
• d: 평가 문서
• rank(result(q), d): 결과 집합 내 문서 d의 순위
• k: 하이퍼파라미터로 상수 값이다. 일반적으로 60 정도로 넣음.

score = 0.0
for q in queries:
    if d in result(q):
        score += 1.0 / (k + rank(result(q), d))
return score

 

RRF 작동 원리:

• 각 쿼리 결과에서 문서의 순위를 기반으로 점수를 계산한다.
• 순위가 높을수록 더 높은 점수를 받음.
• 각 쿼리 결과에서 문서의 순위를 기반으로 점수를 계산해서 단일 집합을 얻는다.

 

 

Reciprocal rank fusion API

Reciprocal Rank Fusion (RRF) API 사용 방법에 대해 다룸.

 

RRF 사용 목적:

• 여러 검색 방법(retrievers)의 결과를 결합하고 순위를 매기는 데 사용된다.
• 최소 두 개의 child retrievers가 필요하다.

 

RRF 쿼리 예시:

• 쿼리에서 retriever 가 파라미터로 필요함.
• rank_constant: 이 값이 클수록 낮은순위 문서의 영향력이 증가한다고 알면됨.
• window_size: 각 쿼리 별 개별 결과 집합의 크기를 나타낸다. 기본값은 size 파라미터와 같음.
• 이 쿼리의 실행 과정을 보면 kNN 검색으로 상위 50개 결과가 나오고, standard query 실행 결과로도 50개의 결과가 나온다. 그리고 두 결과를 RRF 공식에 의해 정렬시키고 마지막으로 상위 10개의 결과를 반환함. (size 파라미터는 기본값이 10이므로)

GET example-index/_search
{
    "retriever": {
        "rrf": { 
            "retrievers": [
                {
                    "standard": { 
                        "query": {
                            "term": {
                                "text": "shoes"
                            }
                        }
                    }
                },
                {
                    "knn": { 
                        "field": "vector",
                        "query_vector": [1.25, 2, 3.5],
                        "k": 50,
                        "num_candidates": 100
                    }
                }
            ],
            "window_size": 50,
            "rank_constant": 20
        }
    }
}

 

 

Reciprocal rank fusion supported features

RRF Retriever 가 지원하는 기능과 지원하지 않는 기능에 대해 다룸.

 

현재 RRF retriever가 지원하는 기능:

• aggregations (집계)
  • 검색 결과에 대한 통계 및 분석 정보를 제공하는 기능
• from
  • 결과 집합의 시작 위치를 지정하는 파라미터

 

RRF retriever가 현재 지원하지 않는 기능:

• scroll
  • 대량의 결과를 효율적으로 검색하기 위한 기능
• point in time
  • 특정 시점의 인덱스 상태를 기준으로 검색하는 기능
• sort
  • 검색 결과를 특정 필드를 기준으로 정렬하는 기능
• rescore
  • 초기 검색 결과의 일부를 다시 점수 매기는 기능
• suggesters
  • 검색어 제안 기능
• highlighting
  • 검색 결과에서 매치된 부분을 강조 표시하는 기능
• collapse
  • 결과를 특정 필드를 기준으로 그룹화하는 기능
• explain
  • 각 검색 결과의 점수 계산 과정을 설명하는 기능
• profiling
  • 검색 쿼리의 실행 과정을 상세히 분석하는 기능

 

Reciprocal rank fusion using multiple standard retrievers

RRF 를 사용해서 여러 standard retriever 의 결과 집합을 결합하는 방법에 대해 다룸.

 

RRF의 주요 사용 사례:

• 전통적인 BM25 쿼리와 ELSER (Elastic Learned Sparse EncodeR) 쿼리의 결과를 결합하여 관련성을 향상시키는 것.

 

검색 예시:

• 첫 번째 standard retriever:
  • BM25 알고리즘을 사용함.
• 두 번째 standrad retriever:
  • ELSER 점수 알고리즘을 사용함.
• RRF 는 두 결과를 합쳐서 최종 결과를 만듬.

GET example-index/_search
{
    "retriever": {
        "rrf": { 
            "retrievers": [
                {
                    "standard": { 
                        "query": {
                            "term": {
                                "text": "blue shoes sale"
                            }
                        }
                    }
                },
                {
                    "standard": { 
                        "query": {
                            "text_expansion":{
                                "ml.tokens":{
                                    "model_id":"my_elser_model",
                                    "model_text":"What blue shoes are on sale?"
                                }
                            }
                        }
                    }
                }
            ],
            "window_size": 50,
            "rank_constant": 20
        }
    }
}

 

 

ELSER (Elastic Learned Sparse EncodeR):

• Elasticsearch에서 사용되는 기계 학습 모델로, 텍스트를 sparse 벡터로 인코딩하는 데 사용됨.
• 자연어 쿼리와 문서 간의 의미적 관계를 더 잘 포착하기 위해 설계되었음.
• 전통적인 키워드 기반 검색을 넘어서는 의미 기반 검색을 가능하게 해줌.
• Sparse Vector 를 이용한 검색 방법임. qdarnt 와 splade 와 유사한 것.
• 문서에서 중요한 단어를 추출해주고 원래 문서나 쿼리에 없던 단어도 어휘 확장을 통해서 추가해주고, 추출된 단어를 문맥에 고려해서 중요도 점수도 넣어줌.

 

 

Reciprocal rank fusion full example

RRF 를 사용한 전체 예제를 다룸.

 

1) 인덱스 생성 및 문서 색인:

• 텍스트, 벡터, 정수 필드를 포함한 인덱스를 생성하고, 5개의 문서를 색인해보자.

PUT example-index
{
    "mappings": {
        "properties": {
            "text" : {
                "type" : "text"
            },
            "vector": {
                "type": "dense_vector",
                "dims": 1,
                "index": true,
                "similarity": "l2_norm"
            },
            "integer" : {
                "type" : "integer"
            }
        }
    }
}

PUT example-index/_doc/1
{
    "text" : "rrf",
    "vector" : [5],
    "integer": 1
}

PUT example-index/_doc/2
{
    "text" : "rrf rrf",
    "vector" : [4],
    "integer": 2
}

PUT example-index/_doc/3
{
    "text" : "rrf rrf rrf",
    "vector" : [3],
    "integer": 1
}

PUT example-index/_doc/4
{
    "text" : "rrf rrf rrf rrf",
    "integer": 2
}

PUT example-index/_doc/5
{
    "vector" : [0],
    "integer": 1
}

POST example-index/_refresh

 

 

RRF 검색 실행:

• standrad 쿼리와 knn 쿼리를 Retriver 로 결합해서 RRF 수행

GET example-index/_search
{
    "retriever": {
        "rrf": {
            "retrievers": [
                {
                    "standard": {
                        "query": {
                            "term": {
                                "text": "rrf"
                            }
                        }
                    }
                },
                {
                    "knn": {
                        "field": "vector",
                        "query_vector": [3],
                        "k": 5,
                        "num_candidates": 5
                    }
                }
            ],
            "window_size": 5,
            "rank_constant": 1
        }
    },
    "size": 3,
    "aggs": {
        "int_count": {
            "terms": {
                "field": "integer"
            }
        }
    }
}

 

 

검색 결과:

• 상위 3개의 문서가 반환되고, _score 대신에 _rank 로 순위가 표시됨.

{
    "took": ...,
    "timed_out" : false,
    "_shards" : {
        "total" : 1,
        "successful" : 1,
        "skipped" : 0,
        "failed" : 0
    },
    "hits" : {
        "total" : {
            "value" : 5,
            "relation" : "eq"
        },
        "max_score" : null,
        "hits" : [
            {
                "_index" : "example-index",
                "_id" : "3",
                "_score" : null,
                "_rank" : 1,
                "_source" : {
                    "integer" : 1,
                    "vector" : [
                        3
                    ],
                    "text" : "rrf rrf rrf"
                }
            },
            {
                "_index" : "example-index",
                "_id" : "2",
                "_score" : null,
                "_rank" : 2,
                "_source" : {
                    "integer" : 2,
                    "vector" : [
                        4
                    ],
                    "text" : "rrf rrf"
                }
            },
            {
                "_index" : "example-index",
                "_id" : "4",
                "_score" : null,
                "_rank" : 3,
                "_source" : {
                    "integer" : 2,
                    "text" : "rrf rrf rrf rrf"
                }
            }
        ]
    },
    "aggregations" : {
        "int_count" : {
            "doc_count_error_upper_bound" : 0,
            "sum_other_doc_count" : 0,
            "buckets" : [
                {
                    "key" : 1,
                    "doc_count" : 3
                },
                {
                    "key" : 2,
                    "doc_count" : 2
                }
            ]
        }
    }
}

 

 

Pagination in RRF

RRF 에서 페이지네이션을 어떻게 사용하는지에 대한 설명.

 

페이지네이션 메커니즘:

• 'from' 파라미터를 사용하여 결과를 페이지네이션한다.
• 일관성을 위해 고정된 'window_size'를 사용해야함.

 

'window_size'의 역할:

• 전체 사용 가능한 결과 집합의 크기를 정의함.
• 페이지네이션 시 일관성을 보장한다.

 

페이지네이션 제한:

• from + size ≤ window_size: 결과 반환 가능
• from + size > window_size: 결과 없음 (범위 초과)

 

페이지네이션 제한에 대해 예시로 설명:

• 다음과 같이 두 쿼리의 조합으로 각각 가져왔다라고 가정해보자.
• 여기서는 window_size 가 5일거임.

     |  queryA   |  queryB    |
_id: |  1        |  5         |
_id: |  2        |  4         |
_id: |  3        |  3         |
_id: |  4        |  1         |
_id: |           |  2         |

 

 

RRF 에 의해서 다음과 같이 정렬될거임:

• 최종 문서 순위: [1, 4, 2, 3, 5]

# doc   | queryA     | queryB       | score
_id: 1 =  1.0/(1+1)  + 1.0/(1+4)      = 0.7
_id: 2 =  1.0/(1+2)  + 1.0/(1+5)      = 0.5
_id: 3 =  1.0/(1+3)  + 1.0/(1+3)      = 0.5
_id: 4 =  1.0/(1+4)  + 1.0/(1+2)      = 0.533
_id: 5 =    0        + 1.0/(1+1)      = 0.5

 

 

여기서 from 과 size 변수에 의한 최종 결과 출력은 당므과 같이 될거임:

• from=0, size=2 would return documents [1, 4] with ranks [1, 2]
• from=2, size=2 would return documents [2, 3] with ranks [3, 4]
• from=4, size=2 would return document [5] with rank [5]
• from=6, size=2 would return an empty result set as it there are no more results to iterate over

 

References:

• https://www.elastic.co/guide/en/elasticsearch/reference/current/rrf.html#rrf-api