Near Optimal Bayesian Active Learning for Decision Making

Shervin Javdani, Yuxin Chen, Amin Karbasi, Andreas Krause, J. Andrew (Drew) Bagnell, and Siddhartha Srinivasa
tech. report CMU-RI-TR-14-03, Robotics Institute, Carnegie Mellon University, April, 2014


Download
  • Adobe portable document format (pdf) (2MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Notes
Note: Extended version of paper with identical title at the International conference on Artificial Intelligence and Statistics (AISTATS) 2014. Please cite AISTATS version instead.

Text Reference
Shervin Javdani, Yuxin Chen, Amin Karbasi, Andreas Krause, J. Andrew (Drew) Bagnell, and Siddhartha Srinivasa, "Near Optimal Bayesian Active Learning for Decision Making," tech. report CMU-RI-TR-14-03, Robotics Institute, Carnegie Mellon University, April, 2014

BibTeX Reference
@techreport{Javdani_2014_7553,
   author = "Shervin Javdani and Yuxin Chen and Amin Karbasi and Andreas Krause and J. Andrew (Drew) Bagnell and Siddhartha Srinivasa",
   title = "Near Optimal Bayesian Active Learning for Decision Making",
   booktitle = "",
   institution = "Robotics Institute",
   month = "April",
   year = "2014",
   number= "CMU-RI-TR-14-03",
   address= "Pittsburgh, PA",
   Notes = "Extended version of paper with identical title at the International conference on Artificial Intelligence and Statistics (AISTATS) 2014. Please cite AISTATS version instead."
}