💻

C# で Reciprocal Rank Fusion (RRF) を実装する

2024/02/16に公開

はじめに

Azure AI Search のハイブリッド検索では、これまでのフルテキスト検索とベクター検索の結果を結合して、よりよい結果を返すことができます。フルテキスト検索とベクター検索の異なるアルゴリズムでスコアリングされた結果を結合するために Reciprocal Rank Fusion (RRF) という仕組みが使われています。数式についてはさっぱりなのですが、以下のドキュメントではわかりやすい説明があります。

より簡単に説明すると以下のような感じです。係数である k についてはいったん忘れます。

リストをスコアリングの順番に並べ替えます。
リストのそれぞれの項目について、1 を順位で割った値を求めます。結果は 1、1/2 (0.5)、1/3 (0.333...) のような値になります。
それぞれのリストに同じ項目があれば算出した値を合計します。
結合したリストを合計された値で並べ替えます。

Azure AI Search 以外でもハイブリッド検索を実装したいような場合は自前で RRF を実装する必要があります。

サンプルコード

コードとしては以下のようになります。

// タプルはキー、スコア、ドキュメントで構成されているとする
public static IEnumerable<Tuple<string, double, T>> Fuse<T>(IEnumerable<IEnumerable<Tuple<string, double, T>>> rankings, double k = 60)
{
    var result = new List<Tuple<string, double, T>>();

    foreach (var ranking in rankings)
    {
        // リストをスコアリングの順番に並べ替える
        var ordered = ranking.OrderByDescending(x => x.Item2).Select((value, order) => Tuple.Create(value, order + 1.0));
        foreach (var (value, order) in ordered)
        {
            // キーで結果のリストを検索する
            var index = result.FindIndex(x => x.Item1 == value.Item1);
            if (index < 0)
            {
                // 項目が存在しなければ 1 を順位で割った値を追加する
                result.Add(Tuple.Create(value.Item1, 1.0 / (order + k), value.Item3));
            }
            else
            {
                // 項目が存在すれば現在の値に 1 を順位で割った値を加算して更新する
                result[index] = Tuple.Create(result[index].Item1, result[index].Item2 + 1.0 / (order + k), result[index].Item3);
            }
        }
    }

    // 結果を並べ替えて返却する
    return result.OrderByDescending(x => x.Item2);
}

これを実行してみると以下のようになるはずです (k = 0 の場合)。

結合前のリスト

順位リスト 1 リスト 2 リスト 3

1 A B C

2 B A A

3 C C B
結合後のリスト

順位名前スコア計算式

1 A 2 1 + 0.5 + 0.5

2 B 1.833... 0.5 + 1 + 0.333...

3 C 1.666... 0.333... + 0.333... + 0.5

順位	リスト 1	リスト 2	リスト 3
1	A	B	C
2	B	A	A
3	C	C	B

順位	名前	スコア	計算式
1	A	`2`	`1 + 0.5 + 0.5`
2	B	`1.833...`	`0.5 + 1 + 0.333...`
3	C	`1.666...`	`0.333... + 0.333... + 0.5`

おわりに

GitHub Copilot に書いてもらったらそれっぽいものができたもののアルゴリズムが間違っており結局自分で書き直しました。

はじめに

サンプル コード

おわりに

Discussion

サンプルコード