Attribute Measurement Policies for Cost-Effective Classification
Andrew Arnt
Shlomo Zilberstein
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.
Download
[pdf]