page_title: Large margin nearest neighbor
section_title: Setup
hierarchical_section_title: Large margin nearest neighbor / Setup
caption_attribution_description: English: Schematic illustration of large margin nearest neighbor.
context_page_description: Large margin nearest neighbor classification is a statistical machine learning algorithm for metric learning. It learns a pseudometric designed for k-nearest neighbor classification. The algorithm is based on semidefinite programming, a sub-class of convex optimization.
  The goal of supervised learning is to learn a decision rule that can categorize data instances into pre-defined classes. The k-nearest neighbor rule assumes a training data set of labeled instances. It classifies a new data instance with the class obtained from the majority vote of the k closest training instances. Closeness is measured with a pre-defined metric. Large margin nearest neighbors is an algorithm that learns this global metric in a supervised fashion to improve the classification accuracy of the k-nearest neighbor rule.
context_section_description: The main intuition behind LMNN is to learn a pseudometric under which all data instances in the training set are surrounded by at least k instances that share the same class label. If this is achieved, the leave-one-out error (a special case of cross validation) is minimized. Let the training data consist of a data set , where the set of possible class categories is .
  The algorithm learns a pseudometric of the type 
  .
  For  to be well defined, the matrix  needs to be positive semi-definite. The Euclidean metric is a special case, where   is the identity matrix. This generalization is often (falsely) referred  to as Mahalanobis metric.
  Figure 1 illustrates the effect of the metric under varying . The two circles show the set of points with equal distance to the center . In the Euclidean case this set is a circle, whereas under the modified (Mahalanobis) metric it becomes an ellipsoid.
  The algorithm distinguishes between two types of special data points: target neighbors and impostors.
caption: Figure 1: Schematic illustration of LMNN.
exif: {}