Efficient Semi-supervised and Active Learning of Disjunctions

Nina Balcan, Christopher Berlind, Steven Ehrlich, Yingyu Liang
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):633-641, 2013.

Abstract

We provide efficient algorithms for learning disjunctions in the semi-supervised setting under a natural regularity assumption introduced by (Balcan & Blum, 2005). We prove bounds on the sample complexity of our algorithms under a mild restriction on the data distribution. We also give an active learning algorithm with improved sample complexity and extend all our algorithms to the random classification noise setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-balcan13, title = {Efficient Semi-supervised and Active Learning of Disjunctions}, author = {Balcan, Nina and Berlind, Christopher and Ehrlich, Steven and Liang, Yingyu}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {633--641}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/balcan13.pdf}, url = {https://proceedings.mlr.press/v28/balcan13.html}, abstract = {We provide efficient algorithms for learning disjunctions in the semi-supervised setting under a natural regularity assumption introduced by (Balcan & Blum, 2005). We prove bounds on the sample complexity of our algorithms under a mild restriction on the data distribution. We also give an active learning algorithm with improved sample complexity and extend all our algorithms to the random classification noise setting. } }
Endnote
%0 Conference Paper %T Efficient Semi-supervised and Active Learning of Disjunctions %A Nina Balcan %A Christopher Berlind %A Steven Ehrlich %A Yingyu Liang %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-balcan13 %I PMLR %P 633--641 %U https://proceedings.mlr.press/v28/balcan13.html %V 28 %N 1 %X We provide efficient algorithms for learning disjunctions in the semi-supervised setting under a natural regularity assumption introduced by (Balcan & Blum, 2005). We prove bounds on the sample complexity of our algorithms under a mild restriction on the data distribution. We also give an active learning algorithm with improved sample complexity and extend all our algorithms to the random classification noise setting.
RIS
TY - CPAPER TI - Efficient Semi-supervised and Active Learning of Disjunctions AU - Nina Balcan AU - Christopher Berlind AU - Steven Ehrlich AU - Yingyu Liang BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/02/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-balcan13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 1 SP - 633 EP - 641 L1 - http://proceedings.mlr.press/v28/balcan13.pdf UR - https://proceedings.mlr.press/v28/balcan13.html AB - We provide efficient algorithms for learning disjunctions in the semi-supervised setting under a natural regularity assumption introduced by (Balcan & Blum, 2005). We prove bounds on the sample complexity of our algorithms under a mild restriction on the data distribution. We also give an active learning algorithm with improved sample complexity and extend all our algorithms to the random classification noise setting. ER -
APA
Balcan, N., Berlind, C., Ehrlich, S. & Liang, Y.. (2013). Efficient Semi-supervised and Active Learning of Disjunctions. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(1):633-641 Available from https://proceedings.mlr.press/v28/balcan13.html.

Related Material