Economical Active Feature-Value Acquisition through Expected Utility Estimation

In many classification tasks training data have missing feature values that can be acquired at a cost.  For building accurate predictive models, acquiring all missing values is often prohibitively expensive or unnecessary, while acquiring a random subset of feature values may not be most effective.  The goal of active feature-value acquisition is to incrementally select feature values that are most cost-effective for improving the model’s accuracy.  We present two policies, Sampled Expected Utility and Expected Utility-ES, that acquire feature values for inducing a classification model based on an estimation of the expected improvement in model accuracy per unit cost.  A comparison of the two policies to each other and to alternative policies demonstrate that Sampled Expected Utility is preferable as it effectively reduces the cost of producing a model of a desired accuracy and exhibits a consistent performance across domains.