Budgeted Learning

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.)



  Title Authors Summary Appears In Links
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. VOI 2005
(NIPS Workshop)
Paper
6 Budgeted Learning of Naive Bayes Classifiers Dan Lizotte MSc dissertation
Everything known about 1 and 3.
  Dissertation
7 Learning and Classifying under Hard Budgets Aloak Kapoor MSc dissertation
Everything known about 2 and 4.
  Dissertation
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
Paper
9 Actively Learning Generative Model Liuyang (Spike) Li MSc dissertation
Everything known about 8.
  Dissertation


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 Goal, Sudipto Guha) especially
    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).
    Algorithm Animations



    Budgeted Learning of Naive Bayes Classifiers
          Dan Lizotte, Omid Madani, Russell Greiner
    Full Paper (UAI 2003)
    Empirical Results



    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
    Full Paper (Utility Based Data Mining Workshop, KDD 2005)


    Note: * = copyright Springer-Verlag. Visit the publisher's website here

    Open Problems