
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) | > Paper | |
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 | > Paper | ||
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 | > Paper | ||
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) | > Paper | |
13 | Budgeted Transcript Discovery: A Framework for joint exploration and Validation Studies | Efficiently identifying biomarkers, and verify them | > Paper | ||
14 | The Budgeted Biomarker Discovery Problem | PhD dissertation. Everything about 12, 13 + mor |
See Also
-
Other Work on Active Learning, especially Active Learning Literature Survey (B Settles, Jan 2009)
-
Optimistic Active Learning using Mutual Information (related especially to 1, 2)
-
Learning to Segment from a Few Well-Selected Training Images (related especially to 1, 2)
-
Learning Cost-Sensitive Active Classifiers (related especially to 4, 7)
-
Other results (by Kamesh Munagala, Ashish Goel, Sudipto Guha) especially
-
Asking the right questions: Model-driven optimization using probes, Kamesh Munagala, Ashish Goel and Sudipto Guha, PODS 2006
-
Approximation algorithms for budgeted learning problems, Sudipto Guha, Kamesh Munagala, STOC 2007
-
The Ratio Index for Budgeted Learning, with Applications, Ashish Goel, Sanjeev Khanna, Brad Null, SODA 2009
-




Dan Lizotte, Omid Madani, Russell Greiner
Empirical Results
-
Synthesized data with single discriminative feature in 10 features: p(+f|+c) = .95, p(+f|-c)=.05 (eps)
-
Performance on several UCI data Sets. Relevant information such as class distribution and the discriminative power of each individual feature can be obtained by clicking on the dataset name. Plots of performance are shown for one or more budgets amounting to less than 30 queries on average per feature:
-
-
Budget of 200 (eps)
-
-
-
Budget of 50 (eps)
-
-
-
Budget of 100 (eps)
-
