Thierry Denoeux
email: tdenoeux@utc.fr

Didier Dubois
email: dubois@irit.fr

Henri Prade
email: prade@irit.fr

Representations of Uncertainty in AI: Beyond Probability and Possibility

This chapter completes the survey of the existing frameworks for representing uncertain and incomplete information, started in the previous chapter of this volume. The theory of belief functions and the theory of imprecise probabilities are presented. The latter setting is mathematically more general than the former, and both include probability theory and quantitative possibility theory as particular cases. Their respective knowledge representation capabilities are highlighted.

Introduction

Usually items of information are neither precise nor always coherent with one another. This chapter presents two uncertainty theories that generalize probability theory while being capable of handing incomplete information in an explicit way, by including possibility theory as a special case. There are two ways of building such a generalized framework.

The first idea is to introduce probability theory on top of the basic set-valued representation of incomplete information. Dempster imagined a set equipped with a probability distribution and a one-to-many mapping from this set to a space of interest. Such probabilities can be subjective or frequentist. Upper and lower probabilities are then obtained on the second space. Dempster considered this set-up as an extension of the fiducial paradigm for statistical inference, while Shafer interpreted these upper and lower probabilities as plausibility and belief functions without reference to an underlying probability space with a one-to-many mapping. The approach so-obtained was called theory of evidence by Shafer. It is tailored for the representation and merging of unreliable pieces of evidence. In contrast, upper and lower probabilities in Dempster set-up may also model ill-known probabilities due to incomplete observations of random variables.

The second idea is to work with (convex) sets of probabilities, either because the statistical model is ill-known, or because the usual protocol for generating subjective probabilities is altered, admitting that buying and selling prices of lotteries attached to risky events may differ. The latter is the basis of Walley theory of lower previsions and imprecise probabilities. It turns out that the framework of Walley is mathematically more general than the theory of Dempster-Shafer. This chapter provides an account of these generalizations of Bayesian probability theory.

Theory of Belief Functions

The belief function model [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Shafer | Perspectives in the theory and practice of belief functions[END_REF]Yager and Liu, 2008] adds probabilities on top of the set-based approach to imprecision. It replaces a representation of the form v ∈ A, where A is a set of possible values of v, by a discrete probability distribution over possible statements of the form v ∈ A (assuming the universe, called frame of discernment by Shafer, S is finite). We denote by m such a probability distribution on the power set 2 S of S (the set of all subsets of S). As m is a probability distribution, condition ∑ A⊆S m(A) = 1 is verified. Function m is called a mass function, and m(A) is called the belief mass assigned to subset A. Any subset A of S such that m(A) > 0 is called a focal set of m. We denote by F the family of focal sets. In general, we do not assign any positive mass to the empty set, i.e., we assume that m( / 0) = 0; mass function m is then said to be normalized. However, the Transferable Belief Model (TBM) [START_REF] Smets | The transferable belief model[END_REF] relaxes this constraint: the mass m( / 0) then represents the degree of internal contradiction of the mass function.

In this hybrid representation of uncertainty, it is important to understand the meaning of the mass function. In particular, the belief mass m(A) should not be confused with a probability of occurrence of A. According to [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], m(A) is "the measure of the belief committed exactly to A". More precisely, we can say that m(A) is the probability that the agent only knows that v ∈ A. There is thus an implicit epistemic modality in m(A), which is absent from P(A). This is the reason why function m may be non-monotonic with respect to inclusion: we may have m(A) > m(B) > 0 when A ⊂ B, if the agent is sure enough that what they know is of the form v ∈ A. In particular, m(S) is the probability that the agent does not know anything. The vacuous mass function m ? defined by m ? (S) = 1 thus represents total ignorance. This epistemic interpretation of mass functions is in line with [START_REF] Shafer | Constructive probability[END_REF]'s random code metaphor outlined in the next section.

Random Code Semantics

A mass function can be interpreted by considering that the information provided by a source (a piece of evidence) can be assimilated to a coded message whose meaning is random [START_REF] Shafer | Constructive probability[END_REF]. More precisely, assume that the source sends an encrypted message using a code chosen at random from a set C = {c 1 , . . . , c n } with probabilities p 1 , . . . , p n . We know the set of codes as well as the chances of each code to be selected. If we decode the message using code c i , we get a decoded message of the form v ∈ Γ (c i ) = A i , where Γ is a multivalued mapping from C to 2 S . The probability that the meaning of the original message is v ∈ A is thus

m(A) = ∑ {1≤i≤n:A i =A} p i .
(1)

In particular, the probability that the message is empty, i.e., that it contains no information about v, is m(S). The triple (C, P,Γ ), where P is a probability measure on C, defines a random set [START_REF] Nguyen | An Introduction to Random Sets[END_REF]. The formal equivalence between random sets and belief functions has been proved for the first time by [START_REF] Nguyen | On random sets and belief functions[END_REF]. However, in random set theory, sets A with m(A) > 0 do not necessarily represent states of knowledge. They can be objects taking the form of sets [START_REF] Couso | Random Sets and Random Fuzzy Sets as Ill-Perceived Random Variables[END_REF], contrary to the case of evidence theory illustrated in the following example.

Example: Consider a watch that may be out of order with some known probability ε. The set C describes the set of states of the watch, C = {working, broken}. Assume that the watch shows time h. In that case, the multivalued mapping Γ is Γ (working) = {h} (if the watch is working, it shows the right time), and Γ (broken) = S (if it is out of order, we do not know what time it is). The mass function induced by S is thus m({h}) = 1ε and m(S) = ε.

The mass function obtained in the previous example is said to be simple because the belief mass is shared between a single subset A of S, and S itself. Such a mass function arises when a non-reliable source states that v ∈ A, and the agent believes that the source is irrelevant with probability ε. This probability is committed to S whereas m(A) = 1ε.

This way of generating a mass function from a multivalued mapping was first proposed by Dempster [1967] in the context of statistical inference. [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] renamed the upper and lower probabilities of Dempster plausibility and belief functions, respectively. To quote Shafer [2016b]'s recent intellectual autobiography:

My thought was to surrender the word probability to the objective concept and to build a new subjective theory using mainly the word belief.

A mass function m models a state of knowledge, whereas the underlying triple (C, P,Γ ) represents a piece of evidence with uncertain meaning. Among theories of uncertainty, the theory of belief functions has the particularity of putting emphasis on the evidence that generates a state of knowledge, as shown by the title of [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]'s seminal book: A Mathematical Theory of Evidence.

Basic Set Functions

A mass function m induces two set functions: a belief function Bel (for "belief") and a plausibility function Pl, defined, respectively, by

Bel(A) = ∑ E⊆A,E = / 0 m(E); Pl(A) = ∑ E∩A = / 0 m(E). (2)
Observe that ∀A,

Bel(A) ≤ Pl(A). When m( / 0) = 0, it is clear that Bel(S) = Pl(S) = 1, Pl( / 0) = Bel( / 0) = 0, and Bel(A) = 1 -Pl(A).
Consequently, these two functions are dual, as are necessity and possibility functions. The degree of belief Bel(A) can be interpreted as the probability of provability of A from the available knowledge represented by m. In the language of modal logic, we should write Bel(A) = P( A), where represents the modality of provability [START_REF] Pearl | Reasoning with belief functions: An analysis of compatibility[END_REF]. In the same way, Pl(A) can be seen as the probability of logical consistency of A with m.

Belief functions Bel are completely monotone, i.e., for any k ≥ 2 and any family (A 1 , . . . , A k ) of subsets of S, the following inequality holds,

Bel i=1,...,k A i ≥ k ∑ i=1 (-1) i+1 ∑ I:|I|=i Bel j∈I A j .
(3)

For Shafer [2016b], these inequalities play for belief functions the same role as Kolmogorov axioms for probability theory. Plausibility functions verify a similar property (they are completely alternating), changing the direction of the inequality and switching the ∩ and ∪ operations.

A commonality function

Q(A) = ∑ E⊇A m(E) (4)
was also introduced in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], essentially for computational reasons. It later appeared that the commonality function is an extension of the guaranteed possibility function in possibility theory [START_REF] Dubois | Not impossible" vs. "guaranteed possible" in fusion and revision[END_REF] (see the previous Chapter 3 in this volume). Conversely, knowing function Bel, we can uniquely recover function m by the Möbius transform

m(E) = ∑ A⊆E (-1) |E\A| Bel(A).
Similar identities make it possible to recover m from Pl or Q. The fast Möbius transform [START_REF] Kennes | Computational aspects of the Möbius transformation of graphs[END_REF] can perform these operations efficiently.

Belief functions are often defined on finite universes. Yet, thanks to the formal identity between belief functions and random sets, it is easy to define belief functions on the real line [START_REF] Dempster | Upper and lower probabilities generated by a random closed interval[END_REF][START_REF] Strat | Continuous belief functions for evidential reasoning[END_REF][START_REF] Smets | Belief functions on real numbers[END_REF][START_REF] Denoeux | Extending stochastic ordering to belief functions on the real line[END_REF], or even on more abstract topological spaces [START_REF] Shafer | Allocations of probability: A theory of partial belief[END_REF][START_REF] Shafer | Allocations of probability[END_REF][START_REF] Nguyen | On random sets and belief functions[END_REF][START_REF] Nguyen | An Introduction to Random Sets[END_REF]. We can also extend belief and plausibility functions to fuzzy events [START_REF] Smets | The degree of belief in a fuzzy event[END_REF] by means of Choquet integrals:

Bel(F) = ∑ E⊆S m(E) • min s∈E F(s) (5)
and

Pl(F) = ∑ E⊆S m(E) • max s∈E F(s), (6)
for the finite case. It is also possible to "fuzzify" the theory of belief functions by allowing either the focal sets to be fuzzy sets [START_REF] Zadeh | Fuzzy sets and information granularity[END_REF][START_REF] Yen | Generalizing the Dempster-Shafer theory to fuzzy sets[END_REF], or the belief masses to be intervals or fuzzy numbers [START_REF] Denoeux | Reasoning with imprecise belief structures[END_REF][Denoeux, , 2000a]].

Two Special Cases

Two remarkable special kinds of belief functions are worth noticing:

1. Probability functions are obtained by assuming the focal sets to be singletons.

= F ∈ F , E ⊂ F or F ⊂ E. In that case, Pl(A ∪ B) = max(Pl(A), Pl(B)) and Bel(A ∩ B) = min(Bel(A), Bel(B)).
For instance, a simple mass function, as in the above watch example, yields possibility and necessity measures.

We can associate to m the mapping

ϕ m : S → [0, 1] called contour function of m defined by ϕ m (s) = Pl({s}), i.e., ∀s ∈ S, ϕ m (s) = ∑ s∈E m(E). (7)
It is easy to see that function ϕ m is normalized in the sense of possibility theory (ϕ m (s) = 1 for some state s ∈ S) whenever the focal sets have a nonempty intersection (which is the case if they are nested). Recovering the mass function m from ϕ m is only possible when the focal sets are either nested or disjoint. In particular, if Bel is a probability measure, ϕ m coincides with m and is a probability distribution. Now assume that the focal sets are nested and form an increasing sequence

E 1 ⊂ E 2 ⊂, . . . , ⊂ E n
, where E i = {s 1 , . . . , s i }; then ϕ m is indeed a possibility distribution π, and (7) reduces to π(s i ) = ∑ n j=i m(E j ). The possibility measure Π and the necessity measure N defined from π coincide, respectively, with the plausibility and belief functions induced by m. The mass function can be recomputed from π as follows (with the notation π(s n+1 ) = 0),

m π (E i ) = π(s i ) -π(s i-1 ), i = 1, . . . , n.
(8)

Combination Rules

The combination of information or evidence from different sources plays a fundamental role in the theory of belief functions. The basic tool is Dempster's rule of combination [Dempster, 1967;[START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], which makes it possible to combine independent pieces of information. This tool, as well as the precise definition of independence in this context can be introduced using the random code metaphor introduced in Section 2.1.

Dempster's Rule of Combination

Let m 1 and m 2 be two mass functions on S induced by random sets (C 1 , P 1 ,Γ 1 ) and (C, P 2 ,Γ 2 ), where C 1 and C 2 are, as before, interpreted as sets of codes. Assume both codes are selected independently at random. For each pair (c 1 , c 2 ) ∈ C 1 × C 2 , the probability that c 1 and c 2 are jointly selected is P 1 ({c 1 })P 2 ({c 2 }); we can then deduce that v ∈ Γ 1 (c 1 ) ∩ Γ 2 (c 2 ). If moreover we assume the two bodies of evidence pertain to the same message, we have to restrict to cases where Γ 1 (c 1 ) ∩ Γ 2 (c 2 ) = / 0. Consequently, the joint probability distribution on C 1 ×C 2 should be conditioned on the set

{(c 1 , c 2 ) ∈ C 1 ×C 2 |Γ 1 (c 1 ) ∩ Γ 2 (c 2 ) = /
0}. This line of reasoning leads to the following rule, called Dempster's rule or the product-intersection rule,

(m 1 ⊕ m 2 )(A) = 1 1 -κ ∑ B∩C=A m 1 (B)m 2 (C) (9)
for any A ⊆ S, A = / 0 and (m 1 ⊕ m 2 )( / 0) = 0, where

κ = ∑ B∩C= / 0 m 1 (B)m 2 (C) (10)
is called the degree of conflict between m 1 and m 2 . If κ = 0, the two bodies of evidence are said to be non-conflicting, i.e., each focal set of m 1 intersects all focal sets of m 2 . If κ = 1, the two bodies of evidence are logically contradictory and, consequently, they cannot be combined. Mass function m 1 ⊕ m 2 is called the orthogonal sum of m 1 and m 2 . The unnormalized version of this rule was introduced by Smets [1990a]. A general definition of Dempster's rule in infinite spaces was given by [START_REF] Shafer | Allocations of probability: A theory of partial belief[END_REF]Shafer [ , 2016a].

Dempster's rule is commutative, associative and it admits the vacuous mass function m ? as neutral element. It can be easily computed using the commonality function (4). Denoting by Q 1 , Q 2 and Q 1 ⊕ Q 2 the commonality functions associated, respectively to m 1 , m 2 and m 1 ⊕ m 2 , the following relation holds,

Q 1 ⊕ Q 2 = 1 1 -κ Q 1 • Q 2 . ( 11
)

Dempster's Rule of Conditioning

Conditioning in evidence theory, referred to as Dempster's rule of conditioning, was proposed by [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. It is a special case of Dempster's rule of combination (cf. Section 2.3.1), mass function m being combined with a logical mass function m C such that m C (C) = 1. The idea is to transfer all the mass from each focal set E to E ∩C = / 0, since m C states that the truth lies in C, and to renormalize the obtained result. The new information C can then be viewed as a revision of the original belief function so as to ensure that Pl(C) = 0: the situations in which C is false are now considered as impossible. Denoting by Pl(A C) the revised plausibility, we have

Pl(A C) = Pl(A ∩C) Pl(C) , (12)
which clearly constitutes an extension of probabilistic conditioning. The conditional belief function is then obtained dually as Bel(A C) = 1-Pl(A C). We can remark that, with this rule of conditioning, the size of focal sets decreases: consequently, information becomes more precise, and the intervals [Bel(A), Pl(A)] become narrower (up to the normalization factor). Especially, when Bel(C) = 0 and Pl(C) = 1 (total ignorance about C), conditioning on C by Dempster's rule increases the precision of the resulting mass function. Indeed, Dempster's conditioning corresponds to a revision process leading to information enrichment. Revision is here viewed as the combination between a body of uncertain evidence and a sure piece of information.

Other Combination Rules

Dempster's rule tends to concentrate belief masses on smaller focal sets: it thus has a conjunctive behavior. We can define a disjunctive counterpart to Dempster's rule [START_REF] Dubois | A set-theoretic view of belief functions: Logical operations and approximations by fuzzy sets[END_REF][START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF] as follows,

∀A ⊆ S, (m 1 ∪ m 2 )(A) = ∑ B∪C=A m 1 (B)m 2 (C). (13)
This combination rule assumes that at least one of the two information sources is reliable, contrary to Dempster's rule, which assumes that they both are reliable. The disjunctive rule is commutative, associative, and admits as neutral element the mass function m such m( / 0) = 1. It can be expressed from belief functions using product:

(Bel 1 ∪ Bel 2 ) = Bel 1 • Bel 2 , ( 14
)
which can be compared to (11). Note that the weighted average of belief functions is still a belief function It offers yet another alternative combination rule. The set of belief functions is thus closed under product and weighted average.

Approximations by Reducing the Number of Focal Sets

Both Dempster's rule (9) and its dual disjunctive rule (13) have the effect of increasing the number of focal sets. To avoid combinatorial explosion, a useful strategy is to approximate each mass function by a simpler one with fewer focal sets. Several methods with different degrees of complexity have been proposed for this purpose [START_REF] Lowrance | A framework for evidential-reasoning systems[END_REF][START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF][START_REF] Bauer | Approximation algorithms and decision making in the Dempster-Shafer theory of evidence -an empirical study[END_REF][START_REF] Harmanec | Faithful approximations of belief functions[END_REF][START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF]. The simplest, yet quite effective approach, is the Summarization algorithm [START_REF] Lowrance | A framework for evidential-reasoning systems[END_REF], which works as follows. Let F 1 , . . . , F n be the focal sets of m ranked by decreasing mass, i.e., m(F

1 ) ≥ m(F 2 ) ≥ . . . ≥ m(F n ).
If n exceeds some the maximum allowed number k of focal sets, then the nk focal sets F i , i = k + 1, . . . , n with the smallest masses are replaced by their union, and m is approximated by the mass function m defined as

m (F i ) = m(F i ), i = 1, . . . , k, (15a)
m n i=k+1 F i = n ∑ i=k+1 m(F i ). (15b)
A more sophisticated algorithm for grouping focal sets while minimizing information loss, based on the principle of hierarchical clustering, was proposed by [START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF].

When Equations ( 11) or ( 14) are used, the complexity depends no longer on the number of focal sets, but on the cardinality of the universe S. An efficient approximation algorithm based on the search for a coarsening (grouping of focal sets) minimizing information loss was proposed by [START_REF] Denoeux | Approximating the combination of belief functions using the fast Moebius transform in a coarsened frame[END_REF]. Using a completely different approach, the combination of several belief functions can also be performed by Monte-Carlo simulation (see, e.g., [Moral andWilson, 1994, 1996]).

Conflict Management

The management of conflict between information sources in an important practical problem, which has drawn a lot of attention over the years [START_REF] Lefèvre | Belief function combination and conflict management[END_REF][START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF][START_REF] Martin | General combination rules for qualitative and quantitative beliefs[END_REF][START_REF] Destercke | Toward an axiomatic definition of conflict between belief functions[END_REF]. When a high conflict between pieces of information is detected, two strategies are possible: we can either revise the way information has been formalized, or we can use a robust combination rule yielding a consistent result in case of conflict.

An example of such rule is the [START_REF] Dubois | A set-theoretic view of belief functions: Logical operations and approximations by fuzzy sets[END_REF] rule defined as follows,

(m 1 m 2 )(A) = ∑ B∩C=A m 1 (B)m 2 (C) + ∑ {B∩C= / 0,B∪C=A} m 1 (B)m 2 (C), (16)
for any A ⊆ Ω , A = / 0, and (m 1 m 2 )( / 0) = 0. When the degree of conflict κ between m 1 and m 2 is zero, we get m 1 m 2 = m 1 ⊕ m 2 : in the absence of conflict, the Dubois-Prade rule is equivalent to Dempster's rule. In contrast, when the degree of conflict is equal to 1, we have m 1 m 2 = m 1 ∪ m 2 : in that case, the Dubois-Prade rule boils down to the disjunctive rule. In all other cases, the behavior of the operator is intermediate between conjunctive and disjunctive modes: it is an adaptive combination rule. We can remark that this rule is commutative but it is not associative. However, an n-ary version can easily be defined, based on maximal consistent subsets of focal sets [START_REF] Dubois | A set-theoretic view of belief functions: Logical operations and approximations by fuzzy sets[END_REF]. More complex ways of distributing the conflict among focal sets have been proposed (see, e.g., [START_REF] Lefèvre | Belief function combination and conflict management[END_REF][START_REF] Martin | General combination rules for qualitative and quantitative beliefs[END_REF]). See also Chapter 14 in this volume, for more details on fusion operations.

Combination of Dependent Information

Dempster's rule ( 9) and its disjunctive counterpart (13) both make an independence assumption about the pieces of information to be combined. While it is often possible to break down a body of evidence into independent pieces [Shafer, 2016c], this is not always the case, especially in sensor fusion applications. It is then useful to have a well-justified rule allowing us to combine non independent pieces of evidence.

Such a rule, called the cautious rule, was proposed by [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]. It is based on the weight function representation, which we will now introduce. A mass function m is said to be separable [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] if it the orthogonal sum of simple mass functions (see Section 2.1). Denoting a simple mass function with focal sets A and S as A w(A) , where w(A) is the mass committed to S (so, 1w(A) is committed to A), a separable mass function can thus be written as

m = / 0 =A⊂S A w(A) . ( 17
)
Considering the negation m of a mass function m, defined by ∀A, m = m(A) [START_REF] Dubois | A set-theoretic view of belief functions: Logical operations and approximations by fuzzy sets[END_REF], there is a De Morgan duality between the disjunctive rule ( 14) and the non-normalized variant of Dempster's rule (9) that has been exploited by [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF] to define a disjunctive decomposition of belief functions. Given a separable mass function m with commonality function Q such that m(S) > 0, the weights w(A) can be recovered from Q as

ln w(A) = -∑ B⊇A (-1) |B|-|A| ln Q(B), ∀A ⊂ S, A = / 0. ( 18
)
The mapping w : 2 S \ { / 0, S} → [0, 1] defined by ( 18) is called the weight function associated to m. When m is not separable but still verifies m(S) > 0 (it is then said to be non dogmatic), we can still define the weight function w from ( 18), but we can now have w(A) > 1 for some A [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF]. Mass function m can then still computed from w using (17), where A w(A) with w(A) > 1 is no longer a proper mass function but a generalized mass function assigning "masses" w(A) > 1 to S and 1w(A) < 0 to A.

Given two non dogmatic mass function m 1 and m 2 with weight functions w 1 and w 2 , their orthogonal sum can be written as:

m 1 ⊕ m 2 = / 0 =A⊂Ω A w 1 (A)w 2 (A) ,
i.e., the weight function of m 1 ⊕ m 2 is the product of those of m 1 and m 2 . In contrast, the cautious rule is defined as

m 1 m 2 = / 0 =A⊂Ω A min(w 1 (A),w 2 (A)) , (19)
i.e., the weight function of m 1 m 2 is the minimum of those of m 1 and m 2 . The cautious rule is commutative, associative and idempotent, which makes it suitable to combine dependent pieces of evidence. It can be justified by the Least Commitment Principle (see Section 2.4). A disjunctive counterpart of , called the bold disjunctive rule, can also be defined [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]. With Dempster's rule and the disjunctive rule ( 13), the cautious and bold rules can be seen as particular elements of infinite families of rules based on triangular norms and on uninorms [START_REF] Pichon | The unnormalized Dempster's rule of combination: a new justification from the least commitment principle and some extensions[END_REF]. Other idempotent, but non associative rules have been defined and studied by [START_REF] Destercke | Idempotent conjunctive combination of belief functions: Extending the minimum rule of possibility theory[END_REF] and [START_REF] Cattaneo | Belief functions combination without the assumption of independence of the information sources[END_REF].

Taking Into Account Metaknowledge About Sources

When combining information from several sources, it is often useful to take into account not only the information provided by the sources, but also metaknowledge about their properties (such as their reliability or truthfulness). The discounting operation [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF] makes it possible to account for the reliability of a source by transferring a fraction α of each mass m(A) for A ⊂ S to S. The discounted mass function, denoted by α m, is then given by

α m = (1 -α) m + α m ? ,
where, as before m ? denotes the vacuous mass function and α is called the discount rate. The contextual discounting operation, introduced by Mercier et al [2008], generalizes discounting by allowing one to take into account the source's reliability in different contexts. [START_REF] Pichon | Relevance and truthfulness in information correction and fusion[END_REF] have proposed a very general mechanism for "correcting" and combining mass functions, taking into account the relevance and truthfulness of information sources; they have shown that all connectives of Boolean logic can be interpreted in the light of these two properties. Other belief function correction mechanisms have been proposed by Mercier et al [2012[START_REF] Mercier | Corrigendum to "Belief functions contextual discounting and canonical decompositions[END_REF], and [START_REF] Pichon | Proposition and learning of some belief function contextual correction mechanisms[END_REF].

Imprecision, Specialization and Information Measures

Like any information items, it is interesting to compare belief functions according to their information content. This makes it possible, in particular, to apply the maximum uncertainty ( [START_REF] Klir | Uncertainty-Based Information[END_REF]) or least commitment ( [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF]) principle, which serves the same purpose as the maximum entropy principle in probability theory and the principle of minimal specificity in possibility theory.

According to this principle, when several belief functions are compatible with a set of constraints, the least committed should be selected. In order to apply this principle, we need to define a partial order on the set of belief functions. For that purpose, we may either define a degree of imprecision or of uncertainty of a belief function, or we may adopt a more qualitative approach and directly define an informational ordering relation on the set of belief functions.

Quantitative Approach

As belief functions model both imprecise and uncertain information, we may be willing to measure imprecision and uncertainty separately. A natural measure of imprecision is the expected cardinality of the random set defined by the mass function,

Imp(m) = ∑ E⊆S m(E) • card(E). (20)
It is clear that Imp(m ? ) = card(S), where m ? is the vacuous mass function, and Imp(m) = 1 when m is a probability mass function. It can be checked that Imp(m) = ∑ s∈S Pl({s}). An alternative measure of imprecision is nonspecificity [START_REF] Dubois | A note on measures of specificity for fuzzy sets[END_REF], defined for a normalized mass function m as

N(m) = ∑ E⊆S m(E) log 2 card(E). ( 21
)
Nonspecificity was shown by [START_REF] Ramer | Uniqueness of information measure in the theory of evidence[END_REF] to be the only measure of imprecision satisfying some rationality requirements. The degree of uncertainty of a belief function can be measured by generalizing the well-known Shannon entropy of a probability measure P defined by

H(P) = - card(S) ∑ i=1 p i • ln p i . ( 22
)
Several extensions of H(p) to belief functions have been proposed, of the form

D(m) = -∑ E⊆S m(E) • ln g(E), (23)
where g can be, e.g., Pl or Bel [START_REF] Dubois | Properties of information measures in evidence and possibility theories[END_REF][START_REF] Klir | Uncertainty-Based Information[END_REF].

For g = Pl, we get a measure of dissonance (or internal conflict), which is maxi-mized by uniform probability measures, and reaches its minimum (zero) when the intersection of focal sets is non empty : {E : m(E) > 0} = / 0. For g = Bel, we rather have a measure of confusion, which is minimal (zero) for logical mass functions verifying m(E) = 1 for some unique focal set E (imprecise but certain and clear information), but high for uniform mass functions over subsets of S with cardinality Card(S)/2 [START_REF] Dubois | Extremal properties of belief measures in the theory of evidence[END_REF]. See also [START_REF] Ramer | Measures of discord in the Dempster-Shafer theory[END_REF][START_REF] Klir | Uncertainty-Based Information[END_REF].

Another approach, proposed by [START_REF] Smets | Information content of an evidence[END_REF], is to define a measure I of information content that relies on the pivotal role of Dempster's rule in the theory of belief functions, namely, it is natural to impose an additivity property with respect to this rule, such as I(m 1 ⊕ m 2 ) = I(m 1 ) + I(m 2 ) for any two non-conflicting mass functions m 1 and m 2 . As shown by [START_REF] Smets | Information content of an evidence[END_REF], this requirement, together with a few additional natural conditions, lead to the following definition:1

I(m) = -∑ E⊆S ln Q(E). ( 24
)
Other quantitative criteria attempt to measure imprecision and uncertainty simultaneously. For instance, aggregate uncertainty [START_REF] Maeda | An uncertainty measure with monotonicity under the random set inclusion[END_REF][START_REF] Harmanec | Measuring total uncertainty in Dempster-Shafer theory: A novel approach[END_REF]] is defined as follows, for a normalized mass function m:

AU(m) = max P∈P(m) H(P), ( 25
)
where H is the Shannon entropy, and P(m) is the set of probability measures on S compatible with m:

P(m) = {P, P(A) ≤ Pl(A), ∀A ⊆ S}. ( 26
)
It is clear that AU(m) is maximal both for the vacuous mass function m = m ? and for the uniform Bayesian mass function m such that m({s}) = 1/card(S) for all s ∈ S; these two mass functions correspond, respectively, to maximal imprecision and to maximal uncertainty. Aggregate uncertainty can be shown to meet a number of reasonable requirements [START_REF] Klir | Uncertainty-Based Information[END_REF]. However, the debate on what should be a "natural" measure of total uncertainty in the theory of belief functions is not settled: see, for instance, the recent proposal and discussion by [START_REF] Jiroušek | Entropy of belief functions in the dempster-shafer theory: A new perspective[END_REF].

Comparative Approach

The second approach to comparing the informational contents of belief functions consists of directly defining a partial order on the set of belief functions. Given two normalized mass functions m 1 and m 2 , m 1 is said to be more precise than m 2 (denoted by m 1 Pl m 2 ) iff, for any subset A of S, the interval

[Bel 1 (A), Pl 1 (A)] is included in the interval [Bel 2 (A), Pl 2 (A)].
Because of the duality of Bel and Pl, this condition can be simplified to: ∀A, Pl 1 (A) ≤ Pl 2 (A). In term of imprecise probabilities, the condition m 1 Pl m 2 means that P(m 1 ) is a subset of P(m 2 ) [START_REF] Dubois | A set-theoretic view of belief functions: Logical operations and approximations by fuzzy sets[END_REF][START_REF] Yager | The entailment principle for Dempster-Shafer granules[END_REF]. Mass function m is thus maximally precise when it coincides with a single probability measure, and minimally precise if m = m ? . It is also clear that, if m 1 Pl m 2 , then AU(m 1 ) ≤ AU(m 2 ). Note that this approach is in agreement with the imprecise probability interpretation of belief functions.

An alternative method for comparing the informativeness of belief functions consists in generalizing relative specificity, viewed as set inclusion, to random sets. A normalized mass function m 1 is a specialization of a normalized mass function m 2 (denoted by m 1 s m 2 ) if and only of the following three conditions hold:

1. Any focal set of m 2 contains at least one focal set of m 1 ; 2. Any focal set of m 1 is included in at least one focal set of m 2 ; 3. There exists a stochastic matrix W whose element w i j is the proportion of the mass m 1 (E i ) assigned to

F j ⊇ E i in order to reconstruct mass m 2 (F j ), i.e., m 2 (F j ) = ∑ i w i j • m 1 (E i ).
This relation is stronger than the previous one: if m 1 is a specialization of m 2 , then m 1 is also more precise than m 2 (but the converse is not true in general, see [START_REF] Dubois | A set-theoretic view of belief functions: Logical operations and approximations by fuzzy sets[END_REF]). It is also obvious that, if m 1 is specialization of m 2 , then Imp(m 1 ) ≤ Imp(m 2 ).

As noted in Section 2.2, in the consonant case, m π and π contain the same information, i.e., Pl = Π and Bel = N. Accordingly, for possibility measures, the precision and specialization orderings both coincide with the specificity ordering for possibility distributions: [START_REF] Dubois | A set-theoretic view of belief functions: Logical operations and approximations by fuzzy sets[END_REF].

m π 1 is a specialization of m π 2 iff Π 1 (A) ≤ Π 2 (A), ∀A ⊆ S iff π 1 (s) ≤ π 2 (s), ∀s ∈ S [
Other informational orderings have been proposed. For instance, m 1 is said to be more informative than m 2 according to commonalities (denoted by [START_REF] Dubois | A set-theoretic view of belief functions: Logical operations and approximations by fuzzy sets[END_REF][START_REF] Yager | The entailment principle for Dempster-Shafer granules[END_REF]. This property can be interpreted from Eq. ( 11): as numbers Q 1 (A) get closer to 1, the influence of m 1 when combined by Dempster's rule with another mass function m 2 becomes smaller, which means that m 1 becomes less informative. Relation Q is weaker than s , but it is not comparable with Pl . Obviously, m 1 Q m 2 implies that I(m 1 ) ≥ I(m 2 ).

m 1 Q m 2 ) iff Q 1 ≤ Q 2 [
Yet another ordering relation was proposed by [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF], based on the weight function (18). Mass function m 1 is said to be more informative than m 2 according to the weights (denoted by m 1 w m 2 ) iff w 1 ≤ w 2 . This means that m 1 is the orthogonal sum of m 2 and a separable mass function m that has no conflict with m 2 : m 1 = m 2 ⊕ m. The cautious rule (19) can be derived from the least commitment principle based on relation w .

Criteria for Decision Under Uncertainty

Consider a set A = {a 1 , . . . , a r } of acts, a set S = {s 1 , . . . , s n } of states of nature, and a payoff matrix U of size r × n, whose element u i j is the utility of choosing act a i if state s j occurs. Assuming the uncertainty about the state of nature to be modeled by a mass function m on S, which act should be chosen? To answer this question, the classical Maximum Expected Utility (MEU) principle [START_REF] Von Neumann | Theory Games and Economic Behavior[END_REF]] can be generalized in a number of ways in the belief function setting (see also Chapter 17 in this volume).

Lower and Upper Expected Utilities

According to Dempster [1967] and [START_REF] Shafer | Constructive probability[END_REF], the lower and upper expected utilities of act a i are defined, respectively, as the following Choquet integrals (further studied in Chapter 17 of this volume) similar to (5):

EU(a i ) = ∑ E⊆S m(E) min s j ∈E u i j (27a) EU(a i ) = ∑ E⊆S m(E) max s j ∈E u i j . (27b)
The lower and upper expected utilities can be shown to be, respectively, the lower and upper bounds of the expected utility with respect to all probability measures P on S compatible with m [START_REF] Shafer | Constructive probability[END_REF]. An optimistic decision-maker (DM) will typically maximize the upper expected utility, while a pessimistic DM will maximize the lower expected utility. These two decision rules can be generalized by considering a convex sum of the lower and upper expected utility [START_REF] Jaffray | Linear utility theory for belief functions[END_REF][START_REF] Strat | Decision analysis using belief functions[END_REF], which generalizes Hurwicz criterion (see Chapter 17 in this volume for a detailed discussion of its aximatization due to Jaffray):

EU α (a i ) = ∑ E⊆S m(E) α min s j ∈E u i j + (1 -α) max s j ∈E u i j (28a) = αEU(a i ) + (1 -α)EU(a i ), (28b)
where α can be seen as a pessimism index. An even more general approach, proposed by [START_REF] Yager | Decision making under Dempster-Shafer uncertainties[END_REF], combines the utilities in each set {u i j | s j ∈ E} by an Ordered Weighted Average (OWA) operator.

Pignistic Probability

Following a different line of reasoning and putting emphasis on the avoidance of Dutch books (i.e., sequences of bets ensuring a sure loss), Smets [1990b] advocated a two-level mental model: the credal level, where uncertainty is represented by a belief function, and the pignistic level, where belief functions are transformed to probabilities for decision-making. The pignistic transformation [Smets, 1990b] consists in distributing each mass m(E) equally to all elements of E, resulting in the probability distribution betp defined as

betp(s) = ∑ E:s∈E m(E) card(E) . ( 29
)
This transformation had been earlier proposed by [START_REF] Dubois | A class of fuzzy measures based on triangular norms. a general framework for the combination of uncertain information[END_REF] as a generalization of Laplace's principle of insufficient reason to belief functions. Smets [1990b] justified it axiomatically, by imposing a linearity property (the pignistic probability of a convex sum of belief functions should be the convex sum of the pignistic probabilities) and an anonymity property (the pignistic probability of an event E should not change after permuting the elements of E). In fact, the pignistic probability was already known in the theory of cooperative games since the 1950's as the Shapley value, and Smets' axioms are mathematically the same as those proposed by [START_REF] Shapley | A value for n-person games[END_REF], albeit in a different context. The pignistic probability is also the center of gravity of the convex set of probabilities that dominate the belief function.

We can also search for the least informative belief function, according to the commonality ordering Q defined in Section 2.4.2, corresponding to a given pignistic probability distribution. As shown by [START_REF] Dubois | A definition of subjective possibility[END_REF], it is unique and consonant; consequently, it induces a possibility distribution.

Having defined the pignistic distribution betp, we can evaluate each act a i by its expected utility with respect to betp,

EU betp (a i ) = ∑ s j ∈S betp(s j )u i j = ∑ E⊆S m(E) 1 card(E) ∑ s j ∈E u i j , (30)
which can be compared to ( 27) and (28a). The pignistic criterion is a special case of Yager's OWA criterion [START_REF] Yager | Decision making under Dempster-Shafer uncertainties[END_REF], as the average is a particular OWA operator.

Applications to Statistical Learning and Data Analysis

In Artificial Intelligence, the theory of belief functions has been used, until the early 1990's, to model uncertainty in expert systems [START_REF] Shafer | Probability judgment in artificial intelligence and expert systems[END_REF][START_REF] Shenoy | A valuation-based language for expert systems[END_REF]. Since the 1990, we have seen the development of another application area: statistical learning (see Chapter 12 of Volume 2). The theory of belief functions has proved to be an efficient formalism for combining models, modeling uncertainty in the outputs of classifiers or clustering algorithms, and learning from uncertain data. In the following, we review some of the recent developments in this area.

Classifier Combination

A first way of applying the theory of belief functions to classification is to consider classifier outputs as items of evidence and to merge them using Dempster's rule, or any other combination rule (see Section 2.3). Given the flexibility of the belief function formalism, this approach can be applied to classifiers of various types, the outputs of with can be converted into belief functions.

For instance, [START_REF] Xu | Methods of combining multiple classifiers and their applications to handwriting recognition[END_REF] proposed to use a confusion matrix to convert a classifier's decision into a mass function. They obtained good results for a handwriting recognition problem. A similar approach was used by [START_REF] Mercier | Decision fusion for postal address recognition using belief functions[END_REF] for postal address recognition. More recently, [START_REF] Bi | The combination of multiple classifiers using an evidential reasoning approach[END_REF] proposed to represent classifier scores as "triplet" mass functions with three focal sets. [START_REF] Bi | The impact of diversity on the accuracy of evidential classifier ensembles[END_REF] studied the influence of classifier diversity and the combination rule on the accuracy of the ensemble. [START_REF] Quost | Classifier fusion in the Dempster-Shafer framework using optimized t-norm based combination rules[END_REF] considered a parametrized family of combination rules, including Dempster's rule and the cautious rule (see Section 2.3.6), and proposed a method to find the best rule in this family.

From a different perspective, [START_REF] Quost | Pairwise classifier combination using belief functions[END_REF] considered the combination of binary classifiers as a way to solve multi-class classification problems. For instance, in the "one-against-one" approach, binary classifiers are trained using data from only two classes; consequently, their outputs can be interpreted as conditional mass functions. The problem is then to construct an unconditional mass function on the whole set of classes, as consistent as possible with the conditional mass functions provided by the binary classifiers.

Evidential Classifiers

An evidential classifier is a classifier whose output is a mass function over a set of classes Ω = {ω 1 , . . . , ω c }. Two main approaches have been proposed for constructing such a classifier from training data.

The first approach, first introduced and justified axiomatically by [START_REF] Appriou | Probabilités et incertitude en fusion de données multi-senseurs[END_REF][START_REF] Appriou | Uncertain data aggregation in classification and tracking processes[END_REF], is to construct a mass function m on Ω from the likelihoods p(x|ω k ), where x is the feature vector. One of the two methods proposed by Appriou is identical to the solution resulting from the application the Generalized Bayes Theorem (GBT) introduced by [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF]. The mass function has the following expression:

m = c k=1 {ω k } α k p(x|ω k ) , (31)
where the α k 's are coefficients ensuring that α k p(x|ω k ) ≤ 1 for k = 1, . . . , c, and the notation A w stands for the simple mass function µ such that µ(A) = 1w and µ(Ω ) = w (see Section 2.3.6). A major advantage of this method is that it can be used without prior class probabilities, or with only weak prior information encoded as a belief function. However, when prior probabilities are given, the GBT yields the same solution as the Bayesian approach. [START_REF] Appriou | Probabilités et incertitude en fusion de données multi-senseurs[END_REF] showed the robustness of this method, in particular when the test data distribution differs from the learning distribution due, e.g., to different data acquisition methods or to sensor malfunction. Another approach, referred to as the evidential k-nearest neighbor (NN) rule, was introduced by [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF]. It consists in considering each training instance (or only each of the k nearest instances in the training set) as a piece of evidence about the class of the new object to be classified. The different pieces of evidence are represented by mass functions and are combined using Dempster's rule. In the most general form of this method, we consider a training set 1) , m (1) ), . . . , (x (N) , m (N) ), where x (i) is the feature vector of instance i and m (i) is a mass function on Ω representing partial knowledge about the class of that example. In the fully supervised case, each mass function m (i) is certain, i.e., we have m (i) ({ω j }) = 1 for some element ω j of Ω . In the general case, we have a partially supervised learning problem. Partial knowledge about the class of training instances may be provided by an expert or derived from indirect observation. We also assume a distance or dissimilarity measure δ between feature vectors.

L = {(x (
The mass function representing the evidence of the training example e (i) = (x (i) , m (i) ) is defined as

m(A | e (i) ) = ϕ δ (x, x (i) ) m (i) (A), ∀A ⊂ Ω (32a) m(Ω | e (i) ) = 1 -∑ A⊂Ω m(A|e (i) ), (32b)
where ϕ is a decreasing function verifying ϕ(0) ≤ 1 and lim d→∞ ϕ(d) = 0. Mass function m(•|e (i) ) is thus obtained by discounting m (i) (see Section 2.3.7), with a discount rate that gets closer to one when the dissimilarity between vectors x and x (i) goes to infinity. The condition lim d→∞ ϕ(d) = 0 ensures that mass function m(•|e (i) ) becomes vacuous when the dissimilarity between vectors x and x (i) goes to infinity.

Let us now consider a new object described by a known feature vector x and an unknown class label y ∈ Ω . Having computed mass functions (32) for each of the K nearest neighbors of x, the combined mass function on Ω is

m(• | L ) = {i|x i ∈N K ( x)} m(• | e (i) ), (33)
where N K ( x) denotes the set of the K nearest neighbors of x. The choice of a best class ŷ ∈ Ω can then be made using one of the decision rules described in Section 2.5 and in Chapter 17 of this volume. [START_REF] Denoeux | Analysis of evidence-theoretic decision rules for pattern classification[END_REF] describes several decision strategies with different reject options. [START_REF] Zouhal | An evidence-theoretic k-NN rule with parameter optimization[END_REF] have proposed a method for choosing function ϕ within a parametric family by minimizing an error function. The evidential neural network classifier introduced by Denoeux [2000b] is a variant of this method, in which the training set is summarized as a set of prototypes. Both the evidential k-NN rule and the evidential neural network classifier have been implemented in the R package evclass [START_REF] Denoeux | evclass: Evidential Distance-Based Classification[END_REF]. [START_REF] Denoeux | Handling possibilistic labels in pattern classification using evidential reasoning[END_REF] have studied another variant of the evidential k-NN rule in which partial information about the class of training instances is given as possibility distributions. Petit-Renaud and Denoeux [2004] have extended the approach to regression problems, where variable y is numerical. Recently, [START_REF] Lian | An evidential classifier based on feature selection and two-step classification strategy[END_REF] proposed a feature selection method based on the evidential k-NN rule, and [START_REF] Lian | Dissimilarity metric learning in the belief function framework[END_REF] described an algorithm for learning the distance function δ in (32).

The evidential k-NN rule has also been extended to multi-label classification problems, in which each object may belong simultaneously to several classes [START_REF] Denoeux | Representing uncertainty on set-valued variables using belief functions[END_REF]. In this case, the universe is the power set 2 Ω of the set of classes. To prevent double exponential complexity in the manipulation of mass functions, belief functions can then be defined on a lattice of subsets of Ω (the intervals with respect to the ordering relation ⊆). A general presentation of this approach (with applications not only to classification, but also to preference elicitation and to clustering) can be found in [START_REF] Denoeux | Evidential reasoning in large partially ordered sets. application to multi-label classification, ensemble clustering and preference aggregation[END_REF]. See also [START_REF] Grabisch | Belief functions on lattices[END_REF] for the general theory of belief functions on lattices.

The likelihood-based and distance-based evidential classification methods outlined above have been compared experimentally by [START_REF] Fabre | Presentation and description of two classification methods using data fusion based on sensor management[END_REF], and theoretically by [START_REF] Denoeux | Classification using belief functions: the relationship between the case-based and model-based approaches[END_REF], who showed that they can both be derived from the GBT.

Evidential Clustering

The theory of belief functions has also been applied to clustering, which consists in finding groups (or clusters) in data (see Chapters 12 and 14 of Volume 2). Here, belief functions can be used to quantify the uncertainty about the group membership of each particular object. Given a set of n objects O = {o 1 , . . . , o n } and a set of c clusters Ω = {ω 1 , . . . , ω c }, [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] defined a credal partition as an n-tuple M = (m 1 , . . . , m n ) of (not necessarily normalized) mass functions on Ω , where m i quantifies the uncertainty about the cluster membership of object o i . A credal partition boils down to a hard partition when all mass functions are precise (i.e., when they focus on only one singleton). Most other "soft" clustering notions such as fuzzy, possibility and rough clustering are also recovered as special cases [Denoeux and Kanjanatarakul, 2016]. For instance, if all mass functions correspond to probability distributions (i.e., their focal sets are singletons), then we can identify each mass m i ({ω k }) with the degree of membership u ik of object o i to cluster ω k , and we have a fuzzy partition [START_REF] Bezdek | Pattern Recognition with fuzzy objective function algorithm[END_REF]. If each mass function m i is categorical (i.e., it has only one focal set A i ), then we can define the lower approximation of cluster ω k as the set of objects o i that surely belong to ω k , i.e., such that A i = {ω k }, and the upper approximation of cluster ω k as the set of objects o i that may belong to ω k , i.e., such that ω k ∈ A i . We then have a rough partition as defined by [START_REF] Lingras | Applying rough set concepts to clustering[END_REF]. A general credal partition can also easily be summarized into a hard partition or any type of soft partition. For instance, we obtain a fuzzy partition by replacing each mass m i by its pignistic probability distribution (29), and we get a rough partition by selecting, for each mass function m i , the focal set with the largest mass [Denoeux and Kanjanatarakul, 2016].

An evidential clustering algorithm is a procedure that constructs a credal partition from a dataset. Several such algorithms have been proposed over the years:

• The EVCLUS algorithm, introduced in [Denoeux and [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF], applies ideas from multidimensional scaling to clustering: given a dissimilarity matrix, it finds a credal partition such that the degrees of conflict (10) between mass functions match the dissimilarities, dissimilar objects being represented by highly conflicting mass functions; this is achieved by iteratively minimizing a stress function. A variant of EVCLUS allowing one to use prior knowledge in the form of pairwise constraints was later introduced in [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF], and several improvements to the original algorithm making it capable of handling large dissimilarity datasets have been reported in [Denoeux et al, 2016] and [START_REF] Li | k-cevclus: Constrained evidential clustering of large dissimilarity data[END_REF]]. • The Evidential c-means (ECM) algorithm [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF] is a cmeans-like algorithm that minimizes a cost function by searching alternatively the space of prototypes and the space of credal partitions. Unlike the hard and fuzzy c-means algorithms, ECM associates a prototype not only to each cluster, but also to each nonempty set of clusters. The prototype associated to a set of clusters is defined as the barycenter of the prototypes of each single cluster in the set. The cost function to be minimized insures that objects close to a prototype have a high mass assigned to the corresponding set of clusters. A variant with adaptive metrics and binary constraints was introduced in [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF], and a relational version for dissimilarity data (called RECM) has been proposed in [START_REF] Masson | RECM: relational evidential c-means algorithm[END_REF]. A version of ECM taking into account spatial constraints and suitable for image segmentation was introduced by Lelandais et al [2014]. • The Ek-NNclus algorithm [START_REF] Denoeux | EK-NNclus: a clustering procedure based on the evidential k-nearest neighbor rule[END_REF]] is a decision-directed clustering procedure based on the evidential k-NN rule described in Section 2.6.2. Starting from an initial partition, the algorithm iteratively reassigns objects to clusters using the evidential k-NN rule, until a stable partition is obtained. After convergence, the cluster membership of each object is described by a mass function on Ω assigning a mass to each cluster and to the whole set of clusters. The mass assigned to the set of clusters can be used to identify outliers. The procedure can be seen as searching for the most plausible partition of the data.

All these algorithms have been implemented in the R package evclust [START_REF] Denoeux | evclust: Evidential Clustering[END_REF].

Imprecise Probabilities

Imprecise probability theory [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF] relies on an approach opposite to the one of belief functions. Instead of randomizing the set-based approach to incomplete information, incompleteness is injected in probability theory. Under the frequentist view, epistemic uncertainty goes on top of a probabilistic model. Under the subjectivist view, the betting protocol is relaxed, by no longer enforcing the equality between buying and selling prices. In the area of economics, [START_REF] Gilboa | Maxmin expected utility with a non-unique prior[END_REF] already showed that by suitably relaxing Savage axioms for decision under uncertainty, it is possible to formally justify the idea that an agent's epistemic state consists of a set of probability distributions on the set S of possible states of the world: in order to hedge against uncertainty, when evaluating a decision, the cautious agent picks the probability distribution that minimizes its expected utility.

Basic Definitions and Interpretations

An imprecise probability model comes down to specifying a family P of probability functions over S. However, there are several approaches to come up with this family according to the understanding of probability (frequentist or subjectivist), and to the available data in the specific application context.

Incomplete Information About Frequentist Probability

Under a frequentist view, P is an epistemic set reflecting incomplete information about an otherwise precise mathematical model of a random process: a probability distribution in P is the right one. The family P thus represents an imprecise probabilistic model. There are several situations that lead to such a model:

• The most common situation is when several probability measures are compatible with the available information, for instance in the case of scarce data. In the parametric case, the parameters of the model are ill-known, because the confidence intervals for these parameters are too wide. Bayesians then often assume a prior probability distribution on the parameter range or the set of possible probability functions. This is precisely what is not assumed in the imprecise probability setting. Some authors may still use the Bayesian paradigm, but assume imprecision about the prior probability (they are called robust Bayesians [START_REF] Huber | Robust statistics[END_REF][START_REF] Berger | An overview of robust Bayesian analysis[END_REF]), resulting in an imprecise posterior distribution. • Imprecise information can be obtained by an expert or from empirical data about statistical parameters (like support, mean, mode, median, some fractiles) but the type of probabilistic model is otherwise ill-known [Baudrit and Dubois, 2006] (e.g., you know the empirical mean and variance but you do not know if the process is Gaussian or not). It may be that the expert provides probability bounds on some events (intervals, quantiles, etc.). In the finite case, an expert may assign a probability interval to each outcome instead of a precise value [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF]]. • A usual setting for getting upper and lower probabilities is the one of imprecise statistical information, that corresponds to Dempster [1967]'s setting for belief functions. The mass value of a focal set is the frequency of observing this incomplete information item. In that case, belief and plausibility functions are lower and upper probabilities, respectively, with a frequentist flavor. See the book by [START_REF] Couso | Random Sets and Random Fuzzy Sets as Ill-Perceived Random Variables[END_REF] for a presentation of this approach to imprecise statistics. • Some authors have even questioned the basic assumptions that frequencies converge toward limit probabilities. For instance it is only known that frequencies eventually remain inside an interval [START_REF] Walley | Towards a frequentist theory of upper and lower probability[END_REF].

Suppose one comes up to a probability family P via some of the above scenarii. Then one can assign to each event lower and upper bounds for the probability of this event [START_REF] Smith | Consistency in statistical inference and decision[END_REF]:

P * (A) = inf P∈P P(A); P * (A) = sup P∈P P(A). ( 34
)
Functions P * and P * are monotonic with respect to inclusion and satisfy the duality property P * (A) = 1 -P * (A). We call set functions P * and P * lower and upper envelopes respectively, after [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]. The additivity property of P enforces the following conditions for such envelopes [START_REF] Good | Subjective probability as the measure of a non-measurable set[END_REF] When this interval reduces to a singleton, full probabilistic knowledge is obtained. Probability envelopes are more general than belief and plausibility functions, hence more general than necessity and possibility measures [START_REF] Chapman | Measures of uncertainty in expert systems[END_REF].

It is important to notice that in general, it is impossible to reconstruct the original set P from the knowledge of these intervals [P * (A), P * (A)] for all events A. Indeed, these intervals correspond to particular projections of P. Namely, let P(P * ) = {P : ∀A ⊆ S, P(A) ≥ P * (A)}, it is easy to see that P(P * ) is convex (if P 1 ∈ P(P * ) and P 2 ∈ P(P * ) then, ∀λ ∈ [0, 1], λ • P 1 + (1λ ) • P 2 ∈ P(P * )) and contains the convex hull of P even if P and P(P * ) have the same upper and lower envelopes.

A characteristic property of an upper envelope (induced by a non-empty set of probabilities) was found by [START_REF] Giles | Foundations for a theory of possibility[END_REF]. Viewing a set A as its {0, 1}-valued characteristic function (A(s) = 1 if s ∈ A and 0 otherwise). A set-function g is an upper envelope if and only if for any tuple A 0 , A 1 , . . . , A k of subsets of S, and any pair of positive integers (r, s)

such that ∑ k i=1 A i (•) ≥ r + s • A 0 (•), it holds that k ∑ i=1 g(A i ) ≥ r + s • g(A 0 ). (36)

The Subjectivist Point of View

The subjectivist approach to imprecise probability was fully developed by [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]. It is powerful enough to encompass all convex sets of probabilities. In this approach the agent proposes buying prices for gambles. A gamble is a function f from S to the real line that expresses losses ( f (s) < 0) or gains ( f (s) > 0). The gamble associated to an event is its characteristic function. The agent is not committed to selling such gambles at the same prices as the ones he or she accepts to buy them.

Informally, the approach relies on so-called desirable gambles [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF] that the agent would agree to buy for a positive price. The set of desirable gambles contains at least all positive gambles. Moreover the sum of two desirable gambles is desirable, and a desirable gamble remains desirable when multiplied by a positive constant. The lower prevision LP( f ) of a gamble f is the maximal value α such that fα is desirable. It can be shown that given a set of gambles f i ∈ G and their lower previsions LP( f i ), there is a convex set of probabilities P, called credal set, such that LP( f i ) is the lower expectation of f i according to P, for all f i ∈ G . One important point is that any convex set of probabilities can be represented by lower previsions on some family of gambles.

In this setting, the upper prevision UP( f ) of a gamble f is provably equal to -LP(f ). The value LP( f ) is thus the maximal buying price for a gamble f , and the upper prevision UP( f )(≥ LP( f )) is the minimal selling price of f . If the credal set attached to a set of gambles and its lower previsions is empty, then the proposal is inconsistent and the agent incurs a sure loss after buying and resolving these gambles. Moreover, due to the interaction between gambles, it may be that the consistent buying prices proposed by the agent for gambles f i ∈ G are too low and could be raised without altering the credal set. A set of buying prices pr( f i ), f i ∈ G is said to be coherent if and only if LP( f i ) = pr( f i ), ∀ f i ∈ G . In other words, letting E P ( f ) be the expectation of f with respect to probability P, a set of buying prices for a set of gambles G is coherent if and only if for any f i ∈ G , inf{E P ( f i ) : P ∈ P} = pr( f i ), where P is the credal set induced by the gambles f i ∈ G , and their buying prices. Clearly, Giles condition (36) is easily interpreted in terms of coherence of gambles. It expresses the coherence of a set of upper probabilities assigned to subsets of S (minimal selling prices of 0-1 gambles), protecting an agent who sells k + 1 lottery tickets corresponding to events A 0 , A 1 , . . . , A k from losing money while proposing optimal selling prices g(A i ).

The gamble approach leads to a decision rule that is specific to the imprecise probability setting, namely a gamble f is preferred to a gamble g if and only the gamble h = fg is desirable, i.e., if the lower expectation of the latter gamble with respect to the corresponding credal set P is positive. It gives a partial ordering on gambles. It implies that ∀P ∈ P, E P ( f ) ≥ E P (g). See Chapter 17 in this volume for other decision rules with credal sets

Special Cases

A monotonic set-function g : 2 S → [0, 1] is said to be a Walley-coherent lower probability if the following property holds:

g(A) = inf{P(A) : P(A) ≥ g(A), ∀A ⊆ S}.
In that case, the credal set P = {P : P(A) ≥ g(A), ∀A ⊆ S} is characterized by the set-function g, that is, it can be described by assigning optimal buying prices to events (viewed as 0-1 gambles) only. Mind that not all credal sets can be characterized in this way. They generally require the assignment of buying (or selling) prices to general gambles. A sufficient condition for a monotonic set function to be Walleycoherent is the supermodularity condition: g(A ∪ B) + g(A ∩ B) ≥ g(A) + g(B). Such a function g is a called a convex capacity. So it is clear that other set-functions met in this chapter and the previous one are Walley-coherent as well, such as belief functions (equivalently plausibility functions) and necessity measures (equivalently possibility measures), which can represent specific credal sets.

Interestingly, Walley-coherence can be viewed as a generalization of deductive closure to families of weighted propositions. Let K be a consistent set of propositions A 0 , A 1 , . . . , A k , and suppose we assign the buying prices pr(

A i ) = 1, i = 0, ...k, then P * (A) = 1 if and only if K |= A.
More about imprecise probability theories can be found in [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]'s book and their relevance for uncertainty management in artificial intelligence is discussed in [START_REF] Chapman | Measures of uncertainty in expert systems[END_REF], where the position of belief functions and possibility measures in the landscape is pointed out. More recent books on the topics are the collection of introductory papers edited by Augustin et al [2014], and the mathematically oriented monograph on lower previsions by de [START_REF] De Cooman | Upper and lower probabilities induced by a multivalued mapping[END_REF].

Two Types of Conditioning

In the framework of imprecise probabilities, there are several ways of extending the Bayesian conditioning of probability theory. It reflects the fact that the two usual tasks performed by Bayes rule, that is prediction and revision, can no longer be performed by the same conditioning rule [Dubois and Prade, 1997b].

Prediction

When a credal set represents generic knowledge, Bayesian prediction or plausible inference is achieved by performing a form of sensitivity analysis on probabilistic conditioning, a rule proposed in [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF][START_REF] Fagin | A new approach to updating beliefs[END_REF]. Let P be a credal set on S. It induces lower and upper bounds P * (A) and P * (A) of the probability of each proposition A. In the presence of new pieces of information about a singular case, summarized by the context C, the belief of the agent that proposition A holds for the case at hand is represented by the interval

[P * (A | C), P * (A | C)] defined by P * (A | C) = inf{P(A | C) s.t. P(C) > 0, P ∈ P} P * (A | C) = sup{P(A | C) s.t. P(C) > 0, P ∈ P}.
Note that it is possible that interval

[P * (A | C), P * (A | C)] is larger than [P * (A), P * (A)],
which means that there is a deficit of information given by the credal set P in the specific context C, while there is more in more general contexts. This is called the dilation effect [START_REF] Seidenfeld | Dilation for sets of probabilities[END_REF]. It reflects the fact that in the presence of incomplete information, the more observations are available on a singular case, the less relevant to this case is generic information about the population of cases, because the less the new one can be viewed as representative of this population. In the case of Bayes rule applied to a known frequentist distribution, this dilation effect does not appear because in any case a single number is obtained. However, this value becomes all the more dubious as the number of cases similar to the one under study in the population justifying the frequentist distribution becomes smaller and smaller as we condition on a more specific context. If P is the credal set associated to a convex capacity (hence, belief functions, necessity measures as well) the upper and lower conditional functions take the remarkable forms [START_REF] Fagin | A new approach to updating beliefs[END_REF]:

P * (A | C) = P * (A ∩C) P * (A ∩C) + P * (A ∩C) ; P * (A | C) = P * (A ∩C) P * (A ∩C) + P * (A ∩C) (37)
It is easy to see that P * (A | C) = 1 -P * (A | C), and these formula extend probabilistic conditioning, in the sense that P * (A | C) is a function of P * (A ∩ C) and P * (C ∪ A) (and similarly for P * (A | C)). It is clear that this form of conditioning does not correspond to the idea of enriching generic information by new observations, i.e., the latter do not alter the credal set. We just extract from it information that fits the available evidence, in the spirit of De Finetti.

In the theory of belief functions, the above form of conditioning can be justified in terms of their mass functions, positive weights m(E) assigned to subsets E of S. When a mass function represents generic knowledge, m(E) may be, e.g., the proportion of individuals for which imprecise proposition E holds, in the whole population. In this setting, prediction in context C consists in evaluating mass function m(• | C) induced by m in context C summarizing the available singular information. Three cases can be considered [START_REF] De Campos | The concept of conditional fuzzy measure[END_REF]]:

1. E ⊆ C: in that case, m(E) remains committed to E; 2. E ∩C = / 0: in that case, m(E) is no longer relevant and is discarded; 3. E ∩ C = / 0 and E ∩ C = / 0: in that case, a part α E • m(E) of m(E) remains committed to E ∩C and the rest, i.e., (1α E ) • m(E), is committed to E ∩C. But the proportion α E is unknown.

The third case corresponds to incomplete information E which neither confirms, nor contradicts C. We do not have information to determine if, in each of the situations corresponding to these observations, C is true or not. Assume that one knows the proportions {α E , E ⊆ S}. We always have α E = 1 in the first case and α E = 0 in the second case. One thus constructs a mass function m α (• | C). We can remark that renormalization of the resulting mass function is necessary whenever Pl(C) < 1: each mass is then divided by Pl(C).

We still obtain belief and plausibility functions2 (see the non-trival proofs by [START_REF] Jaffray | Bayesian updating and belief functions[END_REF] and [START_REF] Paris | The Uncertain Reasoner' Companion[END_REF]). Let us notice that if Bel(C) = 0 and Pl(C) = 1 (total ignorance about C) then all focal sets of m overlap C but C does not contain any of them. In that case, Bel(A | C) = 0 and Pl(A | C) = 1, ∀A = S, / 0: nothing can be inferred in context C.

Revision

In the framework of imprecise probabilities, a simple brute force approach to revision of a credal set P by an information item C consists in enforcing the additional constraint P(C) = 1 to P, namely restrict the latter, and update the upper and lower probabilities of events accordingly: (42)

Clearly, it is supposed, in contrast with the assumption in the prediction problem, that the new item of information is of the same nature as the original credal set, and can be modelled by the credal set {P : P(C) = 1} (it can be frequentist or subjectivist). However, by doing so, it may be that the intersection of the two credal sets, i.e., {P ∈ P s.t. P(C) = 1} is empty. This is for instance most of the time the case in the standard probabilistic setting since P reduces to a singleton. The way out is to apply the maximum likelihood principle [START_REF] Gilboa | Updating ambiguous beliefs[END_REF] (44)

For convex capacities, it holds that P * (A || C) = P * (A∩C) P * (C) , which generalizes Dempster rule of conditioning. In the belief function setting, this form of conditioning systematically assumes that α E = 1 whenever E ∩C = / 0 in Bel α (A | C) and Pl α (A | C). From the perspective of Shafer and Smets, mass function m does not represent generic information, but uncertain singular information, such as unreliable testimonies or inconclusive pieces of evidence about a specific situation. The existence of two forms of conditioning in the theory of belief functions can thus be explained by the difference between generic and singular information.

As a general setting for the numerical representation of uncertainty, liable of various interpretations, and encompassing other theories of uncertainty as formal particular cases, imprecise probabilities receive an increasing attention and foster a number of theoretical works (for instance, in de [START_REF] De Cooman | Imprecise probability trees: Bridging two theories of imprecise probability[END_REF] bridges are built between Walley's approach to imprecise probabilities and the game-theoretic view of probability by [START_REF] Shafer | Probability and Finance: It's Only a Game![END_REF]). Practical representation methods in artificial intelligence are also studied, for instance the imprecise probability version of Bayesian nets, including dedicated uncertainty propagation algorithms [START_REF] Cozman | Credal networks[END_REF][START_REF] De Campos | The inferential complexity of Bayesian and credal networks[END_REF][START_REF] Cozman | On the complexity of propositional and relational credal networks[END_REF].

Conclusion

Artificial Intelligence, when focusing on representation and reasoning with imperfect information, was naturally bound to realize that classical logic on the one hand, and precise probabilities on the other hand, were separately insufficient to deal with this issue. Alternative formal frameworks have emerged in the last 40 years or so to that effect, that this chapter partially accounts for. These frameworks are numerous and often complement each other rather than compete, even if research in this area remains fragmented. Nevertheless, these alternative theories of uncertain, incomplete or conflicting information offer a very rich range of formalisms. It is important to correctly understand their potentials and limitations prior to appropriately exploiting them. These frameworks can be qualitative (like possibilistic logic, dicussed in the previous chapter) or quantitative (like belief functions and imprecise probabilities). A significant effort is still needed before a full-fledged unification of the various approaches is achieved, and the links with neighboring disciplines like statistics are fully established, in order to master their use in applications.

  : ∀A, B ⊆ S, such that A ∩ B = / 0, P * (A) + P * (B) ≤ P * (A ∪ B) ≤ P * (A) + P * (B) ≤ P * (A ∪ B) ≤ P * (A) + P * (B). (35)The width of the interval [P * (A), P * (A)] represents the amount of ignorance of the agent as to the truth of proposition A. Total ignorance is when this interval is [0, 1].

  Denoting by Bel α (A | C) and Pl α (A | C) the belief and plausibility obtained by focalization on C with vector of proportions α, we can define the conditional degrees of belief and of plausibility given C asBel(A | C) = inf α Bel α (A | C); Pl(A | C) = sup α Pl α (A | C). (38)These definitions yield the following special cases of Bayesian conditioning for imprecise probability (37):Bel(A | C) = inf{P(A | C) s.t. P(C) > 0, P ≥ Bel} = Bel(A ∩C) Bel(A ∩C) + Pl(A ∩C) ; (39) Pl(A | C) = sup{P(A | C) s.t. P(C) > 0, P ≥ Bel} = Pl(A ∩C) Pl(A ∩C) + Bel(A ∩C).

P

  * (A || C) = inf{P(A | C) s.t. P(C) = 1, P ∈ P}; (41) P * (A || C) = sup{P(A | C) s.t. P(C) = 1, P ∈ P}.

  , selecting the most likely probability functions in P, replacing condition P(C) = 1 by P(C) = P * (C) in the above definition of conditioning: P * (A || C) = inf{P(A | C) s.t. P(C) = P * (C), P ∈ P}; (43) P * (A || C) = sup{P(A | C) s.t. P(C) = P * (C), P ∈ P}.

Considering the disjunctive rule instead of the conjunctive rule would lead to replace Q by Bel in (24).

When applied to necessity and plausibility measures, these two formulas also preserve consonance and yield another form of conditional possibility and necessity[Dubois and Prade, 1997a].