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 com- monly 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 probabil- ity value. We show that unlike the non-adaptive case, the maximum entropy criterion is not able to achieve an approximation that is within a con- stant 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 ver- sion space. We consider a third greedy active learning criterion, the Gibbs error criterion, and generalize it to handle arbitrary loss functions be- tween 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 com- monly 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 probabil- ity value. We show that unlike the non-adaptive case, the maximum entropy criterion is not able to achieve an approximation that is within a con- stant 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 ver- sion space. We consider a third greedy active learning criterion, the Gibbs error criterion, and generalize it to handle arbitrary loss functions be- tween 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 com- monly 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 probabil- ity value. We show that unlike the non-adaptive case, the maximum entropy criterion is not able to achieve an approximation that is within a con- stant 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 ver- sion space. We consider a third greedy active learning criterion, the Gibbs error criterion, and generalize it to handle arbitrary loss functions be- tween 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