Neighbourhood components analysis

Consider predicting the class label of a single data point by consensus of its ${\displaystyle k}$-nearest neighbours with a given distance metric. This is known as leave-one-out classification. However, the set of nearest-neighbours ${\displaystyle C_{i}}$ can be quite different after passing all the points through a linear transformation. Specifically, the set of neighbours for a point can undergo discrete changes in response to smooth changes in the elements of ${\displaystyle A}$, implying that any objective function ${\displaystyle f(\cdot )}$ based on the neighbours of a point will be piecewise-constant, and hence not differentiable.

We can resolve this difficulty by using an approach inspired by stochastic gradient descent. Rather than considering the ${\displaystyle k}$-nearest neighbours at each transformed point in LOO-classification, we'll consider the entire transformed data set as stochastic nearest neighbours. We define these using a softmax function of the squared Euclidean distance between a given LOO-classification point and each other point in the transformed space:

${\displaystyle p_{ij}={\begin{cases}{\frac {e^{-||Ax_{i}-Ax_{j}||^{2}}}{\sum _{k\neq i}e^{-||Ax_{i}-Ax_{k}||^{2}}}},&{\mbox{if}}j\neq i\\0,&{\mbox{if}}j=i\end{cases}}}$

The probability of correctly classifying data point ${\displaystyle i}$ is the probability of classifying the points of each of its neighbours with the same class ${\displaystyle C_{i}}$:

${\displaystyle p_{i}=\sum _{j\in C_{i}}p_{ij}\quad }$ where ${\displaystyle p_{ij}}$ is the probability of classifying neighbour ${\displaystyle j}$ of point ${\displaystyle i}$.

Define the objective function using LOO classification, this time using the entire data set as stochastic nearest neighbours:

${\displaystyle f(A)=\sum _{i}\sum _{j\in C_{i}}p_{ij}=\sum _{i}p_{i}}$

Note that under stochastic nearest neighbours, the consensus class for a single point ${\displaystyle i}$ is the expected value of a point's class in the limit of an infinite number of samples drawn from the distribution over its neighbours ${\displaystyle j\in C_{i}}$ i.e.: ${\displaystyle P(Class(X_{i})=Class(X_{j}))=p_{ij}}$. Thus the predicted class is an affine combination of the classes of every other point, weighted by the softmax function for each ${\displaystyle j\in C_{j}}$ where ${\displaystyle C_{j}}$ is now the entire transformed data set.

This choice of objective function is preferable as it is differentiable with respect to ${\displaystyle A}$ (denote ${\displaystyle x_{ij}=x_{i}-x_{j}}$):

${\displaystyle {\frac {\partial f}{\partial A}}=-2A\sum _{i}\sum _{j\in C_{i}}p_{ij}\left(x_{ij}x_{ij}^{T}-\sum _{k}p_{ik}x_{ik}x_{ik}^{T}\right)}$

${\displaystyle =2A\sum _{i}\left(p_{i}\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}\right)}$

Obtaining a gradient for ${\displaystyle A}$ means that it can be found with an iterative solver such as conjugate gradient descent. Note that in practice, most of the innermost terms of the gradient evaluate to insignificant contributions due to the rapidly diminishing contribution of distant points from the point of interest. This means that the inner sum of the gradient can be truncated, resulting in reasonable computation times even for large data sets.

"Maximizing ${\displaystyle f(\cdot )}$ is equivalent to minimizing the ${\displaystyle L_{1}}$-distance between the predicted class distribution and the true class distribution (ie: where the ${\displaystyle p_{i}}$ induced by ${\displaystyle A}$ are all equal to 1). A natural alternative is the KL-divergence, which induces the following objective function and gradient:" (Goldberger 2005)

${\displaystyle g(A)=\sum _{i}\log \left(\sum _{j\in C_{i}}p_{ij}\right)=\sum _{i}\log(p_{i})}$

${\displaystyle {\frac {\partial g}{\partial A}}=2A\sum _{i}\left(\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-{\frac {\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}}{\sum _{j\in C_{i}}p_{ij}}}\right)}$

In practice, optimization of ${\displaystyle A}$ using this function tends to give similar performance results as with the original.

• The MLPACK library contains a C++ implementation
• nca (C++)
• scikit-learn's "NeighborhoodComponentsAnalysis" implementation (Python)