RAG(検索拡張生成)システムでは、ベクトル検索で候補文書を取得した後、リランキング(Reranking)によって順位を再計算することで、検索精度を大幅に向上させることができます。
本記事では、リランキングの各種手法を数学的な観点から解説し、Pythonでの実装方法を説明します。
本記事の内容
- リランキングの基本概念と必要性
- Bi-EncoderとCross-Encoderの違い
- Cross-Encoder、ColBERTによるリランキング
- Pythonでの実装と性能比較
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- RAG(検索拡張生成)の基礎
- ベクトルデータベースの仕組み
- Transformerの基本的な仕組み
リランキングとは
リランキングは、初期検索(ファーストステージ検索)で取得した候補文書に対して、より精密なスコアリングを行い、順位を再計算する処理です。
2段階検索アーキテクチャ
典型的なRAGシステムは以下の2段階で検索を行います。
-
ファーストステージ(Retrieval): 高速だが粗い検索 – Bi-Encoderによる埋め込み検索 – 数百万件から上位100件程度を取得
-
セカンドステージ(Reranking): 低速だが高精度 – Cross-Encoder等による詳細スコアリング – 上位100件を再順位付けして上位k件を選択
$$ \text{Documents} \xrightarrow[\text{(fast)}]{\text{Retrieval}} \text{Top-100} \xrightarrow[\text{(accurate)}]{\text{Reranking}} \text{Top-k} $$
Bi-EncoderとCross-Encoderの違い
Bi-Encoder
Bi-Encoderは、クエリと文書を独立にエンコードします。
$$ \bm{q} = E_q(\text{query}), \quad \bm{d} = E_d(\text{document}) $$
スコアは埋め込みベクトルの内積やコサイン類似度で計算:
$$ s(\text{query}, \text{document}) = \bm{q} \cdot \bm{d} $$
メリット: 文書の埋め込みを事前計算可能 → 高速 デメリット: クエリと文書の相互作用を捉えにくい → 精度に限界
Cross-Encoder
Cross-Encoderは、クエリと文書を連結してエンコードします。
$$ s(\text{query}, \text{document}) = f(\text{Encoder}([\text{CLS}] + \text{query} + [\text{SEP}] + \text{document})) $$
メリット: クエリと文書の詳細な相互作用を捉える → 高精度 デメリット: 各ペアで推論が必要 → 低速
計算量の比較
| 手法 | 検索時計算量 | 特徴 |
|---|---|---|
| Bi-Encoder | $O(n)$ 内積計算 | 事前計算可能 |
| Cross-Encoder | $O(n \cdot L^2)$ 推論 | ペアごとに推論 |
ここで $n$ は候補数、$L$ は入力長です。
Cross-Encoderによるリランキング
数学的定式化
Cross-Encoderは、クエリ $q$ と文書 $d$ のペアに対して関連性スコアを直接出力します。
入力テンソル:
$$ \bm{X} = \text{Tokenize}([\text{CLS}], q_1, \ldots, q_m, [\text{SEP}], d_1, \ldots, d_n, [\text{SEP}]) $$
Transformerでエンコード:
$$ \bm{H} = \text{Transformer}(\bm{X}) $$
CLSトークンの出力を分類ヘッドに通してスコアを得る:
$$ s = \sigma(\bm{W} \cdot \bm{h}_{[\text{CLS}]} + b) $$
Pythonでの実装
import torch
from transformers import AutoTokenizer, AutoModelForSequenceClassification
import numpy as np
class CrossEncoderReranker:
def __init__(self, model_name='cross-encoder/ms-marco-MiniLM-L-6-v2'):
"""Cross-Encoderリランカーの初期化"""
self.tokenizer = AutoTokenizer.from_pretrained(model_name)
self.model = AutoModelForSequenceClassification.from_pretrained(model_name)
self.model.eval()
def score(self, query, documents):
"""クエリと文書ペアのスコアを計算"""
pairs = [[query, doc] for doc in documents]
with torch.no_grad():
inputs = self.tokenizer(
pairs,
padding=True,
truncation=True,
max_length=512,
return_tensors='pt'
)
outputs = self.model(**inputs)
scores = outputs.logits.squeeze(-1).numpy()
return scores
def rerank(self, query, documents, k=5):
"""文書をリランキング"""
scores = self.score(query, documents)
ranked_indices = np.argsort(scores)[::-1][:k]
return [
{'document': documents[i], 'score': scores[i]}
for i in ranked_indices
]
# 使用例
documents = [
"RAGは検索拡張生成の略称です。",
"Pythonは人気のプログラミング言語です。",
"RAGシステムは外部知識を活用してLLMの回答精度を向上させます。",
"機械学習にはさまざまなアルゴリズムがあります。",
"検索拡張生成はハルシネーションを軽減する効果があります。",
]
reranker = CrossEncoderReranker()
query = "RAGとは何ですか?"
results = reranker.rerank(query, documents, k=3)
print(f"Query: {query}\n")
print("Reranked results:")
for i, r in enumerate(results, 1):
print(f" {i}. {r['document']} (score: {r['score']:.4f})")
ColBERT
アルゴリズムの概要
ColBERT(Contextualized Late Interaction over BERT)は、Bi-EncoderとCross-Encoderの中間に位置する手法です。
Late Interaction: クエリと文書を独立にエンコードしつつ、トークンレベルでの相互作用を計算します。
数学的定式化
クエリのトークン埋め込み:
$$ \bm{Q} = \text{Encoder}_q(\text{query}) \in \mathbb{R}^{m \times d} $$
文書のトークン埋め込み:
$$ \bm{D} = \text{Encoder}_d(\text{document}) \in \mathbb{R}^{n \times d} $$
MaxSim演算でスコアを計算:
$$ s(q, d) = \sum_{i=1}^{m} \max_{j=1}^{n} \bm{Q}_i \cdot \bm{D}_j^T $$
各クエリトークンに対して、最も類似度の高い文書トークンとのスコアを合計します。
計算量
- 文書の埋め込み: 事前計算可能(Bi-Encoderと同様)
- 検索時: $O(m \cdot n \cdot d)$ の内積計算
Bi-EncoderよりはコストがかかるがCross-Encoderよりは高速です。
Pythonでの簡易実装
import numpy as np
from transformers import AutoTokenizer, AutoModel
import torch
class SimpleColBERT:
def __init__(self, model_name='bert-base-uncased'):
"""ColBERTの簡易実装"""
self.tokenizer = AutoTokenizer.from_pretrained(model_name)
self.model = AutoModel.from_pretrained(model_name)
self.model.eval()
def encode(self, text):
"""テキストをトークンレベルの埋め込みに変換"""
with torch.no_grad():
inputs = self.tokenizer(
text,
padding=True,
truncation=True,
max_length=512,
return_tensors='pt'
)
outputs = self.model(**inputs)
# 全トークンの隠れ状態を取得
embeddings = outputs.last_hidden_state.squeeze(0).numpy()
return embeddings
def maxsim_score(self, query_emb, doc_emb):
"""MaxSimスコアを計算"""
# (m, d) x (n, d).T = (m, n)
similarity_matrix = np.dot(query_emb, doc_emb.T)
# 各クエリトークンの最大類似度を合計
max_similarities = np.max(similarity_matrix, axis=1)
return np.sum(max_similarities)
def rerank(self, query, documents, k=5):
"""文書をリランキング"""
query_emb = self.encode(query)
scores = []
for doc in documents:
doc_emb = self.encode(doc)
score = self.maxsim_score(query_emb, doc_emb)
scores.append(score)
scores = np.array(scores)
ranked_indices = np.argsort(scores)[::-1][:k]
return [
{'document': documents[i], 'score': scores[i]}
for i in ranked_indices
]
# 使用例
colbert = SimpleColBERT()
documents = [
"Machine learning is a subset of artificial intelligence.",
"Python is widely used for data science.",
"Deep learning uses neural networks with many layers.",
"Natural language processing handles text data.",
]
query = "What is machine learning?"
results = colbert.rerank(query, documents, k=3)
print(f"Query: {query}\n")
print("ColBERT reranked results:")
for i, r in enumerate(results, 1):
print(f" {i}. {r['document']} (score: {r['score']:.2f})")
LLMベースのリランキング
アルゴリズムの概要
LLMを使って、文書の関連性を直接判定する手法です。
Pointwise: 各文書を独立にスコアリング Pairwise: 2文書を比較して順序を決定 Listwise: 文書リスト全体を一度に順位付け
Pointwiseリランキング
def llm_pointwise_rerank(query, documents, llm_client):
"""LLMによるPointwiseリランキング(疑似コード)"""
scores = []
for doc in documents:
prompt = f"""以下の文書が質問に対してどの程度関連しているか、0から10のスコアで評価してください。
質問: {query}
文書: {doc}
スコア(0-10の整数のみ):"""
response = llm_client.generate(prompt)
score = int(response.strip())
scores.append(score)
# スコア順にソート
ranked = sorted(zip(documents, scores), key=lambda x: -x[1])
return ranked
Pairwiseリランキング
def llm_pairwise_compare(query, doc_a, doc_b, llm_client):
"""2文書を比較"""
prompt = f"""質問に対して、どちらの文書がより関連していますか?
質問: {query}
文書A: {doc_a}
文書B: {doc_b}
「A」または「B」で回答:"""
response = llm_client.generate(prompt)
return 'A' if 'A' in response else 'B'
def llm_pairwise_rerank(query, documents, llm_client):
"""LLMによるPairwiseリランキング(バブルソート)"""
docs = documents.copy()
for i in range(len(docs)):
for j in range(len(docs) - i - 1):
winner = llm_pairwise_compare(query, docs[j], docs[j+1], llm_client)
if winner == 'B':
docs[j], docs[j+1] = docs[j+1], docs[j]
return docs
評価指標
リランキングの性能を評価する指標を紹介します。
NDCG(Normalized Discounted Cumulative Gain)
順位を考慮した評価指標です。
$$ \text{DCG}_k = \sum_{i=1}^{k} \frac{2^{\text{rel}_i} – 1}{\log_2(i + 1)} $$
$$ \text{NDCG}_k = \frac{\text{DCG}_k}{\text{IDCG}_k} $$
ここで $\text{rel}_i$ は位置 $i$ の文書の関連度、$\text{IDCG}_k$ は理想的な順序でのDCGです。
MRR(Mean Reciprocal Rank)
最初の正解文書の順位の逆数の平均:
$$ \text{MRR} = \frac{1}{|Q|} \sum_{q \in Q} \frac{1}{\text{rank}_q} $$
Pythonでの評価実装
import numpy as np
def dcg_at_k(relevances, k):
"""DCG@kを計算"""
relevances = np.array(relevances)[:k]
gains = 2 ** relevances - 1
discounts = np.log2(np.arange(len(relevances)) + 2)
return np.sum(gains / discounts)
def ndcg_at_k(relevances, k):
"""NDCG@kを計算"""
dcg = dcg_at_k(relevances, k)
ideal_relevances = sorted(relevances, reverse=True)
idcg = dcg_at_k(ideal_relevances, k)
return dcg / idcg if idcg > 0 else 0
def mrr(ranks):
"""MRRを計算"""
return np.mean([1.0 / r for r in ranks if r > 0])
# 使用例
# 関連度スコア(実際の順序)
relevances = [3, 2, 0, 1, 0] # 1位が関連度3, 2位が関連度2, ...
print(f"NDCG@3: {ndcg_at_k(relevances, 3):.4f}")
print(f"NDCG@5: {ndcg_at_k(relevances, 5):.4f}")
# 正解文書の順位
ranks = [1, 3, 2, 5] # 4クエリで正解が1位, 3位, 2位, 5位
print(f"MRR: {mrr(ranks):.4f}")
リランキング手法の比較
| 手法 | 精度 | 速度 | コスト |
|---|---|---|---|
| Cross-Encoder | 高 | 遅い | 中 |
| ColBERT | 中〜高 | 中 | 中 |
| LLM Pointwise | 高 | 遅い | 高 |
| LLM Pairwise | 非常に高 | 非常に遅い | 非常に高 |
まとめ
本記事では、RAGシステムにおけるリランキング手法を解説しました。
- リランキングの目的: ファーストステージ検索の結果を精密に再順位付け
- Cross-Encoder: クエリと文書を連結して高精度にスコアリング
- ColBERT: トークンレベルのLate Interactionで効率と精度を両立
- LLMベース: 最も高精度だが計算コストが高い
次のステップとして、以下の記事も参考にしてください。