技術

RRFとは

Reciprocal Rank Fusion

複数の検索手法によるランキング結果を、順位の逆数の和で統合するハイブリッド検索のスコア統合手法

ひとことで言うと

違う検索方法の結果を、順位だけをもとに1つのランキングへまとめる手法。

概要

RRF(Reciprocal Rank Fusion)とは、キーワード検索(BM25等)とベクトル検索(embedding類似度)のように、異なる検索手法が出力した複数のランキング結果を、各文書の「順位」のみをもとに1つのランキングへ統合する手法。各検索結果におけるドキュメントの順位の逆数を、平滑化のための定数で補正しながら合計し、そのスコアをもとに並べ替えて統合ランキングを得る。スコアそのものの値ではなく順位のみを使うため、検索手法ごとにスコアのスケールが異なっていても、正規化なしにそのまま組み合わせられる点が特徴。 BM25によるキーワード検索とベクトル検索を組み合わせるハイブリッド検索において、両者の結果を統合する代表的な手法として広く使われている。

背景

キーワード検索とベクトル検索は、それぞれ得意とするクエリ・文書の特性が異なり、検索精度を高めるためには両者を組み合わせるハイブリッド検索が有効とされる。しかし、各検索手法が出力するスコアは値のスケールや分布が異なるため単純に加算・平均できない。RRFは、スコアの値ではなく順位という共通の指標をもとに複数の検索結果を統合する手法として考案された。

歴史

2009年: Gordon V. Cormackらが、SIGIR 2009にて論文「Reciprocal Rank Fusion outperforms Condorcet and Individual Rank Learning Methods」を発表しRRFを提案。共著者はCharles L. A. ClarkeとStefan Büttcher。

アーキテクチャ

各ドキュメントについて、検索手法ごとの順位を求め、その逆数を平滑化定数で補正した値を、複数の検索手法にわたって合計することでRRFスコアを算出する。この定数は順位の影響を滑らかにするためのパラメータで、Cormackらの実験では60程度の値が良好な結果を示すとされている。

コード例

RRFによる複数ランキングの統合

def reciprocal_rank_fusion(rankings, k=60):
    """rankings: 各検索手法が返した文書IDの順位付きリストのリスト"""
    scores = {}
    for ranking in rankings:
        for rank, doc_id in enumerate(ranking, start=1):
            scores[doc_id] = scores.get(doc_id, 0.0) + 1.0 / (k + rank)

    return sorted(scores.items(), key=lambda x: x[1], reverse=True)

bm25_ranking = ["doc3", "doc1", "doc5"]
vector_ranking = ["doc1", "doc4", "doc3"]
fused = reciprocal_rank_fusion([bm25_ranking, vector_ranking])

利点

検索手法ごとのスコアのスケールが異なっていても、正規化なしに複数の結果を統合できる
実装がシンプルで、追加の学習データやチューニングをほとんど必要としない

欠点

順位のみを利用するため、スコアの差の大きさ(自信度)は考慮されない
定数の設定によって統合結果の傾向が変わり、データセットに応じた調整を要することがある

比較

ハイブリッド検索 — RRFは、ハイブリッド検索でキーワード検索とベクトル検索の結果を統合する代表的な手法の1つ
BM25 — RRFは、BM25によるキーワード検索の結果とベクトル検索の結果を統合する際によく使われる

よくある質問

RRFの平滑化定数はどのように決める?

Cormackらの原論文では60程度の値が良好な結果を示すとされ、多くの実装でデフォルト値として採用されている。値を大きくすると上位の順位差の影響が緩やかになり、小さくすると上位の順位差がスコアへより強く反映される。

参考文献

Research PaperReciprocal Rank Fusion outperforms Condorcet and Individual Rank Learning Methods