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.
The aforementioned RCKL methods can be viewed as solving a kernelized special case of the classic non-metric multidimensional scaling problem @cite_21 , where the goal is to find an embedding of objects in @math such that they satisfy given Euclidean distance constraints. In contrast to many of the kernel-learning formulations, their analogous embedding-learning counterparts are non-convex optimization problems, which only guarantee convergence to a local minimum. In the typical non-convex batch setting, multiple solutions are found with different initializations and the best is chosen among them. This strategy is poorly suited for the online setting where triplets are being observed sequentially, and which solution is best may change as feedback is received.
@cite_21
1973192023
We describe the numerical methods required in our approach to multi-dimensional scaling. The rationale of this approach has appeared previously.