Efficient Active Learning of Halfspaces: an Aggressive Approach

Alon Gonen, Sivan Sabato, Shai Shalev-Shwartz
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):480-488, 2013.

Abstract

We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and practical, while also having theoretical guarantees under reasonable assumptions. We further show, both theoretically and experimentally, that it can be preferable to mellow approaches. Our efficient aggressive active learner of half-spaces has formal approximation guarantees that hold when the pool is separable with a margin. While our analysis is focused on the realizable setting, we show that a simple heuristic allows using the same algorithm successfully for pools with low error as well. We further compare the aggressive approach to the mellow approach, and prove that there are cases in which the aggressive approach results in significantly better label complexity compared to the mellow approach. We demonstrate experimentally that substantial improvements in label complexity can be achieved using the aggressive approach, for both realizable and low-error settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-gonen13, title = {Efficient Active Learning of Halfspaces: an Aggressive Approach}, author = {Gonen, Alon and Sabato, Sivan and Shalev-Shwartz, Shai}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {480--488}, 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/gonen13.pdf}, url = {https://proceedings.mlr.press/v28/gonen13.html}, abstract = {We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and practical, while also having theoretical guarantees under reasonable assumptions. We further show, both theoretically and experimentally, that it can be preferable to mellow approaches. Our efficient aggressive active learner of half-spaces has formal approximation guarantees that hold when the pool is separable with a margin. While our analysis is focused on the realizable setting, we show that a simple heuristic allows using the same algorithm successfully for pools with low error as well. We further compare the aggressive approach to the mellow approach, and prove that there are cases in which the aggressive approach results in significantly better label complexity compared to the mellow approach. We demonstrate experimentally that substantial improvements in label complexity can be achieved using the aggressive approach, for both realizable and low-error settings. } }
Endnote
%0 Conference Paper %T Efficient Active Learning of Halfspaces: an Aggressive Approach %A Alon Gonen %A Sivan Sabato %A Shai Shalev-Shwartz %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-gonen13 %I PMLR %P 480--488 %U https://proceedings.mlr.press/v28/gonen13.html %V 28 %N 1 %X We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and practical, while also having theoretical guarantees under reasonable assumptions. We further show, both theoretically and experimentally, that it can be preferable to mellow approaches. Our efficient aggressive active learner of half-spaces has formal approximation guarantees that hold when the pool is separable with a margin. While our analysis is focused on the realizable setting, we show that a simple heuristic allows using the same algorithm successfully for pools with low error as well. We further compare the aggressive approach to the mellow approach, and prove that there are cases in which the aggressive approach results in significantly better label complexity compared to the mellow approach. We demonstrate experimentally that substantial improvements in label complexity can be achieved using the aggressive approach, for both realizable and low-error settings.
RIS
TY - CPAPER TI - Efficient Active Learning of Halfspaces: an Aggressive Approach AU - Alon Gonen AU - Sivan Sabato AU - Shai Shalev-Shwartz BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/02/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-gonen13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 1 SP - 480 EP - 488 L1 - http://proceedings.mlr.press/v28/gonen13.pdf UR - https://proceedings.mlr.press/v28/gonen13.html AB - We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and practical, while also having theoretical guarantees under reasonable assumptions. We further show, both theoretically and experimentally, that it can be preferable to mellow approaches. Our efficient aggressive active learner of half-spaces has formal approximation guarantees that hold when the pool is separable with a margin. While our analysis is focused on the realizable setting, we show that a simple heuristic allows using the same algorithm successfully for pools with low error as well. We further compare the aggressive approach to the mellow approach, and prove that there are cases in which the aggressive approach results in significantly better label complexity compared to the mellow approach. We demonstrate experimentally that substantial improvements in label complexity can be achieved using the aggressive approach, for both realizable and low-error settings. ER -
APA
Gonen, A., Sabato, S. & Shalev-Shwartz, S.. (2013). Efficient Active Learning of Halfspaces: an Aggressive Approach. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(1):480-488 Available from https://proceedings.mlr.press/v28/gonen13.html.

Related Material