The Sample Complexity of Self-Verifying Bayesian Active Learning

Liu Yang, Steve Hanneke, Jaime Carbonell
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:816-822, 2011.

Abstract

We prove that access to a prior distribution over target functions can dramatically improve the sample complexity of self-terminating active learning algorithms, so that it is always better than the known results for prior-dependent passive learning. In particular, this is in stark contrast to the analysis of prior-independent algorithms, where there are simple known learning problems for which no self-terminating algorithm can provide this guarantee for all priors.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-yang11a, title = {The Sample Complexity of Self-Verifying Bayesian Active Learning}, author = {Yang, Liu and Hanneke, Steve and Carbonell, Jaime}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {816--822}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/yang11a/yang11a.pdf}, url = {https://proceedings.mlr.press/v15/yang11a.html}, abstract = {We prove that access to a prior distribution over target functions can dramatically improve the sample complexity of self-terminating active learning algorithms, so that it is always better than the known results for prior-dependent passive learning. In particular, this is in stark contrast to the analysis of prior-independent algorithms, where there are simple known learning problems for which no self-terminating algorithm can provide this guarantee for all priors.} }
Endnote
%0 Conference Paper %T The Sample Complexity of Self-Verifying Bayesian Active Learning %A Liu Yang %A Steve Hanneke %A Jaime Carbonell %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-yang11a %I PMLR %P 816--822 %U https://proceedings.mlr.press/v15/yang11a.html %V 15 %X We prove that access to a prior distribution over target functions can dramatically improve the sample complexity of self-terminating active learning algorithms, so that it is always better than the known results for prior-dependent passive learning. In particular, this is in stark contrast to the analysis of prior-independent algorithms, where there are simple known learning problems for which no self-terminating algorithm can provide this guarantee for all priors.
RIS
TY - CPAPER TI - The Sample Complexity of Self-Verifying Bayesian Active Learning AU - Liu Yang AU - Steve Hanneke AU - Jaime Carbonell BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-yang11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 816 EP - 822 L1 - http://proceedings.mlr.press/v15/yang11a/yang11a.pdf UR - https://proceedings.mlr.press/v15/yang11a.html AB - We prove that access to a prior distribution over target functions can dramatically improve the sample complexity of self-terminating active learning algorithms, so that it is always better than the known results for prior-dependent passive learning. In particular, this is in stark contrast to the analysis of prior-independent algorithms, where there are simple known learning problems for which no self-terminating algorithm can provide this guarantee for all priors. ER -
APA
Yang, L., Hanneke, S. & Carbonell, J.. (2011). The Sample Complexity of Self-Verifying Bayesian Active Learning. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:816-822 Available from https://proceedings.mlr.press/v15/yang11a.html.

Related Material