论文标题
通过会员查询学习半空间
Learning Halfspaces With Membership Queries
论文作者
论文摘要
主动学习是机器学习的子场，其中允许学习算法选择其学习的数据。在某些情况下，已经表明，主动学习可以在算法需要看到的样本数量中获得指数增益，以达到概括错误$ \ \leqε$。在这项工作中，我们研究了通过会员查询学习半空间的问题。在会员查询方案中，我们允许学习算法要求输入空间中每个样本的标签。我们为此问题建议了一种新算法，并证明它在某些情况下达到了几乎最佳的标签复杂性。我们还表明，该算法在实践中效果很好，并且明显优于不确定性抽样。
Active learning is a subfield of machine learning, in which the learning algorithm is allowed to choose the data from which it learns. In some cases, it has been shown that active learning can yield an exponential gain in the number of samples the algorithm needs to see, in order to reach generalization error $\leq ε$. In this work we study the problem of learning halfspaces with membership queries. In the membership query scenario, we allow the learning algorithm to ask for the label of every sample in the input space. We suggest a new algorithm for this problem, and prove it achieves a near optimal label complexity in some cases. We also show that the algorithm works well in practice, and significantly outperforms uncertainty sampling.
