Not Logged In

Learning and Classifying under Hard Budgets

Full Text: Aloak-MScThesis.pdf PDF

When learning a classifier for a function Y = f(X), the features, X, often have an associated cost. Since resources for feature acquisition are usually finite, learners and classifiers must be able to act intelligently under hard budgets. In this thesis, the goal is a learner that spends its fixed learning budget bL acquiring features of labelled training instances so as to produce the most accurate “active classifier” that spends at most bC per instance. To produce this fixed budget classifier, the fixed budget learner must sequentially decide which feature values to collect to learn the relevant information about the distribution. We explore several approaches the learner can take, ranging from Reinforcement Learning techniques, to the obvious “round robin” strategy that spends equally on all features. We show empirically that round robin is problematic (especially for small bL), and provide alternate learning strategies that achieve superior performance on a variety of datasets.

Citation

A. Kapoor. "Learning and Classifying under Hard Budgets". MSc Thesis, University of Alberta, October 2005.

Keywords: budgeted learning, machine learning, reinforcement learning, hard budget
Category: MSc Thesis

BibTeX

@mastersthesis{Kapoor:05,
  author = {Aloak Kapoor},
  title = {Learning and Classifying under Hard Budgets},
  School = {University of Alberta},
  year = 2005,
}

Last Updated: September 12, 2007
Submitted by Russ Greiner

University of Alberta Logo AICML Logo