Yonatan Carlos

Carranza Alarcón

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

Multi-label Chaining with Imprecise Probabilities

Keywords: imprecise probabilities, multi-label, classifier chains

We present two different strategies to extend the classical multi-label chaining approach to handle imprecise probability estimates. These estimates use convex sets of distributions (or credal sets) in order to describe our uncertainty rather than a precise one. The main reasons one could have for using such estimations are (1) to make cautious predictions (or no decision at all) when a high uncertainty is detected in the chaining and (2) to make better precise predictions by avoiding biases caused in early decisions in the chaining. We adapt both strategies to the case of the naive credal classifier, showing that this adaptations are computationally efficient. Our experimental results on missing labels, which investigate how reliable these predictions are in both approaches, indicate that our approaches produce relevant cautiousness on those hard-to-predict instances where the precise models fail.

Multi-label classification (MLC) is a generalization of traditional classification (with a single label), as well as a special case of multi-task learning. This approach is increasingly required in different research fields, such as the classification of proteins in bioinformatics [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF], text classification in information retrieval [START_REF] Fürnkranz | Multilabel classification via calibrated label ranking[END_REF], object recognition in computer vision [START_REF] Boutell | Learning multi-label scene classification[END_REF], and so on.

A classical issue in multi-label learning techniques is how to integrate the possible dependencies between labels while keeping the inference task tractable. Indeed, while decomposition techniques [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF][START_REF] Fürnkranz | Multilabel classification via calibrated label ranking[END_REF] such as Binary relevance or Calibrated ranking allow to speed up both the learning and inference tasks, they roughly ignore the label dependencies, while using a fully specified model such as in probabilistic trees [START_REF] Dembczynski | Bayes optimal multilabel classification via probabilistic classifier chains[END_REF] requires, at worst, to scan all possible predictions (whose quantity grows exponentially in the number of labels). A popular technique, known as chaining [START_REF] Read | Classifier chains for multi-label classification[END_REF] to solve this issue, at least for the inference task, is to use heuristic predictions: they consists in using, incrementally, the predictions made on previous labels as additional conditional features to help better predict the relevance of a current label, rather than using the prediction probabilities.

To the best of our knowledge, there are only a few works on multi-label classification producing cautious predictions, such as the reject option [START_REF] Pillai | Multi-label classification with a reject option[END_REF], partial predictions [START_REF] Destercke | Multilabel prediction with probability sets: the hamming loss case[END_REF][START_REF] Antonucci | The multilabel naive credal classifier[END_REF] or abstaining labels [START_REF] Vu-Linh Nguyen | Reliable multilabel classification: Prediction with partial abstention[END_REF], but none of these have studied this issue in chaining (or classifier-chains approach).

In this paper, we consider the problem of extending chaining to the imprecise probabilistic case, and propose two different extensions, as some predictive probabilities are too imprecise to use predicted labels, henceforth called abstained labels, in the chaining. The first extension treats the abstained labels in a robust way, exploring all possible conditional situation in order not to propagate early uncertain decisions, whereas the latter marginalizes the probabilistic model over those labels, ignoring them in the predictive model.

Section 1 introduces the notations that we use for the multi-label setting, and gives the necessary reminders about making inferences with convex sets of probabilities. In Section 2, we recall the classical classifier-chains approach and then we present our extended approaches based on imprecise probabilities. Section 3 then shows that in the case of the naive credal classifier (NCC) [START_REF] Zaffalon | The naive credal classifier[END_REF], those strategies can be performed in polynomial time.

Finally, in Section 4, we perform a set of experiments on real data sets, which are perturbed with missing labels, in order to investigate how cautious (when we abstain on labels difficult to predict) is our approach. In order to adhere to the page limit, all proofs and supplementary experimental results have been relegated to the appendix of an online extended version [START_REF] Carranza Alarcón | Multi-label chaining with imprecise probabilities[END_REF].

Problem Setting

In the multi-label problem, an instance x of an input space X = R p is no longer associated with a single label m k of an output space K = {m 1 , . . . , m m }, as in the traditional classification problem, but with a subset of labels Λ x ⊆ K often called the set of relevant labels while its complement K\Λ x is considered as irrelevant for x. Let Y = {0, 1} m be a m-dimensional binary space and y = (y 1 , . . . , y m ) ∈ Y be any element of Y such that y i = 1 if and only if m i ∈ Λ x .

From a decision theoretic approach (DTA), the goal of the multi-label problem is the same as usual classification. Given a probability distribution P fitting a set of i.i.d. observations D = {(x i , y i )|i = 1, . . . , N } issued from a (true) theoretical probability distribution P : X × Y → [0, 1], DTA aims to minimize the risk of getting missclassification with respect to a specified loss function (

•, •): R (Y, h(X)) = min h E P [ (Y, h(X))] . (1)
where h : X → Y is a m-dimensional vector function. If (•, •) is defined instancewise, that is : Y×Y → R, the solution of Equation ( 1) is obtained by minimizing the conditional expected risk (cf. [7, eq. 3] and [9, eq. 2.21])

h(x) = arg min y∈Y E PY |x [ (Y, y)] = arg min y∈Y y ∈Y P (Y = y |X = x) (y , y) (2)
or, equivalently, by picking the undominated elements of the order relation1 over Y ×Y for which y 1 y 2 (y 1 is preferred to/dominates y 2 ) iff

E PY |x (y 2 , •) -(y 1 , •) = E PY |x (y 2 , •) -E PY |x (y 1 , •) ≥ 0. (3)
This amounts to saying that exchanging y 2 for y 1 would incur a non-negative expected loss (which is not desirable).

In this paper, we are also interested in making set-valued predictions when uncertainty is too high (e.g. due to insufficient evidence to include or discard a label as relevant, see Example 1). The set-valued prediction will here be described as a partial binary vector y * ∈ Y where Y = {0, 1, * } m is the new output space with a new element * representing the abstention. For instance, a partial prediction y * = ( * , 1, 0) corresponds to two plausible binary vector solutions {(0, 1, 0), (1, 1, 0)} ⊆ Y . To obtain such predictions, we will use imprecise probabilities as a well-founded framework.

Notions about Imprecise Probabilities

Imprecise probabilities consist in representing our uncertainty by a convex set of probability distributions P X [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF][START_REF] Augustin | Introduction to imprecise probabilities[END_REF] (i.e. a credal set [START_REF] Levi | The enterprise of knowledge: An essay on knowledge, credal probability, and chance[END_REF]), defined over a space X rather than by a precise probability measure P X [START_REF] Taylor | Introduction to measure and integration[END_REF]. Given such a set of distributions P X and any measurable event A ⊆ X , we can define the notions of lower and upper probabilities as:

P X (A) = inf P ∈P X P (A) and P X (A) = sup P ∈P X P (A) (4)
where P X (A) = P X (A) only when we have sufficient information about event A. The lower probability is dual to the upper [START_REF] Augustin | Introduction to imprecise probabilities[END_REF], in the sense that P X (A) = 1 -P X (A c ) where A c is the complement of A. Many authors [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF][START_REF] Zaffalon | The naive credal classifier[END_REF] have argued that when information is lacking or imprecise, considering credal sets as our model of information better describes our actual uncertainty. However, such an approach comes with extra challenges in the learning and inference step, especially in combinatorial domains. In this paper, we will consider making a chain of binary inferences, each inference influenced by the previous one. If we consider Y = {0, 1} as the output space and Y as a univariate random variable on Y, a standard way to take a decision with abstention given a credal set

P on Y is ŷ =      1 if P x (Y = 1) > 0.5, 0 if P x (Y = 1) < 0.5, * if 0.5 ∈ P x (Y = 1), P x (Y = 1) . ( 5
)
The next example illustrates such notions on a multi-label example Example 1. We consider an output space of two labels K = {m 1 , m 2 }, a single binary feature x 1 and Table 1 Based on the probabilities of Table 1, we have that P0 (y 1 = 0) := P (y 1 = 0|x 1 = 0) = 1 and P0 (y 2 = 0) ∈ [0.4, 0.7], therefore not knowing whether P0 (y 2 = 0) > 0.5. This could lead us to propose as a prediction ŷ * = (0, * ). On the contrary, the imprecision on the right hand-side is such that P1 (y 2 = 0) ∈ [0.6, 0.8], leading to the precise prediction ŷ * = (1, 0).

Multilabel Chaining with Imprecise Probabilities

Solving (2) can already be computationally prohibitive in the precise case [START_REF] Dembczynski | Bayes optimal multilabel classification via probabilistic classifier chains[END_REF], which is why heuristic to approximate inferences done on the full joint models such as the chain model have been proposed. This section recalls its basics and presents our proposed extension. To do so, we will need a couple notations: we will denote by I subsets of label indices and by j = {1, . . . , j} the set of the first j integers. Given a prediction made in the j first labels, we will denote by 1. (relevant labels) I j R ⊆ j the indices of the labels predicted as relevant among the j first, i.e. ∀i ∈ I j R , y i = 1, 2. (irrelevant labels) I j I ⊆ j , I j I ∩I j R = ∅ the indices of the labels predicted as irrelevant among the j first, i.e. ∀i ∈ I j I , y i = 0, and 3. (abstained labels) I j A = j \(I j R ∪ I j I ) the indices of the labels on which we abstained among the j first, i.e. ∀i ∈ I j A , y i = {0, 1} := * , and of course I j = I j A ∪ I j R ∪ I j I = j . Besides, for the sake of simplicity, we will use the notation

P j-1 x (Y j = 1) := P (Y j = 1|Y I j-1= ŷI j-1 , X = x), (6)
where ŷI j-1 is a (j -1)-dimensional vector that contains the previously inferred precise and/or abstained values of labels having indices I j-1 .

Precise Probabilistic Chaining

Classifier chains is a well-known approach exploiting dependencies among labels by fitting at each step of the chain (see Figure 1) a new classifier model h j : X × {0, 1} j-1 → {0, 1} predicting the relevance of the jth label. This classifier combines the original input space attribute and all previous predictions in the chain in order to create a new input space X * j-1 = X × {0, 1} j-1 , j ∈ N >0 . In brief, we consider a chain h = (h 1 , . . . , h m ) of binary classifiers resulting in the full prediction ŷ obtained by solving each single classifier as follows ŷj := h j (x) = arg max y∈{0,1}

P j-1 x (Y j = y). (7)
The classical multi-label chaining then works as follows:

1. Random label ordering. We randomly pick an order between labels and assume that the indices are relabelled in an increasing order. 2. Prediction j th label. For a label y j and the previous predictions on labels y 1 , . . . , y j-1 and let I j-1 R , I j-1 I ⊆ j -1 be set of indices of relevant and irrelevant labels with

I j-1 R ∩I j-1 I = ∅.
Then, the prediction of ŷj (or

h j (x)) for a new instance x is ŷj = 1 if P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0) = P j-1 x (Y j = 1) ≥ 0.5 0 if P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0) = P j-1 x (Y j = 1) < 0.5 (8)
Figure 1 summarizes the procedure presented above, as well as the obtained predictions for a specific case (in bold red predicted labels and probabilities). In what follows, we propose two different extensions of precise chaining based on imprecise probability estimates, in which the final prediction belongs to the output space Y of partial bianry vectors.

Y1 = 1 (1, 1) P x (Y 2 = 1|Y 1 = 1) = 0.6 (1, 0) Px( Y2 = 0|Y1 = 1) = 0.4 P x (Y 1 = 1) = 0. 6 Y1 = 0 (0, 1) P x (Y 2 = 1|Y 1 = 0) = 0.1 (0, 0) Px( Y2 = 0|Y1 = 0) = 0.9 Px (Y1 = 0) = 0. 4 (a) Chaining with {Y1, Y2} Y2 = 1 (1, 1) P x (Y 1 = 1|Y 2 = 1) = 0.9 (0, 1) Px( Y1 = 0|Y2 = 1) = 0.1 P x (Y 2 = 1) = 0. 4 Y2 = 0 (1, 0) P x (Y 1 = 1|Y 2 = 0) = 0.4 (0, 0) Px( Y1 = 0|Y2 = 0) = 0.6 Px (Y2 = 0) = 0. 6 (b) Chaining with {Y2, Y1}

Imprecise Probabilistic Chaining

We now consider that the estimates P

j-1 x (Y j = 1) can become imprecise, that is, we now have [P j-1 x ](Y j = y j ) := [P j-1 x (Y j = y j ), P j-1 x (Y j = y j )].
The basic idea of using such estimates is that in the chaining, we should be cautious when the classifier is unsure about the most probable prediction. In this section, we describe two different strategies (or extensions) in a general way, and we will propose an adaptation of those strategies to the NCC in the next section.

Let us first formulate the generic procedure to calculate the probability bound of the j th label, 1. Random label ordering. As in the precise case.

2. Prediction j th label. For a given label y j , we assume we have (possily imprecise) predictions for y 1 , . . . , y j-1 such that I j-1

A

are the indices of labels on which we abstained { * } so far, and I j-1 R and I j-1 I remain the indices of relevant and irrelevant labels, such that I j-1

A ∪ I j-1 R ∪ I j-1 I = I j-1 . Then, we calculate [P j-1 x
](Y j = 1) in order to predict the label ŷj as

ŷj =      1 if P j-1 x (Y j = 1) > 0.5, 0 if P j-1 x (Y j = 1) < 0.5, * if 0.5 ∈ [P j-1 x (Y j = 1), P j-1 x (Y j = 1)], (9)
where this last equation is a slight variation of Equation ( 5) by using the new input space X * j-1 .

We propose the following two different extensions of how to calculate [P

j-1 x
](Y j = 1) at each inference step of the imprecise chaining.

Imprecise Branching The first strategy treats unsure predictions in a robust way, considering all possible branchings in the chaining as soon as there is an abstained label. Thus, the estimation of [P j-1

x (Y j = 1), P j-1 x (Y j = 1)] (for Y j = 0, it directly obtains as P j-1 x (Y j = 0) = 1 -P j-1 x (Y j = 1)
, and similarly for the upper bound) comes down to computing

P j-1 x (Y j = 1) = min y∈{0,1} |I j-1 A | P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0, Y I j-1 A = y), P j-1 x (Y j = 1) = max y∈{0,1} |I j-1 A | P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0, Y I j-1 A = y).

(IB)

So we consider all possible replacements of variables for which we have abstained so far. This corresponds to a very robust version of the chaining, where every possible path is explored. It will propagate imprecision along the tree, and may produce quite imprecise evaluations, especially if we abstain on the first labels.

Illustrations providing some intuition about this strategy can be seen in

1 = 1 (1, 1) P x(Y 2 = 1|Y 1 = 1) = 0.6 (1, 0) Px( Y2 = 0|Y1 = 1) = 0.4 [ Px]( Y 1= 1) [0 .4 5, 0. 7] Y 1 = 0 (0, 1) P x(Y 2 = 1|Y 1 = 0) = 0.1 (0, 0) Px( Y2 = 0|Y1 = 0) = 0.9 [ Px ]( Y1 = 0) [0 .3 , 0. 55 ] (a) Imprecise chain on labels {Y1, Y2} 0 1 1 1 1 (0, 1, 1, 1, 1) 0 1 (0, 1, 1, 0, 1) 0 1 1 1 (0, 0, 1, 1, 1) 0 1 (0, 0, 1, 0, 1) (b) Evaluating Y5 = 1 label with {0, * , 1, * , ?}

Fig. 2. Imprecise branching strategy

In Figure 2(a), we will consider the previous example (see Figure 1) in order to study in detail how we should calculate probability bounds [P j-1

x (Y j = 1), P j-1 x (Y j = 1)].
For the sake of simplicity, we assume that probabilities about Y 2 are precise and that the probability bounds for Y 1 = 1 is P 0 x (Y 1 = 1) ∈ [0.45, 0.70]. Taking all possible paths (bold on Figure 2(a)) for which Y 2 = 1, we get

P 1 x (Y 2 = 1) = min y1∈{0,1} P x (Y 2 = 1|Y 1 = y 1 ) = min(0.1, 0.6) = 0.1, P 1 x (Y 2 = 1) = max y1∈{0,1} P x (Y 2 = 1|Y 1 = y 1 ) = max(0.1, 0.6) = 0.6,
which means that in this case we would abstain on both labels, i.e. (ŷ 1 , ŷ2 )=( * , * ).

Marginalization The second strategy simply ignores unsure predictions in the chaining. Its interest is that it will not propagate imprecision in the tree. Thus, we begin by presenting the general formulation (which will after lead to the formulation without unsureness) which takes into account unsure predicted labels conditionally, so the estimation of probability bounds [P j-1

x (Y j = 1), P j-1 x (Y j = 1)] comes down to computing

P j-1 x (Y j = 1) = P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0, Y I j-1 A = {0, 1} |I j-1 A | ), P j-1 x (Y j = 1) = P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0, Y I j-1 A = {0, 1} |I j-1 A | ), (MAR)
where I j-1

A

= {i 1 , . . . , i k } denotes the set of indices of abstained labels and the last conditional term of probability bounds can be defined as

Y I j-1 A = {0, 1} |I j-1 A | := (Y i1 = 0 ∪ Y i1 = 1) ∩ • • • ∩ (Y i k = 0 ∪ Y i k = 1). ( 10
)
The MAR formulation can be reduced by using Bayes's theorem in conjunction with the law of total probability. That is, for instance, given abstained labels (Y 1 = * , Y 3 = * ) and the precise prediction (Y 2 = 1), inferring Y 4 = 1 comes down to computing

P x (Y 4 = 1|(Y 1 = 0 ∪ Y 1 = 1), Y 2 = 1, (Y 3 = 0 ∪ Y 3 = 1)) as follows y3,y1∈{0,1} 2 P x (Y 4 = 1, Y 1 = y 1 , Y 2 = 1, Y 3 = y 3 ) y3,y1∈{0,1} 2 P x (Y 1 = y 1 , Y 2 = 1, Y 3 = y 3 ) = P x (Y 4 = 1, Y 2 = 1) P x (Y 2 = 1) = P x (Y 4 = 1|Y 2 = 1),
An illustration providing some intuition about this last example can be seen in Fig. 3(a), in which we draw the possible path to infer the label Y 4 (considering a third branch in the chain to represent abstained labels).

The results of the last example can easily be generalized, and hence, MAR comes down to calculating the new formulation called (MAR*)

P j-1 x (Y j = 1) = min P ∈P * P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0), (11)
P j-1 x (Y j = 1) = max P ∈P * P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0). ( 12
)
where P * is simply the set of joint probability distributions described by the imprecise probabilistic tree (we refer to [START_REF] De Cooman | Imprecise probability trees: Bridging two theories of imprecise probability[END_REF] for a detailed analysis). (MAR) comes down to restrict the conditional chain model to consider only those labels on which we have not abstained (for which we have sufficient reliable information).

In general, both (IB) and (MAR) can lead to burdensome computations. In the next section, we propose to adapt their principle to the NCC, showing that this can be done efficiently.

Remark 1. Note that another strategy that would be computationally efficient would be to simply considers all precise chaining paths consistent with local intervals, pruning dominated branches. However, this would also mean that each explored branch would have all previous predicted labels as conditioning features, thus still being impacted by the bias of picking those predictions.

3 Imprecise Chaining with NCC NCC extends the classical naive Bayes classifier (NBC) on a set of distributions. NCC preserves the assumption of feature independence made by NBC, and relies on the Imprecise Dirichlet model (IDM) [START_REF] Walley | Inferences from multinomial data: learning about a bag of marbles[END_REF] to estimate class-conditional imprecise probabilities, whose imprecision level is controlled through a hyperparameter s ∈ R. Therefore, the class-conditional probability bounds evaluated for Y j = 1 (Y j = 0 can be directly calculated using duality) can be calculated as follows2

P (Yj = 1|X = x,Y I j-1= ŷI j-1) = 1+ P (Yj = 0)P 0(X = x)P 0(YI j-1= ŷI j-1 ) P (Yj = 1)P 1 (X = x)P 1 (Y I j-1= ŷI j-1 ) -1

,

P (Yj = 1|X = x,Y I j-1= ŷI j-1) = 1+ P (Yj = 0)P 0 (X = x)P 0 (Y I j-1= ŷI j-1 ) P (Yj = 1)P 1(X = x)P 1(YI j-1= ŷI j-1 ) -1

.

where conditional upper probabilities of [P 1 , P 1 ] and [P 0 , P 0 ] are defined as

P (Y k = ŷk |Yj = a), (15)
where a ∈ {0, 1}. Conditional lower probabilities are obtained similarly. Using Equations ( 13) and ( 14), we now propose efficient procedures to solve the aforementioned strategies.

Imprecise Branching

In the specific case where we use the NCC, we can efficiently reduce the optimization problems of Equations (IB), as expressed in the proposition below.

Proposition 1. Optimisation problems of the imprecise branching (IB) can be reduced by using probability bounds obtained from the NCC, namely Equations (13) and ( 14), as follows

P j-1 x (Y j = 1) ∝ max y∈{0,1} |I j-1 A | P 0 (Y I j-1 A = y) P 1 (Y I j-1 A = y) and P j-1 x (Y j = 1) ∝ min y∈{0,1} |I j-1 A | P 0 (Y I j-1 A = y) P 1 (Y I j-1 A = y) .
Besides, applying the equations derived from the imprecise Dirichlet model, we have that the values of abstained labels for which the previous optimisation problems are solved are, respectively

ŷI j-1 A := arg max y∈{0,1} |I j-1 A | yi∈y
n(y i |y j = 0)+s n(y i |y j = 1) and ŷI j-1

A := arg min y∈{0,1} |I j-1 A | yi∈y
n(y i |y j = 0) n(y i |y j = 1)+s ( 16)

where I j-1
A is the set of indices of the (j -1)th first predicted abstained labels, n(•) is a count function that counts the number of occurrences of the event y i |y j and n(y i |y j = 1) is always strictly positive.

Proposition 1 says that it is not necessary to know the original input features X and neither the (j -1)th first precise predicted labels, in order to get the lower and upper probability bound of Equations (IB). However, it is necessary to keep track of the estimates made on all abstained labels, which is consistent with the fact that we want to capture the optimal lower and upper bounds of the conditional probability over all possible paths on which we have abstained.

Proposition 1 allows us to propose an algorithm below that can calculate Equations ( 16) linearly in the number of abstained labels. The following proposition provides the time complexity of the inference step of the imprecise branching strategy, jointly with the NCC and previous results. Proposition 3. The global time complexity of the imprecise branching strategy in the worst-case is O(m 2 ) and in the best-case is O(m).

Marginalization

When the NCC is considered, nothing needs to be optimized in the marginalization strategy, thanks to the assumption of independence applied between the binary conditional models of the chain.

We recall that the marginalization strategy needs to compute the conditional models described in Equations (MAR). These latter can be solved by simply ignoring the abstained labels in Equations ( 13) and ( 14) of the NCC. We thus focus on adapting Equation ( 14) (Equation ( 13) can be treated similarly), in order to show that the abstained labels can be removed of the conditioning and to get the expression presented in Equation [START_REF] Levi | The enterprise of knowledge: An essay on knowledge, credal probability, and chance[END_REF]. Based on Equation ( 14), we can only focus on the conditional upper probability on labels, namely Equation ( 15), and rewrite it as follows:

P 0 (Y I j-1 = ŷI j-1 ) := P 0 (Y I j-1 * = ŷI j-1 * , Y I j-1 A = {0, 1} |I j-1 A | ) ( 17
)
where

I j-1 * = I j-1 R ∪ I j-1 I
is the set of indices of relevant and irrelevant inferred labels, and the right side of last equation can be stated as max

P ∈ P Y k |Y j ,P Ya |Y j k∈I j-1 * ,a∈I j-1 A k∈I j-1 * P (Y k = ŷk |Y j = 0) a∈I j-1 A P (Y a = 0 ∪ Y a = 1|Y j = 0).
Thanks to the product assumption in the NCC, each term can be treated separately, making it possible to decouple the multiplication in two parts; max

P ∈P Y k |Y j k∈I j-1 * k∈I j-1 * P (Y k = ŷk |Y j = 0) × max P ∈P Ya |Y j a∈I j-1 A a∈I j-1 A P (Y a = 0 ∪ Y a = 1|Y j = 0),
where P (Y a = 0∪Y a = 1|Y j = 0)=1, and hence the second part becomes 1. Replacing this result in Equation ( 17), and then this latter in Equation ( 14), we get

P j-1 x (Y j = 1) = max P ∈P Y j |Y I j-1 R ,Y I j-1 I P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0).
Therefore, at each inference step, we can apply Equations ( 13) and ( 14) on the reduced new formulation of the marginalization strategy (MAR*). An illustration providing some intuition about this reduction can be seen in Figure 3.

Experiments

In this section, we perform experiments3 on 6 data sets issued from the MULAN repository4 (c.f. Table 2), following a 10×10 cross-validation procedure.

Evaluation and Setting

The usual metrics used in multi-label problems are not adapted at all when we infer set-valued predictions. Thus, we consider appro-

SA( ŷ, y) = 1 (y∈ ŷ) and CP ( ŷ, y) = |Q| m ,
where ŷ is the partial binary prediction (i.e. the set of all possibles binary vectors) and Q denote the set of non-abstained labels. When predicting complete vectors, then CP = 1 and SA equals the 0/1 loss function and when predicting the empty vector, i.e. all labels ŷi = * , then CP = 0 and by convention SA = 1. The reason for using SA is that chaining is used as an approximation of the optimal prediction for a 0/1 loss function.

Imprecise Classifier As mentioned in Section 3, we will use the naive credal classifier (NCC). Note that NCC needs discretized input spaces, so we discretize data sets to z = 6 intervals (except for Medical and Enron data sets). Besides, we restrict the values of the hyper-parameter of the imprecision to s ∈ {0.0, 0.5, . . . , 4.5, 5.5} (when s = 0.0, NCC becomes the precise classifier NBC). At higher values of s, the NCC model will make mostly vacuous predictions (i.e. abstain in all labels ∀i, Y i = * ) for the data sets we consider here.

Missing Labels To simulate missingness during the training step, we uniformly pick at random a percentage of labels Y j,i (the jth label of the ith instance), which are then removed from the training data used to fit the conditional models in the chain. In this paper, we set up five different percentages of missingness: {0, 20, 40, 60, 80}%.

Experimental Results

Figure 4, we provide the results for 3 data sets, showing set-accuracy and completeness measures in average5 (%) obtained by fitting the NCC model for different percentages of missing labels, respectively, applied to the data sets of Table 2 and using the imprecise branching strategy (trends were similar for the marginalization strategies, not displayed due to lack of space) 6 . The results show that when the percentage of missing labels increases, the setaccuracy (SA) increases (regardless of the amount of imprecision s we inject) as we abstain more and more (as completeness decreases). This means that the more imprecise we get, the more accurate are those predictions we retain. However, a high amount of imprecision is sometimes required to include the ground-truth solution within the set-valued prediction (this may be due to the very restrictive 0/1 loss metric). For instance, with s = 5.5 and 40% of missingness, we get a > 65% of set-accuracy versus a < 50% of completeness, in the Emotions data set. Overall, the results are those that we expect and are also sufficient to show that cautious inferences with probability sets may provide additional benefits when dealing with missing labels.

Conclusions

In this paper, we have proposed two new strategies to adapt the classical chaining multi-label problem to the case of handling imprecise probability estimates. Such strategies come with daunting challenges to obtain cautious and reliable predictions, and have been successfully resolved using the NCC model.

While the NCC makes easy to solve the strategies thanks to its assumptions, the same restrictive assumptions may also be the reason why the initial accuracy is rather low (especially for Yeast). Indeed, it seems reasonable to think that the independence assumptions somehow limit the benefits of including label dependencies information through the chaining. It seems therefore essential, in future works, to investigate other classifiers as well as to solve optimisation issues in a general or approximative way.

Another open issue is how we can use or extend the existing heuristics of probabilistic classifier approaches on our proposal strategies, such as epsilonapproximate inference, A * and beam search methods [START_REF] Mena | An overview of inference methods in probabilistic classifier chains for multilabel classification[END_REF][START_REF] Kumar | Beam search algorithms for multilabel learning[END_REF].

where probability bounds [P 1 , P 1 ] and [P 0 , P 0 ] of each different conditional event are defined as follows The last conditional probability bounds are derived using the Imprecise Dirichlet model (IDM) [START_REF] Walley | Inferences from multinomial data: learning about a bag of marbles[END_REF] P (X i = x i |Y j = y j ) = n(x i |y j ) n(y j ) + s and P (

X i = x i |Y j = y j ) = n(x i |y j ) + s n(y j ) + s (25)
where n(•) is a count function that counts the number of occurrences of events x i |y j and y j in the observed data set. For instance; n(x i |y j ) is the number of instances in the training set where X i = x i and the label value is Y i = y i .

In the same way as precedent equations, we can obtain probability bounds

[P (Y k = ŷk |Y j = y j ), P (Y k = ŷk |Y j = y j )].
Remark 2. The denominator of Equations ( 21) and ( 22) may in some cases (depending on the training data) become zero, and therefore, the division would not be defined. In these cases, we adopt the "Laplace smoothing" technique for the precise probabilities P (Y j = 0) and P (Y j = 1). Furthermore, if we obtain an undefined division, i.e. 0/0, we manually put 0. Remark 3. Note that the choice of the marginal distribution P Yj in lieu of a credal set P Yj does not change the theoretical results obtained in Proposition 1. However, if the credal P Y is considered, we can obtain a very small, but not significant, improvement in the experimental results 7 .

B Proofs for our results

Proof (of Proposition 1). Let us begin to prove the optimization problem of the lower probability of (IB) evaluated to Y j = 1

P j-1 x (Y j = 1) = min y∈{0,1} | I j-1 A | P x (Y j = 1|Y I j-1 R = 1, Y I j-1 I = 0, Y I j-1 A = y). (26) Let us to define I j-1 * = I j-1 R ∪ I j-1 I
as the set of indices of relevant and irrelevant predicted labels down to the (j-1)th index. By applying Equation [START_REF] Zaffalon | The naive credal classifier[END_REF] to the right side of last equation, we get min y∈{0,1} | I j-1

A | 1 + P (Y j = 0)P 0 (X = x)P 0 (Y I j-1 * = ŷI j-1 * , Y I j-1 A = y) P (Y j = 1)P 1 (X = x)P 1 (Y I j-1 * = ŷI j-1 * , Y I j-1 A = y) -1
, where ŷI j-1 * is the binary vector with predicted relevant and irrelevant values. So, using the fact that minimizing 1 1+x is equal to maximizing x, we therefore get

max y∈{0,1} | I j-1 A | P (Y j = 0)P 0 (X = x)P 0 (Y I j-1 * = ŷI j-1 * )P 0 (Y I j-1 A = y) P (Y j = 1)P 1 (X = x)P 1 (Y I j-1 * = ŷI j-1 * )P 1 (Y I j-1 A = y)
.

The first three terms of the numerator (and of the denominator) of the last equation can be omitted from the optimization problem since they do not change the optimal solution, and by applying Equations ( 23), ( 24) and (25), to the last term, we get what we sought max y∈{0,1} | I j-1

A | P 0 (Y I j-1 A = y) P 1 (Y I j-1 A = y) ⇐⇒ max y∈{0,1} | I j-1 A | k∈I j-1 A P (Y k = y k |Y j = 0) k∈I j-1 A P (Y k = y k |Y j = 1) ⇐⇒ max y∈{0,1} | I j-1 A | k∈I j-1 A n(y k |yj =0)+s n(yj =0)+s k∈I j-1 A n(y k |yj =1) n(yj =1)+s ⇐⇒ max y∈{0,1} | I j-1 A | n(y j = 1) + s n(y j = 0) + s |I j-1 A | i∈I j-1 A yi∈y n(y i |y j = 0) + s n(y i |y j = 1) , in which it is easy see that: (1) the term [• • • ] |I j-1 A
| can be omitted, and hence, we can get ŷI j-1

A

, and (2) using similar arguments as above we can easily get the labels ŷI j-1 A which maximise the upper probability P x (Y j = 1) of (IB).

Proof (of Proposition 2). This proof can be performed using a dichotomy algorithm (equivalent to a binary search tree), starting with y k last abstained label (i.e. k = |I A | -1) and calculating the values n(y k =1|•)+s n(y k =1|•) and n(y k =0|•)+s n(y k =0|•) , then we retain the maximal value of these last two terms (or the minimal value, whichever applies) and we go forward with second-to-last label y k-1 , but this time multiplied by the last term retained, and so on. After having obtained the lower binary path ŷI j-1 A (or the upper binary path ŷI j-1 A ), we can directly calculate the values P j-1 x (Y j = 1) and P Proof (of Proposition 3). The proof for the best-case is straighforward, because if there is not any abstained labels, the time complexity is the same than precise chaining O(m). The worst-case complexity, in which all inferred labels are abstained, is also easy to calculate: the first label performs a single operation, i.e. O(1), then the second label is also inferred in a single operation due to the number of previous abstained labels being equal to 1 (c.f. Proposition 2), then the third label takes into account two previous abstained labels and performs two operations (c.f. Proposition 2), and the fourth label performs three operations, and so on. We therefore obtain O( m(m-1) /2 + 1) operations which is equal to O(m 2 ) asymptotically. (c) CAL500 Fig. 6. Missing labels -Imprecise Branching Evolution of the average (%) setaccuracy (top) and completeness (down) for each level of imprecision (a curve for each one) and a discretization z = 6, with respect to the percentage of missing labels.

C Supplementary results

Set-accuracy

Fig. 1 .

 1 Fig. 1. Precise chaining

Figure 1

 1 Figure1shows that using this heuristic can lead to strong biases, as two different orderings of the same joint model can lead to shift from one prediction to its opposite. Intuitively, adding some robustness and cautiousness in the process could help to avoid unwarranted biases.In what follows, we propose two different extensions of precise chaining based on imprecise probability estimates, in which the final prediction belongs to the output space Y of partial bianry vectors.

  Figure 2(b) where we have abstained on labels (Y 2 , Y 4 ) and we want to compute lower and upper probability bounds of the label Y 5 = 1.

Y

P

  a(X = x) := p i=1 P (Xi = xi|Yj = a) and P a(Y I j-1 = y I j-1 ) := j-1 k=1

Proposition 2 . 1 A and ŷI j- 1 A

 211 The chain of labels ŷI j-can be obtained in a time complexity of O(|I j-1 A |).

Fig. 3 .

 3 Fig. 3. Marginalization strategy applied to NCC for four labels {Y1, Y2, Y3, Y4}

Fig. 4 .

 4 Fig.4. Missing labels -Imprecise Branching Evolution of the average (%) setaccuracy (top) and completeness (down) for each level of imprecision (a curve for each one) and a discretization z = 6, with respect to the percentage of missing labels.

P 1 k=1P 1 k=1P

 11 0(X = x) := p i=1 P (Xi = xi|Yj = 0) and P 0(YI j-1 = y I j-1 ) := j-(Y k = ŷk |Yj = 0), (23) P 1 (X = x) := p i=1 P (Xi = xi|Yj = 1) and P 1 (Y I j-1 = y I j-1 ) := j-(Y k = ŷk |Yj = 1).(24)

  = 1) (and by duality of the lower and upper probability bounds [P j-1 x (Y j = 0), P j-1 x (Y j = 0)]).

Fig. 5 .

 5 Fig. 5. Missing labels -Marginalization Evolution of the average (%) set-accuracy (top) and completeness (down) for each level of imprecision (a curve for each one) and discretization z = 6, with respect the percentage of missing labels.

Table 1 .

 1 with imprecise estimations of P(Y 1 , Y 2 |X 1 ). Estimated conditional probability distributions P(Y1, Y2|X1) ∈ PY 1 ,Y 2 |X 1 .

	y1 y2 x1	PY1,Y2|X1=0 y1 y2 x1	PY1,Y2|X1=1
	0	0	0	[0.4,0.7]	0	0	1	0.00
	0	1	0	[0.3,0.6]	0	1	1	0.00
	1	0	0	0.00	1	0	1	[0.6,0.8]
	1	1	0	0.00	1	1	1	[0.2,0.4]

Table 2 .

 2 Multi-label data sets summary priate to use the set-accuracy (SA) and completeness (CP) [8, §4.1], as follows

	Data set #Domain #Features #Labels #Instances #Cardinality #Density
	emotions	music	72	6	593	1.90	0.31
	scene	image	294	6	2407	1.07	0.18
	yeast	biology	103	14	2417	4.23	0.30
	cal500	music	68	174	502	26.04	0.15
	medical	text	1449	45	978	1.25	0.03
	enron	text	1001	53	1702	3.38	0.06

A complete, transitive, and asymmetric binary relation

For reviewer convenience, details are given in the supplementary material.

Implemented in Python, see https://github.com/sdestercke/classifip

http://mulan.sourceforge.net/datasets.html

The confidence intervals obtained on the experimental results are very small and we therefore prefer not to display them in the figures in order not to overcharge them.

The supplementary results can be found in the online extend version[START_REF] Carranza Alarcón | Multi-label chaining with imprecise probabilities[END_REF]

Anyone can reproduce these results by using our online implementation.

Acknowledgments. We wish to thank the reviewers of the ECSQARU conference, especially one of them who was thorough, and made us rethink a lot of aspects (of which only some are visible in the revised version).

Appendix A NCC derivation for multi-label chaining

As the purpose of the imprecise chaining is to compute binary conditional dependence models, we need only get conditional probability bounds of the probability P (Y j = y j |X = x, Y I j-1= ŷI j-1 ), so by using Bayes' theorem and naive Bayes' attribute independence assumption, it can be written as follows

Computing lower and upper probability bounds [P , P ] over all possible marginals P Yj and conditional distributions P Xi|Yj , P Y k |Yj can be performed by solving the following minimization/maximization problem of Equation ( 18) as follows

i=1,...,d k=1,...,j-1 P (Y j = y j |X= x, Y I j-1= ŷI j-1 ), ( 19)

..,d k=1,...,j-1 P (Y j = y j |X= x, Y I j-1= ŷI j-1 ). [START_REF] Walley | Inferences from multinomial data: learning about a bag of marbles[END_REF] In practice, we assume a precise estimation of the marginal distribution P Yj in lieu of a credal set P Yj , so optimization problems over the credal set of marginal distributions P Yj can be ignored. Therefore, one can easily show that last equations evaluated to Y j = 1 (Y j = 0 can be directly calculated using duality) are equivalent to

P (Y j = 1|X = x, Y I j-1 = ŷI j-1 ) = 1 + P (Y j = 0)P 0 (X = x)P 0 (Y I j-1 = ŷI j-1 ) P (Y j = 1)P 1 (X = x)P 1 (Y I j-1 = ŷI j-1 ) -1

(22)


Alain Rakotomamonjy

Mokhtar Zahdi
email: mokhtarzahdi.alaya@gmail.com

El Alaya

Maxime Berar
email: maxime.beraro@univ-rouen.fr

Gilles Gasso
email: gilles.gasso@insa-rouen.fr

Statistical and Topological Properties of Gaussian Smoothed Sliced Probability Divergences

Gaussian smoothed sliced Wasserstein distance has been recently introduced for comparing probability distributions, while preserving privacy on the data. It has been shown, in applications such as domain adaptation, to provide performances similar to its non-private (non-smoothed) counter-part. However, the computational and statistical properties of such a metric is not yet been well-established. In this paper, we analyze the theoretical properties of this distance as well as those of generalized versions denoted as Gaussian smoothed sliced divergences. We show that smoothing and slicing preserve the metric property and the weak topology. We also provide results on the sample complexity of such divergences. Since, the privacy level depends on the amount of Gaussian smoothing, we analyze the impact of this parameter on the divergence. We support our theoretical findings with empirical studies of Gaussian smoothed and sliced version of Wassertein distance, Sinkhorn divergence and maximum mean discrepancy (MMD). In the context of privacy-preserving domain adaptation, we confirm that those Gaussian smoothed sliced Wasserstein and MMD divergences perform very well while ensuring data privacy.

Introduction

Divergences for comparing two distributions have been shown to be important for achieving good performances in the contexts of generative modeling [START_REF] Arjovsky | Wasserstein generative adversarial networks[END_REF][START_REF] Salimans | Improving GANs using optimal transport[END_REF], domain adaptation [START_REF] Long | Learning transferable features with deep adaptation networks[END_REF][START_REF] Courty | Optimal transport for domain adapta-tion[END_REF][START_REF] Lee | Sliced wasserstein discrepancy for unsupervised domain adaptation[END_REF], and in computer vision [START_REF] Bonneel | Displacement interpolation using lagrangian mass transport[END_REF][START_REF] Solomon | Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains[END_REF] among many more applications [START_REF] Kolouri | Optimal mass transport: Signal processing and machine-learning applications[END_REF][START_REF] Peyré | Computational optimal transport[END_REF]. Examples of divergences that have been proven to be useful for those tasks are maximum mean discrepancy [START_REF] Gretton | A kernel two-sample test[END_REF][START_REF] Long | Learning transferable features with deep adaptation networks[END_REF][START_REF] Sutherland | Generative models and model criticism via optimized maximum mean discrepancy[END_REF], Wasserstein distance [START_REF] Monge | Mémoire sur la théotie des déblais et des remblais[END_REF][START_REF] Kantorovich | On the transfer of masses (in russian)[END_REF][START_REF] Villani | Optimal Transport: Old and New[END_REF] or its variant the sliced Wasserstein distance (SWD) [START_REF] Bonneel | Spot: Sliced partial optimal transport[END_REF][START_REF] Kolouri | Generalized sliced Wasserstein distances[END_REF][START_REF] Nguyen | Distributional sliced-Wasserstein and applications to generative modeling[END_REF][START_REF] Kolouri | Sliced Wasserstein kernels for probability distributions[END_REF].

Sliced Wasserstein distance has the advantage of being computationally efficient as it exploits a closedform solution for distributions with support on R, by computing the expectation of one-dimensional random projections of distributions in R d . Owing to this efficiency and the resulting scalability, this distance has been successfully applied in several applications ranging from generative models to domain adaptation [START_REF] Kolouri | Sliced Wasserstein auto-encoders[END_REF][START_REF] Deshpande | Max-sliced Wasserstein distance and its use for gans[END_REF][START_REF] Wu | Sliced wasserstein generative models[END_REF][START_REF] Lee | Sliced wasserstein discrepancy for unsupervised domain adaptation[END_REF] and its statistical property has been well-studied [START_REF] Nadjahi | Statistical and topological properties of sliced probability divergences[END_REF].

A differentially private variant of sliced Wasserstein distance has been recently introduced in [START_REF] Rakotomamonjy | Differentially private sliced wasserstein distance[END_REF], for comparing distributions in relation to sensitive applications in which training data can not be disclosed. Privacy through a so-called Gaussian mechanism is induced by adding Gaussian noise to each 1D projection of each distribution, leading to the so-called Gaussiansmoothed sliced Wasserstein distance. This relationship between Gaussian smoothing and privacy has also been mentioned by Nietert et al. [START_REF] Nietert | From smooth wasserstein distance to dual sobolev norm: Empirical approximation and statistical applications[END_REF] as future work to address, while they analyzed the structural and statistical behavior of Gaussian smoothed Wasserstein distances.

However, up to now, theoretical properties of this Gaussian smoothed sliced Wasserstein distance are not well fully understood except for its metric properties [START_REF] Rakotomamonjy | Differentially private sliced wasserstein distance[END_REF]. In this work, we investigate those theoretical properties and the one of more general Gaussian smoothed sliced divergences. Indeed, given a base distance or divergence for distributions in R d , we can introduce its related Gaussian smoothed sliced divergence. Specifically, the theoretical properties of interest are the metric property and the underlying topology. From a statistical point of view, we seek at understanding the relationship between the sample complexity of the base divergence and its Gaussian smoothed sliced version. Regarding privacy, the role of the Gaussian smoothing is of primary importance as it induces the privacy level achieved by the divergence. Hence, we also provide an analysis on its impact with respect to the standard deviation of the Gaussian noise. For supporting our theoretical study, we provide some numerical experiments on toy problem, and we also provide some numerical study on domain adaptation illustrating how owing to the topology induced by our metric, differential privacy comes almost for free (without loss of performances) in this context.

The paper is organized as follows, after introducing the notations and some background in Section 2, we detail the topological properties of Gaussian smoothed sliced divergence in Section 3.1 while the statistical properties are established in Section 3.2. Experimental analyses for supporting the theory and showcasing the relevance of our divergences in a domain adaptation situation are depicted in Section 4. Discussions on the perspectives and limitations are in Section 5.

Preliminaries

For the reader's convenience, we provide a brief summary of the standard notations and the definitions that will be used throughout the paper.

Notations. For d ∈ N * , let P(R d ) be the set of Borel probability measures on R d and P p (R d ) ⊂ P(R d ), those with finite moment of order p, i.e., P p (R d ) {µ ∈ P :

x p dµ(x) < +∞}, where • is the Euclidean norm and •, • is the Euclidean inner-product. For two probability distributions µ and ν, we denote their convolution as µ * ν ∈ P(R d ) and by definition, we have (µ * ν)(A) = x y 1 A (x + y)dµ(x)dν(y), where 1 A (•) is the indicator function over A. Given two independent random variables X ∼ µ and Y ∼ ν, we remind that X + Y ∼ µ * ν.

The d-dimensional unit-sphere is noted as S d-1 {θ ∈ R d : θ = 1}. We denote by u d the uniform distribution on S d-1 and we use δ(•) to denote the Kronecker delta function. We note as E µ f the expectation of the function f with respect to µ. Hence, the characteristic function of a probability distribution µ

∈ P(R d ) is ϕ µ (t) = E µ [e iX t ]
. Given this definition, similarly to the Fourier transform, the characteristic function of the convolution of two probability distributions has the following form

ϕ ν * µ (t) = ϕ ν (t) • ϕ µ (t).
Sliced Wasserstein Distance. We remind in this paragraph several measures of similarity between two distributions. The Wasserstein distance of order p ∈ [1, ∞) between two measures in P p (R d ) is given by the relaxation of the optimal transport problem, and it is defined as

W p p (µ, ν) = inf γ∈Π(µ,ν) R d ×R d x -x p γ(x, x )dxdx where Π(µ, ν) {γ ∈ P(R d × R d )|π 1# γ = µ, π 2# γ =
ν} and π 1 , π 2 are the marginal projectors of γ on each of its coordinates. When d = 1, the Wasserstein distance can be computed in a closed-form owing to the cumulative distributions of µ and ν [START_REF] Rachev | Mass Transportation Problems: Volume I: Theory. Mass Transportation Problems[END_REF]. Note that the superscript in W p p refers to the power p. In practice for empirical distributions, the closed-form solution needs just the sorting of samples, which makes it very efficient. Due to this efficiency, efforts have been devoted to derive a metric for high-dimensional distributions based on 1D Wasserstein distance. The main idea is to project high-dimensional probability distributions onto a random 1-dimensional space and then to compute the Wasserstein distance. That operation can be theoretically formalized through the use of the Radon transform, leading to the so-called sliced Wasserstein distance [START_REF] Bonneel | Spot: Sliced partial optimal transport[END_REF][START_REF] Kolouri | Generalized sliced Wasserstein distances[END_REF][START_REF] Nguyen | Distributional sliced-Wasserstein and applications to generative modeling[END_REF][START_REF] Kolouri | Sliced Wasserstein kernels for probability distributions[END_REF]. Definition 1. For any p ∈ [1, ∞) and two measures µ, ν ∈ P p (R d ), the sliced Wasserstein distance (SWD) reads as SWD p p (µ, ν)

S d-1 W p p (R u µ, R u ν)u d (u)du.
where R u is the Radon transform of a probability distribution, namely

R u µ(•) = R d µ(s)δ(• -s u)ds.
In practice, the integral is approximated through a Monte-Carlo simulation leading to a sum of 1D Wasserstein distances over a fixed number of random directions u.

Gaussian Smoothed Sliced Wasserstein Distance. Based on this definition of SWD, replacing the Radon projected measures with their Gaussiansmoothed counterpart leads to the following definition: Definition 2. The σ-Gaussian smoothed p-Sliced Wasserstein distance between probability distributions µ and

ν in P p (R d ) is G σ SWD p p (µ, ν) S d-1 W p p (R u µ * N σ , R u ν * N σ )u d (u)du.
It is important to note here that the smoothing (convolution) operation occurs after projection onto the onedimensional space. Hence, assuming X ∼ µ, Y ∼ ν in the integral, for a given u, we compute the 1D Wasserstein distance between the probability laws of u X +Z and u Y +Z with Z, Z ∼ N σ being independent random variables. The metric properties of G σ SWD p p for p ≥ 1, of this Gaussian smoothed sliced Wasserstein distance have been discussed in a recent work [START_REF] Rakotomamonjy | Differentially private sliced wasserstein distance[END_REF]. This latter work has also shown, in the context of differential privacy, the importance of convolving the Radon projected distribution with a Gaussian instead of computing the sliced Wasserstein distance of the original distribution smoothed with a d-dimensional Gaussian µ * N σ .

Gaussian Smoothed Sliced Divergence. The idea of slicing high-dimensional distributions before feeding them to a divergence between probability distributions can be extended to other distance than Wasserstein distance. Those sliced divergences have been studied by [START_REF] Nadjahi | Statistical and topological properties of sliced probability divergences[END_REF]. In a similar way, we can define a Gaussian smoothed sliced divergence, given a divergence

D : P(R d ) × P(R d ) → R + for d ≥ 1 as: Definition 3. The σ-Gaussian smoothed p-Sliced Di- vergence between probability distributions µ and ν in P p (R d ) associated to the divergence D D R , p ≥ 1 is G σ SD p (µ, ν) S d-1 D p (R u µ * N σ , R u ν * N σ )u d (u)du.
where the superscript p refers to a power.

Typical relevant divergence is the maximum mean discrepancy (MMD) [START_REF] Gretton | A kernel two-sample test[END_REF] or the Sinkhorn divergence [START_REF] Genevay | Learning generative models with sinkhorn divergences[END_REF][START_REF] Peyré | Computational optimal transport[END_REF]. In Section 4, we report empirical findings based on these divergences as well as on the Wasserstein distance.

Theoretical Properties

In this section, we will analyze the properties of the Gaussian smoothed sliced divergence, in term of topological and statistical properties and the influence of the Gaussian smoothing parameter σ on the distance.

Topology

It has already been shown in [START_REF] Rakotomamonjy | Differentially private sliced wasserstein distance[END_REF] that the Gaussian smoothed sliced Wasserstein is a metric on P(R d ). In the next, we extend these results to any divergence D(•, •) under some assumptions. Theorem 1. For any p ∈ [1, ∞) and σ > 0, the following properties hold: The above theorem shows that under mild hypotheses over the base divergence D, as being a metric for instance, the metric property of its Gaussian smoothed sliced version naturally derives. As exposed in the appendix, the more involved property to prove is the identity of indiscernibles. Now, we establish under which conditions on the divergence D, the convergence of a sequence in G σ SD p implies weak convergence in P(R d ).

1. if D(•, •) is non-negative (or symmetric), then G σ SD p (•, •) is non-negative (or symmetric);
Theorem 2. Let σ ≥ 0, p ∈ [1, ∞), µ ∈ P p (R d ), the sequence of distributions {µ k ∈ P p (R d )} k≥1 .
Assume that the divergence D metricizes the weak topology. Then, lim k→∞ G σ SD p (µ k , µ) = 0 if and only if {µ k } k converges weakly to µ i.e., if for any f in the set of bounded and continuous functions,

µ k → µ if R d f (x)dµ k (x) → R d f (x)dµ(x).
Proof. By using results from [START_REF] Nadjahi | Statistical and topological properties of sliced probability divergences[END_REF], we know that if D metricizes the weak topology for P(R) then the weak convergence in P(R) is equivalent to the convergence under D. Hence, we have

G σ SD p (µ k , µ) → 0 ⇔ µ k * N σ → µ * N σ
then, using the convolution property of characteristic function gives

ϕ µ k (t)ϕ Nσ (t) → ϕ µ (t)ϕ Nσ (t) ∀t.
This means that for all t, ϕ µ k (t) → ϕ µ (t) which concludes the proof, owing to the one-to-one correspondence between characteristic functions.

Statistical properties

The next theoretical question we are interested in is about the error we made when the true distribution µ is approximated by its empirical distribution μ. Such a case is common in practical applications where only (high-dimensional) empirical samples are at disposal. Specifically, we are interested in quantifying two key properties of empirical Gaussian smoothed divergence:

(i) the convergence of G σ SD p (μ n , νn ) to G σ SD p (µ, ν) (ii) the convergence of G σ SD p (µ, ν) to G σ SD p (µ, ν),
i.e., when approximating the expectation over the random projection with sample mean.

Sample complexity

Herein, our goal is to quantify the error made when approximating G σ SD p (µ, ν) with G σ SD p (μ n , νn ), where μn , νn are the empirical counterparts of µ, ν defined over n samples. More precisely, we are interested in establishing an order of the convergence rate of G σ SD p (μ n , νn ) towards G σ SD p (µ, ν), according to the number of samples n. This rate stands for the socalled sample complexity.

Theorem 3. Fix p ∈ [1, ∞) and assume that for any

µ ∈ P(R) with empirical measure μ n , E[D p (μ n , µ )] ≤ α n (p). Then, for any µ ∈ P(R d ) with empirical mea- sure μn , E[G σ SD p (μ n , µ)] ≤ α n (p).
Additionally, if D p is a pseudo-metric (non-negative, symmetric with triangle inequality), then

E[|G σ SD p (μ n , νn ) -G σ SD p (µ, ν)|] ≤ 2α n (p).
Proof. We have

E[G σ SD p (μ n , µ)] = E S d-1 D p (R u μn * N σ , R u µ * N σ )u d (u)du ≤ S d-1 E D p (R u μn * N σ , R u µ * N σ )u d (u)du ≤ S d-1 α n (p)u d (u)du = α n (p).
The triangle inequality entails that, G σ SD p (μ n , νn ) ≤ G σ SD p (μ n , µ) + G σ SD p (µ, ν) + G σ SD p (ν, νn ), which entails, by taking expectation with respect to μn , νn ,

E |G σ SD p (μ n , νn ) -G σ SD p (µ, ν)| ≤ E G σ SD p (μ n , µ) + E G σ SD p (ν, νn ) ≤ E G σ SD p (μ n , µ) + E G σ SD p (ν n , ν) ≤ 2α n (p),
which completes the proof.

Remark 1. Given any base divergence D p , Theorem 3 shows that the sample complexity of G σ SD p is proportional to the one dimensional sample complexity of D p .

Next, we focus on the sample complexity for the special case of Gaussian smoothed sliced Wasserstein distance. We also provide the convergence rate of G σ SW D p (μ n , νn ) towards G σ SW D p (µ, ν).

Proposition 1. For any p, q ∈ [1, ∞) such that q > p, consider µ, ν ∈ P q (R d ) with its empirical measure μn .

Then, the following holds

E[|G σ SW D p (μ n , νn ) -G σ SW D p (µ, ν)|] ≤ α n (p, q, σ)
where α n (p, q, σ) = 2C p,q × 2 p(q-1)/q (M q (µ, ν) + M q (N σ )) p/q 1 q∈2N * , 2 p(q-1)/q M q (µ, ν)) p/q 1 q∈2N+1 ,

×      n -1/2 1 q>2p , n -1/2 log(n)1 q=2p n -(q-p)/q 1 q∈(p,2p)
and where M q (µ, ν) = M q (µ) + M q (ν), C p,q is a positive constant depending only p, q, and M q (N σ ) stands for the q-th moment of N σ , that is

M q (N σ ))1 q∈2N * = (2q)! 2 q q! σ 2q = 1 • 2 • 3 • • • (2q -1)σ 2q .
The latter theoretical results show that empirical Gaussian smoothed Wasserstein distance converges at a rate of order n -1/2 in the best scenario. It is worth also noting that the sample complexity depends on the amount of smoothing through the moment of the Gaussian noise : the larger the amount of smoothing, the worse is the constant of the complexity.

Projection complexity

To compute the Gaussian smoothed sliced divergence, one may resort to a Monte Carlo scheme to numerically approximate the integral in G σ SD p (µ, ν). Towards this, let define the following sum:

G σ SD p (µ, ν) = 1 L L l=1 D p (R u l μn * N σ , R u l νn * N σ ),
where u l is a random vector uniformly drawn from S d-1 , for l = 1, . . . , L. Theorem 4 shows that for a fixed dimension d, the root mean square error of Monte Carlo approximation is of order O 1 √ L , which corresponds to the projection complexity.

Theorem 4. Let µ, ν ∈ P(R d ) and fix p ∈ [1, ∞).
Then, the error related to the Monte Carlo estimation of G σ SD p is bounded as follows

E[| G σ SD p (µ, ν) -G σ SD p (µ, ν)|] ≤ A(p, σ) √ L , where A 2 (p, σ) = S d-1 D p (R u µ * N σ , R u ν * N σ ) - θp 2 du d (u), with θp = S d-1 D p (R u µ * N σ , R u ν * N σ )du d (u).
The term A 2 (p, σ) corresponds to the variance of D p (R u µ * N σ , R u ν * N σ ) with respect to u ∼ u d drawn according to the uniform distribution over the unitsphere S d-1 . It is worth to note that the precision of the Monte Carlo scheme approximation depends on the number of projections L and the variance of the evaluations of the divergence D p . The estimation error decreases at the rate L -1/2 according to the number of projections used to compute the smoothed sliced divergence.

Remark 2. Given the above results, we can provide a finer analysis of the Gaussian smoothed SWD sample complexity. For any µ, ν ∈ P q (R d ), the overall complexity of the Gaussian smoothed sliced Wasserstein distance is bounded by the sample and projection complexities, that is,

complexity(G σ SW D p (µ, ν)) = O α n (p, q, σ)+ A(p, σ) √ L .
If we consider the number of projections as L = n β for some β ∈ (0, 1) then the overall complexity complexity(G σ SD p (µ, ν)) = O(n -β/2 ). We further mention that complexity is "interestingly" independent of the dimension d.

Noise-level dependencies

When considered in sensitive applications requiring privacy preserving, the parameter σ of the Gaussian smoothing function N σ may significantly influence the attained privacy level. Hence, we provide theoretical results analyzing the effect of the noise level σ on the induced Gaussian smoothed sliced divergence.

Order relation. We first show that the noise level tends to reduce the difference between two distributions as measured using G σ SD p (µ, ν) provided the base divergence D satisfies some mild assumptions.

Proposition 2. Let µ and ν two distributions in P(R d ) and consider the noise levels σ 1 , σ 2 such that

0 ≤ σ 1 ≤ σ 2 < ∞. Assume that the base divergence D satisfies D p (µ * N σ2 , ν * N σ2 ) ≤ D p (µ * N σ1 , ν * N σ1 ),
for any µ , ν ∈ P(R). Then,

G σ2 SD p (µ, ν) ≤ G σ1 SD p (µ, ν).
Proof. For all u ∈ S d-1 we have R u µ, R u ν ∈ P(R).

By application of the inequality of noise level satisfied by D p p in one dimension we get

D p (R u µ * N σ2 , R u ν * N σ2 ) ≤ D p (R u µ * N σ1 , R u ν * N σ1 ).
Then, computing the expectation over the projections u since the divergence is non-negative concludes the proof.

Note that the assumption for the base divergence inequality holds for the Gaussian smoothed Wasserstein distance [START_REF] Nietert | From smooth wasserstein distance to dual sobolev norm: Empirical approximation and statistical applications[END_REF]. While we conjecture that it holds also for smoothed Sinkhorn and MMD, we leave the proofs for future works.

Based on the property in Proposition 2, we can show some specific properties of the metric with respect to the noise level σ. Proposition 3. G σ SD p (µ, ν) is decreasing with respect to σ and we have

lim σ→0 G σ SD p (µ, ν) = D p (µ, ν).
Proof. The proof comes straightforwardly from Proposition 2 by taking σ 2 = 0 and letting σ 1 → 0. This property interestingly states that the G σ SD p recovers the sliced divergence when the noise level vanishes. We end up this section by providing a relation between Gaussian smoothed sliced Wasserstein

G σ1 SW D p (µ, ν) ≤ 2 p-1 G σ2 SW D p (µ, ν) + 2π d/2 Γ(d/2) 2 3p/2 (σ 2 2 -σ 2 1 ) 2p ,
where Γ : R → R is the Gamma function expressed as

Γ(v) = ∞ 0 t v-1 e -t dt.
The above proposition allows to control the variation of the G σ SW D divergence with respects to the amount of Gaussian smoothing.

Remark 3. All these properties hold for the population case. When considering empirical approximation of the true distribution, it may not hold due to the impact of N σ over the sample complexity.

Numerical Experiments

In this section, we report on a serie of experiments that support the theoretical results established in the previous section. We also highlight the usefulness of the findings in a context of privacy-preserving domain adaptation problem.

Supporting the theorical results

Sample complexity

The first experiment (see Figure 1) analyzes the sample complexity of the different Gaussian smoothed sliced divergences. It shows that the sample complexity stays similar to the one of their original and sliced counterparts up to a constant (see Theorem 3). For this purpose, we have considered Figure 4: Absolute difference between the approximated Monte-carlo approximation of all divergences compared to the true one (evaluated with 10, 000 number of projections). The two sets of 500 samples in R 50 are randomly drawn from N (0, I). The Gaussian smoothed divergences are parameterized with σ = 3.

samples in R d randomly drawn from a Normal distribution N (0, I). For the Sinkhorn divergence, the entropy regularization has been set to 0.1 and for MMD, we used a Gaussian kernel for which the bandwidth has been set to the mean of all pairwise distances between samples. The number of projections has been fixed to L = 50 and we perform 20 runs per experiment. For the first study, the convergence rate has been evaluated by increasing the samples number up to 25,000 with fixed dimension d = 50. For the second one, we vary both the dimension and the number of samples.

Figure 1 shows the sample complexity of some sliced divergences, respectively noted as SWD, SKD and MMD for Sliced Wasserstein distance, Sinkhorn divergence and Maximum Mean discrepancy) and their Gaussian-smoothed version, named as GS SWD, GS SKD and GS MMD. On the left plot, we can see that all Gaussian smoothed divergences preserve the complexity rate with just a slight to moderate overhead. The worst difference is for Sinkhorn divergence, while smoothed MMD almost comes for free in term of complexity. From the right plot where sample complexities for different dimensions d are given, we confirm the finding that Gaussian smoothing keeps the independence of the convergence rate to the dimension of sliced divergences. We have also evaluated the sample complexity for the CIFAR dataset by sampling sets of increasing size. Results reported in Figure 2 confirms the findings obtained from the toy dataset.

Identity of indescernibles

The second experiment aims at checking whether our divergences converge towards a small value when the distributions to be compared are the same. For this, we consider samples from distributions µ and ν chosen as normal distributions with respectively mean 2×1 d and s1 d with varying s (noted as the displacement). Results are depicted in Figure 3. We can see that all methods are able to attain their minimum when s = 2. Interestingly, the gap between the Gaussian smoothed and non-smoothed divergences for Wasserstein and Sinkhorn is almost indiscernible as the distance between distribution increases.

Projection complexity We have also investigated the impact of the number of projections when estimating the distance between two sets of 500 samples drawn from the same distribution, N (0, I). Figure 4 plots the approximation error between the true expectation of the sliced divergences (computed for a number of L = 10, 000 projections) and its approximated versions. We remark that, for all methods, the error ranges within 10-fold when approximating with 50 projections and decreases with the number of projections.

Impact of the noise parameter. Since the Gaussian smoothing parameter is key in a privacy preserving context, as it impacts on the level of privacy of the Gaussian mechanism, we have analyzed its impact of the smoothed sliced divergence. We have reproduced the experiment for the sample complexity but with different values of σ. The number of projections has been set to 50. Figure 5 shows these sample complexities. The first very interesting point to note is that the smoothing parameter has almost no effect on the MMD sample complexity. For the Gaussian smoothed SWD and Sinkhorn divergences, instead, the smoothing tends to increase the divergence at fixed number of samples. Another interpretation is that to achieve a given value of divergence, one needs more far samples when the smoothing is larger (i.e for getting a given divergence value at σ = 5, one needs almost 10-fold more samples for σ = 15). This overhead of samples needed when smoothing increases is properly described, for the Gaussian smoothed SWD in our Proposition 1, as the sample complexity depends on the moments of the Gaussian.

As for conclusion from these analyses, we highlight that the Gaussian smoothed Sliced MMD seems to present several strong benefits : its sample complexity does not depend on the dimension and seems to be the best one among the divergence we considered. More interestingly, it is not impacted by the amount of Gaussian smoothing and thus not impacted by a desired privacy level.

L c (h(g(X s )), y s ) + D(g(X s ), g(X t ))
where L c can be the cross-entropy loss or a quadratic loss and D a divergence between empirical distributions, in our case, D will be any Gaussian smoothed sliced divergence. We solve this problem through stochastic gradient descent, similarly to many approaches that use Sliced Wasserstein Distance as a distribution distance [START_REF] Lee | Sliced wasserstein discrepancy for unsupervised domain adaptation[END_REF]. Note that, in practice, using a smoothed divergence preserves the privacy of the target samples as shown by Rakotomamonjy & Ralaivola [START_REF] Rakotomamonjy | Differentially private sliced wasserstein distance[END_REF].

Our experiments evaluate the studied Gaussiansmoothed sliced divergences in classical unsupervised domain adaptation. We have considered twi datasets: a handwritten digit recognition (USPS/MNIST) and Office 31 datasets. Our goal is to analyze how our divergences perform compared with non-smoothed divergences. The first one is the Sliced Wasserstein Distance (SWD) [START_REF] Lee | Sliced wasserstein discrepancy for unsupervised domain adaptation[END_REF] and the second one is the Jenssen-Shannon approximation based on adversarial approach, known as DANN [START_REF] Ganin | Unsupervised domain adaptation by backpropagation[END_REF]. For all methods and for each dataset, we used the same neural network architecture for representation mapping and for classification. Approaches differ only on how distance between distributions have been computed.

Results are depicted in Figure 6. For the two problems, we can see that performances obtained with the Gaussian smoothed sliced Wasserstein or MMD divergences are similar to those obtained with DANN or SWD across all ranges of noise. The smoothed version of Sinkhorn is less stable and induces a slight loss of performance. Owing to the metric property and the induced weak topology, the privacy preservation comes almost without loss of performance in this domain adaptation context.

Conclusion

In this study, we have analyzed the properties of Gaussian smoothed sliced divergence for comparing distributions as they play a crucial role in a privacy preserving context. We have derived several theoretical results related to their topological and statistical properties. More precisely, we have shown that under mild condition on their base divergence, the smoothing and slicing operations preserves metric property. From a statistical point of view, we have shown that sample complexity does not depend on the dimension of the problem and follows a similar complexity than their sliced version, although some overhead may have to be paid due to the smoothing. We have illustrated those theoretical findings through some experimental analyses on toy problem. We have also analyzed the behavior of our divergence on domain adaptation problems and confirm the fact that using those divergences yields only to slight loss of performances while preserving privacy. One lesson we have also learnt is that Gaussian smoothed sliced MMD seems to present several strong benefits in term of sample complexity.

2 .

 2 if the base divergence D(•, •) satisfies the identity of indiscernibles, for µ , ν ∈ P(R), D(µ , ν ) = 0 if and only if µ = ν , then this identity also holds for G σ SD p (•, •) for any µ, ν ∈ P(R d ); 3. if the D(•, •) satisfies the triangle inequality then its Gaussian smoothed sliced version G σ SD p (•, •) satisfies the triangle inequality.

Figure 1 :

 1 Figure 1: Measuring the divergence between two sets of samples in R 50 , of increasing size, randomly drawn from N (0, I). We compare three sliced divergences and their Gaussian smoothed versions with a σ = 3. (left) dimension has been set to d = 50. (right) sample complexity with different dimensions. This plot confirms that the complexity is dimension-independent.

Figure 2 :

 2 Figure 2: Measuring the divergence between two sets of samples drawn iid from the CIFAR10 dataset. We compare three sliced divergences and their Gaussian smoothed versions with a σ = 3.

Figure 3 :

 3 Figure 3: Measuring the divergence between two sets of samples in R 50 , one with mean 21 d and the other with mean s1 d with increasing s. We compare three sliced divergences and their Gaussian smoothed version with a σ = 3.

Figure 5 :

 5 Figure 5: Measuring the divergence between two sets of samples in R 50 drawn from N (0, I). We plot the sample complexity for different Gaussian smoothed divergence at different level of noises.

Figure 6 :

 6 Figure 6: Domain adaptation performances using different divergences on distributions with respect to the Gaussian smoothing. (left) USPS to MNIST. (middle) Office-31 Webcam to DSLR. (right) Office-31 Amazon to Webcam.

A Additional definitions

A.1 Maximum Mean Discrepancy

Let k : X × X → R be the reproducing kernel of a reproducing kernel Hilbert space H. The metric on distance denoted as maximum mean discrepancy between µ and ν belonging to P(X ) is defined as:

For empirical distributions, one can estimate the MMD using biased or unbiased formulations as given by Gretton et al. [START_REF] Gretton | A kernel two-sample test[END_REF]: For empirical distributions, one can estimate the MMD using biased or unbiased formulations as given by Gretton et al. [START_REF] Gretton | A kernel two-sample test[END_REF]:

A.2 Sinkhorn Divergence and Gaussian Smoothed Sliced Sinkhorn Divergence

Let define the entropic regularized Wasserstein distance [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF] between distributions µ and ν as

x -y p γ(x, y)dxdy

where the set Π(µ, ν) is defined as in Section 2. The term H(•|•) is the relative entropy regularization of the transport plan with respect to the product measure µ ⊗ ν, and is given by

The related regularization parameter is λ ≥ 0. Then, the Sinkhorn divergence is defined as

Accordingly the Gaussian Smoothed Sliced Sinkhorn Divergence is expressed as

B Proofs

B.1 Proof of Theorem 1

• Non-negativity (or symmetry). The non-negativity (or symmetry) follows directly from the non-negativity (or symmetry) of D p , see Definition 3.

• Identity property. For the identity property, if the base divergence D p satisfies the identity property in one dimenstional measures, then for any

Let us now prove the fact that for any µ, ν ∈

Following the techniques in proof of Proposition 5.1.2 in [START_REF] Bonnotte | Unidimensional and Evolution Methods for Optimal Transportation[END_REF], for any measure η ∈ P(R m ) (with m ≥ 1), F[η](•) stands for the Fourier transform of s and is given as

Since the Fourier transform is injective, we conclude that µ = ν. •Triangle inequality. Assume that D p is a metric and let µ, ν, η ∈ P(R d ). We then have

where inequality in ( ) follows from the application of Minkowski inequality.

B.2 Proof of Proposition 1

Let us first upper bound the k-th moment of M k (R u µ * N σ ), for all k ≥ 1. For all u ∈ S d-1 , one has

Using the elementary inequality (a + b) k ≤ 2 k-1 (a k + b k ) for k ≥ 1, a ≥ 0, and b ≥ 0, we obtain

We then use the following result: Lemma 1 (see proof of Theorem 1 in [START_REF] Fournier | On the rate of convergence in Wasserstein distance of the empirical measure[END_REF]). Let η ∈ P(R) and let p ≥ 1. Assume that M q (η) < ∞ for some q > p. There exists a constant C p,q depending only on p, q such that, for all n ≥ 1,

n -(q-p)/q 1 q∈(p,2p) .

Let us fix µ ∈ P q (R d ) with q > p ≥ 1 an empirical measure μn . Then, one has

By Lemma 1, we obtain

On the other hand, since W p (•, •) is a metric, by applying Theorem 3, we obtain the following:

n -(q-p)/q 1 q∈(p,2p) .

× 2 q-1 (M q (µ, ν)) + M q (N σ )) p/q 1 q∈2N * 2 q-1 (M q (µ, ν)) p/q 1 q∈2N+1 .

B.3 Proof of Theorem 4

Using Holder's inequality, we have

B.4 Proof of Proposition 4

The proof follows the same lines in proof of Lemma 1 in [START_REF] Nietert | Smooth p-wasserstein distance: Structure, empirical approximation, and statistical applications[END_REF]. First, we have that

. Setting the following random variables: