论文标题
有效的积极学习
Efficient Active Learning with Abstention
论文作者
论文摘要
积极学习的目的是通过被动学习实现相同的准确性，同时使用更少的标签。在非常特殊的情况下，已经证明了标签复杂性的指数节省，但是基本的下限表明，这种改进总体上是不可能的。这表明需要探索积极学习的替代目标。戒除学习就是这样的选择。在这种情况下，主动学习算法可能弃权，并产生比随机猜测略小的错误。我们开发了第一个具有弃权的计算有效的主动学习算法。我们的算法可证明达到$ \ mathsf {polylog}（\ frac {1} {\ varepsilon}）$标签复杂性，而没有任何低噪声条件。相对于不允许弃权的被动学习和主动学习，这种性能保证通过指数因素降低了标签的复杂性。此外，我们的算法只能放弃在硬示例上（真正的标签分布接近公平硬币），这是我们任期\ emph {适当弃权}的新型属性，也可以带来其他许多期望的特征（例如，在标准环境中恢复最小的确保在标准的环境中恢复，并避免了可行的nose noise'noise'''''''''''''''''''''''''''''''''''''''''''noise-````'''我们还提供了实现\ emph {constant}标记复杂性并处理模型错误指定的新型算法扩展。
The goal of active learning is to achieve the same accuracy achievable by passive learning, while using much fewer labels. Exponential savings in terms of label complexity have been proved in very special cases, but fundamental lower bounds show that such improvements are impossible in general. This suggests a need to explore alternative goals for active learning. Learning with abstention is one such alternative. In this setting, the active learning algorithm may abstain from prediction and incur an error that is marginally smaller than random guessing. We develop the first computationally efficient active learning algorithm with abstention. Our algorithm provably achieves $\mathsf{polylog}(\frac{1}{\varepsilon})$ label complexity, without any low noise conditions. Such performance guarantee reduces the label complexity by an exponential factor, relative to passive learning and active learning that is not allowed to abstain. Furthermore, our algorithm is guaranteed to only abstain on hard examples (where the true label distribution is close to a fair coin), a novel property we term \emph{proper abstention} that also leads to a host of other desirable characteristics (e.g., recovering minimax guarantees in the standard setting, and avoiding the undesirable ``noise-seeking'' behavior often seen in active learning). We also provide novel extensions of our algorithm that achieve \emph{constant} label complexity and deal with model misspecification.
