
## 4.4 Diagonal Learning

The MKPOE optimization is formulated as a semi-definite program over m different n×n matrices Wp - or, as shown in Table 1, a single mn×mn PSD matrix with a block-diagonal sparsity structure. Scaling this approach to large data sets can become problematic, as they require optimizing over multiple high-dimensional PSD matrices.

To cope with larger problems, the optimization problem can be refined to constrain each Wp to the set of diagonal matrices. If Wpare all diagonal, positive semi-definiteness is equivalent to non-negativity of the diagonal values (since they are also the eigenvalues of the matrix). This allows the constraints Wp  0 to be replaced by linear constraints W
p ii ≥ 0, and the resulting optimization problem is a linear program (LP), rather than an SDP. This modification reduces the flexibility of the model, but leads to a much more efficient optimization procedure.

More specifically, our implementation of Algorithm 4 operates by alternating gradient descent on Wpand projection onto the feasible set Wp  0 (see Appendix B for details). For full matrices, this projection is accomplished by computing the spectral decomposition of each Wp, and thresholding the eigenvalues at 0. For diagonal matrices, this projection is accomplished simply by W
p ii 7→ max {0, Wp ii} ,
which can be computed in O(mn) time, compared to the O(mn3) time required to compute m spectral decompositions.

Restricting Wpto be diagonal not only simplifies the problem to linear programming, but carries the added interpretation of weighting the contribution of each (kernel, training point) pair in the construction of the embedding. A large value at W
p ii corresponds to point i being a landmark for the features encoded in Kp. Note that each of the formulations listed in Table 1 has a corresponding diagonal variant, however, as in the full matrix case, only K1 and K4 lead to convex optimization problems.

## 5. Experiments

To evaluate our framework for learning multi-modal similarity, we first test the multiple kernel learning formulation on a simple toy taxonomy data set, and then on a real-world data set of musical perceptual similarity measurements.

## 5.1 Toy Experiment: Taxonomy Embedding

For our first experiment, we generated a toy data set from the Amsterdam Library of Object Images (ALOI) data set (Geusebroek et al., 2005). ALOI consists of RGB images of 1000 classes of objects against a black background. Each class corresponds to a single object, and examples are provided of the object under varying degrees of out-of-plane rotation.

In our experiment, we first selected 10 object classes, and from each class, sampled 20 examples.

We then constructed an artificial taxonomy over the label set, as depicted in Figure 4. Using the taxonomy, we synthesized relative comparisons to span subtrees via their least common ancestor.

For example,
(Lemon \#1, Lemon \#2, Lemon \#1, P ear\#1),
(Lemon \#1, P ear\#, 1, Lemon \#1, Sneaker\#1),