ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits

Arghya Roy Chaudhuri, Pratik Jawanpuria, Bamdev Mishra
Proceedings of The 14th Asian Conference on Machine Learning, PMLR 189:169-184, 2023.

Abstract

In this work, we propose a multi-armed bandit based framework for identifying a compact set of informative data instances (i.e., the prototypes) that best represents a given target set. Prototypical examples of a given dataset offer interpretable insights into the underlying data distribution and assist in example-based reasoning, thereby influencing every sphere of human decision making. A key challenge is the large-scale setting, in which similarity comparison between pairs of data points needs to be done for almost all possible pairs. We propose to overcome this limitation by employing stochastic greedy search on the space of prototypical examples and multi-armed bandit approach for reducing the number of similarity comparisons. A salient feature of the proposed approach is that the total number of similarity comparisons needed is independent of the size of the target set. Empirically, we observe that our proposed approach, ProtoBandit, reduces the total number of similarity computation calls by several orders of magnitudes (100-1000 times) while obtaining solutions similar in quality to those from existing state-of-the-art approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v189-chaudhuri23a, title = {{ProtoBandit}: Efficient Prototype Selection via Multi-Armed Bandits}, author = {Chaudhuri, Arghya Roy and Jawanpuria, Pratik and Mishra, Bamdev}, booktitle = {Proceedings of The 14th Asian Conference on Machine Learning}, pages = {169--184}, year = {2023}, editor = {Khan, Emtiyaz and Gonen, Mehmet}, volume = {189}, series = {Proceedings of Machine Learning Research}, month = {12--14 Dec}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v189/chaudhuri23a/chaudhuri23a.pdf}, url = {https://proceedings.mlr.press/v189/chaudhuri23a.html}, abstract = {In this work, we propose a multi-armed bandit based framework for identifying a compact set of informative data instances (i.e., the prototypes) that best represents a given target set. Prototypical examples of a given dataset offer interpretable insights into the underlying data distribution and assist in example-based reasoning, thereby influencing every sphere of human decision making. A key challenge is the large-scale setting, in which similarity comparison between pairs of data points needs to be done for almost all possible pairs. We propose to overcome this limitation by employing stochastic greedy search on the space of prototypical examples and multi-armed bandit approach for reducing the number of similarity comparisons. A salient feature of the proposed approach is that the total number of similarity comparisons needed is independent of the size of the target set. Empirically, we observe that our proposed approach, ProtoBandit, reduces the total number of similarity computation calls by several orders of magnitudes (100-1000 times) while obtaining solutions similar in quality to those from existing state-of-the-art approaches.} }
Endnote
%0 Conference Paper %T ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits %A Arghya Roy Chaudhuri %A Pratik Jawanpuria %A Bamdev Mishra %B Proceedings of The 14th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Emtiyaz Khan %E Mehmet Gonen %F pmlr-v189-chaudhuri23a %I PMLR %P 169--184 %U https://proceedings.mlr.press/v189/chaudhuri23a.html %V 189 %X In this work, we propose a multi-armed bandit based framework for identifying a compact set of informative data instances (i.e., the prototypes) that best represents a given target set. Prototypical examples of a given dataset offer interpretable insights into the underlying data distribution and assist in example-based reasoning, thereby influencing every sphere of human decision making. A key challenge is the large-scale setting, in which similarity comparison between pairs of data points needs to be done for almost all possible pairs. We propose to overcome this limitation by employing stochastic greedy search on the space of prototypical examples and multi-armed bandit approach for reducing the number of similarity comparisons. A salient feature of the proposed approach is that the total number of similarity comparisons needed is independent of the size of the target set. Empirically, we observe that our proposed approach, ProtoBandit, reduces the total number of similarity computation calls by several orders of magnitudes (100-1000 times) while obtaining solutions similar in quality to those from existing state-of-the-art approaches.
APA
Chaudhuri, A.R., Jawanpuria, P. & Mishra, B.. (2023). ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits. Proceedings of The 14th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 189:169-184 Available from https://proceedings.mlr.press/v189/chaudhuri23a.html.

Related Material