主动学习 K-近邻
- 提出者
- Settles, B. (active learning framework); Fix & Hodges (KNN base)
- 年份
- 1951–2010
- 类型
- Active learning with KNN base learner
- 类别
- Machine learning
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
主动学习 K-近邻(Active Learning K-Nearest Neighbors)结合了 K-近邻(KNN)的实例式预测与一种迭代式查询策略,该策略选择信息量最大的未标记样本进行标注。模型仅请求那些邻域投票边际最窄的实例的标签,从而以远少于全监督 KNN 的标记样本在表格数据上达到具有竞争力的准确率。
方法背后的直觉
KNN 通过查看其 k 个最近的标记邻居并进行多数表决来对一个点进行分类。当这些邻居在类别之间几乎均分时,模型确实存在不确定性——而这种不确定性恰恰指明了哪个未标记的示例最值得标记。主动学习利用了这一信号:在每次迭代中,算法找到邻域划分最均匀的未标记点,请求一个“神谕”(oracle)为其打标签,将其添加到标记池中,然后重复此过程。其结果是,标记工作集中在决策边界附近,新标签在此处能提供最多的信息。
历史学
K-近邻分类器起源于 Fix 和 Hodges (1951) 的工作,并由 Cover 和 Hart (1967) 正式化。主动学习作为一个原则性框架,由 Burr Settles (2010) 系统性地进行了综述,他记录了基于池的不确定性采样、查询委员会和密度加权策略。自 Cohn, Atlas 和 Ladner 的开创性工作 (1994) 以来,KNN 一直是基于池的主动学习基准测试中的基础学习器,因其透明的不确定性信号和每次迭代零重新训练成本而受到重视。
何时使用
当标记数据稀缺或获取成本高昂,未标记实例充足,特征空间维度适中,且预期决策边界局部平滑时,使用主动学习与 KNN。这在标记工作必须配给的分类项目早期阶段尤其实用。避免在数据集维度非常高(KNN 距离度量在高维空间中会退化,即维度灾难)、标记池已很大(被动式 KNN 已足够)、需要大规模低延迟预测(KNN 预测成本随标记集大小线性增长,为 O(n))或标签预算非常小以至于邻域估计不可靠时使用。
局限与注意事项
- 预测成本随标记数据集大小线性增长,导致随着池的增长推理速度变慢。
- 由于维度灾难,基于距离的不确定性在高维空间中急剧退化。
- KNN 的准确率上限低于集成方法;主动策略无法弥补基础学习器的有限容量。
- 对 k 值和距离度量的选择敏感;不好的默认值会导致不可靠的不确定性估计。
- 所有标记点都存储在内存中;大的预算会导致高内存消耗。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 非参数且无假设:不需要对数据进行任何分布假设。
- 不确定性估计自然且可解释——它直接反映了最近邻居之间的投票划分。
- 惰性学习意味着每次迭代没有重新训练成本;扩展后的标记数据集即为更新后的模型。
- 在集中标记靠近决策边界方面效果显著,用少量标注即可获得良好的边界分辨率。
- 在具有连续和二元特征的中等维度表格数据上表现良好。
应用
- 医学记录或图像标注,其中专家标注时间有限且决策边界局部平滑。
- 文本或文档分类,使用基于嵌入的距离,具有少量标记语料库和大量未标记文档。
- 传感器和工业故障检测任务,其中只有一小部分事件可以手动验证。
- 生态调查,其中物种标签的实地确认成本高昂且局部聚集。
- 早期原型分类器,在收集到足够的标签后切换到更高容量的模型。
使用方式
使用方式
首先准备一小部分初始标记实例作为种子,以及一个更大的未标记实例池。建议采用分层随机抽样,以确保每类至少有一个示例,从而在主动学习循环开始之前,为 KNN 提供有意义的初始邻域。
使用选定的 k 值和距离度量(通常是欧几里得距离或余弦距离)在当前的标记数据集上拟合一个 KNN 分类器。由于 KNN 是惰性学习器,它存储所有训练点,拟合过程是瞬时的,但预测成本随标记数据集的大小线性增长——这是一个需要考虑的相关因素,因为池会随着迭代而增长。
对每个未标记实例,根据一个信息量准则进行评分。边际采样(Margin sampling)计算前两个类别在 k 个邻居中的得票率之差;熵采样(Entropy sampling)计算所有类别比例的 H(y-hat | x)。查询具有最小边际或最高熵的实例:x* = argmax H(y-hat | x)。
公式
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)被查询的实例被发送给一个“神谕”(oracle)——人类标注员或自动化标记机制——以获取其真实标签。该标签被添加到训练集中,该实例从标记池中移除。应监控标注员的可靠性,因为有噪声的标签会急剧降低决策边界附近的 KNN 性能。
由于 KNN 是惰性学习器,无需显式重新训练;扩展后的标记数据集立即构成了新模型。查询-评分-标签循环重复进行,直到标记预算耗尽、达到验证准确率阈值或达到最大迭代次数。最终性能在独立的保留测试集上报告。
常见陷阱
- 在计算距离之前未能对特征进行归一化,导致高幅度特征主导邻域。
- 使用测试集来指导或评估查询选择,这构成了数据泄露。
- 在决策边界附近将 k 设置得太小(k=1),会产生高度可变的噪声不确定性分数,不能反映真实的歧义。
- 在种子集中忽略类别不平衡,这会使早期查询偏向于多数类别边界。
- 将主动学习的准确率视为等同于全监督基线,而不报告所使用的标签数量。
常见问题
为什么使用 KNN 而不是更强大的模型作为主动学习基础?
KNN 的投票划分不确定性计算成本低廉且无需重新训练——添加一个新的标记点会立即更新模型。这使得它在每次迭代计算成本很重要的场景下具有吸引力。对于固定的标签预算,为了获得最大准确率,随机森林或梯度提升等集成基础学习器通常优于 KNN。
如何为主动学习选择 k 值?
一个常见的起始范围是 k = 5 到 15。较小的 k 值会产生更嘈杂的不确定性估计;较大的 k 值会平滑边界但可能错过细粒度的歧义。在初始标记种子集上对 k 进行交叉验证,并随着标记池的增长进行调整。
特征缩放是否重要?
是的,至关重要。如果特征未归一化,KNN 距离将由高幅度特征主导。在计算距离和不确定性分数之前,务必应用最小-最大缩放或 z-score 标准化。
需要多少初始标记示例?
最少需要每个类别一个或两个标记实例,以便 KNN 可以为所有类别形成邻域。实际上,5-20 个标记实例可以提供更稳定的初始不确定性估计;更少的实例可能导致退化的邻域,产生信息量不足的早期查询。
何时应停止主动学习循环?
提前设定标记预算,或监控验证准确率,当每个新标签的改进低于有意义的阈值时停止。切勿使用测试集作为停止信号,因为这会将信息泄露到查询过程中。
相关方法
参考文献
Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.
打开出版物文献已复制。Zhu, X., Lafferty, J., & Ghahramani, Z. (2003). Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the ICML 2003 Workshop on the Continuum from Labeled to Unlabeled Data, 58–65.
打开出版物文献已复制。