检索变好了吗？recall@k、MRR 与 nDCG

1先建评测集：查询 + 相关性标注

检索评测集长这样：一批查询，每条查询标出语料里哪些文档相关、相关到什么程度。BugHunt-Bench 里的一条：

{"id": "q18", "text": "我收藏的文章列表显示错了",
 "rel": {"BUG-118": 2, "REQ-09": 2, "EXP-05": 1}}   # 没列出的文档都算 0

等级要事先写成规则，否则两个人标出来不一样：2 = 能直接回答查询（同一个 Bug，或明确规定这个行为的需求条款）；1 = 相关、有帮助（同模块的相关 Bug、页面探索记录）；0 = 无关。

查询从哪来，各有什么偏差

三种来源混着用最稳：真实日志定分布，人工补难例，LLM 生成扩量但必须人工核对、补标其他相关文档。查询要按模块和类型分层，别让一个模块占一半。

2四个指标：定义和手算

记 \(R\) 为一条查询的相关文档集合（等级 > 0），检索结果前 \(k\) 名为 \(\text{top}_k\)，第 \(i\) 名的等级为 \(rel_i\)。

IDCG 是把全部已标注的相关文档按等级从高到低排好后的 DCG，不是只把检索到的那几篇重排。所以检索结果里漏掉一篇相关文档，nDCG 也会被扣分。

手算：q18 "我收藏的文章列表显示错了"

相关文档 3 篇：BUG-118（2）、REQ-09（2）、EXP-05（1）。两个检索器的前 5 名等级：

IDCG@5 = 2/1 + 2/log₂3 + 1/log₂4 = 2 + 1.262 + 0.5 = 3.762。两个系统都找到了 2 篇、漏了 EXP-05，recall 和 precision 一模一样；B 把两篇最相关的放在最前面，RR 和 nDCG 才看得出来。

几个容易算错的地方

1. precision@k 的分母固定是 k：只返回了 3 篇，precision@5 也除以 5。
2. MRR 要写截断：前 10 名都没有相关文档时 RR 记 0，汇报成 MRR@10。TREC-8 问答评测（Voorhees，1999）用的就是这个规则，只看前 5 个回答。
3. recall、precision、MRR 要先把等级二值化：这里"等级 > 0 就算相关"；阈值换成"等级 = 2"，数字会变，要写清楚。
4. 增益和折扣有不同写法：上面是线性增益 \(rel_i\)、折扣 \(\log_2(i+1)\)，和 scikit-learn 的 ndcg_score 一致。另一种常见写法是增益 \(2^{rel_i}-1\)（Burges 等 2005 年的 RankNet 论文就这么定义），更看重高等级文档。DCG 最早见于 Järvelin 和 Kekäläinen 在 SIGIR 2000 的论文，归一化的 nDCG 在两人 2002 年的 TOIS 论文里给出；原文的折扣对排在前 \(b\) 名（\(b\) 是对数的底）的文档不打折，和上面的写法也不一样。不同写法的数字不能混着比较，汇报时写清楚。
5. 没有相关文档的查询：recall 和 nDCG 的分母是 0，要么从评测集里去掉，要么单独统计"应该什么都不返回"的情况。

3指标之间的取舍

上面的 q18 已经说明：只看 recall 会以为 A、B 一样。反过来也有：一个系统把唯一一篇相关文档从第 1 名挤到第 4 名，recall@5 不变，MRR 从 1 掉到 0.25。

4重排：先粗后细

第一阶段用便宜的检索器（BM25、嵌入向量）从全库捞出前 100 篇；第二阶段用更贵的模型对这 100 篇重新打分，取前几名。

几个一手数字。Nogueira 和 Cho（2019）用 BERT 做这种"查询 + 段落"拼接打分的重排，MS MARCO 开发集上 MRR@10 从 BM25 的 16.7 提到 36.5（BERT Large）。Sentence-BERT 论文（Reimers 和 Gurevych，2019）算过交叉编码的代价：在 10,000 个句子里找最相似的一对，要做约 5000 万次推理，V100 上约 65 小时；先各自算嵌入只要约 5 秒。RankGPT（Sun 等，2023）让 LLM 对 BM25 的前 100 篇输出排列，一次放不下，就用窗口 20、步长 10 从后往前滑。BEIR 基准（Thakur 等，2021）的结论是：BM25 是稳健的基线；零样本下，重排模型（BM25 + 交叉编码重排）和后期交互模型（ColBERT）平均效果最好，但计算成本高。

5两个版本对比：按查询配对

两个检索器跑的是同一批查询，这和「新 prompt 从 82% 涨到 86%，是真的变好了吗？」那章的同一批用例是一回事：查询是配对单位。每条查询算一个差值 \(d_q = \text{B 的得分} - \text{A 的得分}\)，然后：

1. 配对 bootstrap：从 \(n\) 条查询里有放回地抽 \(n\) 条（抽中一条，就同时带上 A 和 B 在它上面的得分），算差值均值；重复 10000 次，取第 2.5、97.5 百分位。
2. 随机化检验（permutation test）：原假设"A、B 可以互换"，每条查询随机交换 A、B 的得分（差值随机变号），看均值差至少这么大的比例。

Smucker、Allan 和 Carterette（2007）在 TREC 数据上比较过几种检验，结论是随机化检验、bootstrap 和配对 t 检验在实践中差别不大；Wilcoxon 和符号检验检出能力差，还可能误报显著，他们建议不再用来检验均值差。

不能把 A、B 各自独立重抽：查询难度差别很大（有的查询两个系统都满分，有的都很差），不配对会把难度的波动算进噪声。下面的实验里，nDCG@5 的不配对区间约是配对区间的两倍宽。

查询要多少条

配对设计下，用正态近似（双侧 α = 0.05，功效 80%）：

\(\sigma_d\) 是逐查询差值的标准差，从一次小规模试跑里估；\(\delta\) 是你关心的最小差距。实验里 nDCG@5 差值的标准差是 0.095：要检出 0.05 的差约 29 条查询，检出 0.02 的差约 179 条。差距减半，查询数翻四倍。

6面试要点与代码

一句话讲清楚

检索评测先建"查询 + 分级相关性"标注集（真实日志定分布、人工补难例、LLM 扩量后人工核对，至少把待比较系统的前 k 名都标了）；recall@k 看找没找全，precision@k 看噪声，MRR 看第一篇有用的排第几，nDCG@k 按等级和位置折扣看整体排序；主指标事先定。两个版本对比按查询配对：逐查询差值做 bootstrap 区间或随机化检验，查询数按差值标准差和想检出的差距估。

追问准备

1. nDCG 的 IDCG 怎么算？用全部已标注的相关文档按等级理想排序，取前 k 名的 DCG。只用检索到的文档会高估。
2. 重排加了，怎么证明值？同一批查询，重排前后做配对比较，主指标看 nDCG@10；同时报第一阶段的 recall@100（重排上限）和每条查询多出的时延、费用。
3. 标注没标全怎么办？把两个系统的前 k 名合并成候选池送去标注；新系统大量检索到未标注文档时，先补标再比较。
4. RAG 端到端答对率已经有了，还要检索指标吗？要。答错时要分清是没检索到，还是检索到了没用上；检索指标单独定位第一种。

常见错误说法

最小实现（Python，只依赖 numpy）

"""检索评测：recall@k、precision@k、MRR、nDCG@k，以及两个检索器的按查询配对 bootstrap。

运行：python3 retrieval_eval.py（依赖 numpy；有 scikit-learn 时顺带用 ndcg_score 校验 nDCG）
数据：同目录 data.json，BugHunt-Bench 场景的小型自制标注集（38 篇文档、30 条查询、0/1/2 分级相关性）。
"""
import json
import math
import re
from pathlib import Path

import numpy as np

K = 5            # 汇报 @5：Agent 一次只往上下文里塞前 5 篇
DEPTH = 10       # MRR 只看前 10 名（MRR@10），10 名以外没找到记 0
N_BOOT = 10_000


# ---------- 指标：ranking 是检索结果的文档 id 列表，rel 是 {文档 id: 相关性等级} ----------

def recall_at_k(ranking, rel, k):
    relevant = {d for d, g in rel.items() if g > 0}
    return len(relevant & set(ranking[:k])) / len(relevant)


def precision_at_k(ranking, rel, k):
    return sum(rel.get(d, 0) > 0 for d in ranking[:k]) / k   # 分母固定是 k，结果不足 k 篇也一样


def reciprocal_rank(ranking, rel, depth=DEPTH):
    for i, d in enumerate(ranking[:depth], start=1):
        if rel.get(d, 0) > 0:
            return 1 / i
    return 0.0


def dcg(gains):
    return sum(g / math.log2(i + 1) for i, g in enumerate(gains, start=1))


def ndcg_at_k(ranking, rel, k):
    ideal = dcg(sorted(rel.values(), reverse=True)[:k])     # 理想排序来自全部标注，不只是检索到的
    return dcg([rel.get(d, 0) for d in ranking[:k]]) / ideal


# ---------- 两个检索器：TF-IDF 余弦 与 BM25，中文按字的一元 + 二元切分 ----------

def tokenize(text):
    tokens = []
    for run in re.findall(r"[a-z0-9]+|[一-鿿]+", text.lower()):
        if run.isascii():
            tokens.append(run)
        else:
            tokens += list(run) + [run[i:i + 2] for i in range(len(run) - 1)]
    return tokens


class Index:
    def __init__(self, docs):
        self.ids = list(docs)
        self.toks = [tokenize(docs[d]) for d in self.ids]
        self.n = len(self.ids)
        self.df = {}
        for toks in self.toks:
            for t in set(toks):
                self.df[t] = self.df.get(t, 0) + 1
        self.avgdl = sum(map(len, self.toks)) / self.n

    def _rank(self, scores):
        order = sorted(range(self.n), key=lambda i: (-scores[i], self.ids[i]))   # 同分按 id 排，结果可复现
        return [self.ids[i] for i in order]

    def tfidf(self, query):
        idf = lambda t: math.log((1 + self.n) / (1 + self.df.get(t, 0))) + 1
        def vec(toks):
            v = {}
            for t in toks:
                v[t] = v.get(t, 0) + idf(t)
            norm = math.sqrt(sum(x * x for x in v.values())) or 1.0
            return {t: x / norm for t, x in v.items()}
        q = vec(tokenize(query))
        return self._rank([sum(q.get(t, 0) * x for t, x in vec(toks).items()) for toks in self.toks])

    def bm25(self, query, k1=1.2, b=0.75):
        qt = tokenize(query)
        scores = []
        for toks in self.toks:
            tf, s = {}, 0.0
            for t in toks:
                tf[t] = tf.get(t, 0) + 1
            for t in qt:
                if t in tf:
                    idf = math.log(1 + (self.n - self.df[t] + 0.5) / (self.df[t] + 0.5))
                    s += idf * tf[t] * (k1 + 1) / (tf[t] + k1 * (1 - b + b * len(toks) / self.avgdl))
            scores.append(s)
        return self._rank(scores)


# ---------- 按查询配对：bootstrap 区间 + 随机化检验 ----------

def paired_bootstrap(a, b, n_boot=N_BOOT, seed=0):
    """a、b 是两个系统在同一批查询上的逐查询得分。整条查询一起重抽，返回 (b - a) 均值差的 95% 区间。"""
    diff = np.asarray(b) - np.asarray(a)
    idx = np.random.default_rng(seed).integers(0, diff.size, size=(n_boot, diff.size))
    return np.percentile(diff[idx].mean(axis=1), [2.5, 97.5])


def randomization_test(a, b, n_perm=N_BOOT, seed=0):
    """原假设：两个系统可以互换。每条查询随机交换 A、B（差值随机变号），看均值差至少这么大的比例（双侧）。"""
    diff = np.asarray(b) - np.asarray(a)
    signs = np.random.default_rng(seed).choice([-1, 1], size=(n_perm, diff.size))
    null = np.abs((signs * diff).mean(axis=1))
    return (np.sum(null >= abs(diff.mean()) - 1e-12) + 1) / (n_perm + 1)


def queries_needed(sd, delta, z_alpha=1.959964, z_beta=0.841621):
    """配对设计、双侧 α = 0.05、功效 80% 的正态近似：要检出均值差 delta 需要多少条查询。"""
    return math.ceil(((z_alpha + z_beta) * sd / delta) ** 2)


def self_check():
    rel = {"d1": 2, "d2": 1, "d3": 2}
    ranking = ["x", "d1", "y", "d2", "z"]
    assert recall_at_k(ranking, rel, 5) == 2 / 3
    assert precision_at_k(ranking, rel, 5) == 2 / 5
    assert reciprocal_rank(ranking, rel) == 1 / 2
    expected = (2 / math.log2(3) + 1 / math.log2(5)) / (2 + 2 / math.log2(3) + 1 / math.log2(4))
    assert abs(ndcg_at_k(ranking, rel, 5) - expected) < 1e-12
    try:  # 用 scikit-learn 交叉校验：分数给全部文档，理想排序也来自全部文档
        from sklearn.metrics import ndcg_score
        docs = ranking + ["d3"]
        y_true = [[rel.get(d, 0) for d in docs]]
        y_score = [[len(docs) - i for i in range(len(docs))]]
        assert abs(ndcg_score(y_true, y_score, k=5) - expected) < 1e-12
    except ImportError:
        pass


def main():
    self_check()
    data = json.loads(Path(__file__).with_name("data.json").read_text(encoding="utf-8"))
    index, queries = Index(data["docs"]), data["queries"]
    metrics = {
        f"recall@{K}": lambda r, rel: recall_at_k(r, rel, K),
        f"precision@{K}": lambda r, rel: precision_at_k(r, rel, K),
        f"MRR@{DEPTH}": reciprocal_rank,
        f"nDCG@{K}": lambda r, rel: ndcg_at_k(r, rel, K),
    }
    runs = {"A: TF-IDF": [index.tfidf(q["text"]) for q in queries],
            "B: BM25": [index.bm25(q["text"]) for q in queries]}
    scores = {(s, m): np.array([f(r, q["rel"]) for r, q in zip(rs, queries)])
              for s, rs in runs.items() for m, f in metrics.items()}

    print(f"{len(data['docs'])} 篇文档，{len(queries)} 条查询，bootstrap / 随机化各 {N_BOOT} 次\n")
    print(f"{'指标':<14}{'A: TF-IDF':>10}{'B: BM25':>10}{'B - A':>9}   {'配对 bootstrap 95% 区间':<24}{'随机化 p':>8}")
    for m in metrics:
        a, b = scores[("A: TF-IDF", m)], scores[("B: BM25", m)]
        lo, hi = paired_bootstrap(a, b)
        print(f"{m:<14}{a.mean():>10.3f}{b.mean():>10.3f}{b.mean() - a.mean():>+9.3f}   "
              f"[{lo:+.3f}, {hi:+.3f}]{'':<10}{randomization_test(a, b):>8.3f}")

    m = f"nDCG@{K}"
    diff = scores[("B: BM25", m)] - scores[("A: TF-IDF", m)]
    print(f"\n{m} 逐查询差值（B - A）：B 更好 {int((diff > 1e-9).sum())} 条，"
          f"A 更好 {int((diff < -1e-9).sum())} 条，打平 {int((np.abs(diff) <= 1e-9).sum())} 条")
    for q, d in sorted(zip(queries, diff), key=lambda x: x[1]):
        if abs(d) > 1e-9:
            print(f"  {q['id']} {d:+.3f}  {q['text']}")
    sd = diff.std(ddof=1)
    print(f"差值标准差 {sd:.3f}；要以 80% 功效检出 nDCG 差 0.02 / 0.05，约需 "
          f"{queries_needed(sd, 0.02)} / {queries_needed(sd, 0.05)} 条查询")


if __name__ == "__main__":
    main()

输出（Python 3.9 / numpy 1.22 / scikit-learn 1.1）：

38 篇文档，30 条查询，bootstrap / 随机化各 10000 次

指标             A: TF-IDF   B: BM25    B - A   配对 bootstrap 95% 区间        随机化 p
recall@5           0.844     0.828   -0.017   [-0.042, +0.000]             0.507
precision@5        0.433     0.420   -0.013   [-0.033, +0.000]             0.507
MRR@10             0.950     1.000   +0.050   [+0.000, +0.117]             0.246
nDCG@5             0.871     0.890   +0.018   [-0.012, +0.055]             0.305

nDCG@5 逐查询差值（B - A）：B 更好 6 条，A 更好 8 条，打平 16 条
  q24 -0.109  编辑器页面提交过哪些 Bug
  q28 -0.092  接口返回 422 但是前端不显示错误
  q12 -0.080  没有头像的用户显示什么
  q20 -0.070  连点两下发布出现两篇一样的文章
  q25 -0.050  文章列表每页显示多少篇
  q01 -0.018  点了收藏数字没有加一
  q13 -0.012  筛选标签以后翻页是空白页
  q21 -0.012  改了密码以后老密码还能用
  q23 +0.022  设置页面已经测过哪些功能
  q03 +0.037  密码输错了界面上没有任何报错
  q27 +0.140  Your Feed 应该显示谁的文章
  q14 +0.236  修改文章正文后 tag 没了
  q30 +0.236  登录页和注册页测过了吗
  q18 +0.326  我收藏的文章列表显示错了
差值标准差 0.095；要以 80% 功效检出 nDCG 差 0.02 / 0.05，约需 179 / 29 条查询

完整脚本（含 TF-IDF、BM25 和数据）在 week04_上下文与记忆/code/retrieval_eval/。用 scikit-learn 的 ndcg_score 交叉校验过 nDCG（把全部文档的分数都传进去，两者一致）。

公式显示依赖 KaTeX（CDN），断网时公式会显示成原始 LaTeX 源码，交互部分不受影响。