知识卡片：有限样本覆盖审计——高召回候选生成的认证与学习理论设计

一句话结论：针对高召回候选生成管道，若要认证遗漏的相关项很少，必须抽样排除池（excluded pool），并且任何有效审计所需排除池标签数至少为 (N_0/m) 量级；本文进而提供了精确有限样本审计工具箱，可在给定审查负担下选择最轻的候选生成器。

事件概述或研究问题：在许多实证管道（如文献筛选、物品推荐、异常检测）中，初始高召回阶段决定哪些项进入后续审查、标注或建模。该阶段遗漏的相关项将永久丢失。研究问题是：需要多少审计标签才能以有限样本有效性认证“遗漏的相关质量很小”？

方法/产品要点：

• 证明仅使用候选集内部标签无法认证任何非平凡的遗漏质量上界；必须从排除池（唯一可能含有未恢复相关项的区域）抽样。
• 证明一个匹配的有限语料下界：任何有效审计（在高概率下认证遗漏少于 (m) 个相关项，即使允许自适应且标注整个包含池）必须检查约 (N_0/m) 个排除池标签。因此，排除池审计在零遗漏情况下是极小极大速率最优的。
• 开发精确有限样本工具箱，使用二项分布和超几何分布反演（而非渐近近似），可认证遗漏质量、通过双池设计转换为召回率、同时认证预指定嵌套候选生成器族、生成针对宣称扰动机制的压力测试证书。
• 证书可与可观察的审查负担配对，选择满足遗漏质量目标的最轻预指定候选生成器。所有保证的前提是：候选生成器（或其预指定族）和审计规则在检查认证标签之前固定。

主要结果或产业意义：

• 理论贡献：刻画了高召回候选生成中遗漏质量认证的标签复杂度，厘清了排除池采样是必要条件且最优。
• 实践贡献：提供了一套无需渐近假设的精确认证方法，可直接用于需要高召回但资源有限的场景，例如法律证据开示、医学诊断筛选、安全审核等。
• 可将审计负担（需要标注的排除池样本量）与可接受的遗漏目标进行权衡，从而辅助系统设计。

为什么重要：现有方法常依赖渐近近似或仅利用候选集内部统计量，本文证明了这些做法在有限样本下对遗漏质量的认证存在根本局限，并给出了可操作的最优方案。它填补了高召回系统认证的理论空白，为需要可证明保证的关键应用提供了严谨工具。

局限与不确定性：待核实。摘要未明确提及局限，但可推断：①方法要求候选生成器（或族）在审计前固定，无法处理动态变化；②压力测试证书依赖于预先声明的扰动机制，对未预见的扰动可能无效；③实际应用中的标签成本可能因领域而异，理论下界在非零遗漏或自适应泄露场景下是否成立需进一步验证。

可用于图书/PPT/简报的角度：

• 对比“只靠内部标签”与“必须抽外部池”的直观反例（例如，过滤一个巨型语料库，仅凭通过过滤器的那部分数据无法知道过滤器外还有多少相关项）。
• 通过一个简单案例解释“极小极大速率最优”的含义：要保证漏掉不到 (m) 个相关项，约需检查 (N_0/m) 个外部样本（(N_0) 为排除池大小）。
• 强调“固定规则后再看标签”这一纪律的重要性，避免数据窥探导致的保证失效。

原始材料：

• 英文标题：Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design
• 英文关键词：high-recall candidate generation, coverage audit, finite-sample certification, missed mass, label complexity, minimax optimality
• 来源URL：https://arxiv.org/abs/2607.21480v1
• 作者：Martin Anthony, Kaveh Salehzadeh Nobari
• 发表于：2026-07-23 (arXiv)
• 类别：cs.LG, stat.ML