Multi-Prototype Label Ranking with Novel Pairwise-to-Total-Rank Aggregation

1 Introduction

In the Label Ranking setup, the input space is defined by a feature vector x ∈ X, and the output is defined as a ranking of labels π ∈ Π (e.g., π = (3, 1, 4, 2)). Given a sample from the underlying distribution D = {(xn, πn), n = 1, ...,N}, where xn is a d-dimensional feature vector and πn is a vector containing either a total or a partial order of a finite set Y of L class labels, the goal is to learn a model that maps x to a total label order L : X → Π.

This problem has received a lot of attention in the machine learning community and has been extensively studied [Dekel et al., 2003; ?; ?; ?; ?]. For a survey of recent Label Ranking algorithms see [G¨artner and Vembu, 2010]. Unlike standard problems of classification and regression, Label Ranking is a complex learning task, which involves prediction of strict label-order relations, rather than single values. It differs from the Learning to Rank setup [Cao et al., 2007], where a feature vector is formed from query features and corresponding document features, and the output is the relevance score. It also differs from the Collaborative Filtering setup [Zhou et al., 2008], where the input space is a set of scores over some of the labels, and the output is a set of scores or rankings of the remaining labels.

There are many practical applications in which the objective is to learn exact label preference of an instance in a form of a total order. For example, in the task of document categorization [Boley et al., 1999] where it is very likely that a

* These authors have contributed equally to this work.

Slobodan Vucetic

Temple University, USA slobodan.vucetic@temple.edu

document belongs to multiple topics (e.g., science, entertainment, news, etc.) multi-label classification has traditionally been used. However, one might not be interested only in distinguishing between relevant and irrelevant topics for a specific document, but also in learning how to find a total order of the topics by relevance.

Personalization and targeting is emerging as an important and practically relevant field. Current trend is that publishers aim at personalizing their content (such as news articles, stories, advertisements) at the fine-grain level of individual user, or at least at the level of a user group [Grbovic et al., 2012]. One way of achieving this is through learning user preferences over content categories or topics (e.g., sports, finance, politics, etc.) in form of total ranking π. Since the user reading history, such as the counts of reading sessions per topic, is directly correlated with the user preferences, one way of inferring ranking π is to sort the counts. However, new users that have just sign up with the publisher have no activity log, and the publisher must look elsewhere for predictive data sources that are indicative of π. Popular cold-start heuristics include randomly suggesting content, or suggesting content popular among a new user's age group or gender [Park and Chu, 2009], and usually fail to initially personalize beyond that. Label Ranking allows us to learn a mapping x → π, from existing users for which information x is available and π is known, where x is a vector created from user's sign-up information (e.g. age, gender, location) and/or third party information (e.g., occupation, hobbies, political views, religion). Since the preferences may change over time, it is important to have a label ranking model with online learning capabilities, such that it can be updated with daily activities of a large user population.

We propose a soft multi-prototype algorithm (SMP-Rank) for learning pairwise label preferences, attractive because of an intuitive online learning process, ease of implementation, and an ability to support various ranking structures, including complete and incomplete rankings, bipartite and multipartite ranking as well as arbitrary pairwise preferences. SMPRank belongs to a class of Learning Vector Quantization [Kohonen, 1990] prototype-based learning algorithms, that have previously been shown useful in classification [Seo and Obermayer, 2003] and regression [Grbovic and Vucetic, 2009] tasks. We derive its adaptation for the Label Ranking task. In addition, we propose a new algorithm for aggregation of arbitrary pairwise preferences into a total ranking. The preference aggregation is a well-known problem in preference learning, where numerous methods have been proposed [Cohen et al., 1999; ?; ?]. It is challenging, since the pairwise preferences may not be transitive. For instance, if we have three labels i, j and k, label ranking algorithmmight prefer i over j, j over k, and finally k over i, thus inducing a cycle. The proposed aggregation algorithm consistently outperforms competing algorithms in this task as the number of labels L grows.

There are several existing approaches to Label Ranking. Pairwise Comparison method (PW) [H¨ullermeier et al., 2008] trains L · (L - 1)/2 classifiers, one for each pair of labels, and aggregates the pairwise predictions into a total order using Soft-Borda Count. Log-Linear Label Ranking (Lin-LL) method [Dekel et al., 2003] learns mappings fk : X → R for each label k = 1, ..,L, to minimize the number of ranking errors. Each fk(·) is modeled as a linear combination of base ranking functions, such that fi (x) > fj (x) if x prefers label i over j . The final rank is produced by sorting the scores fk(·).

On the other hand, instance-based Mallows (IB-Mal) [Cheng et al., 2009] and Plackett-Luce (IB-PL) [Cheng et al., 2010] methods use the k-Nearest Neighbor algorithm to locate neighbors in the feature space, and rely on the Mallows [Mallows, 1967] or the Plackett-Luce [Plackett, 1975] probabilistic ranking models to combine neighbors' label rankings into a single prediction. The instance-based methods have been shown to outperform the competitors. However, their success comes at a large cost associated with both memory and time. Firstly, they require that the entire training data set is stored in memory, which can be very costly or even impossible in resource-constrained applications. Secondly, the Mallows and Plackett-Luce parameters are not learned during training, instead they are estimated at prediction time for each test instance separately, making it hard to achieve real-time predictions in web-based applications such as ad targeting.

There are several main justifications for using a prototypebased algorithm in Label Ranking. One is that it allows a clear mechanism for designing a prototype-based ranker on a fixed prototype budget. Unlike classification, where methods such as condensing [Hart, 1968] have been proposed for nearest neighbor classifiers, there is no clear alternative for building budget-based nearest neighbor and Parzen window algorithms for Label Ranking. Another justification is that the proposed SMP-Rank has low training cost with linear time and constant memory scaling with training size. In particular, gradient descent-based models, such as the proposed SMPRank, are most practical when it comes to needing to update the model with millions of examples every day, without having to store them. This makes it attractive for online learning applications.

There is one more property that distinguishes the proposed algorithm from the competition. Most of the existing algorithms are designed to learn from label orderings that form a ranking, either complete or partial top-k rankings. In order to be able to learn from arbitrary pairwise preferences that cannot form a ranking (e.g., 1 ≻ 5, 2 ≻ 1, 3 ≻ 4, where ≻ is read as "is preferred over") most of them need to improvise by imputing missing comparisons, for instance, based on conditional insertion probabilities [Lu and Boutilier, 2011].

SMP-Rank, however, handles such incomplete data directly, without having to estimate the missing information.

We conducted thorough empirical evaluation on synthetic and real-world data, with various data and label set sizes. The results illustrate the usefulness of the proposed methodology in the label ranking task, and also in the task of pairwise-tototal-rank aggregation, where the new aggregation algorithm outperforms the existing solutions.

2 Preliminaries

In the label ranking scenario, a single instance, described by a d-dimensional vector x, is associated with a total order of assigned class labels, represented as a permutation π of the set {1, ..., L}, where L is the number of available class labels. We define π such that π(i) is the class label at the i-th position in the order, and π-1 (j ) is a position of the yj class label in the order. The permutation can also describe incomplete ranking {π(1), ..., π(k )} ⊂ {1, ..., L}, k < L.

In our approach we represent the label ranking for each instance x in the following way. Instead of the total order, we use a zero-diagonal preference matrix Y, where Y(i, j ) > Y(j , i) if label yi is preferred over label yj and Y(i, j ) + Y(j , i) = 1, for i, j ∈ {1, ..., L}. A value of Y(i, j ) which is close to 1 is interpreted as a strong preference that yi should be ranked before yj . Similarly, uncertain (soft) preferences can be modeled by using values lower than 1. For example, indifferences (ties) are represented by setting Y(i , j ) = Y(j , i ) = 0.5. Given potentially incomplete permutation π, the preference matrix consistent with it can be formed in many ways. A typical approach is to assign Y(i, j ) = 1 and Y(j , i) = 0 if yi ≻ yj and Y(i , j ) = Y(j , i) = 0 in case of incomparable or missing class label preferences. This representation allows us to work with complete and top-k label rankings, bipartite and multipartite label rankings, as well as with arbitrary pairwise preferences and indifferences.

2.1 EvaluationMetrics

Let us assume that N historical observations are collected in a form of a data set D = {(xn,Yn), n = 1, ...,N}. The objective in all scenarios is to train a ranking function L : xn → ˆπn that outputs a total label order.

In the Label Ranking scenario, to measure the degree of correspondence between true and predicted rankings for the n-th example, πn and ˆπn respectively, it is common to use the Kendall's tau distance dn =| {(yi, yj) : π-1 n (yi) > π-1 n (yj)∧ˆπ-1 n (yj) > ˆπ-1 n (yi)} |. To evaluate a label ranking model, the label ranking loss on the data set D is defined as the average normalized Kendall's tau distance,

Note that the measure simply counts the number of discordant label pairs and reports the average over all considered pairwise rankings. Given the preference matrix representation, assuming binary predictions ˆYn, we can rewrite (1) as

where ‖ · ‖F is the Frobenius norm, and entries for which Yn(i, j ) = Yn(j , i) = 0 are skipped over. For models with soft label preference predictions ˆYn, e.g., ˆYn(i, j) = 0.7, ˆYn(j, i) = 0.3, loss (2) can be interpreted as a soft version of (1).

In the proposed methodology, we learn the mapping L : xn → πn in two stages. In the learning stage, function f : xn → Yn is learned via minimizing (2). In the aggregation stage, given the model predictions in a form of Yn, the total order prediction πn is computed using a preference aggregation h : Yn → πn.

3 SMP-Rank algorithm

The proposed method is completely defined by a set of K prototypes {(mk,Qk), k = 1, ...,K}, where mk is a ddimensional vector in input space, and Qk is the corresponding pairwise preference matrix.

The starting point in the design of SMP-Rank is to introduce the probability P(k | x) of assigning observation xn to the k-th prototype that is dependent on their (Euclidean) distance. Let us assume that the probability density P(xn) can be described by a mixture model,

where K is the number of prototypes, P(k) is the prior probability that a data point is generated by the k-th prototype, and P(xn | k) is the conditional probability that the k-th prototype generates particular data point xn. Let us represent the conditional density function P(xn | k) with the normalized exponential form P(xn | k) = θ(k) · exp(f(xn,mk)) and consider a Gaussian mixture with θ(k) = (2πσ2 p )-1/2 and f (xn, mk) = -‖xn -mk‖2/2σ2 p . We assume that all prototypes have the same standard deviation σp and the same prior, P(k) = 1/K. Given these assumptions, using the Bayes' rule we can write the assignment probability as

For compactness we introduced the following notation, gnk = P(k | xn).

To derive a cost function for SMP-Rank, we use the prediction model that assigns data point xn to the prototypes probabilistically and predicts based on the weighted average of the prototype preference matrices. Assuming such a model we can write the posterior probability P(Y | x) as

where we introduced enk = N (Yn - Qk, σ2 y ).

The mixture model assumes the conditional independence between xn and Y given k, P(Y | xn, k) = P(Y | k). For P(k | xn) we assume the Gaussian distribution from (4). For the probability of generating a preference matrix Y by prototype k, P(Y | k), we also assume Gaussian error model with mean (Y-Qk) and standard deviation σy. The resulting cost function can be written as the negative log-likelihood,

It is important to observe that, after proper normalization, (6) reduces to (2) if examples are assigned to prototypes deterministically. Therefore, it can be interpreted as its soft version. If prototype matrices Qk consisted of only 0 and 1 entries (hard label preferences) (6) further reduces to (1).

The objective is to estimate the unknown model parameters, namely prototype positions mk and their preference matrices Qk, k = 1, ...,K. This is done by minimizing the cost function losssmp with respect to these parameters. If online learning capability is a requirement, one can use the stochastic gradient descent method and obtain the learning rules at the t-th iteration by calculating derivatives ∂losstsmp/∂mk and ∂losstsmp/∂Qk for k = 1, ...,K. This results in following rules for the n-th training example,

where Ln = ∑Kk=1 gnk · enk. The resulting model has training time complexity of O(NKL). Note that it is straightforward to cast the optimization into EM framework following the procedure from [Weigend et al., 1995].

At iteration t = 0, the procedure starts by selecting first K training points as initial prototypes. If any Qk prototype preference matrix obtained in such manner contains empty elements, they are replaced with 0.5 entries, as the corresponding labels will initially be treated equally. Then, prototype parameters are learned using the iterative procedure (7). Learning is terminated when the loss function losssmp stops improving (e.g., changes by less than 10-5 ).

During inference, rank prediction ˆπu of unlabeled data point xu is determined as an aggregated weighted average of the prototype preference matrices Qk, ˆπu = h( ˆYu), where ˆYu = (∑Kk=1 guk · Qk) is the aggregated preference matrix, and h(·) is an aggregation function presented in Section 4.

An important issue to be addressed is the choice of parameter σp. The update rule can be derived using the gradient descent method. However, we experimentally determined that this could lead to instabilities in the learning process. We employ a simpler approach, and anneal σp using a specific schedule, σp(t + 1) = σp(0) · σT /(σT + t), where σT is the decay parameter. However, we do not wish σp to drop to a value near zero as that would result in possibly suboptimal hard prototype assignments, thus we resort to using a validation data set and continue decreasing σp as long as losssmp value is being improved on the validation set. Lastly, σ2 y is set to the mean of squared Frobenius norm ‖Yn - ˆYn‖2F of the current model.

3.1 Low-rank preference matrix approximation

Since the preference matrix Qk is of size L × L, memory required to store preference matrix even for a single prototype can be prohibitively large when number of labels L is very high. In such cases we can resort to low-rank matrix approximation of preference matrix using singular value decomposition (SVD), by representing a matrix as

where Uk and Vk are L×m matrices, while Σk is a diagonal m×m matrix for some m ≤ L. Low-rank matrix approximation allows us to work with large matrices Qk by actually storing Uk, Σk, and Vk to memory, and can also help filter out noise fromQk. Substituting equation (8) to (6), and taking derivatives with respect to matrices Uk, Σk, and Vk we can easily obtain update rules for Uk, Σk, and Vk to replace the Qk updates in (7).

4 Pairwise Preference Aggregation algorithm

For an instance x, the SMP-Rank output is represented by pairwise preference matrix Y. The aggregation algorithm computes the total order given these, often conflicting, pairwise preferences. Since pairwise preferences are not transitive in general, inferring total order of labels is not a trivial task. If a measure of goodness of the total order is defined as

where π-1 (i) > π-1 (j) if and only if label yi is preferred over label yj in total order π, the task to find π∗ that maximizes (9) is NP-complete [Cohen et al., 1999]. Several heuristic methods have been proposed to obtain the approximate solution to this problem. One of the first were Borda count [de Borda, 1781], which sorts the labels by the counts of victories over the opponents, and Soft Borda, which sorts by the sums of preference degrees over the opponents. Several other sorting-by-degree methods exist [Cohen et al., 1999; ?], as well as the approach from [Ailon and Mohri, 2008] which we refer to as QuickSort, as it is based on the popular sorting algorithm [Hoare, 1962]. A recent paper [Ailon, 2012] presents a near-optimal algorithm NearOpt with complexity O(ϵ-6LlogL6 ) for a regret of ϵ times the optimal loss.

We propose a novel aggregation algorithm, called TOUGH, with the same worst-case theoretical guarantees as [Cohen et al., 1999]. However, it is both simpler and more accurate than current state-of-the-art, as we show in Section 5.1. The algorithm starts with empty ordered list ˆπ. At every iteration, it expands the current ordered list by greedily adding a new label to the position in ˆπ that maximizes (9). When the list includes all labels the algorithm terminates. Algorithm 1 shows the TOUGH pseudocode.

Let us represent the preference matrix Y as a directed graph, where each label is represented by a node, and there is a directed edge between every i-th and j-th node with weight Y(i, j). Then, the following lemma holds for Algorithm 1.

Algorithm 1 Total-Order-Under-Greedy-Heuristic (TOUGH)

Inputs: label instance set Ω = {1, 2, ..., L}, preference matrix Y Output: approximately optimal ordering ˆπ

1. Initialize ˆπ to empty list
2. while (Ω is not empty)
3. Find highest value in Y and take the preferred label temp
4. Try every place in ˆπ for temp, and put in the place maximizing (9) of ˆπ
5. Set to 0 entries in Y between temp and other members of ˆπ
6. Delete temp fromΩ

Lemma 1. Let ˆπt-1 be the total order after the first t - 1 iterations of TOUGH, and ˆπt be the total order after the tth iteration (i.e., after addition of temp, see Algorithm 1). Furthermore, let at and dt be the sums of all outgoing and incoming edges at the t-th iteration, respectively, from temp to the nodes in ˆπt-1. Then, ∆t, defined as the contribution of temp at the t-th iteration to the measure of goodness (9) is bounded below as

Proof. Consider putting temp at the first place of the current total order list, and then at the last place, which completely reverses the chosen edges. ∆t for one of these two positions must be larger than or equal to one half of the sum of all the weights from temp to nodes in current total order, since sum of ∆t of these two positions is exactly equal to the sum of all the weights from temp to nodes in a current total order.

The lemma states that, when searching for the position for temp (Algorithm 1, step 4), there is always a position such that the sum of the temp's weights that will be included in the new measure of goodness is larger than or equal to one half of the sum of all weights of edges that connect temp to nodes in the current total order. Using Lemma 1, it can be shown that the approximate solution ˆπ is within a factor of 2 to the optimal solution π∗.

Theorem 1. Let OPT(Y) be the weighted agreement (9) achieved by an optimal total order π∗ for the preference matrix Y, and let APPROX(Y) be the weighted agreement achieved by output of TOUGH algorithm ˆπ. Then,

Proof. It is clear that APPROX(Y) = ∑Lt=1 ∆t, where ∆t is defined as in Lemma 1, and L is the number of labels (nodes). Then, using the result of Lemma 1, it follows that APPROX(Y) = ∑Lt=1 ∆t ≥ 1 2 ∑Lt=1 (at + dt). Further, following [Cohen et al., 1999], we have

The first inequality holds because OPT(Y) can at best include every edge in the graph, and since every edge is removed exactly once (weight of edge set to 0), each edge must contribute to some at or some dt.

(a) Smaller label set

(b) Larger label set

Figure 1: Comparison of pairwise preference aggregation algorithms

The time complexity of TOUGH is O(L2 log L). A simple modification in Step 3 of Algorithm 1 that takes a random label instead of the highest preferred label results in a TOUGHr algorithm with O(L2 ) time complexity. Theorem 10 holds for TOUGHr as well and, as the results show, its performance converges to TOUGH performance for large L.

A popular aggregation algorithm is SCC+Greedy [Cohen et al., 1999], which first orders strongly connected components (SCC) and then the nodes within each SCC, restricting a node to stay in a part of the rank determined by its SCC. On the other hand, TOUGH tries out all possible locations in the partial ordering, which produces a more consistent total ordering. TOUGH is straightforward to implement, e.g., much simpler than SCC+Greedy, which requires a preprocessing step that finds SCC in a graph.

Finally, we note that the authors of the QuickSort algorithm [Ailon and Mohri, 2008] prove regret bound and loss bound seemingly better than the one we show. However, as their algorithm is non-deterministic, the loss bound is on the expectation of loss, where expectation is over random choices of pivot labels. In practice, it achieves bad results if pivot is chosen poorly, performing worse than the bound we give. Therefore, QuickSort does not have this worst-case guarantee, unlike SCC+Greedy and TOUGH algorithms.

5 Empirical Evaluation

5.1 Preference Aggregation Evaluation

We compared 8 different aggregation algorithms: SCC+Greedy, Borda count, Soft Borda, QuickSort, NearOpt, TOUGH, TOUGHr and Randomized. Randomized algorithm is a heuristic that chooses the better between some random order and its inverse (L, 10L and 100L random orders were compared for each matrix). We randomly generated 10,000 Y matrices of sizes ranging from 3 to 30, where element Y(i, j) is sampled uniformly from [0, 1] and Y(j, i) = 1 -Y(i, j). For pairwise preference matrices of size up to and including 10, we calculated the optimal total ordering π∗ using exhaustive search. Given the approximate total order ˆπ we calculated the fraction of optimal solution as

For matrices of size over 10 we did not calculate the optimal total order due to high computational cost. Instead, given ˆπ we calculated the fraction of total weight as

The results of the comparison are given in Figures 1a and 1b. Despite its simplicity, TOUGH outperformed all other aggregation methods, except for L ≤ 6, where Randomized100 is better because it performs exhaustive search. Note that Randomized10 approximates the number of operations in TOUGH and is more expensive than TOUGHr.

At the first glance, Figure 1 seems to show that the performance improvement of TOUGH is not large. However, by taking a closer look, we can see that for L = 10, fraction of the optimal solution of TOUGH is 3% smaller than the optimal brute force algorithm. SCC+Greedy is 6% worse than the optimal (2× performance decrease when compared to TOUGH), while the other algorithms such as QuickSort and Borda are over 10% worse than the optimal solution.

Finally, NearOpt falls well behind TOUGH for ϵ = 0.3. We have experimented with values of ϵ = 0.1 and 0.2 as well. Our conclusion was that it exceeded reasonable time requirements for bigger L, while achieving same or slightly better performance than TOUGH. For example, the ϵ = 0.1 experiment for L = 10 could not finish in 1 day.

5.2 Evaluation of Label Ranking Techniques

Here we evaluate the performance of SMP-Rank on label ranking problems. Our preliminary results showed that SMP- Rank with TOUGH performed better than with other aggregation algorithms. Therefore, only these results are shown.

We used 22 data sets (Table 1); 17 semi-synthetic data sets obtained by converting benchmark multi-class (A) and regression data (B) from the UCI and Statlog repositories into label ranking data, using the Na¨ıve Bayes (A) and featureto-label technique (B) [Cheng et al., 2009], and 6 real-world data sets from the medical [H¨ullermeier et al., 2008] and food [Kamishima and Akaho, 2006] domains.

SMP-Rank parameter α0 = 0.04 and update step α(t) = α0αT /(αT + t) were used, where t denotes the training iteration and αT = 5N, with N being the training set size. The parameter σp was initialized to the value of within-data variance, and updated by schedule described in Section 3 with σT = 5N. Validation was done using 10% of the training data. Number of prototypes K was set to 100.

SMP-Rank was compared to simple 1-NN rule, instancebased Mallows (IB-Mal) and Plackett-Luce (IB-PL) models, two log-linear label ranking models (Lin-LL and Lin-PL), and to the PW approach [H¨ullermeier et al., 2008] that uses RBF kernel SVM classifiers as base models. Preliminary results showed that using TOUGH aggregation with PW instead of originally proposed Soft-Borda greatly improves performance, therefore TOUGH was used with PW. For IB algorithms, the neighborhood size k ∈ {5, 10, 15, 20} was selected through cross-validation.

Table 1 shows the results obtained using training data with complete rankings, 30% and 60% of missing labels (partial orders), and 30% missing preferences. The results are given in terms of average lossLR (1) after five repetitions of a tenfold cross-validation. Partial orders were simulated by removing uniformly at random a certain percentage of labels from the training data. Missing preferences were simulated by removing uniformly at random a percentage of pairwise preferences. Since only SMP-Rank and PW can learn from partial preferences that do not form an order, only these two algorithms were compared in this setting. To account for missing preferences between labels yi and yj, SMP-Rank simply ignored fields Y(i, j) and Y(j, i) during training.

It can be observed that SMP-Ranktough achieved the best overall accuracy and consistently outperformed the competitors, particularly on large data sets and when confronted with the missing label problem. For example, it outperforms the best considered algorithm (PWtough) 16 out of 22 times for 60% missing labels, while the worst-performing algorithm (Lin-LL) is outperformed 20 out of 22 times.

The dominance over the IB-based algorithms can be explained by the fact that the performance of IB algorithms is highly dependent on the quality of the training data, since no abstraction is made during the training phase. Clearly, it is advantageous to use a model that abstracts over more data, thus alleviating influence of noise. If we try to achieve this by considering a larger number of neighbors in the IB algorithms, we start ignoring distances between an instance and its neighbors as a similarity measure. On the other hand, SMP-Rank generalizes training data to produce a representation in terms of prototype vectors, effectively utilizing distances to prototypes as a similarity measure.

6 Conclusion

We introduced SMP-Rank algorithm for prediction of label rankings with a novel pairwise preference aggregation algorithm for which we prove the worst-case guarantee. The algorithm is capable of operating in an online manner, it is memory-efficient since it operates on predefined budget, and it carries out pairwise preference aggregation more accurately than the previously proposed methods. Empirical investigation indicates that SMP-Rank produces better results than the current state-of-the-art, especially when learning from incomplete label preferences where the performance is improved by the largest margin.