Timezone: »
We formulate the problem of metric learning for k nearest neighbor classification as a large margin structured prediction problem, with a latent variable representing the choice of neighbors and the task loss directly corresponding to classification error. We describe an efficient algorithm for exact loss augmented inference,and a fast gradient descent algorithm for learning in this model. The objective drives the metric to establish neighborhood boundaries that benefit the true class labels for the training points. Our approach, reminiscent of gerrymandering (redrawing of political boundaries to provide advantage to certain parties), is more direct in its handling of optimizing classification accuracy than those previously proposed. In experiments on a variety of data sets our method is shown to achieve excellent results compared to current state of the art in metric learning.
Author Information
Shubhendu Trivedi (MIT)
David Mcallester (Toyota Tech Institute Chicago)
Greg Shakhnarovich (TTI-Chicago)
More from the Same Authors
-
2017 Poster: Exploring Generalization in Deep Learning »
Behnam Neyshabur · Srinadh Bhojanapalli · David Mcallester · Nati Srebro -
2016 Poster: Depth from a Single Image by Harmonizing Overcomplete Local Network Predictions »
Ayan Chakrabarti · Jingyu Shao · Greg Shakhnarovich -
2013 Workshop: Deep Learning »
Yoshua Bengio · Hugo Larochelle · Russ Salakhutdinov · Tomas Mikolov · Matthew D Zeiler · David Mcallester · Nando de Freitas · Josh Tenenbaum · Jian Zhou · Volodymyr Mnih -
2011 Workshop: Beyond Mahalanobis: Supervised Large-Scale Learning of Similarity »
Greg Shakhnarovich · Dhruv Batra · Brian Kulis · Kilian Q Weinberger -
2011 Poster: Object Detection with Grammar Models »
Ross B Girshick · Pedro Felzenszwalb · David Mcallester -
2011 Spotlight: Object Detection with Grammar Models »
Ross B Girshick · Pedro Felzenszwalb · David Mcallester -
2011 Poster: Generalization Bounds and Consistency for Latent Structural Probit and Ramp Loss »
David Mcallester · Joseph Keshet -
2011 Oral: Generalization Bounds and Consistency for Latent Structural Probit and Ramp Loss »
David Mcallester · Joseph Keshet -
2010 Poster: Sparse Coding for Learning Interpretable Spatio-Temporal Primitives »
Taehwan Kim · Greg Shakhnarovich · Raquel Urtasun