We develop an online learning algorithm for identifying unlabeled data points that are most informative for training (i.e., active learning). By formulating the active learning problem as the prediction with sleeping experts problem, we provide a framework for identifying informative data with respect to any given definition of informativeness. At the core of our work is an efficient algorithm for sleeping experts that is tailored to achieve low regret on predictable (easy) instances while remaining resilient to adversarial ones. This stands in contrast to state-of-the-art active learning methods that are overwhelmingly based on greedy selection, and hence cannot ensure good performance across varying problem instances. We present empirical results demonstrating that our method (i) instantiated with an informativeness measure consistently outperforms its greedy counterpart and (ii) reliably outperforms uniform sampling on real-world data sets and models.
翻译:我们开发了一种在线学习算法,用于识别最能为培训(即积极学习)提供信息的未贴标签数据点。 通过将积极学习问题作为睡眠专家问题的预测,我们提供了一个框架,用以识别与任何特定信息性定义有关的信息性数据。我们工作的核心是为睡眠专家设计的高效算法,该算法旨在降低对可预见(容易)案例的遗憾程度,同时保持对对抗性案例的适应性。这与最先进的积极学习方法形成鲜明对比,后者绝大多数以贪婪选择为基础,因此无法确保不同问题实例的良好表现。我们介绍了实证结果,表明我们的方法(一)与信息性衡量一致,始终优于贪婪对应方,以及(二)可靠地优于真实世界数据集和模型的统一抽样。