top of page

Budgeted Learning

Learning tasks typically begin with a data sample --- eg, symptoms and test results for a set of patients, together with their clinical outcomes. By contrast, many real-world studies begin with no actual data, but instead with a budget --- funds that can be used to collect the relevant information. For example, one study has allocated $30 thousand to develop a system to diagnose cancer, based on a battery of patient tests, each with its own (known) costs and (unknown) discriminative powers. Given our goal of identifying the most accurate classifier, what is the best way to spend the $30 thousand? Should we indiscriminately run every test on every patient, until exhausting the budget? Or, should we selectively, and dynamically, determine which tests to run on which patients? We call this task budgeted learning.

​Our initial work on this task studied the theoretical foundations of budgeted learning and proved several important results, such as NP-hardness. Our other work builds upon the theory, and provides algorithms for budgeted learning a passive (Naive Bayes) classifer. Finally, our most recent extensions consider both learning and classifying under a budget, and thus budgeted-learn a bounded active classifier. As budgeted learning is a sequential decision problem, we also provide empirical results which demonstrate that the obvious Reinforcement Learning techniques do not perform particularly well on this high-dimensional and complex task, and are typically bested by our simpler, heuristic policies. A list of all these works and additional experiments is given below. (See also Open Problems.)

​

Update 2021: Short tutorial overviewing "Active Learning": Slides​

Title
Authors
Summary
Appears In
Links
1
Active Model Selection

Explores the budgeted multi-armed bandit task

2
Reinforcement Learning for Active Model Selection

Compares RL to heuristic spending policies

UBDM 2005 (KDD Workshop)

3
Budgeted Learning of Naive-Bayes Classifiers

Provides effective algorithms for budgeted learning a passive classifier

4
Learning and Classifying under Hard Budgets

Considers budgeted learning a bounded active classifier.

5
Using Value of Information to Learn and Classify under Hard Budgets

Short abstract summarizing budgeted learning results, in context of Value-of Info

VOI 2005 (NIPS Workshop)

6
Budgeted Learning of Naive Bayes Classifiers

MSc dissertation

Everything known about 1 and 3

7
Learning and Classifying under Hard Budgets

MSc dissertation

Everything known about 2 and 4

8
Budgeted Distribution Learning in Parametric Models

Learning the parameters for belief net, to minimze expected KL divergence

9
Actively Learning Generative Model

MSc dissertation

Everything known about 8

10
Online Learning with Costly Features and Labels

On-line analysis of how many probes are needed

11
Probe Efficent Learning

MSc dissertation. Everything known about 10.

12
The Budgeted Biomarker Discovery Problem: A Variant of Association Studies

Efficiently identifying biomarkers

MAIHA 2014 (AAAI Workshop)

13
Budgeted Transcript Discovery: A Framework for joint exploration and Validation Studies

Efficiently identifying biomarkers, and verify them

14
The Budgeted Biomarker Discovery Problem

PhD dissertation. Everything about 12, 13 + mor

See Also​

​

Short Version (in  UAI 2004)

​

Algorithm Animations

​​

Dan Lizotte, Omid Madani, Russell Greiner

​

Empirical Results

Anchor 1
bottom of page