Active Model Selection
By Omid Madani, Daniel J. Lizotte, R. Greiner. 2004
79 citations recorded by the source corpus.
Classical learning assumes the learner is given a labeled data sample, from which it learns a model. The field of Active Learning deals with the situation where the learner begins not with a training sample, but instead with resources that it can use to obtain information to help identify the optimal model. To better understand this task, this paper presents and analyses the simplified "(budgeted) active model selection" version, which captures the pure exploration aspect of many active learning problems in a clean and simple problem formulation. Here the learner can use a fixed budget of "model probes" (where each probe evaluates the specified model on a random indistinguishable instance) to identify which of a given set of possible models has the highest expected accuracy. Our goal is a policy that sequentially determines which model to probe next, based on the information observed so far. We present a formal description of this task, and show that it is NP-hard in general. We then investigate a number of algorithms for this task, including several existing ones (eg, "Round-Robin", "Interval Estimation", "Gittins") as well as some novel ones (e.g., "Biased-Robin"), describing first their approximation properties and then their empirical performance on various problem instances. We observe empirically that the simple biased-robin algorithm significantly outperforms the other algorithms in the case of identical costs and priors.
Subfields: Artificial Intelligence, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Frank Hutter
- Nando de Freitas
- Ziyun Wang
- Kevin Swersky
- Sergey Levine
- Bobak Shahriari
- Ryan P. Adams
- Quoc V. Le
In Management Science and Operations Research
- Ziyun Wang
- Frank Hutter
- Bobak Shahriari
- Kevin Swersky
- Ryan P. Adams
- Nando de Freitas
- R. Greiner
- Susan A. Murphy
Citations in the corpus
- Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “arm identification problem, which is more suitable for the model selection task [7], [30], [50], [51], [72], [104].”
- Budgeted Learning for Developing Personalized Treatment (2014, background): “A budgeted version of the Bernoulli bandit problem was studied in [11], in which the goal is to minimize the difference between the success probability of the chosen arm and that of the best arm.”