Two stage decision system

In many classification systems, features have different acquisition costs. It is often unnecessary to acquire every feature to classify a majority of examples. We study a two-stage system, where new features can be acquired at the second stage for an additional cost. We seek decision rules to reduce the average cost of classifying samples but with little performance degradation. We formulate a two-stage empirical risk minimization problem, wherein the first stage either classifies a sample or rejects it to the next stage to acquire a new attribute. We construct a global surrogate risk and develop iterative algorithm in the boosting framework. We test our work on synthetic, medical and explosives detection datasets. Our results demonstrate that substantial cost reduction without a significant sacrifice in accuracy is achievable.