[IR] RRF(Reciprocal Rank Fusion) 설명과 파이썬 코드

본 포스트에서는 정보 검색과 랭킹에서 사용되는 알고리즘인 RRF(Reciprocal Rank Fusion)에 대해 알아보겠습니다. 먼저 정의를 살펴본 후, 파이썬에서 구현하며 어떻게 결과가 바뀔 수 있는지 함께 확인하겠습니다.

 

 

RRF(Reciprocal Rank Fusion) 알고리즘이란?

 

RRF를 우리말로 옮기면 "상호간의 순위 융합" 정도가 되겠습니다. 말그대로, 다양한 검색 결과의 순위를 종합하여(있어보이는 표현으로는 "하이브리드하게"라는 표현이 있음) 검색 순위를 다시 매기는 하이브리드 알고리즘입니다. 다양한 검색 결과를 종합하는 이유는, 한 가지 방법론을 사용해 얻은 검색 결과만으로는 사용자들의 다양한 요구사항을 두루두루 만족시킬 수 없기 때문입니다. 여러 방법론으로 검색 결과를 얻게 되는 경우, 각 검색 스코어들은 스코어의 범위, 분포가 다를 수 있겠죠. RRF는 각 검색 결과의 "순위"를 이용하기 때문에 스코어의 범위와 무관하게 사용할 수 있습니다. 

 

저의 경우 BM25 유사도의 결과와 코사인 유사도 스코어의 결과를 종합하고 싶었는데요. BM25 스코어는 0 이상의 실수값을 범위로 갖지만, 코사인 유사도는 -1부터 1까지의 값을 갖고 있었습니다. 가중합을 사용하자니 둘의 범위를 상이하여 BM25를 스케일링해야하나? 생각하고 있었는데요. 이 RRF의 경우 스코어의 범위와 무관하게, 각 결과의 순위를 사용해 최종 순위를 얻을 수 있기 때문에 스케일링을 고려할 필요가 없습니다.

 

Elasticsearch 공식 문서에서 제공하는 알고리즘 코드를 보며 RRF를 이해해보겠습니다.

 

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

 

score는 이제 순위를 매길 대상인 문서 d의 유사도입니다. queries는 질의(query) 집합입니다. result(q)는 q를 질의했을 때 얻게된 결과 문서 목록이구요. 그렇다면 rank(result(q), d)는 q를 질의했을 때 얻은 문서들의 순위 결과에서, 특정 문서 d의 순위라고 이해할 수 있겠습니다. k는 랭킹 상수로, 각 검색 순위가 최종 순위에 미치는 영향력을 결정합니다. 공식 문서상 디폴트값은 60이라고 합니다.

질의 집합인 queries를 순회하면서, 문서 d가 q를 질의했을 때 얻은 결과 집합에 들어있다면 (해당 순위 + k)의 역수를 더하여 최종 스코어를 계산합니다. 최종 스코어값이 클수록 전체 검색 결과에서 전반적으로 순위가 높다는 의미이며, 이 스코어를 사용해서 최종 순위를 얻을 수 있습니다. 

 

 

파이썬에서 RRF 사용하기

 

python: v3.8.10
kiwipiepy: v0.16.2
rank_bm25: v0.2.2
transformers: v4.36.2
torch: v2.1.2

import pandas as pd
import jsonlines

from kiwipiepy import Kiwi
from rank_bm25 import BM25Okapi
from transformers import ElectraTokenizer, ElectraModel
import torch

 

RRF 를 적용해보기 위해 이전에 BM25 알고리즘 포스트에서 사용했던 데이터를 그대로 다시 사용해보겠습니다. 아래와 같은 순서로 진행됩니다.

 

1. 먼저 데이터를 불러온 후,

2. 형태소 단위로 텍스트를 분리하여 BM25 스코어를 얻고,

3. 임베딩 벡터를 이용해 코사인 유사도를 계산하고,

4. 2와 3에서 얻은 스코어와 유사도를 통해 얻게된 2가지 랭킹을 이용하여 RRF를 계산하겠습니다.

 

# define function to read jsonl file
def read_jsonl(path):
    data = list()
    with jsonlines.open(path) as f:
        for line in f:
            data.append(line)
    return data

train_data = read_jsonl('./data/nikluge-sa-2022-train.jsonl')

 

먼저 kiwipiepy 라이브러리를 사용해서 텍스트를 형태소 단위로 분리했습니다. 단순하게 띄어쓰기를 사용하는 것보다, 의미 단위로 쪼갠 후 BM25 알고리즘을 적용하는 것이 의미론적으로 유사한 텍스트들을 찾을 수 있기 때문입니다.

 

kiwi = Kiwi()
corpus = [data['sentence_form'] for data in train_data]
tokenized_corpus = [[t.form for t in kiwi.tokenize(doc)] for doc in corpus]
bm25 = BM25Okapi(tokenized_corpus)

query = "촉촉하고 부드럽다"
tokenized_query = [t.form for t in kiwi.tokenize(query)]
doc_scores = bm25.get_scores(tokenized_query)
print(doc_scores)
print(bm25.get_top_n(tokenized_query, corpus, n=1))

[0.         2.52088322 3.77316568 ... 0.         0.         0.        ]
['부드럽고 촉촉하게 발리는데다 순하기까지하다닝']

 

"촉촉하고 부드럽다"라고 하는 쿼리를 던졌을 때, 각 텍스트마다 BM25 스코어를 얻었습니다. "부드럽"과 "촉촉"을 함께 포함하고 있는 "부드럽고 촉촉하게 발리는데다 순하기까지 하다닝" 텍스트가 가장 높은 스코어를 얻은 것으로 나왔네요. 

 

model_name="monologg/koelectra-small-discriminator"
tokenizer = ElectraTokenizer.from_pretrained(model_name)
model = ElectraModel.from_pretrained(model_name)

def get_koelectra_embedding(text, model, tokenizer, max_length=512):
    inputs = tokenizer(text, return_tensors="pt", max_length=max_length, padding=True, truncation=True)
    
    with torch.no_grad():
        outputs = model(**inputs)
    embeddings = outputs.last_hidden_state.mean(dim=1).squeeze()

    return embeddings.numpy()

embedding_vector = get_koelectra_embedding(corpus, model, tokenizer)
query_vec = get_koelectra_embedding(query, model, tokenizer)

from numpy import dot
from numpy.linalg import norm

def cos_sim(A, B):
  return dot(A, B) / (norm(A) * norm(B))

cos_scores = [cos_sim(query_vec, embedding_vector[i, :]) for i in range(len(embedding_vector))]

 

다음으로, 텍스트마다 임베딩 벡터를 얻고 "촉촉하고 부드럽다"와의 코사인 유사도를 계산합니다. 임베딩 벡터를 얻기 위해 한국어 자연어처리를 위해 학습된 KoELECTRA-small 모델을 사용하였습니다.

 

result = pd.DataFrame({
    'text': corpus,
    'bm_score': doc_scores,
    'cos_score': cos_scores,
})
result['bm_rnk'] = result['bm_score'].rank(ascending=False)
result['cos_rnk'] = result['cos_score'].rank(ascending=False)
result.sort_values(['bm_rnk'], ascending=True)

 

텍스트마다 BM25 스코어와 코사인 유사도를 이용해 랭크를 계산했습니다. 한눈에 확인하기 위해 데이터프레임을 이용해 결과를 확인해보았는데요, 아까 위에서도 확인했듯이 "부드럽"과 "촉촉"을 포함하는 텍스트들이 BM25 스코어가 높게 나타나고 있었습니다. 다만 코사인 유사도의 순위는 크게 높지 않은데요. 이제 두 랭킹을 이용하여 RRF 를 계산하고 순위까지 얻어보겠습니다.

 

k = 60
result['rrf_score'] = result.apply(lambda x: sum(1.0 / (k + x[rnk]) for rnk in ['bm_rnk', 'cos_rnk']), axis=1)
result['rrf_rnk'] = result['rrf_score'].rank(ascending=False)
result.sort_values('rrf_rnk', ascending=True)

각 순위와 RRF 공식을 이용하여 스코어를 계산하고, 이를 통해 최종 순위를 얻었습니다. RRF 순위가 가장 높게 나타난 텍스트는

천연오일이\xa0 함유된 고보습 고영양크림으로 깊고\xa0 진한 영양성분이\xa0거칠고 건조해진 \xa0예민한\xa0\xa0피부에 피부 장벽을\xa0 강화하여 끈적임없이\xa0 촉촉하고 \xa0부드럽게 장시간 보습력을\xa0 유지해 준답니다 ♥

였습니다. 검색 쿼리였던 "촉촉하고 부드럽다"와 동일한 키워드를 갖고 있으면서, 코사인 유사도로 얻은 순위까지 종합하여 최종 1위가 되었네요. 검색 쿼리의 키워드를 갖고 있지 않으면서 코사인 유사도도 매우 낮은 텍스트들은 순위를 종합했을 때도 역시나 낮은 순위를 기록하고 있었습니다.

 

여기까지 RRF의 정의와 파이썬을 사용한 결과를 확인해보았습니다. RRF를 사용한다면 다양한 검색 결과를 종합하여 검색 품질을 높이고 사용자가 더 만족할 수 있는 결과를 제공할 수 있을 것 같습니다. 각 검색 결과의 스코어를 이용하는 것이 아니라 순위를 이용하기 때문에 스코어의 범위에 대한 고민을 할 필요가 없다는 점이 장점이었습니다. 검색 결과 개선이 필요하다면 RRF를 도입해보시길 추천합니다. 

 

 

참고

https://safjan.com/implementing-rank-fusion-in-python/

Implementing Reciprocal Rank Fusion (RRF) in Python

https://www.elastic.co/guide/en/elasticsearch/reference/current/rrf.html

Reciprocal rank fusion | Elasticsearch Guide [8.11] | Elastic

https://wikidocs.net/24603

05-01 코사인 유사도(Cosine Similarity)

https://github.com/bab2min/kiwipiepy

GitHub - bab2min/kiwipiepy: Python API for Kiwi