Robust Interactive Learning

Maria Florina Balcan, Steve Hanneke
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:20.1-20.34, 2012.

Abstract

In this paper we propose and study a generalization of the standard active-learning model where a more general type of queries including class conditional queries and mistake queries are allowed. Such queries have been quite useful in applications, but have been lacking theoretical understanding. In this work, we characterize the power of such queries under several well-known noise models. We give nearly tight upper and lower bounds on the number of queries needed to learn both for the general agnostic setting and for the bounded noise model. We further show that our methods can be made adaptive to the (unknown) noise rate, with only negligible loss in query complexity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-balcan12c, title = {Robust Interactive Learning}, author = {Balcan, Maria Florina and Hanneke, Steve}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {20.1--20.34}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/balcan12c/balcan12c.pdf}, url = {https://proceedings.mlr.press/v23/balcan12c.html}, abstract = {In this paper we propose and study a generalization of the standard active-learning model where a more general type of queries including class conditional queries and mistake queries are allowed. Such queries have been quite useful in applications, but have been lacking theoretical understanding. In this work, we characterize the power of such queries under several well-known noise models. We give nearly tight upper and lower bounds on the number of queries needed to learn both for the general agnostic setting and for the bounded noise model. We further show that our methods can be made adaptive to the (unknown) noise rate, with only negligible loss in query complexity.} }
Endnote
%0 Conference Paper %T Robust Interactive Learning %A Maria Florina Balcan %A Steve Hanneke %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-balcan12c %I PMLR %P 20.1--20.34 %U https://proceedings.mlr.press/v23/balcan12c.html %V 23 %X In this paper we propose and study a generalization of the standard active-learning model where a more general type of queries including class conditional queries and mistake queries are allowed. Such queries have been quite useful in applications, but have been lacking theoretical understanding. In this work, we characterize the power of such queries under several well-known noise models. We give nearly tight upper and lower bounds on the number of queries needed to learn both for the general agnostic setting and for the bounded noise model. We further show that our methods can be made adaptive to the (unknown) noise rate, with only negligible loss in query complexity.
RIS
TY - CPAPER TI - Robust Interactive Learning AU - Maria Florina Balcan AU - Steve Hanneke BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-balcan12c PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 20.1 EP - 20.34 L1 - http://proceedings.mlr.press/v23/balcan12c/balcan12c.pdf UR - https://proceedings.mlr.press/v23/balcan12c.html AB - In this paper we propose and study a generalization of the standard active-learning model where a more general type of queries including class conditional queries and mistake queries are allowed. Such queries have been quite useful in applications, but have been lacking theoretical understanding. In this work, we characterize the power of such queries under several well-known noise models. We give nearly tight upper and lower bounds on the number of queries needed to learn both for the general agnostic setting and for the bounded noise model. We further show that our methods can be made adaptive to the (unknown) noise rate, with only negligible loss in query complexity. ER -
APA
Balcan, M.F. & Hanneke, S.. (2012). Robust Interactive Learning. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:20.1-20.34 Available from https://proceedings.mlr.press/v23/balcan12c.html.

Related Material