

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

## 7. Conclusion

We have demonstrated a novel method for optimally integrating heterogeneous data to conform to measurements of perceptual similarity. By interpreting a collection of relative similarity comparisons as a directed graph over pairs, we are able to apply graph-theoretic techniques to isolate and prune inconsistencies in the training set and reduce computational overhead by eliminating redundant constraints in the optimization procedure.

Our multiple-kernel formulation offers a principled way to integrate multiple feature modalities into a unified similarity space. Our formulation carries the intuitive geometric interpretation of concatenated projections, and results in a semidefinite program. By incorporating diagonal constraints as well, we are able to reduce the computational complexity of the algorithm, and learn a model which is both flexible - only using kernels in the portions of the space where they are informative - and interpretable - each diagonal weight corresponds to the contribution to the optimized space due to a single point within a single feature space. Table 1 provides a unified perspective of multiple kernel learning formulations for embedding problems, but it is clearly not complete. It will be the subject of future work to explore and compare alternative generalizations and restrictions of the formulations presented here.

## Appendix A. Embeddability Of Partial Orders

In this appendix, we prove that any set X with a partial order over distances C can be embedded into R
n while satisfying all distance comparisons.

In the special case where C is a total ordering over all pairs (*i.e.*, a chain graph), the problem reduces to non-metric multidimensional scaling (Kruskal, 1964), and a constraint-satisfying embedding can always be found by the constant-shift embedding algorithm of Roth et al. (2003). In general, C is not a total order, but a C-respecting embedding can always be produced by reducing the partial order to a (weak) total order by topologically sorting the graph (see Algorithm 5).

Let ∆ be the dissimilarity matrix produced by Algorithm 5 on an instance (X , C). An embedding can be found by first applying classical multidimensional scaling (MDS) (Cox and Cox, 1994)