Information-theoretic metric learning

In this paper, we present an information-theoretic approach to learning a Mahalanobis distance function. We formulate the problem as that of minimizing the differential relative entropy between two multivariate Gaussians under con- straints on the distance function. We express this problem as a particular Bregman optimiza- tion problem—that of minimizing the LogDet di- vergence subject to linear constraints. Our result- ing algorithm has several advantages over exist- ing methods. First, our method can handle a wide variety of constraints and can optionally incorpo- rate a prior on the distance function. Second, it is fast and scalable. Unlike most existing meth- ods, no eigenvalue computations or semi-definite programming are required. We also present an online version and derive regret bounds for the resulting algorithm. Finally, we evaluate our method on a recent error reporting system for software called Clarify, in the context of met- ric learning for nearest neighbor classification, as well as on standard data sets.