Supervised Sequential Classification Under Budget Constraints
Supervised Sequential Classification Under Budget Constraints
复制标题
DOI：
--
复制
发表时间：
2013-04
期刊：
影响因子：
--
通讯作者：
K. Trapeznikov;Venkatesh Saligrama
中科院分区：
文献类型：
--
作者：
K. Trapeznikov;Venkatesh Saligrama
在本文中，我们开发了一个在预算约束下进行多类分类的顺序决策的框架。在许多分类系统中，例如医疗诊断和国土安全，通常需要顺序决策。对于每种情况，首先选择传感器来获取测量结果，然后基于可用信息决定（拒绝）从新传感器/模态寻求更多测量结果，或者通过基于可用信息对示例进行分类来终止。不同的传感器具有不同的采购成本，这些成本涉及延迟、吞吐量或货币价值。因此，我们寻求在预算限制下最大化系统性能的方法。我们制定多阶段多类经验风险目标，并从训练数据中学习顺序决策函数。我们证明每个阶段的拒绝决策都可以被视为有监督的二元分类。我们推导出多级系统 VC 维度的界限来量化泛化误差。我们将我们的方法与几个多类现实世界数据集上的替代策略进行比较。
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 instance, a sensor is first chosen for acquiring measurements and then based on the available information one decides (rejects) to seek more measurements from a new sensor/modality or to terminate by classifying the example based on the available information. Different sensors have varying costs for acquisition, and these costs account for delay, throughput or monetary value. Consequently, we seek methods for maximizing performance of the system subject to budget 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 classification. We derive bounds for the VC dimension of the multi-stage system to quantify the generalization error. We compare our approach to alternative strategies on several multi-class real world datasets.