↑ arvau

Wikipedia / Neighbourhood components analysis

Neighbourhood components analysis is a supervised learning method for classifying multivariate data into distinct classes according to a given distance metric over the data. Functionally, it serves the same purposes as the K-nearest neighbors algorithm and makes direct use of a related concept termed stochastic nearest neighbours.

Definition

, followed by the use of an iterative solver such as conjugate gradient descent, up to a scalar constant. This use of the algorithm, therefore, addresses the issue of model selection.

Explanation

such that this objective function is maximized.

Leave-one-out (LOO) classification

-nearest neighbours with a given distance metric. This is known as leave-one-out based on the neighbours of a point will be piecewise-constant, and hence not differentiable.

Solution

We can resolve this difficulty by using an approach inspired by stochastic gradient descent-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:

:

.

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

. Thus the predicted class is an affine combination is now the entire transformed data set.

):

Obtaining a gradient 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.

Alternative formulation

are all equal to 1). A natural alternative is the KL-divergence, which induces the following objective function and gradient:" (Goldberger 2005)

using this function tends to give similar performance results as with the original.

History and background

Neighbourhood components analysis was developed by Jacob Goldberger, Sam Roweis, Ruslan Salakhutdinov, and Geoff Hinton at the University of Toronto's department of computer science in 2004.

See also

References

  • J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) Neighbourhood Components Analysis . Advances in Neural Information Processing Systems. 17, 513–520, 2005.

Software