Many learning algorithms use a metric defined over the input space as
a principal tool, and their performance critically depends on the
quality of this metric.  We address the problem of learning metrics
using side-information in the form of equivalence constraints.  Unlike
labels, we demonstrate that this type of side-information can
sometimes be automatically obtained without the need of human
intervention.  We show how such side-information can be used to modify
the representation of the data, leading to improved clustering and
classification.

Specifically, we present the Relevant Component Analysis (RCA)
algorithm, which is a simple and efficient algorithm for learning a
full ranked Mahalanobis metric. We show that RCA is the solution of an
interesting optimization problem, founded on an information theoretic
basis. If the Mahalanobis matrix is allowed to be singular, we show
that Fisher's linear discriminant followed by RCA is the optimal
dimensionality reduction algorithm under the same criterion. Moreover,
under certain Gaussian assumptions, RCA can be viewed as an ML
estimation of the inner class covariance matrix.  We conclude with
extensive empirical evaluations of RCA, showing its advantage over
alternative methods.