Visualizing pairwise similarity via semidefinite programming
Amir Globerson, Sam T. Roweis · International Conference on Artificial Intelligence and Statistics · 2007
We introduce a novel learning algorithm for binary pairwise similarity measurements on a set of objects. The algorithm delivers an embedding of the objects into a vector representation space that strictly respects the known similarities, in the sense that objects known to be similar are always closer in the embedding than those known to be dissimilar. Subject to this constraint, our method selects the mapping in which the variance of the embedded points is maximized. This has the efiect of favoring embeddings with low efiective dimensionality. The related optimization problem can be cast as a convex Semideflnite Program (SDP). We also present a parametric version of the problem, which can be used for embedding out of sample points. The parametric version uses kernels to obtain nonlinear maps, and can also be solved using an SDP. We apply the two algorithms to an image embedding problem, where it efiectively captures the low dimensional structure corresponding to camera viewing parameters.