Online Set Learning from Precision and Recall Feedback¶

会议: NeurIPS 2026
arXiv: 2605.09565
OpenReview: https://openreview.net/forum?id=8KsPIzpp5i
领域: 其他
关键词: 在线学习、集合学习、精确率与召回率、VC维、遗憾界

一句话总结¶

本文首次形式化了仅接收随机单样本精确率与召回率反馈的在线未知集合学习问题，证明了假设类可学习的充要条件是有穷 VC 维，并在可实现与不可知设定下分别给出了次线性遗憾界算法与下界刻画。

研究背景与动机¶

在推荐系统、招聘候选人初筛、异常网络流量检测及信息检索等广泛的决策场景中，系统往往需要向外部环境或用户输出一个候选项集合，而非单一实体或单一样本标签。在评估集合预测质量时，传统监督学习常用的严格 0/1 匹配损失过于严苛，只要预测集合覆盖了绝大部分目标项且仅夹杂少量无关项，在实际应用中就应被视为高质量预测；因此，衡量相关性比例的精确率（Precision）与衡量覆盖范围的召回率（Recall）成为了集合预测最通用的自然准则。

然而，将精确率与召回率置于序贯在线决策框架中时，学习器面临着极不对称的反馈机制与严峻的信息局限。在每一轮交互中，学习器只能获得单一样本维度的二值反馈：要么是从预测集合中随机采样一项并获知其是否属于目标集（精确率反馈），要么是从真实目标集中随机采样一项并获知其是否落在预测集合中（召回率反馈）。这导致精确率反馈呈现典型的多臂老虎机（Bandit）局部可见性——未被选中的集合完全无法观测其精确率；而召回率反馈则具备全信息（Full-Information）特性，任何目标集正样本都可用来同时检验所有候选集合的覆盖情况。在经典离线 PAC 学习中，经验风险最小化（ERM）原则通常足以解决可实现问题；但在此类在线非对称反馈模型下，任意经验一致的假设都会因预测过大而在未探索区域遭遇灾难性的精确率惩罚，导致传统 ERM 彻底失效，甚至在不可知（Agnostic）场景下所有适定（Proper）学习算法都必然蒙受线性遗憾。

面对这种强依赖性与信息不对称，理论机器学习的核心基础问题亟待解答：在线集合学习的统计可学习性本质上由何种复杂度维度所刻画？学习器能否仅凭单点弱反馈突破适定学习的瓶颈？核心 idea：本文证明在线集合学习可学习的充要条件是假设类具有有限 VC 维，在可实现设定下通过「最小一致集选择」仅凭召回反馈实现 $O(d \log^2 T)$ 紧凑遗憾；在不可知设定下通过「基数转换估计」与包含空集输出的非适定三阶段算法 APRIL，将遗憾界压制至 $\tilde{O}(d^{1/4} T^{3/4})$。

方法详解¶

整体框架¶

在线集合学习的交互协议建立在基域 $\mathcal{X}$、环境给定的可用子集 $X \subseteq \mathcal{X}$ 以及未知的目标集合 $N^{\text{target}} \subseteq X$ 之上。在每一轮 $t=1, \dots, T$，学习器输出一个预测子集 $N_t \subseteq X$。环境以等概率 $1/2$ 独立提供两种反馈之一：以 $1/2$ 概率提供召回反馈，从 $N^{\text{target}}$ 中均匀随机抽取样本 $u_t \sim \text{Unif}(N^{\text{target}})$，学习器获得即时收益 $g_t(N_t) = \mathbb{I}(u_t \in N_t)$；以 $1/2$ 概率提供精确率反馈，从预测集 $N_t$ 中均匀随机抽取样本 $v_t \sim \text{Unif}(N_t)$ 并揭示真实正负标签 $y_t = \mathbb{I}(v_t \in N^{\text{target}})$，即时收益为 $g_t(N_t) = y_t$。任何集合 $N$ 的期望收益均严格对应精确率与召回率的等权平均： $$g(N) = \frac{1}{2} r(N) + \frac{1}{2} p(N) = \frac{1}{2} \frac{|N \cap N^{\text{target}}|}{|N^{\text{target}}|} + \frac{1}{2} \frac{|N \cap N^{\text{target}}|}{|N \cap X|}$$

针对可实现与不可知两种学习环境，本文提出了分层处理的算法体系。在可实现设定中，学习器只需维护与历史召回样本一致的假设子类，并始终选取在当前可用域 $X$ 中基数最小的集合；在不可知设定中，算法 APRIL（Adaptive Precision-Recall Interactive Learner）采用三阶段自适应交互架构：第一阶段通过任意集合探测并过滤召回率，第二阶段利用高召回集中最具紧凑性的代表项探测精确率并反推真实目标集基数 $|N^{\text{target}}|$，第三阶段进入自适应在线更新；当发现假设类收益无法战胜基准时果断预测空集 $\emptyset$（非适定学习）。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["输入：假设类 H、可用域 X、轮数 T"] --> S1["阶段1：召回率全局粗筛<br/>固定采样 T1 轮，保留高召回候选子集 H1"]
    S1 --> S2["阶段2：紧凑集探测与基数反演<br/>运行最小集 N1 收集精确率反馈，估计目标集大小 n*"]
    S2 --> S3{"阶段3：非适定检验与候选过滤"}
    S3 -->|候选集 H_hat 为空| BranchEmpty["输出空集 ∅<br/>保底获得 1/2 收益，规避线性遗憾"]
    S3 -->|候选集 H_hat 非空| BranchUpdate["阶段3：在线自适应微调<br/>轮轮更新 r_t 与 p_t，输出经验收益最大假设"]
    BranchEmpty --> Out["累积遗憾分析与理论界保证"]
    BranchUpdate --> Out

关键设计¶

1. 极小一致子集选择（可实现设定）：仅依赖召回反馈的正则化 ERM

在可实现设定中，存在最优假设 $N^\star \in \mathcal{H}$ 满足 $r(N^\star)=1$ 且 $p(N^\star)=1$。直觉上采用标准经验风险最小化（ERM）选取任意与历史观测一致的假设似乎可行，但这一直觉完全错误：若目标集 $N^{\text{target}} = \{0\}$，而某个平凡候选集包含了全集 $\{0, 1, \dots, n\}$，该超集永远满足召回样本 $u_t=0$ 的一致性要求，却会因包含了大量外部负样本而持续遭受高达 $1/2$ 的精确率损失。因此，标准 ERM 无法收敛。

为此，设计采用极大似然正则化原则：在每一轮 $t$，仅维护与所有历史召回反馈样本 $\{u_\tau\}_{\tau=1}^{t-1}$ 一致的候选集子族 $H_t = \{N \in \mathcal{H} \mid u_\tau \in N, \forall \tau < t\}$，并强制选择有效元素基数最小的集合： $$N_t \in \arg\min_{N \in H_t} |N \cap X|$$ 该设计的精妙之处在于：由于目标集本身 $N^\star$ 必然属于 $H_t$ 且具备完美精确率与召回率，其有效基数必定满足 $|N^\star \cap X| = |N^{\text{target}}|$。选取基数最小的集合确保了 $|N_t \cap X| \le |N^\star \cap X| = |N^{\text{target}}|$。根据恒等式 $p(N_t) = r(N_t) \frac{|N^{\text{target}}|}{|N_t \cap X|}$，立刻推导出 $p(N_t) \ge r(N_t)$。这意味着学习器完全不需要显式观测任何精确率反馈，精确率误差被召回率误差严格单调上界控制；借助有限 VC 维在均匀分布下的 PAC 泛化界，单轮召回损失在 $t$ 步后以高概率衰减为 $O(\frac{d \log(t/d) + \log(T/\delta)}{t})$，求和后直接达成 $O(d \log^2 T)$ 的高概率遗憾界。

2. 目标集基数间接估计器（不可知设定）：打通 Bandit 精确率全域评估

在不可知设定下，$g(N^\star)$ 可能远小于 1，上述以最小基数保证 $p(N) \ge r(N)$ 的代数结构彻底失效，学习器必须同时感知精确率与召回率。然而精确率反馈具有 Bandit 局部性（只有选中的集合才能被采样），无法直接对假设类中的海量集合逐一评估。

为打破这一信息瓶颈，设计发掘了精确率、召回率与目标集合总大小之间的核心代数关联：对于任意集合 $N \subseteq X$，均恒有 $|N^{\text{target}}| = \frac{p(N) \cdot |N \cap X|}{r(N)}$。如果算法能够准确获知全局标量 $|N^{\text{target}}|$，那么任意未曾执行过的候选假设 $N'$ 的精确率都可以通过其已知的全信息召回率估计 $\hat{r}(N')$ 与集合基数 $|N' \cap X|$ 间接合成出来：$\hat{p}(N') = \hat{r}(N') \frac{\hat{n}^\star}{|N' \cap X|}$。算法利用任意选定的一组探测序列及其精确率观测值 $y_t \in \{0, 1\}$，构造了全局目标基数无偏估计器： $$\hat{n}^\star = \text{EST}\left(\hat{r}(\cdot), (N_t, y_t)_{t=1}^m\right) = \frac{1}{m} \sum_{t=1}^m \frac{\mathbb{I}(y_t = 1) \cdot |N_t \cap X|}{\hat{r}(N_t)}$$ 通过 Azuma-Hoeffding 不等式与一致收敛性分析，只要探测集具有非平凡的召回率下界 $\alpha$，该估计器对目标集大小的相对误差便以 $\tilde{O}(\frac{1}{\alpha \sqrt{m}})$ 的速率快速收敛，从而使全域离线评估所有假设的精确率成为可能。

3. 三阶段自适应筛选与非适定预测（APRIL 框架）：突破线性遗憾下界

在不可知集合学习中，适定算法（Proper Learner，每轮预测强制取自 $\mathcal{H}$）存在天然缺陷：当 $\mathcal{H}$ 由 $T$ 个互相正交的大集合组成时，环境可以将真实目标集构造为在其中一个集合中包含稍多的正样本，使问题退化为多臂老虎机硬实例，迫使任何适定算法蒙受 $\Omega(T)$ 的线性遗憾。然而观察发现，平凡预测——空集 $\emptyset$ 与全集 $X$——在任意数据分布下的收益至少为 $1/2$（$p(\emptyset)=1, r(\emptyset)=0$ 带来收益 $1/2$；$r(X)=1, p(X) \ge 0$ 也可提供底线保证）。如果最优假设的最优裕度 $\alpha_{\mathcal{H}} = 2g(N^\star) - 1 < 0$，预测类内假设反而不如直接预测空集。

APRIL 框架依此将非适定输出（允许预测 $\emptyset$）与三阶段自适应过滤深度融合： - 阶段 1（召回过滤）：运行固定集合 $T_1 = \tilde{O}(d/\alpha^2)$ 轮，利用全信息召回样本建立经验召回率 $\hat{r}_0(N)$，利用 VC 维一致收敛界保留 $\hat{r}_0(N) \ge 7\alpha/8$ 的子集族 $H_1$；并在其中选出密度最高项 $N_1 = \arg\max_{N \in H_1} \frac{\hat{r}_0(N)}{|N \cap X|}$； - 阶段 2（精确率过滤）：执行 $N_1$ 共 $T_2 = \tilde{O}(1/\alpha^2)$ 轮以获得稳定的精确率样本，调用基数估计器生成 $\hat{n}_0^\star$，构造各假设的经验精确率 $\hat{p}_0(N) = \hat{r}_0(N) \frac{\hat{n}_0^\star}{|N \cap X|}$，过滤得到双高子集族 $\hat{\mathcal{H}}$； - 阶段 3（在线决策或止损）：若 $\hat{\mathcal{H}} = \emptyset$，判定该类在当前环境下最优裕度不足，在剩余所有轮次恒定输出空集 $\emptyset$ 止损；若非空，则利用累积的历史样本持续更新动态估计量 $(\hat{r}_t, \hat{n}^\star_t, \hat{p}_t)$，贪心选择综合收益估计最高的假设 $N_t = \arg\max_{N \in \hat{\mathcal{H}}} (\hat{r}_t(N) + \hat{p}_t(N))$。

损失函数 / 训练策略¶

该框架下的优化目标为最小化期望累积遗憾： $$\text{Reg}_T = g(N^\star) \cdot T - \sum_{t=1}^T g(N_t)$$ 在不可知 APRIL 算法中，裕度超参数 $\alpha$ 平衡了探索成本（阶段 1 与阶段 2 的固定轮数 $T_1 + T_2 = \tilde{O}(d/\alpha^2)$）与利用阶段的逼近误差（$\tilde{O}(\frac{\sqrt{d T}}{\alpha})$ 或 $\alpha T$）。通过理论最优化配置： $$\alpha^\star = \left(\frac{d \log(2eT/d) + \log(T/\delta)}{T}\right)^{1/4}$$ 算法平衡了两项阶数，达到无条件高概率遗憾界 $O(\sqrt{d T \log(T/d)} + (d \log(T/d))^{1/4} T^{3/4}) = \tilde{O}(d^{1/4} T^{3/4})$。当外部环境具有常数裕度 $\alpha_{\mathcal{H}} \ge C > 0$ 时，结合在区间 $[\alpha^\star, 1]$ 上的对分搜索，该算法的遗憾界进一步加速收敛至经典下界量级 $\tilde{O}(\sqrt{d T})$。

实验关键数据¶

主实验¶

本文为纯统计学习理论研究，无传统经验数据集 Benchmark。核心主结果为对在线集合学习在可实现与不可知两大设定下的理论可学习性、遗憾界复杂度与算法机制对比：

学习设定	算法方案	学习类型	依赖反馈类型	理论遗憾上界 $\text{Reg}_T$	理论遗憾下界	核心复杂度指标
可实现设定 (Realizable)	在线分类规约 (Alg 1)	适定 (Proper)	召回 + 精确率	$O(\text{Ldim}(\mathcal{H}))$	$\Omega(1)$	Littlestone 维
可实现设定 (Realizable)	极大似然极小集 (Alg 2 原理)	适定 (Proper)	仅召回反馈 (Recall-only)	$O(d \log^2 T)$	$\Omega(d)$	VC 维 $d$
不可知设定 (Agnostic)	任意适定算法 (Proper)	适定 (Proper)	召回 + 精确率	$\Omega(T)$ (线性遗憾/不可学)	$\Omega(T)$	任何维度失效
不可知设定 (Agnostic)	APRIL (通用参数 $\alpha^\star$)	非适定 (Improper, 含 $\emptyset$)	召回 + 精确率	$\tilde{O}(d^{1/4} T^{3/4})$	$\Omega(\sqrt{d T})$	VC 维 $d$
不可知设定 (Agnostic)	APRIL (常数裕度 $\alpha_{\mathcal{H}} \ge C$)	非适定 (Improper, 含 $\emptyset$)	召回 + 精确率	$\tilde{O}(\sqrt{d T})$	$\Omega(\sqrt{d T})$	VC 维 $d$

消融实验¶

为解析各核心算法组件与信息源的必要性，下表系统总结了针对反馈类型、算法适定性及假设选择准则的理论消融与失效机理：

算法机制变体	设定场景	理论遗憾表现	机制状态与行为特征	失效或改变之根因分析
标准任意 ERM	可实现	$\Omega(T)$ (线性发散)	选取任意一致超集 $N \in H_t$	缺乏基数惩罚，过大集合持续遭受固定精确率惩罚
极小一致集 ERM (本文)	可实现	$O(d \log^2 T)$ (次线性)	严格选取 $	N \cap X
丢弃召回反馈 (纯精确率)	可实现 / 不可知	$\Omega(T)$ (无法收敛)	仅能观察预测集局部正负例	Bandit 精确率缺乏全局探索机制，无法发现未命中正例
丢弃精确率反馈 (纯召回)	不可知	$\Omega(T)$ (无法区分精度)	仅凭召回率对全类打分	无法识别超大低精度集合，缺失基数乘子修正因子
强制适定学习 (禁用 $\emptyset$)	不可知	$\Omega(T)$ (多臂硬实例)	限制在 $\mathcal{H}$ 内部输出	当全类收益 $< 1/2$ 时无法借助空集止损避开对抗臂
APRIL 引入非适定 $\emptyset$	不可知	$\tilde{O}(d^{1/4} T^{3/4})$ (成功可学)	动态检验并允许预测 $\emptyset$	空集稳定获得 $1/2$ 基准保底收益，平抑裕度亏损风险

关键发现¶

VC 维而非 Littlestone 维决定可学习性：尽管在线二值分类的可学习性本质上受 Littlestone 维统治，但在线集合学习问题可学习的充要条件退化回了经典的有限 VC 维。即便某假设类的 Littlestone 维为无穷大，只要 VC 维有限，依然能实现次线性遗憾。
反馈信息的不对称性破缺：在可实现情形下，精确率反馈是完全多余的（Redundant），仅仅利用正样本召回信号即可实现完备学习；然而在不可知情形下，两者缺一不可，必须借助召回率与目标集基数的代数变换来重构未见集合的精确率。
适定与非适定的相变分离：在不可知场景下，强求适定性会直接导致算法遭遇信息论下界阻击（$\Omega(T)$）；而非适定预测（仅仅加入一个极其简单的平凡解 $\emptyset$）便足以使整个不可学习的困难问题跃迁为可学习。

亮点与洞察¶

将几何尺寸作为隐式正则项：在可实现场景中，算法通过显式偏好更小的子集，自动使得 $p(N) \ge r(N)$，巧妙地将单向二值召回误差转化为精确率的双向约束，完全省去了对精确率的随机探索开销。
目标集基数作为全局信息的代理桥梁：面对精确率反馈的多臂老虎机局部性，论文没有陷入复杂的局部探索-利用权衡，而是挖掘出了 $|N^{\text{target}}| = p(N)|N|/r(N)$ 这一全局守恒量，以全局基数估计作为杠杆撬动了所有未选集合的离线评估。
非适定预测作为低裕度安全气囊：在假设类整体表现不佳时，跳出类内假设、退避至常数收益的空集 $\emptyset$，这种机制为高噪声或低质量特征下的在线决策系统提供了极为实用的止损范式。

局限与展望¶

收敛速率的对数阶差距：在可实现设定中，当前算法上界为 $O(d \log^2 T)$，而信息论下界为 $\Omega(d)$，两者之间存在 $\log^2 T$ 的差距，尚不明确该因子能否被彻底消除。
不可知遗憾界非紧：不可知设定下 APRIL 算法的通用遗憾界为 $\tilde{O}(d^{1/4} T^{3/4})$，而经典在线学习的匹配界通常为 $\tilde{O}(\sqrt{d T})$，弥合此 $T^{1/4}$ 的差距仍属未决开放问题。
固定已知可用域假设：论文理论依赖于学习器事先完全知晓候选有限域 $X \subseteq \mathcal{X}$，若可用域随时间动态变化或未知，有穷 VC 维是否仍为充要条件仍有待探索。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立精确率-召回率弱反馈下的在线集合学习框架，理论贡献扎实深刻。
实验充分度: ⭐⭐⭐⭐☆ 纯统计理论论文，缺乏大规模真实推荐/检索系统上的工程落地验证，但理论证明与反例构造完备严谨。
写作质量: ⭐⭐⭐⭐⭐ 概念动机清晰自然，数学推导流畅严密，定理表述层次分明。
价值: ⭐⭐⭐⭐⭐ 为信息检索、安全检测与冷启动推荐中的集合决策提供了清晰的统计学习复杂度基准。

算法机制变体	设定场景	理论遗憾表现	机制状态与行为特征	失效或改变之根因分析
标准任意 ERM	可实现	\(\Omega(T)\) (线性发散)	选取任意一致超集 \(N \in H_t\)	缺乏基数惩罚，过大集合持续遭受固定精确率惩罚
极小一致集 ERM (本文)	可实现	\(O(d \log^2 T)\) (次线性)	严格选取 $	N \cap X
丢弃召回反馈 (纯精确率)	可实现 / 不可知	\(\Omega(T)\) (无法收敛)	仅能观察预测集局部正负例	Bandit 精确率缺乏全局探索机制，无法发现未命中正例
丢弃精确率反馈 (纯召回)	不可知	\(\Omega(T)\) (无法区分精度)	仅凭召回率对全类打分	无法识别超大低精度集合，缺失基数乘子修正因子
强制适定学习 (禁用 \(\emptyset\))	不可知	\(\Omega(T)\) (多臂硬实例)	限制在 \(\mathcal{H}\) 内部输出	当全类收益 \(< 1/2\) 时无法借助空集止损避开对抗臂
APRIL 引入非适定 \(\emptyset\)	不可知	\(\tilde{O}(d^{1/4} T^{3/4})\) (成功可学)	动态检验并允许预测 \(\emptyset\)	空集稳定获得 \(1/2\) 基准保底收益，平抑裕度亏损风险