Supervised Sequential Classification Under Budget Constraints
Kirill Trapeznikov, Venkatesh Saligrama · 2013
In this paper we develop a framework for a sequential decision making under budget constraints for multi-class classification. In many classification systems, such as medical diagnosis and homeland security, sequential decisions are often warranted. For each in-stance, a sensor is first chosen for acquir-ing measurements and then based on the available information one decides (rejects) to seek more measurements from a new sen-sor/modality or to terminate by classifying the example based on the available informa-tion. Different sensors have varying costs for acquisition, and these costs account for delay, throughput or monetary value. Con-sequently, we seek methods for maximizing performance of the system subject to bud-get constraints. We formulate a multi-stage multi-class empirical risk objective and learn sequential decision functions from training data. We show that reject decision at each stage can be posed as supervised binary clas-sification. We derive bounds for the VC di-mension of the multi-stage system to quan-tify the generalization error. We compare our approach to alternative strategies on several multi-class real world datasets. 1