Neighbourhood components analysis
Algorithms AIMech:NeighborhoodComponentsAnalysis DRAFT
Aliases: Neighborhood components analysis, NCA
A supervised metric-learning algorithm that learns a linear transformation by maximizing the expected number of correctly classified training examples under stochastic leave-one-out neighbor selection.
Identity Notes & Concept Scope
NCA is Goldberger et al.’s transformation-learning procedure, not ordinary k-nearest-neighbor voting or an unsupervised local-coordinate reconstruction. Its main objective sums correct-class probabilities; the paper also discusses a sum-of-log-probabilities alternative, which is a different objective. A rectangular transformation enables supervised dimensionality reduction. The AIO MetricLearning node is explicitly a deep neural network, so the original linear NCA procedure is not treated as its subclass. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 223 preceding native IDs/names/aliases. Word-delimited fixed-string searches of both full checkouts, including ignored and hidden files, returned 2 worktree lines in discovery context and 6 main-checkout lines including four unrelated ignored dependency matches. Six neighboring native records and nine exact AIO nodes with scoped synonyms and outgoing edges were inspected.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
For labeled vectors x_i, choose a matrix A, possibly rectangular, and use squared transformed distance d_ij=||A(x_i−x_j)||², with Q=A^T A positive semidefinite. For j!=i set p_ij=exp(−d_ij)/sum_(k!=i)exp(−d_ik), and set p_ii=0. Define p_i=sum_(j:c_j=c_i)p_ij. Optimize f(A)=sum_i p_i by a gradient-based method; this is the expected number of correct labels when each training point selects one other point as its neighbor according to p_ij. For dimensionality reduction use A with d rows, store Ax_i and classify a new projected point using ordinary Euclidean k-nearest-neighbor voting. Learning the scale of A changes the softness of the training neighbor distribution; it does not uniquely determine the later integer k.
⚠️ Curated Limitations & Negative Results
- Training uses class labels and a smooth stochastic surrogate, not the discontinuous deterministic k-nearest-neighbor accuracy. Improving its training objective does not certify held-out classification accuracy.
- The objective is nonconvex in A; initialization and the optimizer affect its result. A=0 is a stationary point of the displayed gradient, so a claim that any initialization learns a useful metric would be unwarranted.
- At least two observations are needed for the leave-one-out denominator. A class represented by a singleton has p_i=0 and contributes no correct-class reward; the paper’s logarithmic alternative is undefined for that point.
- Rectangular or rank-deficient A yields a positive-semidefinite squared distance with possible collapsed directions. It need not define a strictly positive distance between distinct original points. No global optimum, absence of overfitting or benchmark advantage is asserted.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:KnearestNeighborClassificationAlgorithm
K-nearest Neighbor Classification Algorithm
|
related_match | NCA learns the distance used by a nearest-neighbor classifier and explicitly applies voting after projection. It is distinct from the AIO voting task, so this is a related method-to-task association. |
AIO:DimensionalityReduction
Dimensionality Reduction
|
related_match | The rectangular NCA configuration learns a lower-dimensional projection using labels. The AIO target is placed under UnsupervisedLearning; this related association preserves the shared reduction operation without asserting that supervised NCA is an unsupervised subclass. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Jacob Goldberger, Sam Roweis, Geoff Hinton, Ruslan Salakhutdinov
|
primary paper
full_text
|
ID: https://papers.nips.cc/paper_files/paper/2004/hash/42fe880812925e520249e808937738d2-Abstract.html
sha256:13831bbd3e69…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T09:45:04Z
Updated: 2026-10-11T09:45:04Z
Source File:
data/curated/NeighborhoodComponentsAnalysis.yaml