Home / Curated / Algorithms / Large margin nearest neighbor

Large margin nearest neighbor

Algorithms AIMech:LargeMarginNearestNeighbor DRAFT

Aliases: LMNN, Large-margin nearest-neighbor classification, Large margin nearest neighbour

A supervised metric-learning method that fits a positive-semidefinite distance matrix by pulling fixed same-class target neighbors together while penalizing margin violations by differently labeled observations.

Identity Notes & Concept Scope The core single-metric LMNN formulation fixes directed target-neighbor assignments before fitting and uses a convex objective in a positive-semidefinite matrix. It is not NCA’s stochastic classification objective, a generic triplet loss, or a deep embedding network. Iteratively reassigning targets, learning local metrics, kernelization and rank constraints are distinct extensions; their behavior is not inferred from the core convex program. The energy-based prediction rule in Section 3.5 is separate from ordinary k-nearest-neighbor voting. No normalized identity match for this candidate was found across all 442 pinned AIO labels/scoped synonyms and 227 preceding native IDs/names/aliases. The same search identified BIRCH as an existing native record and excluded it from additions. Full-checkout word-delimited fixed-string searches included ignored and hidden files, with 79 worktree and 79 main-checkout matching lines; these concern BIRCH identity/proposal/review context and discovery leads. Ten exact AIO CLASS nodes with scoped synonyms and outgoing edges, and nine neighboring native records, were inspected.

Claims & Grounded Evidence

2 Claims

Mechanism #method

For labeled vectors choose k other same-class target neighbors T_i for each training point, usually using Euclidean distance before fitting; these directed sets remain fixed in the core method. Let d_M(i,j)=(x_i-x_j)^T M(x_i-x_j), with M positive semidefinite. Minimize (1-mu)sum_i sum_(j in T_i)d_M(i,j)+mu sum_i sum_(j in T_i)sum_(l:y_l!=y_i)max(0,1+d_M(i,j)-d_M(i,l)), with mu in [0,1]. The pull term concerns target neighbors, not all same-class pairs, and the hinge is not squared. Introducing nonnegative slack variables for the margin violations yields a semidefinite program. After learning, factor M=L^T L and use the learned distances for k-nearest-neighbor classification. The matrix-variable objective is convex for fixed target sets; optimizing directly in L is not generally convex.

supports Source: Distance Metric Learning for Large Margin Nearest Neighbor Classification · Locator: Section 2.1, PDF pp. 3–4 (printed 209–210), squared-distance parameterization; Sections 3.1–3.4, PDF pp. 9–15 (printed 215–221), Equations (10)–(14) and boxed semidefinite program; Section 3.5 for prediction-rule distinction

Limitation #source-convention-check

Curator calculation: for one-dimensional points 0,1,2 and M=1, d_M(0,2)=4 exceeds d_M(0,1)+d_M(1,2)=2. The squared expression used for training therefore need not satisfy a metric triangle inequality. The exact calculation is saved in research/discovery/metric-source-boundaries.py.

supports Source: Distance Metric Learning for Large Margin Nearest Neighbor Classification · Locator: Section 2.1, PDF pp. 3–4, Equations (1)–(3) define the squared distances evaluated by the curator; the surrounding metric terminology is qualified.

⚠️ Curated Limitations & Negative Results

Each point needs enough other same-class observations for its chosen target count. Target selection, labels, weighting, feature scale and the solver affect the learned representation; training margins do not certify held-out accuracy.
The source uses metric terminology for quadratic distances. The displayed d_M is a squared distance and does not itself generally satisfy the triangle inequality; its square root is a pseudometric when M is positive semidefinite and may collapse distinct points if M is rank deficient.
Convexity applies to the fixed-target optimization over M, not to arbitrary factorized, rank-constrained or target-reassignment extensions. Convexity also does not imply a unique optimum, perfect training separation or a certified result from every numerical solver.
The endpoints of the stated weight interval can remove one training term; mu=0 permits the collapsed M=0 solution. The paper’s unit margin is a scale convention. No benchmark, special-purpose solver implementation or extension was reproduced.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:KnearestNeighborClassificationAlgorithm` K-nearest Neighbor Classification Algorithm	related_match	LMNN learns the distance used in nearest-neighbor voting. The target describes the voting task, so this is a related metric-training-to-classification association, not algorithm identity.
`AIO:SupervisedLearning` Supervised Learning	related_match	Class labels determine target eligibility and differently labeled margin constraints. The target is a broad learning task, while LMNN is a specific metric-learning algorithm; this related mapping preserves that abstraction difference.

Evidence Sources & Primary Literature

1 Source

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	Distance Metric Learning for Large Margin Nearest Neighbor Classification Kilian Q. Weinberger, Lawrence K. Saul	primary paper full_text	ID: https://www.jmlr.org/papers/v10/weinberger09a.html sha256:514d0b11319e…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T09:58:22Z

Updated: 2026-10-11T09:58:22Z

Source File: data/curated/LargeMarginNearestNeighbor.yaml