We study pool-based active learning of halfspaces, in which a learner receives a pool of unlabeled examples, and iteratively queries a teacher for the labels of examples from the pool, in order to identify all the labels of pool examples. We revisit the idea of greedily selecting examples to label, and use it to derive an efficient algorithm, called ALuMA, that approximates the optimal label complexity for a given pool in $\reals^d$. We show that ALuMA obtains an $O(d^2 \log(d))$ approximation factor if the examples in the pool are numbers with a finite accuracy. We further prove a result for general hypothesis classes, showing that a slight change to the greedy approach leads to an improved target-dependent guarantee on the label complexity. In particular, we conclude a better guarantee for ALuMA if the target hypothesis has a large margin. We further compare our approach to other common active learning strategies, and provide a theoretical and empirical evaluation of the advantages and disadvantages of the approach.

研究池化主动学习半平面问题，重点挖掘了实现的情况下侵略性方法的可行性及其理论保证，证明在合理假设下其具有实用性；理论和实验结果显示此方法比较温和的方法更具优势，可以更好降低标签复杂度，不仅阐述了实现的情况下其近似保证，还说明了相应启发式策略在其他情况下也可以成功使用。

半空间的高效主动学习：一种积极方法