Timezone: »

Efficient Learning by Directed Acyclic Graph For Resource Constrained Prediction
Joseph Wang · Kirill Trapeznikov · Venkatesh Saligrama

Thu Dec 10 08:00 AM -- 12:00 PM (PST) @ 210 C #40

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.

Author Information

Joseph Wang (Boston University)
Kirill Trapeznikov (STR)
Venkatesh Saligrama (Boston University)

More from the Same Authors