主动学习与分歧系数

标签是稀缺资源 ​

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

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

version space 与分歧区域 ​

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

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

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

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

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

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

分歧系数 ​

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

$$d(h,g)={\text{Pr}}_{X\sim P_X}(h(X)\ne g(X)).$$

围绕目标 $h^{\ast }$ 的半径球为

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

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

$${\theta }_{h^{\ast }}(r_0)=\underset{r>r_0}{sup}\frac{P_X(\mathrm{DIS}(B(h^{\ast },r)))}{r}.$$

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

阈值分类器例子 ​

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

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

一般标签复杂度形状 ​

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

$$\tilde{O}({\theta }_{h^{\ast }}(\epsilon )(d\log \left(1/\epsilon \right)+\log \left(1/\delta \right))),$$

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

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

失败边界 ​

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

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

与其他查询模型的边界 ​

池式/流式主动学习只能查询由 $P_X$ 产生的输入。成员查询公理库成员与等价查询学习Membership query learning · Equivalence query learning · Exact learning from queries在可主动询问目标概念标签并提交完整候选接受反例的协议中，以查询数和计算时间衡量精确概念识别。允许任意构造 $x$，可能访问分布质量为零的点；等价查询还能获得全局反例。三者的 label/query complexity 不应直接比较而不说明 oracle 能力。

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

参考资料

• 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.