  Metric learning methods have been shown to perform well on different learning
tasks. Many of them rely on target neighborhood relationships that are computed
in the original feature space and remain fixed throughout learning. As a
result, the learned metric reflects the original neighborhood relations. We
propose a novel formulation of the metric learning problem in which, in
addition to the metric, the target neighborhood relations are also learned in a
two-step iterative approach. The new formulation can be seen as a
generalization of many existing metric learning methods. The formulation
includes a target neighbor assignment rule that assigns different numbers of
neighbors to instances according to their quality; `high quality' instances get
more neighbors. We experiment with two of its instantiations that correspond to
the metric learning algorithms LMNN and MCML and compare it to other metric
learning methods on a number of datasets. The experimental results show
state-of-the-art performance and provide evidence that learning the
neighborhood relations does improve predictive performance.
