Timezone: »
We develop a novel approach for supervised learning based on adaptively partitioning the feature space into different regions and learning local region-specific classifiers. We formulate an empirical risk minimization problem that incorporates both partitioning and classification in to a single global objective. We show that space partitioning can be equivalently reformulated as a supervised learning problem and consequently any discriminative learning method can be utilized in conjunction with our approach. Nevertheless, we consider locally linear schemes by learning linear partitions and linear region classifiers. Locally linear schemes can not only approximate complex decision boundaries and ensure low training error but also provide tight control on over-fitting and generalization error. We train locally linear classifiers by using LDA, logistic regression and perceptrons, and so our scheme is scalable to large data sizes and high-dimensions. We present experimental results demonstrating improved performance over state of the art classification techniques on benchmark datasets. We also show improved robustness to label noise.
Author Information
Joseph Wang (Amazon Alexa)
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: Pruning Random Forests for Prediction on a Budget »
Feng Nan · Joseph Wang · 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 -
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