THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Talk
ProtoNN: Compressed and Accurate kNN for Resource-scarce Devices
Chirag Gupta · ARUN SUGGALA · Ankit Goyal · Saurabh Goyal · Ashish Kumar · Bhargavi Paranjape · Harsha Vardhan Simhadri · Raghavendra Udupa · Manik Varma · Prateek Jain

Mon Aug 07 11:24 PM -- 11:42 PM (PDT) @ C4.6 & C4.7
in Metric learning »

Several real-world applications require real-time prediction on resource-scarce devices such as an Internet of Things (IoT) sensor. Such applications demand prediction models with small storage and computational complexity that do not compromise significantly on accuracy. In this work, we propose ProtoNN, a novel algorithm that addresses the problem of real-time and accurate prediction on resource-scarce devices. ProtoNN is inspired by k-Nearest Neighbor (KNN) but has several orders lower storage and prediction complexity. ProtoNN models can be deployed even on devices with puny storage and computational power (e.g. an Arduino UNO with 2kB RAM) to get excellent prediction accuracy. ProtoNN derives its strength from three key ideas: a) learning a small number of prototypes to represent the entire training set, b) sparse low dimensional projection of data, c) joint discriminative learning of the projection and prototypes with explicit model size constraint. We conduct systematic empirical evaluation of ProtoNN on a variety of supervised learning tasks (binary, multi-class, multi-label classification) and show that it gives nearly state-of-the-art prediction accuracy on resource-scarce devices while consuming several orders lower storage, and using minimal working memory.

[ PDF]  [ ss Summary/Notes]  [ Video] 

Author Information

Chirag Gupta (Microsoft Research, India)
ARUN SUGGALA (Carnegie Mellon University)
Ankit Goyal (University of Michigan)
Saurabh Goyal (IBM India Pvt Ltd)
Ashish Kumar (Microsoft Research)
Bhargavi Paranjape (Microsoft Research)
Harsha Vardhan Simhadri (Microsoft Research)
Raghavendra Udupa (Microsoft Research)
Manik Varma (Microsoft Research)
Prateek Jain (Microsoft Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors