Not Logged In

Active Model Selection

Full Text: YRL-2004-032.pdf PDF

Classical learning assumes the learner is given a labeled data sample, from which it learns a classifier. The field of Active Learning deals with the situationwhere the learner begins not with a training sample, but instead with resources that it can use to obtain informationto help identify the optimal classifier. 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 ``classifier probes'' (where each probe evaluates the specified classifier on a random ``indistinguishable'' instance) to identify which of a given set of possible classifiershas the highest expected accuracy. Our goal is a policy that sequentially determines which classifier 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, both standard (eg, ``round-robin'', ``Hoeffding Races'') and novel (``biased robin'', ``Gittins''), describing first their approximation properties and then their empirical performance on various problem instances. These results show that many standard algorithms perform much worse than the novel algorithms proposed in this paper.

Citation

O. Madani, D. Lizotte, R. Greiner. "Active Model Selection". Conference on Uncertainty in Artificial Intelligence (UAI), Banff, Alberta, pp 357-365, July 2004.

Keywords: machine learning, budgeted learning, active learning
Category: In Conference

BibTeX

@incollection{Madani+al:UAI04,
  author = {Omid Madani and Dan Lizotte and Russ Greiner},
  title = {Active Model Selection},
  Pages = {357-365},
  booktitle = {Conference on Uncertainty in Artificial Intelligence (UAI)},
  year = 2004,
}

Last Updated: September 26, 2011
Submitted by Russ Greiner

University of Alberta Logo AICML Logo