Thierry Denoeux

Marie-Hélène Masson

Evidential reasoning in large partially ordered sets Application to multi-label classification, ensemble clustering and preference aggregation

Keywords: Belief Functions, Dempster-Shafer theory, Evidence Theory, Lattices, Lattice Intervals, Classification, Clustering, Learning, Preference Relation, Preorder

The Dempster-Shafer theory of belief functions has proved to be a powerful formalism for uncertain reasoning. However, belief functions on a finite frame of discernment Ω are usually defined in the power set 2 Ω , resulting in exponential complexity of the operations involved in this framework, such as combination rules. When Ω is linearly ordered, a usual trick is to work only with intervals, which drastically reduces the complexity of calculations. In this paper, we show that this trick can be extrapolated to frames endowed with an arbitrary lattice structure, not necessarily a linear order. This principle makes it possible to apply the Dempster-Shafer framework to very large frames such as the power set, the set of partitions, or the set of preorders of a finite set. Applications to multi-label classification, ensemble clustering and preference aggregation are demonstrated.

Introduction

The theory of belief functions originates from the pioneering work of Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Dempster | Upper and lower probabilities generated by a random closed interval[END_REF] and Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF]. In the 1990's, the theory was further developed by Smets [START_REF] Smets | The combination of evidence in the Transferable Belief Model[END_REF][START_REF] Smets | The Transferable Belief Model[END_REF], who proposed a non probabilistic interpretation (referred to as the "Transferable Belief Model") and introduced several new tools for information fusion and decision making. Big steps towards the application of belief functions to real-world problems involving many variables have been made with the introduction of efficient algorithms for computing marginals in valuation-based systems [START_REF] Shafer | Propagating belief functions in qualitative Markov trees[END_REF][START_REF] Shenoy | Binary joint trees for computing marginals in the Shenoy-Shafer architecture[END_REF].

Although there has been some work on belief functions on continuous frames (see, e.g., [START_REF] Liu | A theory of Gaussian belief functions[END_REF][START_REF] Smets | Belief functions on real numbers[END_REF]), the theory of belief functions has been mainly applied in the discrete setting. In this case, all functions introduced in the theory as representations of evidence (including mass, belief, plausibility and commonality functions) are defined from the Boolean lattice Thierry Denoeux Heudiasyc, Université de Technologie de Compiègne, CNRS, E-mail: tdenoeux@hds.utc.fr Marie-Hélène Masson Heudiasyc, Université de Picardie Jules Verne, CNRS, E-mail: mmasson@hds.utc.fr (2 Ω , ⊆) to the interval [0, 1]. Consequently, all operations involved in the theory (such as the conversion of one form of evidence to another, or the combination of two items of evidence using Dempster's rule) have exponential complexity with respect to the cardinality K of the frame Ω , which makes it difficult to use the Dempster-Shafer formalism in very large frames [START_REF] Wilson | Algorithms for Dempster-Shafer theory[END_REF].

When the frame Ω is linearly ordered, a usual trick is to constrain the focal elements (i.e., the subsets of Ω such that m(A) > 0) to be intervals (see, for instance, [START_REF] Denoeux | Constructing belief functions from sample data using multinomial confidence regions[END_REF]). The complexity of manipulating and combining mass functions is then drastically reduced from 2 K to K 2 . Most formula of belief function theory work for intervals, because the set of intervals equipped with the inclusion relation has a lattice structure. As shown recently in [START_REF] Grabisch | Belief functions on lattices[END_REF], belief functions can be defined in any lattice, not necessarily Boolean. In this paper, this trick will be extended to the case of frames endowed with a lattice structure, not necessarily a linear order. As it will be shown, a lattice of intervals can be constructed, in which belief functions can be defined. This approach makes it possible to define belief functions in very large frames (such as the power set of a finite set Ω , the set of partitions of a finite set, or the set of preorders of a finite set) with manageable complexity.

The rest of this paper is organized as follows. The necessary background on belief functions and on lattices will first be recalled in Sections 2 and 3, respectively. Our main idea will then be exposed in Section 4. It will then be applied to three data analysis problems involving the definition and manipulation of belief functions on 1. The powerset of a finite set (Section 5), with application to multi-label classification; 2. The set of partitions of a finite set (Section 6), with application to ensemble clustering; 3. The set of preorders of a finite set (Section 7), with application to preference aggregation from pairwise comparisons.

Finally, Section 8 will conclude this paper. Note that the applications to multi-label classification and ensemble clustering have been described separately in [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF][START_REF] Younes | An evidence-theoretic k-nearest neighbor rule for multi-label classification[END_REF] and [START_REF] Masson | Belief functions and cluster ensembles[END_REF][START_REF] Masson | Ensemble clustering in the belief functions framework[END_REF], respectively. The present paper presents the approach in much greater generality and provides a unified view of the two previous applications. To demonstrate the generality of the new introduced framework, a third application to preference aggregation is dealt with. A unified decision making procedure based on commonalities is also introduced.

Belief Functions: Basic Notions

Let Ω be a finite set. A (normalized) mass function on Ω is a function m : 2 Ω → [0, 1] such that m( / 0) = 0 and

∑ A⊆Ω m(A) = 1. (1)
The subsets A of Ω such that m(A) > 0 are called the focal elements of m. The normalization property can be relaxed by dropping the condition m( / 0) = 0. Only normalized mass functions will be considered in this paper. A mass function m is often used to model beliefs held by an agent about a variable X taking a single but ill-known value ω 0 in Ω [START_REF] Smets | The Transferable Belief Model[END_REF]. The quantity m(A) is then interpreted as the measure of the belief that is committed exactly to the hypothesis ω 0 ∈ A. Full certainty corresponds to the case where m({ω k }) = 1 for some ω k ∈ Ω , while total ignorance is modeled by the vacuous mass function verifying m(Ω ) = 1.

To each normalized mass function m can be associated a belief function bel defined as follows:

bel(A) = ∑ B⊆A m(B), (2)
for all A ⊆ Ω . It is clear that bel( / 0) = 0 and bel(Ω ) = 1. Each quantity bel(A) is interpreted as the total degree of justified belief [START_REF] Smets | The Transferable Belief Model[END_REF] in the proposition "The true value ω 0 of X belongs to A". Conversely, m can be recovered from bel as

m(A) = ∑ B⊆A (-1) |A\B| bel(B), (3)
for all A ⊆ Ω , where | • | denotes cardinality. Function m is said to be the Möbius transform of bel. For any function f from 2 Ω to [0, 1] such that f ( / 0) = 0 and f (Ω ) = 1, the following conditions are known to be equivalent [START_REF] Shafer | A mathematical theory of evidence[END_REF]:

1. The Möbius transform m of f is positive and verifies ∑ A⊆Ω m(A) = 1. 2. f is totally monotone, i.e., for any k ≥ 2 and for any family

A 1 , . . ., A k in 2 Ω , f k i=1 A i ≥ ∑ / 0 =I⊆{1,...,k} (-1) |I|+1 f i∈I A i .
Hence, bel defined by ( 2) is totally monotone.

Other functions related to m are the plausibility function, defined as

pl(A) = ∑ B∩A =/ 0 m(B) = 1 -bel(A), ∀A ⊆ Ω (4)
and the commonality function (or co-Möbius transform of bel) defined as

q(A) = ∑ B⊇A m(B), ∀A ⊆ Ω . (5)
Obviously, q( / 0) = 1 and q(Ω ) = m(Ω ). Function m can be recovered from q using the following relation:

m(A) = ∑ B⊇A (-1) |B\A| q(B). ( 6
)
Functions m, bel, pl and q are thus in one-to-one correspondence and can be regarded as different facets of the same information.

When the reliability of a source is doubtful, the mass provided by this source can be discounted using the following operation:

α m(A) = (1 -α)m(A) ∀A = Ω , α m(Ω ) = (1 -α)m(Ω ) + α, (7)
where 0 ≤ α ≤ 1 is the discount rate. This coefficient is related to our confidence in the reliability of the source of information [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF]. It can be interpreted as the plausibility that the source is unreliable. When α is equal to 1, the vacuous mass function is obtained. When α = 0, m remains unchanged.

Let us now assume that we receive two normalized mass functions m 1 and m 2 from two distinct sources of information assumed to be reliable. Then m 1 and m 2 can be combined using Dempster's rule of combination defined as follows:

(m 1 ⊕ m 2 )(A) =    ∑ B∩C=A m 1 (B)m 2 (C) 1 -κ if A = / 0 0 if A = / 0, (8)
where κ = ∑ B∩C=/ 0 m 1 (B)m 2 (C) is the degree of conflict between the two mass functions, assumed to be strictly smaller than one. This rule is commutative, associative, and admits the vacuous mass function as neutral element. Let q 1 ⊕ q 2 denote the commonality function corresponding to m 1 ⊕ m 2 . It can be computed from q 1 and q 2 , the commonality functions associated to m 1 and m 2 , as follows:

(q 1 ⊕ q 2 )(A) = q 1 (A) • q 2 (A) 1 -κ , (9)
for all non empty subset A of Ω , and (q 1 ⊕ q 2 )( / 0) = 1. The conjunctive sum has a dual disjunctive rule [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF], obtained by substituting union for intersection in [START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF], and dropping the normalization constant, which is no longer needed:

(m 1 ∪ m 2 )(A) = ∑ B∪C=A m 1 (B)m 2 (C), ∀A ⊆ Ω . ( 10
)
Denoting by bel 1 ∪ bel 2 the belief function corresponding to m 1 ∪ m 2 , it can be shown that

(bel 1 ∪ bel 2 )(A) = bel 1 (A) • bel 2 (A), ∀A ⊆ Ω , (11)
which is the counterpart of ( 9). Given two mass functions m 1 and m 2 on the same frame of discernment Ω , we say that m 1 is a specialization of m 2 (or, equivalently, that m 2 is a generalization of m 1 ), if m 1 can be obtained from m 2 by transferring masses m 2 (B) to subsets of B, for all focal elements B of m 2 [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF]. It is then more informative, or more committed. Formally, this property can be expressed as follows:

m 1 (A) = ∑ B⊆Ω S(A, B)m 2 (B), ∀A ⊆ Ω , (12)
where S :

2 Ω × 2 Ω → [0, 1] verifies ∑ A⊆Ω S(A, B) = 1, ∀B ⊆ Ω , and
S(A, B) > 0 ⇒ A ⊆ B, A, B ⊆ Ω .

Belief Functions in General Lattices

As shown by Grabisch [START_REF] Grabisch | Belief functions on lattices[END_REF], the theory of belief functions can be defined not only in Boolean lattices, but in any lattice, not necessarily Boolean. We will first recall some basic definitions about lattices. Grabisch's results used in this work will then be summarized.

Lattices

A review of lattice theory can be found in [START_REF] Monjardet | The presence of lattice theory in discrete problems of mathematical social sciences[END_REF]. The following presentation follows [START_REF] Grabisch | Belief functions on lattices[END_REF].

Let L be a finite set and ≤ a partial ordering (i.e., a reflexive, antisymmetric and transitive relation) on L. The structure (L, ≤) is called a poset. We say that (L, ≤) is a lattice if, for every x, y ∈ L, there is a unique greatest lower bound (denoted x ∧ y) and a unique least upper bound (denoted x ∨ y). Operations ∧ and ∨ are called the meet and join operations, respectively. For finite lattices, the greatest element (denoted ⊤) and the least element (denoted ⊥) always exist. A strict partial ordering < is defined from ≤ as x < y if x ≤ y and ¡ ¢ £ Fig. 1 Hasse diagram of a lattice on Ω = {x,y,z,t}.

x = y. We say that x covers y if y < x and there is no z such that y < z < x. An element x of L is an atom if it covers only one element and this element is ⊥. It is a co-atom if it is covered by a single element and this element is ⊤.

Two lattices L and L ′ are isomorphic if there exists a bijective mapping f from L to L ′ such that x ≤ y ⇔ f (x) ≤ f (y). For any poset (L, ≤), we can define its dual (L, ≥) by inverting the order relation. A lattice is autodual if it is isomorphic to its dual.

A lattice is distributive if (x ∨ y) ∧ z = (x ∧ z) ∨ (y ∧ z) holds for all x, y, z ∈ L. For any x ∈ L, we say that x has a complement in L if there exists x ′ ∈ L such that x ∧ x ′ = ⊥ and x ∨ x ′ = ⊤. L is said to be complemented if any element has a complement. Boolean lattices are distributive and complemented lattices. In a Boolean lattice, every element has a unique complement. Every Boolean lattice is isomorphic to (2 Ω , ⊆) for some set Ω . For the lattice (2 Ω , ⊆), we have ∧ = ∩, ∨ = ∪, ⊥ = / 0 and ⊤ = Ω .

Example 1 Let Ω = {x, y, z,t} be a frame of discernment, and let ≤ be the following partial order: x ≤ y, x ≤ z, y ≤ t, z ≤ t. This order is represented by the Hasse diagram shown in Figure 1. In this representation, a line segments goes upward from a to b if b covers a. It is easy to see that (Ω , ≤) forms a lattice, isomorphic to the Boolean lattice (2 Θ , ⊆) with |Θ | = 2. The least element is x, the greatest element is t, and y and z are both atoms and co-atoms.

A closure system on a set Θ is a family C of subsets of Θ containing Θ , and closed under intersection. As shown in [START_REF] Monjardet | The presence of lattice theory in discrete problems of mathematical social sciences[END_REF], any closure system (C , ⊆) is a lattice with ∧ = ∩ and ∨ = ⊔ defined by

A ⊔ B = {C ∈ C |A ∪ B ⊆ C}, ∀(A, B) ∈ C 2 . ( 13
)

Belief Functions on Lattices

Let (L, ≤) be a finite poset having a least element, and let f be a function from L to R.

The Möbius transform of f is the function m : L → R defined as the unique solution of the equation:

f (x) = ∑ y≤x m(y), ∀x ∈ L. ( 14
)
Function m can be expressed as:

m(x) = ∑ y≤x µ(y, x) f (y), (15)
where µ(x, y) : L 2 → R is the Möbius function, which is defined inductively by:

µ(x, y) =        1 if x = y, -∑ x≤t<y µ(x,t) if x < y, 0, otherwise. (16)
The co-Möbius transform of f is defined as:

q(x) = ∑ y≥x m(y), ( 17
)
and m can be recovered from q as:

m(x) = ∑ y≥x µ(x, y)q(y). ( 18
)
Let us now assume that (L, ≤) is a lattice. Following Grabisch [START_REF] Grabisch | Belief functions on lattices[END_REF], a function bel : L → [0, 1] will be called a belief function on L if bel(⊥) = 0, bel(⊤) = 1, and its Möbius transform is non negative.

As shown in [START_REF] Grabisch | Belief functions on lattices[END_REF], any belief function on (L, ≤) is totally monotone, i.e., for any k ≥ 2 and for any family x 1 , . . .,

x k in L, bel k i=1 x i ≥ ∑ / 0 =I⊆{1,...,k} (-1) |I|+1 bel i∈I x i .
However, the converse does not hold in general: a totally monotone function may not have a non negative Möbius transform.

As shown in [START_REF] Grabisch | Belief functions on lattices[END_REF], most results of Dempster-Shafer theory can be transposed in the general lattice setting. For instance, Dempster's rule can be extended by replacing ∩ by ∧ in [START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF], and relation (9) between commonality functions is preserved. Similarly, we can extend the disjunctive rule [START_REF] Denoeux | Conjunctive and Disjunctive Combination of Belief Functions Induced by Non Distinct Bodies of Evidence[END_REF] by substituting ∨ for ∪ in [START_REF] Denoeux | Conjunctive and Disjunctive Combination of Belief Functions Induced by Non Distinct Bodies of Evidence[END_REF], and relation [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF] still holds.

The discounting operation [START_REF] Denoeux | Analysis of evidence-theoretic decision rules for pattern classification[END_REF] and the notion of specialization [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF] can be also generalized in straightforward ways. However, the extension of other notions from classical Dempster-Shafer theory may require additional assumptions on (L, ≤). For instance, the definition of the plausibility function pl as the dual of bel using (4) can only be extended to autodual lattices [START_REF] Grabisch | Belief functions on lattices[END_REF].

Belief functions with Lattice Intervals as Focal Elements

Let Ω be a finite frame of discernment. If the cardinality of Ω is very large, working in the Boolean lattice (2 Ω , ⊆) may become intractable. This problem can be circumvented by defining the set of propositions as a strict subset of 2 Ω . As shown in Section 3, the Dempster-Shafer calculus can be applied in this restricted set of propositions as long as it has a lattice structure. To be meaningful, the definition of propositions should be based on some underlying structure of the frame of discernment.

When the frame Ω is linearly ordered, then a usual trick consists in assigning non zero masses only to intervals. Here, we propose to extend and formalize this approach, by considering the more general case where Ω has a lattice structure for some partial ordering ≤.

The set of events is then defined as the set I Ω ,≤ of lattice intervals in (Ω , ≤). We will show that (I Ω ,≤ , ⊆) is then itself a lattice, in which the Dempster-Shafer calculus can be applied.

The lattice (I Ω ,≤ , ⊆) of intervals of a lattice (Ω , ≤) will first be introduced more precisely in Section 4.1. The definition of belief functions in (I Ω ,≤ , ⊆) will then be dealt with in Section 4.2.

4.1 The Lattice (I Ω ,≤ , ⊆)

Let Ω be a finite frame of discernment, and let ≤ be a partial ordering of Ω such that (Ω , ≤) is a lattice, with greatest element ⊤ and least element ⊥. A subset I of Ω is a (lattice) interval if there exist elements a and b of Ω such that

I = {x ∈ Ω |a ≤ x ≤ b}.
We then denote I as [a, b]. Obviously, Ω is the interval [⊥, ⊤] and / 0 is the empty interval represented by [a, b] for any a and b such that a ≤ b does not hold. Let I Ω ,≤ ⊆ 2 Ω be the set of intervals, including the empty set / 0:

I Ω ,≤ = {[a, b]|a, b ∈ Ω , a ≤ b} ∪ { / 0}.
The intersection of two intervals is an interval:

[a, b] ∩ [c, d] = [a ∨ c, b ∧ d] if a ∨ c ≤ b ∧ d, / 0 otherwise.
Consequently, I Ω ,≤ is a closure system, and (I Ω ,≤ , ⊆) is a lattice, with least element / 0 and greatest element Ω . We have

[a, b] ⊆ [c, d] ⇔ c ≤ a and b ≤ d.
The meet operation is the intersection, and the join operation ⊔ is defined by

[a, b] ⊔ [c, d] = [a ∧ c, b ∨ d]. ( 19
) Clearly, [a, b] ⊆ [a, b] ⊔ [c, d] and [c, d] ⊆ [a, b] ⊔ [c, d], hence [a, b] ∪ [c, d] ⊆ [a, b] ⊔ [c, d],
but the inclusion is strict in general. We note that (I Ω ,≤ , ⊆) is a subposet, but not a sublattice of (2 Ω , ⊆), because they do not share the same join operation.

The atoms of (I Ω ,≤ , ⊆) are the singletons of Ω , while the co-atoms are intervals of the form [⊥, x], where x is a co-atom of (Ω , ≤), or [x, ⊤], where x is an atom of (Ω , ≤). The lattice (I Ω ,≤ , ⊆) is usually neither autodual, nor Boolean.

Example 2 Let (Ω , ≤) be the lattice defined in Example 1. Figure 2 displays the corresponding lattice of intervals (I Ω ,≤ , ⊆). There are ten distinct intervals of (Ω , ≤), including the empty set. The atoms of (I Ω ,≤ , ⊆) are the singletons of Ω , and the co-atoms are [x, y] = {x, y}, [x, z] = {x, z}, [y,t] = {y,t} and [z,t] = {z,t}. This lattice is complemented, but the complements are not unique: for instance, {x, z} ∩ {y,t} = / 0 and {x, z} ⊔ {y,t} = Ω , but we also have {x, z} ∩ {t} = / 0 and {x, z} ⊔ {t} = Ω : consequently, {y,t} and {t} are two complements of {x, z}. As a consequence, the lattice (I Ω ,≤ , ⊆) is not Boolean.

¡ ¢ £ ¢ ¤ ¢ ¥ ¢ ¡ ¦ £ ¢ ¡ ¦ ¤ ¢ £ ¦ ¥ ¢ ¤ ¦ ¥ ¢ :
Fig. 2 The lattice (I Ω,≤ ,⊆) of intervals of the lattice (Ω ,≤) shown in Figure 1.

Belief Functions in

(I Ω ,≤ , ⊆)
Let m be a mass function from I Ω ,≤ to [0, 1]. Belief and commonality functions can be defined in (I Ω ,≤ , ⊆) as explained in Section 3. Conversely, m can be recovered from bel and q using (15) and ( 18), where the Möbius function µ depends on the lattice (I Ω ,≤ , ⊆).

As the cardinality of I Ω ,≤ is at most proportional to K 2 , where K is the cardinality of Ω , all these operations, as well as the conjunctive and disjunctive sums can be performed in polynomial time.

Example 3 Let us come back to Example 2. Given a mass function m : I Ω ,≤ → [0, 1], the corresponding belief function can be computed as bel( / 0) = 0, bel(Ω ) = 1, and

bel({x}) = m({x}), bel({y}) = m({y}), bel({z}) = m({z}), bel({t}) = m({t}), bel({x, y}) = m({x}) + m({y}) + m({x, y}), bel({x, z}) = m({x}) + m({z}) + m({x, z}), bel({y,t}) = m({y}) + m({t}) + m({y,t}), bel({z,t}) = m({z}) + m({t}) + m({z,t}).
By solving the above linear system, we easily find that m can be recovered from bel using [START_REF] Gonzales-Pachon | Inferring consensus weights from pairwise comparison matrices without suitable properties[END_REF], with the Möbius function defined for all A and B in I Ω ,≤ by

µ(A, B) = (-1) |B\A| if A ⊆ B 0 otherwise.
Given a mass function m on (I Ω ,≤ , ⊆), we may define a function m * on (2 Ω , ⊆) as

m * (A) = m(A) if A ∈ I Ω ,≤ , 0 otherwise. m * will be called the extension of m in (2 Ω , ⊆).
Let bel * and q * be the belief and commonality functions associated to m * . It is obvious that bel * (I) = bel(I) and q * (I) = q(I) for all I ∈ I Ω ,≤ . Let m 1 and m 2 be two mass functions on (I Ω ,≤ , ⊆), and let m * 1 and m * 2 be their extensions in (2 Ω , ⊆). Because the meet operations

(I Ω,≤ ,⊆) of Example 2. A m 1 (A) m 2 (A) bel 1 (A) bel 2 (A) (bel 1 ∪ bel 2 )(A) (m 1 ∪ m 2 )(A) / 0 0 0 0 0 0 0 {x} 0.1 0 0.1 0 0 0 {y} 0.2 0.
(m * 1 ⊕ m * 2 )(A) = (m 1 ⊕ m 2 )(A) if A ∈ I Ω ,≤ , 0 otherwise.
However, computing the disjunctive sum in (2 Ω , ⊆) or (I Ω ,≤ , ⊆) is not equivalent, because the join operation in (I Ω ,≤ , ⊆), defined by [START_REF] Liu | A theory of Gaussian belief functions[END_REF], is not identical to the union operation in 2 Ω . Consequently, when computing the disjunctive sum of m * 1 and m * 2 , the product

m * 1 (A)m * 2 (B) is transferred to A ∪ B, whereas the product m 1 (A)m 2 (B) is transferred to A ⊔ B when com- bining m 1 and m 2 . Let (m 1 ∪ m 2 ) * be the extension of m 1 ∪ m 2 in (2 Ω , ⊆). As A ⊔ B ⊇ A ∪ B, (m 1 ∪ m 2 )
* is thus a generalization (i.e., an outer approximation [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF][START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF]

) of m * 1 ∪ m * 2 .
When masses are assigned to intervals of the lattice (Ω , ≤), doing the calculations in (I Ω ,≤ , ⊆) can thus be seen an approximation of the calculations in (2 Ω , ⊆), with a loss of information only when a disjunctive combination is performed.

Example 4 Table 1 shows two mass functions m 1 and m 2 on the lattice (I Ω ,≤ , ⊆) defined in Example 2, as well as the corresponding belief functions, and the result m 1 ∪ m 2 of their disjunctive combination. Table 2 shows the extensions m * 1 and m * 2 of m 1 and m 2 in 2 Ω , as well as their disjunctive combination m * 1 ∪ m * 2 . It can be verified that m * 1 ∪ m * 2 is a specialization of (m 1 ∪ m 2 ) * , i.e., it is strictly more committed. Computing the disjunctive combination in the lattice (I Ω ,≤ , ⊆) has thus resulted in a loss of information.

To conclude this section, we may also remark that the reduction of complexity obtained by expressing beliefs in the lattice of intervals comes with a loss of expressive power. It is clear that, whereas any mass function m in I Ω ,≤ has an extension m * in 2 Ω , any mass function in 2 Ω with at least one focal element A ⊆ Ω not belonging to I Ω ,≤ cannot be expressed in that lattice. Such a mass function could be approximated by transferring each mass m(A) for A ∈ I Ω ,≤ to the smallest interval containing A. However, in the worst case, all information can be lost in this process.

For instance, considering again the lattice defined in Example 2, let m be the mass function on (2 Ω , ⊆) such that m({y, z,t}) = 1. This mass function expresses the opinion that the true value ω 0 in Ω is certainly not equal to x. It can be approximated in I Ω ,≤ by transferring the unit mass of belief to the smallest interval containing {y, z,t}, which is Ω itself, resulting in the vacuous mass function. However, this is a somewhat extreme case. Complex real-world problems in which useful information can be expressed in a lattice of intervals will be described below.

A m * 1 (A) m * 2 (A) bel * 1 (A) bel * 2 (A) (bel * 1 ∪ bel * 2 )(A) (m * 1 ∪ m * 2 )(A) * / 0 0 0 0 0 0 0 * {x} 0.1 0 0.1 0 0 0 *

Decision making

When working with belief functions in a Boolean Lattice (2 Ω , ⊆), a usual decision rule is to select the singleton {ω} of Ω with the largest plausibility or, equivalently, with the largest commonality [START_REF] Denoeux | Analysis of evidence-theoretic decision rules for pattern classification[END_REF][START_REF] Cobb | On the plausibility transformation method for translating belief function models to probability models[END_REF]. In the lattice (I Ω ,≺ , ⊆), the plausibility function is not defined, but the commonality function exists and its maximum can sometimes be computed efficiently without enumerating the elements of Ω , as will be shown below. A possible rule for decision making is thus to select the element of Ω with the largest commonality.

Reasoning with Set-valued Variables

In this section, we present a first application of the above scheme to the representation of knowledge regarding set-valued variables [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF]. The general framework will be presented in Section 5.1, and it will be applied to multi-label classification in Section 5.2.

Evidence on Set-valued Variables

Let Θ be a finite set, and let X be a variable taking values in the power set 2 Θ . Such a variable is said to be set-valued, or conjunctive [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF][START_REF] Yager | Set-based representations of conjunctive and disjunctive knowledge[END_REF]. For instance, in diagnosis problems, Θ may denote the set of faults that can possibly occur in a system, and X the set of faults actually occurring at a given time, under the assumption that multiple faults can occur. In text classification, Θ may be a set of topics, and X the list of topics dealt with in a given text, etc. Defining belief functions on the lattice (2 2 Θ , ⊆) is practically intractable, because of the double exponential complexity involved. However, we may exploit the lattice structure induced by the ordering ⊆ in Ω = 2 Θ , using the general approach outlined in Section 4 [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF].

For any two subsets A and B of Θ such that A ⊆ B, the interval [A, B] is defined as

[A, B] = {C ⊆ Θ |A ⊆ C ⊆ B}.
The set of intervals of the lattice (Ω , ⊆) is thus

I Ω ,⊆ = {[A, B]|A, B ∈ Ω , A ⊆ B} ∪ / 0 Ω ,
where / 0 Ω denotes the empty sets of Ω (as opposed to the empty set of Θ ). Clearly, I Ω ,⊆ ⊆ 2 Ω = 2 2 Θ . The interval [A, B] can be seen as the specification of an unknown subset C of Θ that surely contains all elements of A, and possibly contains elements of B. Alternatively, C surely contains no element of B.

As the meet and join in the lattice (Θ , ⊆) are set intersection and union, respectively, the corresponding operations in (I Ω ,⊆ , ⊆) are

[A, B] ∩ [C, D] = [A ∪C, B ∩ D] if A ∪C ⊆ B ∩ D, / 0 Ω otherwise and [A, B] ⊔ [C, D] = [A ∩C, B ∪ D].
As noticed in [START_REF] Grabisch | Bi-capacities -I: definition, Möbius transform and interaction[END_REF], any interval [A, B] of subsets of Θ = {θ 1 , . . . , θ K } can be represented by a vector (u 1 , . . . , u K ) ∈ {-1, 0, 1} K , with

u k =      1 if θ k ∈ A, -1 if θ k ∈ B, 0 otherwise.
This encoding makes it possible to implement the ∩ and ⊔ operations in a simple way using generalized truth tables. It also makes it clear that the cardinality of I Ω ,⊆ is equal to 3 K + 1, which is much less than the 2 2 K elements of 2 Ω .

Example 5 Let Θ = {a, b, c, d} be the set of possible faults of a given system. Assume that several faults can occur simultaneously, and we receive two independent pieces of evidence:

-Item of evidence 1: fault a is surely present and faults {b, c} may also be present, with confidence 0.7. This is represented by the following mass function:

m 1 ([{a}, {a, b, c}]) = 0.7, m 1 ([ / 0 Θ ,Θ ]) = 0.3.
-Item of evidence 2: fault c is surely present, and either faults {a, b} (with confidence 0.8) or faults {a, d} (with confidence 0.2) may also be present. This is represented by

m 2 ([{c}, {a, b, c}]) = 0.8, m 2 ([{c}, {a, c, d}]) = 0.2.
The combination of m 1 and m 2 by Dempster's rule can be computed using the following table:

[{a}, {a, b, c}] [ / 0 Θ ,Θ ] 0.7 0.3 [{c}, {a, b, c}] [{a, c}, {a, b, c}] [{c},

Application to Multi-label Classification

In [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF][START_REF] Younes | An evidence-theoretic k-nearest neighbor rule for multi-label classification[END_REF], the above framework was applied to multi-label classification [START_REF] Zhang | ML-KNN: a lazy learning approach to multi-label learning[END_REF][START_REF] Trohidis | Multi-label classification of music into emotions[END_REF]. In this learning task, each object may belong simultaneously to several classes, contrary to standard single-label problems where objects belong to only one class. For instance, in image retrieval, each image may belong to several semantic classes such as "beach" or "urban".

In such problems, the goal is to predict the value of the class variable for a new instance, based on a training set. As the class variable is set-valued, the framework developed in the previous section can be applied.

In order to construct a multi-label classifier, we generally assume the existence of a labeled training set, composed of n examples (x i ,Y i ), where x i is a feature vector describing instance i, and Y i is a label set for that instance, defined as a subset of the set Θ of classes [START_REF] Zhang | ML-KNN: a lazy learning approach to multi-label learning[END_REF][START_REF] Trohidis | Multi-label classification of music into emotions[END_REF]. In practice, however, gathering such high quality information is not always feasible at a reasonable cost. In many problems, there is no ground truth for assigning unambiguously a label set to each instance, and the opinions of one or several experts have to be elicited. Typically, an expert will sometimes express lack of confidence for assigning exactly one label set.

The formalism described in Section 5.1 can easily be used to handle such situations. In the most general setting, the opinions of one or several experts regarding the set of classes that pertain to a particular instance i may be modeled by a mass function m i in (I Ω ,⊆ , ⊆). A less general, but arguably more operational option is to restrict m i to be categorical, i.e., to have a single focal element [A i , B i ], with A i ⊆ B i ⊆ Θ . The set A i is then the set of classes that certainly apply to example i, while B i is the set of classes that possibly apply to that instance. In a multiple expert setting, A i might represent the set of classes indicated by all experts as relevant to describe instance i, while B i would be the set of classes mentioned by some experts. The usual situation of precise labeling is recovered in the special case where

A i = B i .
For instance, assume that instances are songs and classes are emotions generated by these songs. Upon hearing a song, an expert may decide that it certainly evokes happiness and certainly does not evoke sadness, but may be undecided regarding the other emotions (such as quietness, anger, surprise, etc.). In that case, the song cannot be assigned a single label set, but we can associate to it the set of all label sets containing "happiness" and not containing "sadness", which has the form suggested above.

The evidential k nearest neighbor rule introduced in [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF] can be extended to the multilabel framework as follows. Let Φ k (x) denote the set of k nearest neighbors of a new instance described by feature vector x, according to some distance measure d, and x i an element of that set with label [A i , B i ]. This item of evidence can be described by the following mass function in (I Ω ,⊆ , ⊆):

m i ([A i , B i ]) = β exp (-γd(x, x i )) = α i , m i ([ / 0 Θ ,Θ ]) = 1 -β exp (-γd(x, x i )) = 1 -α i ,
where β and γ are two parameters such that 0 < β < 1 and γ > 0. These k mass functions are then combined into a single one m using Dempster's rule:

m = ⊕ k i=1 m i . (20)
For decision making, it was proposed in [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF][START_REF] Younes | An evidence-theoretic k-nearest neighbor rule for multi-label classification[END_REF] to use the following rule. Let Y be the predicted label set for instance x. To decide whether to include each class θ ∈ Θ or not, two quantities were computed: the degree of belief bel([{θ },Θ ]) that the true label set Y contains θ , and the degree of belief bel([ / 0, {θ }]) that it does not contain θ . The set of predicted labels Y was then defined as

Y = {θ ∈ Θ | bel([{θ },Θ ]) ≥ bel([ / 0, {θ }])}.
This method was shown in [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF][START_REF] Younes | Evidential multi-label classification approach to learning from data with imprecise labels[END_REF] to yield good performances compared to standard multilabel classification methods, especially when class labels are uncertain.

As noted in Section 4.3, an alternative way of making a decision is to find the set of labels with the greatest commonality. This approach may be formalized as follows. The commonality function corresponding to the combination ( 20) is given by:

q ∝ k ∏ i=1 q i , (21)
where q i is the commonality function associated to m i . These individual commonalities can be simply expressed for any subset Y of Θ by:

q i (Y ) = 1 if A i ⊆ Y ⊆ B i , 1 -α i otherwise. ( 22
)
We thus have :

q(Y ) ∝ k ∏ i=1 (1 -α i ) 1-δ i , (23)
with

δ i = 1 if A i ⊆ Y ⊆ B i 0 otherwise.
For each focal element [A i , B i ], let us introduce the following notations:

a i j = 1 if θ j ∈ A i 0 otherwise. and b i j = 1 if θ j ∈ B i 0 otherwise.
In the same way, a subset Y of Θ will be represented by a K-dimensional vector y whose component are defined by y j = 1 if θ j ∈ Y and 0 otherwise. With these notations, the inclusion constraint A i ⊆ Y may be translated by:

K ∑ j=1 a i j y j = K ∑ j=1 a i j .
Similarly, the constraint Y ⊆ B i , or, equivalently, Bi ⊆ Ȳ , may be written as:

K ∑ j=1 (1 -b i j )(1 -y j ) = K ∑ j=1 (1 -b i j ).
Maximizing q(Y ) is equivalent to maximizing its logarithm, which is equal to:

ln q(Y ) = k ∑ i=1 (1 -δ i ) ln(1 -α i ) + constant.
To find the set Y of greatest commonality, we can thus solve the following binary integer programming problem:

min y∈{0,1} K ,δ ∈{0,1} k k ∑ i=1 δ i ln(1 -α i ), (24)
subject to the constraints:

         K ∑ j=1 a i j y j ≥ δ i K ∑ j=1 a i j ∀i = 1, k, K ∑ j=1 (1 -b i j )(1 -y j ) ≥ δ i K ∑ j=1 (1 -b i j ) ∀i = 1, k. ( 25
)
Note that the way in which the constraints [START_REF] Perny | Multicriteria filtering methods based onconcordance and non-discordance principles[END_REF] are written ensures that if δ i is set to 1, Y is enforced to belong to [A i , B i ], and if δ i is set to 0, there is no constraint on Y with respect to A i and B i . This method is more general and computationally more efficient than the method described in [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF][START_REF] Younes | Evidential multi-label classification approach to learning from data with imprecise labels[END_REF]; it has been found experimentally to yield similar results when applied to multi-label classification problem.

Belief Functions on Partitions

Ensemble clustering methods [START_REF] Hornik | Ensemble methods for cluster analysis[END_REF][START_REF] Fred | Cluster ensemble methods: from single clusterings to combined solutions[END_REF] aim at combining multiple clustering solutions or partitions into a single one, offering a better description of the data. In this section, we explain how to address this fusion problem using the general framework introduced in Section 4. Each clustering algorithm (or "clusterer") can be considered as a partially reliable source, giving an opinion about the true, unknown, partition of the objects. This opinion provides evidence in favor of a set of possible partitions. Moreover, we suppose that the reliability of each source is described by a confidence degree, either assessed by an external agent or evaluated using a class validity index. Manipulating beliefs defined on sets of partitions is intractable in the usual case where the number of potential partitions is high (for example, a set composed of 6 elements has 203 potential partitions!) but it can be manageable using the lattice structure of partitions, as will be explained below. Note that, due to space limitations, only the main principles will be introduced. More details may be found in [START_REF] Masson | Belief functions and cluster ensembles[END_REF][START_REF] Masson | Ensemble clustering in the belief functions framework[END_REF].

First, basic notions about the lattice of partitions of a set are recalled in Section 6.1, then our approach is explained and illustrated in Section 6.2 using a synthetic data set.

Lattice of Partitions

Let E denote a finite set of n objects. A partition p is a set of non empty, pairwise disjoint subsets E 1 , . . . , E k of E, such that their union is equal to E. Every partition p can be associated to an equivalence relation (i.e., a reflexive, symmetric, and transitive binary relation) on E, denoted by R p , and characterized, for all (a i , a j ) ∈ E 2 , by: R p (a i , a j ) = 1 if a i and a j belong to the same cluster in p, 0 otherwise.

The set of all partitions of E, denoted Ω , can be partially ordered using the following ordering relation: partition p is said to be finer than partition p ′ on the same set E (denoted p p ′ ) if the clusters of p can be obtained by splitting those of p ′ (or equivalently, if each cluster of p ′ is the union of some clusters of p). This partial ordering can be alternatively defined using the equivalence relations associated to p and p ′ :

p p ′ ⇔ R p (a i , a j ) ≤ R p ′ (a i , a j ), ∀(a i , a j ) ∈ E 2 .
The set Ω endowed with the -order has a lattice structure [START_REF] Monjardet | The presence of lattice theory in discrete problems of mathematical social sciences[END_REF]. In this lattice, the meet p ∧ p ′ of two partitions p and p ′ is defined as the coarsest partition among all partitions finer than p and p ′ . The clusters of the meet p ∧ p ′ are obtained by considering pairwise intersections between clusters of p and p ′ . The equivalence relation R p∧p ′ is simply obtained as the minimum of R p and R p ′ . The join p ∨ p ′ is similarly defined as the finest partition among those that are coarser than p and p ′ . The equivalence relation R p∨p ′ is the transitive closure of the maximum of R p and R p ′ . The least element ⊥ of that lattice is the finest partition, denoted p 0 = (1/2/ • • • /n), in which each object is a cluster. The greatest element ⊤ of (Ω , ) is the coarsest partition denoted p E = (123 • • • n), composed of a single cluster containing the n objects. In this order, each partition precedes every partition derived from it by aggregating two of its clusters. Similarly, each partition covers all partitions derived by subdividing one of its clusters in two clusters.

Figures 3 and4 show examples of partition lattices in the case where E is composed of three and four objects, respectively. The atoms of (Ω , ) are the partitions preceded by p 0 . There are n(n -1)/2 such partitions of n -1 clusters. Atoms are associated to matrices R p with only one off-diagonal entry equal to 1. The co-atoms are dichotomies, i.e., partitions composed of two clusters.

For any partitions p and p of Ω such that p p, the interval [p, p] is defined as:

[p, p] = {p ∈ Ω | p p p}. ( 26
)
It is a particular set of partitions, namely, the set of all partitions finer than p and coarser than p. The set of intervals of the lattice (Ω , ) is: Fig. 4 Lattice of partitions of a four-element set.

I Ω , = {[p, p]|p, p ∈ Ω , p p} ∪ / 0 Ω .
In the lattice (I Ω , , ⊆), the least element ⊥ is / 0 Ω and the greatest element ⊤ is Ω . The atoms are the singletons of Ω . The co-atoms are of the form [p 0 , p] with p a co-atom of (Ω , ), or [p, p E ] with p an atom of (Ω , ). An example of such a lattice, in the case where E is composed of three objects, is shown in Figure 5.

Several forms of imprecise knowledge about a partition can be expressed in (I Ω , , ⊆). For instance, the intervals [p 0 , p] and [p, p E ] represent the set of partitions finer and coarser, respectively, than a given partition p. Suppose now that the elements of a set A ⊆ E are known to belong to the same cluster. This information can be represented by the interval [p A , p E ], where p A denotes the partition in which the only elements that are clustered together are the elements of A:

p A = {A} ∪ {a i }/a i ∈ Ā .

Application to Ensemble Clustering

In [START_REF] Masson | Ensemble clustering in the belief functions framework[END_REF], the above approach was applied to ensemble clustering. The basic strategy can be summarized as follows:

1) Mass generation: Given r clusterers, build a collection of r mass functions m 1 , m 2 ,..., m r on the lattice of intervals (I Ω , , ⊆); the way of choosing the focal elements and allocating the masses from the results of several clusterers depends mainly on the applicative context and on the nature of the clusterers in the ensemble. Fig. 5 Lattice of intervals of the lattice shown in Figure 3.

2) Aggregation: Combine the r mass functions into a single one using Dempster's rule. The result of this combination is a mass function m with focal elements [p k , p k ] and associated masses m k , k = 1, . . . , s. The equivalence relations corresponding to p k and p k will be denoted R k and R k , respectively. 3) Decision making: as for multi-label classification, it is possible to solve a binary integer optimization problem for picking the best partition p with the greatest commonality. However, although theoretically possible, this approach necessitates a too large number of binary variables and renders the approach intractable even for moderate-sized data sets. We have thus proposed another way of making a decision: let p i j denote the partition with n -1 clusters, in which the only objects that are clustered together are objects i and j (partition p i j is an atom in the lattice (Ω , )). Then, the interval [p i j , p E ] represents the set of all partitions in which objects i and j are in the same cluster. Our belief in the fact that i and j belongs to the same cluster can be characterized by the credibility of [p i j , p E ], which can be computed as follows:

Bel i j = bel([p i j , p E ]) = ∑ [p k ,p k ]⊆[p i j ,p E ] m k = ∑ p k p i j m k = s ∑ k=1 m k R k (i, j). ( 27
)
Matrix Bel = (Bel i j ) can be considered as a new similarity matrix and can in turn be clustered using, e.g., a hierarchical clustering algorithm. If a partition is needed, the classification tree (dendogram) can be cut at a specified level so as to insure a userdefined number of clusters.

Example 6

The data set used to illustrate the method is the half-ring data set inspired from [START_REF] Fred | Data clustering using evidence accumulation[END_REF]. It consists of two clusters of 100 points each in a two-dimensional space. To build the ensemble, we used the fuzzy c-means algorithm with a varying number of clusters (from 6 to 11). The six hard partitions computed from the soft partitions are represented in Figure 6. Each hard partition p ℓ (ℓ = 1, . . . , 6) was characterized by a confidence degree α ℓ , which was computed using a validity index measuring the quality of the partition. Considering that the true partition is coarser than each individual one, and taking into account the uncertainty of the clustering process, the following mass functions were defined:

m ℓ ([p ℓ , p E ]) = α ℓ m ℓ ([p 0 , p E ]) = 1 -α ℓ . (28)
The six mass functions (with two focal elements each) were then combined using Dempster's rule. A hierarchy was computed from matrix Bel using Ward's linkage. The dendrogram, represented in the left part of Figure 7, reveals a clear separation in two clusters. Cutting the tree to obtain two clusters yields the partition represented in the right part of Figure 7. We can see that the natural structure of the data is perfectly recovered.

Beliefs on Preorders

In Section 6.1, we presented the lattice of partitions of a finite set, which is isomorphic to the lattice of equivalence relations. We will now introduce a more general lattice of relations, the lattice of preorders, and we will illustrate its interest for aggregating preference relations.

Lattice of preorders

Let E = {a 1 , . . ., a n } be a finite set of n objects. A preorder R on E is a binary reflexive and transitive relation. Preorders are very general relations encompassing partial orders (antisymmetric preorders) and equivalence relations (symmetric preorders) as special cases.

The set Ω of all preorders defined on E can be equipped with the same ordering relation as the one introduced for equivalence relations: a preorder R is said to be finer than a preorder R ′ (we write R R ′ ) if and only if:

R(a i , a j ) ≤ R ′ (a i , a j ) ∀(a i , a j ) ∈ E 2 .
(Ω , ) is a lattice. Note that the lattice of equivalence relations is a sublattice of the lattice of preorders. As for equivalence relations, the minimal element ⊥ in this lattice is represented by a diagonal matrix and the maximal element ⊤ by a matrix with all entries equal to one. As in Section 6.1, the meet and the join of two elements R 1 and R 2 are defined, respectively, as the minimum of R 1 and R 2 , and as the transitive closure of the maximum of R 1 and R 2 . For any two relations R and R such that R R, we can define the interval [R, R], i.e., the set of all preorders coarser than R and finer than R:

[R, R] = {R ∈ Ω |R R R}.
The set of intervals of the lattice (Ω , ) defined by:

I Ω , = {[R, R]|R, R ∈ Ω , R R} ∪ / 0 Ω ,
is also a lattice, endowed with the inclusion relation. This framework will be used in the next section for representing and aggregating partial information regarding the ranking of a set of objects.

Application to Preference Aggregation

It is often desirable, for decision making purposes, to define an order between different alternatives or objects, on the basis of different opinions or preferences provided by decisionmakers. This problem has attracted considerable interest (see, e.g., [START_REF] Owsinski | Preferences, agreement, consensus -measuring, aggregation and control[END_REF][START_REF] Perny | Multicriteria filtering methods based onconcordance and non-discordance principles[END_REF][START_REF] Charon | Lamarckian genetic algorithms applied to the aggregation of preferences[END_REF][START_REF] Gonzales-Pachon | Inferring consensus weights from pairwise comparison matrices without suitable properties[END_REF][START_REF] Charon | An updated survey on the linear ordering problem for weighted or unweighted tournaments[END_REF]). Preferences are often expressed through pairwise comparisons. As explained in [START_REF] Oztürk | Preference modelling[END_REF], comparing two objects a j and a i can be seen as determining which of the four following possible situations holds:

1. Object a i is "before" object a j , where "before" implies some kind of order between a i and a j , induced either by direct preference (a i is preferred to a j ) or by measurements on an associated scale; 2. The converse situation: object a j is "before" object a i ; 3. Object a i is "near" object a j , where "near" can be considered either as indifference (object a i or object a j will do equally well for some purpose), or as a similarity; 4. Objects a i and a j cannot be compared because, for example, of lack of information, high uncertainty, or conflicting information.

A preference relation R = (r i j ) defined on the set of alternatives E is a preorder on E, which encodes the four above situations as follows:

1. Object a i is strictly preferred to a j (a i > a j ) ⇔ r i j = 1 and r ji = 0; 2. Object a j is strictly preferred to a i (a i < a j ) ⇔ r i j = 0 and r ji = 1; 3. Objects a i et a j are indifferent (a i ∼ a j ) ⇔ r i j = 1 and r ji = 1; 4. Objects a i et a j are incomparable (a i <> a j ) ⇔ r i j = 0 and r ji = 0;

The problem addressed here is to derive such a preference relation from the opinions expressed by K agents about pairs of objects. More precisely, we suppose that, for each pair of alternatives {a i , a j }, each agent k has to choose between the four situations described above, and that he is able to quantify his degree of belief in the selected proposition by a value α i jk ∈ [0, 1]. The choice of agent k for any pair {a i , a j } with i < j will be indicated using four binary variables δ (ℓ) i jk , ℓ = 1, 4, using the following convention:

δ (1) i jk = 1 if a i > a j 0 otherwise, (29) δ (2)
i jk = 1 if a i < a j 0 otherwise, (30) δ (3)
i jk = 1 if a i ∼ a j 0 otherwise, (31) δ (4)
i jk = 1 if a i <> a j 0 otherwise. ( 32
)
It is clear that exactly one of these four binary variables is equal to one, i.e., the following equation holds:

4 ∑ ℓ=1 δ (ℓ) i jk = 1.
Let us assume that an agent k has expressed his preference about objects a i and a j by setting the values of the four binary variables δ (ℓ) i jk , ℓ = 1, . . . , 4. This piece of information can be seen as defining a constraint on the underlying preorder R over the set E of objects. To express the set of preorders R compatible with this information, let us introduce two preorders ρ i j and ρ i j on E defined as follows:

ρ i j (a i , a j ) = 1, ρ i j (a k , a l ) = 0 ∀(k, l) = (i, j). and ρ i j (a i , a j ) = 0, ρ i j (a k , a l ) = 1 ∀(k, l) = (i, j).
It is clear that the following equivalences hold:

δ (1) i jk = 1 ⇔ R ∈ I (1) i j = [ρ i j , ρ ji ], δ (2) i jk = 1 ⇔ R ∈ I (2) i j = [ρ ji , ρ i j ], δ (3)
i jk = 1 ⇔ R ∈ I (3) i j = [ρ i j ∨ ρ ji , ⊤], δ (4) i jk = 1 ⇔ R ∈ I (4) i j = [⊥, ρ i j ∧ ρ ji ].
Example 7 Let E be a set composed of three elements. Suppose that an agent has chosen the proposition a 1 > a 2 . Then relation R has to belong to the following interval:

    1 1 0 0 1 0 0 0 1   ,   1 1 1 0 1 1 1 1 1     = [ρ 12 , ρ 21 ],
i.e., all terms of matrix R are free except r 12 = 1 and r 21 = 0.

If the agent has chosen the indifference between a 1 and a 2 , then the relation R is supposed to belong to:

    1 1 0 1 1 0 0 0 1   ,   1 1 1 1 1 1 1 1 1     = [ρ 12 ∨ ρ 21 ; ⊤].
In this case, all terms of matrix R are free except r 12 = r 21 = 1.

The opinion of an agent k may be thus expressed in the lattice (I Ω , , ⊆) of preorder intervals by the following mass assignment (for all i < j):

m i jk (I (ℓ) i j ) = δ (ℓ) i jk α i jk , ℓ = 1, . . . , 4, m i jk ([⊥, ⊤]) = 1 -α i jk . (33)
The opinion given by K evaluators about the n(n -1)/2 pairs of objects may finally be combined into a single mass function m using Dempster's rule:

m = K k=1 i< j m i jk . ( 34
)
Remark 1 The applicability of Dempster's rule is conditioned by the assumption of independence of the sources to be combined. The use of this rule can thus be questioned when combining several pairwise evaluations of a single agent. However, the dependency of these evaluations is not so straightforward, as explained in [START_REF] Tritchler | Modelling the reliability of paired comparisons[END_REF]. Even using unblinded comparisons, when comparing a 1 vs. a 2 and a 2 vs. a 3 , the fact that a 2 is common to both comparisons does not necessarily imply a dependence of the evaluations, unless the expert is employing a notion of transitivity to force his choices to be coherent. The interested reader can refer to [START_REF] Tritchler | Modelling the reliability of paired comparisons[END_REF] for a detailed discussion about this issue. If the independence cannot be assumed, other combinations rules, such as the cautious conjunctive introduced [START_REF] Denoeux | Conjunctive and Disjunctive Combination of Belief Functions Induced by Non Distinct Bodies of Evidence[END_REF], can be used. We may note here that this rule is based on the canonical decomposition of belief functions, which can be computed in any lattice [START_REF] Grabisch | Belief functions on lattices[END_REF]: consequently, it is well defined in the setting considered in this paper (see also [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF]).

The corresponding commonality function q can be computed using (9) in the lattice (I Ω ,≺ , ⊆) as:

q ∝ K ∏ k=1 ∏ i< j q i jk , (35)
where q i jk is the commonality function associated to m i jk .

The commonality of a singleton {R} is equal to:

q({R}) ∝ ∏ k ∏ i< j q i jk ({R}), (36)
with:

q i jk ({R}) = 1 if ∃ℓ such that δ (ℓ) i jk = 1 and R ∈ I (ℓ) i j , 1 -α i jk otherwise. (37)
Equation ( 37) can be simplified by encoding relation R using new variables X (ℓ)

i j for i < j and ℓ = 1, . . . , 4, defined as follows:

           X (1) i j = r i j (1 -r ji ), X (2)
i j = r ji (1r i j ), X

i j = r i j r ji , X

i j = (1 -r i j )(1 -r ji ). (4)
We thus have:

R ∈ I (1)
i j ⇔ r i j = 1 and r ji = 0 ⇔ X

(1)

i j = 1, R ∈ I (2) i j ⇔ r i j = 0 and r ji = 1 ⇔ X (2) i j = 1, R ∈ I (3) i j ⇔ r i j = 1 and r ji = 1 ⇔ X (3) i j = 1, R ∈ I (4) i j ⇔ r i j = 0 and r ji = 0 ⇔ X (4) i j = 1.
With this notation, (37) can be rewritten as:

q i jk ({R}) =      1 if 4 ∑ ℓ=1 δ (ℓ) i jk X (ℓ) i j = 1, 1 -α i jk otherwise. (39)
Maximizing q({R}) is equivalent to maximizing its logarithm, which is equal to:

ln q({R}) = ∑ k ∑ i< j 1 - 4 ∑ ℓ=1 δ (ℓ) i jk X (ℓ) i j ln (1 -α i jk ) + constant. (40)
By eliminating the constant term and permuting the sums, we can see that the optimal relation R maximizing (40) can finally be obtained by solving the following binary integer programming problem: min

X (ℓ) i j ∈{0,1} ∑ i< j 4 ∑ ℓ=1 X (ℓ) i j ∑ k δ (ℓ) i jk ln (1 -α i jk ) (41)
subject to the constraints:

4 ∑ ℓ=1 X (ℓ) i j = 1, ∀i < j (42) r i j + r jk -1 ≤ r ik ∀i = j = k. ( 43
)
Constraints (42) ensure that only one X (ℓ) i j is equal to 1. Constraints (43) ensure the transitivity of the resulting matrix R. Note that constraints (43) can be easily expressed with the unknowns of the problem, since the following relation holds:

r i j = X (1) i j + X (3) i j if i < j, X (2) i j + X (3) i j if i > j. ( 44
)
Example 8 We illustrate our approach using a synthetic example. We generated at random a preorder R * = (r * i j ) on a set E of n = 6 objects. Then, we assumed that a varying number of respondents (from 1 to 35) were asked for their opinion about the 15 pairs of objects. Their evaluation was simulated as follows. For each pair {a i , a j } and each respondent k, a probability p i jk of error was drawn from a beta distribution. Then, the true evaluation was kept with probability 1p i jk , and changed with probability p i jk , a wrong evaluation being uniformly chosen among the three remaining possibilities. The parameters of the beta distribution were varied so as to induce different noise levels in the evaluations (the first parameter of the distribution was set to 20 and the second parameter was chosen in the set {0.5, 2, 5, 10, 15, 18, 20} so that the expectation for the error probability varied between 2% and 50%). Lastly, we assumed that each respondent was able to quantify the error level in his evaluations, so that we fixed α i jk = 1p i jk , ∀i < j and ∀k. The relation R obtained by solving problem (41-43) was compared to the true preorder using the error rate defined as:

e = 2 n(n -1) ∑ i< j 1 r i j =r * i j
The simulation process was repeated 100 times and the results were averaged. They are presented in Figure 8. We can see from the figure that our approach acts as a good denoising process, since, for every noise levels, the error tends to zero as the number of respondents grows. Note that a reduction of error rate is also observed even if only one respondent is considered.

When pooling the opinions of the experts using the linear programming approach (41), it is clear that the internal coherence of each expert is not taken into account. If one wants to take into account the self consistency of each expert, it is possible to use a two-step procedure. The first step consists in assessing the internal coherence of each expert by applying the decision making approach to each preorder and discounting the opinion of the experts according to this coherence. In fact, when the procedure is applied individually to each expert, the maximal value of q({R}) reflects the consistency of the expert: if this value is equal to 1, then the evaluations of the expert are fully consistent. A value less than 1 reflects some conflict in the evaluations of the expert. The maximal commonality values for each expert can thus be used to discount expert opinions, before applying the overall procedure.

Example 9 We illustrate this point using an example inspired from [START_REF] Tritchler | Modelling the reliability of paired comparisons[END_REF]. In a study conducted at the Ontario Cancer Institute, subjects were asked to give their preferences about four scenarios describing ethical dilemmas in health care. The preferences for all six possible scenario pairs were obtained. The experts were also asked to rate the reliability of their evaluations. The preferences for one subject (expert 1) were: -Scenario B is preferred to scenario A with reliability 0.44, -Scenario D is preferred to scenario B with reliability 0.74, -Scenario D is preferred to scenario C with reliability 0.06, -Scenario A is preferred to scenario C with reliability 0.97, -Scenario A is preferred to scenario D with reliability 0.94, -Scenario B is preferred to scenario C with reliability 0.93.

The preference of a subject can be represented by a directed graph in which the vertices are the scenarios and the edges represent the relation "is preferred to". The corresponding graph of expert 1 is given in Figure 9a. The fact that the graph contains a cycle (ADB) shows that the evaluations of expert 1 are not fully consistent. We suppose now that the evaluations of a second subject (expert 2), represented in Figure 9b, are given. This time, there is no cycle in the graph, but the degrees of belief are weaker than for expert 1. Applied individually to each expert, the procedure gives a a commonality of 0.56 for the first expert, and a commonality of 1 for the second expert. If the evaluations are merged directly, one obtains the relation represented in Figure 10a, which is close to the relation given by expert 1 with a correction of transitivity. If the evaluations of the experts are beforehand discounted using one minus the individual commonalities as discounting factors, then the relation represented in Figure 10b with a commonality equal to 0.36 is found, which is the relation given by expert 2.

Conclusion

The exponential complexity of operations in the theory of belief functions has long been seen as a shortcoming of this approach, and has prevented its application to very large frames of discernment. We have shown in this paper that the complexity of the Dempster-Shafer calculus can be drastically reduced, while retaining sufficient expressive power, if belief functions are defined over a suitable subset of the power set equipped with a lattice structure.

When the frame of discernment forms itself a lattice for some partial ordering, the set of events may be defined as the set of intervals in that lattice. Using this method, it is possible to define and manipulate belief functions in very large frames such as the power set of a finite set, the set of partitions of n objects or the set of preorders over a set of alternatives. This approach opens the way to the application of Dempster-Shafer theory to a wide range of computationally demanding tasks in Decision Analysis and Machine Learning.

2 Fig. 6

 26 Fig. 6 Half-rings data set. Individual partitions.

Fig. 7

 7 Fig. 7 Half-rings data set. Ward's linkage computed from Bel and derived consensus.

Fig. 8 Fig. 9

 89 Fig.8Error rate as a function of the number of respondents.

Fig. 10

 10 Fig. 10 Graph representation of the aggregation; (a): without discounting (max q({R}) = 0.11); (b): with discounting (max q({R}) = 0.29).

Table 1

 1 Disjunctive combination of two mass functions m 1 and m 2 on the lattice

  Ω ,≤ , ⊆) and (2 Ω , ⊆), computing the conjunctive sum in any of these two lattices yields the same result, as we have

			3	0.2	0.3	0.06	0.06
	{x,y}	0.3	0	0.6	0.3	0.18	0.12
	{z}	0	0	0	0	0	0
	{x,z}	0.2	0.4	0.3	0.4	0.12	0.12
	{t}	0	0.1	0	0.1	0	0
	{y,t}	0	0.1	0.2	0.5	0.1	0.04
	{z,t} Ω	0 0.2	0 0.1	0 1	0.1 1	0 1	0 0.66
	are identical in (I

Table 2

 2 Disjunctive combination of two mass functions m * 1 and m * 2 on the Boolean lattice (2 Ω ,⊆) with Ω = {x,y,z,t}. Mass functions m * 1 and m * 2 are the extensions of m 1 and m 2 in Table 1. The elements of the lattice I Ω,≤ are preceded by an asterisk.

  Let m 12 = m 1 ⊕ m 2 . We thus get m 12 ([{a, c}, {a, b, c}]) = 0.56, m 12 ([{c}, {a, b, c}]) = 0.24, m 12 ([{a, c}, {a, c}]) = 0.14, m 12 ([{c}, {a, c, d}]) = 0.06. Based on this evidence, we can compute our degrees of belief in the following propositions: Θ , {d}]) = bel 12 ([ / 0 Θ , {a, b, c}]) = 0.56 + 0.14 + 0.24 = 0.94 -Only faults a and c are present: bel 12 ([{a, c}, {a, c}]) = 0.14.

	-Fault a is present:
	bel 12 ([{a},Θ ]) = 0.56 + 0.14 = 0.7
	-Fault d is not present:
	bel 12 ([ / 0
			{a, b, c}]
	0.8	0.56	0.24
	[{c}, {a, c, d}]	[{a, c}, {a, c}]	[{c}, {a, c, d}]
	0.2	0.14	0.06