Qinghua Liu

Marta Crispino

Ida Scheel

Valeria Vitelli

Arnoldo Frigessi

Model-based learning from preference data

Keywords: Preference learning with uncertainty, Mallows model, Plackett-Luce model, recommender systems, Bayesian inference, Bradley-Terry model

published or not. The documents may come

Introduction

Massive Online Open Courses (MOOC) are offered by many universities. Thousands of students sign up for the most popular MOOCs and this has lead to challenges in grading so many written exams. One way to evaluate exams is to let the students themselves check the exams of their peers. All the exams are distributed to students, assigning a small set of exams to each student. Every exam is assigned to several assessors. Every student acts as an assessor and ranks the exams he has been assigned. The task is then to aggregate all these partial rankings into a full ranking of all exams, on the basis of which grades are given: the top 5% receive an A and so on, see for instance [START_REF] Fang | RankwithTA: A robust and accurate peer grading mechanism for MOOCs[END_REF], [START_REF] Raman | Bayesian ordinal peer grading[END_REF]. This is an example of rank aggregation, where the aim is to summarize the preferences or opinions about a set of items expressed by a group of assessors. Voting systems, where every individual ranks a list of candidates, are another common application of rank aggregation [START_REF] Jacques | Model-based clustering for multivariate partial ranking data[END_REF]. Search result aggregation, as performed for example by metasearch engines [START_REF] Desarkar | Preference relations based unsupervised rank aggregation for metasearch[END_REF], is another form of compiling a consensus ordering of items from independent rankings.

In other situations, the aim is not to produce a consensus ranking of the items, but to estimate the ranking of each individual assessor, when she has only given partial information on her preferences pertaining the items. Recommender systems [START_REF] Aggarwal | Recommender systems[END_REF] are algorithms that select, among many, the items which each individual user of a system is likely to be mostly interested in, beyond the ones she has already interacted with. Web-based, video-on-demand companies (like Netflix or Spotify), where customers log-on to their individual accounts, use expressions of preferences made by each customer to predict new videos (items) which she is likely to find attractive. Preference learning is about inferring individual preferences to perform personalized recommendations [START_REF] Agarwal | Statistical methods for recommender systems[END_REF].

This paper is concerned with statistical methods for rank aggregation and individual preference learning. Since these types of problems and the corresponding rank data are very common and important, the literature is vast, see for example the excellent books by [START_REF] Marden | Analyzing and Modeling Rank Data[END_REF], Alvo & Yu (2014), [START_REF] Ricci | Recommender systems: introduction and challenges[END_REF] and [START_REF] Fürnkranz | Preference learning: An introduction[END_REF]. Many methods are not based on statistical models, and do not allow for quantification of the uncertainty of the predictions. The Borda counts method [START_REF] Lansdowne | Applying the borda ranking method[END_REF] for example, is an easy and classical way of computing rank averages, but is not probabilistic. Machine learning approaches for learning to rank and rank aggregation, are often optimizing some objective functions, as in [START_REF] Kemeny | Mathematical models in the social sciences[END_REF], but often do not provide uncertainty quantification of the estimates. In this paper we focus on probabilistic methods for rank aggregation and individual preference learning, based on statistical models that allow for uncertainty quantification. We present the most important approaches and illustrate their usage.

There are three main objectives when assessors (users) rate, rank or compare items: (i) aggregate the data coming from a group of homogeneous assessors, and summarize their preferences into a shared consensus ranking of the items; (ii) estimate for each assessor her individual ranking of the items, when the assessors express only incomplete preferences; this amounts to predicting the ranks of (all or some of) the unranked items at the individual level; (iii) cluster the assessors into groups, each sharing a consensus ranking of the items, and classify new assessors. Often objective (iii) appears in combination with the other two, because the assessors are not all sharing a common preference.

Data is usually classified into two main classes: (i) explicit data, when assessors express a direct opinion about some items, in the form of a rating (by assigning likes, stars), of a ranking (by ordering some items according to their preferences), or of pair comparisons (by indicating which of two items they prefer); (ii) implicit data, when assessors express an indirect preference by choosing some items and not others, in the form of clicking/buying/watching, in general interacting with an item, chosen among several possible ones.

The type of data is application dependent. When there are many items to compare or when the subjective preference is complicated, it is often easier for assessors to compare items in pairs rather than ranking several items at the same time. Another typical situation where pairwise comparison data arise is tournament data, when two players or teams play against each other, see [START_REF] Glickman | Parameter estimation in large dynamic paired comparison experiments[END_REF]. In this paper we will deal with both explicit and implicit data, appearing in three forms: full rankings of all items, partial rankings of some items, and pairwise comparisons of some items.

Once a consensus ranking or an individual ranking is estimated, it can be used in subsequent decisions. In the MOOC example, grades are assigned to each exam; in the recommender system example, a set of items is suggested to each user. These downstream activities can be, and actually often are, challenging and inferential in nature. Where should be the threshold between grade A and B? How many items should be recommended because they are likely to be liked by the user ("exploit") and how many should be suggested among other types of items ("explore")? In this paper we will not discuss these following problems. However, uncertainty quantification of the estimated consensuses and individual rankings, as well as class memberships when clustering is involved, appears to be of fundamental importance. Actions based on unreliable predictions might better be postponed until more data is available and safer predictions can be made. A very natural approach to uncertainty quantification is the Bayesian approach, and in this paper Bayesian inference will play an important role.

This paper is organized as follows. In Section 2 we introduce the mathematical notation. Section 3 is dedicated to methods: first for consensus learning (Section 3.1) and then for individual preference learning (Section 3.2). Then we illustrate several methods in Section 4. The purpose is to see various approaches in action and we do this with the help of a compact dataset, namely our potato ranking data. We explain the differences between the various methods, and the contexts when they are most appropriate. Section 5 is dedicated to a larger, this time simulated, example, where assessors are heterogeneous to meet goal (iii). We conclude with a short discussion of aspects which were not discussed in this paper.

Notation

A full ranking of n items is a mapping R : A → P n from a finite set A = {A 1 , ..., A n }, the set of labeled items to be ranked, to the space of n-dimensional permutations P n . This results from the attribution of a rank R i ∈ {1, ..., n} to each item A i , according to some criteria. We denote a full ranking of all items as R = (R 1 , ..., R n ). By convention, R i < R k means that item A i is preferred to item A k , since the rank assigned to A i is lower than the one assigned to A k (the most preferred item has rank 1), but is read A i is ranked higher than A k . The full ordering of the n items is an alternative way of representing ranking data, and is denoted by X = (X 1 , ..., X n ). Here the components are items in A, ordered from the most preferred to the least, according to R. In other words, we have:

X i = A k ⇐⇒ R k = i, ∀i, k = 1, ..., n.
For this we use the shorthand, X = R -1 . Then X ∈ X n is the set of permutations of the labels in A.

For example, given the following full ranking of the items labelled 7, 8, 2, 10, 4, 6, 9, 3, 5 , the corresponding ordering vector is the following:

A = {A 1 , ..., A 10 } A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 ( ) R = 1,
3 1 2 3 4 5 6 7 8 9 10 ( ) X = A 1 , A 4 , A 9 , A 6 , A 10 , A 7 , A 2 , A 3 , A 8 , A 5 .
Some methods are naturally defined on rankings, while others, equivalently, on orderings.

Preferences are expressed by N users or assessors, indexed by j ∈ {1, ..., N }. The full ranking given by user j is denoted by R j , with components R ji , i ∈ {1, ..., n}.

There is an important relation between a ranking and pairwise preferences. For an unordered pair of items {A i , A k }, we denote a pairwise preference between the two items as

(A i ≺ A k ), if item A i is preferred to item A k .
Given a full ranking R ∈ P n , it is immediate to list all the possible n(n -1)/2 pairwise orderings among the items, according to the rule

(A t1 ≺ A t2 ) ⇐⇒ R t1 < R t2 , t 1 , t 2 ∈ {1, ..., n}, t 1 = t 2 . ( 1
)
We refer to the pairwise preferences obtained above as derived pairwise preferences (DPP), to distinguish them from real pairwise preferences (RPP), which arise when assessors compare items in pairs directly, rather than providing a full ranking. The main difference between DPP and RPP is that DPP are always complete and transitive, while RPP can be incomplete (if an assessor does not compare all the possible pairs), and non-transitive (if an assessor happens to contradict herself).

Methods

In this paper we group preference learning methods according to their tasks, namely (1) methods for learning the consensus ranking of a set of items by a group of assessors, or rank aggregation methods, and (2) methods for learning the individual rankings, when they are not readily available from the data, in order to perform personalized recommendations. In most practical situations, it is also necessary to partition the assessors into homogeneous groups, each one sharing a consensus ranking. In this section we assume that the group of users is homogeneous, while in Section 5 we will show an example requiring clustering of the users.

Most of the methods in this paper assume that items are characterized by a real-valued score (or utility). The score can be shared by a group of assessors, or each assessor can have her own score. The assessors' preferences depend on this score such that the item with a higher score at the moment of comparison has a tendency to be preferred to an item with lower score. When the task is rank aggregation, the purpose is to infer the shared latent score. In the case of learning individual ranking, the focus is on the assessors' individual scores, even though many methods also provide an estimate of the shared score. Other methods are based on a latent-ranking of the items, with a parameter varying in P n .

Methods for rank aggregation, inference on the consensus

We start with the class of so-called order statistics models, originating from the work of [START_REF] Thurstone | A law of comparative judgment[END_REF], who introduced the Law of Comparative Judgment.

Formally, the order statistics model assumes that in a ranking task involving n items, there exist n random score variables Y 1 , ..., Y n , assumed independent and each distributed according to its own distribution F i . The model then assigns a ranking R = (R 1 , ..., R n ) ∈ P n to the items according to the probability

P (R) = P (Y X1 < Y X2 < • • • < Y Xn |X = R -1 ).
(2)

Under the order statistics model, the generative process of a ranking of n items is determined by the relative ordering of the n random scores. The most common simplification of ( 2) is to assume an additive parametric model for the random scores, that is,

Y i = u i + i , i = 1, ..., n,
where the u i is the mean score associated with item A i and i captures its variability. Such models are known as Thurstone order statistics models. Depending on the choice of F i (y) = F (y -u i ) different models arise: the Gaussian assumption on F gives rise to the Thurstone model [START_REF] Thurstone | A law of comparative judgment[END_REF] and the Bradley-Terry-Luce (BTL) model [START_REF] Bradley | Rank analysis of incomplete block designs: I. The method of paired comparisons[END_REF][START_REF] Luce | Individual choice behavior: A theoretical analysis[END_REF] assumes that F is Gumbel. The probability in (2) has a closed form under the BTL model, therefore many works on order statistics ranking models are based on the BTL model. Based on data R 1 , ..., R N from N users, the purpose is to estimate the parameter vector u = (u 1 , ..., u n ), which can be converted to a consensus ranking by applying the rank transformation rank(u), defined as follows: Y = rank(u) if and only if

Y i = n h=1 1(u h ≥ u i ), i = 1, ..., n.
A different way to build a likelihood for the data R 1 , ..., R N is to transform these full rankings into pair comparisons, in the spirit of DPP. The most famous models in this class are the Mallows-Bradley-Terry (MBT) and the φ-and ρ-models, both developed by [START_REF] Mallows | Non-null ranking models[END_REF].

The MBT assumes that the probability that an item A i is preferred to an item A k in each comparison, P (A i ≺ A k ), has the Bradley-Terry form [START_REF] Bradley | Rank analysis of incomplete block designs: I. The method of paired comparisons[END_REF], P (A i ≺ A k ) = µi µi+µ k , where µ i > 0, i = 1, ..., n, and n i=1 µ i = 1. That is to say, it only depends on the item-specific score parameters of the two items under comparison (larger values of µ i correspond to more preferred items). The MBT model likelihood term for one assessor is then,

P (R|µ) = c(µ) n-1 i=1 µ n-Ri i , (3)
where c(µ) is the normalizing factor. If the N users express independent preferences, then the maximum likelihood estimate of µ = (µ 1 , ..., µ n ) is obtained by maximizing N j=1 P (R j |µ). Finally, the consensus ranking is obtained by ordering the vector of estimated scores using rank(µ).

The Plackett-Luce (PL) model [START_REF] Luce | Individual choice behavior: A theoretical analysis[END_REF][START_REF] Plackett | The Analysis of Permutations[END_REF] is a multistage ranking model. The PL model assumes that, given a vector of score parameters µ = (µ 1 , ..., µ n ), an ordering X arises through the following process: the top ranked item is A i with probability µi n k=1 µ k , i = 1, ..., n; then the second to the top item is chosen among the remaining items, excluding the item chosen as first, say A m , with renormalized multinomial probabilities µi k =m µ k , i = m; the process continues by excluding items already selected and renormalizing the multionomial probabilities, until a full ordering is obtained. The probability of an ordering X = (X 1 , ..., X n ) is

P (X|µ) = n-1 i=1 µ i n j=i µ j . ( 4
)
In view of the one-to-one correspondence between ordering and ranking vectors, the probabilities of eq. ( 4) can be converted to those for rankings R = X -1 , by performing a simple manipulation. Inferring the parameters of the PL model is typically done by maximum likelihood, using a Majorize-Minimization algorithm (see e.g. [START_REF] Hunter | MM algorithms for generalized Bradley-Terry models[END_REF].

Among the Bayesian approaches, [START_REF] Caron | Efficient Bayesian inference for generalized Bradley-Terry models[END_REF] proposed an efficient data augmentation scheme, which, combined with the introduction of a conjugate prior specification, allows to perform a Gibbs sampling for the PL parameters. Recently, Mollica & Tardella (2016b) developed the PLMIX R package, which provides basic functions to make Bayesian inference on the PL model parameters. Both [START_REF] Caron | Efficient Bayesian inference for generalized Bradley-Terry models[END_REF] and Mollica & Tardella (2016a) specify independent gamma priors for each element of the score parameter vector µ, that is, they assume the prior π(µ) = n i=1 Ga(µ i ; a, b). A different way of building statistical models for ranking data is to design appropriate distributions over the space of permutations P n , avoiding the use of a real valued score. A class of such models is the distance-based family of distributions for rankings, referred to as the Mallows model (MM) [START_REF] Mallows | Non-null ranking models[END_REF].

The MM, formalized in its general form by [START_REF] Diaconis | Group representations in probability and statistics[END_REF], assumes that the probability of an observed ranking decays as the distance between the ranking and the consensus increases. The probability of a ranking R = (R 1 , ..., R n )

∈ P n is P (R | α, ρ) = 1 Z n (α) exp - α n d(R, ρ) , (5)
where ρ ∈ P n is the location parameter (representing the shared true consensus ranking), α > 0 is the scale parameter (describing the concentration around the shared consensus), d(•, •) is a right-invariant distance function, which is unaffected by any relabelling of the items [START_REF] Diaconis | Group representations in probability and statistics[END_REF], between two n-dimensional permutations. Z n (α) is the partition function.

Depending on the choice of the distance, several models arise: the φ-model, originally proposed in [START_REF] Mallows | Non-null ranking models[END_REF], corresponds to the MM with the Kendall distance

d K (R, ρ) = i<k 1 [(ρ i -ρ k ) (R i -R k ) < 0] , 1 ≤ i < k ≤ n,
and the ρ-model [START_REF] Mallows | Non-null ranking models[END_REF] , ρ), which measures the minimum number of transpositions to convert R into ρ, and the Ulam distance d U (R, ρ), which is the number of deletion-insertion operations to convert R into ρ, see [START_REF] Marden | Analyzing and Modeling Rank Data[END_REF] for details. The Kendall distance, which measures the number of adjacent transpositions required to convert R into ρ or, equivalently, the number of discordant pairs in R and ρ, is by far the most popular one in the literature on the MM, mainly for computational reasons. The partition function Z n (α) exists in closed form only for some choices of right-invariant distances, in particular for the Kendall distance [START_REF] Lu | Effective sampling and learning for Mallows models with pairwise-preference data[END_REF][START_REF] Meilǎ | Dirichlet Process Mixtures of Generalized Mallows Models[END_REF], the Hamming distance [START_REF] Irurozki | Sampling and learning the Mallows and generalized Mallows models under the Hamming distance[END_REF] and the Cayley distance [START_REF] Irurozki | Sampling and learning mallows and generalized mallows models under the cayley distance[END_REF].

uses the Spearman's (l 2 ) distance d S (R, ρ) = n i=1 (ρ i -R i ) 2 . Other relevant distance functions are the footrule (l 1 ) dis- tance d F (R, ρ) = n i=1 |ρ i -R i | , the Hamming distance d H (R, ρ) = n - n i=1 1 ρi (R i ) , the Cayley distance d C (R
Inferencing on ρ in the MM by maximum likelihood is challenging. Assuming N observed rankings, {R 1 , ..., R N }, the maximum likelihood estimator for ρ is obtained as ρ = argmin ρ∈Pn N j=1 d(R j , ρ). The search space for ρ is P n , and computation is infeasible except for certain distances. [START_REF] Vitelli | Probabilistic preference learning with the Mallows rank model[END_REF] introduced a Bayesian approach for the Mallows model, which we will refer to as the Bayesian Mallows Model, or BMM. In the BMM, a uniform prior distribution is usually chosen for the consensus parameter ρ, π(ρ) = n! -1 . For the scale parameter α, an exponential prior may be employed, π(α) = λ α e λαα 1 [0,∞) (α). The hyper-parameter λ α is determined by tuning or by subjective reasonings, see [START_REF] Vitelli | Probabilistic preference learning with the Mallows rank model[END_REF]. The joint posterior distribution of ρ and α is given (up to a constant of proportionality) by

π(ρ, α|R (N ) ) ∝ π(ρ)π(α) [Z n (α)] N exp   - α n N j=1 d(R j , ρ)   . ( 6
)
Posterior samples of ρ and α can be obtained by applying a version of the Metropolis-Hastings algorithm. The Mallows models have parameters varying in the discrete space of all n! permutations of the integers 1, ...n, which is more structured than the continuous parameters in the MBT and PL models. We will see in some of our experiments that this makes a difference. On the other hand, the continuous parametrization is computationally advantageous.

Both distance and score based methods can be extended to data that originates from the comparison of items in pairs. For a complete review of these models, we refer to [START_REF] Cattelan | Models for paired comparison data: A review with emphasis on dependent data[END_REF]. The two traditional probabilistic models for pairwise comparison data is the [START_REF] Thurstone | A law of comparative judgment[END_REF] and the [START_REF] Bradley | Rank analysis of incomplete block designs: I. The method of paired comparisons[END_REF] models. Based on these, many extensions were derived in the past, mostly in the econometric and psychometric literatures. The models for pairwise comparison data are designed for real pair preferences (RPP), but can obviously be applied to derived pair preferences (DPP).

We here present the Bradley-Terry (BT) model, first proposed in [START_REF] Zermelo | Die berechnung der turnier-ergebnisse als ein maximumproblem der wahrscheinlichkeitsrechnung[END_REF], for which the probability of a pair comparison can be expressed in the form

P (A i ≺ A k |u) = 1 1 + e -(ui-u k ) = µ i µ i + µ k = P (A i ≺ A k |µ), (7)
where the transformation µ i = e ui , i = 1, ...n, shows the relation to the MBT model. The key assumption of the BT model is that all pairwise probabilities are conditionally independent given the vector of scores u (or µ), and that they depend only on the relative sizes of the corresponding score parameters. Suppose we have collected a number of pairwise comparisons among n items. Let W be the n × n data matrix with entries w ik being the number of times item A i is preferred to item A k among all assessors. Under the BT model, the likelihood of µ is

P (W |µ) = 1≤i =k≤n µ i µ i + µ k w ik . ( 8
)
The BT model has been generalized in several directions (see e.g. [START_REF] Crispino | On extending the Bradley-Terry model to accommodate ties in paired comparison experiments[END_REF][START_REF] Agresti | Categorical data analysis[END_REF][START_REF] Wu | Clustering and inference from pairwise comparisons[END_REF]. Maximum likelihood estimation is typically performed through iterative algorithms and Majorized -Minimization algorithms [START_REF] Hunter | MM algorithms for generalized Bradley-Terry models[END_REF]. In the Bayesian framework, the scheme of [START_REF] Caron | Efficient Bayesian inference for generalized Bradley-Terry models[END_REF], was specifically developed for the BT model.

The BT model has a major drawback: inference fails when the data is very sparse, and in particular when the strong connection condition [START_REF] Ford | Solution of a ranking problem from binary comparisons[END_REF] is not met. This condition guarantees the existence and uniqueness of the maximum likelihood estimates of the BT parameters. It holds for a data set if for any partition of the n items into two sets, some items in the second set have been compared to some items in the first set at least once by some assessor, see [START_REF] Yan | Ranking in the generalized Bradley-Terry models when the strong connection condition fails[END_REF]. This might not be the case in situations where only few comparisons have been made.

The BMM has also been extended to pair comparison data by means of data augmentation, see [START_REF] Vitelli | Probabilistic preference learning with the Mallows rank model[END_REF]. The underlying principle is to augment, for every assessor, her comparison data into a latent full ranking of all n items, which is compatible with the pair preferences. These augmented individual latent rankings Rj , for all assessors j, resemble the shared latent consensus ρ via (6). This construction assumes that the pair comparisons expressed by each assessor are transitive, that is, compatible with some latent R j . For example preferring item A 1 to item A 2 and this to item A 3 but then prefering A 3 to item A 1 would not be coherent. Crispino et al. (2018) extend the BMM to nontransitive pair comparsons, by adding a further component of the model which captures such mistakes (or incoherences) made by the individual user.

Methods for preference learning, inference on the individual rankings

Apart from performing rank aggregation or consensus learning, another main objective of preference learning is learning individuals' preferences, when not readily available from the data. This situation is common when the data is in the form of partial rankings (that is, when assessors only rank a subset of all items, typically their most preferred), or pairwise preferences (when each assessor is repeatedly asked to choose the preferred item in a number of pairs).

In such cases, the full individual ranking is unknown, and the interest is to infer it. Personalized recommendations can hence be made based on the inferred complete individual ranking: the recommended items are the ones on top.

The most popular approaches so far for recommender systems is the wellknown collaborative filtering (CF) method [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. Unlike the model-based approaches mentioned in the previous sections, CF does not produce an aggregation of group preferences, but is a method that only infers on personal preferences. CF is grounded on matrix factorization technique. Suppose we have an N × n sparse matrix R, which contains some explicit ratings given by N users to n items, as well as some missing values. Let κ be te set of (user, item) pairs, which are given (not missing). Typically |κ| << nN .

CF's goal is to obtain two factor matrices -a user matrix U ∈ R N ×L , in which each user is associated with a vector u j , and an item matrix V ∈ R n×L , where each item is associated with an item vector v i . Both u j ,v i ∈ R L , j = 1, ..., N , i = 1, ..., n. L is much smaller than n and N . The product U T V should approximate the non-missing entires κ of the matrix R, and otherwise filling out all missing entries. This matrix can then be used to make personalized recommendations. The latent factors U and V can be learned by optimizing the function min U,V

(j,i)∈κ (r ji -u i T v j ) 2 + γ(||u i || 2 + ||v j || 2 ). ( 9
)
The first term in the objective function describes the squared error between the data matrix R and the estimated product matrix. The second term is a ridgelike penalization term to avoid overfitting. Popular optimization techniques employed here include the Alternating Least Square and Stochastic Gradient Descent algorithms. The regularization parameter γ and choice of L are often selected by cross-validation. The dimension-reduction nature of the technique reveals its close relationship to singular value decomposition and principal component analysis.

Rating is a form of explicit expression of preference. Explicit feedback has the advantage of easy interpretation -it can reflect both positive and negative preference. However, there are also limitations. First, explicit feedbacks can be biased, some users tend to give high ratings to most items while others are stricter. Second, explicit feedbacks are more difficult to collect. In order to tackle these challenges, implicit feedback, such as clicking data, can be utilized. Clicking data arises naturally when users are interacting with an interface, therefore, is easy to collect and exists in abundance. The biggest challenge in handling click data is the interpretation of negative feedback and missing values. [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF] introduced a CF model that specifically handles implicit datasets. In this model, the user-item interaction is represented as r ji . For example, r ji can be the number of times a user has clicked on an item, or a measure of the extent to which a user has interacted with an item. In the case of movie streaming, r ji can say whether the user had seen the whole movie or only a part. Based on r ji , two sets of variables are defined. The first is binary and represents user preference x ij =1 {rij >0} . When x ij = 0, it indicates that user j has not expressed preference on item i, and should not be regarded as a negative feedback. A second set of variables, called "confidence" variables c ji , describe the strength of the preference. Different implicit feedbacks give the recommender various levels of confidence: for example, if a user finishes watching a movie, the level of positive preference is stronger than if the movie was only seen in part. In general, the level of confidence c ji has a positive correlation with r ji , and c ji often is modeled as a linear function on r ji , namely as c ji = 1 + αr ji .

As the CF model for explicit feedback, the goal of this model for implicit data is to obtain the latent user-and item-factors, by optimizing the following function:

min U,V (j,i)

c ji (x ji -u i T v j ) 2 + γ(||u i || 2 + ||v j || 2 ), (10)
and by cross-validating the dimension L, γ and α.

Once u i and v j are computed, then the ranking of all items for user j is obtained by ordering u i T v j for i = 1, ..., n, and this can be used to perform individual recomendation.

Among the probabilistic approaches for individual preference learning, we here mention two examples: the Bayesian Mallows model [START_REF] Vitelli | Probabilistic preference learning with the Mallows rank model[END_REF], and the Hierarchical Bradley Terry, HBT, model (Crispino & Frigessi, 2018, draft).

The model-based approach to individual preference learning recently proposed by [START_REF] Vitelli | Probabilistic preference learning with the Mallows rank model[END_REF] extends the BMM to handle the problem of individual preference learning. In the top-k rankings case the model is specified as follows. Suppose each assessor j has ranked the subset of items A j ⊆ {A 1 , A 2 , . . . , A n }, giving them top ranks from 1 to k j = |A j |. The data is then in the form of partial rankings, R 1 , ..., R N . The idea is to estimate the full latent rankings of each assessor, denoted by R1 , ..., RN , where for each Rj , the top-k j ranks are fixed and identical to the data. The idea of the model is to define these augmented latent vectors R1 , ..., RN , assuming they are i.i.d. given the Mallows model parameters ρ and α. The likelihood is then

P (R 1 , . . . , R N |α, ρ) = R1∈S1 • • • RN ∈S N P ( R1 , . . . , RN |α, ρ), (11)
where

S j = { Rj ∈ P n : Rij = R ij , ∀i ≤ n j }, j = 1, . . . , N
, is the set of rankings compatible with the partial information in the data R j . Inference in this model can be performed through an MCMC scheme with a data augmentation [START_REF] Tanner | The calculation of posterior distributions by data augmentation (with discussion)[END_REF] step to handle the estimation of the individual random rankings. The choice of prior distributions is the same as described in Section 3.1. Personalized recommendations can hence be made based on the inferred individual rankings Rj .

In the case of transitive pairwise comparisons, the BMM is specified as follows. Suppose each assessor j has performed a number of comparisons B j = {(A i ≺ j A k )} i =j∈{1,..n} , where the symbol ≺ j indicates the pairwise preference ordering of assessor j. The data is then a collection of sets, B 1 , ..., B N . Similarly to the top-k case, the idea is to estimate the full latent rankings of each assessor, where now the items seen by each assessor are, in general, not fixed to a given rank. Hence, each augmented latent vector Rj is required to agree, in the sense of eq. ( 1), with the partial information given in B j . The likelihood is

P (B 1 , . . . , B N |α, ρ) = R1∈T1 • • • RN ∈T N P ( R1 , . . . , RN |α, ρ), (12)
where, for each j, T j is the set of rankings compatible with the pairwise preferences in B j . This model was extended to non-transitive pairwise comparisons by Crispino et al. (2018).

Note that the BMM can also be applied to implicit data. In this case, the implicit data is first transformed into pairwise comparisons such that each each clicked item is preferred to each of the non-clicked items, and inference can hence be made using the pairwise comparison version of the BMM.

Another model-based approach to personalized preference learning is a recently proposed extension to the BT model, named Hierarchical Bradley Terry, HBT (Crispino & Frigessi, 2018, draft). As in the BT model, suppose that the preferences expressed by an assessor are pair comparisons as in ( 7), but now allowing the score parameters to vary from one assessor to another. In other words, denoting the parameter vector of assessor j by µ j = (µ j1 , ..., µ jn ), the probability that assessor j prefers item A i to item A k has the BT form

P (A i ≺ j A k |µ ji , µ jk ) = µ ji µ ji + µ jk . ( 13
)
The pairwise comparisons for assessor j depend only on the relative sizes of the individual score parameters of the items being compared. We denote by W j the n × n data matrix, where each element w jik is the number of times item A i was preferred to A k by assessor j. Assuming that the individual pairwise comparisons of assessor j are conditionally independent given µ j , the likelihood of µ 1 , ..., µ N is

P (W 1 , ..., W N |µ 1 , ..., µ N ) = N j=1 1≤i =k≤n µ ji µ ji + µ jk w jik . ( 14
)
The assessor specific parameters µ j are assumed a priori independent and distributed according to a gamma distribution with a common mean vector µ; for µ an inverse gamma prior is assumed. Inference on this model's parameters is performed with an extension of the Gibbs sampler of [START_REF] Caron | Efficient Bayesian inference for generalized Bradley-Terry models[END_REF].

Personalized recommendation in the HBT model is then performed by means of the estimated individual latent score parameters µ j . The individual full ranking of the items, which corresponds to the Rj rankings of eq. ( 11), can be obtained by the rank transformation rank(µ j ).

Comparing the three approaches, HBT, BMM and CF, we observe that each has a latent individual vector, namely µ j , Rj and the vector (u 1 T v j , ..., u T n v j ), respectively. The first and third are vectors with continuous real components; the second is a permutation of n integers. The product form of the parametrization of CF is much more sparse compared to the one of HBT, because L << n, N . This gives computational advantages, but it also results in less flexibility.

Preference learning in practice

In this section, we illustrate and assess the performance of the methods mentioned in Section 3 with a simple dataset. We purchased a bag of n = 20 potatoes (items), which were placed on a table, randomly labeled by letters A,B,C,D..., T. N = 12 assessors were asked to visually inspect the potatoes, and to rank them according to their weight, with rank 1 assigned to the heaviest and 20 to the lightest potato. There was no communication between assessors. After the experiment, each potato was weighed, thus obtaining the true ranking of the potatoes, denoted by ρ true . This dataset therefore contains N = 12 full rankings of n = 20 items.The data will be referred to as R N ={R 1 , ..., R N }, where each vector R j ∈ P n is the full ranking provided by assessor j. The purpose is not to compare the precision of the different methods, for which purpose a systematic study would be needed, but to illustrate the methods via a simple real data set. We aim at showing how the methods can be used, which choices must be made in order to perform the analyses, what results can be obtained and how they can be visualised. There is an interesting literature on how to compare methods that estimate rankings (see [START_REF] Gunawardana | Evaluating recommender systems[END_REF].

footrule, mse = 0.94 kendall, mse = 0.95 spearman, mse = 0.64

L M I J G N P Q K E A S T R F D B O
L M I J G N P Q K E A S T R F D B O
L M I J G N P Q K E A S T R F D B O

Estimating the consensus ranking

Inference from full rankings

In this section, we illustrate the performance of the BMM and the PL model as rank aggregation methods, when a full ranking of all items is given by each assessor. In the case of the BMM we use three different distance measures: the footrule, Spearman and Kendall distances. The exponential prior hyperparameter λ α was chosen to be λ α = 1/10 for the footrule and Kendall distances; and λ α = n/20 for the Spearman distance, following the recommendations in [START_REF] Vitelli | Probabilistic preference learning with the Mallows rank model[END_REF]. As n = 20, the partition function is computed exactly. We used the authors' R package (soon available on CRAN). For the analysis of the PL model, we exploit the PLMIX R package of Mollica & Tardella (2016b), setting the number of mixture components to 1, and with the default choices for the prior hyper-parameters in the gamma priors. The heatplots in Figure 1 represent the marginal posterior distribution of ρ obtained using the BMM. The x-axis represents the 20 potatoes, re-arranged according to their true weights in descending order. The y-axis lists the ranks and each column represents the posterior distribution of the corresponding potato, i.e. P (ρ i = k | R N ), for each potato i. These plots do not compare the estimated consensus rankings with the unknown group consensus ranking, but with the ranking based on the actual weights, i.e., ρ true . Comparing the estimated consensus with the known ρ true allows us to evaluate how the assessors performed as a group.

To assess the accuracy of the inferred group consensus ρ, incorporating the uncertainty associated with it, we use the posterior expected mean squared error (mse), defined as

mse = E 1 n ||ρ -ρ true || 2 2 R 1 , ...R N = 1 n n i=1 n r=1 (r-ρ true,i ) 2 P (ρ i = r | R 1 , ...R N ).
From Figure 1, it can be observed that the BMM is able to estimate a group consensus ρ that resembles ρ true well. Consistently in all three distances, BMM produces a consensus ρ with high accuracy for items L, M and I, the Plackett-Luce, mse = 1.45 top-weighed potatoes, as well as items C and H, the lightest potatoes. However, the consensus rankings of the potatoes in the middle-range, i.e. items K,E and A, are not estimated as accurately and certainly. This can be explained by the fact that the true weights of these potatoes are differed only by a few grams, and the assessors were not in agreement with each other regarding their rankings. We also notice that potato Q was ranked higher than its actual weight implied.

L M I J G N P Q K E A S T R F D B O
The choice of distances also affects the ranking aggregation performance of BMM. Shown in Figure 1, the footrule and Kendall distances produce very similar posterior distributions. This is consistent with [START_REF] Diaconis | Spearman's Footrule as a Measure of Disarray[END_REF], where it is proved that ∀r ∈ P n , d K (r, 1) ≤ d F (r, 1) ≤ 2d K (r, 1), where 1 = (1, ..., n). The Spearman distance produces a flatter marginal posterior distribution for each item. Overall, the Spearman distance has a slight edge in terms of mse in this case, and this is largely attributed to item Q, for which both the footrule and Kendall distances produce wrong estimations with a high degree of certainty.

Next we consider the same data and estimation problem, but apply the PL model. Since this method produces estimates of µ, we applied the rank transformation to obtain a ranking. In the case of the PL model, the marginal posterior distribution produced for each item is flatter and less certain compared to the BMM, as shown in Figure 2. Only for items C and H, the two bottomranked items, the PL model produces estimations with high certainty. All four estimations of the consensus indicate that the twelve assessors did a rather good job in evaluating the weight of our potatoes. Three medium-weight potatoes were difficult to rank: the estimated consensus obtained by the PL model and the BMM with the Kendall distance is rather uniform among a group of ranks. The BMM with the footrule and Spearman distances take a clearer decision. One potato (Q) was missplaced by most assessors: the BMM with the footrule and Kendall distances estimate its consensus rank most likely as fifth, which implies that the next potato (G) has to be sixth. For the PL model, the pattern is more uniform, because an estimate of µ Q does not force particularly µ G . We here see the difference between a continuous real-valued parametrization and one with permutations of n integers. We also see that the choice of the distance in the BMM matters.

Inference from top-k rankings

In this section, we illustrate the rank aggregation performance of the BMM and the PL model when each assessor j only ranks her top k j items, k j < n, exploiting a modified version of the potato dataset. We sample k j from a Poisson distribution truncated in the interval [1,17], and with the expected number of ranked items set to 7. After the k j -th item, further items are considered as missing values. Ten experiments are conducted using 10 different datasets. The parameters of both BMM and PL are chosen as in Section 4.1.1, and only the BMM with the footrule distance is discussed in this section.

The two left panels in Figure 3 show the heatplots corresponding to the first experiment run, summarizing the marginal posterior distribution for each item in the consensus ρ, using the BMM (left) and the PL model (middle). Both models, compared to the other items, produce clearer consensus estimations for the top-ranked items, i.e., items L, M and I, as there is sufficient and non-noisy information about these items. Both models also correctly produce uniform distributions for the 6 bottom-ranked items, since in this experiment run, no assessor included these 6 items in her top-k j ranked items. As a consequence there is no preference information regarding these items in the data (see also [START_REF] Vitelli | Probabilistic preference learning with the Mallows rank model[END_REF]. Consistently with the description in Section 4.1.1, the PL model produces a consensus estimation with more uncertainty compared to the BMM, and the BMM has a tendency to produce a more certain estimation on some items. Compared to the actual weight of the potato, BMM is making more mistakes for the middle-ranked potatoes. However, overall, as shown in the right panel of Figure 3, the BMM produces consensus estimation with lower mse (with respect to the true weight) compared to the PL model, consistently throughout all 10 runs of the experiment.

BMM, mse = 3.22

L M I J G N P Q K E A S T R F D B O

Inference form pairwise comparisons

In this section, we illustrate the rank aggregation performance of the BMM and the BT models when data is in the form of pairwise comparisons (RPP). We exploit the MCMC algorithm of [START_REF] Vitelli | Probabilistic preference learning with the Mallows rank model[END_REF] for making inference on the BMM parameters, and the Gibbs sampling of [START_REF] Caron | Efficient Bayesian inference for generalized Bradley-Terry models[END_REF] for making inference on the BT parameter.

We assume that each assessor j provides a fraction n j ≤ n(n -1)/2 of the possible pairwise preferences, using the potato dataset. Here, n j = n, ∀ j, and n is chosen deterministically, as we wish to control the number of pair comparisons made by each assessor. However the pairs that are actually compared are chosen uniformly at random among all pairs, without replacement. For each assessor j, we sample randomly n ≤ 190 different pairs of items {A i , A k } (i.e., the potatoes) from the collection of all possible pairs. We then assign the preference between the tested pair of potatoes according to the individual ranking R j , available in the full potato data. We are left with the data D N = {D 1 , ..., D N }, where each D j , j = 1, ..., N , is a collection of pairwise preferences in the form (A i ≺ j A k ), where, as in equation ( 1

), (A i ≺ j A k ) ⇐⇒ R ji < R jk , i, k = 1, ..., n, i = k. The notation (A i ≺ j A k ) means that item A i is preferred to item A k by assessor j.
We here investigate how the accuracy of the BMM and the BT is affected by data incompleteness. As such, we create 10 nested datasets, each containing a different number of pairs: from 10% of all available pairs, to 100% of available pairs (DPP). The datasets are nested in the sense that when we increase the fraction of pairs given to each assessor, we only add new pairs, hence ensuring that any changes in prediction accuracy is solely due to the increase of data availability.

As in the previous section, we conducted 10 experiments for each scenario to take care of the randomness involved in pairs selection. The BMM parameters are chosen as in Section 4.1.1, while for the BT we follow the specification of [START_REF] Caron | Efficient Bayesian inference for generalized Bradley-Terry models[END_REF]. Figure 4 shows the 95% confidence interval for the expected posterior mse for the different scenarios of data incompleteness, and for the two methods: BMM (black dots), and BT (red dots). The posterior sample of BT parameters µ was converted into a sample of rankings simply by applying the rank transformation, similarly to what we did with the PL parameters earlier.

It can be observed that the mse of both methods dramatically decreases when we increase the fraction of available pairs from 0.1 to 0.2. When 20% of pairwise comparisons are collected from each assessor, the BMM can already estimate the consensus ranking with reasonable accuracy, with an mse below 2. The BMM does not gain much prediction accuracy after we give each assessor more than 50% of all available pairs. The BT is considerably less accurate than the BMM when fewer pairs are given to the assessors (less than 30%), in terms of mse, but the two methods perform similarly as the number of pairs increases.

Individual preference learning

Here we consider the situation where assessors have expressed incomplete preferences and we are interested in completing the understanding of their individual prteferences.

Inference from top-k rankings

Consider the situation where the assessors rank only their top preferred items. Often it is of interest to recommend to each assessor her "next" items, in order of preference. For instance, given that an assessor j has ranked her top k j items,

95% CI for individual assessor and fitted exp model for mse

fraction of available pairs mse q q q q q q q q q q q q q q q q q q q q o o BMM BT it may be interesting to estimate which items are most likely to be ranked by the same assessor j as the (k j + 1)-th and (k j + 2)-th, which we call the "next two" items. Among the methods mentioned in Section 3, BMM produces complete augmented ranking vectors Rj for each individual j. We demonstrate how BMM makes inference on the "next m" (with m = 1 or 2) individual preferences, using the top-k potato datasets (with 10 repeated experiments) explained in Section 4.1.2, where the expected number of ranked items per assessor is 7. Notice that the potatoes are difficult to order in that range. The "next m" items recommended to each assessor j are those associated to the highest posterior probability of being her most preferred, among the items that assessor j did not rank. Such posterior probabilities are computed on the basis of the individual augmented latent ranking Rj as follows: for each assessor j, and each item i, we compute

P ij = P (k j + 1 ≤ Rij ≤ k j + m|R 1 , ..., R N ).
Then, for each assessor j, the m items associated with the highest posterior probabilities, P ij , are recommended to the assessor. Obviously, the items that are already ranked by an assessor are not considered for recommendations. After estimating the next m items for each assessor, we can compare the prediction with the original full potato dataset.

Table 1 presents the average number of correctly predicted next 1 and 2 items for the 12 assessors, with the 95% confidence intervals over 10 experiments. We compare the performance with the reference of choosing the recommended items at random among the non-ranked items. The expected value of this

E[number of correct random guesses] = m i=1 i • m i n-λ-m m-1 n-λ m
, where λ is the parameter of the truncated Poisson. BMM is able to correctly predict roughly 45% of the next 1 item, and 66% out of the next 2 items. The BMM makes a very large improvement for both next 1 and next 2 items compared to naive guess.

The Bayesian approach gives an estimate of the uncertainty of the prediction of the "next" items, namely the posterior probability P ij for the item i to be among the "next m" items for assessor j. Table 2 shows the summary of these probabilities across all assessors and all recommended items. The mean of the estimated P ij for m = 1 is 0.484. For some assessors, the probabilities are so low that the item should probably not be recommended. On the other hand, for m = 1, for more than 25% of the assessors the probability is above 0.5. All probabilities are larger for m = 2, because the item can be either of the "next two": the median is 0.673. Comparing the estimated mean of P ij , which is 0.484 for m = 1, with the average number of correctly predicted next 1 item shown in Table 1 (45%), and similarly for m = 2, we see that the BMM predictions are well calibrated, and the produced uncertainty is reliable. The results are rather good, given the diffiuclty of the potato data in the middle range.

Inference from pairwise comparisons

When the assessors perform pairwise comparisons, it is relevant to predict individual preferences that are not in the data, usually the "top" preferred items for an assessor. We here use the same datasets used in Section 4.1.3 to illustrate the performance of two methods: the BMM and the HBT. Both methods produce full augmented vectors, the latent ranking Rj (BMM) and the individual vector of score parameters µ j (HBT), one for each assessor j, which are then used to recommend items to the assessors.

After estimating the Rj and µ j , we can refer to the original R N data matrix, to check whether they are correctly estimated. Figure 5 shows the average posterior expected mse of the individual rankings of all assessors against the proportion of compared pairs in the data, for the two methods: BMM (black dots), and HBT (red dots). Since we know the true ranking of the assessors, in this case the comparison of this with the estimate is meaningful. It is clear that in terms of mse the BMM outperforms the HBT. As we mentioned before, this may be due to the fact that the BMM augments the partial information with full rankings in the space of n-dimensional permutations. For this reason, the number of possible rankings that are compatible with the partial information in the data is limited. The HBT on the other hand, augments the partial information in the data with the real-valued vectors µ j , j = 1, ..., N , which are much more variable. fraction of available pairs mse q q q q q q q q q q q q q q q q q q q q fitted values BMM HBT

Figure 5: Average mse and 95% confidence interval for the pairwise experiment with different fractions of pairs available in the data, 10 independent repetitions. dots: HBT; Black dots: BMM. The lines are fitted from an exponential model.

A similar effect can be observed from Figure 6, which presents the heatplots of the posterior distribution for each item plotted against the true ranking for assessor 1, when assessor 1 is given 20%, 60% and 100% of all available pairs (run 1). The three lower plots are obtained with the BMM, the three upper ones with the HBT. Notice the special case where all pairwise comparisons are given to the assessors (right panels): the BMM heatplot (bottom-right) does not show any variability. This is due to the fact that there is only one ranking vector Rj which is consistent with the given n(n -1)/2 possible pairs. On the other hand, the plot obtained with HBT in the same situation (top-right) is very accurate, but still shows some variability around the correct ranking. We clearly see that BMM has more peaked marginal posteriors, and that they often peak around the diagonal, i.e. the correct ranking.

Let us finally look at the estimates of the assessors' top-3 items using the two methods, shown in Figure 7. For run 1, when the proportion of pairs assessed by each individual assessor is 50%, Figure 7 was obtained as follows: in the separate column on the left, we display the posterior probability P (ρ Ai ≤ 3 | D N ) that a given potato A i , i = 1, ..., 20, is among the top-3 in the estimated consensus ρ. In the other columns we show, for each potato A i , the individual posterior probabilities Pij = P ( Rj,Ai ≤ 3 | D N ) of being among the top-3 for assessor j, j = 1, ..., 12. The left panel is obtained with HBT, the right one with BMM. These probabilities are used to assign the top-3 potatoes to each assessor individually. We see again how more marked BMM's posterior probabilities are, though individual posterior rankings are allowed to depart from the consensus.

Figure 8 shows the prediction outcome for the top three items using the BMM and HBT, averaged among all assessors and runs, plotted against the fraction of pairs evaluated by each assessor. For both BMM and HBT, we observe an expected increase of prediction accuracy as the number of assessed pairs increases. BMM performs well in predicting the top-3 items for each Figure 6: Heatplots of the posterior distribution for each item for assessor 1, when assessor 1 is given (left panels) 20%, (middle panels) 60% and (right panels) 100% of all available pairs (in run 1). The three lower plots are obtained with the BMM, the three upper ones with the HBT. Note that the ranges of the color scales in the different panels are different.

L M I G J E Q P N A T K S R D F O B C
assessor: already when only 10% of the pairs are compared, on average 2.5 items are correct, and the average number of correct items increases then slowly.

One could conclude that in this data set it is probably not worth to extend the learning task very much. For HBT the situation is different. The same curve starts around 1.7 and reaches 2.5 items approximately when 50% of the pairs are compared in the data. Here, asking the assessors to express more preferences appears to be important, result in line with the strong connection condition introduced in Section 3.1. We can see that the BMM has an edge in terms of accuracy for the potato data, we believe also due to the discrete parametrization in P n .

Top-k rankings with implicit data

The most common and abundant type of preference data is in an implicit form.

In order to use clicking data to make inference on individual preferences, an underlying assumption is needed, namely that the items that are clicked by assessor j are preferred, compared to the non-cliked ones. This assumption naturally forms pairwise comparisons. Denote the set of items that are clicked by assessor j as C j , and the non-clicked set as

C c j . Then A i ≺ j A k if A i ∈ C j and A k ∈ C c j .
We can therefore use also in this case the same methods as in the case of pair comparison data. The BMM and the CF methods for implicit datasets [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF] will be considered. For each assessor j, the aim is to infer on the next m = 2 items (contained in C c j ), which are ranked next to the ones in C j .

We continue with the potato dataset, which we convert into the implicit form as follows. For each assessor j, we sample the number k j of items that she has clicked, using k j ∼Truncated Poisson [1,n] (λ). We let λ vary to increase the amount of data. Then we look to the potato data and define the implicit interaction between assessor j and item i as

I ij = 1 if R ij ≤ k j 0 otherwise.
The BMM first converts the implicit data into all implied pairwise comparisons, and then uses the pairwise comparison version of the method, as in Section 4.2.2, to obtain the augmented ranking vectors Rj for each assessor. The CF method follows the matrix factorization approach, and handles the implicit dataset more directly. Note that in this experiment, r ji and x ji as described above in the CF model take the same value, since the implicit dataset is in a binary form. We consider data with λ = 3, 4, ...12, and record the average number of correctly predicted next 2 items across all assessors. Ten independent implicit datasets are generated for each λ to produce 95% confidence intervals.

Figure 9 shows the prediction outcome using the BMM and CF. Both models perform well in predicting the next m = 2 items for each individual assessor: on average more than 50% of the items are correctly predicted. The BMM appears to have a slight edge in terms of accuracy, with narrower 95% confidence interval, because of its better performance on the more difficult of the ten datasets. Quite surprisingly, for both BMM and CF, we do not observe an increasing prediction accuracy as λ increases. This can be explained by the strong consensus shared by the assessors in the potato experiment, as described in Section 4.1.1. Except from the middle-ranked items, most assessors tend to agree on the rankings of the top and bottom-ranked items. To make inference on each assessor's next m = 2 items, the models borrow information about the non-clicked items, A j ∈ C c j . In this example however, as λ increases, due to the strong consensus shared between assessors, this information does not increase much.

Non-homogeneous assessors

In real situations, assessors often do not all share the same preference on a set of items. The methods which are built around a common consensus can be extended to handle this more complex situation. We demonstrate an example of inference from top-k rankings when the assessors in the sample do not share one single consensus, but multiple group consensuses exist. Clustering the assessors can be handled by many of the methods presented in Section 3. In this section, we illustrate the BMM, extended to finite mixtures in [START_REF] Asfaw | Time-varying rankings with the Bayesian Mallows model[END_REF], and the PL model, which was generalized to infinite non-parametric mixture by Caron et al (2014), and to parametric mixtures by Mollica and Tardella (2016). In this section, we also use a larger simulated data set, in order to discuss briefly scaling issues, for large N and n.

We sampled N = 2000 assessors from the Mallows distribution using the simulator described in [START_REF] Vitelli | Probabilistic preference learning with the Mallows rank model[END_REF], each ranking n = 100 items. We assume that the assessors belong to C = 3 distinct clusters, characterised by three true cluster consensuses: {n, n -1, ...1}, {1, 2, ...n},and {n/2, n/2 -1, ...1, n, n -1, ..., n/2 + 1}. The central cluster is twice as large as the other two, as we use proportions {0.25, 0.5, 0.25}, respectively. The three clusters share the same α = 3. Similar to Section 4.1.2, the dataset is then converted into top-k j rankings, where k j ∼ Truncated Poisson [1,97] (20), thus on average, 20% of the items' rankings are reported.

The prior and distance choices for the BMM are the same as in Section 4.1.2 . The normalizing constant Z n is approximated by the IPFP method of [START_REF] Mukherjee | Estimation in exponential families on permutations[END_REF], and the MCMC is run for 10 5 iterations.

First we specify the correct number of clusters, C = 3, and let both the PL model and the BMM estimate the group consensus rankings. The heatplots of the estimated consensuses for the three clusters and the two methods are shown in Figure 10. The hundred items are not ordered in the x-axis according to the true consensus. Careful inspection of the heatplots reveals that the top ranked items are estimated with higher accuracy, while for the other items an almost flat posterior distribution appears. This is as expected, as each assessor provides on average only the 20 top items of the 100 items, and there is little information regarding the other items. Both methods deliver estimated consensuses which resembles to a reasonable extent the true consensuses of each of the three clusters. The mse (reported on top of each panel) is significantly smaller for cluster 2 because this cluster has more assessors. The two methods perform rather similarly in terms of mse.

The approach to estimating the clusters when applying the PL model is different from when using the BMM. The PL model is a mixture model with the form p(R j |µ 1 , ..., µ K ) = K k=1 w k p(R j |µ k ), where the weights {w 1 , ...,w C } are parameters to be estimated. The BMM, on the other hand, estimates the auxiliary variables, z j ∈ {1, ..., C} for each assessor j, which indicates which cluster the observation R j belongs to. We refer to the auxiliary variables as cluster assignments. Table 3 shows the cluster weights estimated by the PL model and BMM. In the case of the PL model, the posterior means of the weight parameters are shown; for the BMM, the mode of the posterior marginal density of the z j 's is used to determine cluster assignments. Both methods perform well. The left panel of Figure 11 shows for each assessor the posterior probabilities of being assigned to each of the three clusters, for BMM. It is clear that the cluster assignment is more certain for users that belong to cluster 1. This is due to the fact that cluster 1 is more distinct from the other 2 clusters -the footrule distances between ρ 1 and the other two clusters are much larger than the footrule distance between ρ 2 and ρ 3 .

In this experiment, the number of clusters C = 3 was known. As this is usually is not the case, the number of clusters needs be estimated. While classical The computing time for this simulation using the BMM is dependent on C. When using one core of the Intel Xeon e-8890 processor, running at 2.5 GHz, the computation with C = 2 took approximately 19.95 minutes and approximately an addition of 4.3 minutes to compute for each extra cluster. The time complexity is linear in terms of N . The increase of n does not greatly affect computing time per iteration, but a longer chain is needed to reach convergence.

Discussion and further developments

In this paper we have reviewed the most important model-based approaches to estimate a consensus ranking of items or the individual rankings of the assessors. Model-based here stands for a statistical model which represents the stochastic process generating the data. In some cases, the decisions made by 1.0 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 2 3 4 5 6 7 4200000 4400000 4600000 clusters sum of within cluster foot rule distance the assessors are assumed to be sequential, from the most preferred downwards; in other cases pair comparisons are thought to be performed; or a complete ranking is assumed to exist so that expressions of preference correspond to this ranking. The key component is a latent vector of scores, utilities or ranks associated with the items, shared by a group of assessors, representing the consensus preference; or a collection of such latent vectors, one per assessor, representing her personal preference. These latent vectors are assumed to be continuous, real and positive, or a permutation of the n integers. We have seen how these choices can be justified, also on the basis of the form of the available data. Both likelihood based and Bayesian approaches are fruitful. Priors on the latent vectors are usually non-informative or uniform, but informative forms can be used when appropriate. In addition to point estimates, which synthesize posterior distributions or likelihoods, it is important to quantify the uncertainty of the estimated consensus or individual rankings.

There are several themes that we have not discussed in this paper. The potato data set allows to illustrate the use of different methods for different types of data, but is not useful for discussing scaling in the number of assessors or items. MCMC algorithms suffer particularly when N and n are large and the data is very incomplete. The amount of expressed preferences by individual assessors of course matters, starting from completely new assessors (the so called "cold start" situation). Bandit models [START_REF] Li | A contextual-bandit approach to personalized news article recommendation[END_REF] are very useful for learning preferences rapidly, by dynamically suggesting items to each assessor, in order to test, and in this way, learn their preferences. In many practical situations, additional information is available on the assessors and the items. Such features or covariates can be very useful for recognizing similarities across assessors and items. Recommender systems using covariates related to the interaction between user and item are called context-aware, see [START_REF] Adomavicius | Context-aware recommender systems[END_REF]. Extracting features that give good descriptions of items or users (for example books or movies, or individual CV's) is difficult and deep learning has been proposed [START_REF] Karatzoglou | Deep learning for recommender systems[END_REF]. Preferences change in time and models can account for time dependence: in [START_REF] Asfaw | Time-varying rankings with the Bayesian Mallows model[END_REF] changes are assumed to be smooth in time. Crispino et al. (2018) consider pair comparison data, where assessors are not consistent with themselves, and non-transitivities appear in the data. Sometimes, preference expressions of various types have been collected from users, for example ratings, rankings and pair comparisons. Mallows models can in principle be extended in this direction, because of the underlying latent structure, conditioned on which likelihood terms can be assumed independent. Regarding Mallows models, it is difficult to recommend one distance with respect to another on the basis of the actual application. Finally, a well studied, difficult question is concerned with the evaluation of preference learning algorithms, see for example [START_REF] Gunawardana | Evaluating recommender systems[END_REF]. This includes also running designed experiments on online systems.

In a world where data and digital information is massively available, users like us would be overloaded, incapable of sorting and finding the needed pieces of knowledge, if not assisted by algorithms. These algorithms have to understand our goals, intentions and preferences: the underlying inferential task is evident. Algorithms must learn from our behavior, and therefore, traces of our actions, roles, conducts and expressions need to be collected. Who should have access to such data, who should own it, how to consent (or not) to its use, and use for what purpose: these are all fundamental issues that question privacy, freedom, democracy, and trust. Mallows, Plackett-Luce, Bradley-Terry, collaborative filtering and all the other preference learning methods contribute to making the information based society possible, but they do not guarantee a fair, legal, good, social use of private data. Science and scientists must engage and keep alert.

Figure 1 :

 1 Figure1: Consensus estimation of the potato experiment with full ranking data produced by the Bayesian Mallows Model. Posterior probability of each item to be ranked as the k-th heaviest potato (y-axis) versus the true ranking of the item (x-axis). Three distances. The posterior expected mse is reported on top of each panel.

Figure 2 :

 2 Figure 2: Consensus estimation of the potato experiment produced by the Plackett-Luce model

Figure 3 :

 3 Figure 3: Left: Consensus estimation of the top-k potato experiment run number 1, using the BMM with footrule distance. Middle: Consensus estimation of the top-k potato experiment using the PL, run number 1. Right: scatter plot of the mse of the 10 experiment runs

Figure 4 :

 4 Figure 4: Pairwise experiment with different fractions of pairs compared by the 12 assessors, from 10% to 100% of the total number of possible pairs (190).Expected postrior mse of the consensus with 95% confidence interval based on ten independent runs. Red dots: BT; Black dots: BMM. x-axis: fractions of pairs; y-axis: mse.

Figure 7 :

 7 Figure 7: Posterior probability, for each potato, of being ranked among the top-3 in ρ (column 1), and in Rj , j = 1, ..., 12 (following columns). Left: results with HBT; Right: results with BMM.

Figure 8 :

 8 Figure8: Average number of correctly predicted top-3 potatoes across all assessors and runs, and 95% confidence interval (y-axis) plotted against fraction of pairs assessed (x-axis) in the potato data set. Blue: prediction outcome using the HBT. Red: prediction outcome using the BMM approach.

  Figure9: Average number of correctly predicted next 2 items across all assessors and 95% confidence interval (y-axis) plotted against average number of items clicked (x-axis). Left: prediction outcome using the BMM. Right: prediction outcome using the CF approach.

Figure 10 :

 10 Figure 10: Heatplots of the posterior distributions of 3 clusters group consensuses. Top: the PL model; Bottom: BMM

Figure 11 :

 11 Figure11: Left: Posterior distribution of cluster assignment for each assessor using the BMM when the number of clusters is C = 3. Right: Boxplots of the sum of within cluster footrule distances for different choices of the number of clusters, using the BMM.

Table 1

 1

	: Next-m = 1, 2 items estimation accuracy based on top-k potato data,
	exp. correct refers to assignment recommendations at random
	scenario	mean correct	95% CI	exp. correct improvement
	Next 1 item	0.450	0.37 -0.53	0.077	485% ±106%
	Next 2 items	1.325	1.230 -1.421	0.333	298%± 29%

Table 2 :

 2 Summary of the posterior probabilities of being next-m items, based on top-k potato data, m = 1, 2.

	P ij	min	25% median mean 75%	max
	Next 1 item 0.172 0.418	0.489	0.484 0.559 0.642
	Next 2 items 0.210 0.576	0.673	0.651 0.755 0.837
	number is shown in the second to the last column and is calculated as

Acknowledgement

Special thanks to Elja Arjas for important discussions, for having conceived the potato experiment and for having bought the potatoes. Øystein Sørensen's MCMC codes have been used in this paper.