Learning Policies for Sequential Time and Cost Sensitive Classification

Andrew Arnt and Shlomo Zilberstein. Learning Policies for Sequential Time and Cost Sensitive Classification. Proceedings of the KDD Workshop on Utility-Based Data Mining, Chicago, Illinois, 2005.


In time and cost sensitive classification, the value of a labeled instance depends not only on the correctness of the labeling, but also the timeliness with which the instance is labeled. Instance attributes are initially unknown, and may take significant time to measure. This results in a difficult problem, trying to manage the tradeoff between time and accuracy. The problem is further complicated when we consider the classification of a sequence of time-sensitive classification tasks, where time spent measuring attributes in one instance can adversely effect the costs of future instances. We solve these problems using a decision theoretic approach. The problem is modeled as an MDP with a potentially very large state space. We discuss how to intelligently discretize time and approximate the effects of measurement actions in the current task given all waiting tasks. The results offer an effective approach to attribute measurement and classification for a variety of time sensitive applications.

Bibtex entry:

  author	= {Andrew Arnt and Shlomo Zilberstein},
  title		= {Learning Policies for Sequential Time and Cost Sensitive
  booktitle     = {Proceedings of the {KDD} Workshop on Utility-Based Data Mining},
  year		= {2005},
  pages		= {},
  address       = {Chicago, Illinois},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/AZubdm05.html}

UMass Amherst