用信息论视角重新理解主动学习的标签效率极限。
Pool-based Active Learning as Noisy Lossy Compression: Characterizing Label Complexity via Finite Blocklength Analysis
- 将主动学习视为有噪有损压缩问题，统一分析数据选择与学习过程。
- 推导出标签复杂度和泛化误差的理论下界，揭示算法过拟合与偏差影响。
- 为研究主动学习提供全新理论框架，适合关注理论深度的研究者。
本文提出一种信息论框架，用于分析池基主动学习（pool-based active learning, AL）的理论极限。该框架将池基AL重构为有噪有损压缩问题：将池中观测映射为有噪符号观测，数据选择对应压缩过程，学习对应解码过程。这一对应关系使得数据选择与学习可统一进行信息论分析。通过应用有噪有损压缩的有限块长分析，本文推导出标签复杂度和泛化误差的信息论下界，这些下界刻画了在最优数据选择策略下的给定学习算法的理论极限。具体而言，这些下界包含反映学习算法过拟合及归纳偏置与目标任务不一致所导致偏差的项，且与已有信息论界和稳定性理论密切相关，此前未被用于池基AL分析。这些特性为池基主动学习提供了新的理论视角。
原文摘要 · Abstract (English)
This paper proposes an information-theoretic framework for analyzing the theoretical limits of pool-based active learning (AL), in which a subset of instances is selectively labeled. The proposed framework reformulates pool-based AL as a noisy lossy compression problem by mapping pool observations to noisy symbol observations, data selection to compression, and learning to decoding. This correspondence enables a unified information-theoretic analysis of data selection and learning in pool-based AL. Applying finite blocklength analysis of noisy lossy compression, we derive information-theoretic lower bounds on label complexity and generalization error that serve as theoretical limits for a given learning algorithm under its associated optimal data selection strategy. Specifically, our bounds include terms that reflect overfitting induced by the learning algorithm and the discrepancy between its inductive bias and the target task, and are closely related to established information-theoretic bounds and stability theory, which have not been previously applied to the analysis of pool-based AL. These properties yield a new theoretical perspective on pool-based AL.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。