Yonatan-Carlos Carranza-Alarcon
email: yonatan-carlos.carranza-alarcon@hds.utc.fr

Soundouss Messoudi
email: soundouss.messoudi@hds.utc.fr

Sébastien Destercke
email: sebastien.destercke@hds.utc.fr

Cautious label-wise ranking with constraint satisfaction

Keywords: Label ranking problem, Constraint satisfaction, Imprecise probabilities

Ranking problems are difficult to solve due to their combinatorial nature. One way to solve this issue is to adopt a decomposition scheme, splitting the initial difficult problem in many simpler problems. The predictions obtained from these simplified settings must then be combined into one single output, possibly resolving inconsistencies between the outputs. In this paper, we consider such an approach for the label ranking problem, where in addition we allow the predictive model to produce cautious inferences in the form of sets of rankings when it lacks information to produce reliable, precise predictions. More specifically, we propose to combine a rank-wise decomposition, in which every sub-problem becomes an ordinal classification one, with a constraint satisfaction problem (CSP) approach to verify the consistency of the predictions. Our experimental results indicate that our approach produces predictions with appropriately balanced reliability and precision, while remaining competitive with classical, precise approaches.

Introduction

In recent years, machine learning problems with structured outputs received an increasing interest. These problems appear in a variety of fields, including biology [START_REF] Weskamp | Multiple graph alignment for the structural analysis of protein active sites. Computational Biology and Bioinformatics[END_REF], image analysis [START_REF] Geng | Multilabel ranking with inconsistent rankers[END_REF], natural language treatment [START_REF] Bordes | Joint learning of words and meaning representations for open-text semantic parsing[END_REF], and so on.

In this paper, we look at label ranking (LR), where one has to learn a mapping from instances to rankings (strict total order) defined over a finite, usually limited number of labels. Most solutions to this problem reduce its initial complexity, either by fitting a probabilistic model (Mallows, Plackett-Luce [START_REF] Cheng | Label ranking methods based on the plackett-luce model[END_REF]) with few parameters, or through a decomposition scheme. For example, ranking by pairwise comparison (RPC) [START_REF] Hüllermeier | Label ranking by learning pairwise preferences[END_REF] transforms the initial problem into binary problems. Constraint classification and log-linear models [START_REF] Dekel | Log-linear models for label ranking[END_REF], as well as SVM-based methods [START_REF] Vembu | Label ranking algorithms: A survey[END_REF] learn, for each label, a (linear) utility function from which the ranking is deduced. Those latter approaches are close to other proposals [START_REF] Destercke | Cautious label ranking with label-wise decomposition[END_REF] that perform a label-wise decomposition.

In ranking problems, it may also be interesting [START_REF] Cheng | Predicting partial orders: ranking with abstention[END_REF][START_REF] Destercke | Cautious label ranking with label-wise decomposition[END_REF] to predict partial rather than complete rankings, abstaining to make a precise prediction in presence of too little information. Such predictions can be seen as extensions of the reject option [START_REF] Bartlett | Classification with a reject option using a hinge loss[END_REF] or of partial predictions [START_REF] Corani | Bayesian networks with imprecise probabilities: Theory and application to classification[END_REF]. They can prevent harmful decisions based on incorrect predictions, and have been applied for different decomposition schemes, be it pairwise [START_REF] Cheng | Label ranking with partial abstention based on thresholded probabilistic models[END_REF] or label-wise [START_REF] Destercke | Cautious label ranking with label-wise decomposition[END_REF], always producing cautious predictions in the form of partial order relations.

In this paper, we propose a new label ranking method, called LR-CSP, based on a label-wise decomposition where each sub-problem intends to predict a set of ranks. More precisely, we propose to learn for each label an imprecise ordinal regression model of its rank [START_REF] Destercke | Cautious ordinal classification by binary decomposition[END_REF], and use these models to infer a set of possible ranks. To do this, we use imprecise probabilistic (IP) approaches are well tailored to make partial predictions [START_REF] Corani | Bayesian networks with imprecise probabilities: Theory and application to classification[END_REF] and represent potential lack of knowledge, by describing our uncertainty by means of a convex set of probability distributions P [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF] rather than by a classical single precise probability distribution P. An interesting point of our method, whose principle can be used with any set of probabilities, is that it does not require any modification of the underlying learning imprecise classifier, as long as the classifier can produce lower and upper bounds [P , P ] over binary classification problems.

We then use CSP techniques on the set of resulting predictions to check whether the prediction outputs are consistent with a global ranking (i.e. that each label can be assigned a different rank).

Section 2 introduces the problem and our notations. Section 3 shows how ranks can be predicted from imprecise probabilistic models and presents the proposed inference method based on robust optimization techniques. Section 4 discusses related work. Finally, Section 5 is devoted to experimental evaluation showing that our approach does reach a higher accuracy by allowing for partial outputs, and remains quite competitive with alternative approaches to the same learning problem.

Problem setting

Multi-class problems consist in associating an instance x coming from an input space X to a single label of the output space Λ = {λ 1 , . . . , λ k } representing the possible classes. In label ranking, an instance x is no longer associated to a unique label of Λ but to an order relation 1

x over Λ × Λ, or equivalently to a complete ranking over the labels in Λ. Hence, the output space is the set L(Λ) of complete rankings of Λ that contains |L(Λ)| = k! elements (i.e., the set of all permutations). Table 1 illustrates a label ranking data set example with k = 3.

We can identify a ranking x with a permutation σ x on {1, . . . , k} such that σ x (i) < σ x (j) iff λ i x λ j , as they are in one-to-one correspondence. σ x (i) is the 1 A complete, transitive, and asymmetric relation. As there is a one-to-one correspondence between permutations and complete rankings, we use the terms interchangeably.

Example 1. Consider the set Λ = {λ 1 , λ 2 , λ 3 } and the observation λ 3 λ 1 λ 2 , then we have

σ x (1) = 2, σ x (2) = 3, σ x (3) = 1.
The usual objective in label ranking is to use the training instances D = {(x i , y i ) | i = 1, . . . , n} with x i ∈ X , y i ∈ L(Λ) to learn a predictor, or a ranker h : X → L(Λ). While in theory this problem can be transformed into a multiclass problem where each ranking is a separate class, this is in practice undoable, as the number of classes would increase factorially with k. The most usual means to solve this issue is either to decompose the problem into many simpler ones, or to fit a parametric probability distribution over the ranks [START_REF] Cheng | Label ranking methods based on the plackett-luce model[END_REF]. In this paper, we shall focus on a label-wise decomposition of the problem.

This rapid increase of |L(Λ)| also means that getting reliable, precise predictions of ranks is in practice very difficult as k increases. Hence it may be useful to allow the ranker to return partial but reliable predictions.

Label-wise decomposition: learning and predicting

This section details how we propose to reduce the initial ranking problem in a set of k label-wise problems, that we can then solve separately. The idea is the following: since a complete observation corresponds to each label being associated to a unique rank, we can learn a probabilistic model p i : K → [0, 1] with K = {1, 2, . . . , k} and where p ij := p i (j) is interpreted as the probability P (σ(i) = j) that label λ i has rank j. Note that j p ij = 1.

A first step is to decompose the original data set D into k data sets D j = {(x i , σ xi (j)) | i = 1, . . . , n}, j = 1, . . . , k. The decomposition is illustrated by Fig. 1. Estimating the probabilities p ij for a label λ i then comes down to solve an ordinal regression problem [START_REF] Li | Ordinal regression by extended binary classification[END_REF]. In such problems, the rank associated to a label is the one minimizing the expected cost E ij of assigning label λ i to rank j, that depends on p ij and a distance D : K × K → R between ranks as follows:

E ij = k =1 D(j, k)p ik . (1)
Common choices for the distances are the L 1 and L 2 norms, corresponding to

D 1 (j, k) = |j -k| and D 2 (j, k) = (j -k) 2 . ( 2
)
Other choices include for instance the pinball loss [START_REF] Steinwart | Estimating conditional quantiles with the help of the pinball loss[END_REF], that penalizes asymmetrically giving a higher or a lower rank than the actual one. An interest of those in the imprecise setting we will adopt next is that it produces predictions in the form of intervals, i.e., in the sense that {1, 3} cannot be a prediction but {1, 2, 3} can. In this paper, we will focus on the L 1 loss, as it is the most commonly considered in ordinal classification problems

Probability set model

Precise estimates for p i issued from the finite data set D k may be unreliable, especially if these estimates rely on little, noisy or incomplete data. Rather than relying on precise estimates in all cases, we propose to consider an imprecise probabilistic model, that is, to consider for each label λ i a polytope (a convex set) P i of possible probabilities. In our setting, a particularly interesting model are imprecise cumulative distributions [START_REF] Destercke | Unifying practical uncertainty representations: I. generalized p-boxes[END_REF], as they naturally encode the ordinal nature of rankings, and are a common choice in the precise setting [START_REF] Frank | A simple approach to ordinal classification[END_REF]. They consist in providing bounds P (A ), P (A ) on events A = {1, . . . , } and to consider the resulting set

P i = p i : P i (A ) ≤ j=1 p ij ≤ P i (A ), j∈K p ij = 1 . (3)
We will denote by F ij = P i (A j ) and F ij = P i (A j ) the given bounds. Table 2 provides an example of a cumulative distribution that could be obtained in a ranking problem where k = 5 and for a label λ i . For other kinds of sets P i we could consider, see [START_REF] Destercke | Special cases. Introduction to Imprecise Probabilities[END_REF]. This approach requires to learn k different models, one for each label. This is to be compared with the RPC [START_REF] Hüllermeier | Label ranking by learning pairwise preferences[END_REF] approach, in which k(k-1) /2 models (one for each pair of labels) have to be learned. There is therefore a clear computational advantage for the current approach when k increases. It should also be noted that the two approaches rely on different models: while the label-wise decomposition uses learning methods issued from ordinal regression problems, the RPC approach usually uses learning methods issued from binary classification.

Rank-wise inferences

The classical means to compare two ranks as possible predictions, given the probability p i , is to say that rank is preferable to rank m (denoted

m) iff k j=1 D 1 (j, m)p ij ≥ k j=1 D 1 (j, )p ij (4)
That is if the expected cost (loss) of predicting m is higher than the expected cost of predicting . The final prediction is then the rank that is not dominated or preferred to any other (with typically a random choice when there is some indifference between the top ranks). When precise probabilities p i are replaced by probability sets P i , a classical extension3 of this rule is to consider that rank is preferable to rank m iff it is so for every probability in P i , that is if

inf pi∈Pi k j=1 (D 1 (j, m) -D 1 (j, ))p ij (5)
is positive. Note that under this definition we may have simultaneously m and m, therefore there may be multiple undominated, incomparable ranks, in which case the final prediction is a set-valued one.

In general, obtaining the set of predicted values requires to solve Equation ( 5) at most a quadratic number of times (corresponding to each pairwise comparison). However, it has been shown [16, Prop. 1] that when considering D 1 as a cost function, the set of predicted values corresponds to the set of possible medians within P i , which is straightforward to compute if one uses the generalized p-box [START_REF] Destercke | Unifying practical uncertainty representations: I. generalized p-boxes[END_REF] as an uncertainty model. Namely, if F i , F i are the cumulative distributions for label λ i , then the predicted ranks under D 1 cost are

Ri = j ∈ K : F i(j-1) ≤ 0.5 ≤ F ij , F i(0) = 0 , (6)
a set that is always non-empty and straightforward to obtain. Looking back at Table 2, our prediction would have been R = {2, 3, 4}, as these are the three possible median values.

As for the RPC approach (and its cautious versions [START_REF] Cheng | Predicting partial orders: ranking with abstention[END_REF]), the label-wise decomposition requires to aggregate all decomposed models into a single (partial) prediction. Indeed, focusing only on decomposed models P i , nothing forbids to predict the same rank for multiple labels. In the next section, we discuss cautious predictions in the form of sets of ranks, as well as how to resolve inconsistencies.

Global inferences

Once we have retrieved the different set-valued predictions of ranks for each label, two important questions remain:

1. Are those predictions consistent with the constraint that each label should receive a distinct rank? 2. If so, can we reduce the obtained predictions by integrating the aforementioned constraint?

Example 2. To illustrate the issue, let us consider the case where we have four labels λ 1 , λ 2 , λ 3 , λ 4 . Then the following predictions

R1 = {1, 2}, R2 = {1, 2}, R3 = {1, 2}, R4 = {3, 4}
are inconsistent, simply because labels λ 1 , λ 2 , λ 3 cannot be given simultaneously a different rank (note that pair-wisely, they are not conflicting). On the contrary, the following predictions

R1 = {1, 2}, R2 = {1, 2, 3}, R3 = {2}, R4 = {1, 2, 3, 4}
are consistent, and could also be reduced to the unique ranking

R 1 = {1}, R 2 = {3}, R 3 = {2}, R 4 = {4},
as the strong constraint R3 = {2} propagates to all other predictions by removing λ 2 from them, which results in a new strong constraint R * 1 = {1} that also propagates to all other predictions. This redundancy elimination is repeated as new strong constraints emerge until we get the unique ranking above. Such a problem is well known in Constraint Programming [START_REF] Dechter | Constraint processing[END_REF], where it corresponds to the alldifferent constraint. In the case where all rank predictions are intervals, that is a prediction Ri contains all values between min Ri and max Ri , efficient algorithms using the fact that one can concentrate on bounds alone exist, that we can use to speed up computations [START_REF] López-Ortiz | A fast and simple algorithm for bounds consistency of the alldifferent constraint[END_REF].

Discussion of related approaches

As said in the introduction, one of our main goals in this paper is to introduce a label ranking method that allows the ranker to partially abstain when it has insufficient information, therefore producing a corresponding set of possible rankings. We discuss here the usefulness of such rank-wise partial prediction (mainly w.r.t. approaches producing partial orders), as well as some related works.

Partial orders vs imprecise ranks

Most existing methods [START_REF] Cheng | Label ranking with partial abstention based on thresholded probabilistic models[END_REF][START_REF] Cheng | Predicting partial orders: ranking with abstention[END_REF] that propose to make set-valued or cautious predictions in ranking problems consider partial orders as their final predictions, that is pairwise relations x that are transitive and asymmetric, but no longer necessarily complete. To do so, they often rely on decomposition approaches estimating preferences between each pairs of labels [START_REF] Hüllermeier | Label ranking by learning pairwise preferences[END_REF].

However, while a complete order can be equivalently described by the relation

x or by the rank associated to each label, this is no longer true when one considers partial predictions. Indeed, consider for instance the case where the set of rankings over three labels {λ 1 , λ 2 , λ 3 } we would like to predict is S = {λ 1 λ 2 λ 3 , λ 1 ≺ λ 2 ≺ λ 3 }, which could correspond to an instance where λ 2 is a good compromise, and where the population is quite divided about λ 1 and λ 3 that represent more extreme options.

While the set S can be efficiently and exactly represented by providing sets of ranks for each item, none of the information it contains can be retained in a partial order. Indeed, the prediction R1 = {1, 3}, R2 = {2}, R3 = {1, 3} perfectly represents S, while representing it by a partial order would result in the empty relation (since for all pairs i, j, we have λ i λ j and λ j λ i in the set S).

We could find an example that would disadvantage a rank-wise cautious prediction over one using partial orders, as one representation is not more general than the other 4 . Yet, our small example shows that considering both approaches makes sense, as one cannot encapsulate the other, and vice-versa.

Score-based approaches

In a recent literature survey [START_REF] Vembu | Label ranking algorithms: A survey[END_REF], we can see that there are many score-based approaches, already been studied and compared in [START_REF] Hüllermeier | Label ranking by learning pairwise preferences[END_REF], such as constraint classification, log-linear models, etc. Such approaches learn, from the samples, a function h j for each label λ j that will predict a strength h j (x * ) for a new instance. Labels are then ranked accordingly to their predicted strengths.

We will consider a typical example of such approaches, based on SVM, that we will call SVM label ranking (SVM-LR). Vembu and Gärtner [START_REF] Vembu | Label ranking algorithms: A survey[END_REF] show that the SVM method [START_REF] Elisseeff | Kernel methods for multi-labelled classification and categorical regression problems[END_REF] solving multi-label problems can be straightforwardly generalized to a label ranking problem. In contrast to our approach where each model is learned separately, SVM-LR fits all the functions at once, even if at prediction time they are evaluated independently. While this may account for label dependencies, this comes at a computational cost since we have to solve a quadratic optimization problem (i.e. the dual problem introduced in [START_REF] Elisseeff | Kernel methods for multi-labelled classification and categorical regression problems[END_REF]) whose scale increases rapidly as the number of training samples and labels grows.

More precisely, the score functions h j (x * ) = w j | x * are scalar products between a weight vector w j and x * . If α ijq are coefficients that represent the existence of either the preference λ q xi λ j or λ j xi λ q of the instance x i , w j can be obtained from the dual problem in [20, §5] as follows:

w j = 1 2 n i=1   (j,q)∈Ei α ijq - (p,j)∈Ei α ipj   x i (7)
where α ipq are the weighted target values to optimize into the dual problem. E i contains all preferences, i.e. {(p, q) ∈ E i ⇐⇒ λ p λ q }, of the training instance x i .

It may seem at first that such approaches, once made imprecise, could be closer to ours. Indeed, the obtained models h i after training also provide labelwise information. However, if we were to turn these method imprecise and obtain imprecise scores [h i , h i ], the most natural way to build a partial prediction would be to consider that λ i λ j when h i > h j , that is when the score of λ i would certainly be higher than the one of λ j . Such a partial prediction would be an interval order and would again not encompass the same family of subsets of rankings, as it would constitute a restricted setting compared to the one allowing for prediction any partial order.

Experiments

This section describes our experiments made to test if our approach is (1) competitive with existing ones and if (2) the partial predictions indeed provide more reliable inferences by abstaining on badly predicted ranks.

Data sets

The data sets used in the experiments come from the UCI machine learning repository [START_REF] Frank | UCI machine learning repository[END_REF] and the Statlog collection [START_REF] King | Statlog: Comparison of classification algorithms on large real-world problems[END_REF]. They are synthetic label ranking data sets built either from classification or regression problems. From each original data set, a transformed data set (x i , y i ) with complete rankings was obtained by following the procedure described in [START_REF] Cheng | Decision tree and instance-based learning for label ranking[END_REF]. A summary of the data sets used in the experiments is given in Table 3. We perform 10×10-fold cross-validation procedure on all the data sets (c.f. Table 3).

Completeness/correctness trade-off

To answer the question whether our method correctly identifies on which label it is desirable to abstain or to deliver a set of possible rankings, it is necessary to measure two aspects: how accurate and how precise the predictions are. Indeed, a good balance should be sought between informativeness and reliability of the predictions. For this reason, and similarly to what was proposed in the pairwise setting [START_REF] Cheng | Predicting partial orders: ranking with abstention[END_REF], we use a completeness and a correctness measure to assess the quality of the predictions. Given the prediction R = { Ri , i = 1, . . . , k}, we propose as the completeness (CP) and correctness (CR) measure where CP is null if all Ri contains the k possible ranks and has value one if all Ri are reduced to singletons, whilst CR is equivalent to the Spearman Footrule when having a precise observation. Note that classical evaluation measures [START_REF] Zaffalon | Evaluating credal classifiers by utilitydiscounted predictive accuracy[END_REF] used in an IP setting cannot be straightforwardly applied here, as they only extend the 0/1 loss and are not consistent with Spearman Footrule, and adapting costsensitive extensions [START_REF] Yang | The costs of indeterminacy: How to determine them[END_REF] to the ranking setting would require some development.

CP ( R) = k 2 - k i=1 | Ri | k 2 -k and CR( R) = 1 - k i=1 min ri∈ Ri |r i -r i | 0.5k 2 (8)

Our approach

As mentioned in Section 3, our proposal is to fit an imprecise ordinal regression model for every label-wise decomposition D i , in which the lower and upper bounds of the cumulative distribution [F i , F i ] must be estimated in order to predict the set of rankings (Eq. 6) of an unlabeled instance x * . In that regard, we propose to use an extension of Frank and Hall [START_REF] Frank | A simple approach to ordinal classification[END_REF] method to imprecise probabilities, already studied in detail in [START_REF] Destercke | Cautious ordinal classification by binary decomposition[END_REF].

Frank and Hall's method takes advantage of k ordered label values by transforming the original k-label ordinal problem to k -1 binary classification subproblems. Each estimates of the probability5 P i (A ) := F i ( ) where A = {1, . . . , } ⊆ K and the mapping F i : K → [0, 1] can be seen as a discrete cumulative distribution. We simply propose to make these estimates imprecise and to use bounds

P i (A j ) := F i (j) and P i (A j ) := F i (j)
which is indeed a generalized p-box model [START_REF] Destercke | Unifying practical uncertainty representations: I. generalized p-boxes[END_REF], as defined in Equation (3).

To estimate these bounds, we use the naive credal classifier (NCC)6 [START_REF] Zaffalon | The naive credal classifier[END_REF], which extends the classical naive Bayes classifier (NBC), as a base classifier. This classifier imprecision level is controlled through a hyper-parameter s ∈ R.

Indeed, the higher s, the wider the intervals [P i (A j ), P i (A j )]. For s = 0, we retrieve the classical NBC with precise predictions, and for s >>> 0, the NCC model will make vacuous predictions (i.e. all rankings for every label).

However, the imprecision induced by a peculiar value of s differs from a data set to another (as show the values in Figure 2), and it is essential to have an adaptive way to quickly obtain two values:

the value s min corresponding to the value with an average completeness close to 1, making the corresponding classifier close to a precise one. This value is the one we will use to compare our approach to standard, precise ones; the value s max corresponding to the value with an average correctness close to 1, and for which the made predictions are almost always right. The corresponding completeness gives an idea of how much we should abstain to get strong guarantees on the prediction, hence of how "hard" is a given data set.

To find those values, we proceed with the following idea: we start from an initial interval of values [s, s], and from target intervals [CP , CP ] and [CR, CR], typically [0.95, 1] of average completeness and correctness. Note that in case of inconsistent predictions, Ri = ∅ and the completeness is higher than 1 (in such case, we consider CR = 0). For s min , we will typically start from s = 0 (for which CP > 1) and will consider a value s large enough for which CP < 0.95 (e.g., starting from s = 2 as advised in [START_REF] Walley | Inferences from multinomial data: learning about a bag of marbles[END_REF] and doubling s iteratively until CP < 0.95, as when s increases completeness decreases and correctness increases in average). We then proceed by dichotomy to find a value s min for which average predictions are within interval [CP , CP ]. We proceed similarly for s max .

With s min and s max found, a last issue to solve is how to get intermediate values of s ∈ [s min , s max ] in order to get an adaptive evolution of completeness/correctness, as in Figure 2. This is done through a simple procedure: first, we start by calculating the completeness/correctness for the middle value between s min and s max , that is for (s min + s max )/2. We then compute the distance between all the pairs of completeness/correctness values obtained for consecutive s values, and add a new s point in the middle between the two points with the biggest Euclidean distance. We repeat the process until we get the number of s values requested, for which we provide completeness/correctness values. The Figure 2 shows that the boundary values of the hyper-parameter of imprecision s actually significantly depend on the data set. Our approach enables us to find the proper "optimal" value s min for each data set, which can be small (as in glass where s min = 1) or big (as in calhousing where s min = 160).

Figure 2 is already sufficient to show that our abstention method is working as expected, as indeed correctness increases quickly when we allow abstention, that is when completeness decreases. Figure 2(a) shows that for some data sets, one can have an almost perfect correctness while not being totally vacuous (as correctness of almost 1 is reached for a completeness slightly below 0.5, for a value s = 4), while this may not be the case for other more difficult data sets such as calhousing, for which one has to choose a trade-off between completeness and correctness to avoid fully vacuous predictions. Yet, for all data sets (only three being shown for lack of space), we witness a regular increase of correctness.

Comparison with other methods

A remaining question is to know whether our approach is competitive with other state-of-art approaches. To do this, we compare the results obtained on test data sets (in a 10x10 fold cross validation) between the results we obtain for s = s min and several methods. Those results are indeed the closest we can get to precise predictions in our setting. The methods to which we compare ourselves are the following:

-The ranking by pairwise comparisons (RPC), as implemented in [START_REF] Balz | Weka-lr: A label ranking extension for weka[END_REF]; -The Label ranking tree (LRT [START_REF] Cheng | Decision tree and instance-based learning for label ranking[END_REF]), that adopt a local non-decomposed scheme; -The SVM-LR approach that we already described in Section 4.2.

As the NCC deals with discrete attributes, we need to discretize continuous attributes in z intervals before training 7 . While z could be optimized, we use in this paper only two arbitrarily chosen levels of discretization z = 5 and z = 6 (i.e. LR-CSP-5 and LR-CSP-6 models) to compare our method against the others, for simplicity and because our goal is only to show competitiveness of our approach.

As mentioned, we consider the comparison by picking the value s min . By fixing this hyper-parameter regulating the imprecision level of our approach, we then compare the correctness measure [START_REF] Cheng | Decision tree and instance-based learning for label ranking[END_REF] with the Spearman Footrule loss obtained for RCP and LRT methods, and implemented into existing software [START_REF] Balz | Weka-lr: A label ranking extension for weka[END_REF]. For the SVM-LR, of which we did not find an online implementation, we used a Python package8 , which solves a quadratic problem with known solvers [START_REF] Andersen | Cvxopt: A python package for convex optimization[END_REF] for little data sets, or a Frank-Wolfe algorithm for bigger data sets. In fact, Frank-Wolfe's algorithm almost certainly guarantees the convergence to the global minimum for convex surfaces and to a local minimum for non-convex surfaces [START_REF] Lacoste-Julien | Convergence rate of frank-wolfe for non-convex objectives[END_REF].

A last issue to solve is how to handle inconsistency predictions, ones in which the alldifferent constraint would not find a precise or partial solution but an empty one. Here, such predictions are ignored, and our results consider correctness and Spearman footrule on consistent solutions only, as dealing with inconsistent predictions will be the object of future works.

Results

The average performances and their ranks in parentheses obtained in terms of the correctness (CR) measure are shown in Table 4(a) and 4(b), with discretization 5 and 6 respectively applied to our proposal method LR-CSP. A Friedman test [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF] on the ranks yields p-values of 0.00006176 and 0.0001097 for LR-CSP-5 and LR-CSP-6, respectively, thus strongly suggesting performance differences between the algorithms. The Nemenyi post-hoc test (see Table 5) further indicates that LR-CSP-5 (and LR-CSP-6) is significantly better than SVM-LR. Our approach also remains competitive with LRT and RPC.

Finally, recall that our method is also quite fast to compute, thanks to the simultaneous use of decomposition (requiring to build k classifiers), and of probability sets and loss functions offering computational advantages that make the prediction step very efficient. Also, thanks to the fact that our predictions are intervals, i.e. sets of ranks without holes in them, we can use very efficient algorithms to treat the alldifferent constraints [START_REF] López-Ortiz | A fast and simple algorithm for bounds consistency of the alldifferent constraint[END_REF].

Note also that our proposal discretized at z = 6 intervals gets more accurate predictions (and also indicate a little drop in the p-value of all comparisons of Table 5) what can suggest us that an optimal value of ẑ may improve the prediction performance (all that remains, of course, hypothetical). LRT RPC SVM-LR 1 LR-CSP-5 = 0.8161 0.6452 0.000066 2 LR-CSP-6 = 0.6450 0.4600 0.000066

Conclusion and perspectives

In this paper, we have proposed a method to make partial predictions in label ranking, using a label-wise decomposition as well as a new kind of partial predictions in terms of possible ranks. The experiments on synthetic data sets show that our proposed model (LR-CSP) produces reliable and cautious predictions and performs close to or even outperforms the existing alternative models. This is quite encouraging, as we left a lot of room for optimization, e.g., in the base classifiers or in the discretization. However, while our method extends straightforwardly to partially observed rankings in training data when those are top-k rankings (considering for instance the rank of all remaining labels as k +1), it may be trickier to apply it to pairwise rankings, another popular way to get such data. Some of our future works will focus on that.

Fig. 1 .

 1 Fig. 1. Label-wise decomposition of rankings

Fig. 2 .

 2 Fig. 2. Evolution of the hyper-parameter s on glass, stock and calhousing data sets.

Table 1 .

 1 An example of label ranking data set D

	X1 X2 X3 X4	Y
	107.1 25 Blue 60 λ1 λ3 λ2
	-50 10 Red 40 λ2 λ3 λ1
	200.6 30 Blue 58 λ2 λ1 λ3
	107.1 5 Green 33 λ1 λ2 λ3
	. . . . . . . . . . . .	. . .

rank of label i in the order relation x .

  2 .

			D
			X1 X2 X3 X4		Y
			107.1 25 Blue 60	λ1	λ3	λ2
			-50 10 Red 40	λ2	λ3	λ1
			200.6 30 Blue 58	λ2	λ1	λ3
			107.1 5 Green 33	λ1	λ2	λ3
			. . . . . . . . . . . .		. . .
	D1		D2			D3
	X1 X2 X3 X4 Y	X1 X2 X3 X4 Y	X1 X2 X3 X4 Y
	107.1 25 Blue 60 1	107.1 25 Blue 60 3	107.1 25 Blue 60 2
	-50 10 Red 40 3	-50 10 Red 40 1	-50 10 Red 40 2
	200.6 30 Blue 58 2	200.6 30 Blue 58 1	200.6 30 Blue 58 3
	107.1 5 Green 33 1	107.1 5 Green 33 2	107.1 5 Green 33 3
	. . . . . . . . .	. . . . . .	. . . . . . . . .	. . . . . .	. . . . . . . . .	. . .

Table 2 .

 2 Imprecise cumulative distribution for λi The approach easily adapts to the other losses.

		Rank j 1	2	3	4 5
		F ij 0.15 0.55 0.70 0.95 1
	2	F ij 0.10 0.30 0.45 0.80 1

Table 3 .

 3 Experimental data sets

	# Data set	Type	#Inst #Attributes #Labels
	a authorship classification 841	70	4
	b bodyfat	regression 252	7	7
	c calhousing regression 20640	4	4
	d cpu-small regression 8192	6	5
	e	fried	regression 40768	9	5
	f	glass	classification 214	9	6
	g housing	regression 506	6	6
	h	iris	classification 150	4	3
	i pendigits classification 10992	16	10
	j segment classification 2310	18	7
	k	stock	regression 950	5	5
	l	vehicle classification 846	18	4
	m vowel classification 528	10	11
	n	wine	classification 178	13	3

Table 4 .

 4 Average correctness accuracies (%) compared to LR-CSP-5 (left) and LR-CSP-6 (right) ) 95.14 ± 0.05 (1) 94.12 ± 0.01 (2) 58.75 ± 2.71 (4) j 91.20 ± 0.85 (3) 96.11 ± 0.10 (1) 94.52 ± 0.03 (2) 66.25 ± 3.05 (4) k 88.63 ± 1.53 (2) 91.64 ± 0.27 (1) 82.23 ± 0.08 (3) 75.20 ± 0.17 (4) l 85.29 ± 1.91 (3) 88.03 ± 0.44 (2) 89.24 ± 0.14 (1) 81.93 ± 1.00 (4) m 88.23 ± 1.00 (1) 84.40 ± 0.62 (2) 72.88 ± 0.06 (3) 65.41 ± 1.21 (4) n 98.20 ± 1.19 (1) 91.80 ± 0.87 (4) 94.58 ± 0.61 (2) 94.56 ± 0.50 (3) avg. 85.03 ± 1.49(1.64) 83.18 ± 0.45(2.21) 81.67 ± 0.19(2.36) 69.30 ± 1.02(3.79)

		LR-CSP-5	LRT	RPC	SVM-LR		LR-CSP-6	LRT	RPC	SVM-LR
	a 94.19 ± 1.31 (1) 91.49 ± 0.31 (3) 93.25 ± 0.25 (2) 64.75 ± 0.41 (4)	a 93.90 ± 0.69 (1) 91.53 ± 0.31 (3) 93.21 ± 0.23 (2) 64.42 ± 0.36 (4)
	b 53.30 ± 3.81 (1) 41.56 ± 1.17 (4) 52.05 ± 0.42 (2) 52.56 ± 0.39 (3)	b 54.12 ± 3.73 (1) 41.70 ± 1.48 (4) 50.43 ± 0.39 (3) 51.10 ± 0.49 (2)
	c 61.46 ± 0.92 (1) 58.33 ± 0.28 (2) 51.76 ± 0.01 (3) 38.48 ± 0.02 (4)	c 61.05 ± 0.80 (1) 58.37 ± 0.28 (2) 51.85 ± 0.02 (3) 38.45 ± 0.02 (4)
	d 68.66 ± 0.63 (1) 60.96 ± 0.24 (3) 62.10 ± 0.04 (2) 47.08 ± 0.85 (4)	d 68.72 ± 1.42 (1) 60.76 ± 0.30 (3) 61.93 ± 0.04 (2) 46.71 ± 0.87 (4)
	e 99.34 ± 0.07 (1) 91.29 ± 0.08 (3) 99.92 ± 0.01 (2) 84.19 ± 2.63 (4)	e 99.20 ± 0.07 (2) 91.26 ± 0.06 (3) 99.92 ± 0.01 (1) 84.18 ± 2.67 (4)
	f	90.92 ± 3.48 (3) 91.75 ± 0.50 (1) 91.05 ± 0.18 (2) 87.16 ± 0.34 (4)	f	91.95 ± 2.90 (1) 91.59 ± 0.47 (2) 90.83 ± 0.24 (3) 85.68 ± 0.33 (4)
	g 79.18 ± 1.98 (2) 84.55 ± 0.51 (1) 74.54 ± 0.15 (3) 69.54 ± 0.35 (4)	g 79.21 ± 3.37 (2) 85.09 ± 0.46 (1) 74.86 ± 0.16 (3) 70.16 ± 0.46 (4)
	h 96.86 ± 3.72 (1) 96.77 ± 0.60 (2) 93.16 ± 0.56 (3) 88.39 ± 0.41 (4)	h 99.36 ± 1.28 (1) 97.16 ± 0.55 (2) 92.75 ± 0.58 (3) 87.39 ± 0.37 (4)
	i	91.55 ± 0.24 (3) 95.15 ± 0.05 (1) 94.12 ± 0.01 (2) 58.66 ± 2.71 (4)	i	91.31 ± 0.14 (3
	j	90.37 ± 0.46 (3) 96.19 ± 0.09 (1) 94.56 ± 0.02 (2) 66.39 ± 3.00 (4)
	k 86.75 ± 1.59 (2) 91.46 ± 0.34 (1) 82.59 ± 0.06 (3) 74.49 ± 0.20 (4)
	l	84.81 ± 2.13 (3) 88.07 ± 0.40 (2) 89.28 ± 0.17 (1) 82.30 ± 0.96 (4)
	m 86.32 ± 2.34 (1) 85.36 ± 0.97 (2) 74.32 ± 0.06 (3) 66.60 ± 1.23 (4)
	n 97.98 ± 2.89 (1) 91.75 ± 0.88 (4) 94.55 ± 0.62 (2) 94.53 ± 0.50 (3)
	avg. 84.41 ± 1.83(1.72) 83.19 ± 0.46(2.14) 81.95 ± 0.18(2.28) 69.65 ± 1.00(3.86)

Table 5 .

 5 Nemenyi post-hoc test: null hypothesis H0 and p-value # H0

Also, known as maximality criterion[START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF].

In the sense that the family of subsets of ranking representable by one is not included in the other.

For readability, we here drop the condition of a new instance in all probabilities, i.e. Pi(A ) := Pi(A |x * ).

Bearing in mind that they can be replaced by any other imprecise classifiers, see[START_REF] Augustin | Introduction to imprecise probabilities[END_REF][START_REF] Carranza-Alarcon | Imprecise gaussian discriminant classification[END_REF].

Available in https://github.com/sdestercke/classifip.

Available in https://pypi.org/project/svm-label-ranking/

Acknowledgments. This work was carried out in the framework of the Labex MS2T and PreServe projects, funded by the French Government, through the National Agency for Research (Reference ANR-11-IDEX-0004-02 and ANR-18-CE23-0008).


Sébastien Destercke
email: sebastien.destercke@hds.utc.fr

Agnès Rico
email: agnes.rico@univ-lyon1.fr

Olivier Strauss
email: olivier.strauss@lirmm.fr

Approximating general kernels by extended fuzzy measures: application to filtering

Keywords: Signal filtering, Probability intervals, Signed fuzzy measures, Interval-valued filtering

Convolution kernels are essential tools in signal processing: they are used to filter noisy signal, interpolate discrete signals, . . . . However, in a given application, it is often hard to select an optimal shape of the kernel. This is why, in practice, it may be useful to possess efficient tools to perform a robustness analysis, talking the form in our case of an imprecise convolution. When convolution kernels are positive, their formal equivalence with probability distributions allows one to use imprecise probability theory to achieve such an imprecise convolution. However, many kernels can have negative values, in which case the previous equivalence does not hold anymore. Yet, we show mathematically in this paper that, while the formal equivalence is lost, the computational tools used to describe sets of probabilities by intervals on the singletons still retain their key properties when used to approximate sets of (possibly) non-positive kernels. We then illustrate their use on a single application that consists of filtering a human electrocardiogram signal by using a low-pass filter whose order is imprecisely known. We show, in this experiment, that the proposed approach leads to tighter bounds than previously proposed approaches.

Introduction

Filtering a signal aims at removing some unwanted components or features, i.e. other signals or measurement noise. It is a common problem in both digital analysis and signal processing [START_REF] Jan | Digital Signal Filtering, Analyses and Restoration[END_REF]. In this context, kernels are used for impulse response modelling, interpolation, linear and non-linear transformations, stochastic or band-pass filtering, etc. However, how to choose a particular kernel and its parameters to filter a given signal is often a tricky question.

A way to circumvent this difficulty is to filter the signal with a convex set of kernels, thus ending up with a set-valued signal, often summarized by lower/upper bounds. The set of kernels has to be convex due to the fact that, if two kernels are suitable to achieve the filtering, a combination of those two kernel should be suitable too. A key problem is then to propose a model to approximate this convex set of kernels in a reasonable way (i.e., without losing too much information) that will perform the set-valued filtering in an algorithmic efficient way guaranteeing the provided bounds (in the sense that the sets of signals obtained by filtering with each kernel of the set is contained within the bounds).

In the case of positive summative kernels, i.e., positive functions summing up to one, previous works used the formal equivalence between such kernels and probabilities at their advantage, and have proposed to use well-known probability set models as approximation tools. For example, maxitive [START_REF] Loquin | On the granularity of summative kernels[END_REF] and cloudy [START_REF] Destercke | Filtering with clouds[END_REF] kernels respectively use possibility distributions and generalized p-boxes to model sets of kernels, and have used the properties of the induced lower measure on events to propose efficient filtering solutions from a computational standpoint.

However, when the kernel set to approximate contains functions that are not positive everywhere (but still sum up to one), this formal analogy is lost, and imprecise probabilistic tools cannot be used straightforwardly to model the set of kernels. Yet, recent works [START_REF] Strauss | Where the domination of maxitive kernels is extended to signed values[END_REF] have shown that in some cases such imprecise models can be meaningfully extended to accommodate negative values, while preserving the properties that makes them interesting for signal filtering (i.e., the guarantees of obtained bounds and the algorithmic efficiency). More formally, this means that we have to study the extension of Choquet-integral based digital filtering to the situation where kernels κ : X → [-A, B] ⊆ R can be any (bounded) function.

In this work, we show that this is also true for another popular model, namely probability intervals [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF], that consists in providing lower/upper bound on singleton probabilities. In particular, while principle applied to sets of additive but possibly negative measures lead to a model inducing a non-monotone set function, called signed measure, we show that the Choquet integral of such a measure still leads to interesting bounds for the filtered signal, in the sense that these bounds are guaranteed and are obtained for specific additive measure dominated by the signed measure. Let us call this new kind of interval-valued kernels imprecise kernels.

The paper is structured as follows. Section 2 recalls the setting we consider, as well as a few preliminaries. We demonstrate in Section 3 that probability intervals can be meaningfully extended to accommodate sets of additive but non-positive measures. Section 4 shows how these results can be applied to numerical signal filtering.

Preliminaries: filtering, signed kernels and fuzzy measures

We assume a finite space X = {x 1 , . . . , x n } of n points, that is a subset of an infinite discrete space Ω that may be a discretization of a continuous space (e.g., the real line), and an observed signal whose values at these points are f (x 1 ), . . . , f (x n ), that can represent a time-or space-dependent record (EEG signal, sound, etc.). A kernel is here a bounded discrete function η : Ω → [-A, B], often computed from a continuous kernel (corresponding, for example, to assumed filter impulse response). This kernel is such that ∑ x∈Ω η(x) = 1, and for a given kernel we will denote b η and a η the sum of the positive and negative parts of the kernel, respectively. That is:

b η = ∑ x∈Ω max(0, η(x)) a η = ∑ x∈Ω max(0, -η(x))
Filtering the signal f by using the kernel η consists of estimating the filtered signal f at each point x of X by:

f (x) = n ∑ i=1 f (x i )η(x i -x) = n ∑ i=1 f (x i )η x (x i ), (1)
where ∀y ∈ X , η x (y) = η(yx).

Since filtering f amounts to compute the value of f at each point of X , let us simplify the previous formal statements by assuming that, at each point x of X exists a kernel κ = η x . Note that the domain of κ can be restricted to X without any loss of generality. Moreover, b κ = ∑ x∈Ω max(0, κ(x)) = b η and a κ = ∑ x∈Ω max(0, -κ(x)) = a η .

From any kernel κ, we can build a set function µ κ : 2 X → [-a κ , b κ ] such that µ κ (A) = ∑ x∈A κ(x) for any A ⊆ X . It is clear that we have µ κ (X ) = 1 and µ κ ( / 0) = 0, but that we can have µ κ (A) > µ κ (B) with A ⊂ B (simply consider A = / 0 and B = x where κ(x) < 0). Note also that if A ∩ B = / 0, we keep µ κ (A ∪ B) = µ κ (A) + µ κ (B), hence the additivity of the measure.

Estimating the value of the signal f in a given point x ∈ X requires to compute a value C κ that can be written as a weighted sum

C κ ( f ) = ∑ n i=1 f (x i )κ(x i ).
If we order and rank the values of f such that f

(x (1) ) ≤ f (x (2) ) ≤ . . . ≤ f (x (n) ), this weighted sum can be rewritten f (x) = C κ ( f ) = n ∑ i=1 f (x (i) ) -f (x (i-1) ) µ κ (A (i) ) (2)
where

A (i) = {x (i) , . . . , x (n) }, f (x (0) ) = 0 and A (1) = X .
One can already notice the similarity with the usual Choquet integral.

Example 1. Consider a kernel η that is a Hermite polynomial of degree 3, and its sampled version pictured in Figure 1, with a = -2. From the picture, it is obvious that some of the values are negative.

η(x) =      (a + 2)|x| 3 -(a + 3)|x| 2 + 1 if |x| ≤ 1 a|x| 3 -5a|x| 2 + 8a|x| -4a if 1 ≤ |x| ≤ 2 0 else
In this paper, we consider the case where the ideal η is ill-known, that is we only know that, for each x ∈ X , η belongs to a convex set N , which entails that κ belongs to a convex set K . This set N (and K ) can reflect, for example, our uncertainty about which kernel should be ideally used (they can vary in shape, bandwidth, etc.). In the following section, we propose to approximate this set K of kernels that we deem suitable to filter f at point x by a measure µ K that is close to a fuzzy measure: it

-3 -2 -1 1 2 3 0.5 1 x κ(x)
Fig. 1. Sampled Hermite polynomial of degree 3

shares with such measures the fact that µ K ( / 0) = 0 and µ K (X ) = 1, and will be a standard fuzzy measure in the case where all κ ∈ K are positive. However, in the case of negative κ ∈ K , we may have µ K (A) < 0 for some A, as well as have for some couple A ⊂ B non-monotonicity in the form µ K (A) > µ K (B).

Approximating set of kernels with extended probability intervals

We now consider a set K of kernels κ defined on X , that can be discretised versions of a set of continuous kernels. We make no assumptions about this set, except for the fact that each kernel κ ∈ K is bounded and such that ∑ x∈X κ(x) = 1. If K contains a large amount of kernels, filtering the signal with each of them and getting the set answer {C κ |κ ∈ K } for each possible point of the signal can be untractable. Rather than doing so, we may search some efficient way to find some lower and upper bounds of {C κ |κ ∈ K } that are not too wide.

To achieve such a task, we propose here to use tools inspired by the imprecise probabilistic literature, namely non-additive set functions and the Choquet integral. To use such tools, we must first build a set-function approximating the set K . To do so, we will extend probabilistic intervals [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF] that consist in associating lower and upper bounds [l(x), u(x)] to each atom, given a set of probabilities. In our case, for each elements x ∈ X , we consider the interval-valued kernel

ρ(x) = [ρ(x), ρ(x)] (3)
such that the bounds are given, for each x ∈ X , as

ρ(x) = inf κ∈K κ(x) and ρ(x) = sup κ∈K κ(x). (4)
Clearly, both can be negative and are not classical probability intervals. Nevertheless, we will show that set-functions induced by these bounds enjoy properties similar to those of standard probability intervals, and hence can be used to efficiently approximate

{C κ |κ ∈ K }.
From the imprecise kernel ρ, we propose to build the set function µ :

X → R such that, for A ⊆ X µ K (A) = max{ ∑ x∈A ρ(x), 1 -∑ x ∈A ρ(x)}, (5)
which is formally the same equation as the one used for probability intervals. We still have that µ( / 0) = 0 and µ(X ) = 1 (as ρ(x) ≤ κ(x) for any µ ∈ K , we necessarily have ∑ x∈X ρ(x) ≤ 1). However, we can have µ(A) > µ(B) with A ⊂ B, meaning that µ is not a classical fuzzy measure, and not a so-called coherent lower probability 4 . It is also non-additive, as we have

µ(A ∪ B) = µ(A) + µ(B) for A ∩ B = / 0 in general. Simply replacing µ κ by µ K in Equation 2 gives us C K ( f ) = n ∑ i=1 f (x (i) ) -f (x (i-1) ) µ K (A (i) ) (6)
= n ∑ i=1 f (x (i) ) µ(A (i) ) -µ(A (i+1) ) , (7)
where

A (n+1) = / 0 and f (x 0 ) = 0. In the positive case, C K ( f ) is well-known to outer-approximate {C κ |κ ∈ K }, as C K ( f ) = inf µ κ ≥µ K C κ ( f ).
In the rest of this section, we show that this is also true when the set K contains non-positive functions. In particular, we will show:

1. that Equation ( 6) still provides a lower bound of inf µ κ ≥µ K C κ ( f ) and, 2. that this lower bound corresponds to an infimum, meaning that it is obtained for a peculiar additive measure of K .

To show the first point, we will first prove the following proposition concerning µ:

Proposition 1. Given a set K , we have for any A ⊆ X

µ K (A) ≤ inf κ∈K µ κ (A)
Proof. To prove it, consider a given κ ∈ K , we have

µ κ (A) = ∑ x∈A κ(x) = 1-∑ x ∈A κ(x)
since ∑ x∈X κ(x) = 1. Now, from Eq. ( 5), we have either

-µ K (A) = ∑ x∈A ρ(x) ≤ ∑ x∈A κ(x) -µ K (A) = 1 -∑ x ∈A ρ(x) ≤ 1 -∑ x ∈A κ(x)
and since this is true for any κ ∈ K , we have the inequality.

Note that µ is a tight measure on singletons, since µ(x) = ρ(x) = inf κ∈K κ(x), hence any set-function higher than µ on singletons would not be a lower envelope of K . The fact that C K ( f ) ≤ C κ ( f ) for any κ ∈ K then simply follows from Proposition 1. If K reduces to a single kernel κ, then we find back the classical filtering result. Note that C K ( f ) is equivalent to filter f , that is to compute C κ , with the specific kernel κ(x (i) ) = µ(A (i) )µ(A (i+1) ). To prove that C K is a tight lower bound, it remains to show that such a kernel is within K .

To show that the bound obtained by Equation ( 6) is actually obtained by an additive measure dominated by µ K , we will first show that it still satisfies a convexity property Proposition 2. Given a set K of kernels, the measure µ K is 2-monotone and convex, as for every pair A, B ⊆ X we have

µ K (A ∪ B) + µ K (A ∩ B) ≥ µ K (A) + µ K (B)
Proof. We will mainly adapt the proof from [1, Proposition 5] to the case of nonpositive kernels and signed measures, as its mechanism still works in this case.

A key element will be to show that for any two subsets C, D with C ∩ D = / 0, there exists a single additive measure µ κ with κ ∈ K such that

µ K (C) = µ κ (C) and µ K (C ∪ D) = µ κ (C ∪ D), (8)
as if we then take C = A ∩ B and D = (A ∪ B) \ (A ∩ B) and choose κ so that it coincides on µ K for events C, D, we do have

µ K (A ∩ B) + µ K (A ∪ B) = µ κ (A ∩ B) + µ κ (A ∪ B) = µ κ (A) + µ κ (B) ≥ µ K (A) + µ K (B).
By Equation ( 5), we know that

µ K (A) = max{ ∑ x∈A ρ(x), 1 -∑ x ∈A ρ(x)}
which means that for any event A, we have two possibilities (the two terms of the max). This means four possibilities when considering C and C ∪ D together. Here, we will only show that Equation ( 8) is true for one of those case, as the proofs for the other cases follow similar reasoning. So let us consider the case where

µ K (C) = ∑ x∈C ρ(x) ≥ 1 -∑ x ∈C ρ(x), µ K (C ∪ D) = 1 -∑ x ∈C∪D ρ(x) ≥ ∑ x∈C∪D ρ(x).
Let us now consider the κ distribution such that κ

(x) = ρ(x) if x ∈ C, κ(x) = ρ(x) if x ∈ (C ∪ D) c
, that fits the requirements of Equation ( 8) and so far satisfy the constraints on K . To get an additive kernel whose weights sum up to one, we must still assign Hence C K is a signed Choquet integral with respect to the convex capacity µ K . We have µ K ( / 0) = 0, so according to [10, Theorem 3], C K is the minimum of the integrals or expectations taken with respect to the additive measures dominating µ K , i.e., C K ( f ) = min{C µ |µ ∈ core(µ K }, where the core of a capacity is the set of additive set function that lie above the capacity everywhere. This allows us to state the following property

λ = 1 -∑ x∈C ρ(x) -∑ x∈(C∪D) c ρ(x)
Proposition 3. C µ K ( f ) = min{C µ |µ ∈ core(µ K )}.
We have therefore shown that, to approximate the result of filtering with any set of kernels (bounded and with no gain), it is still possible to use tools issued from imprecise probabilistic literature. However, it is even clearer in this case that such tools should not be interpreted straightforwardly as uncertainty models (as set-functions are not monotone, a property satisfied by standard fuzzy measures and coherent lower probabilities), but as convenient and efficient tools to perform robust filtering.

Remark 1. An upper bound C K ( f ) can be obtained by using the conjugate capacity µ K (A) = 1µ K (A c ) in Equation ( 6). As µ K is a concave capacity, we also have C K ( f ) = max{C µ |µ ∈ anticore(µ K )}, where the anticore of a capacity is the set of additive set function that lie below the capacity everywhere. Note that µ ∈ core(µ K ) is equivalent to µ ∈ anticore(µ K ).

Example 2. Consider the imprecise kernel ρ whose values on X = {x 1 , . . . , x 5 } are given in Table 1. For such an imprecise kernel, we have for instance µ K ({x 1 }) = x 1 x 2 x 3 x 4 x 5 ρ -0.1 0.3 0.9 0.3 -0.1 ρ -0.2 0.2 0.8 0.2 -0.2 Table 1. Imprecise kernel example max(-0.2, 1-(1.4)) = -0.2 and µ K ({x 1 , x 5 }) = max(-0.4, 1-(1.5)) = -0.4, showing that the defined measure is not monotonic with inclusion.

Finally, it should be noted that applying Equation ( 6) does not require to evaluate our lower measure on every possible events, but only in a linear number of them (once function values have been ordered). Moreover, evaluating the value of this lower measure on any interval is quite straightforward given Equation [START_REF] Jan | Digital Signal Filtering, Analyses and Restoration[END_REF]. So, even though the measure is non-additive (and not necessarily monotonic), evaluating the filtered values can be done quite efficiently.

Illustration of signed filtering on a real case

We now illustrate the use of our method on a real case scenario involving the filtering of human electrocardiogram (ECG) signals, using data initially collected to detect heart conditions under different settings [START_REF] Poree | Stability analysis of the 12lead ecg morphology in different physiological conditions of interest for biometric applications[END_REF]. ECG signals contain many types of noises -e.g. baseline wander, power-line interference, electromyographic (EMG) noise, electrode motion artifact noise, etc. Baseline wander is a low-frequency noise of around 0.5 to 0.6 Hz that is usually removed during the recording by a high-pass filtering of cut-off frequency 0.5 to 0.6 Hz. EMG noise, which is a high frequency noise of above 100 Hz, may be removed by a digital low-pass filter with an appropriate cut-off frequency. In [START_REF] Poree | Stability analysis of the 12lead ecg morphology in different physiological conditions of interest for biometric applications[END_REF] they propose to use a cut-off frequency of 45 Hz to preprocess the ECG signals. The noisy ECG signal to be filtered is presented in Figure 2. To prevent phase distortion in the bandpass, a Butterworth kernel should preferably be chosen. Moreover, since the signal has not to be processed on line, a symmetric Butterworth filter can be used, is the combination of a causal and an anti-causal Butterworth kernel. Using such an even kernel prevents from phase delay.

In this experiment, we suppose that the 45 Hz cutoff frequency proposed in [START_REF] Poree | Stability analysis of the 12lead ecg morphology in different physiological conditions of interest for biometric applications[END_REF] is appropriate while the suitable order of the kernel is imprecisely known. Figure 3 presents the superposition of 13 kernels that are the impulse responses of the 13 symmetric lowpass Butterworth kernels of orders 1 to 13. Figure 3.a shows the superimposed kernels, that constitute the set N of kernels we have to approximate.

Applying our approximation to N provides the upper (ρ) and lower (ρ) bounds of the imprecise kernel that are pictured in Figure 3.c, with the lower in red, the upper in blue. These bounds are simply obtained by computing ρ = min n=1...13 η n and ρ = max n=1...13 η n where η n is the impulse response of the lowpass symmetric Butterworth kernel of order n with cutoff frequency equal to 45 Hz.

To have a comparison point, we will also apply to the same signal the maxitive approach proposed in [START_REF] Strauss | Where the domination of maxitive kernels is extended to signed values[END_REF], where a signed kernel is approximated by a couple of extended possibility distributions (π -, π + ). This couple of functions is computed in this way: π + = max n=1...13 π + n , where π + n is the most specific maxitive kernel that dominates η + n = max(0, η n ) and π -= max n=1...13 π - n , where π - n is the most specific maxitive ker- nel that dominates η - n = max(0, -η n ) (see [START_REF] Strauss | Where the domination of maxitive kernels is extended to signed values[END_REF] Equation ( 4)). Figure 3.b plots π + (in blue) and -π -(in red). One can readily notice that, if their shape are similar, their boundary values are quite different (the imprecise maxitive kernel varying between -0.5 and 1.5, and our imprecise kernel between -0.01 and 0.07).

In Figures 5 and4, we have plotted the ECG signal of Figure 2 filtered by the 13 kernels of Figure 3.a, as well as the imprecise signal obtained by using the most specific signed maxitive kernel defined by the couple of functions (π -, π + ), and the imprecise signal obtained by using the imprecise kernel plotted in Figure 3.c, respectively. The upper bounds of the imprecise filtered signals are plotted in blue while their lower bounds is plotted in red. It seems obvious, by looking at Figure 4, that the imprecise signal obtained by this new approach reaches our pursued goal, i.e. the obtained imprecise signal contains all the signals that would have been obtained by using the conventional approach. Moreover, the bounds are reasonably tight, which means that the core of the imprecise kernel is specific enough as an approximation. Indeed, non-parametric imprecise representation of kernels always leads to include unwanted kernels, and may lead to over-conservative bounds. This is even more patent if we compare it to the signal bounds obtained with the maxitive approach, as this latter one leads to a less specific interval-valued signal. For instance, the values spanned by the interval-valued signal in our approach span from -500 to 200, and -800 to 500 for the maxitive approach. Another possible advantage of our approach is that the Kroenecker impulse is not necessarily included in the described set of kernels, while it is systematically included in a maxitive kernel, meaning that in this latter case the interval-valued signal always include the noisy original signal itself.

Discussion and conclusion

In this paper, we have explored to which extent some of the tools usually used to model and reason with sets of probabilities can still be used when considering sets of additive measures that can be negative and fail the monotonicity condition. Such a situation happens, for instance, when filtering a signal.

We have proved that approximating such sets with interval-valued bounds on singletons by extending probability intervals still provides tools that allow on the one hand to use efficient algorithms, and on the other hand to get tight bounds (in the sense that obtained bounds are reached by specific additive measures). We have provided some preliminary experiments showing how our results could be used in filtering problems.

Future works could include the investigation of other imprecise probabilistic models that also offer computational advantages in the case of positive measures, such as using lower and upper bounds over sequences of nested events [START_REF] Destercke | Unifying practical uncertainty representations: I. Generalized p-boxes[END_REF][START_REF] Strauss | F-boxes for filtering[END_REF]. Complementarily, we could investigate whether computations with some parametric sets of signed kernels can be achieved exactly and efficiently without resorting to an approximation, as can be sometimes done for positive kernels [START_REF] Dendievel | Density estimation with imprecise kernels: Application to classification[END_REF].

  mass over the singletons composing D. One can see that∑ x∈D ρ(x) ≤ λ ≤ ∑ x∈D ρ(x): for instance, that ∑ x∈D ρ(x) ≤ λ immediately follows from the fact that in this sub-case 1 -∑ x ∈C∪D ρ(x) ≥ ∑ x∈C∪D ρ(x). This means that one can choose values κ(x) ∈ [ρ(x), ρ(x)] for each x ∈ D such that ∑ x∈D κ(x) = λ .So in this case we can build an additive κ ∈ K with ∑ κ(x) = 1.That a single additive κ ∈ K reaching the bounds µ K (C) and µ K (C ∪ D) can be built in other sub-cases can be done similarly (we refer to [1, Proposition 5], as the proofs are analogous).

Fig. 2 .

 2 Fig.2. The ECG signal to be low-pass filtered.

Fig. 3 .Fig. 3 .Fig. 3 .

 333 Fig. 3.a: 13 superimposed symmetric Butterworth kernel impulse responses.

Fig. 4 .

 4 Fig. 4. The ECG signal being low-pass filtered by the 13 classical symmetric Butterworth (in cyan) and by the imprecise kernel (in red -lower and blue -upper).

Fig. 5 .

 5 Fig. 5. The ECG signal being low-pass filtered by the 13 classical symmetric Butterworth (in cyan) and by the signed maxitive kernel (in red -lower and blue -upper).

The lower envelope of a set of probability measures.


Juliette Ortholand
email: juliette.ortholand@hds.utc.fr

Sébastien Destercke
email: sebastien.destercke@hds.utc.fr

Khaled Belahcene
email: khaled.belahcene@hds.utc.fr

Equity in learning problems: an OWA approach

published or not. The documents may come

Introduction

The typical way to learn a predictive model from data is to search for the model that minimizes the average loss of the predictions made by this model on a set of training data. However, minimizing the average loss may well lead to poor results on some under-represented populations. This is a well known fact, that happens in several settings that have proposed different solutions to the issue: in class imbalanced data sets, concerning for instance rare diseases or default (of payment, of production), the classical solution is to modify the sample sizes, for instance by over-sampling instances of the under-represented class [START_REF] Han | Borderline-smote: a new over-sampling method in imbalanced data sets learning[END_REF]; in fairness issues [START_REF] Hashimoto | Fairness without demographics in repeated loss minimization[END_REF], where the goal can be to protect sensitive populations or minorities, often by modifying not the sample but the loss function adequately; in extreme statistics [START_REF] Jalalzai | On binary classification in extreme regions[END_REF], where one must guarantee that rare instances will be well predicted, for instance by learning a model specifically dedicated to them.

In this paper, we look at another aspects of misrepresentation of some data in the learning problem. Namely, we want to ensure that the loss incurred for data poorly represented in the feature space (whatever their class is) is not high. This is yet a different kind of under-representation of some population, whose closest related problem is the previously mentioned one of extreme statistics [START_REF] Jalalzai | On binary classification in extreme regions[END_REF]. Our goal here is to propose a method ensuring that under-represented data will not suffer from a too high loss, while preserving a good average accuracy. To perform such a task, we will modify the classical expected loss by using the notion of ordered weighted averaging, an often used notion in fairness problems within computational social choice [START_REF] Shams | Minimizing and balancing envy among agents using ordered weighted average[END_REF].

More precisely, we will propose to give more weight to unknown zones. The paper is organised as follows: the formal mathematical framework can be found in Section 2, where we provide reminders, notations and prelimnarieis, and in Section 3, where we describe our proposal. This is followed by the experiments in Section 4 then by some related works in the Section 5. The paper ends with some conclusion and discussion on our work in Section 6.

Preliminaries

We consider a standard supervised problem where we have observations (x i , y i ) ∈ X × Y, i = 1, . . . , n where x i are some inputs, and y i the observed outputs.

Supervised classification via Empirical Risk Minimization

The general goal of supervised machine learning is to estimate a predictive model h * : X → Y, issued from a space H of hypothesis, such that the model delivers good prediction in average. This principle is most often translated by choosing the model minimizing the empirical risk, i.e.,

h * = arg min h∈H R emp (h) where R emp (h) = n i=1 (h(x i ), y i ) (1)
with (h(x i ), y i ) the loss of predicting h(x) when y is the observed value. This empirical loss serves as an estimate of the true loss, i.e., R(h) = X ×Y (h(x), y)dp(x, y), that is inaccessible as we do not know p(x, y). Also, in many cases, H is a parametric family with parameters θ ∈ Θ, and in this case we will denote by h θ the predictive function having θ for parameter.

Some shortcomings due to the averaging of the risk

Guaranteeing a low average loss does not prevent from having large losses for poorly represented groups of values, and even in some cases promote such large discrepancies [START_REF] Hashimoto | Fairness without demographics in repeated loss minimization[END_REF].

Example 1. Figure 1 displays two different classes (i.e., y ∈ {0, 1}) represented in red and blue, that suffer from the problem we consider in this paper. Indeed, the two classes are balanced (there are about as much red as blue), but some region of the input space are less represented than others. More precisely, the data corresponding to each class have been generated by the following distributions:

X|y = 0 ∼ π 1 0 N ( 1 1 , 3 0 0 0.5 ) + π 2 0 N ( 16 6 , 1 0 0 0.5 ) X|y = 1 ∼ π 1 0 N ( 0 2 , 3 0 0 0.5 ) + π 2 0 N ( 15 7 , 1 0 0 0.5 )
with π 1 0 = π 1 1 = 0.95 and π 2 0 = π 2 1 = 0.05, meaning that the upper-right region is much less represented than the lower-left in Figure 1. The frontier in this region corresponds to the one obtained by a logistic regression trained according to Equation 1. It is easy to see that the model does a very bad job at predicting the data in the upper-right corner, as could be expected. The OWA operators, initially introduced by Yager [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF], apply a weighted aggregation functions on ordered values. Usually, the OWA is applied to a vector a = (a 1 , . . . , a n ) of real-valued quantities a i ∈ R, and is defined by a set (w 1 , . . . , w n ) of positive weights (w i ≥ 0) summing up to one ( i w i = 1). Formally speaking, the OWA consists in first permuting the values a i in ascending order, i.e., such that for i < j, we have a σ(i) ≤ a σ(j) , with σ denoting the permutation. The classical OWA operator is then

OW A(a 1 , . . . , a n ) = n i=1 w i a σ(i) . (2)
The OWA operator therefore allows to put different strength on lower or higher values, irrespectively of where they appear in the vector a. We retrieve the arithmetic mean for w i = 1 /n, and kth percentiles when we have wk /n = 1 for some i. In particular, the minimum and maximum values are respectively retrieved for w 1 = 1 and w n = 1. They characterize what Yager called extreme behaviour of "andness" and "orness", respectively.

Our Proposal

In this paper, we consider the use of OWA operators [START_REF] Grabisch | OWA operators and nonadditive integrals[END_REF], that propose to make weighted averages not on the initial observations (x i , y i ) and their associated losses, but on a re-ordering of them, with the idea that a higher weight should be given to poorly represented instances, to be ranked first in our proposal. We will denote by (x σ(i) , y σ(i) ) the corresponding permutation on observations. More precisely, we propose not to optimise R emp (h), but rather R OW A (h), where

R OW A (h) = n i=1 w i (h(x σ(i) ), y σ(i) ) (3)
with the idea that when i ≤ j, the instances x σ(i) is not as well represented as x σ(j) in the data set. It should be noted that in contrast to usual OWA and Equation (3), we will not considering the re-ordering of values (h(x σ(i) ), y σ(i) ), but a re-ordering based on the representativeness of the instances x i .

Ranking instances by representativeness

A first task to apply Equation (3) to our setting is to order the instances by their representativeness in the data set. To do this, we can order them by measuring, for instance, the epistemic uncertainty, or lack of knowledge concerning each instance x i , e.g., following ideas from [START_REF] Senge | Reliable classification: Learning classifiers that distinguish aleatoric and epistemic uncertainty[END_REF] to obtain a score E i for each instance x i , and then ordering them accordingly in Equation ( 3), i.e., σ(i

) ≤ σ(j) if E i ≥ E j .
One simple idea that we will apply in the following is to measure the density of points around a neighbourhood of fixed size around x i to compute its associated epistemic uncertainty. For this, an easy technique one can use is to simply perform a kernel density estimation through the formula

f (x) = 1 n n i=1 K (x -x i )
with K a kernel function. Common choices of kernel functions include:

the Parzen window, defined as K (x -x i ) = 1 2 1 |x-xi|< , that simply comes down to count the number of points that are at a distance below a certain ; the triangle kernel, defined as

K (x -x i ) = ( 1 -|x -x i |)1 |x-xi|< , for which
weights decrease linearly from one to zero depending on the distance;

the normal window, defined as

K (x -x i ) = 1 √ 2π e -(x-x i ) 2 2 2
, for which the weights for the points depend on a normal distribution around the chosen point with a mean of zero and a standard deviation of .

The three kernels are pictured in Figure 2a.

Once a kernel is chosen, we can then simply use f (x i ) = E i as a score quantifying epistemic uncertainty. Note that in our case, it is not important to have a reliable estimate of the density (a very difficult problem), but to just have a reliable ordering between the different points, as f (x i ) will only be used to order values in OWA operators.

Figure 2b represents the distribution of the epistemic uncertainty of points given in Figure 1, computed for a triangular kernel with being the mean distance between points. One can readily see that the most uncertain points (hence the first in the re-ordering) are those in the upper right corner, that is precisely those for which we would like to increase accuracy, followed by the ones on the border of the big cluster.

OWA weights to induce equity

The next step is how we can choose the weights in Equation (3) so as to balance the accuracy in the model between well-represented and poorly represented instances. Clearly, if we pick w i = 1 /n, this re-ordering is a useless step and leads us to the usual solution. However, we can easily pick weights that will enforce giving more importance to poorly represented instances. More precisely, we can pick a function φ : [0, 1] → [0, 1] and take as weights

w i = φ( i /n) -φ( i-1 /n) if φ(x) =
x, then we retrieve the weighted average. If φ is concave, then we start giving more weights to first ordered instances, and less weight to last ordered instances. In terms of OWA, we increase the "andness" of the function, that we can then parameterize to be more or less fair. Ideally, this number of parameters should not be too high, and example of such functions include:

-The L p norm on with p ∈ [0, 1], which function is φ(x) = x p . The lower p, the more we increase the "andness"

piece-wise linear functions made of two linear parts, that can be define with two parameters p and prop as follows:

φ(x) = px if x ≤ prop 1-p×prop 1-prop x + prop(p-1) 1-prop if prop ≤ x ≤ 1 ( 4
)
where p defines the slope before the abscissa value prop.

Both are represented on Figure 3 with the L1 /2 norm and the linear by part function with prop = 0.1 and p = 4.

Fig. 3: Different functions for φ Remark 1 (Model optimisation). Note that as we do not modify the nature of the loss function , most optimisation techniques used for the arithmetic mean will be straightforward to extend. Thanks to the versatility of φ, we can also think of other kind of behaviours than concave ones. For instance, an S-shaped function would amount to try to balance between being quite good on poorly represented as well as quite good of very-well represented groups, thus protecting minorities and majorities.

Experiments

This section presents some experiments using our approach to try to augment the accuracy on the poorly represented data, that we will call minority, while preserving a good average accuracy. After quickly describing the chosen model, we will provide results first on synthetic data sets, second on real-world data sets. In this latter case, since there are no benchmark data sets focusing on the problem we try to solve, we will try to adapt common UCI data sets [START_REF] Frank | UCI machine learning repository[END_REF] to our setting.

Implementing the proposal

We will apply our approach to standard regularized logistic regression in binary classification problems, with the output class Y ∈ {0, 1}. Let us simply recall that in this case, we learn a probabilistic model of the shape

h θ (x) = 1 1 + exp -θx (5)
with h θ (x) = p(y = 1|x). The associated loss is

(y, h θ (x)) = -(ylog(h θ (x)) + (1 -y)log(1 -h θ (x)) + θ 2 (6)
that corresponds to a logarithmic loss with a L 2 regularisation term. In experiments, we use python sklearn package to fit the different models, with which it is straightforward to add weights to samples.

In the experiments, we used the triangle kernel applied to data with an Euclidean distance computed between them. The reason for this choice is that it gives no ties between values f (x i ) in practice (while Parzen windows delivers the same value when having the same number of data within it), and that it has a finite support, therefore being more coherent than the normal kernel with the fact that epistemic uncertainty is mostly a local property. However, our tests with other kernel functions show no significant differences.

Regarding the parametric shape of the OWA, we picked the shape given by Equation ( 4), as in our experiments the use of the L p norm tended to give too quickly too much importance to poorly represented data, introducing sometimes important discontinuities in our results for small changes of the parameter. This can already be seen in Figure 3. Thus, the φ function depends on two parameters p, the slope of the first linear part of the function and prop, the abscissa of the slope breaking point.

As our aim is to improve accuracy on minorities while keeping a good average accuracy, this means that our performances will be measures according to two values: the average accuracy on the minority samples only, acc ∈ [0, 1], and the classical average accuracy, ACC ∈ [0, 1]. For this reasons, we will present our experimental results a Pareto front on the space [0, 1]×[0, 1], as for a given couple (p, prop) k of the proposal, we will obtain a pair (acc k , ACC k ). This means that we will present the results for all non-dominated values, that is all (acc k , ACC k ) such that there will be no other pairs (p, prop) k with acc k ≥ acc k and ACC k ≥ ACC k .

Synthetic data set

In the first set of experiments, we simply consider the same distributions as the ones described in Example 1 for a binary problem.

As in Example 1, minorities of each class represent about 5% of the total quantity of samples from that class. For each set of experiments, we generate 1000 points for the training set, and as much for the testing set.

In the experiments, we proceeded with a simple grid search to fix p and prop. We let p vary between 1 and 5 with a 0.5 increment, and prop between [0.1, 0.3] with a step of 0.05. Every test is made on 10 different sets of data and the mean Fig. 4: Logistic Regression Boundaries for extrem values is taken to obtain reliable estimates. The total accuracy and the accuracy of the minority are studied.

Figure 4 illustrates the results obtained for a particular run and give the model obtained for the parameters p = 5.0 and prop = 0.2. One can easily see that the obtained model is much more relevant on the minorities, as it starts to discriminate the two classes in this region.

One question though is to know whether this potential benefit on the minority region does not alter too much the overall accuracy. The answer is provided by Figure 5 that displays the obtained Pareto front as well as the results of the basic model (1, -). One can observe that the accuracy on the minority region can increase by more than 10%, going from 0.53 to 0.66, while the loss on the average accuracy is below 3%. Note that the Pareto allows a possible decision maker to finely choose the trade-off between minority protection and overall performances.

UCI data sets

As we said, there are to our knowledge no benchmark data set that explicitly deals with the problem of within-class imbalance, the situation described by our synthetic example. For this reason, we tried to apply it to UCI data sets susceptible to display similar behaviours.

To test whether this is the case, a simple procedure is adopted: we split the data set into training and test sets, and order the elements of the test set according to their epistemic uncertainty, computed by using the samples of the training set. A logistic regression is then fitted to the data, and we check the difference between the global average accuracy (ACC) and the average accuracy of the first α% of the ordered test samples (acc). If the difference ACC -acc is big enough, we retain the data set. In our experiment, we fixed the value α to 10%, and similarly to the previous case, proceeded to apply our method by letting p vary between 1 and 5 with a 0.5 increment, and prop between [0.1, 0.3] with a step of 0.05. Each training/testing experiment is made by taking 50% of the data set as training, and the process is repeated a hundred times for each configuration, the mean being kept as a representative point.

Data set Samples Percentage of positive class

Istanbul Stock Exchange [START_REF] Akbilgic | A novel hybrid rbf neural networks model as a forecaster[END_REF] 536 50% Credit Approval [START_REF] Dua | UCI machine learning repository[END_REF] 653 45% Vertebral Column [START_REF] Dua | UCI machine learning repository[END_REF] 310 68%

Table 1: Data set descriptions Perhaps surprisingly, it proved quite hard in this manner to find suitable data sets. Finally, we retained three binary classification data sets that are summarised in Table 1.

The resulting Pareto fronts of our experiments, along with the accuracies of the base model corresponding to (1, -), are given in Figures 6 (Istanbul), 7 (Credit) and 8 (Vertebral). In each of them, we can see a possible increase in the minority accuracy that out-weights the drop in global, average accuracy. However, it is clear that since for these data sets the difference between acc and ACC is already quite low for the basic model (given by the point (1, -) in So, while the presented results confirm that the proposed approach is working, future works should focus on exhibiting similar behaviours in existing data sets, maybe by revisiting the ordering we use, the considered learning algorithm or by focusing on specific data sets such as class imbalanced data sets, hoping that the imbalance in the classes is transferred to the input space.

Links with other learning and estimation approaches

To our knowledge, the learning approach presented here is quite original, in the sense that applying OWA to learning problems in order to solve inequities has, to our knowledge, not been done before.

From OWA to probability sets

A now well-established trend in the learning literature is the so-called distributionally robust approach [START_REF] Abadeh | Distributionally robust logistic regression[END_REF][START_REF] Gabrel | Recent advances in robust optimization: An overview[END_REF] that consider the problem of finding the minimax model over a possible set P of probability distributions, mostly defined as a neighbourhood of the empirical distribution of the observations (x i , y i ). Such approaches have been applied, for instance, to fairness issues in machine learning [START_REF] Hashimoto | Fairness without demographics in repeated loss minimization[END_REF] or to transfer learning problems [START_REF] Abadeh | Wasserstein distributionally robust kalman filtering[END_REF].

Since it is well-known that the OWA operator correspond to apply a Choquet integral with a specific Choquet measure [START_REF] Grabisch | OWA operators and nonadditive integrals[END_REF], and that such Choquet integral can correspond to lower/upper expectations computed for specific probability sets, it would be interesting to study under which conditions and to which extent our current approach could be interpreted as the solution of a minimax problem for some specific set P 5.2 From OWA loss to weighted likelihood Another classical way to learn a model, and particularly probabilistic models, is through the maximisation of a likelihood function. In such a case, each parameter value θ determine a probability distribution of a random variable X. First recall that the likelihood of a parameter value θ, given a set of observations

x i ∈ X is L(θ|x i ) = i p θ (x i )
Provided we consider the logarithmic loss in Equation ( 3), one can easily express our weighting scheme in terms of likelihood. For this, it is sufficient to consider the log-likelihood

C(θ|x i ) = -ln(L(θ|x i )) = - i ln(p θ (x i )) (7)
where the loss is ln(p θ (x i )). We can then apply the OWA loss instead of the current loss to get C OW A (θ|x i ) =i w i ln(p θ (x σ(i) )) with w i the OWA weights.It is then possible to go back to the formula of the likelihood, obtaining L(X) = i p θ (x σ(i) ) wi as our new, weighted likelihood. Thus the OWA transformation on the loss which corresponds to multiply the terms by weights, is equivalent to a exponent operation with weight for the likelihood. While such an exponent weight may appear odd at first, it should be noticed that it has been proposed and used before like in [START_REF] Agostinelli | Weighted likelihood in bayesian inference[END_REF], where it has been used to down weight anomalous point in Bayesian prediction.

Conclusion

In this paper, we have presented an original approach, based on OWA operators, to obtain more balanced and equitable classifiers in those problems where data can be scarce in some regions of the input space. Such an approach aims at ensuring that even poorly represented instances will be treated fairly, in the sense that we will not allow them to suffer huge losses, while keeping an average loss comparable to the one obtained without including such equity requirement.

Our illustrative experiments on synthetic data sets indeed show that the method is appropriate, and allows one to obtain a more balanced model. We have also shown that the same observation can be made on UCI data sets, albeit the improvement is here much more general, due to the fact that there is no benchmark data sets explicitly suffering from the problem we have considered in this paper.

We nevertheless believe that the idea of using aggregation operators issued from the social choice literature to solve inequities and unfairness in supervised learning procedure is a promising idea, that needs to be developed. This study is simply a first proposal going in this direction, and many aspects remain to be studied, such as the nature of the ordering between instances or whether there are algorithms where our approach can make a bigger difference, notably in the case of multi-class problems, as we only used logistic regression on binary problems here.

Fig. 1 :

 1 Fig. 1: Logistic Regression boundary

  Fig. 2: Epistemic uncertainty

Fig. 5 :

 5 Fig. 5: Pareto front on synthetic data set

Fig. 6 :Fig. 7 :Fig. 8 :

 678 Fig. 6: Istanbul Stock Exchange Pareto Front with (p, prop) values


The Dark Side of the Wall: Atomic Force Microscopy Revelations on Drug Resistance and Adhesion.

Hélène Martin-Yken 1 , Cécile Formosa-Dague 1 , Marion Schiavone 1 , and Etienne Dague 2 .

1 LISBP, INSA, Université de Toulouse, INRA UMR792, CNRS UMR5504, 135 avenue de Rangueil, Toulouse, F-31077, France 2 LAAS, CNRS, 7 Avenue du Colonel Roche, Toulouse, F-31077, France e-mail: helene.martin@insa-toulouse.fr

The cell wall of yeast and fungi plays a crucial role in the way these cells sense, respond and adapt to environmental perturbations. Using recent Atomic Force Microscopy technological developments, the biophysical consequences of different stresses on the major human fungal pathogen, Candida albicans, were imaged and measured. Morphological changes were characterized at the nanoscale, including surface roughness, elasticity and adhesive properties. Exposure to the antifungal Caspofungin was shown to cause a deep cell wall remodeling with major modifications of chitin and beta-glucan content. Remarkably, a low dose of Caspofungin (i.e., 0.5 × MIC) provoked a strong expression of adhesive proteins on the cell surface of C. albicans, a side effect highly relevant considering its wide spread medical use. Moreover, Single Molecule Force Spectroscopy (SMFS) experiments by AFM allowed us to visualize the organization of these adhesins, to map them on the cell surface and to quantify the adhesion forces, including on cells undergoing mophogenetic differentiation. Combined with molecular biology tools, this approach enabled us to unravel the particular contribution of previously uncharacterized proteins (PGA22 and PGA59) to C. albicans adhesion mechanism. In addition, functionalizing the AFM tip with antibodies allows following the appearance of specific proteins, while precisely mapping them at the cell surface and even measuring the time scale of their progression through the cell wall. The example of Hwp1 appearance on geminating hyphal tubes will be illustrated.