Timezone: »

Discriminative Metric Learning by Neighborhood Gerrymandering
Shubhendu Trivedi · David Mcallester · Greg Shakhnarovich

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D

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