  Distance metric learning has attracted a lot of interest for solving machine
learning and pattern recognition problems over the last decades. In this work
we present a simple approach based on concepts from statistical physics to
learn optimal distance metric for a given problem. We formulate the task as a
typical statistical physics problem: distances between patterns represent
constituents of a physical system and the objective function corresponds to
energy. Then we express the problem as a minimization of the free energy of a
complex system, which is equivalent to distance metric learning. Much like for
many problems in physics, we propose an approach based on Metropolis Monte
Carlo to find the best distance metric. This provides a natural way to learn
the distance metric, where the learning process can be intuitively seen as
stretching and rotating the metric space until some heuristic is satisfied. Our
proposed method can handle a wide variety of constraints including those with
spurious local minima. The approach works surprisingly well with stochastic
nearest neighbors from neighborhood component analysis (NCA). Experimental
results on artificial and real-world data sets reveal a clear superiority over
a number of state-of-the-art distance metric learning methods for nearest
neighbors classification.
