Adaptive Submodularity with Varying Query Sets: An Application to Active Multi-label Learning

Alan Fern, Robby Goetschalckx, Mandana Hamidi-Haines, Prasad Tadepalli
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:577-592, 2017.

Abstract

Adaptive submodular optimization, where a sequence of items is selected adaptively to optimize a submodular function, has been found to have many applications from sensor placement to active learning. In the current paper, we extend this work to the setting of multiple queries at each time step, where the set of available queries is randomly constrained. A primary contribution of this paper is to prove the first near optimal approximation bound for a greedy policy in this setting. A natural application of this framework is to crowd-sourced active learning problem where the set of available experts and examples might vary randomly. We instantiate the new framework for multi-label learning and evaluate it in multiple benchmark domains with promising results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-fern17a, title = {Adaptive Submodularity with Varying Query Sets: An Application to Active Multi-label Learning}, author = {Fern, Alan and Goetschalckx, Robby and Hamidi-Haines, Mandana and Tadepalli, Prasad}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {577--592}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/fern17a/fern17a.pdf}, url = {https://proceedings.mlr.press/v76/fern17a.html}, abstract = {Adaptive submodular optimization, where a sequence of items is selected adaptively to optimize a submodular function, has been found to have many applications from sensor placement to active learning. In the current paper, we extend this work to the setting of multiple queries at each time step, where the set of available queries is randomly constrained. A primary contribution of this paper is to prove the first near optimal approximation bound for a greedy policy in this setting. A natural application of this framework is to crowd-sourced active learning problem where the set of available experts and examples might vary randomly. We instantiate the new framework for multi-label learning and evaluate it in multiple benchmark domains with promising results.} }
Endnote
%0 Conference Paper %T Adaptive Submodularity with Varying Query Sets: An Application to Active Multi-label Learning %A Alan Fern %A Robby Goetschalckx %A Mandana Hamidi-Haines %A Prasad Tadepalli %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-fern17a %I PMLR %P 577--592 %U https://proceedings.mlr.press/v76/fern17a.html %V 76 %X Adaptive submodular optimization, where a sequence of items is selected adaptively to optimize a submodular function, has been found to have many applications from sensor placement to active learning. In the current paper, we extend this work to the setting of multiple queries at each time step, where the set of available queries is randomly constrained. A primary contribution of this paper is to prove the first near optimal approximation bound for a greedy policy in this setting. A natural application of this framework is to crowd-sourced active learning problem where the set of available experts and examples might vary randomly. We instantiate the new framework for multi-label learning and evaluate it in multiple benchmark domains with promising results.
APA
Fern, A., Goetschalckx, R., Hamidi-Haines, M. & Tadepalli, P.. (2017). Adaptive Submodularity with Varying Query Sets: An Application to Active Multi-label Learning. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 76:577-592 Available from https://proceedings.mlr.press/v76/fern17a.html.

Related Material