Check out the recent ICML'2010 workshop on Budgeted Learning -- see here.
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.)
|1||Active Model Selection||Omid Madani, Dan Lizotte, Russell Greiner||Explores the budgeted multi-armed bandit task.||UAI 2004||Details, or Paper|
|2||Reinforcement Learning for Active Model Selection||Aloak Kapoor, Russell Greiner||Compares RL to heuristic spending policies.||UBDM 2005 (KDD Workshop)||Details, or Paper|
|3||Budgeted Learning of Naive-Bayes Classifiers||Dan Lizotte, Omid Madani, Russell Greiner||Provides effective algorithms for budgeted learning a passive classifier.||UAI 2003||Details, or Paper|
|4||Learning and Classifying under Hard Budgets||Aloak Kapoor, Russell Greiner||Considers budgeted learning a bounded active classifier.||ECML 2005||Details, or Paper*|
|5||Using Value of Information to Learn and Classify under Hard Budgets||Russell Greiner||Short abstract summarizing budgeted learning results, in context of Value-of-Information.||
|6||Budgeted Learning of Naive Bayes Classifiers||Dan Lizotte||MSc dissertation
Everything known about 1 and 3.
|7||Learning and Classifying under Hard Budgets||Aloak Kapoor||MSc dissertation
Everything known about 2 and 4.
|8||Budgeted Distribution Learning in Parametric Models||Liuyang (Spike) Li Barnabas Poczos Csaba Szepesvári, Russell Greiner||Learning the parameters for belief net, to minimize expected KL divergence||ICML 2010
|9||Actively Learning Generative Model||Liuyang (Spike) Li||MSc dissertation
Everything known about 8.
|Active Model Selection|
|Omid Madani, Dan Lizotte, Russell Greiner|
|Short version (in UAI 2004)|
|Longer version (Under revision; includes more explanations, experimental results as well as proofs and derivations in the appendices).|
|Budgeted Learning of Naive Bayes Classifiers|
|Dan Lizotte, Omid Madani, Russell Greiner|
|Full Paper (UAI 2003)|
|Learning and Classifying under Hard Budgets|
|Aloak Kapoor, Russell Greiner|
|Full Paper* (ECML 2005)|
|(Extended version, with Proofs)|
|Foundations: Learning Cost-Sensitive Active Classifiers|
|Reinforcement Learning for Active Model Selection|
|Aloak Kapoor, Russell Greiner|
(Utility Based Data Mining Workshop, KDD 2005)
Note: * = copyright Springer-Verlag. Visit the publisher's website here