Distance Metric Learning for Large Margin Nearest Neighbor Classification

摘要

The accuracy of k-nearest neighbor (kNN) classification dependssignificantly on the metric used to compute distances betweendifferent examples. In this paper, we show how to learn a Mahalanobisdistance metric for kNN classification from labeled examples. TheMahalanobis metric can equivalently be viewed as a global lineartransformation of the input space that precedes kNN classificationusing Euclidean distances. In our approach, the metric is trainedwith the goal that the k-nearest neighbors always belong to the sameclass while examples from different classes are separated by a largemargin. As in support vector machines (SVMs), the margin criterionleads to a convex optimization based on the hinge loss. Unlikelearning in SVMs, however, our approach requires no modification orextension for problems in multiway (as opposed to binary)classification. In our framework, the Mahalanobis distance metric isobtained as the solution to a semidefinite program. On several datasets of varying size and difficulty, we find that metrics trained inthis way lead to significant improvements in kNN classification.Sometimes these results can be further improved by clustering thetraining examples and learning an individual metric within eachcluster. We show how to learn and combine these local metrics in aglobally integrated manner. color="gray">