Near-optimal Adaptive Pool-based Active Learning with General Loss

Nguyen Viet Cuong NUS, Wee Sun Lee NUS, Nan Ye NUS
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:156-165, 2014.

Abstract

We consider adaptive pool-based active learning in a Bayesian setting. We first analyze two commonly used greedy active learning criteria: the maximum entropy criterion, which selects the example with the highest entropy, and the least confidence criterion, which selects the example whose most probable label has the least probability value. We show that unlike the non-adaptive case, the maximum entropy criterion is not able to achieve an approximation that is within a constant factor of optimal policy entropy. For the least confidence criterion, we show that it is able to achieve a constant factor approximation to the optimal version space reduction in a worst-case setting, where the probability of labelings that have not been eliminated is considered as the version space. We consider a third greedy active learning criterion, the Gibbs error criterion, and generalize it to handle arbitrary loss functions between labelings. We analyze the properties of the generalization and its variants, and show that they perform well in practice.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-nus14a, title = {Near-optimal Adaptive Pool-based Active Learning with General Loss}, author = {NUS, Nguyen Viet Cuong and NUS, Wee Sun Lee and NUS, Nan Ye}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {156--165}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/nus14a/nus14a.pdf}, url = {https://proceedings.mlr.press/r12/nus14a.html}, abstract = {We consider adaptive pool-based active learning in a Bayesian setting. We first analyze two commonly used greedy active learning criteria: the maximum entropy criterion, which selects the example with the highest entropy, and the least confidence criterion, which selects the example whose most probable label has the least probability value. We show that unlike the non-adaptive case, the maximum entropy criterion is not able to achieve an approximation that is within a constant factor of optimal policy entropy. For the least confidence criterion, we show that it is able to achieve a constant factor approximation to the optimal version space reduction in a worst-case setting, where the probability of labelings that have not been eliminated is considered as the version space. We consider a third greedy active learning criterion, the Gibbs error criterion, and generalize it to handle arbitrary loss functions between labelings. We analyze the properties of the generalization and its variants, and show that they perform well in practice.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Near-optimal Adaptive Pool-based Active Learning with General Loss %A Nguyen Viet Cuong NUS %A Wee Sun Lee NUS %A Nan Ye NUS %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-nus14a %I PMLR %P 156--165 %U https://proceedings.mlr.press/r12/nus14a.html %V R12 %X We consider adaptive pool-based active learning in a Bayesian setting. We first analyze two commonly used greedy active learning criteria: the maximum entropy criterion, which selects the example with the highest entropy, and the least confidence criterion, which selects the example whose most probable label has the least probability value. We show that unlike the non-adaptive case, the maximum entropy criterion is not able to achieve an approximation that is within a constant factor of optimal policy entropy. For the least confidence criterion, we show that it is able to achieve a constant factor approximation to the optimal version space reduction in a worst-case setting, where the probability of labelings that have not been eliminated is considered as the version space. We consider a third greedy active learning criterion, the Gibbs error criterion, and generalize it to handle arbitrary loss functions between labelings. We analyze the properties of the generalization and its variants, and show that they perform well in practice. %Z Reissued by PMLR on 04 October 2026.
APA
NUS, N.V.C., NUS, W.S.L. & NUS, N.Y.. (2014). Near-optimal Adaptive Pool-based Active Learning with General Loss. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:156-165 Available from https://proceedings.mlr.press/r12/nus14a.html. Reissued by PMLR on 04 October 2026.

Related Material