Efficient Learning by Directed Acyclic Graph For Resource Constrained Prediction

Abstract

We study the problem of reducing test-time acquisition costs in classification systems. Our goal is to learn decision rules that adaptively select sensors for each example as necessary to make a confident prediction. We model our system as a directed acyclic graph (DAG) where internal nodes correspond to sensor subsets and decision functions at each node choose whether to acquire a new sensor or classify using the available measurements. This problem can be naturally posed as an empirical risk minimization over training data. Rather than jointly optimizing such a highly coupled and non-convex problem over all decision nodes, we propose an efficient algorithm motivated by dynamic programming. We learn node policies in the DAG by reducing the global objective to a series of cost sensitive learning problems. Our approach is computationally efficient and has proven guarantees of convergence to the optimal system for a fixed architecture. In addition, we present an extension to map other budgeted learning problems with large number of sensors to our DAG architecture and demonstrate empirical performance exceeding state-of-the-art algorithms for data composed of both few and many sensors.

To appear in NIPS 2015

References in corpus (3)

• Cost-Sensitive Tree of Classifiers
• The Greedy Miser: Learning under Test-time Budgets
• Fast classification using sparse decision DAGs

Cited by in corpus (11)

• Classification with Costly Features as a Sequential Decision-Making Problem
• Anytime Stereo Image Depth Estimation on Mobile Devices
• Learning Tree-Structured Detection Cascades for Heterogeneous Networks of Embedded Devices
• Online Algorithm for Unsupervised Sequential Selection with Contextual Information
• Optimally Pruning Decision Tree Ensembles With Feature Cost
• Classification with Costly Features in Hierarchical Deep Sets
• Many could be better than all: A novel instance-oriented algorithm for Multi-modal Multi-label problem
• Cost-Sensitive Feature-Value Acquisition Using Feature Relevance
• Field of Groves: An Energy-Efficient Random Forest
• Adaptive Covariate Acquisition for Minimizing Total Cost of Classification
• Sequential Dynamic Decision Making with Deep Neural Nets on a Test-Time Budget