of which all but 5 were found in the collaborative filtering graph. The resulting graph has 336527 users and 407 artists, and is equivalently represented by a binary matrix where each row i corresponds to an artist, and each column j corresponds to a user. The ij entry of this matrix is 1 if we observe a user-artist association, and 0 otherwise. The kernel between artists in this view is the cosine of the angle between corresponding rows in the matrix, which can be interpreted as counting the amount of overlap between the sets of users listening to each artist and normalizing for overall artist popularity. For the 5 artists not found in the graph, we fill in the corresponding rows and columns of the kernel matrix with the identity matrix.

## 5.2.2 Experimental Procedure

The data set was split into 330 training and 82 test artists. Given the inherent ambiguity in the task and the format of the survey, there is a great deal of conflicting information in the survey responses. To obtain a more accurate and internally coherent set of training comparisons, directly contradictory comparisons (*e.g.*, (**i, j, i, k**) and (**i, k, i, j**)) are removed from the training set, reducing the set from 7915 to 6583 relative comparisons. The training set is further cleaned by finding an acyclic subset of comparisons and taking its transitive reduction, resulting in a minimal partial order with 4401 comparisons.

To evaluate the performance of an embedding learned from the training data, we apply it to the test data, and then measure accuracy by counting the fraction of similarity measurements (**i, j, i, k**)
correctly predicted by distance in the embedding space, where i belongs to the test set, and j and k belong to the training set. This setup can be viewed as simulating a query (by-example) i and ranking the responses **j, k** from the training set. To gain a more accurate view of the quality of the embedding, the test set was also pruned to remove directly contradictory measurements. This reduces the test set from 2095 to 1753 comparisons. No further processing is applied to test measurements, and we note that the test set is not internally consistent, so perfect accuracy is not achievable.

For each experiment, the optimal β is chosen from {10−2, 10−1**, . . . ,** 107} by 10-fold crossvalidation, *i.e.*, repeating the test procedure above on splits within the training set. Once β is chosen, an embedding is learned with the entire training set, and then evaluated on the test set.

## 5.2.3 Embedding Results

For each base kernel, we evaluate the test-set performance in the native space (*i.e.*, by distances calculated directly from the entries of the kernel matrix), and by learned metrics, both diagonal and full (optimizing over K1 with a single base kernel). Table 3 lists the results. In all cases, we observe significant improvements in accuracy over the native space. In all but one case, full-matrix embeddings significantly outperform diagonally-constrained embeddings.

We then repeated the experiment by examining different groupings of base kernels: acoustic
(MFCC and Auto-tags), semantic (Social tags and Bio), social (Collaborative filter), and combinations of the groups. The different sets of kernels were combined by Algorithm 4 (optimizing over K4). The results are listed in Table 4. For comparison purposes, we also include the unweighted sum of all base kernels (listed in the *Native* column).

In all cases, MKPOE improves over the unweighted combination of base kernels. Moreover, many combinations outperform the single best kernel (ST), and the algorithm is generally robust in the presence of poorly-performing distractor kernels (MFCC and AT). Note that the poor performance of MFCC and AT kernels may be expected, as they derive from song-level rather than