Timezone: »
We propose to prune a random forest (RF) for resource-constrained prediction. We first construct a RF and then prune it to optimize expected feature cost & accuracy. We pose pruning RFs as a novel 0-1 integer program with linear constraints that encourages feature re-use. We establish total unimodularity of the constraint set to prove that the corresponding LP relaxation solves the original integer program. We then exploit connections to combinatorial optimization and develop an efficient primal-dual algorithm, scalable to large datasets. In contrast to our bottom-up approach, which benefits from good RF initialization, conventional methods are top-down acquiring features based on their utility value and is generally intractable, requiring heuristics. Empirically, our pruning algorithm outperforms existing state-of-the-art resource-constrained algorithms.
Author Information
Feng Nan (Boston University)
Joseph Wang (Boston University)
Venkatesh Saligrama (Boston University)
More from the Same Authors
-
2021 Spotlight: Online Selective Classification with Limited Feedback »
Aditya Gangrade · Anil Kag · Ashok Cutkosky · Venkatesh Saligrama -
2021 : Surprisingly Simple Semi-Supervised Domain Adaptation with Pretraining and Consistency »
Samarth Mishra · Kate Saenko · Venkatesh Saligrama -
2021 Poster: Online Selective Classification with Limited Feedback »
Aditya Gangrade · Anil Kag · Ashok Cutkosky · Venkatesh Saligrama -
2021 Poster: Bandit Quickest Changepoint Detection »
Aditya Gopalan · Braghadeesh Lakshminarayanan · Venkatesh Saligrama -
2020 Poster: Learning to Approximate a Bregman Divergence »
Ali Siahkamari · XIDE XIA · Venkatesh Saligrama · David Castañón · Brian Kulis -
2020 Poster: Online Algorithm for Unsupervised Sequential Selection with Contextual Information »
Arun Verma · Manjesh Kumar Hanawal · Csaba Szepesvari · Venkatesh Saligrama -
2020 Poster: Limits on Testing Structural Changes in Ising Models »
Aditya Gangrade · Bobak Nazer · Venkatesh Saligrama -
2019 Poster: Efficient Near-Optimal Testing of Community Changes in Balanced Stochastic Block Models »
Aditya Gangrade · Praveen Venkatesh · Bobak Nazer · Venkatesh Saligrama -
2019 Poster: Shallow RNN: Accurate Time-series Classification on Resource Constrained Devices »
Don Dennis · Durmus Alp Emre Acar · Vikram Mandikal · Vinu Sankar Sadasivan · Venkatesh Saligrama · Harsha Vardhan Simhadri · Prateek Jain -
2017 Poster: Adaptive Classification for Prediction Under a Budget »
Feng Nan · Venkatesh Saligrama -
2016 Poster: Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings »
Tolga Bolukbasi · Kai-Wei Chang · James Y Zou · Venkatesh Saligrama · Adam T Kalai -
2015 Poster: Efficient Learning by Directed Acyclic Graph For Resource Constrained Prediction »
Joseph Wang · Kirill Trapeznikov · Venkatesh Saligrama -
2014 Poster: Efficient Minimax Signal Detection on Graphs »
Jing Qian · Venkatesh Saligrama -
2012 Poster: Local Supervised Learning through Space Partitioning »
Joseph Wang · Venkatesh Saligrama -
2010 Poster: Probabilistic Belief Revision with Structural Constraints »
Peter B Jones · Venkatesh Saligrama · Sanjoy K Mitter -
2009 Poster: Anomaly Detection with Score functions based on Nearest Neighbor Graphs »
Manqi Zhao · Venkatesh Saligrama -
2009 Spotlight: Anomaly Detection with Score functions based on Nearest Neighbor Graphs »
Manqi Zhao · Venkatesh Saligrama