Tathagata Basu

Sébastien Destercke

Benjamin Quost

An Imprecise Label Ranking Method for Heterogeneous Data

Learning to rank is an important problem in many sectors ranging from social sciences to artificial intelligence. However, it remains a rather difficult task to perform. Therefore, in some cases, it is preferable to perform cautious inference. For this purpose, we look into the possibility of an imprecise probabilistic approach for the Plackett-Luce model, a popular probabilistic model for label ranking. We aim at extending current Bayesian inference techniques for the Plackett-Luce model to an imprecise probabilistic setting so that we can deal with heterogeneous data by means of cautious mixture modelling. To achieve this, we perform a robust Bayesian analysis over a set of imprecise Dirichlet priors, which allows us to perform cautious label ranking. Finally, we use a synthetic dataset to illustrate our imprecise estimation method.

Introduction

Ranking objects is an important problem in many areas, such as social sciences, stock markets, e-commerce, etc. Sometimes, such rankings proceed from pairwise comparisons between the objects: one such treatment can be found in the model defined by [START_REF] Bradley | Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons[END_REF]. This model naturally extends to the Plackett-Luce model in the case of multiple comparisons, as suggested by [START_REF] Plackett | The Analysis of Permutations[END_REF] and [START_REF] Luce | Individual Choice Behavior: A Theoretical analysis[END_REF]. Several frequentist and Bayesian estimation methods have been developed based on these models.

Once the ranking model has been constructed, it can be used to estimate an optimal ranking between the objects. However, estimation of this ranking requires the data to be homogeneous, i.e. the objects are compared by a sub-Tathagata Basu ( ) • Sébastien Destercke • Benjamin Quost UMR CNRS 7253 Heudiasyc, Université de Technologie de Compiègne Compiègne, France. e-mail: {name.surname}@hds.utc.fr 1 population of rankers which are assumed to be consistent with each other. In reality this might not be the case as we may gather this ranking data from different sources making the data heterogeneous. In such cases, mixtures of ranking models allow us to capture the sample information efficiently and also opens up the possibility of predicting a ranking after observing the ranker.

One of the first works on heterogeneous data was done by [START_REF] Gormley | Analysis of Irish third-level college applications data[END_REF] where they suggested a mixture model using the Plackett-Luce model. Later, [START_REF] Caron | Bayesian nonparametric Plackett-Luce models for the analysis of preferences for college degree programmes[END_REF] suggested a Bayesian alternative using a Dirichlet process model, where infinitely many models are assumed to be present in the mixture. A similar idea involving a finite mixture was proposed by [START_REF] Mollica | Bayesian Plackett-Luce mixture models for partially ranked data[END_REF] for partially ranked data. Recently, [START_REF] Adam | Inferring from an Imprecise Plackett-Luce Model: Application to Label Ranking[END_REF] proposed an imprecise probabilistic approach for the Plackett-Luce model where imprecise estimation was carried out using likelihood cuts.

In this paper, we discuss the notion of robust Bayesian analysis for the Plackett-Luce model. Section 2 presents our approach, very similar to that of [START_REF] Mollica | Bayesian Plackett-Luce mixture models for partially ranked data[END_REF]. In our approach we overcome the difficulty of obtaining closed forms for the imprecise estimates by using a non-linear optimiser for certain parameter estimates. Section 3 illustrates our approach on a synthetic dataset. Section 4 concludes the paper along with a discussion on future works.

The Plackett-Luce Model

The Plackett-Luce model [START_REF] Plackett | The Analysis of Permutations[END_REF]) is a simple and intuitive probabilistic model which gives us a probability for any observed ranking of 𝑝 objects. Each object is associated with a strength parameter 𝜆, which determines its probability of being preferred over others when drawing a sequence of objects. This model gives the probability of 𝑛 independent rankings as

𝑃(𝑋 | 𝜆) = 𝑛 𝑖=1 𝑝 𝑖 -1 𝑗=1 𝜆 𝑥 𝑖 𝑗 𝑝 𝑖 𝑚= 𝑗 𝜆 𝑥 𝑖𝑚 . ( 1
)
where 𝑝 𝑖 ≤ 𝑝 is the number of objects in the 𝑖-th ranking, 𝜆 (𝜆 1 , • • • , 𝜆 𝑝 ) is the vector of strength parameters, and 𝑋 [𝑥 𝑖 𝑗 ] is the 𝑛 × 𝑝 matrix containing the rankings (i.e., 𝑥 𝑖 𝑗 is the rank of the 𝑗th object or participant in the 𝑖th observed ranking, with 𝑖 = 1, . . . , 𝑛 and 𝑗 = 1, . . . , 𝑝 𝑖 ). Note that Eq. ( 1) may be called the Plackett-Luce distribution because of its probabilistic formulation.

Example 1 Table 1 displays 𝑛 = 2 rankings observed over 𝑝 = 4 different objects 'A', 'B', 'C' and 'D'; where A and B have rank 4 and 1 in the first observed ranking (𝑥 12 = 1 and 𝑥 11 = 4). The probability of these data is given by Eq. (2):

Obj. 1 Obj. 2 Obj. 3 Obj. 4 Ranking 1 B D C A Ranking 2 B A C - Table 1 Toy example with 𝑛 = 2 rankings of 𝑝 = 4 objects 𝑃(𝑋 | 𝜆) = 𝜆 𝐵 𝜆 𝐵 + 𝜆 𝐷 + 𝜆 𝐶 + 𝜆 𝐴 • 𝜆 𝐷 𝜆 𝐷 + 𝜆 𝐶 + 𝜆 𝐴 • 𝜆 𝐶 𝜆 𝐶 + 𝜆 𝐴 • 𝜆 𝐵 𝜆 𝐵 + 𝜆 𝐴 + 𝜆 𝐶 • 𝜆 𝐴 𝜆 𝐴 + 𝜆 𝐶 . (2)
We aim to estimate the strength parameters which maximise this probability.

Hierarchical model

We follow [START_REF] Mollica | Bayesian Plackett-Luce mixture models for partially ranked data[END_REF] to construct our hierarchical mixture model. Though, we interpret a partial ordering involving 𝐾 ≤ 𝑝 objects as a top-𝐾 ordering, assuming the remaining objects to be absent from the model. This also simplifies the expression of the PL distribution, which is beneficial for faster computation.

Assuming a total of 𝐺 components in the mixture, the model can be written as

𝑋 𝑖 | 𝜆, 𝜔 ∼ 𝐺 ∑ 𝑔=1 𝜔 𝑔 PL(𝑋 𝑖 | 𝜆 𝑔 ), PL(𝑋 𝑖 | 𝜆 𝑔 ) = 𝑝 𝑖 -1 𝑗=1 𝜆 𝑔,𝑥 𝑖 𝑗 𝑝 𝑖 𝑚= 𝑗 𝜆 𝑔,𝑥 𝑖𝑚 .
We associate each observation with a unique latent membership indicator 𝑧 𝑖 , which follows a categorical distribution

𝑧 𝑖 | 𝜔 ∼ Cat(𝜔 1 , • • • , 𝜔 𝐺 ),
with 𝜔 𝑔 being the weight of the 𝑔-th mixture component. For a full Bayesian treatment, we assign a set of imprecise Dirichlet priors on these weights:

𝜔 | 𝑠, 𝛼 ∼ Dir(𝑠; 𝛼 1 , • • • , 𝛼 𝐺 ), where 𝛼 𝑔 ≤ 𝛼 𝑔 ≤ 𝛼 𝑔 for 𝑔 = 1, • • • , 𝐺
, with in addition 𝑔 𝛼 𝑔 = 1 and 𝑠 > 0. For the data augmentation process, we follow [START_REF] Mollica | Bayesian Plackett-Luce mixture models for partially ranked data[END_REF] and use exponentially distributed variables 𝑦 𝑖 𝑗 so that

𝑦 𝑖 𝑗 ind ∼ Exp 𝐺 𝑔=1 𝑝 𝑖 ∑ 𝑚= 𝑗 𝜆 𝑔,𝑥 𝑖𝑚 𝑧 𝑖𝑔 .
Finally, we specify the strength parameters 𝜆 using gamma priors:

𝜆 𝑔𝑘 ∼ Gamma(𝑎 𝑔𝑘 , 𝑏 𝑘 ), with 𝑎 𝑔𝑘 ≤ 𝑎 𝑔𝑘 ≤ 𝑎 𝑔𝑘 , for 1 ≤ 𝑔 ≤ 𝐺 and 1 ≤ 𝑘 ≤ 𝑝.

Parameter Estimation

To discuss parameter estimation, we first look at the following iterative steps. These formulas can be obtained by adding log-prior components to the complete data log-likelihood given by [START_REF] Gormley | Analysis of Irish third-level college applications data[END_REF]. Since details are provided in this latter reference, we omit them here.

𝑧 (𝑡+1) 𝑖𝑔 = 𝜔 (𝑡) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) ∑ 𝑔 𝜔 (𝑡) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) , 𝜔 (𝑡+1) 𝑔 = 𝑠 𝛼 𝑔 -1 + 𝑖 𝑧 (𝑡+1) 𝑖𝑔 𝑠 -𝐺 + 𝑁 , 𝜆 (𝑡+1) 𝑔𝑘 = 𝑎 𝑔𝑘 -1 + 𝑖 𝑧 (𝑡+1) 𝑖𝑔 𝑢 𝑖𝑘 𝑏 𝑔 + ∑ 𝑖 𝑧 (𝑡+1) 𝑖𝑔 ∑ 𝑗 𝛿 𝑖 𝑗 𝑘 𝑝 𝑖 𝑚= 𝑗 𝜆 (𝑡) 𝑔,𝑥 𝑖𝑚 , (3)
where

𝑢 𝑖𝑘 = I 𝑘 ∈ {𝑥 𝑖1 ,••• , 𝑥 𝑖 ( 𝑝 𝑖 -1) } and 𝛿 𝑖 𝑗 𝑘 = I 𝑘 ∈ {𝑥 𝑖 𝑗 ,••• ,𝑥 𝑖 𝑝 𝑖 } .
Note that, to start this iterative process we need suitable initial guesses for 𝜆 𝑔 and 𝜔 𝑔 .

Imprecise Estimates

In order to compute imprecise estimates, we need to calculate the bounds of the parameters in Eq. ( 3) over the sets of all possible values of 𝛼

(𝛼 1 , • • • , 𝛼 𝐺 ).
From the iterative formula of the posterior membership probability ( 𝑧 𝑖𝑔 ), we have

𝑧 (𝑡+1) 𝑖𝑔 = 𝜔 (𝑡) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) 𝑔 𝜔 (𝑡) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) = 1 1 + 𝑔 ′ ≠𝑔 𝜔 (𝑡 ) 𝑔 ′ PL(𝑋 𝑖 | 𝜆 (𝑡 ) 𝑔 ′ ) 𝜔 (𝑡 ) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡 ) 𝑔 ) ≥ 1 1 + 𝑔 ′ ≠𝑔 max 𝜔 (𝑡 ) 𝑔 ′ , 𝜆 (𝑡 ) 𝑔 ′ 𝜔 (𝑡) 𝑔 ′ PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ′ ) min 𝜔 (𝑡 ) 𝑔 , 𝜆 (𝑡 ) 𝑔 𝜔 (𝑡) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) . Now, let PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) min 𝜆 (𝑡 ) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) , PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) max 𝜆 (𝑡 ) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) such that 𝜆 (𝑡) 𝑔𝑘 ≤ 𝜆 (𝑡) 𝑔𝑘 ≤ 𝜆 (𝑡)
𝑔𝑘 for 1 ≤ 𝑘 ≤ 𝑝. Then, the lower bound of the posterior membership probability is given by: ẑ𝑖𝑔 = 𝜔 (𝑡) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 )

𝜔 (𝑡) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) + 𝑔 ′ ≠𝑔 𝜔 (𝑡) 𝑔 ′ PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ′ ) , (4)
and similarly the upper bound is given by:

ẑ𝑖𝑔 = 𝜔 (𝑡) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) 𝜔 (𝑡) 𝑔 PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) + 𝑔 ′ ≠𝑔 𝜔 (𝑡) 𝑔 ′ PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ′ ) , (5)
where the lower and upper bounds 𝜔 (𝑡) 𝑔 and 𝜔 (𝑡)

𝑔 on the mixture weights 𝜔 (𝑡) 𝑔 is obtained from Eq. ( 3), so that

𝜔 (𝑡) 𝑔 = 𝑠𝛼 𝑔 -1 + 𝑖 𝑧 (𝑡) 𝑖𝑔 𝑠 -𝐺 + 𝑁 and 𝜔 (𝑡) 𝑔 = 𝑠𝛼 𝑔 -1 + 𝑖 𝑧 (𝑡) 𝑖𝑔 𝑠 -𝐺 + 𝑁 . (6)
Even though the update equations for these parameter bounds can be derived easily, computing these bounds is difficult and we need to employ an optimiser to compute PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) and PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) We face similar issues for the strength parameters as well, as 𝜆

min 𝜆 (𝑡+1) 1𝑘 , 𝜆 (𝑡+1) 2𝑘 , • • • , 𝜆 (𝑡+1) 𝐺𝑘 and max 𝜆 (𝑡+1) 1𝑘 , 𝜆 (𝑡+1) 2𝑘 , • • • , 𝜆 (𝑡+1) 𝐺𝑘 , (7)
such that 𝑧 𝑖𝑔 ≤ 𝑧 𝑖𝑔 ≤ 𝑧 𝑖𝑔 , for 1 ≤ 𝑔 ≤ 𝐺 and 1 ≤ 𝑖 ≤ 𝑁.

Illustration

We illustrate our approach using a synthetic dataset, which allows us to assess the performance of our method in estimating the strength parameters. We consider a set of 𝑝 = 8 objects, together with two different sets of strengths 𝜆: in one case,

(𝜆 1,1 , 𝜆 1,2 , • • • 𝜆 1,8 ) = (8, 7, • • • , 1)
, and in the other case

(𝜆 2,1 , 𝜆 2,2 , • • • 𝜆 2,8 ) = (1, 2, • • • , 8
). These strengths correspond to two ranking processes which order the objects in an exactly opposite way.

We use these parameters to randomly generate our ranking dataset using the generative model suggested by [START_REF] Caron | Efficient Bayesian Inference for Generalized Bradley-Terry Models[END_REF]. Then, we pick 60% samples from the first set, and the remaining 40% from the second one. Note that, this is a randomised generative process and in the estimation the orderings of the components may not be estimated based on this generation.

Results

To show our results, we consider two different settings. In the first case, we consider the weights of the Dirichlet model to be precise and equal. In the second case, we define imprecise initial weights, such that 0.5 ≤ 𝛼 1 ≤ 0.7 and 0.3 ≤ 𝛼 2 ≤ 0.5. In both cases, we set our initial estimates for 𝑎 𝑔𝑘 , so that they satisfy the orderings of 𝜆 𝑔𝑘 estimated from a precise estimation process. This initialisation step is crucial to avoid 𝜆 (𝑡) 𝑔 taking extreme values, which would be problematic for the convergence of the iterative algorithm. Moreover, in each iteration, we need to enforce orderings of these 𝜆 (𝑡) 𝑔𝑘 estimates whilst computing PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) and PL(𝑋 𝑖 | 𝜆 (𝑡) 𝑔 ) using the optimiser. Nevertheless, to ensure robustness, we take a large interval for each 𝑎 𝑔𝑘 for capturing the imprecision in the data. For precise and equal initial weights, we get estimated mixture weights 𝜔 1 ∈ [0.36; 0.63] and 𝜔 2 ∈ [0.37; 0.64]. The corresponding strengths are displayed in Fig. 1 (first component on left and the second one on right). We notice that the strength parameters follow a strict ordering for the first component, which is not the case for the second one1 : in this latter case, we notice that '2' and '5' are not comparable, which leads to a partial ordering. We notice a similar outcome for imprecise initial weights (Fig. 2). In this case, we obtain mixture weight estimates 𝜔 1 ∈ [0.21; 0.62] and 𝜔 2 ∈ [0.38; 0.78]. We can observe from the figure that the intervals tend to be larger than the intervals in the first case, confirming the initial imprecise prior. Furthermore, we see that the estimated ranking from the first component is the same as in the precise initialisation case (see Fig. 1). However, the estimates are slightly different for the second component: then, '2' is not comparable to both '4' and '5', though '5' is strictly preferred to '4'.

We also notice that our choice of ordered imprecise weights gives us better estimates for the mixture weights, which is not the case for starting with equal weights. This happens as for the equal weights, the imprecision in the data is only captured through our ignorance about the size of the mixture components whereas for the ordered weights, our model tends to assign membership probabilities more efficiently and can also capture the imprecision in rankings.

Conclusion

In this article, we investigate inferring a probabilistic ranking model from heterogeneous data: we assume the data to come from several sub-populations, each of which can be associated with a Plackett-Luce ranking model. We propose a robust Bayesian approach to estimate the strength parameters of the resulting mixture of PL models. We notice that estimating the model is computationally expensive, since it requires to repeatedly calculate the bounds of each PL distribution -which involves solving nonlinear optimisation problems.

We illustrate our method using a synthetic dataset, in order to study its efficiency in inferring a mixture of rankings. The experiments show that im-precise initial mixture weights tend to produce wider intervals for the strength estimates, which reflects our methods ability to showcase the inherent imprecision in scarce data. This is extremely important for cautious ranking as we may want to abstain from ordering in certain scenarios.

A major issue remaining to be addressed is the high computation time of the estimation procedure. This motivates us to find tight approximate bounds to ensure monotonicity. Hopefully, this will help us to reduce the computation cost significantly, while allowing us to investigate problems with a high number of mixture components.

  need to solve the following multiobjective optimisation problems:

Fig. 1

 1 Fig. 1 Strength parameter estimates for 𝛼 1 = 𝛼 2 = 0.5 and 𝑠 = 5.

Fig. 2

 2 Fig.2Strength parameter estimates for 0.3 ≤ 𝛼 1 ≤ 0.5; 0.5 ≤ 𝛼 2 ≤ 0.7 and 𝑠 = 5.

We consider, object 𝑖 is preferred to object 𝑗 if 𝜆 𝑖 > 𝜆 𝑗 and 𝜆 𝑖 > 𝜆 𝑗 .

Acknowledgements This research was funded by the project PreServe (ANR Grant ANR-18-CE23-0008).