Neighbourhood components analysis (NCA) learns a linear map W so that nearest-neighbour classification works well in the mapped space, that is, with the Mahalanobis distance of matrix WTW (16.2). Point i picks neighbour j with the softmax probability pij ∝ exp(−‖W(xi − xj)‖2) (16.6); the objective J(W) is the expected number of points that pick a neighbour of their own class, and each step below is one step of gradient ascent on it. On the first data set the classes differ along a tilted direction while a much larger spread runs across it: Euclidean neighbours are dominated by the nuisance spread, and NCA learns to shrink it. On the four-blob (XOR layout) data the Euclidean metric is already good, so there is little to learn: a linear map can only rescale and rotate, and an XOR pattern cannot be unfolded by one, which is the limit of this family and one reason for deep metric learning (Section 16.2.2). Click a point to see its three nearest neighbours in the current metric.
Data: 80 points per data set, simulated. Start W = identity, fixed step size 0.002 on the gradient (16.6)–J, so the objective rises monotonically. The leave-one-out error of K-NN excludes each point from its own neighbourhood. The learned map is only defined up to a rotation (J(QW) = J(W) for orthogonal Q), so the picture in the middle may be rotated.
code/ch16_exemplar_based_methods.py (nca_obj_grad, nca_fit, lmnn_fit).