论文标题
具有比较查询的可靠，可靠的主动分类
Noise-tolerant, Reliable Active Classification with Comparison Queries
论文作者
论文摘要
在过去的几年中，随着大量，广泛可用的未标记数据的爆炸，找到标签和时间效率，健壮的学习算法在理论和实践中变得越来越重要。我们研究了主动学习的范式，其中具有大量数据池的算法可能会自适应地选择要标记的样品，以期提高效率。通过引入比较（比较两个点）的另一种查询类型，我们提供了第一次和查询有效的算法来学习非均匀的线性分离器对有限（MassArt）噪声的鲁棒性。我们进一步提供了对流行的Tsybakov低噪声条件的概括的算法，并展示了比较如何提供强大的可靠性保证，而可靠性保证通常是不切实际或仅使用标签的不可能的 - 返回分类器，而分类器没有很高的概率错误。
With the explosion of massive, widely available unlabeled data in the past years, finding label and time efficient, robust learning algorithms has become ever more important in theory and in practice. We study the paradigm of active learning, in which algorithms with access to large pools of data may adaptively choose what samples to label in the hope of exponentially increasing efficiency. By introducing comparisons, an additional type of query comparing two points, we provide the first time and query efficient algorithms for learning non-homogeneous linear separators robust to bounded (Massart) noise. We further provide algorithms for a generalization of the popular Tsybakov low noise condition, and show how comparisons provide a strong reliability guarantee that is often impractical or impossible with only labels - returning a classifier that makes no errors with high probability.
