Active Learning from Positive and Unlabeled Examples¶

会议: NeurIPS 2026
arXiv: 2602.02081
OpenReview: https://openreview.net/forum?id=DaOrmOgOYi
领域: 其他
关键词: 主动学习, PU学习, 标签复杂度, 分歧系数, 弱监督学习

一句话总结¶

针对正例与无标签数据（PU学习）中专家仅以概率检出正例标签的弱反馈场景，本文首次提出了具备严格理论保障的主动PU学习框架与算法，证明了在先验已知与未知情形下仅需多付出与分歧系数 $\theta$ 成正比的代价即可达到 PAC 学习目标。

研究背景与动机¶

正例与无标签学习（PU Learning）是二分类中一种典型的弱监督学习范式，广泛存在于个性化推荐、异常检测、生物医学知识图谱补全及遥感影像分类等现实任务中。例如在推荐系统中，用户点击互动明确代表正向偏好，而未点击行为则含义模糊（可能是负向兴趣，也可能只是未被曝光）；在异常检测中，绝大多数有标记样本均为正常样本（正类），异常样本极度稀缺且难以明确标注。在此类应用中，专家标注资源昂贵且获取代价极高，亟需引入主动学习（Active Learning）机制，通过自适应选择最具信息量的数据样本来显著降低标注负担。

然而，将主动学习推广至 PU 场景面临独特的弱反馈壁垒。传统主动学习假定预言机（Oracle）能够对任何查询样本返回确定的二元标签（正例或负例）。但在 PU 场景下，专家往往无法判定样本是否为反例，甚至对正例也只能在特定成功率下做出确诊（即选自完全随机 SCAR 假设：正例仅以概率 $\omega$ 被确认并返回正标签，反例或未检出的正例均返回无信息的空符号 $\star$）。由于查询无法获得显式的负反馈，算法极易陷入假阳性风险失控或在缺乏正反馈时无法收敛版本空间的困境。此前虽然有少数基于启发式不确定性采样或正例优先级排序的实证研究，但始终缺乏有限样本下的严格标签复杂度（Label Complexity）理论分析。

针对这一根本理论空白，本文深入探究了连续分布下的主动 PU 学习极限。核心 idea：利用未标记数据先验质量约束限制假阳性上界，并将正例查询命中率转化为与分歧系数 $\theta$ 的几何约束，提出两阶段二分搜索与版本空间减半机制，首次建立有限标签复杂度理论界。

方法详解¶

整体框架¶

本文提出的主动 PU 学习框架涵盖“正类先验已知”与“正类先验未知”两种设定。算法核心遵循分歧驱动（Disagreement-based）的主动学习范式。在每轮查询中，算法仅对当前版本空间 $V$ 存在预测分歧的区域 $\text{DIS}(V)$ 进行拒绝采样并向预言机发起查询。若返回反馈为正标签（$s(x)=1$），则直接剔除所有预测为负的假设；若返回空反馈（$\star$），则根据当前累积的正例反馈率自适应调整正类先验边界，从而完成版本空间的压缩。

针对先验 $\pi_{\mathcal{D}}$ 未知的普遍场景，算法整体分为两大阶段：第一阶段运行正例检出率估计子程序 $\text{EstRate}$，在无监督与弱正例反馈下以高概率将专家检出概率 $\omega$ 估计至常数因子精度；第二阶段维护未标记集合上的正样本经验比例上界 $u_i$ 与所有假设一致预测为正的下界 $b_i$，通过监测分歧区内的正反馈检出率动态执行“先验二分收缩”或“版本空间分歧减半”，最终以至多 $O(\log(1/\varepsilon))$ 轮迭代收敛到误差小于 $\varepsilon$ 的分类器。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：假设空间 H、未标注池 D、精度 ε、置信度 δ"] --> B["阶段一：EstRate 检出概率估计<br/>估计专家检出率 ω_hat ∈ [ω/2, 2ω]"]
    B --> C["阶段二：先验区间与版本空间初始化<br/>初始化上界 u_0=1，下界 b_0，大样本集 S_1"]
    C --> D["分歧区域拒绝采样与查询<br/>在 DIS(V_i) 中抽取 λ_1 个样本发起专家查询"]
    D -->|正反馈比例 < ω_hat / 128θ| E["先验上界二分折半更新<br/>u_i+1 ← (u_i + b_i) / 2 并根据新先验剪枝 V_i"]
    D -->|正反馈比例 ≥ ω_hat / 128θ| F["分歧驱动版本空间减半剪枝<br/>基于被动 PU 极小化经验正例并减半 Δ_D(V_i)"]
    E --> G{"终止条件判断<br/>u_i - b_i ≤ ε/6 或 Δ_S1(V_i) ≤ ε/3"}
    F --> G
    G -->|未满足| D
    G -->|满足| H["输出强泛化分类器 h_hat (误差 ≤ ε)"]

关键设计¶

1. 先验约束下的假阳性-假阴性转化控制：将无监督正类质量转化为不对称误差上界

在缺乏负类显式标签的 PU 学习中，仅凭正例反馈无法直接限制假设的假阳性率（False Positive Rate）。本文通过在初始阶段抽取未标记样本集 $S$，限制版本空间仅保留在 $S$ 上经验预测正例比例不超过 $\pi_{\mathcal{D}} + \gamma$ 的假设（其中 $\gamma = \varepsilon / (8\theta)$）。由一致收敛界可得，该约束将假设空间严格限制在测度球 $V_0 \subseteq \mathcal{B}_{\mathcal{D}}(\mathbf{0}, \pi_{\mathcal{D}} + 2\gamma)$ 内。由此诱导出关键的误差转化关系：对任意保留的候选假设 $h$，假阳性概率与假阴性概率之差被严格限制在 $2\gamma$ 内：

\[\Pr_{x\sim\mathcal{D}}[\ell(x)=0, h(x)=1] - \Pr_{x\sim\mathcal{D}}[\ell(x)=1, h(x)=0] = \Pr_{x\sim\mathcal{D}}[h(x)=1] - \pi_{\mathcal{D}} \leq 2\gamma\]

这一设计保证了只要利用收集到的正例反馈将假阴性率控制住，假阳性率即可自动被约束，进而将总二分类误差控制在 $\Delta_{\mathcal{D}}(V)/(2\theta)$ 范围以内，彻底消除了缺乏负标签导致的单侧误差爆炸隐患。

2. 分歧区正例密度几何下界：依托分歧系数保障有效反馈查询速率

主动学习效率的核心瓶颈在于分歧区域内有效标签的到达率。若在分歧区 $\text{DIS}(V)$ 中正样本极其稀疏，专家将频繁返回无信息符号 $\star$，导致算法发生停滞。本文给出了关于分歧系数 $\theta$ 的几何引理：若版本空间满足先验紧致包络 $V \subseteq \mathcal{B}(\mathbf{0}, \pi_{\mathcal{D}} + \varepsilon/4)$ 且内部假设最大误差超过 $\varepsilon$，则分歧区域内真实正样本的条件概率具有不依赖于特定分布形状的全局下界：

\[\Pr_{x\sim\mathcal{D}}[\ell(x)=1 \mid x \in \text{DIS}(V)] \geq \frac{1}{4\theta}\]

由于每个正样本被独立检出的概率为 $\omega$，因此在分歧区内执行查询时，正反馈检出率保持在 $\Omega(\omega / \theta)$ 以上。该性质证明了即使在正类被动采样失衡的极端情况下，通过版本空间的几何包络即可倒逼出主动查询的正反馈频率，为每阶段在多项式步内将分歧测度 $\Delta_{\mathcal{D}}(V_t)$ 减半奠定了理论支撑。

3. 未知先验下的二分搜索校准与参数免调估计：自适应跨越双重未知参数

在先验 $\pi_{\mathcal{D}}$ 未知的普遍情形下，算法无法预先剪除过大的假设。本文通过 Algorithm 2（$\text{EstRate}$）与 Algorithm 3 的两级嵌套机制化解这一挑战。$\text{EstRate}$ 程序利用倍增采样和被动 PU 极小化经验正例技术，在纯无标记与弱正例数据中自适应挖掘出所有保留假设一致判定为正的高纯度样本集 $P$，从而以 $O(\frac{\theta(d\ln(\theta/\pi_{\mathcal{D}}) + \ln(1/\delta))}{\pi_{\mathcal{D}}^2 \omega})$ 次标签请求得到满足 $\omega/2 \leq \hat{\omega} \leq 2\omega$ 的检出率估计。

随后，主算法维护正样本经验比例上界 $u_i$ 与一致正例下界 $b_i$。在分歧区采样 $\lambda_1$ 个点后，若正例反馈频率不足 $\frac{\hat{\omega}}{128\theta}$，根据反偶证明必有经验正例率 $\hat{\pi}_{S_1} < \frac{u_i + b_i}{2}$，此时算法安全地将上界折半更新 $u_{i+1} \leftarrow \frac{u_i + b_i}{2}$ 并将版本空间与经验球 $\hat{\mathcal{B}}_{S_1}(\mathbf{0}, u_{i+1})$ 求交；若反馈率充足，则直接运行被动 PU 经验风险极小化将分歧测度 $\Delta_{\mathcal{D}}(V)$ 减半。由于上界折半与分歧减半各自至多发生 $\log_2(6/\varepsilon)$ 次，整个自适应进程无需用户指定 $\pi_{\mathcal{D}}$ 即可严格终止。

实验关键数据¶

主实验¶

本文是一篇纯理论机器学习论文，核心贡献为对主动 PU 学习标签复杂度的数学界证明，建立了在目标误差 $\varepsilon$ 与失败概率 $\delta$ 下的标签请求上界，并与被动 PU 学习及经典监督主动学习（CAL 算法）进行了严格的理论横向对比。

学习范式与算法	先验 $\pi_{\mathcal{D}}$ 要求	标签反馈机制	标签复杂度 (Label Complexity)	相较基线复杂度差距
被动完全监督学习 (Passive SL)	无需先验	完整标注 $(x, y)$	$\Theta\left(\frac{d + \ln(1/\delta)}{\varepsilon}\right)$	基准下界
被动 PU 学习 (Passive PU, Mansouri & Ben-David 2025)	无需先验	随机 SCAR 弱反馈 $(\omega)$	$\Omega\left(\frac{d + \ln(1/\delta)}{\pi_{\mathcal{D}} \varepsilon}\right)$	引入 $\frac{1}{\pi_{\mathcal{D}} \varepsilon}$ 样本量惩罚
监督主动学习 (CAL Algorithm, Hanneke 2009)	无需先验	确定性查询 $(x \to y)$	$O\left(\ln(1/\varepsilon) \theta \left(d\ln(\theta) + \ln\ln(1/\varepsilon) + \ln(1/\delta)\right)\right)$	主动学习标准上界
本文算法 1 (Active PU, 已知 $\pi_{\mathcal{D}}$)	已知严格先验	弱正例查询 $(x \to 1 \text{ 或 } \star)$	$O\left(\frac{\ln(1/\varepsilon) \theta^2 \left(d\ln(\theta) + \ln\ln(1/\varepsilon) + \ln(1/\delta)\right)}{\omega}\right)$	仅较 CAL 多出乘法因子 $\frac{\theta}{\omega}$
本文算法 3 (Active PU, 未知 $\pi_{\mathcal{D}}$)	无需已知先验	弱正例查询 $(x \to 1 \text{ 或 } \star)$	$O\left(\frac{\ln(1/\varepsilon) \theta^2 \left(d\ln\theta + \ln\ln\frac{1}{\varepsilon} + \ln\frac{1}{\delta}\right)}{\omega} + \frac{\theta(d\ln(\theta/\pi_{\mathcal{D}}) + \ln(1/\delta))}{\pi_{\mathcal{D}}^2 \omega}\right)$	第二项与 $\varepsilon$ 解耦，主项保持同阶

消融与理论界成分分析¶

下表对未知先验算法（Algorithm 3）的总标签复杂度各关键子模块所消耗的样本量与查询量进行了渐近解构：

算法子模块 / 阶段	采样类型与目标	核心状态转移条件	理论标签请求量 / 样本复杂度	对总复杂度的渐近贡献
子程序 $\text{EstRate}$	独立倍增未标记池采样	$r \geq 8\ln(8/\delta)$ 终止	$O\left(\frac{\theta(d\ln(\theta/\pi_{\mathcal{D}}) + \ln(1/\delta))}{\pi_{\mathcal{D}}^2 \omega}\right)$	独立于 $\varepsilon$ 的一次性初始化开销
未标记基准池 $S_1$	全局分布 $\mathcal{D}$ 无标记采样	维系经验球与真实测度球包络	$	S_1
分歧区采样探测 $\lambda_1$	针对 $\text{DIS}(V_i)$ 拒绝采样	正反馈检出率评估检验	$\lambda_1 = O\left(\frac{\theta \ln(N/\delta)}{\hat{\omega}}\right)$ (单轮)	每轮检测开销，至多运行 $2\log_2(6/\varepsilon)$ 轮
分歧区版本空间减半 $\lambda_2$	针对 $\text{DIS}(V_i)$ 拒绝采样	检出率充足时执行被动 PU 优化	$\lambda_2 = O\left(\frac{\theta^2 (d\ln\theta + \ln(N/\delta))}{\hat{\omega}}\right)$ (单轮)	分歧测度折半驱动项，至多执行 $\log_2(6/\varepsilon)$ 轮
整体二分搜索框架	交替执行先验收缩与测度减半	$u_i - b_i \leq \frac{\varepsilon}{6}$ 或 $\hat{\Delta}_{S_1}(V_i) \leq \frac{\varepsilon}{3}$	$N = 2\log_2(6/\varepsilon)$ 轮内严格终止	主导项达对数精度依赖 $O(\ln(1/\varepsilon))$

关键发现¶

标签复杂度与精度 $\varepsilon$ 的依赖关系从被动 PU 学习的 $1/\varepsilon$ 骤降至主动学习特有的对数阶 $\ln(1/\varepsilon)$，证明了在 PU 弱反馈下主动查询策略依然具有指数级加速收敛的优越性。
在先验 $\pi_{\mathcal{D}}$ 未知的情况下，先验估计与二分搜索带来的开销项 $\frac{\theta(d\ln(\theta/\pi_{\mathcal{D}}) + \ln(1/\delta))}{\pi_{\mathcal{D}}^2 \omega}$ 完全独立于目标精度 $\varepsilon$。当对高精度分类器（$\varepsilon \to 0$）进行学习时，该项退化为低阶常数项，算法在渐近尺度下达到了与已知先验完全相同的渐近收敛速率。
相比于经典完全监督下的 CAL 算法，主动 PU 学习的标签复杂度仅产生了一个乘法因子 $\frac{\theta}{\omega}$ 的额外代价。其中因子 $1/\omega$ 来源于专家 coin-flip 检出成功率的理论下界，而多出的分歧系数 $\theta$ 则源于分歧区内正样本到达率的几何稀释。

亮点与洞察¶

首次确立了主动 PU 学习的理论可学习性与标签复杂度上界，填补了弱监督主动学习领域长期缺乏有限样本非渐近理论证明的空白。
提出了基于经验正类质量上界约束来反向钳制假阳性率的精妙转化技巧，通过控制测度球的单侧收缩消除了单侧标签反馈中常见的过泛化偏差。
构筑了无需预知正类先验 $\pi_{\mathcal{D}}$ 的自适应二分搜索架构，利用反馈率作为隐式预言机，将参数搜索与版本空间减半无缝耦合，这一设计可直接迁移推广至正类不确定性检测、开集主动识别及伴随随机丢失机制的其他弱监督学习问题中。

局限与展望¶

依赖连续分布假设：现有理论推导建立在分布无原子点（Continuous Distribution，即对任意单个样本测度为零）的假设上。在离散数据分布下，若高概率质量样本在查询中未返回正反馈（返回 $\star$），学习器将陷入无法区分其是负例还是未检出正例的信息盲区。
$\theta^2$ 依赖的紧致性待解：相较于完全监督主动学习的 $\theta$ 线性依赖，本文界中出现了 $\theta^2$ 项。该依赖是由分歧区正样本稀疏度与被动 PU 经验极小化复合产生的，该上界是否为信息论下界、能否进一步消除一个 $\theta$ 仍是一个悬而未决的开放性理论问题。
不可实现（Agnostic）场景外推受限：目前定理均在可实现假定（Realizable Setting，即最优真实分类器严格存在于假设空间 $\mathcal{H}$ 中）下导出，向存在对抗噪声或非线性不可分不可实现场景的泛化推广有待进一步研究。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次给出主动 PU 学习的非渐近标签复杂度理论分析，填补了领域理论空白。
实验充分度: ⭐⭐⭐⭐ 纯理论数学证明工作，引理、定理推导与复杂度解构严密完整，无实证代码仿真。
写作质量: ⭐⭐⭐⭐⭐ 符号系统规范清晰，数学直觉与动机阐释透彻，逻辑脉络层层递进。
价值: ⭐⭐⭐⭐⭐ 为弱监督主动学习、异常检测及推荐冷启动提供了关键的理论基石与算法设计指引。

学习范式与算法	先验 \(\pi_{\mathcal{D}}\) 要求	标签反馈机制	标签复杂度 (Label Complexity)	相较基线复杂度差距
被动完全监督学习 (Passive SL)	无需先验	完整标注 \((x, y)\)	\(\Theta\left(\frac{d + \ln(1/\delta)}{\varepsilon}\right)\)	基准下界
被动 PU 学习 (Passive PU, Mansouri & Ben-David 2025)	无需先验	随机 SCAR 弱反馈 \((\omega)\)	\(\Omega\left(\frac{d + \ln(1/\delta)}{\pi_{\mathcal{D}} \varepsilon}\right)\)	引入 \(\frac{1}{\pi_{\mathcal{D}} \varepsilon}\) 样本量惩罚
监督主动学习 (CAL Algorithm, Hanneke 2009)	无需先验	确定性查询 \((x \to y)\)	\(O\left(\ln(1/\varepsilon) \theta \left(d\ln(\theta) + \ln\ln(1/\varepsilon) + \ln(1/\delta)\right)\right)\)	主动学习标准上界
本文算法 1 (Active PU, 已知 \(\pi_{\mathcal{D}}\))	已知严格先验	弱正例查询 \((x \to 1 \text{ 或 } \star)\)	\(O\left(\frac{\ln(1/\varepsilon) \theta^2 \left(d\ln(\theta) + \ln\ln(1/\varepsilon) + \ln(1/\delta)\right)}{\omega}\right)\)	仅较 CAL 多出乘法因子 \(\frac{\theta}{\omega}\)
本文算法 3 (Active PU, 未知 \(\pi_{\mathcal{D}}\))	无需已知先验	弱正例查询 \((x \to 1 \text{ 或 } \star)\)	\(O\left(\frac{\ln(1/\varepsilon) \theta^2 \left(d\ln\theta + \ln\ln\frac{1}{\varepsilon} + \ln\frac{1}{\delta}\right)}{\omega} + \frac{\theta(d\ln(\theta/\pi_{\mathcal{D}}) + \ln(1/\delta))}{\pi_{\mathcal{D}}^2 \omega}\right)\)	第二项与 \(\varepsilon\) 解耦，主项保持同阶

算法子模块 / 阶段	采样类型与目标	核心状态转移条件	理论标签请求量 / 样本复杂度	对总复杂度的渐近贡献
子程序 \(\text{EstRate}\)	独立倍增未标记池采样	\(r \geq 8\ln(8/\delta)\) 终止	\(O\left(\frac{\theta(d\ln(\theta/\pi_{\mathcal{D}}) + \ln(1/\delta))}{\pi_{\mathcal{D}}^2 \omega}\right)\)	独立于 \(\varepsilon\) 的一次性初始化开销
未标记基准池 \(S_1\)	全局分布 \(\mathcal{D}\) 无标记采样	维系经验球与真实测度球包络	$	S_1
分歧区采样探测 \(\lambda_1\)	针对 \(\text{DIS}(V_i)\) 拒绝采样	正反馈检出率评估检验	\(\lambda_1 = O\left(\frac{\theta \ln(N/\delta)}{\hat{\omega}}\right)\) (单轮)	每轮检测开销，至多运行 \(2\log_2(6/\varepsilon)\) 轮
分歧区版本空间减半 \(\lambda_2\)	针对 \(\text{DIS}(V_i)\) 拒绝采样	检出率充足时执行被动 PU 优化	\(\lambda_2 = O\left(\frac{\theta^2 (d\ln\theta + \ln(N/\delta))}{\hat{\omega}}\right)\) (单轮)	分歧测度折半驱动项，至多执行 \(\log_2(6/\varepsilon)\) 轮
整体二分搜索框架	交替执行先验收缩与测度减半	\(u_i - b_i \leq \frac{\varepsilon}{6}\) 或 \(\hat{\Delta}_{S_1}(V_i) \leq \frac{\varepsilon}{3}\)	\(N = 2\log_2(6/\varepsilon)\) 轮内严格终止	主导项达对数精度依赖 \(O(\ln(1/\varepsilon))\)