主动学习与分歧系数

形式陈述

本页把可实现 PAC 学习放在输入边缘与标签条件分布明确的主动查询协议中；标签数、未标记样本数和计算时间是不同资源。

主动学习假设未标记输入容易获得，标签昂贵。stream-based 协议逐个看到 $X_t\sim P_X$ 后决定是否请求 $Y_t$ ；pool-based 协议先得到一批未标记点，再从池中选择标注。目标以 label complexity 衡量达到风险 $\varepsilon$ 、置信度 $1-\delta$ 所需的标签数，未标记样本数和计算时间仍应另行报告。

本页以可实现二分类为主：存在 $h^*\in H$ 使 $Y=h^*(X)$ 几乎处处。主动学习的基本机会来自候选假设在大部分输入上已经一致；那些点的标签无论是什么都不会区分候选，付费查询没有信息收益。

version space 与分歧区域

给定已标记集合 $L$ ，version space 为

V(L)=\{h\in H:h(x)=y\text{ 对所有 }(x,y)\in L\}.

对任意 $V\subseteq H$ ，定义分歧区域

\operatorname{DIS}(V) =\{x\in X:\exists h,g\in V, h(x)\ne g(x)\}.

在 $x\notin\operatorname{DIS}(V)$ 上，所有仍可能正确的假设给出相同标签，不请求也不会改变 version space。CAL 一类算法只在 $X_t\in\operatorname{DIS}(V)$ 时查询，然后删除与标签不一致的假设。

可实现假设保证 $h^*$ 始终留在 $V$ 中。噪声存在时，单次冲突不再足以删除候选，必须用置信风险集合替代硬一致 version space。

分歧系数

以边缘分布 $P_X$ 定义假设间伪度量

d(h,g)=\Pr_{X\sim P_X}(h(X)\ne g(X)).

围绕目标 $h^*$ 的半径球为

B(h^*,r)=\{h\in H:d(h,h^*)\le r\}.

在基准尺度 $r_0\ge0$ 上，分歧系数定义为

\theta_{h^*}(r_0) =\sup_{r>r_0} \frac{P_X(\operatorname{DIS}(B(h^*,r)))}r.

分子问所有“风险距离至多 $r$ ”的近邻假设总共在哪些输入上仍意见不一。若它只与 $r$ 同阶缩小， $\theta$ 为常数，主动算法会很快把查询区域压缩；若大量近邻的微小分歧散布在互不相同的位置，并集可能覆盖很大区域， $\theta$ 就大。

直觉

主动学习只为仍能改变候选集合的标签付费。version space 越收缩，分歧区域通常越小；分歧系数衡量“候选已经彼此接近”能否真正转化成“需要查询的输入区域也同步缩小”。

主动学习与分歧系数：阈值 version space 收缩图 — 主动学习与分歧系数示意图

例子与边界

阈值分类器例子

令 $H=\{h_a(x)=\mathbf1\{x\ge a\}:a\in\mathbb R\}$ ， $P_X$ 在区间上连续。与目标阈值 $a^*$ 距离至多 $r$ 的阈值，其切点落在 $a^*$ 两侧总概率质量约 $r$ 的邻域内。所有这些阈值的分歧区域也只是该邻域，故分歧系数为常数量级。

算法只需不断查询当前候选阈值夹出的窄区间内的点，标签复杂度可对 $1/\varepsilon$ 呈对数依赖，而被动学习仍需要看到足够多自然落近边界的标记点。这一收益来自有序阈值几何和边缘分布，不是主动选择对所有类都能指数省标签。

一般标签复杂度形状

在可实现条件、VC 维 $d$ 和适当 CAL 分析下，标签复杂度常呈现

\widetilde O\!\left( \theta_{h^*}(\varepsilon) \bigl(d\log(1/\varepsilon)+\log(1/\delta)\bigr) \right),

其中波浪号隐藏额外对数。若 $\theta$ 很小，优于被动的 $O((d+\log(1/\delta))/\varepsilon)$ ；若 $\theta$ 随 $1/\varepsilon$ 增长，优势可能消失。

该式只说明标签数。为了等到足够多落在分歧区域的未标记点，算法可能消费更多未标记样本；如果收集输入也昂贵，就不能把它们视为免费。

失败边界

若假设类能在许多互不相交的小区域各自翻转标签，则每个近邻只与 $h^*$ 在很小区域不同，但这些区域的并集可能覆盖几乎全部输入，分歧系数很大。算法几乎处处都需查询，主动学习退回被动复杂度。小 VC 维也不单独保证小分歧系数，因为后者同时依赖 $P_X$ 和目标位置。

标签噪声、模型错设和选择偏差会改变 version space。硬删除真实目标后无法恢复；实际噪声主动学习使用置信区间、surrogate loss 或 disagreement-based 的软版本，并需要 Massart/Tsybakov 等额外条件。

与其他查询模型的边界

池式/流式主动学习只能查询由 $P_X$ 产生的输入。成员查询允许任意构造 $x$ ，可能访问分布质量为零的点；等价查询还能获得全局反例。三者的 label/query complexity 不应直接比较而不说明 oracle 能力。

主动学习降低的是标注成本，不自动降低总体风险估计偏差。因为训练样本被选择性标注，若要估计自然分布下的风险，需使用独立评估集或校正查询概率。

推论与应用

阈值与低分歧系数类可把标签复杂度对 $1/\varepsilon$ 的依赖从线性降为对数，而未标记样本和计算成本仍需单独核算。噪声条件下，置信 version space 与 Massart/Tsybakov 结构决定这种收益能否保留。

池式筛选、流式触发和成员查询使用不同输入权限。应用到医学标注、内容审核或实验设计时，应先说明系统能否选择任意输入、是否只能从自然流中挑选，以及最终风险如何在原分布上评估。

参考资料

David Cohn, Les Atlas, and Richard Ladner, “Improving Generalization with Active Learning,” Machine Learning, 1994.
Steve Hanneke, “A Bound on the Label Complexity of Agnostic Active Learning,” ICML, 2007.
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni, “A General Agnostic Active Learning Algorithm,” NeurIPS, 2007.

形式陈述 ​

version space 与分歧区域 ​

分歧系数 ​

阈值分类器例子 ​

一般标签复杂度形状 ​

失败边界 ​