Active Metric Learning from Relative Comparisons
  This work focuses on active learning of distance metrics from relative
comparison information. A relative comparison specifies, for a data point
triplet $(x_i,x_j,x_k)$, that instance $x_i$ is more similar to $x_j$ than to
$x_k$. Such constraints, when available, have been shown to be useful toward
defining appropriate distance metrics. In real-world applications, acquiring
constraints often require considerable human effort. This motivates us to study
how to select and query the most useful relative comparisons to achieve
effective metric learning with minimum user effort. Given an underlying class
concept that is employed by the user to provide such constraints, we present an
information-theoretic criterion that selects the triplet whose answer leads to
the highest expected gain in information about the classes of a set of
examples. Directly applying the proposed criterion requires examining $O(n^3)$
triplets with $n$ instances, which is prohibitive even for datasets of moderate
size. We show that a randomized selection strategy can be used to reduce the
selection pool from $O(n^3)$ to $O(n)$, allowing us to scale up to larger-size
problems. Experiments show that the proposed method consistently outperforms
two baseline policies.
