Learning Policies for Sequential Time and Cost Sensitive Classification
Andrew Arnt
Shlomo Zilberstein
Abstract
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.
Download
[pdf]