Attribute Measurement Policies for Cost-Effective Classification

Andrew Arnt and Shlomo Zilberstein. Attribute Measurement Policies for Cost-Effective Classification. Proceedings of the SIAM/SDM Workshop on Data Mining in Resource Constrained Environments, Lake Buena Vista, Florida, 2004.

Abstract

Many systems with machine learning classifiers as components require the ability to function in realtime, online settings. Such systems must be able to quickly classify instances so as to minimize a variety of costs. We identify three components of cost that must be considered: penalties incurred due to the misclassification of an instance, costs incurred when measuring an attribute of the instance, and a utility cost related to the time elapsed while measuring attributes. We show how to model this problem as a Markov Decision Process (MDP), and then use AO* heuristic search to build a policy given a set of labeled training data. Additionally, we discuss how to modify this system to cope with a stream of instances arriving over time, where time taken to measure attributes in the current instance can influence time-sensitive costs of waiting instances.

Bibtex entry:

@inproceedings{AZsdm04,
  author	= {Andrew Arnt and Shlomo Zilberstein},
  title		= {Attribute Measurement Policies for Cost-Effective Classification},
  booktitle     = {Proceedings of the {SIAM/SDM} Workshop on Data Mining in Resource
                   Constrained Environments},
  year		= {2004},
  pages		= {},
  address       = {Lake Buena Vista, Florida},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/AZsdm04.html}
}

shlomo@cs.umass.edu