We consider the problem of metric learning subject to a set of constraints on relative-distance comparisons between the data items. Such constraints are meant to reflect side-information that is not expressed directly in the feature vectors of the data items. The relative-distance constraints used in this work are particularly effective in expressing structures at finer level of detail than must-link (ML) and cannot-link (CL) constraints, which are most commonly used for semi-supervised clustering. Relative-distance constraints are thus useful in settings where providing an ML or a CL constraint is difficult because the granularity of the true clustering is unknown. Our main contribution is an efficient algorithm for learning a kernel matrix using the log determinant divergence --- a variant of the Bregman divergence --- subject to a set of relative-distance constraints. The learned kernel matrix can then be employed by many different kernel methods in a wide range of applications. In our experimental evaluations, we consider a semi-supervised clustering setting and show empirically that kernels found by our algorithm yield clusterings of higher quality than existing approaches that either use ML CL constraints or a different means to implement the supervision using relative comparisons.
As stated in the introduction, our work is based on metric learning . Most of the metric-learning literature, starting by the work of , aims at finding a Mahalanobis matrix subject to either ML CL or relative distance constraints. use ML CL constraints, while present a similar approach to handle relative comparisons. Metric learning often requires solving a semidefinite optimization problem. For instance, @cite_1 propose an online kernel learning method using stochastic gradient descent. However, the method requires an additional projection step onto the positive semidefinite cone. This problem becomes easier if Bregman divergence, in particular the log det divergence, is used to formulate the optimization problem. Such an approach was first used for metric learning by with ML CL constraints, and subsequently by likewise with ML CL constraints, as well as by with relative comparisons. Our algorithm also uses the log det divergence, and we extend the technique of to handle relative comparisons.
@cite_1
1573782941
Learning a kernel matrix from relative comparison human feedback is an important problem with applications in collaborative filtering, object retrieval, and search. For learning a kernel over a large number of objects, existing methods face significant scalability issues inhibiting the application of these methods to settings where a kernel is learned in an online and timely fashion. In this paper we propose a novel framework called Efficient online Relative comparison Kernel LEarning (ERKLE), for efficiently learning the similarity of a large set of objects in an online manner. We learn a kernel from relative comparisons via stochastic gradient descent, one query response at a time, by taking advantage of the sparse and low-rank properties of the gradient to efficiently restrict the kernel to lie in the space of positive semidefinite matrices. In addition, we derive a passive-aggressive online update for minimally satisfying new relative comparisons as to not disrupt the influence of previously obtained comparisons. Experimentally, we demonstrate a considerable improvement in speed while obtaining improved or comparable accuracy compared to current methods in the online learning setting.