Plackett-Luce Networks for Dyad Ranking

Abstract

We propose a new method for dyad ranking, a problem that was recently introduced in the realm of preference learning. Our method, called PLNet, combines a statistical model for rank data, namely the Plackett-Luce model, with neural networks (feed-forward multi-layer perceptrons) in order to learn joint-feature representations for dyads, which are pairs of objects from two domains. The e cacy of PLNet is shown by comparing it experimentally with state-of-the-art methods for dyad and label ranking.

Keywords

• Preference learning
• dyad ranking
• Plackett-Luce model
• multi-layer perceptrons

Introduction

A speci c problem in the realm of preference learning [ 7 ] is the problem of label ranking, which consists of learning a model that maps instances to rankings (total orders) over a nite set of prede ned alternatives [ 20 ]. An instance, which de nes the context of the preference relation, is typically characterized in terms of a set of attributes or features; for example, an instance could be a person described by properties such as sex, age, income, etc. As opposed to this, the alternatives to be ranked, e.g., the political parties of a country, are only identi ed by their name (label), while not being characterized in terms of any properties or features.

In [ 17 ], we introduced dyad ranking as a practically motivated generalization of the label ranking problem. In dyad ranking, not only the instances but also the alternatives are represented in terms of attributes|a dyad is a pair consisting of an instance and an alternative. Moreover, for learning in the setting of dyad ranking, we proposed an extension of an existing label ranking method based on the Plackett-Luce model, a statistical model for rank data. This approach is based on modeling latent utility scores of dyads in the form of a Kronecker product of the feature representations of the instance and alternative, respectively, which is why we speak of a bilinear Plackett-Luce model.

In this paper, we propose a variant of this approach, called PLNet, that allows for modeling latent utilities in a more exible way. Instead of assuming a bilinear structure of the joint-feature representation, we model utilities as (feedforward) neural networks; thanks to the hidden layer of such networks, important non-linear dependencies can thus be captured [ 16 ].

The rest of the paper is organized as follows. We provide a formal description of the dyad ranking problem in Section 2 and an overview of related methods in Section 3. Our new method PLNet is described in Section 4. Experimental results are presented in Section 5, prior to concluding in Section 6. 2

Problem Setting

Formally, a dyad is a pair of feature vectors z = (x; y) 2 Z = X Y, where the feature vectors are from two (not necessarily di erent) domains X and Y. A single training observation n (1 n N ) takes the form of a dyad ranking n : z(1) z(2) : : : z(Mn); Mn 2; (1) the length Mn of which can vary between observations in the data set D =

N f ngn=1. An equivalent notation for a single training example that will be used later on is a set of dyads

%n = nz(1); z(2); : : : ; z(Mn)o together with a permutation n : f1; : : : ; Mng ! f1; : : : ; Mng indicating how these dyads are ranked.

The task of a dyad ranking method is to learn a ranking function that accepts as input any set of (new) dyads and produces as output a ranking of these dyads.

An important special case, called contextual dyad ranking, is closely related to label ranking [ 17 ]. As already mentioned, the label ranking problem is about learning a model that maps instances to rankings over a nite set of prede ned choice alternatives Y = fy1; : : : ; yK g. In terms of dyad ranking this means that all dyads in an observation share the same context x, i.e., they are all of the form z(j) = (x; y(j)); in this case, (1) can also be written as n : x; y(1) x; y(2) : : : x; y(Mn) : (2) Likewise, a prediction problem will typically consist of ranking a subset ny(1); y(2); : : : ; y(M)o

Y in a given context x. Contextual dyad ranking generalizes label ranking by considering feature vectors instead of labels. This includes vector space embeddings of labels and additional descriptions (side-information) about labels. Contextual dyadic preferences are equivalent to training triplets of the form y(1) x y(2), which are encountered frequently in applications such as similarity learning.

Related Work

The Bilinear Plackett-Luce model (BilinPL) for dyad ranking was introduced in [ 17 ]. It builds on a statistical ranking model introduced by Plackett and Luce [ 14 ] and represents the parameters of this model as a log-bilinear function f (x; y) = exp g(x; y), which takes as input the dyad member feature vectors x and y. The output of the function is a real positive value, which can be interpreted as a utility score. The bilinear function g(x; y) = x>W y can equivalently be expressed as the function g(x; y) = hw; x yi, i.e., the dot product between a weight vector and a joint-feature vector consisting of cross-products (also known as the Kronecker product). This kind of joint-feature vector formulation strongly depends on the dyad feature vectors, and the representation bias it imposes on the model can be suboptimal.

Comparison training refers to a framework introduced for learning from pairwise preferences with a neural network [ 19 ]. The network architecture consists of two subnetworks which are connected to a single output node and indicates which of the two inputs is preferred over the other. The weights associated with the last hidden layer of one subnetwork is the mirrored version of the other subnetwork's weights. This setup solves two principal problems, namely e ciency and consistency. In the evaluation phase it is su cient to use just one subnetwork and evaluate n alternatives instead of O(n2) pairs. Furthermore, this kind of network architecture also enforces transitivity of the predicted preferences. Although many modi cations of the original comparison training have been proposed in the past (see e.g. the survey [ 6 ]), its inputs however are essentially restricted to pairwise training signals.

The aforementioned label ranking problem has been tackled with neural network approaches previously [ 15, 11 ]. A multi-layer perceptron (MLP) has been utilized to produce recommendations on meta-heuristics (labels) on di erent meta-features (instances) within the realm of meta-learning [ 11 ]. This kind of neural network exhibits an output layer with as many nodes as there are labels. The error signal used to modify the network's weights is formed by using the mean squared error on the target rank positions of the labels. In [ 15 ] more e ort has been spent to incorporate label ranking loss information into the backpropagation procedure. To this end some variations for this procedure have been investigated. Both architectures are similar to each other and have two essential limitations: rst, they depend on a xed number of labels, and second, they cannot cope with incomplete ranking observations. In addition, they lack the ability to provide probabilistic information on their predictions.

In the domain of information retrieval, the neural network-based approaches RankNet and ListNet have a probabilistic foundation [ 2, 3 ]. RankNet [ 2 ] uses pairwise inputs to learn a utility scoring function with the cross entropy loss. To this end, the training data consists of sample pairs together with target probabilities. These quantify the probability to rank the rst sample higher than the second. With the introduction of target probabilities, this approach enables the possibility of modeling ties between samples. ListNet [ 3, 13 ] similarly uses the cross entropy as a metric, but in contrast to RankNet it processes lists of samples instead of pairwise preferences as basic observation. There are, however, some important di erences between ListNet and our approach: { The learning approach in ListNet addresses only a special case of the Plackett

Luce distribution, namely the case of Top-k data with k = 1. { In ListNet, a linear neural network is used. This is in contrast to our approach, in which non-linear relationships between inputs and outputs are learned. Linearity in the ListNet approach implies that much emphasize must be put on engineering joint feature input vectors. { In ListNet, the query-document features are associated with absolute scores (relevance degrees) as training information, i.e., quantitative data, whereas PLNet deals with rankings, i.e., data of qualitative nature.3 ListNet as well as RankNet expect single instance joint-feature vectors x = (q; d) as inputs that are created from query-document pairs (q; d) via featureengineering. These approaches are closely related to our method, though with the major di erence of ranked dyads instead of absolute ratings as training input; and perhaps more importantly, our goal is to learn joint-feature representations instead of engineering them. 4

Plackett-Luce Network

Throughout this section we use the following notation. A ranking of dyads is represented in terms of a permutation . More speci cally, given a numbering of dyads from 1 to M , let (i) be the number j of the dyad put on the i-th position in the ranking; the inverse 1(j) denotes the rank position of the dyad speci ed by index j. 4.1

Plackett-Luce Model

The Plackett-Luce (PL) model is a parameterized probability distribution on the set of all rankings over a set of alternatives y1; : : : ; yK . It is speci ed by a parameter vector v = (v1; v2; : : : ; vK ) 2 R+K , in which vi accounts for the (latent) utility or \skill" of the option yi. The probability assigned by the PL model to a ranking with a permutation is given by

K P( j v) = Y

v (i) i=1 v (i) + v (i+1) + : : : + v (K)

K 1 = Y i=1

v (i) PK j=i v (j) (3) Obviously, the Plackett-Luce model is only determined up to a positive multiplicative constant, i.e., P( j v) P( j s v) for all s > 0.

As an appealing property of the PL model, we also note that its marginal probabilities (probabilities of rankings on subsets of alternatives) are easy to compute and can be expressed in closed form. More speci cally, the marginal of a PL model on M < K alternatives yi(1); : : : ; yi(M) is again a PL model with parameters vi(1); : : : ; vi(M). 3 The use of query-document-associated scores as PL model parameters is arguable. 4.2

Architecture

The core idea of the Placket-Luce Network (PLNet) is to learn (latent) utility functions u = g(x; y), where g is a single multi-layer feed-forward neural network. Since we are interested in utility scores that re ect rankings, we utilize the Plackett-Luce model and express its real-valued skill parameters as functions of the form log(v) = u = g(x; y). Thus, probabilities of rankings are given by

K 1 P ( j %; u) = Y k=1

exp(u (k)) PK l=k exp(u (l)) : (4) The PLNet is a multi-layer perceptron (MLP), which is constructed as shown in Figure 1. It consists of multiple layers and takes as input two vectors corresponding to the members of a dyad. There is at least one hidden layer with nodes using a sigmoidal activation function to learn non-linear mappings. The output layer produces a scalar value of the form u = hwL; aL 1i+bL. Technically, a bias term bL is actually not needed, as it has no e ect on the PLNet model (4): With the choice of the exponential function (to ensure positivity of the parameters v) and the independence of bL of the inputs x and y, we have v = exp hwL; aL 1i + bL = bL exp hwL; aL 1i ; and as noted before, the PL model is invariant toward multiplication of the weights with a positive scalar.

layers input 1 hidden

L-1 output

L x1 xr y1 yc 1 u Fig. 1. PLNet architecture. This kind of feed-forward neural network is composed of several layers. Dyad members z = (x; y) are entered at the input layer, whose nodes are fully connected with the nodes of the next layer. Inner (hidden) layers have nodes endowed with a non-linear activation function. The output layer consists of a single node with linear activation function. 4.3

Training

The training procedure uses back-propagation, which is a gradient technique to nd optimal weights [ 16 ]. Following [ 1 ], a feed-forward network can be seen as a framework for modeling the conditional probability distribution. For a set of training data f%n; ng with

%n = n x(n1); y(n1) ; : : : ; x(nMn); y(nMn) o ; the likelihood can be written as

L =

Y P(%n; n) = n

Y P( n j %n)P(%n) n if we assume the observations f%n; ng to be independent and identically distributed. It is generally more convenient to minimize the logarithm of the likelihood, hence we aim to minimize the following error function:

E = ln L =

X ln P( n j %n) n

X P(%n) n (5) The second term in (5) can be dropped, as it does not depend on the network parameters (and only represents an additive constant). More speci cally, we denote the negative log-likelihood (NLL) by E = Pn En, where En = log P ( n j %n; u) =

Mn 1 Mn X log X exp u (l) k=1 l=k

Mn 1 X k=1 u (k) : (6) The errors propagated back to the network can thus be expressed as the (partial) derivatives of the NLL:

L i

Mn 1 1 X

f k=1

1(i) kg exp(ui) PlM=nk exp(u (l)) 1fi Mn 1g (7) Note that the calculation of the error in (7) depends on all the Mn utilities of a training sample. To this end, we propose a training procedure as depicted in Figure 2, where we run Mn feed-forward calculations for a sample (consisting of Mn dyads) in parallel to obtain utility values. The -values obtained according to (7) can then be used for the standard back-propagation procedure on each of the parallel Mn copies of the master network. After performing the weight updates individually, the master's weights can be updated by aggregating the individual weight changes. In the implementation we applied the following simple strategy: wji = wji wjki, 1 k Mn, where denotes the learning rate. The procedure is then repeated several times with the training samples and stopped when the error has diminished su ciently.

Another point to be mentioned is regularization. Here, we suggest to use early stopping by tracking the NLL values of the training and validation data during the learning process. A good point to stop the training and to prevent over- tting is when the validation NLL values begin to rise again. x1 3.gCalculategM-manygLδhs usinggNLLgderivativesg In order to apply PLNet on the problem of label ranking, one needs a vector representation for labels. Unless other label features are available, a natural approach is to a use 1-of-K encoding. Thus, given K labels, the i-th label is represented by the vector ei 2 f0; 1gK with entry 1 at position i and 0 otherwise. 5

Experiments

In the following experiments, the predictive performance is measured in terms of the Kendall's tau coe cient [ 12 ], a rank correlation measure commonly used in the statistical and preference learning literature [ 20, 21 ]. It is de ned as =

C( ; ^)

K(K

D( ; ^) 1)=2 ; (8) with C and D the number of concordant (put in the same order) and discordant (put in the reverse order) label pairs, respectively, and K the length of the rankings and ^ (number of alternatives). Kendall's tau assumes values in [ 1; +1], with = +1 for the perfect prediction ^ = and = 1 if ^ is the exact reversal of . 5.1

Synthetic Data

Here, we compare the dyad ranking methods PLNet and BilinPL. To this end, we sample from a PLNet with three layers. Its inputs are dyads composed of one-dimensional vectors, i.e., x; y 2 [ 1; 1]. The hidden layer has 25 nodes and all weights are initialized at random by sampling from the uniform distribution in [ 15; 15]. From a total of 400 dyads, we sample 500 training and 50 test rankings consisting of 5 dyads each.

For the BilinPL, we choose from three di erent variants of input features. They are based on the Kronecker product between object pair features to from joint-feature vectors (resulting in rst and second order models): xf yf ) zf

Identi er x y [x y] BilinPL-1 [x; 1] [y; 1] [x; y; xy; 1] BilinPL-2 [x; x2; 1] [y; y2; 1] [x; x2; y; y2; xy; xy2; x2y; x2y2; 1] BilinPL-3

Table 1 and the corresponding Figure 3 underpin two key aspects. Firstly, the expressiveness of PLNet can be much larger compared to the BilinPL versions. Secondly, the predictive quality varies strongly for BilinPL depending on the choice of the dyad features. A suite of benchmark data sets have been established for the label ranking setting [ 4 ].4 They are based on 16 well known multi-class and regression data sets from the UCI repository and processed in two ways to address the ranking problem (see Table 2 for their properties). For data sets of type A (multi-class problems), rankings were generated by training a naive Bayes classi er on the complete data set and ordering the class labels according to the predicted class probabilities for each example. For data sets of type B (regression problems), a subset of instance attributes are removed from the data sets and were interpreted as labels. Rankings were then obtained by standardizing the attributes and then ordering them by size. This approach is justi ed by assuming that the original attributes are correlated and the remaining features contain information about the rankings of the removed attributes.

We compare the performance of PLNet to other state-of-the-art label rankings methods on these data sets using 10-fold cross-validation. For PLNet, we use three layers with 10 neurons for the hidden layer. In addition to BilinPL, we include Ranking by Pairwise Comparison (RPC, [ 10 ]), Constrained Classi cation (CC, [ 8, 9 ]), and the log-linear model for label ranking (LL, [ 5 ]) as additional baselines.5 For BilinPL, we chose as dyad features xf = [x; 1] and yf(i) = ei, which by means of the Kronecker product results in a joint-feature vector representation called multi-vector [ 18 ].

The results (see Table 3) indicate that PLNet is competitive to the other approaches and most of the time even superior. The performances on data sets where PLNet is less powerful also show its weakness. For data sets consisting of only a few instances but many attributes, PLNet is likely to over- t. Of course, another issue is the choice of the architecture itself (how many layers, how many nodes, ...). Linear models are advantageous in comparison to PLNet if their inductive bias is correct, which is the case, for example, for the fried problem. 6

Conclusion

We introduced a new method for the problem of dyad ranking, called PLNet. The method exhibits some interesting properties, notably the following: it is 4 Available online at https://www-old.cs.uni-paderborn.de/fachgebiete/intelligentesysteme/software/label-ranking-datasets.html. 5 CC was used in its online variant as described in [ 10 ]. probabilistic in nature, can handle incomplete rankings, and builds on standard neural network components. Thus, it is possible to improve the method further with techniques developed in the neural networks literature during the last years, especially with recent advances in deep learning. This point is an important aspect of future research. The study of other neural network architectures such as (restricted) Boltzman machines for dyad ranking are also conceivable.

References

1. Christopher M. Bishop . Neural Networks for Pattern Recognition . Oxford University Press, Inc., New York, NY, USA, 1995 .

2. Chris Burges , Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender . Learning to rank using gradient descent . In Proceedings ICML, 22nd International Conference on Machine Learning , pages 89 { 96 , New York, NY, USA, 2005 . ACM.

3. Zhe Cao , Tao Qin, Tie-Yan Liu , Ming-Feng Tsai , and Hang Li . Learning to rank: From pairwise approach to listwise approach . In Proceedings ICML, 24th International Conference on Machine Learning , pages 129 { 136 , New York, NY, USA, 2007 . ACM.

4. Weiwei Cheng, Jens Huhn, and Eyke Hullermeier. Decision tree and instance-based learning for label ranking . In Proceedings ICML, 26th International Conference on Machine Learning , pages 161 { 168 , Montreal, Canada, June 2009 . Omnipress.

5. Ofer Dekel , Yoram Singer, and Christopher D Manning . Log-linear models for label ranking . In S. Thrun, L. K. Saul , and B. Scho lkopf, editors, Advances in Neural Information Processing Systems 16 (NIPS-2003) , pages 497 { 504 . MIT Press, 2003 .

6. Johannes Fu rnkranz. Machine learning in games: A survey . In Johannes Furnkranz and M. Kubat, editors, Machines that Learn to Play Games, chapter 2 , pages 11 { 59 . Nova Science Publishers, Huntington, NY, 2001 .

7. Johannes Fu rnkranz and Eyke Hullermeier . Preference Learning . Springer, New York, NY, USA, 2011 .

8. Sariel Har-Peled , Dan Roth , and Dav Zimak . Constraint classi cation: A new approach to multiclass classi cation . In Proceedings ALT, 13th International Conference on Algorithmic Learning Theory.

9. Sariel Har-Peled , Dan Roth , and Dav Zimak . Constraint classi cation for multiclass classi cation and ranking . In S. Becker, S. Thrun , and K. Obermayer, editors, Advances in Neural Information Processing Systems 15 , pages 809 { 816 . MIT Press, 2002 .

10. Eyke Hullermeier, Johannes Furnkranz, Weiwei Cheng, and Klaus Brinker. Label ranking by learning pairwise preferences . Arti cial Intelligence , 172 ( 16 ): 1897 { 1916 , 2008 .

11. Jorge Kanda , Carlos Soares, Eduardo R. Hruschka , and Andre Carlos Ponce Leon Ferreira de Carvalho . A meta-learning approach to select meta-heuristics for the traveling salesman problem using MLP-based label ranking . In Proceedings ICONIP, 19th International Conference on Neural Information Processing , pages 488 { 495 , Doha , Qatar, 2012 . Springer.

12. M. G. Kendall . A new measure of rank correlation . Biometrika , 30 ( 1 /2): 81 { 93 , 1938 .

13. Tianyi Luo , Dong Wang, Rong Liu, and Yiqiao Pan . Stochastic top-k listnet . In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing , pages 676 { 684 , Lisbon, Portugal, September 2015 . Association for Computational Linguistics .

14. John I. Marden. Analyzing and Modeling Rank Data . Chapman & Hall , 1995 .

15. Geraldina Ribeiro , Wouter Duivesteijn, Carlos Soares, and Arno J. Knobbe . Multilayer perceptron for label ranking . In Proceedings ICANN, 22nd International Conference on Arti cial Neural Networks , pages 25 { 32 , Lausanne , Switzerland, 2012 . Springer.

16. David E. Rumelhart , Geo rey E. Hinton , and Ronald J. Williams . Learning representations by back-propagating errors . Nature , 323 : 9 , 1986 .

17. Dirk Schafer and Eyke Hullermeier. Dyad ranking using a bilinear Plackett-Luce model . In Proceedings ECML/PKDD{2015, European Conference on Machine Learning and Knowledge Discovery in Databases, Porto, Portugal . Springer.

18. Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms . Cambridge University Press, New York, NY, USA, 2014 .

19. Gerald Tesauro . Connectionist learning of expert preferences by comparison training . In D. Touretzky, editor, Advances in Neural Information Processing Systems 1 (NIPS-1988) , pages 99 { 106 . Morgan Kaufmann, 1989 .

20. Shankar Vembu and Thomas G artner. Label ranking algorithms: A survey . In J. Furnkranz and E. Hullermeier, editors, Preference Learning , pages 45 { 64 . Springer-Verlag, 2011 .

21. Yangming Zhou , Yangguang Liu, Jiangang Yang, Xiaoqi He , and Liangliang Liu . A taxonomy of label ranking algorithms . Journal of Computers , 9 ( 3 ): 557 { 565 , 2014 .