Near Optimal Bayesian Active Learning for Decision Making

Shervin Javdani, Yuxin Chen, Amin Karbasi, Andreas Krause, Drew Bagnell, Siddhartha Srinivasa
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:430-438, 2014.

Abstract

How should we gather information to make effective decisions? We address Bayesian active learning and experimental design problems, where we sequentially select tests to reduce uncertainty about a set of hypotheses. Instead of minimizing uncertainty per se, we consider a set of overlapping decision regions of these hypotheses. Our goal is to drive uncertainty into a single decision region as quickly as possible. We identify necessary and sufficient conditions for correctly identifying a decision region that contains all hypotheses consistent with observations. We develop a novel Hyperedge Cutting (HEC) algorithm for this problem, and prove that is competitive with the intractable optimal policy. Our efficient implementation of the algorithm relies on computing subsets of the complete homogeneous symmetric polynomials. Finally, we demonstrate its effectiveness on two practical applications: approximate comparison-based learning and active localization using a robot manipulator.

Cite this Paper

BibTeX
@InProceedings{pmlr-v33-javdani14, title = {{Near Optimal Bayesian Active Learning for Decision Making}}, author = {Javdani, Shervin and Chen, Yuxin and Karbasi, Amin and Krause, Andreas and Bagnell, Drew and Srinivasa, Siddhartha}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {430--438}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/javdani14.pdf}, url = {https://proceedings.mlr.press/v33/javdani14.html}, abstract = {How should we gather information to make effective decisions? We address Bayesian active learning and experimental design problems, where we sequentially select tests to reduce uncertainty about a set of hypotheses. Instead of minimizing uncertainty per se, we consider a set of overlapping decision regions of these hypotheses. Our goal is to drive uncertainty into a single decision region as quickly as possible. We identify necessary and sufficient conditions for correctly identifying a decision region that contains all hypotheses consistent with observations. We develop a novel Hyperedge Cutting (HEC) algorithm for this problem, and prove that is competitive with the intractable optimal policy. Our efficient implementation of the algorithm relies on computing subsets of the complete homogeneous symmetric polynomials. Finally, we demonstrate its effectiveness on two practical applications: approximate comparison-based learning and active localization using a robot manipulator.} }
Endnote
%0 Conference Paper %T Near Optimal Bayesian Active Learning for Decision Making %A Shervin Javdani %A Yuxin Chen %A Amin Karbasi %A Andreas Krause %A Drew Bagnell %A Siddhartha Srinivasa %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-javdani14 %I PMLR %P 430--438 %U https://proceedings.mlr.press/v33/javdani14.html %V 33 %X How should we gather information to make effective decisions? We address Bayesian active learning and experimental design problems, where we sequentially select tests to reduce uncertainty about a set of hypotheses. Instead of minimizing uncertainty per se, we consider a set of overlapping decision regions of these hypotheses. Our goal is to drive uncertainty into a single decision region as quickly as possible. We identify necessary and sufficient conditions for correctly identifying a decision region that contains all hypotheses consistent with observations. We develop a novel Hyperedge Cutting (HEC) algorithm for this problem, and prove that is competitive with the intractable optimal policy. Our efficient implementation of the algorithm relies on computing subsets of the complete homogeneous symmetric polynomials. Finally, we demonstrate its effectiveness on two practical applications: approximate comparison-based learning and active localization using a robot manipulator.
RIS
TY - CPAPER TI - Near Optimal Bayesian Active Learning for Decision Making AU - Shervin Javdani AU - Yuxin Chen AU - Amin Karbasi AU - Andreas Krause AU - Drew Bagnell AU - Siddhartha Srinivasa BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-javdani14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 430 EP - 438 L1 - http://proceedings.mlr.press/v33/javdani14.pdf UR - https://proceedings.mlr.press/v33/javdani14.html AB - How should we gather information to make effective decisions? We address Bayesian active learning and experimental design problems, where we sequentially select tests to reduce uncertainty about a set of hypotheses. Instead of minimizing uncertainty per se, we consider a set of overlapping decision regions of these hypotheses. Our goal is to drive uncertainty into a single decision region as quickly as possible. We identify necessary and sufficient conditions for correctly identifying a decision region that contains all hypotheses consistent with observations. We develop a novel Hyperedge Cutting (HEC) algorithm for this problem, and prove that is competitive with the intractable optimal policy. Our efficient implementation of the algorithm relies on computing subsets of the complete homogeneous symmetric polynomials. Finally, we demonstrate its effectiveness on two practical applications: approximate comparison-based learning and active localization using a robot manipulator. ER -
APA
Javdani, S., Chen, Y., Karbasi, A., Krause, A., Bagnell, D. & Srinivasa, S.. (2014). Near Optimal Bayesian Active Learning for Decision Making. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:430-438 Available from https://proceedings.mlr.press/v33/javdani14.html.

Related Material