BRAIN. Broad Research in Artificial Intelligence and Neuroscience, ISSN 2067-3957, Volume 1, October 2010, Special Issue on Advances in Applied Sciences, Eds Barna Iantovics, Marius Mǎruşteri, Rodica-M. Ion, Roumen Kountchev AN INTRODUCTION TO DSMT IN INFORMATION FUSION Jean Dezert and Florentin Smarandache Abstract. The management and combination of uncertain, imprecise, fuzzy and even paradoxical or highly conflicting sources of information has al- ways been, and still remains today, of primal importance for the development of reliable modern information systems involving artificial reasoning. In this introduction, we present a survey of our recent theory of plausible and para- doxical reasoning, known as Dezert-Smarandache Theory (DSmT), developed for dealing with imprecise, uncertain and conflicting sources of information. We focus our presentation on the foundations of DSmT and on its most im- portant rules of combination, rather than on browsing specific applications of DSmT available in literature. Several simple examples are given throughout this presentation to show the efficiency and the generality of this new theory. Keywords: Dezert-Smarandache Theory, DSmT, quantitative and quali- tative reasoning, information fusion 2000 Mathematics Subject Classification: 68T37, 94A15, 94A17, 68T40. 1 1This paper is based on the first chapter of [35]. 1 Jean Dezert and Florentin Smarandache - An introduction to DSmT 1 Introduction The management and combination of uncertain, imprecise, fuzzy and even paradoxical or highly conflicting sources of information has always been, and still remains today, of primal importance for the development of reliable mod- ern information systems involving artificial reasoning. The combination (fu- sion) of information arises in many fields of applications nowadays (especially in defense, medicine, finance, geo-science, economy, etc). When several sen- sors, observers or experts have to be combined together to solve a problem, or if one wants to update our current estimation of solutions for a given problem with some new information available, we need powerful and solid mathematical tools for the fusion, specially when the information one has to deal with is im- precise and uncertain. In this chapter, we present a survey of our recent theory of plausible and paradoxical reasoning, known as Dezert-Smarandache Theory (DSmT) in the literature, developed for dealing with imprecise, uncertain and conflicting sources of information. Recent publications have shown the interest and the ability of DSmT to solve problems where other approaches fail, espe- cially when conflict between sources becomes high. We focus this presentation rather on the foundations of DSmT, and on the main important rules of combi- nation, than on browsing specific applications of DSmT available in literature. Successful applications of DSmT in target tracking, satellite surveillance, situ- ation analysis, robotics, medicine, biometrics, etc, can be found in Parts II of [29, 33, 35] and on the world wide web [36]. Several simple examples are given in this paper to show the efficiency and the generality of DSmT 2 Foundations of DSmT The development of DSmT (Dezert-Smarandache Theory of plausible and paradoxical reasoning [29, 6]) arises from the necessity to overcome the in- herent limitations of DST (Dempster-Shafer Theory [22]) which are closely related with the acceptance of Shafer’s model for the fusion problem under consideration (i.e. the frame of discernment Θ is implicitly defined as a finite set of exhaustive and exclusive hypotheses θi, i = 1, . . . , n since the masses of belief are defined only on the power set of Θ - see section 2.1 for details), the third middle excluded principle (i.e. the existence of the complement for any elements/propositions belonging to the power set of Θ), and the acceptance of Dempster’s rule of combination (involving normalization) as the framework for 2 Jean Dezert and Florentin Smarandache - An introduction to DSmT the combination of independent sources of evidence. Discussions on limitations of DST and presentation of some alternative rules to Dempster’s rule of combi- nation can be found in [53, 54, 55, 49, 56, 9, 50, 19, 38, 46, 13, 17, 15, 21, 16, 29] and therefore they will be not reported in details in this introduction. We argue that these three fundamental conditions of DST can be removed and another new mathematical approach for combination of evidence is possible. This is the purpose of DSmT. The basis of DSmT is the refutation of the principle of the third excluded middle and Shafer’s model, since for a wide class of fusion problems the intrinsic nature of hypotheses can be only vague and imprecise in such a way that precise refinement is just impossible to obtain in reality so that the exclusive elements θi cannot be properly identified and precisely separated. Many problems in- volving fuzzy continuous and relative concepts described in natural language and having no absolute interpretation like tallness/smallness, pleasure/pain, cold/hot, Sorites paradoxes, etc, enter in this category. DSmT starts with the notion of free DSm model, denoted Mf (Θ), and considers Θ only as a frame of exhaustive elements θi, i = 1, . . . , n which can potentially overlap. This model is free because no other assumption is done on the hypotheses, but the weak exhaustivity constraint which can always be satisfied according the closure principle explained in [29]. No other constraint is involved in the free DSm model. When the free DSm model holds, the commutative and associa- tive classical DSm rule of combination, denoted DSmC, corresponding to the conjunctive consensus defined on the free Dedekind’s lattice is performed. Depending on the intrinsic nature of the elements of the fusion problem under consideration, it can however happen that the free model does not fit the reality because some subsets of Θ can contain elements known to be truly exclusive but also truly non existing at all at a given time (specially when working on dynamic fusion problem where the frame Θ varies with time with the revision of the knowledge available). These integrity constraints are then explicitly and formally introduced into the free DSm model Mf (Θ) in order to adapt it properly to fit as close as possible with the reality and permit to construct a hybrid DSm model M(Θ) on which the combination will be ef- ficiently performed. Shafer’s model, denoted M0(Θ), corresponds to a very specific hybrid DSm model including all possible exclusivity constraints. DST has been developed for working only with M0(Θ) while DSmT has been de- 3 Jean Dezert and Florentin Smarandache - An introduction to DSmT veloped for working with any kind of hybrid model (including Shafer’s model and the free DSm model), to manage as efficiently and precisely as possible im- precise, uncertain and potentially highly conflicting sources of evidence while keeping in mind the possible dynamicity of the information fusion problematic. The foundations of DSmT are therefore totally different from those of all ex- isting approaches managing uncertainties, imprecisions and conflicts. DSmT provides a new interesting way to attack the information fusion problematic with a general framework in order to cover a wide variety of problems. DSmT refutes also the idea that sources of evidence provide their beliefs with the same absolute interpretation of elements of the same frame Θ and the conflict between sources arises not only because of the possible unreliability of sources, but also because of possible different and relative interpretation of Θ, e.g. what is considered as good for somebody can be considered as bad for somebody else. There is some unavoidable subjectivity in the belief as- signments provided by the sources of evidence, otherwise it would mean that all bodies of evidence have a same objective and universal interpretation (or measure) of the phenomena under consideration, which unfortunately rarely occurs in reality, but when basic belief assignments (bba’s) are based on some objective probabilities transformations. But in this last case, probability the- ory can handle properly and efficiently the information, and DST, as well as DSmT, becomes useless. If we now get out of the probabilistic background argumentation for the construction of bba, we claim that in most of cases, the sources of evidence provide their beliefs about elements of the frame of the fusion problem only based on their own limited knowledge and experience without reference to the (inaccessible) absolute truth of the space of possibili- ties. 2.1 The power set, hyper-power set and super-power set In DSmT, we take very care about the model associated with the set Θ of hypotheses where the solution of the problem is assumed to belong to. In particular, the three main sets (power set, hyper-power set and super-power set) can be used depending on their ability to fit adequately with the nature of hypotheses. In the following, we assume that Θ = {θ1, . . . , θn} is a finite 4 Jean Dezert and Florentin Smarandache - An introduction to DSmT set (called frame) of n exhaustive elements2. If Θ = {θ1, . . . , θn} is a priori not closed (Θ is said to be an open world/frame), one can always include in it a closure element, say θn+1 in such away that we can work with a new closed world/frame {θ1, . . . , θn, θn+1}. So without loss of generality, we will always assume that we work in a closed world by considering the frame Θ as a finite set of exhaustive elements. Before introducing the power set, the hyper-power set and the super-power set it is necessary to recall that subsets are regarded as propositions in Dempster-Shafer Theory (see Chapter 2 of [22]) and we adopt the same approach in DSmT. • Subsets as propositions: Glenn Shafer in pages 35–37 of [22] consid- ers the subsets as propositions in the case we are concerned with the true value of some quantity θ taking its possible values in Θ. Then the propositions Pθ(A) of interest are those of the form3: Pθ(A) , The true value of θ is in a subset A of Θ. Any proposition Pθ(A) is thus in one-to-one correspondence with the subset A of Θ. Such correspondence is very useful since it translates the logical notions of conjunction ∧, disjunction ∨, implication ⇒ and nega- tion ¬ into the set-theoretic notions of intersection ∩, union ∪, inclusion ⊂ and complementation c(.). Indeed, if Pθ(A) and Pθ(B) are two propo- sitions corresponding to subsets A and B of Θ, then the conjunction Pθ(A)∧Pθ(B) corresponds to the intersection A∩B and the disjunction Pθ(A) ∨ Pθ(B) corresponds to the union A ∪ B. A is a subset of B if and only if Pθ(A) ⇒ Pθ(B) and A is the set-theoretic complement of B with respect to Θ (written A = cΘ(B)) if and only if Pθ(A) = ¬Pθ(B). In other words, the following equivalences are then used between the operations on the subsets and on the propositions: • Canonical form of a proposition: In DSmT we consider all propo- sitions/sets in a canonical form. We take the disjunctive normal form, which is a disjunction of conjunctions, and it is unique in Boolean alge- bra and simplest. For example, X = A ∩ B ∩ (A ∪ B ∪ C) it is not in 2We do not assume here that elements θi are necessary exclusive, unless specified. There is no restriction on θi but the exhaustivity. 3We use the symbol , to mean equals by definition; the right-hand side of the equation is the definition of the left-hand side. 5 Jean Dezert and Florentin Smarandache - An introduction to DSmT Operations Subsets Propositions Intersection/conjunction A ∩ B Pθ(A) ∧ Pθ(B) Union/disjunction A ∪ B Pθ(A) ∨ Pθ(B) Inclusion/implication A ⊂ B Pθ(A) ⇒ Pθ(B) Complementation/negation A = cΘ(B) Pθ(A) = ¬Pθ(B) Table 1: Correspondence between operations on subsets and on propositions. a canonical form, but we simplify the formula and X = A ∩ B is in a canonical form. • The power set: 2Θ , (Θ, ∪) Aside Dempster’s rule of combination, the power set is one of the corner stones of Dempster-Shafer Theory (DST) since the basic belief assignments to com- bine are defined on the power set of the frame Θ. In mathematics, given a set Θ, the power set of Θ, written 2Θ, is the set of all subsets of Θ. In Zer- meloFraenkel set theory with the axiom of choice (ZFC), the existence of the power set of any set is postulated by the axiom of power set. In other words, Θ generates the power set 2Θ with the ∪ (union) operator only. More precisely, the power set 2Θ is defined as the set of all composite propositions/subsets built from elements of Θ with ∪ operator such that: 1. ∅, θ1, . . . , θn ∈ 2Θ. 2. If A, B ∈ 2Θ, then A ∪ B ∈ 2Θ. 3. No other elements belong to 2Θ, except those obtained by using rules 1 and 2. • The hyper-power set: DΘ , (Θ, ∪, ∩) One of the cornerstones of DSmT is the free Dedekind’s lattice [3] denoted as hyper-power set in DSmT framework. Let Θ = {θ1, . . . , θn} be a finite set (called frame) of n exhaustive elements. The hyper-power set DΘ is defined as the set of all composite propositions/subsets built from elements of Θ with ∪ and ∩ operators such that: 1. ∅, θ1, . . . , θn ∈ DΘ. 6 Jean Dezert and Florentin Smarandache - An introduction to DSmT 2. If A, B ∈ DΘ, then A ∩ B ∈ DΘ and A ∪ B ∈ DΘ. 3. No other elements belong to DΘ, except those obtained by using rules 1 or 2. Therefore by convention, we write DΘ = (Θ, ∪, ∩) which means that Θ generates DΘ under operators ∪ and ∩. The dual (obtained by switching ∪ and ∩ in expressions) of DΘ is itself. There are elements in DΘ which are self-dual (dual to themselves), for example α8 for the case when n = 3 in the following example. The cardinality of DΘ is majored by 22 n when the cardinality of Θ equals n, i.e. |Θ| = n. The generation of hyper-power set DΘ is closely related with the famous Dedekind’s problem [3, 2] on enumerating the set of isotone Boolean functions. The generation of the hyper-power set is presented in [29]. Since for any given finite set Θ, |DΘ| ≥ |2Θ| we call DΘ the hyper-power set of Θ. The cardinality of hyper-power set DΘ for n ≥ 1 follows the sequence of Dedekind’s numbers [24], i.e. 1,2,5,19,167, 7580,7828353,... and analytical ex- pression of Dedekind’s numbers has been obtained recently by Tombak in [45] (see [29] for details on generation and ordering of DΘ). Interesting investiga- tions on the programming of the generation of hyper-power sets for engineering applications have been done in Chapter 15 of [33] and in [35]. Shafer’s model of a frame: More generally, when all the elements of a given frame Θ are known (or are assumed to be) truly exclusive, then the hyper-power set DΘ reduces to the classical power set 2Θ. Therefore, working on power set 2Θ as Glenn Shafer has proposed in his Mathematical Theory of Evidence [22]) is equivalent to work on hyper-power set DΘ with the assump- tion that all elements of the frame are exclusive. This is what we call Shafer’s model of the frame Θ, written M0(Θ), even if such model/assumption has not been clearly stated explicitly by Shafer himself in his milestone book. • The super-power set: SΘ , (Θ, ∪, ∩, c(.)) The notion of super-power set has been introduced by Smarandache in the Chapter 8 of [33]. It corresponds actually to the theoretical construction of the power set of the minimal4 refined frame Θref of Θ. Θ generates SΘ under operators ∪, ∩ and complementation c(.). SΘ = (Θ, ∪, ∩, c(.)) is a Boolean 4The minimality refers here to the cardinality of the refined frames. 7 Jean Dezert and Florentin Smarandache - An introduction to DSmT algebra with respect to the union, intersection and complementation. There- fore working with the super-power set is equivalent to work with a minimal theoretical refined frame Θref satisfying Shafer’s model. More precisely, SΘ is defined as the set of all composite propositions/subsets built from elements of Θ with ∪, ∩ and c(.) operators such that: 1. ∅, θ1, . . . , θn ∈ SΘ. 2. If A, B ∈ SΘ, then A ∩ B ∈ SΘ, A ∪ B ∈ SΘ. 3. If A ∈ SΘ, then c(A) ∈ SΘ. 4. No other elements belong to SΘ, except those obtained by using rules 1, 2 and 3. As reported in [30], a similar generalization has been previously used in 1993 by Guan and Bell [12] for the Dempster-Shafer rule using propositions in sequential logic and reintroduced in 1994 by Paris in his book [18], page 4. A one-to-one correspondence between the elements of SΘ and 2Θ ref can be defined for any cardinality |Θ| ≥ 2 of the frame Θ and thus one can consider SΘ as the mathematical construction of the power set 2Θ ref of the minimal refinement of the frame Θ. Of course, when Θ already satisfies Shafer’s model, the hyper-power set and the super-power set coincide with the classical power set of Θ. It is worth to note that even if we have a mathematical tool to built the minimal refined frame satisfying Shafer’s model, it doesn’t mean necessary that one must work with this super-power set in general in real applications because most of the times the elements/granules of SΘ have no clear physical meaning, not to mention the drastic increase of the complexity since one has 2Θ ⊆ DΘ ⊆ SΘ and |2Θ| = 2|Θ| < |DΘ| < |SΘ| = 2|Θ ref | = 22 |Θ|−1 (1) Typically, In summary, DSmT offers truly the possibility to build and to work on re- fined frames and to deal with the complement whenever necessary, but in most of applications either the frame Θ is already built/chosen to satisfy Shafer’s model or the refined granules have no clear physical meaning which finally pre- vent to be considered/assessed individually so that working on the hyper-power 8 Jean Dezert and Florentin Smarandache - An introduction to DSmT |Θ| = n |2Θ| = 2n |DΘ| |SΘ| = |2Θref | = 22n−1 2 4 5 23 = 8 3 8 19 27 = 128 4 16 167 215 = 32768 5 32 7580 231 = 2147483648 Table 2: Cardinalities of 2Θ, DΘ and SΘ. set is usually sufficient for dealing with uncertain imprecise (quantitative or qualitative) and highly conflicting sources of evidences. Working with SΘ is actually very similar to working with 2Θ in the sense that in both cases we work with classical power sets; the only difference is that when working with SΘ we have implicitly switched from the original frame Θ representation to a minimal refinement Θref representation. Therefore, in the sequel we focus our discussions based mainly on hyper-power set rather than (super-) power set which has already been the basis for the development of DST. But as already mentioned, DSmT can easily deal with belief functions defined on 2Θ or SΘ similarly as those defined on DΘ. Generic notation: In the sequel, we use the generic notation GΘ for denoting the sets (power set, hyper-power set and super-power set) on which the belief functions are defined. The main distinctions between DSmT and DST are summarized by the fol- lowing points: 1. The refinement is not always (physically) possible, especially for elements from the frame of discernment whose frontiers are not clear, such as: colors, vague sets, unclear hypotheses, etc. in the frame of discernment; DST does not fit well for working in such cases, while DSmT does; 2. Even in the case when the frame of discernment can be refined (i.e. the atomic elements of the frame have all a distinct physical meaning), it is still easier to use DSmT than DST since in DSmT framework the refinement is done automatically by the mathematical construction of the super-power set; 3. DSmT offers better fusion rules, for example Proportional Conflict re- distribution Rule # 5 (PCR5) - presented in the sequel - is better than 9 Jean Dezert and Florentin Smarandache - An introduction to DSmT Dempster’s rule; hybrid DSm rule (DSmH) works for the dynamic fu- sion, while Dubois-Prade fusion rule does not (DSmH is an extension of Dubois-Prade rule); 4. DSmT offers the best qualitative operators (when working with labels) giving the most accurate and coherent results; 5. DSmT offers new interesting quantitative conditioning rules (BCRs) and qualitative conditioning rules (QBCRs), different from Shafer’s condi- tioning rule (SCR). SCR can be seen simply as a combination of a prior mass of belief with the mass m(A) = 1 whenever A is the conditioning event; 6. DSmT proposes a new approach for working with imprecise quantita- tive or qualitative information and not limited to interval-valued belief structures as proposed generally in the literature [4, 5, 47]. 2.2 Notion of free and hybrid DSm models Free DSm model: The elements θi, i = 1, . . . , n of Θ constitute the finite set of hypotheses/concepts characterizing the fusion problem under consideration. When there is no constraint on the elements of the frame, we call this model the free DSm model , written Mf (Θ). This free DSm model allows to deal directly with fuzzy concepts which depict a continuous and relative intrinsic nature and which cannot be precisely refined into finer disjoint information granules having an absolute interpretation because of the unreachable univer- sal truth. In such case, the use of the hyper-power set DΘ (without integrity constraints) is particularly well adapted for defining the belief functions one wants to combine. Shafer’s model: In some fusion problems involving discrete concepts, all the elements θi, i = 1, . . . , n of Θ can be truly exclusive. In such case, all the exclusivity constraints on θi, i = 1, . . . , n have to be included in the previous model to characterize properly the true nature of the fusion problem and to fit it with the reality. By doing this, the hyper-power set DΘ as well as the super-power set SΘ reduce naturally to the classical power set 2Θ and this con- stitutes what we have called Shafer’s model , denoted M0(Θ). Shafer’s model 10 Jean Dezert and Florentin Smarandache - An introduction to DSmT corresponds actually to the most restricted hybrid DSm model. Hybrid DSm models: Between the class of fusion problems correspond- ing to the free DSm model Mf (Θ) and the class of fusion problems corre- sponding to Shafer’s model M0(Θ), there exists another wide class of hybrid fusion problems involving in Θ both fuzzy continuous concepts and discrete hypotheses. In such (hybrid) class, some exclusivity constraints and possibly some non-existential constraints (especially when working on dynamic5 fusion) have to be taken into account. Each hybrid fusion problem of this class will then be characterized by a proper hybrid DSm model denoted M(Θ) with M(Θ) 6= Mf (Θ) and M(Θ) 6= M0(Θ). In any fusion problems, we consider as primordial at the very beginning and before combining information expressed as belief functions to define clearly the proper frame Θ of the given problem and to choose explicitly its correspond- ing model one wants to work with. Once this is done, the second important point is to select the proper set 2Θ, DΘ or SΘ on which the belief functions will be defined. The third point concerns the choice of an efficient rule of com- bination of belief functions and finally the criteria adopted for decision-making. In the sequel, we focus our presentation mainly on hyper-power set DΘ (unless specified) since it is the most interesting new aspect of DSmT for read- ers already familiar with DST framework, but a fortiori we can work similarly on classical power set 2Θ if Shafer’s model holds, and even on 2Θ ref (the power set of the minimal refined frame) whenever one wants to use it and if possible. Examples of models for a frame Θ: • Let’s consider the 2D problem where Θ = {θ1, θ2} with DΘ = {∅, θ1 ∩ θ2, θ1, θ2, θ1∪θ2} and assume now that θ1 and θ2 are truly exclusive (i.e. Shafer’s model M0 holds), then because θ1 ∩ θ2 M 0 = ∅, one gets DΘ = {∅, θ1 ∩ θ2 M 0 = ∅, θ1, θ2, θ1 ∪ θ2} = {∅, θ1, θ2, θ1 ∪ θ2} ≡ 2Θ. • As another simple example of hybrid DSm model, let’s consider the 3D case with the frame Θ = {θ1, θ2, θ3} with the model M 6= Mf in which we force 5i.e. when the frame Θ and/or the model M is changing with time. 11 Jean Dezert and Florentin Smarandache - An introduction to DSmT all possible conjunctions to be empty, but θ1 ∩ θ2. This hybrid DSm model is then represented with the Venn diagram on Fig. 1 (where boundaries of intersection of θ1 and θ2 are not precisely defined if θ1 and θ2 represent only fuzzy concepts like smallness and tallness by example). &% '$ &% '$ &% '$ @R θ1 ¡ª θ2 ¾ θ3 12 3 21 Figure 1: Venn diagram of a DSm hybrid model for a 3D frame. 2.3 Generalized belief functions From a general frame Θ, we define a map m(.) : GΘ → [0, 1] associated to a given body of evidence B as m(∅) = 0 and ∑ A∈GΘ m(A) = 1 (2) The quantity m(A) is called the generalized basic belief assignment/mass (gbba) of A. The generalized belief and plausibility functions are defined in almost the same manner as within DST, i.e. Bel(A) = ∑ B⊆A B∈GΘ m(B) Pl(A) = ∑ B∩A6=∅ B∈GΘ m(B) (3) We recall that GΘ is the generic notation for the set on which the gbba is defined (GΘ can be 2Θ, DΘ or even SΘ depending on the model chosen for Θ). These definitions are compatible with the definitions of the classical belief functions in DST framework when GΘ = 2Θ for fusion problems where Shafer’s model M0(Θ) holds. We still have ∀A ∈ GΘ, Bel(A) ≤ Pl(A). Note that when working with the free DSm model Mf (Θ), one has always Pl(A) = 1 ∀A 6= ∅ ∈ (GΘ = DΘ) which is normal. 12 Jean Dezert and Florentin Smarandache - An introduction to DSmT 2.4 The classic DSm rule of combination When the free DSm model Mf (Θ) holds for the fusion problem under consid- eration, the classic DSm rule of combination mMf (Θ) ≡ m(.) , [m1 ⊕ m2](.) of two independent6 sources of evidences B1 and B2 over the same frame Θ with belief functions Bel1(.) and Bel2(.) associated with gbba m1(.) and m2(.) corresponds to the conjunctive consensus of the sources. It is given by [29]: ∀C ∈ DΘ, mMf (Θ)(C) ≡ m(C) = ∑ A,B∈DΘ A∩B=C m1(A)m2(B) (4) Since DΘ is closed under ∪ and ∩ set operators, this new rule of com- bination guarantees that m(.) is a proper generalized belief assignment, i.e. m(.) : DΘ → [0, 1]. This rule of combination is commutative and associative and can always be used for the fusion of sources involving fuzzy concepts when free DSm model holds for the problem under consideration. This rule has been extended for s > 2 sources in [29]. According to Table 2, this classic DSm rule of combination looks very ex- pensive in terms of computations and memory size due to the huge number of elements in DΘ when the cardinality of Θ increases. This remark is however valid only if the cores (the set of focal elements of gbba) K1(m1) and K2(m2) coincide with DΘ, i.e. when m1(A) > 0 and m2(A) > 0 for all A 6= ∅ ∈ DΘ. Fortunately, it is important to note here that in most of the practical appli- cations the sizes of K1(m1) and K2(m2) are much smaller than |DΘ| because bodies of evidence generally allocate their basic belief assignments only over a subset of the hyper-power set. This makes things easier for the implemen- tation of the classic DSm rule (4). The DSm rule is actually very easy to implement. It suffices for each focal element of K1(m1) to multiply it with the focal elements of K2(m2) and then to pool all combinations which are equiva- lent under the algebra of sets. While very costly in term on memory storage in the worst case (i.e. when all m(A) > 0, A ∈ DΘ or A ∈ 2Θref ), the DSm rule however requires much smaller memory storage than when working with 6While independence is a difficult concept to define in all theories managing epistemic uncertainty, we follow here the interpretation of Smets in [37] and [38], p. 285 and consider that two sources of evidence are independent (i.e distinct and noninteracting) if each leaves one totally ignorant about the particular value the other will take. 13 Jean Dezert and Florentin Smarandache - An introduction to DSmT SΘ, i.e. working with a minimal refined frame satisfying Shafer’s model. In most fusion applications only a small subset of elements of DΘ have a non null basic belief mass because all the commitments are just usually impossible to obtain precisely when the dimension of the problem increases. Thus, it is not necessary to generate and keep in memory all elements of DΘ (or eventually SΘ) but only those which have a positive belief mass. However there is a real technical challenge on how to manage efficiently all elements of the hyper-power set. This problem is obviously much more difficult when trying to work on a refined frame of discernment Θref if one really prefers to use Dempster-Shafer theory and apply Dempster’s rule of combination. It is important to keep in mind that the ultimate and minimal refined frame consisting in exhaustive and exclusive finite set of refined exclusive hypotheses is just impossible to justify and to define precisely for all problems dealing with fuzzy and ill-defined continuous concepts. A discussion on refinement with an example has be included in [29]. 2.5 The hybrid DSm rule of combination When the free DSm model Mf (Θ) does not hold due to the true nature of the fusion problem under consideration which requires to take into account some known integrity constraints, one has to work with a proper hybrid DSm model M(Θ) 6= Mf (Θ). In such case, the hybrid DSm rule (DSmH) of combination based on the chosen hybrid DSm model M(Θ) for k ≥ 2 independent sources of information is defined for all A ∈ DΘ as [29]: mDSmH (A) = mM(Θ)(A) , φ(A) [ S1(A) + S2(A) + S3(A) ] (5) where all sets involved in formulas are in the canonical form and φ(A) is the characteristic non-emptiness function of a set A, i.e. φ(A) = 1 if A /∈ ∅ and φ(A) = 0 otherwise, where ∅ , {∅M, ∅}. ∅M is the set of all elements of DΘ which have been forced to be empty through the constraints of the model M and ∅ is the classical/universal empty set. S1(A) ≡ mMf (θ)(A), S2(A), S3(A) are defined by S1(A) , ∑ X1,X2,...,Xk∈DΘ X1∩X2∩...∩Xk=A k∏ i=1 mi(Xi) (6) 14 Jean Dezert and Florentin Smarandache - An introduction to DSmT S2(A) , ∑ X1,X2,...,Xk∈∅ [U=A]∨[(U∈∅)∧(A=It)] k∏ i=1 mi(Xi) (7) S3(A) , ∑ X1,X2,...,Xk∈DΘ X1∪X2∪...∪Xk=A X1∩X2∩...∩Xk∈∅ k∏ i=1 mi(Xi) (8) with U , u(X1) ∪ u(X2) ∪ . . . ∪ u(Xk) where u(X) is the union of all θi that compose X, It , θ1 ∪ θ2 ∪ . . . ∪ θn is the total ignorance. S1(A) corresponds to the classic DSm rule for k independent sources based on the free DSm model Mf (Θ); S2(A) represents the mass of all relatively and absolutely empty sets which is transferred to the total or relative ignorances associated with non existential constraints (if any, like in some dynamic problems); S3(A) transfers the sum of relatively empty sets directly onto the canonical disjunctive form of non-empty sets. The hybrid DSm rule of combination generalizes the classic DSm rule of combination and is not equivalent to Dempter’s rule. It works for any models (the free DSm model, Shafer’s model or any other hybrid models) when ma- nipulating precise generalized (or eventually classical) basic belief functions. An extension of this rule for the combination of imprecise generalized (or even- tually classical) basic belief functions is presented in next section. As already stated, in DSmT framework it is also possible to deal directly with comple- ments if necessary depending on the problem under consideration and the information provided by the sources of evidence themselves. The first and simplest way is to work with SΘ on Shafer’s model when a minimal refinement is possible and makes sense. The second way is to deal with partially known frame and introduce directly the complementary hypotheses into the frame itself. By example, if one knows only two hypotheses θ1, θ2 and their complements θ̄1, θ̄2, then we can choose to switch from original frame Θ = {θ1, θ2} to the new frame Θ = {θ1, θ2, θ̄1, θ̄2}. In such case, we don’t nec- essarily assume that θ̄1 = θ2 and θ̄2 = θ1 because θ̄1 and θ̄2 may include other unknown hypotheses we have no information about (case of partial known frame). More generally, in DSmT framework, it is not necessary that the frame is built on pure/simple (possibly vague) hypotheses θi as usually done 15 Jean Dezert and Florentin Smarandache - An introduction to DSmT in all theories managing uncertainty. The frame Θ can also contain directly as elements conjunctions and/or disjunctions (or mixed propositions) and nega- tions/complements of pure hypotheses as well. The DSm rules also work in such non-classic frames because DSmT works on any distributive lattice built from Θ anywhere Θ is defined. 2.6 Examples of combination rules Here are some numerical examples on results obtained by DSm rules of com- bination. More examples can be found in [29]. 2.6.1 Example with Θ = {θ1, θ2, θ3, θ4} Let’s consider the frame of discernment Θ = {θ1, θ2, θ3, θ4}, two independent experts, and the two following bbas m1(θ1) = 0.6 m1(θ3) = 0.4 m2(θ2) = 0.2 m2(θ4) = 0.8 represented in terms of mass matrix M = [ 0.6 0 0.4 0 0 0.2 0 0.8 ] • Dempster’s rule cannot be applied because: ∀1 ≤ j ≤ 4, one gets m(θj) = 0/0 (undefined!). • But the classic DSm rule works because one obtains: m(θ1) = m(θ2) = m(θ3) = m(θ4) = 0, and m(θ1∩θ2) = 0.12, m(θ1∩θ4) = 0.48, m(θ2∩θ3) = 0.08, m(θ3 ∩ θ4) = 0.32 (partial paradoxes/conflicts). • Suppose now one finds out that all intersections are empty (Shafer’s model), then one applies the hybrid DSm rule and one gets (index h stands here for hybrid rule): mh(θ1 ∪ θ2) = 0.12, mh(θ1 ∪ θ4) = 0.48, mh(θ2 ∪ θ3) = 0.08 and mh(θ3 ∪ θ4) = 0.32. 2.6.2 Generalization of Zadeh’s example with Θ = {θ1, θ2, θ3} Let’s consider 0 < ²1, ²2 < 1 be two very tiny positive numbers (close to zero), the frame of discernment be Θ = {θ1, θ2, θ3}, have two experts (independent sources of evidence s1 and s2) giving the belief masses m1(θ1) = 1 − ²1 m1(θ2) = 0 m1(θ3) = ²1 16 Jean Dezert and Florentin Smarandache - An introduction to DSmT m2(θ1) = 0 m2(θ2) = 1 − ²2 m2(θ3) = ²2 From now on, we prefer to use matrices to describe the masses, i.e. [ 1 − ²1 0 ²1 0 1 − ²2 ²2 ] • Using Dempster’s rule of combination, one gets m(θ3) = (²1²2) (1 − ²1) · 0 + 0 · (1 − ²2) + ²1²2 = 1 which is absurd (or at least counter-intuitive). Note that whatever posi- tive values for ²1, ²2 are, Dempster’s rule of combination provides always the same result (one) which is abnormal. The only acceptable and cor- rect result obtained by Dempster’s rule is really obtained only in the trivial case when ²1 = ²2 = 1, i.e. when both sources agree in θ3 with certainty which is obvious. • Using the DSm rule of combination based on free-DSm model, one gets m(θ3) = ²1²2, m(θ1 ∩ θ2) = (1 − ²1)(1 − ²2), m(θ1 ∩ θ3) = (1 − ²1)²2, m(θ2 ∩ θ3) = (1 − ²2)²1 and the others are zero which appears more reliable/trustable. • Going back to Shafer’s model and using the hybrid DSm rule of combi- nation, one gets m(θ3) = ²1²2, m(θ1 ∪θ2) = (1−²1)(1−²2), m(θ1 ∪θ3) = (1 − ²1)²2, m(θ2 ∪ θ3) = (1 − ²2)²1 and the others are zero. Note that in the special case when ²1 = ²2 = 1/2, one has m1(θ1) = 1/2 m1(θ2) = 0 m1(θ3) = 1/2 m2(θ1) = 0 m2(θ2) = 1/2 m2(θ3) = 1/2 Dempster’s rule of combinations still yields m(θ3) = 1 while the hybrid DSm rule based on the same Shafer’s model yields now m(θ3) = 1/4, m(θ1 ∪ θ2) = 1/4, m(θ1 ∪ θ3) = 1/4, m(θ2 ∪ θ3) = 1/4 which is normal. 17 Jean Dezert and Florentin Smarandache - An introduction to DSmT 2.6.3 Comparison with Smets, Yager and Dubois & Prade rules We compare the results provided by DSmT rules and the main common rules of combination on the following very simple numerical example where only 2 independent sources (a priori assumed equally reliable) are involved and providing their belief initially on the 3D frame Θ = {θ1, θ2, θ3}. It is assumed in this example that Shafer’s model holds and thus the belief assignments m1(.) and m2(.) do not commit belief to internal conflicting information. m1(.) and m2(.) are chosen as follows: m1(θ1) = 0.1 m1(θ2) = 0.4 m1(θ3) = 0.2 m1(θ1 ∪ θ2) = 0.3 m2(θ1) = 0.5 m2(θ2) = 0.1 m2(θ3) = 0.3 m2(θ1 ∪ θ2) = 0.1 These belief masses are usually represented in the form of a belief mass matrix M given by M = [ 0.1 0.4 0.2 0.3 0.5 0.1 0.3 0.1 ] (9) where index i for the rows corresponds to the index of the source no. i and the indexes j for columns of M correspond to a given choice for enumerating the focal elements of all sources. In this particular example, index j = 1 cor- responds to θ1, j = 2 corresponds to θ2, j = 3 corresponds to θ3 and j = 4 corresponds to θ1 ∪ θ2. Now let’s imagine that one finds out that θ3 is actually truly empty because some extra and certain knowledge on θ3 is received by the fusion center. As example, θ1, θ2 and θ3 may correspond to three suspects (potential murders) in a police investigation, m1(.) and m2(.) corresponds to two reports of indepen- dent witnesses, but it turns out that finally θ3 has provided a strong alibi to the criminal police investigator once arrested by the policemen. This situation corresponds to set up a hybrid model M with the constraint θ3 M= ∅. Let’s examine the result of the fusion in such situation obtained by the Smets’, Yager’s, Dubois & Prade’s and hybrid DSm rules of combinations. First note that, based on the free DSm model, one would get by applying the 18 Jean Dezert and Florentin Smarandache - An introduction to DSmT classic DSm rule (denoted here by index DSmC) the following fusion result mDSmC (θ1) = 0.21 mDSmC (θ2) = 0.11 mDSmC (θ3) = 0.06 mDSmC (θ1 ∪ θ2) = 0.03 mDSmC (θ1 ∩ θ2) = 0.21 mDSmC (θ1 ∩ θ3) = 0.13 mDSmC (θ2 ∩ θ3) = 0.14 mDSmC (θ3 ∩ (θ1 ∪ θ2)) = 0.11 But because of the exclusivity constraints (imposed here by the use of Shafer’s model and by the non-existential constraint θ3 M = ∅), the total con- flicting mass is actually given by k12 = 0.06 + 0.21 + 0.13 + 0.14 + 0.11 = 0.65. • If one applies Dempster’s rule [22] (denoted here by index DS), one gets: mDS(∅) = 0 mDS(θ1) = 0.21/[1 − k12] = 0.21/[1 − 0.65] = 0.21/0.35 = 0.600000 mDS(θ2) = 0.11/[1 − k12] = 0.11/[1 − 0.65] = 0.11/0.35 = 0.314286 mDS(θ1 ∪ θ2) = 0.03/[1 − k12] = 0.03/[1 − 0.65] = 0.03/0.35 = 0.085714 • If one applies Smets’ rule [39, 40] (i.e. the non normalized version of Dempster’s rule with the conflicting mass transferred onto the empty set), one gets: mS(∅) = m(∅) = 0.65 (conflicting mass) mS(θ1) = 0.21 mS(θ2) = 0.11 mS(θ1 ∪ θ2) = 0.03 • If one applies Yager’s rule [48, 49, 50], one gets: mY (∅) = 0 mY (θ1) = 0.21 mY (θ2) = 0.11 mY (θ1 ∪ θ2) = 0.03 + k12 = 0.03 + 0.65 = 0.68 19 Jean Dezert and Florentin Smarandache - An introduction to DSmT • If one applies Dubois & Prade’s rule [10], one gets because θ3 M= ∅ : mDP (∅) = 0 (by definition of Dubois & Prade’s rule) mDP (θ1) = [m1(θ1)m2(θ1) + m1(θ1)m2(θ1 ∪ θ2) + m2(θ1)m1(θ1 ∪ θ2)] + [m1(θ1)m2(θ3) + m2(θ1)m1(θ3)] = [0.1 · 0.5 + 0.1 · 0.1 + 0.5 · 0.3] + [0.1 · 0.3 + 0.5 · 0.2] = 0.21 + 0.13 = 0.34 mDP (θ2) = [0.4 · 0.1 + 0.4 · 0.1 + 0.1 · 0.3] + [0.4 · 0.3 + 0.1 · 0.2] = 0.11 + 0.14 = 0.25 mDP (θ1 ∪ θ2) = [m1(θ1 ∪ θ2)m2(θ1 ∪ θ2)] + [m1(θ1 ∪ θ2)m2(θ3) + m2(θ1 ∪ θ2)m1(θ3)] + [m1(θ1)m2(θ2) + m2(θ1)m1(θ2)] = [0.30.1] + [0.3 · 0.3 + 0.1 · 0.2] + [0.1 · 0.1 + 0.5 · 0.4] = [0.03] + [0.09 + 0.02] + [0.01 + 0.20] = 0.03 + 0.11 + 0.21 = 0.35 Now if one adds up the masses, one gets 0+0.34+0.25+0.35 = 0.94 which is less than 1. Therefore Dubois & Prade’s rule of combination does not work when a singleton, or an union of singletons, becomes empty (in a dynamic fusion problem). The products of such empty-element columns of the mass matrix M are lost; this problem is fixed in DSmT by the sum S2(.) in (5) which transfers these products to the total or partial ignorances. 20 Jean Dezert and Florentin Smarandache - An introduction to DSmT • Finally, if one applies DSmH rule, one gets because θ3 M= ∅ : mDSmH (∅) = 0 (by definition of DSmH) mDSmH (θ1) = 0.34 (same as mDP (θ1)) mDSmH (θ2) = 0.25 (same as mDP (θ2)) mDSmH (θ1 ∪ θ2) = [m1(θ1 ∪ θ2)m2(θ1 ∪ θ2)] + [m1(θ1 ∪ θ2)m2(θ3) + m2(θ1 ∪ θ2)m1(θ3)] + [m1(θ1)m2(θ2) + m2(θ1)m1(θ2)] + [m1(θ3)m2(θ3)] = 0.03 + 0.11 + 0.21 + 0.06 = 0.35 + 0.06 = 0.41 6= mDP (θ1 ∪ θ2) We can easily verify that mDSmH (θ1)+mDSmH (θ2)+mDSmH (θ1∪θ2) = 1. In this example, using the hybrid DSm rule, one transfers the product of the empty-element θ3 column, m1(θ3)m2(θ3) = 0.2 · 0.3 = 0.06, to mDSmH (θ1 ∪ θ2), which becomes equal to 0.35 + 0.06 = 0.41. Clearly, DSmH rule doesn’t provide the same result as Dubois and Prade’s rule, but only when working on static frames of discernment (restricted cases). 2.7 Fusion of imprecise beliefs In many fusion problems, it seems very difficult (if not impossible) to have pre- cise sources of evidence generating precise basic belief assignments (especially when belief functions are provided by human experts), and a more flexible plau- sible and paradoxical theory supporting imprecise information becomes neces- sary. In the previous sections, we presented the fusion of precise uncertain and conflicting/paradoxical generalized basic belief assignments (gbba) in DSmT framework. We mean here by precise gbba, basic belief functions/masses m(.) defined precisely on the hyper-power set DΘ where each mass m(X), where X belongs to DΘ, is represented by only one real number belonging to [0, 1] such that ∑ X∈DΘ m(X) = 1. In this section, we present the DSm fusion rule for dealing with admissible imprecise generalized basic belief assignments mI (.) defined as real subunitary intervals of [0, 1], or even more general as real sub- unitary sets [i.e. sets, not necessarily intervals]. An imprecise belief assignment mI (.) over DΘ is said admissible if and only if there exists for every X ∈ DΘ at least one real number m(X) ∈ mI (X) such 21 Jean Dezert and Florentin Smarandache - An introduction to DSmT that ∑ X∈DΘ m(X) = 1. The idea to work with imprecise belief structures represented by real subset intervals of [0, 1] is not new and has been inves- tigated in [14, 4, 5] and references therein. The proposed works available in the literature, upon our knowledge were limited only to sub-unitary interval combination in the framework of Transferable Belief Model (TBM) developed by Smets [39, 40]. We extend the approach of Lamata & Moral and Denœux based on subunitary interval-valued masses to subunitary set-valued masses; therefore the closed intervals used by Denœux to denote imprecise masses are generalized to any sets included in [0,1], i.e. in our case these sets can be unions of (closed, open, or half-open/half-closed) intervals and/or scalars all in [0, 1]. Here, the proposed extension is done in the context of DSmT frame- work, although it can also apply directly to fusion of imprecise belief structures within TBM as well if the user prefers to adopt TBM rather than DSmT. Before presenting the general formula for the combination of generalized imprecise belief structures, we remind the following set operators involved in the DSm fusion formulas. Several numerical examples are given in the chapter 6 of [29]. • Addition of sets S1 ¢ S2 = S2 ¢ S1 , {x | x = s1 + s2, s1 ∈ S1, s2 ∈ S2} • Subtraction of sets S1 ¯ S2 , {x | x = s1 − s2, s1 ∈ S1, s2 ∈ S2} • Multiplication of sets S1 � S2 , {x | x = s1 · s2, s1 ∈ S1, s2 ∈ S2} • Division of sets: If 0 doesn’t belong to S2, S1 � S2 , {x | x = s1/s2, s1 ∈ S1, s2 ∈ S2} 22 Jean Dezert and Florentin Smarandache - An introduction to DSmT 2.7.1 DSm rule of combination for imprecise beliefs We present the generalization of the DSm rules to combine any type of im- precise belief assignment which may be represented by the union of several sub-unitary (half-) open intervals, (half-)closed intervals and/or sets of points belonging to [0,1]. Several numerical examples are also given. In the sequel, one uses the notation (a, b) for an open interval, [a, b] for a closed interval, and (a, b] or [a, b) for a half open and half closed interval. From the previous operators on sets, one can generalize the DSm rules (classic and hybrid) from scalars to sets in the following way [29] (chap. 6): ∀A 6= ∅ ∈ DΘ, mI (A) = ∑ X1,X2,...,Xk∈DΘ (X1∩X2∩...∩Xk)=A ∏ i=1,...,k mIi (Xi) (10) where ∑ and ∏ represent the summation, and respectively product, of sets. Similarly, one can generalize the hybrid DSm rule from scalars to sets in the following way: mIDSmH (A) = m I M(Θ)(A) , φ(A) � [ SI1 (A) ¢ S I 2 (A) ¢ S I 3 (A) ] (11) where all sets involved in formulas are in the canonical form and φ(A) is the characteristic non emptiness function of the set A and SI1 (A), S I 2 (A) and S I 3 (A) are defined by SI1 (A) , ∑ X1,X2,...,Xk∈DΘ X1∩X2∩...∩Xk=A ∏ i=1,...,k mIi (Xi) (12) SI2 (A) , ∑ X1,X2,...,Xk∈∅ [U=A]∨[(U∈∅)∧(A=It)] ∏ i=1,...,k mIi (Xi) (13) SI3 (A) , ∑ X1,X2,...,Xk∈DΘ X1∪X2∪...∪Xk=A X1∩X2∩...∩Xk∈∅ ∏ i=1,...,k mIi (Xi) (14) 23 Jean Dezert and Florentin Smarandache - An introduction to DSmT In the case when all sets are reduced to points (numbers), the set operations be- come normal operations with numbers; the sets operations are generalizations of numerical operations. When imprecise belief structures reduce to precise belief structure, DSm rules (10) and (11) reduce to their precise version (4) and (5) respectively. 3 Proportional Conflict Redistribution rule Instead of applying a direct transfer of partial conflicts onto partial uncertain- ties as with DSmH, the idea behind the Proportional Conflict Redistribution (PCR) rule [31, 33] is to transfer (total or partial) conflicting masses to non- empty sets involved in the conflicts proportionally with respect to the masses assigned to them by sources as follows: 1. calculation the conjunctive rule of the belief masses of sources; 2. calculation the total or partial conflicting masses; 3. redistribution of the (total or partial) conflicting masses to the non-empty sets involved in the conflicts proportionally with respect to their masses assigned by the sources. The way the conflicting mass is redistributed yields actually several versions of PCR rules. These PCR fusion rules work for any degree of conflict, for any DSm models (Shafer’s model, free DSm model or any hybrid DSm model) and both in DST and DSmT frameworks for static or dynamical fusion situations. We present below only the most sophisticated proportional conflict redistri- bution rule denoted PCR5 in [31, 33]. PCR5 rule is what we feel the most efficient PCR fusion rule developed so far. This rule redistributes the partial conflicting mass to the elements involved in the partial conflict, considering the conjunctive normal form of the partial conflict. PCR5 is what we think the most mathematically exact redistribution of conflicting mass to non-empty sets following the logic of the conjunctive rule. It does a better redistribution of the conflicting mass than Dempster’s rule since PCR5 goes backwards on the tracks of the conjunctive rule and redistributes the conflicting mass only to the sets involved in the conflict and proportionally to their masses put in the conflict. PCR5 rule is quasi-associative and preserves the neutral impact of the vacuous belief assignment because in any partial conflict, as well in the 24 Jean Dezert and Florentin Smarandache - An introduction to DSmT total conflict (which is a sum of all partial conflicts), the conjunctive normal form of each partial conflict does not include Θ since Θ is a neutral element for intersection (conflict), therefore Θ gets no mass after the redistribution of the conflicting mass. We have proved in [33] the continuity property of the fusion result with continuous variations of bba’s to combine. 3.1 PCR formulas The PCR5 formula for the combination of two sources (s = 2) is given by: mP CR5(∅) = 0 and ∀X ∈ GΘ \ {∅} mP CR5(X) = m12(X) + ∑ Y ∈GΘ\{X} X∩Y =∅ [ m1(X) 2m2(Y ) m1(X) + m2(Y ) + m2(X) 2m1(Y ) m2(X) + m1(Y ) ] (15) where all sets involved in formulas are in canonical form and where GΘ cor- responds to classical power set 2Θ if Shafer’s model is used, or to a con- strained hyper-power set DΘ if any other hybrid DSm model is used instead, or to the super-power set SΘ if the minimal refinement Θref of Θ is used; m12(X) ≡ m∩(X) corresponds to the conjunctive consensus on X between the s = 2 sources and where all denominators are different from zero. If a denominator is zero, that fraction is discarded. A general formula of PCR5 for the fusion of s > 2 sources has been proposed in [33], but a more intuitive PCR formula (denoted PCR6) which provides good results in practice has been proposed by Martin and Osswald in [33] (pages 69-88) and is given by: mP CR6(∅) = 0 and ∀X ∈ GΘ \ {∅} mP CR6(X) = m12...s(X)+ s∑ i=1 mi(X) 2 ∑ s−1∩ k=1 Yσi(k) ∩X≡∅ (Yσi(1) ,...,Yσi(s−1))∈(G Θ)s−1   s−1∏ j=1 mσi(j)(Yσi(j)) mi(X)+ s−1∑ j=1 mσi(j)(Yσi(j))   (16) 25 Jean Dezert and Florentin Smarandache - An introduction to DSmT where σi counts from 1 to s avoiding i: { σi(j) = j if j < i, σi(j) = j + 1 if j ≥ i, (17) Since Yi is a focal element of expert/source i, mi(X)+ s−1∑ j=1 mσi(j)(Yσi(j)) 6= 0; the belief mass assignment m12...s(X) ≡ m∩(X) corresponds to the conjunctive consensus on X between the s > 2 sources. For two sources (s = 2), PCR5 and PCR6 formulas coincide. 3.2 Examples • Example 1: Let’s take Θ = {A, B} of exclusive elements (Shafer’s model), and the following bba’s: A B A ∪ B m1(.) 0.6 0 0.4 m2(.) 0 0.3 0.7 m∩(.) 0.42 0.12 0.28 The conflicting mass is k12 = m∩(A ∩ B) and equals the sum of partial conflicts m1(A)m2(B)+m1(B)m2(A) = 0.18. Since A and B are the only focal elements involved in the conflict. According to the PCR5 hypothe- sis, only A and B deserve a part of the conflicting mass and A∪B do not deserve. With PCR5, one redistributes the conflicting mass k12 = 0.18 to A and B proportionally with the masses m1(A) and m2(B) assigned to A and B respectively. Here are the results obtained from Dempster’s rule, DSmH and PCR5: A B A ∪ B mDS 0.512 0.146 0.342 mDSmH 0.420 0.120 0.460 mP CR5 0.540 0.180 0.280 • Example 2: Let’s modify example 1 and consider 26 Jean Dezert and Florentin Smarandache - An introduction to DSmT A B A ∪ B m1(.) 0.6 0 0.4 m2(.) 0.2 0.3 0.5 m∩(.) 0.50 0.12 0.20 The conflicting mass k12 = m∩(A ∩ B) as well as the distribution coef- ficients for the PCR5 remains the same as in the previous example but one gets now A B A ∪ B mDS 0.609 0.146 0.231 mDSmH 0.500 0.120 0.380 mP CR5 0.620 0.180 0.200 • Example 3: Let’s modify example 2 and consider A B A ∪ B m1(.) 0.6 0.3 0.1 m2(.) 0.2 0.3 0.5 m∩(.) 0.44 0.27 0.05 The conflicting mass k12 = 0.24 = m1(A)m2(B) + m1(B)m2(A) = 0.24 is now different from previous examples, which means that m2(A) = 0.2 and m1(B) = 0.3 did make an impact on the conflict. Therefore A and B are the only focal elements involved in the conflict and thus only A and B deserve a part of the conflicting mass. PCR5 redistributes the partial conflicting mass 0.18 to A and B proportionally with the masses m1(A) and m2(B) and also the partial conflicting mass 0.06 to A and B proportionally with the masses m2(A) and m1(B). After all derivations (see [11] for details), one finally gets: A B A ∪ B mDS 0.579 0.355 0.066 mDSmH 0.440 0.270 0.290 mP CR5 0.584 0.366 0.050 27 Jean Dezert and Florentin Smarandache - An introduction to DSmT One clearly sees that mDS(A ∪ B) gets some mass from the conflicting mass although A ∪ B does not deserve any part of the conflicting mass (according to PCR5 hypothesis) since A∪B is not involved in the conflict (only A and B are involved in the conflicting mass). Dempster’s rule appears to us less exact than PCR5 and Inagaki’s rules [13]. It can be showed [11] that Inagaki’s fusion rule (with an optimal choice of tuning parameters) can become in some cases very close to PCR5 but upon our opinion PCR5 result is more exact (at least less ad-hoc than Inagaki’s one). • Example 4 (A more concrete example): Three people, John (J), George (G), and David (D) are suspects to a murder. So the frame of discernment is Θ , {J, G, D}. Two sources m1(.) and m2(.) (witnesses) provide the following information: J G D m1 0.9 0 0.1 m2 0 0.8 0.2 We know that John and George are friends, but John and David hate each other, and similarly George and David. a) Free model, i. e. all intersections are nonempty: J ∩G 6= ∅, J ∩D 6= ∅, G ∩ D 6= ∅, J ∩ G ∩ D 6= ∅. Using the DSm classic rule one gets: J G D J ∩ G J ∩ D G ∩ D J ∩ G ∩ D mDSmC 0 0 0.02 0.72 0.18 0.08 0 So we can see that John and George together (J ∩G) are most likely to have committed the crime, since the mass mDSmC (J ∩ G) = 0.72 is the biggest resulting mass after the fusion of the two sources. In Shafer’s model, only one suspect could commit the crime, but the free and hybrid models allow two or more people to have committed the same crime - which happens in reality. b) Let’s consider the hybrid model, i. e. some intersections are empty, and others are not. According to the above statement about the relationships between the three suspects, we can deduce that J∩G 6= 28 Jean Dezert and Florentin Smarandache - An introduction to DSmT ∅, while J ∩ D = G ∩ D = J ∩ G ∩ D = ∅. Then we first apply the DSm Classic rule, and then the transfer of the conflicting masses is done with PCR5: J G D J ∩ G J ∩ D G ∩ D J ∩ G ∩ D m1 0.9 0 0.1 m2 0 0.8 0.2 mDSmC 0 0 0.02 0.72 0.18 0.08 0 Using PCR5 now we transfer m(J ∩ D) = 0.18, since J ∩ D = ∅, to J and D proportionally with 0.9 and 0.2 respectively, so J gets 0.15 and D gets 0.03 since: xJ/0.9 = z1D/0.2 = 0.18/(0.9 + 0.2) = 0.18/1.1 whence xJ = 0.9(0.18/1.1) = 0.15 and z1D = 0.2(0.18/1.1) = 0.03. Again using PCR5, we transfer m(G ∩ D) = 0.08, since G ∩ D = ∅, to G and D proportionally with 0.8 and 0.1 respectively, so G gets 0.07 and D gets 0.01 since: yG/0.8 = z2D/0.1 = 0.08/(0.8 + 0.1) = 0.08/0.9 whence yG = 0.8(0.08/0.9) = 0.07 and zD = 0.1(0.08/0.9) = 0.01. Adding we get finally: J G D J ∩ G J ∩ D G ∩ D J ∩ G ∩ D mP CR5 0.15 0.07 0.06 0.72 0 0 0 So one has a high belief that the criminals are John and George (both of them committed the crime) since m(J ∩ D) = 0.72 and it is by far the greatest fusion mass. In Shafers model, if we try to refine we get the disjoint parts: D, J ∩ G, J \ (J ∩ G), and G \ (J ∩ G), but the last two are ridiculous (what is the real/physical nature of J \ (J ∩ G) or G \ (J ∩ G) ? Half of a person(!) ?), so the refining does not work here in reality. Thats why the hybrid and free models are needed. • Example 5 (Imprecise PCR5): The PCR5 formula can naturally work also for the combination of imprecise bba’s. This has been already presented in section 1.11.8 page 49 of [33] with a numerical example to show how to apply it. This example will therefore not be reincluded here. 29 Jean Dezert and Florentin Smarandache - An introduction to DSmT 3.3 Zadeh’s example We compare here the solutions for well-known Zadeh’s example [53, 56] pro- vided by several fusion rules. A detailed presentation with more comparisons can be found in [29, 33]. Let’s consider Θ = {M, C, T} as the frame of three po- tential origins about possible diseases of a patient (M standing for meningitis, C for concussion and T for tumor), the Shafer’s model and the two following belief assignments provided by two independent doctors after examination of the same patient. m1(M ) = 0.9 m1(C) = 0 m1(T ) = 0.1 m2(M ) = 0 m2(C) = 0.9 m2(T ) = 0.1 The total conflicting mass is high since it is m1(M )m2(C) + m1(M )m2(T ) + m2(C)m1(T ) = 0.99 • with Dempster’s rule and Shafer’s model (DS), one gets the counter- intuitive result (see justifications in [53, 9, 50, 46, 29]): mDS(T ) = 1 • with Yager’s rule [50] and Shafer’s model: mY (M ∪ C ∪ T ) = 0.99 and mY (T ) = 0.01 • with DSmH and Shafer’s model: mDSmH (M ∪ C) = 0.81 mDSmH (T ) = 0.01 mDSmH (M ∪ T ) = mDSmH (C ∪ T ) = 0.09 • The Dubois & Prade’s rule (DP) [9] based on Shafer’s model provides in Zadeh’s example the same result as DSmH, because DP and DSmH coincide in all static fusion problems7. • with PCR5 and Shafer’s model: mP CR5(M ) = mP CR5(C) = 0.486 and mP CR5(T ) = 0.028. 7Indeed DP rule has been developed for static fusion only while DSmH has been developed to take into account the possible dynamicity of the frame itself and also its associated model. 30 Jean Dezert and Florentin Smarandache - An introduction to DSmT One sees that when the total conflict between sources becomes high, DSmT is able (upon authors opinion) to manage more adequately through DSmH or PCR5 rules the combination of information than Dempster’s rule, even when working with Shafer’s model - which is only a specific hybrid model. DSmH rule is in agreement with DP rule for the static fusion, but DSmH and DP rules differ in general (for non degenerate cases) for dynamic fusion while PCR5 rule is the most exact proportional conflict redistribution rule. Besides this particular example, we showed in [29] that there exist several infinite classes of counter-examples to Dempster’s rule which can be solved by DSmT. In summary, DST based on Dempster’s rule provides counter-intuitive re- sults in Zadeh’s example, or in non-Bayesian examples similar to Zadeh’s and no result when the conflict is 1. Only ad-hoc discounting techniques allow to circumvent troubles of Dempster’s rule or we need to switch to another model of representation/frame; in the later case the solution obtained doesn’t fit with the Shafer’s model one originally wanted to work with. We want also to em- phasize that in dynamic fusion when the conflict becomes high, both DST [22] and Smets’ Transferable Belief Model (TBM) [39] approaches fail to respond to new information provided by new sources. This can be easily showed by the very simple following example. Example (where TBM doesn’t respond to new information): Let Θ = {A, B, C} with the (precise) bba’s m1(A) = 0.4, m1(C) = 0.6 and m2(A) = 0.7, m2(B) = 0.3. Then one gets 8 with Dempster’s rule, Smets’ TBM (i.e. the non-normalized version of Dempster’s combination), DSmH and PCR5: m12DS(A) = 1, m 12 T BM (A) = 0.28, m 12 T BM (∅) = 0.72,    m12DSmH (A) = 0.28 m12DSmH (A ∪ B) = 0.12 m12DSmH (A ∪ C) = 0.42 m12DSmH (B ∪ C) = 0.18 and    m12P CR5(A) = 0.574725 m12P CR5(B) = 0.111429 m12P CR5(C) = 0.313846 Now let’s consider a temporal fusion problem and introduce a third source m3(.) with m3(B) = 0.8 and m3(C) = 0.2. Then one sequentially combines the results obtained by m12T BM (.), m 12 DS(.), m 12 DSmH (.) and m 12 P CR(.) with the 8We introduce here explicitly the indexes of sources in the fusion result since more than two sources are considered in this example. 31 Jean Dezert and Florentin Smarandache - An introduction to DSmT new evidence m3(.) and one sees that m (12)3 DS becomes not defined (division by zero) and m (12)3 T BM (∅) = 1 while (DSmH) and (PCR5) provide    m (12)3 DSmH (B) = 0.240 m (12)3 DSmH (C) = 0.120 m (12)3 DSmH (A ∪ B) = 0.224 m (12)3 DSmH (A ∪ C) = 0.056 m (12)3 DSmH (A ∪ B ∪ C) = 0.360 and    m (12)3 P CR5(A) = 0.277490 m (12)3 P CR5(B) = 0.545010 m (12)3 P CR5(C) = 0.177500 When the mass committed to empty set becomes one at a previous temporal fusion step, then both DST and TBM do not respond to new information9. Let’s continue the example and consider a fourth source m4(.) with m4(A) = 0.5, m4(B) = 0.3 and m4(C) = 0.2. Then it is easy to see that m ((12)3)4 DS (.) is not defined since at previous step m (12)3 DS (.) was already not defined, and that m ((12)3)4 T BM (∅) = 1 whatever m4(.) is because at the previous fusion step one had m (12)3 T BM (∅) = 1. Therefore for a number of sources n ≥ 2, DST and TBM approaches do not respond to new information incoming in the fusion process while both (DSmH) and (PCR5) rules respond to new information. To make DST and/or TBM working properly in such cases, it is necessary to introduce ad-hoc temporal discounting techniques which are not necessary to introduce if DSmT is adopted. If there are good reasons to introduce temporal discounting, there is obviously no difficulty to apply the DSm fusion of these discounted sources. An analysis of this behavior for target type tracking is presented in [7, 33]. 4 Uniform and partially uniform redistribu- tion rules The principles of Uniform Redistribution Rule (URR) and Partially Uniform Redistribution Rule (PURR) have been proposed in 2006 with examples in [32]. 9Actually Dempster’s rule doesn’t respond also to new compatible information/bba as soon as a total mass of belief is already committed by a source to only one focal element. For example, if one considers Θ = {A, B} with Shafer’s model (A∩B = ∅) and with m1(A) = 1, m2(A) = 0.2 and m2(B) = 0.8, then Dempster’s rule always provides mDS (A) = 1 whatever are the values taken by m2(A) > 0 and m2(B) > 0. 32 Jean Dezert and Florentin Smarandache - An introduction to DSmT The Uniform Redistribution Rule consists in redistributing the total con- flicting mass k12 to all focal elements of G Θ generated by the consensus op- erator. This way of redistributing mass is very simple and URR is different from Dempster’s rule of combination, because Dempster’s rule redistributes the total conflict proportionally with respect to the masses resulted from the conjunctive rule of non-empty sets. PCR5 rule presented previously does pro- portional redistributions of partial conflicting masses to the sets involved in the conflict. The URR formula for two sources is given by: ∀A 6= ∅ m12U RR(A) = m12(A) + 1 n12 ∑ X1,X2∈GΘ X1∩X2=∅ m1(X1)m2(X2) (18) where m12(A) is the result of the conjunctive rule applied to belief assignments m1(.) and m2(.), and n12 = Card{Z ∈ GΘ, m1(Z) 6= 0 or m2(Z) 6= 0}. For s ≥ 2 sources to combine: ∀A 6= ∅, one has m12...sU RR(A) = m12...s(A) + 1 n12...s ∑ X1,X2,...,Xs∈GΘ X1∩X2∩...∩Xs=∅ s∏ i=1 m1(Xi) (19) where m12...s(A) is the result of the conjunctive rule applied to mi(.), for all i ∈ {1, 2, . . . , s} and n12...s = Card{Z ∈ GΘ, m1(Z) 6= 0 or m2(Z) 6= 0 or . . . or ms(Z) 6= 0} As alternative (modified version of URR), we can also consider the cardinal of the ensemble of sets whose masses resulted from the conjunctive rule are non-null, i.e. the cardinality of the core of conjunctive consensus: nc12...s = Card{Z ∈ GΘ, m12...s(Z) 6= 0} It is also possible to do a uniformly partial redistribution, i.e. to uniformly redistribute the conflicting mass only to the sets involved in the conflict. For example, if m12(A∩B) = 0.08 and A∩B = ∅, then 0.08 is equally redistributed to A and B only, supposing A and B are both non-empty, so 0.04 assigned to A and 0.04 to B. 33 Jean Dezert and Florentin Smarandache - An introduction to DSmT The Partially Uniform Redistribution Rule (PURR) for two sources is defined as follows: ∀A 6= ∅ m12P U RR(A) = m12(A) + 1 2 ∑ X1,X2∈GΘ X1∩X2=∅ X1=A or X2=A m1(X1)m2(X2) (20) where m12(A) is the result of the conjunctive rule applied to belief assignments m1(.) and m2(.). For s ≥ 2 sources to combine: ∀A 6= ∅, one has m12...sP U RR(A) = m12...s(A) + 1 s ∑ X1,X2,...,Xs∈GΘ X1∩X2∩...∩Xs=∅ at leat one Xj =A,j∈{1,...,s} CardA({X1, . . . , Xs}) s∏ i=1 m1(Xi) (21) where CardA({X1, . . . , Xs}) is the number of A’s occurring in {X1, X2, . . . , Xs}. If A = ∅, m12P U RR(A) = 0 and m12...sP U RR(A) = 0. These rules have a low computation cost with respect to Proportional Con- flict Redistribution (PCR) rules developed in the DSmT framework and they preserve the neutrality of the vacuous belief assignment (VBA) since any bba m1(.) combined with VBA defined on any frame Θ = {θ1, . . . , θn} by mV BA(θ1 ∪ . . .∪θn) = 1, using the conjunctive rule, gives m1(.), so no conflict- ing mass is needed to transfer. Of course these rules are very easy to implement but from a theoretical point of view they remain less precise in their transfer of conicting beliefs since they do not take into account the proportional redistri- bution with respect to the mass of each set involved in the conict. Reasonably, URR or PURR cannot outperform PCR5 but they may hopefully could appear as good enough in some specic fusion problems when the level of total conict is not important. PURR does a more rened redistribution that URR and MURR but it requires a little more calculation. 34 Jean Dezert and Florentin Smarandache - An introduction to DSmT 5 RSC Fusion rules In this section, we briefly recall a new class of fusion rules based on the be- lief redistribution to subsets or complements and denoted CRSC (standing for Class of Redistribution rules to Subsets or Complements) for short. This class is presented in details in [35] with several examples. Let m1(.) and m2(.) be two normalized basic belief assignments (bbas) defined10 from SΘ to [0, 1]. We use the conjunctive rule to first combine m1(.) with m2(.) to get m∩(.) and then the mass of conflict say m∩(X∩Y ) = 0, when X ∩Y = ∅ or even when X ∩Y is different from the empty set is redistributed to subsets or complements in many ways (see [35] for details). The new class of fusion rule (denoted CRSCc) for transferring the conflicting masses only is defined for A ∈ SΘ \ {∅, It} by: mCRSCc (A) = m∩(A) + [α · m∩(A) + β · Card(A) + γ · f (A)]· · ∑ X, Y ∈ SΘ X ∩ Y = ∅ A ⊆ M m1(X)m2(Y )∑ Z∈SΘ,Z⊆M [α · m∩(Z) + β · Card(Z) + γ · f (Z)] (22) where It = θ1∪θ2∪. . .∪θn represents the total ignorance when Θ = {θ1, . . . , θn}. M can be c(X ∪ Y ) (the complement of X ∪ Y ), or a subset of c(X ∪ Y ), or X ∪ Y , or a subset of X ∪ Y ; α, β, γ ∈ {0, 1} but α + β + γ 6= 0; in a weighted way we can take α, β, γ ∈ [0, 1] also with α + β + γ 6= 0; f (X) is a function of X, i.e. another parameter that the mass of X is directly proportionally with respect to; Card(X) is the cardinal of X. The mass of belief mCRSCc (It) committed to the total ignorance is given by: mCRSCc (It) = m∩(It) + ∑ X, Y ∈ SΘ {X ∩ Y = ∅ and M = ∅} or{X ∩ Y = ∅ and Den(Z) = 0} m1(X)m2(Y ) (23) 10Since these rules use explicitely the complementation operator c(.), they apply only with the super-power set SΘ or on 2Θ depending on the underlying model chosen for the frame Θ. 35 Jean Dezert and Florentin Smarandache - An introduction to DSmT where Den(Z) , ∑ Z∈SΘ,Z⊆M [α · m∩(Z) + β · Card(Z) + γ · f (Z)]. A more general formula for the redistribution of conflict and non-conflict to subsets or complements class of rules for the fusion of masses of belief for two sources of evidence is defined A ∈ (SΘ r Snon∅∩ ) r {∅, Θ} by: mCRSC (A) = m∩(A) + ∑ X, Y ∈ SΘ {X ∩ Y = ∅, A ∈ T (X, Y )} or {X ∩ Y ∈ Snon∅∩,r , A ∈ T ′(X, Y )} f (A) m1(X)m2(Y )∑ Z∈T (X,Y ) f (Z) (24) and for A = It: mCRSC (It) = m∩(It) + ∑ X, Y ∈ SΘ X ∩ Y = ∅, {T (X, Y ) = ∅ or ∑ Z∈T (X,Y ) f (Z) = 0} m1(X)m2(Y ) (25) where S∩ = {X ∈ SΘ|X = Y ∩Z, where Y, Z ∈ SΘr{∅}}, all propositions are expressed in their canonical form and where Xcontains at least an ∩ symbol in its expression; S∅∩ be the set of all empty intersections from S∩ (i.e. the set of exclusivity constraints), and Snon∅∩ the set of all non-empty intersections from S∩. S non∅ ∩,r is the set of all non-empty intersections from S non∅ ∩ whose masses are redistributed to other sets/propositions. The set Snon∅∩,r highly depends on the model for the frame of the application under consideration. f (.) is a mapping from SΘ to R+. For example, we can choose f (X) = m∩(X), f (X) = |X|, fT (X) = |X||T (X,Y )|, or f (x) = m∩(X) + |X|, etc. The function T specifies a subset of SΘ, for example T (X, Y ) = {c(X ∪ Y )}, or T (X, Y ) = {X ∪ Y } or can specify a set of subsets of SΘ. For example, T (X, Y ) = {A ⊂ c(X ∪ Y )}, or T (X, Y ) = {A ⊂ X ∪ Y }. The function T ′ is a subset of SΘ, for example T ′(X, Y ) = {X ∪ Y }, or T ′ is a subset of X ∪ Y , etc. It is important to highlight that in formulas (22)-(23) one transfers only the conflicting masses, whereas the formulas (24)-(25) are more general since one transfers the conflicting masses or the non-conflicting masses as well depend- ing on the preferences of the fusion system designer. The previous formulas have been directly extended for any s ≥ 2 sources of evidence in [35]. All 36 Jean Dezert and Florentin Smarandache - An introduction to DSmT denominators in these CRSC formulas are naturally supposed different from zero. It is worth to note also that the extensions of these rules for including the reliabilities of the sources are also presented in [35]. 6 Generalized pignistic transformation (GPT) 6.1 The classical pignistic transformation We follow here Philippe Smets’ vision which considers the management of in- formation as a two 2-levels process: credal (for combination of evidences) and pignistic11 (for decision-making) , i.e ”when someone must take a decision, he/she must then construct a probability function derived from the belief func- tion that describes his/her credal state. This probability function is then used to make decisions” [38] (p. 284). One obvious way to build this probability function corresponds to the so-called Classical Pignistic Transformation (CPT) defined in DST framework (i.e. based on the Shafer’s model assumption) as [40]: BetP{A} = ∑ X∈2Θ |X ∩ A| |X| m(X) (26) where |A| denotes the cardinality of A (with convention |∅|/|∅| = 1, to define BetP{∅}). Decisions are achieved by computing the expected utilities of the acts using the subjective/pignistic BetP{.} as the probability function needed to compute expectations. Usually, one uses the maximum of the pignistic probability as decision criterion. The maximum of BetP{.} is often considered as a prudent betting decision criterion between the two other alternatives (max of plausibility or max. of credibility which appears to be respectively too optimistic or too pessimistic). It is easy to show that BetP{.} is indeed a probability function (see [39]). 6.2 Notion of DSm cardinality One important notion involved in the definition of the Generalized Pignistic Transformation (GPT) is the DSm cardinality. The DSm cardinality of any 11Pignistic terminology has been coined by Philippe Smets and comes from pignus, a bet in Latin. 37 Jean Dezert and Florentin Smarandache - An introduction to DSmT element A of hyper-power set DΘ, denoted CM(A), corresponds to the number of parts of A in the corresponding fuzzy/vague Venn diagram of the problem (model M) taking into account the set of integrity constraints (if any), i.e. all the possible intersections due to the nature of the elements θi. This intrinsic cardinality depends on the model M (free, hybrid or Shafer’s model). M is the model that contains A, which depends both on the dimension n = |Θ| and on the number of non-empty intersections present in its associated Venn diagram (see [29] for details ). The DSm cardinality depends on the cardinal of Θ = {θ1, θ2, . . . , θn} and on the model of DΘ (i.e., the number of intersections and between what elements of Θ - in a word the structure) at the same time; it is not necessarily that every singleton, say θi, has the same DSm cardinal, because each singleton has a different structure; if its structure is the sim- plest (no intersection of this elements with other elements) then CM(θi) = 1, if the structure is more complicated (many intersections) then CM(θi) > 1; let’s consider a singleton θi: if it has 1 intersection only then CM(θi) = 2, for 2 intersections only CM(θi) is 3 or 4 depending on the model M, for m intersec- tions it is between m + 1 and 2m depending on the model; the maximum DSm cardinality is 2n−1 and occurs for θ1 ∪ θ2 ∪ . . . ∪ θn in the free model Mf ; sim- ilarly for any set from DΘ: the more complicated structure it has, the bigger is the DSm cardinal; thus the DSm cardinality measures the complexity of an element from DΘ, which is a nice characterization in our opinion; we may say that for the singleton θi not even |Θ| counts, but only its structure (= how many other singletons intersect θi). Simple illustrative examples are given in Chapter 3 and 7 of [29]. One has 1 ≤ CM(A) ≤ 2n − 1. CM(A) must not be confused with the classical cardinality |A| of a given set A (i.e. the number of its distinct elements) - that’s why a new notation is necessary here. CM(A) is very easy to compute by programming from the algorithm of generation of DΘ given explicated in [29]. 6.3 The Generalized Pignistic Transformation To take a rational decision within DSmT framework, it is necessary to gener- alize the Classical Pignistic Transformation in order to construct a pignistic probability function from any generalized basic belief assignment m(.) drawn from the DSm rules of combination. Here is the simplest and direct extension 38 Jean Dezert and Florentin Smarandache - An introduction to DSmT of the CPT to define the Generalized Pignistic Transformation: ∀A ∈ DΘ, BetP{A} = ∑ X∈DΘ CM(X ∩ A) CM(X) m(X) (27) where CM(X) denotes the DSm cardinal of proposition X for the DSm model M of the problem under consideration. The decision about the solution of the problem is usually taken by the maximum of pignistic probability function BetP{.}. Let’s remark the close ressemblance of the two pignistic transformations (26) and (27). It can be shown that (27) reduces to (26) when the hyper-power set DΘ reduces to classical power set 2Θ if we adopt Shafer’s model. But (27) is a generalization of (26) since it can be used for computing pignistic probabilities for any models (including Shafer’s model). It has been proved in [29] (Chap. 7) that BetP{.} defined in (27) is indeed a probability distribution. In the following section, we introduce a new alternative to BetP which is presented in details in [35]. 7 The DSmP transformation In the theories of belief functions, the mapping from the belief to the probabil- ity domain is a controversial issue. The original purpose of such mappings was to make (hard) decision, but contrariwise to erroneous widespread idea/claim, this is not the only interest for using such mappings nowadays. Actually the probabilistic transformations of belief mass assignments (as the pignistic transformation mentioned previously) are for example very useful in modern multitarget multisensor tracking systems (or in any other systems) where one deals with soft decisions (i.e. where all possible solutions are kept for state estimation with their likelihoods). For example, in a Multiple Hypotheses Tracker using both kinematical and attribute data, one needs to compute all probabilities values for deriving the likelihoods of data association hypotheses and then mixing them altogether to estimate states of targets. Therefore, it is very relevant to use a mapping which provides a highly probabilistic informa- tion content (PIC) for expecting better performances. In this section, we briefly recall a new probabilistic transformation, denoted DSmP and introduced in [8] which is explained in details in [35]. DSmP is 39 Jean Dezert and Florentin Smarandache - An introduction to DSmT straight and different from other transformations. The basic idea of DSmP consists in a new way of proportionalizations of the mass of each partial igno- rance such as A1 ∪ A2 or A1 ∪ (A2 ∩ A3) or (A1 ∩ A2) ∪ (A3 ∩ A4), etc. and the mass of the total ignorance A1 ∪ A2 ∪ . . . ∪ An, to the elements involved in the ignorances. This new transformation takes into account both the values of the masses and the cardinality of elements in the proportional redistribution process. We first remind what PIC criteria is and then shortly present the general formula for DSmP transformation with few numerical examples. More examples and comparisons with respect to other transformations are given in [35]. 7.1 The Probabilistic Information Content (PIC) Following Sudano’s approach [41, 42, 44], we adopt the Probabilistic Informa- tion Content (PIC) criterion as a metric depicting the strength of a critical decision by a specific probability distribution. It is an essential measure in any threshold-driven automated decision system. The PIC is the dual of the normalized Shannon entropy. A PIC value of one indicates the total knowledge to make a correct decision (one hypothesis has a probability value of one and the rest of zero). A PIC value of zero indicates that the knowledge to make a correct decision does not exist (all the hypotheses have an equal probability value), i.e. one has the maximal entropy. The PIC is used in our analysis to sort the performances of the different pignistic transformations through several numerical examples. We first recall what Shannon entropy and PIC measure are and their tight relationship. • Shannon entropy Shannon entropy, usually expressed in bits (binary digits), of a probability measure P{.} over a discrete finite set Θ = {θ1, . . . , θn} is defined by12 [23]: H(P ) , − n∑ i=1 P{θi} log2(P{θi}) (28) H(P ) is maximal for the uniform probability distribution over Θ, i.e. when P{θi} = 1/n for i = 1, 2, . . . , n. In that case, one gets H(P ) = Hmax = 12with common convention 0 log2 0 = 0. 40 Jean Dezert and Florentin Smarandache - An introduction to DSmT − ∑ni=1 1n log2( 1n ) = log2(n). H(P ) is minimal for a totally deterministic prob- ability, i.e. for any P{.} such that P{θi} = 1 for some i ∈ {1, 2, . . . , n} and P{θj} = 0 for j 6= i. H(P ) measures the randomness carried by any discrete probability P{.}. • The PIC metric The Probabilistic Information Content (PIC) of a probability measure P{.} associated with a probabilistic source over a discrete finite set Θ = {θ1, . . . , θn} is defined by [42]: P IC(P ) = 1 + 1 Hmax · n∑ i=1 P{θi} log2(P{θi}) (29) The PIC is nothing but the dual of the normalized Shannon entropy and thus is actually unit less. P IC(P ) takes its values in [0, 1]. P IC(P ) is maximum, i.e. P ICmax = 1 with any deterministic probability and it is minimum, i.e. P ICmin = 0, with the uniform probability over the frame Θ. The simple relationships between H(P ) and P IC(P ) are P IC(P ) = 1 − (H(P )/Hmax) and H(P ) = Hmax · (1 − P IC(P )). 7.2 The DSmP formula Let’s consider a discrete frame Θ with a given model (free DSm model, hybrid DSm model or Shafer’s model), the DSmP mapping is defined by DSmP²(∅) = 0 and ∀X ∈ GΘ \ {∅} by DSmP²(X) = ∑ Y ∈GΘ ∑ Z⊆X∩Y C(Z)=1 m(Z) + ² · C(X ∩ Y ) ∑ Z⊆Y C(Z)=1 m(Z) + ² · C(Y ) m(Y ) (30) where ² ≥ 0 is a tuning parameter and GΘ corresponds to the generic set (2Θ, SΘ or DΘ including eventually all the integrity constraints (if any) of the model M); C(X ∩ Y ) and C(Y ) denote the DSm cardinals13 of the sets X ∩ Y and Y 13We have omitted the index of the model M for the notation convenience. 41 Jean Dezert and Florentin Smarandache - An introduction to DSmT respectively. ² allows to reach the maximum PIC value of the approximation of m(.) into a subjective probability measure. The smaller ², the better/bigger PIC value. In some particular degenerate cases however, the DSmP²=0 values cannot be derived, but the DSmP²>0 values can however always be derived by choosing ² as a very small positive number, say ² = 1/1000 for example in order to be as close as we want to the maximum of the PIC. When ² = 1 and when the masses of all elements Z having C(Z) = 1 are zero, (30) reduces to (27), i.e. DSmP²=1 = BetP . The passage from a free DSm model to a Shafer’s model involves the passage from a structure to another one, and the cardinals change as well in the formula (30). DSmP works for all models (free, hybrid and Shafer’s). In order to ap- ply classical transformation (Pignistic, Cuzzolin’s one, Sudano’s ones, etc - see [35]), we need at first to refine the frame (on the cases when it is possible!) in order to work with Shafer’s model, and then apply their formulas. In the case where refinement makes sense, then one can apply the other subjective prob- abilities on the refined frame. DSmP works on the refined frame as well and gives the same result as it does on the non-refined frame. Thus DSmP with ² > 0 works on any models and so is very general and appealing. DSmP does a redistribution of the ignorance mass with respect to both the singleton masses and the singletons’ cardinals in the same time. Now, if all masses of singletons involved in all ignorances are different from zero, then we can take ² = 0, and DSmP gives the best result, i.e. the best PIC value. In summary, DSmP does an ’improvement’ over previous known probabilistic transformations in the sense that DSmP mathematically makes a more accurate redistribution of the ignorance masses to the singletons involved in ignorances. DSmP and BetP work in both theories: DST (= Shafer’s model) and DSmT (= free or hybrid models) as well. 8 Fusion of qualitative beliefs We recall here the notion of qualitative belief assignment to model beliefs of human experts expressed in natural language (with linguistic labels). We show how qualitative beliefs can be efficiently combined using an extension of DSmT to qualitative reasoning. A more detailed presentation can be found in [33, 35]. The derivations are based on a new arithmetic on linguistic labels which allows 42 Jean Dezert and Florentin Smarandache - An introduction to DSmT a direct extension of all quantitative rules of combination and conditioning. The qualitative version of PCR5 rule and DSmP is also presented in the sequel. 8.1 Qualitative Operators Computing with words (CW) and qualitative information is more vague, less precise than computing with numbers, but it offers the advantage of robust- ness if done correctly. Here is a general arithmetic we propose for comput- ing with words (i.e. with linguistic labels). Let’s consider a finite frame Θ = {θ1, . . . , θn} of n (exhaustive) elements θi, i = 1, 2, . . . , n, with an as- sociated model M(Θ) on Θ (either Shafer’s model M0(Θ), free-DSm model Mf (Θ), or more general any Hybrid-DSm model [29]). A model M(Θ) is defined by the set of integrity constraints on elements of Θ (if any); Shafer’s model M0(Θ) assumes all elements of Θ truly exclusive, while free-DSm model Mf (Θ) assumes no exclusivity constraints between elements of the frame Θ. Let’s define a finite set of linguistic labels L̃ = {L1, L2, . . . , Lm} where m ≥ 2 is an integer. L̃ is endowed with a total order relationship ≺, so that L1 ≺ L2 ≺ . . . ≺ Lm. To work on a close linguistic set under linguistic addi- tion and multiplication operators, we extends L̃ with two extreme values L0 and Lm+1 where L0 corresponds to the minimal qualitative value and Lm+1 corresponds to the maximal qualitative value, in such a way that L0 ≺ L1 ≺ L2 ≺ . . . ≺ Lm ≺ Lm+1 where ≺ means inferior to, or less (in quality) than, or smaller (in quality) than, etc. hence a relation of order from a qualitative point of view. But if we make a correspondence between qualitative labels and quantitative values on the scale [0, 1], then Lmin = L0 would correspond to the numerical value 0, while Lmax = Lm+1 would correspond to the numerical value 1, and each Li would belong to [0, 1], i. e. Lmin = L0 < L1 < L2 < . . . < Lm < Lm+1 = Lmax From now on, we work on extended ordered set L of qualitative values L = {L0, L̃, Lm+1} = {L0, L1, L2, . . . , Lm, Lm+1} In our previous works, we did propose approximate qualitative operators, but in [35] we propose to use better and accurate operators for qualitative 43 Jean Dezert and Florentin Smarandache - An introduction to DSmT labels. Since these new operators are defined in details in the chapter of [35] devoted on the DSm Field and Linear Algebra of Refined Labels (FLARL), we just briefly introduce here only the the main ones (i.e. the accurate label addition, multiplication and division). In FLARL, we can replace the ”qual- itative quasi-normalization” of qualitative operators we used in our previous papers by ”qualitative normalization” since in FLARL we have exact qualita- tive calculations and exact normalization. • Label addition : La + Lb = La+b (31) since a m+1 + b m+1 = a+b m+1 . • Label multiplication : La × Lb = L(ab)/(m+1) (32) since a m+1 · b m+1 = (ab)/(m+1) m+1 . • Label division (when Lb 6= L0): La ÷ Lb = L(a/b)(m+1) (33) since a m+1 ÷ b m+1 = a b = (a/b)(m+1) m+1 . More accurate qualitative operations (substraction, scalar multiplication, scalar root, scalar power, etc) can be found in [35]. Of course, if one really needs to stay within the original set of labels, an approximation will be necessary at the very end of the calculations. 8.2 Qualitative Belief Assignment A qualitative belief assignment14 (qba) is a mapping function qm(.) : GΘ 7→ L where GΘ corresponds either to 2Θ, to DΘ or even to SΘ depending on the model of the frame Θ we choose to work with. In the case when the labels are equidistant, i.e. the qualitative distance between any two consecutive labels is the same, we get an exact qualitative result, and a qualitative basic belief as- signment (bba) is considered normalized if the sum of all its qualitative masses 14We call it also qualitative belief mass or q-mass for short. 44 Jean Dezert and Florentin Smarandache - An introduction to DSmT is equal to Lmax = Lm+1. If the labels are not equidistant, we still can use all qualitative operators defined in the FLARL, but the qualitative result is approximate, and a qualitative bba is considered quasi-normalized if the sum of all its masses is equal to Lmax. Using the qualitative operator of FLARL, we can easily extend all the combination and conditioning rules from quanti- tative to qualitative. In the sequel we will consider s ≥ 2 qualitative belief assignments qm1(.), . . . , qms(.) defined over the same space G Θ and provided by s independent sources S1, . . . , Ss of evidence. Note: The addition and multiplication operators used in all qualitative fusion formulas in next sections correspond to qualitative addition and qualitative multiplication operators and must not be confused with classical addition and multiplication operators for numbers. 8.3 Qualitative Conjunctive Rule The qualitative Conjunctive Rule (qCR) of s ≥ 2 sources is defined similarly to the quantitative conjunctive consensus rule, i.e. qmqCR(X) = ∑ X1,...,Xs∈GΘ X1∩...∩Xs=X s∏ i=1 qmi(Xi) (34) The total qualitative conflicting mass is given by K1...s = ∑ X1,...,Xs∈GΘ X1∩...∩Xs=∅ s∏ i=1 qmi(Xi) 8.4 Qualitative DSm Classic rule The qualitative DSm Classic rule (q-DSmC) for s ≥ 2 is defined similarly to DSm Classic fusion rule (DSmC) as follows : qmqDSmC (∅) = L0 and for all X ∈ DΘ \ {∅}, qmqDSmC (X) = ∑ X1,,...,Xs∈DΘ X1∩...∩Xs=X s∏ i=1 qmi(Xi) (35) 45 Jean Dezert and Florentin Smarandache - An introduction to DSmT 8.5 Qualitative hybrid DSm rule The qualitative hybrid DSm rule (q-DSmH) is defined similarly to quantitative hybrid DSm rule [29] as follows: qmqDSmH (∅) = L0 (36) and for all X ∈ GΘ \ {∅} qmqDSmH (X) , φ(X) · [ qS1(X) + qS2(X) + qS3(X) ] (37) where all sets involved in formulas are in the canonical form and φ(X) is the characteristic non-emptiness function of a set X, i.e. φ(X) = Lm+1 if X /∈ ∅ and φ(X) = L0 otherwise, where ∅ , {∅M, ∅}. ∅M is the set of all elements of DΘ which have been forced to be empty through the constraints of the model M and ∅ is the classical/universal empty set. qS1(X) ≡ qmqDSmC (X), qS2(X), qS3(X) are defined by qS1(X) , ∑ X1,X2,...,Xs∈DΘ X1∩X2∩...∩Xs=X s∏ i=1 qmi(Xi) (38) qS2(X) , ∑ X1,X2,...,Xs∈∅ [U=X]∨[(U∈∅)∧(X=It)] s∏ i=1 qmi(Xi) (39) qS3(X) , ∑ X1,X2,...,Xk∈DΘ X1∪X2∪...∪Xs=X X1∩X2∩...∩Xs∈∅ s∏ i=1 qmi(Xi) (40) with U , u(X1) ∪ . . . ∪ u(Xs) where u(X) is the union of all θi that compose X, It , θ1 ∪ . . . ∪ θn is the total ignorance. qS1(X) is nothing but the qDSmC rule for s independent sources based on Mf (Θ); qS2(X) is the qualitative mass of all relatively and absolutely empty sets which is transferred to the total or relative ignorances associated with non existential constraints (if any, like in some dynamic problems); qS3(X) transfers the sum of relatively empty sets directly onto the canonical disjunctive form of non-empty sets. qDSmH generalizes qDSmC works for any models (free DSm model, Shafer’s model or any hybrid models) when manipulating qualitative belief assignments. 46 Jean Dezert and Florentin Smarandache - An introduction to DSmT 8.6 Qualitative PCR5 rule (qPCR5) In classical (i.e. quantitative) DSmT framework, the Proportional Conflict Redistribution rule no. 5 (PCR5) defined in [33] has been proven to provide very good and coherent results for combining (quantitative) belief masses, see [31, 7]. When dealing with qualitative beliefs within the DSm Field and Linear Algebra of Refined Labels [35] we get an exact qualitative result no matter what fusion rule is used (DSm fusion rules, Dempster’s rule, Smets’s rule, Dubois-Prade’s rule, etc.). The exact qualitative result will be a refined label (but the user can round it up or down to the closest integer index label). 8.7 A simple example of qualitative fusion of qba’s Let’s consider the following set of ordered linguistic labels L = {L0, L1, L2, L3, L4, L5} (for example, L1, L2, L3 and L4 may represent the values: L1 , very poor, L2 , poor, L3 , good and L4 , very good, where , symbol means by defini- tion). Let’s consider now a simple two-source case with a 2D frame Θ = {θ1, θ2}, Shafer’s model for Θ, and qba’s expressed as follows: qm1(θ1) = L1, qm1(θ2) = L3, qm1(θ1 ∪ θ2) = L1 qm2(θ1) = L2, qm2(θ2) = L1, qm2(θ1 ∪ θ2) = L2 The two qualitative masses qm1(.) and qm2(.) are normalized since: qm1(θ1) + qm1(θ2) + qm1(θ1 ∪ θ2) = L1 + L3 + L1 = L1+3+1 = L5 and qm2(θ1) + qm2(θ2) + qm2(θ1 ∪ θ2) = L2 + L1 + L2 = L2+1+2 = L5 We first derive the result of the conjunctive consensus. This yields: qm12(θ1) = qm1(θ1)qm2(θ1) + qm1(θ1)qm2(θ1 ∪ θ2) + qm1(θ1 ∪ θ2)qm2(θ1) = L1 × L2 + L1 × L2 + L1 × L2 = L 1·2 5 + L 1·2 5 + L 1·2 5 = L 2 5 + 2 5 + 2 5 = L 6 5 = L1.2 47 Jean Dezert and Florentin Smarandache - An introduction to DSmT qm12(θ2) = qm1(θ2)qm2(θ2) + qm1(θ2)qm2(θ1 ∪ θ2) + qm1(θ1 ∪ θ2)qm2(θ2) = L3 × L1 + L3 × L2 + L1 × L1 = L 3·1 5 + L 3·2 5 + L 1·1 5 = L 3 5 + 6 5 + 1 5 = L 10 5 = L2 qm12(θ1 ∪ θ2) = qm1(θ1 ∪ θ2)qm2(θ1 ∪ θ2) = L1 × L2 = L 1·2 5 = L 2 5 = L0.4 qm12(θ1 ∩ θ2) = qm1(θ1)qm2(θ2) + qm1(θ2)qm2(θ1) = L1 × L1 + L2 × L3 = L 1·1 5 + L 2·3 5 = L 1 5 + 6 5 = L 7 5 = L1.4 Therefore we get: • for the fusion with qDSmC, when assuming θ1 ∩ θ2 6= ∅, qmqDSmC (θ1) = L1.2 qmqDSmC (θ2) = L2 qmqDSmC (θ1 ∪ θ2) = L0.4 qmqDSmC (θ1 ∩ θ2) = L1.4 • for the fusion with qDSmH, when assuming θ1 ∩ θ2 = ∅. The mass of θ1 ∩ θ2 is transferred to θ1 ∪ θ2. Hence: qmqDSmH (θ1) = L1.2 qmqDSmH (θ2) = L2 qmqDSmH (θ1 ∩ θ2) = L0 qmqDSmH (θ1 ∪ θ2) = L0.4 + L1.4 = L1.8 • for the fusion with qPCR5, when assuming θ1 ∩ θ2 = ∅. The mass qm12(θ1 ∩ θ2) = L1.4 is transferred to θ1 and to θ2 in the following way: qm12(θ1 ∩ θ2) = qm1(θ1)qm2(θ2) + qm2(θ1)qm1(θ2) Then, qm1(θ1)qm2(θ2) = L1 × L1 = L 1·1 5 = L 1 5 = L0.2 is redistributed to θ1 and θ2 proportionally with respect to their qualitative masses put in the conflict L1 and respectively L1: xθ1 L1 = yθ2 L1 = L0.2 L1 + L1 = L0.2 L1+1 = L0.2 L2 = L 0.2 2 ·5 = L 1 2 = L0.5 whence xθ1 = yθ2 = L1 × L0.5 = L 1·0.5 5 = L 0.5 5 = L0.1. 48 Jean Dezert and Florentin Smarandache - An introduction to DSmT Actually, we could easier see that qm1(θ1)qm2(θ2) = L0.2 had in this case to be equally split between θ1 and θ2 since the mass put in the conflict by θ1 and θ2 was the same for each of them: L1. Therefore L0.2 2 = L 0.2 2 = L0.1. Similarly, qm2(θ1)qm1(θ2) = L2 × L3 = L 2·3 5 = L 6 5 = L1.2 has to be redistributed to θ1 and θ2 proportionally with L2 and L3 respectively : x′θ1 L2 = y′θ2 L3 = L1.2 L2 + L3 = L1.2 L2+3 = L1.2 L5 = L 1.2 5 ·5 = L1.2 whence { x′θ1 = L2 × L1.2 = L 2·1.25 = L 2.45 = L0.48 y′θ2 = L3 × L1.2 = L 3·1.25 = L 3.65 = L0.72 Now, add all these to the qualitative masses of θ1 and θ2 respectively: qmqP CR5(θ1) = qm12(θ1) + xθ1 + x ′ θ1 = L1.2 + L0.1 + L0.48 = L1.2+0.1+0.48 = L1.78 qmqP CR5(θ2) = qm12(θ2) + yθ2 + y ′ θ2 = L2 + L0.1 + L0.72 = L2+0.1+0.72 = L2.82 qmqP CR5(θ1 ∪ θ2) = qm12(θ1 ∪ θ2) = L0.4 qmqP CR5(θ1 ∩ θ2) = L0 The qualitative mass results using all fusion rules (qDSmC,qDSmH,qPCR5) remain normalized in FLARL. Naturally, if one prefers to express the final results with qualitative labels belonging in the original discrete set of labels L = {L0, L1, L2, L3, L4, L5}, some approximations will be necessary to round continuous indexed labels to their closest integer/discrete index value; by example, qmqP CR5(θ1) = L1.78 ≈ L2, qmqP CR5(θ2) = L2.82 ≈ L3 and qmqP CR5(θ1 ∪ θ2) = L0.4 ≈ L0. 8.8 A simple example for the qDSmP transformation We first recall that the qualitative extension of (30), denoted qDSmP²(.) is given by qDSmP²(∅) = 0 and ∀X ∈ GΘ \ {∅} by qDSmP²(X) = ∑ Y ∈GΘ ∑ Z⊆X∩Y C(Z)=1 qm(Z) + ² · C(X ∩ Y ) ∑ Z⊆Y C(Z)=1 qm(Z) + ² · C(Y ) qm(Y ) (41) 49 Jean Dezert and Florentin Smarandache - An introduction to DSmT where all operations in (41) are referred to labels, that is q-operators on lin- guistic labels and not classical operators on numbers. Let’s consider the simple frame Θ = {θ1, θ2} (here n = |Θ| = 2) with Shafer’s model (i.e. θ1 ∩ θ2 = ∅) and the set L = {L0, L1, L2, L3, L4, L5} of linguistic labels, with L0 = Lmin and L5 = Lmax = Lm+1 (here m = 4) and the following qualitative belief assignment: qm(θ1) = L1, qm(θ2) = L3 and qm(θ1 ∪ θ2) = L1. qm(.) is quasi-normalized since ∑ X∈2Θ qm(X) = L5 = Lmax. In this example and with DSmP transformation, qm(θ1 ∪ θ2) = L1 is redistributed to θ1 and θ2 proportionally with respect to their qualitative masses L1 and L3 respectively. Since both L1 and L3 are different from L0, we can take the tuning parameter ² = 0 for the best transfer. ² is taken different from zero when a mass of a set involved in a partial or total ignorance is zero (for qualitative masses, it means L0). Therefore using (33), one has xθ1 L1 = xθ2 L3 = L1 L1 + L3 = L1 L4 = L 1 4 ·5 = L 5 4 = L1.25 and thus using (32), one gets xθ1 = L1 × L1.25 = L 1·(1.25) 5 = L 1.25 5 = L0.25 xθ2 = L3 × L1.25 = L 3·(1.25) 5 = L 3.75 5 = L0.75 Therefore, qDSmP²=0(θ1 ∩ θ2) = qDSmP²=0(∅) = L0 qDSmP²=0(θ1) = L1 + xθ1 = L1 + L0.25 = L1.25 qDSmP²=0(θ2) = L3 + xθ2 = L3 + L0.75 = L3.75 Naturally in our example, one has also qDSmP²=0(θ1 ∪ θ2) = qDSmP²=0(θ1) + qDSmP²=0(θ2) − qDSmP²=0(θ1 ∩ θ2) = L1.25 + L3.75 − L0 = L5 = Lmax Since Hmax = log2 n = log2 2 = 1, using the qualitative extension of PIC formula (29), one obtains the following qualitative PIC value: 50 Jean Dezert and Florentin Smarandache - An introduction to DSmT P IC = 1 + 1 1 · [qDSmP²=0(θ1) log2(qDSmP²=0(θ1)) + qDSmP²=0(θ2) log2(qDSmP²=0(θ2))] = 1 + L1.25 log2(L1.25) + L3.75 log2(L3.75) ≈ L0.94 since we considered the isomorphic transformation Li = i/(m + 1) (in our particular example m = 4 interior labels). 9 Belief Conditioning Rules 9.1 Shafer’s Conditioning Rule (SCR) Until very recently, the most commonly used conditioning rule for belief revi- sion was the one proposed by Shafer [22] and referred here as Shafer’s Condi- tioning Rule (SCR). The SCR consists in combining the prior bba m(.) with a specific bba focused on A with Dempster’s rule of combination for transferring the conflicting mass to non-empty sets in order to provide the revised bba. In other words, the conditioning by a proposition A, is obtained by SCR as follows : mSCR(.|A) = [m ⊕ mS](.) (42) where m(.) is the prior bba to update, A is the conditioning event, mS(.) is the bba focused on A defined by mS(A) = 1 and mS(X) = 0 for all X 6= A and ⊕ denotes Dempster’s rule of combination [22]. The SCR approach based on Dempster’s rule of combination of the prior bba with the bba focused on the conditioning event remains subjective since actually in such belief revision process both sources are subjective and in our opinions SCR doesn’t manage satisfactorily the objective nature/absolute truth carried by the conditioning term. Indeed, when conditioning a prior mass m(.), knowing (or assuming) that the truth is in A, means that we have in hands an absolute (not subjective) knowledge, i.e. the truth in A has oc- curred (or is assumed to have occurred), thus A is realized (or is assumed to be realized) and this is (or at least must be interpreted as) an absolute truth. The conditioning term ”Given A” must therefore be considered as an absolute 51 Jean Dezert and Florentin Smarandache - An introduction to DSmT truth, while mS(A) = 1 introduced in SCR cannot refer to an absolute truth actually, but only to a subjective certainty on the possible occurrence of A from a virtual second source of evidence. The advantage of SCR remains un- doubtedly in its simplicity and the main argument in its favor is its coherence with the conditional probability when manipulating Bayesian belief assign- ment. But in our opinion, SCR should better be interpreted as the fusion of m(.) with a particular subjective bba mS(A) = 1 rather than an objective belief conditioning rule. This fundamental remark motivated us to develop a new family of BCR [33] based on hyper-power set decomposition (HPSD) explained briefly in the next section. It turns out that many BCR are possible because the redistribution of masses of elements outside of A (the conditioning event) to those inside A can be done in n-ways. This will be briefly presented right after the next section. 9.2 Hyper-Power Set Decomposition (HPSD) Let Θ = {θ1, θ2, . . . , θn}, n ≥ 2, a model M(Θ) associated for Θ (free DSm model, hybrid or Shafer’s model) and its corresponding hyper-power set DΘ. Let’s consider a (quantitative) basic belief assignment (bba) m(.) : DΘ 7→ [0, 1] such that ∑ X∈DΘ m(X) = 1. Suppose one finds out that the truth is in the set A ∈ DΘ \ {∅}. Let PD(A) = 2A ∩ DΘ \ {∅}, i.e. all non-empty parts (subsets) of A which are included in DΘ. Let’s consider the normal cases when A 6= ∅ and ∑Y ∈PD(A) m(Y ) > 0. For the degenerate case when the truth is in A = ∅, we consider Smets’ open-world, which means that there are other hypotheses Θ′ = {θn+1, θn+2, . . . θn+m}, m ≥ 1, and the truth is in A ∈ DΘ′ \{∅}. If A = ∅ and we consider a close-world, then it means that the problem is impossible. For another degenerate case, when ∑ Y ∈PD(A) m(Y ) = 0, i.e. when the source gave us a totally (100%) wrong information m(.), then, we define: m(A|A) , 1 and, as a consequence, m(X|A) = 0 for any X 6= A. Let s(A) = {θi1 , θi2 , . . . , θip}, 1 ≤ p ≤ n, be the singletons/atoms that compose A (for example, if A = θ1 ∪ (θ3 ∩ θ4) then s(A) = {θ1, θ3, θ4}). The Hyper- Power Set Decomposition (HPSD) of DΘ \∅ consists in its decomposition into the three following subsets generated by A: • D1 = PD(A), the parts of A which are included in the hyper-power set, except the empty set; • D2 = {(Θ \ s(A)), ∪, ∩}\{∅}, i.e. the sub-hyper-power set generated by 52 Jean Dezert and Florentin Smarandache - An introduction to DSmT Θ \ s(A) under ∪ and ∩, without the empty set. • D3 = (DΘ\{∅})\(D1∪D2); each set from D3 has in its formula singletons from both s(A) and Θ \ s(A) in the case when Θ \ s(A) is different from empty set. D1, D2 and D3 have no element in common two by two and their union is DΘ \ {∅}. Simple example of HPSD: Let’s consider Θ = {θ1, θ2, θ3} with Shafer’s model (i.e. all elements of Θ are exclusive) and let’s assume that the truth is in θ2 ∪θ3, i.e. the conditioning term is θ2 ∪θ3. Then one has the following HPSD: D1 = {θ2, θ3, θ2 ∪ θ3}, D2 = {θ1} and D3 = {θ1 ∪ θ2, θ1 ∪ θ3, θ1 ∪ θ2 ∪ θ3}. More complex and detailed examples can be found in [33]. 9.3 Quantitative belief conditioning rules (BCR) Since there exists actually many ways for redistributing the masses of elements outside of A (the conditioning event) to those inside A, several BCR’s have been proposed in [33]. In this introduction, we will not browse all the possi- bilities for doing these redistributions and all BCR’s formulas but only one, the BCR number 17 (i.e. BCR17) which does in our opinion the most refined redistribution since: - the mass m(W ) of each element W in D2 ∪D3 is transferred to those X ∈ D1 elements which are included in W if any proportionally with respect to their non-empty masses; - if no such X exists, the mass m(W ) is transferred in a pessimistic/prudent way to the k-largest element from D1 which are included in W (in equal parts) if any; - if neither this way is possible, then m(W ) is indiscriminately distributed to all X ∈ D1 proportionally with respect to their nonzero masses. BCR17 is defined by the following formula (see [33], Chap. 9 for detailed explanations and examples): 53 Jean Dezert and Florentin Smarandache - An introduction to DSmT mBCR17(X|A) = m(X) · [ SD1 + ∑ W∈D2∪D3 X⊂W S(W ) 6=0 m(W ) S(W ) ] + ∑ W∈D2∪D3 X⊂W, X is k-largest S(W )=0 m(W )/k (43) where ”X is k-largest” means that X is the k-largest (with respect to inclusion) set included in W and S(W ) , ∑ Y ∈D1,Y ⊂W m(Y ) SD1 , ∑ Z∈D1, or Z∈D2 |@Y ∈D1 with Y ⊂Z m(Z) ∑ Y ∈D1 m(Y ) Note: The authors mentioned in an Erratum to the printed version of the sec- ond volume of DSmT book series (http://fs.gallup.unm.edu//Erratum.pdf) and they also corrected the online version of the aforementioned book (see page 240 in http://fs.gallup.unm.edu//DSmT-book2.pdf that all denominators of the BCR’s formulas are naturally supposed to be different from zero. Of course, Shafer’s conditioning rule as stated in Theorem 3.6, page 67 of [22] does not work when the denominator is zero and that’s why Shafer has introduced the condition Bel(B̄) < 1 (or equivalently P l(B) > 0) in his theorem when the conditioning term is B. A simple example for BCR17: Let’s consider Θ = {θ1, θ2, θ3} with Shafer’s model (i.e. all elements of Θ are exclusive) and let’s assume that the truth is in θ2 ∪θ3, i.e. the conditioning term is A , θ2 ∪θ3. Then one has the following HPSD: D1 = {θ2, θ3, θ2 ∪ θ3}, D2 = {θ1} 54 Jean Dezert and Florentin Smarandache - An introduction to DSmT D3 = {θ1 ∪ θ2, θ1 ∪ θ3, θ1 ∪ θ2 ∪ θ3}. Let’s consider the following prior bba: m(θ1) = 0.2, m(θ2) = 0.1, m(θ3) = 0.2, m(θ1 ∪ θ2) = 0.1, m(θ2 ∪ θ3) = 0.1 and m(θ1 ∪ θ2 ∪ θ3) = 0.3. With BCR17, for D2, m(θ1) = 0.2 is transferred proportionally to all el- ements of D1, i.e. xθ2 0.1 = yθ3 0.2 = zθ2∪θ3 0.1 = 0.2 0.4 = 0.5 whence the parts of m(θ1) redistributed to θ2, θ3 and θ2 ∪ θ3 are respectively xθ2 = 0.05, yθ3 = 0.10, and zθ2∪θ3 = 0.05. For D3, there is actually no need to transfer m(θ1 ∪ θ3) because m(θ1 ∪ θ3) = 0 in this example; whereas m(θ1 ∪ θ2) = 0.1 is transferred to θ2 (no case of k-elements herein); m(θ1 ∪ θ2 ∪ θ3) = 0.3 is transferred to θ2, θ3 and θ2 ∪ θ3 proportionally to their corresponding masses: xθ2 /0.1 = yθ3 /0.2 = zθ2∪θ3 /0.1 = 0.3/0.4 = 0.75 whence xθ2 = 0.075, yθ3 = 0.15, and zθ2∪θ3 = 0.075. Finally, one gets mBCR17(θ2|θ2 ∪ θ3) = 0.10 + 0.05 + 0.10 + 0.075 = 0.325 mBCR17(θ3|θ2 ∪ θ3) = 0.20 + 0.10 + 0.15 = 0.450 mBCR17(θ2 ∪ θ3|θ2 ∪ θ3) = 0.10 + 0.05 + 0.075 = 0.225 which is different from the result obtained with SCR, since one gets in this example: mSCR(θ2|θ2 ∪ θ3) = mSCR(θ3|θ2 ∪ θ3) = 0.25 mSCR(θ2 ∪ θ3|θ2 ∪ θ3) = 0.50 More complex and detailed examples can be found in [33]. 9.4 Qualitative belief conditioning rules In this section we present only the qualitative belief conditioning rule no 17 which extends the principles of the previous quantitative rule BCR17 in the qualitative domain using the operators on linguistic labels defined previously. We consider from now on a general frame Θ = {θ1, θ2, . . . , θn}, a given model M(Θ) with its hyper-power set DΘ and a given extended ordered set L of qualitative values L = {L0, L1, L2, . . . , Lm, Lm+1}. The prior qualitative basic belief assignment (qbba) taking its values in L is denoted qm(.). We assume in the sequel that the conditioning event is A 6= ∅, A ∈ DΘ, i.e. the absolute 55 Jean Dezert and Florentin Smarandache - An introduction to DSmT truth is in A. The approach we present here is a direct extension of BCR17 using FLARL operators. Such extension can be done with all quantitative BCR’s rules proposed in [33], but only qBCR17 is presented here for the sake of space limitations. 9.4.1 Qualitative Belief Conditioning Rule no 17 (qBCR17) Similarly to BCR17, qBCR17 is defined by the following formula: qmqBCR17(X|A) = qm(X) · [ qSD1 + ∑ W∈D2∪D3 X⊂W qS(W )6=0 qm(W ) qS(W ) ] + ∑ W∈D2∪D3 X⊂W, X is k-largest qS(W )=0 qm(W )/k (44) where ”X is k-largest” means that X is the k-largest (with respect to inclusion) set included in W and qS(W ) , ∑ Y ∈D1,Y ⊂W qm(Y ) SD1 , ∑ Z∈D1, or Z∈D2 |@Y ∈D1 with Y ⊂Z qm(Z) ∑ Y ∈D1 qm(Y ) Naturally, all operators (summation, product, division, etc) involved in the formula (44) are the operators defined in FLARL working on linguistic labels. It is worth to note that the formula (44) requires also the division of the label qm(W ) by a scalar k. This division is defined as follows: 56 Jean Dezert and Florentin Smarandache - An introduction to DSmT Let r ∈ R, r 6= 0. Then the label division by a scalar is defined by La r = La/r (45) 9.4.2 A simple example for qBCR17 Let’s consider L = {L0, L1, L2, L3, L4, L5, L6} a set of ordered linguistic labels. For example, L1, L2, L3, L4 and L5 may represent the values: L1 , very poor, L2 , poor, L3 , medium, L4 , good and L5 , very good. Let’s consider also the frame Θ = {A, B, C, D} with the hybrid model corresponding to the Venn diagram on Figure 2. &% '$ &% '$ &% '$ &% '$ @R A ¡ª B ¾ C ¾ D Figure 2: Venn Diagram for the hybrid model for this example. We assume that the prior qualitative bba qm(.) is given by: qm(A) = L1, qm(C) = L1, qm(D) = L4 and the qualitative masses of all other elements of GΘ take the minimal/zero value L0. This qualitative mass is normalized since L1 + L1 + L4 = L1+1+4 = L6 = Lmax. If we assume that the conditioning event is the proposition A ∪ B, i.e. the absolute truth is in A ∪ B, the hyper-power set decomposition (HPSD) is obtained as follows: D1 is formed by all parts of A∪B, D2 is the set generated by {(C, D), ∪, ∩}\∅ = {C, D, C∪D, C∩D}, and D3 = {A∪C, A∪D, B∪C, B∪ D, A ∪ B ∪ C, A ∪ (C ∩ D), . . .}. Because the truth is in A ∪ B, qm(D) = L4 is transferred in a prudent way to (A ∪ B) ∩ D = B ∩ D according to our hybrid model, because B ∩ D is the 1-largest element from A ∪ B which is included 57 Jean Dezert and Florentin Smarandache - An introduction to DSmT in D. While qm(C) = L1 is transferred to A only, since it is the only element in A ∪ B whose qualitative mass qm(A) is different from L0 (zero); hence: qmqBCR17(A|A ∪ B) = qm(A) + qm(C) = L1 + L1 = L1+1 = L2. Therefore, one finally gets: qmqBCR17(A|A ∪ B) = L2 qmqBCR17(C|A ∪ B) = L0 qmqBCR17(D|A ∪ B) = L0 qmqBCR17(B ∩ D|A ∪ B) = L4 which is a normalized qualitative bba. More complicated examples based on other qBCR’s can be found in [34]. 10 Conclusion A general presentation of the foundations of DSmT has been proposed in this introduction. DSmT proposes new quantitative and qualitative rules of com- bination for uncertain, imprecise and highly conflicting sources of information. Several applications of DSmT have been proposed recently in the literature and show the potential and the efficiency of this new theory. DSmT offers the possibility to work in different fusion spaces depending on the nature of problem under consideration. Thus, one can work either in 2Θ = (Θ, ∪) (i.e. in the classical power set as in DST framework), in DΘ = (Θ, ∪, ∩) (the hyper-power set also known as Dedekind’s lattice) or in the super-power set SΘ = (Θ, ∪, ∩, c(.)), which includes 2Θ and DΘ and which represents the power set of the minimal refinement of the frame Θ when the refinement is possible (because for vague elements whose frontiers are not well known the refinement is not possible). We have enriched the DSmT with a subjective probability (DSmP²) that gets the best Probabilistic Information Content (PIC) in com- parison with other existing subjective probabilities. Also, we have defined and developed the DSm Field and Linear Algebra of Refined Labels that permit the transformation of any fusion rule to a corresponding qualitative fusion rule which gives an exact qualitative result (i.e. a refined label), so far the best in literature. 58 Jean Dezert and Florentin Smarandache - An introduction to DSmT References [1] J. Bolanos, L.M. De Campos, S. Moral, Propagation of linguistic labels in causal networks, Proc. of 2nd IEEE Int. Conf. on Fuzzy Systems, Vol. 2, pp. 863–870, 28 March–1 April 1993. [2] L. Comtet, Sperner Systems, Sec.7.2 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, D. Reidel Publ. Co., pp.271-273, 1974. [3] R. Dedekind, ber Zerlegungen von Zahlen durch ihre grssten gemeinsam- men Teiler, In Gesammelte Werke, Bd. 1. pp.103-148, 1897. [4] T. Denœux, Reasoning with imprecise belief structures, Technical Report Heudiasys 97/44, available at http://www.hds.utc.fr/~tdenoeux/. [5] T. Denœux, Reasoning with imprecise belief structures, International Jour- nal of Approximate Reasoning, 20, pp. 79-111, 1999. [6] J. Dezert J., F. Smarandache, DSmT: A New Paradigm Shift for Infor- mation Fusion, in Proceedings of Cogis ’ 06 Conference, Paris, March 2006. [7] J. Dezert, A. Tchamova, F. Smarandache, P. Konstantinova, Target Type Tracking with PCR5 and Dempster’s rules: A Comparative Analysis, in Proceedings of Fusion 2006 International conference on Information Fu- sion, Fusion 2006, Firenze, Italy, July 10-13, 2006. [8] J. Dezert, F. Smarandache, A new probabilistic transformation of belief mass assignment, in Proceedings of Fusion 2008 Conference, Cologne, Germany, July 2008. [9] D. Dubois, H. Prade, On the unicity of Dempster rule of combination, International Journal of Intelligent Systems, Vol. 1, pp 133-142, 1986. [10] D. Dubois, H. Prade, Representation and combination of uncertainty with belief functions and possibility measures, Computational Intelligence, 4, pp. 244-264, 1988. 59 Jean Dezert and Florentin Smarandache - An introduction to DSmT [11] M.C. Florea,Combinaison dinformations htrognes dans le cadre unifica- teur des ensembles alatoires : Approximations et robustesse, Ph. D. The- sis, Laval University, Canada, July 2007. [12] J.W. Guan, D.A. Bell, Generalizing the Dempster-Shafer rule of combi- nation to Boolean algebras, Proc. of IEEE/ACM Int. Conf. on Developing and Managing Projects, Washington, March, pp. 229–236, 1993. [13] T. Inagaki, Interdependence between safety-control policy and multiple- sensor schemes via Dempster-Shafer theory, IEEE Trans. on reliability, Vol. 40, no. 2, pp. 182-188, 1991. [14] M. Lamata, S. Moral, Calculus with linguistic probabilities and beliefs, In R. R. Yager, M. Fedrizzi, and J. Kacprzyk, editors, Advances in Dempster- Shafer Theory of Evidence, pp. 133-152, Wiley. [15] E. Lefevre, O. Colot, P. Vannoorenberghe, Belief functions combination and conflict management, Information Fusion Journal, Elsevier Publisher, Vol. 3, No. 2, pp. 149-162, 2002. [16] E. Lefevre, O. Colot, P. Vannoorenberghe, Reply to the Comments of R. Haenni on the paper ”Belief functions combination and conflict manage- ment”, Information Fusion Journal, Elsevier Publisher, Vol. 4, pp. 63-65, 2003. [17] C.K. Murphy,Combining belief functions when evidence conflicts, Decision Support Systems, Elsevier Publisher, Vol. 29, pp. 1-9, 2000. [18] J.B. Paris, The uncertain reasoner’s companion, a mathematical perspec- tive, Cambridge University Press, 1994. [19] J. Pearl, Probabilistic reasoning in Intelligent Systems: Networks of Plau- sible Inference, Morgan Kaufmann Publishers, San Mateo, CA, 1988. [20] A. Robinson, Non-Standard Analysis, North-Holland Publ. Co., 1966. [21] K. Sentz, S. Ferson, Combination of evidence in Dempster-Shafer Theory, SANDIA Tech. Report, SAND2002-0835, 96 pages, April 2002. [22] G. Shafer, A Mathematical Theory of Evidence, Princeton Univ. Press, Princeton, NJ, 1976. 60 Jean Dezert and Florentin Smarandache - An introduction to DSmT [23] C.E. Shannon, A Mathematical Theory of Communication, Bell Syst. Tech. J., 27, pp. 379-423 and 623-656, 1948. [24] N.J.A. Sloane, The On-line Encyclopedia of Integer Sequences 2003, (Se- quence No. A014466), http://www.research.att.com/~njas/sequences/ [25] F. Smarandache, A Unifying Field in Logics: Neutrosophic Logic. Neu- trosophy, Neutrosophic Set, Probability, and Statistics, (4th Ed.), Amer. Research Press, Rehoboth, 2005. [26] F. Smarandache, A Unifying Field in Logics: Neutrosophic Logic, Multiple-valued logic, An international journal, Vol. 8, No. 3, pp. 385- 438, 2002. [27] F. Smarandache, Neutrosophy: A new branch of philosophy, Multiple- valued logic, An international journal, Vol. 8, No. 3, pp. 297-384, 2002. [28] F. Smarandache (Editor), Proceedings of the First International Confer- ence on Neutrosophics, Univ. of New Mexico, Gallup Campus, NM, USA, 1-3 Dec. 2001, Xiquan, Phoenix, 2002. [29] F. Smarandache, J. Dezert (Editors), Applications and Advances of DSmT for Information Fusion, Am. Res. Press, Rehoboth, 2004. http://www.gallup.unm.edu/~smarandache/DSmT-book1.pdf [30] F. Smarandache, Unification of Fusion Theories (UFT), Presented at NATO Advanced Study Institute, Albena, Bulgaria, 16-27 May 2005 also in International Journal of Applied Mathematics & Statistics, Vol. 2, 1-14, 2004 and on http://arxiv.org/abs/cs/0409040. [31] F. Smarandache, J. Dezert, Information Fusion Based on New Propor- tional Conflict Redistribution Rules, Proceedings of Fusion 2005 Conf., Philadelphia, July 26-29, 2005. [32] F. Smarandache, J. Dezert, Uniform and Partially Uniform Redistribu- tion Rules, published in ”Advances and Applications of DSmT for Plau- sible and Paradoxical Reasoning for Information Fusion”, International Workshop organized by the Bulgarian IST Centre of Competence in 21st 61 Jean Dezert and Florentin Smarandache - An introduction to DSmT Century, December 14, 2006, Bulg. Acad. of Sciences, Sofia, Bulgaria. http://xxx.lanl.gov/abs/cs/070202 [33] F. Smarandache, J. Dezert (Editors), Applications and Advances of DSmT for Information Fusion, Vol. 2, American Research Press, Rehoboth, Au- gust 2006. http://www.gallup.unm.edu/~smarandache/DSmT-book2.pdf [34] F. Smarandache, J. Dezert, Qualitative Belief Conditioning Rules, Pro- ceedings of Fusion 2007 Conf., Québec, Canada, July 2007. [35] F. Smarandache, J. Dezert (Editors), Applications and Advances of DSmT for Information Fusion, Vol. 3, American Research Press, Rehoboth, 2009. [36] F. Smarandache, DSmT web page, http:/fs.gallup.unm.edu//DSmT.htm [37] Ph. Smets, Combining non distinct evidence, Proc. North American Fuzzy Information Processing (NAFIP 1986), New Orleans, LA, 1986. [38] Ph. Smets, E.H. Mamdani, D. Dubois, H. Prade (Editors), Non-Standard Logics for Automated Reasoning, Academic Press, 1988. [39] Smets Ph., Kennes R., The transferable belief model, Artif. Intel., 66(2), pp. 191-234, 1994. [40] Ph. Smets, Data Fusion in the Transferable Belief Model, Proceedings of the 3rd International Conference on Information Fusion, Fusion 2000, Paris, July 10-13, 2000, pp PS21-PS33. [41] J. Sudano, “Pignistic Probability Transforms for Mixes of Low- and High- Probability Events”, Proc. of Fusion 2001, Montreal, August 2001. [42] J. Sudano, “The system probability information content (PIC) . . . ”, Proc. of Fusion 2002, Annapolis, July 2002. [43] J. Sudano, “Equivalence Between Belief Theories and Naive Bayesian Fu- sion for Systems with Independent Evidential Data - Part I, The Theory”, Proc. of Fusion 2003 , Cairns, July 2003. 62 Jean Dezert and Florentin Smarandache - An introduction to DSmT [44] J. Sudano, “Yet Another Paradigm Illustrating Evidence Fusion (YAPIEF)”, Proc. of Fusion 2006, Florence, July 2006. [45] M. Tombak, A. Isotamm, T. Tamme, On logical method for counting Dedekind numbers, Lect. Notes on Comp.Sci., 2138, p. 424-427, Springer- Verlag, 2001. [46] F. Voorbraak, On the justification of Dempster’s rule of combination, Ar- tificial Intelligence, 48, pp. 171-197, 1991. http://turing.wins.uva.nl/~fransv/#pub [47] Y.-M. Wang, J.-B. Yang, D.-L. Xu, K.-S. Chin, On the combination and normalization of interval-valued belief structures, Information Sciences 177, pp. 1230–1247, 2007. [48] R. R. Yager, Hedging in the combination of evidence, Journal of Informa- tion and Optimization Science, Vol. 4, No. 1, pp. 73-81, 1983. [49] R. R. Yager, On the relationships of methods of aggregation of evidence in expert systems, Cybernetics and Systems, Vol. 16, pp. 1-21, 1985. [50] R. R. Yager, On the Dempster-Shafer framework and new combination rules, Information Sciences, Vol. 41, pp. 93–138, 1987. [51] L. Zadeh, Fuzzy sets, Inform. and Control 8, pp. 338-353, 1965. [52] L. Zadeh, Fuzzy Logic and Approximate Reasoning, Synthese, 30, 407-428, 1975. [53] L. Zadeh, On the validity of Dempster’s rule of combination, Memo M 79/24, Univ. of California, Berkeley, 1979. [54] L. Zadeh, Review of Mathematical theory of evidence, by Glenn Shafer, AI Magazine, Vol. 5, No. 3, pp. 81-83, 1984. [55] L. Zadeh, A simple view of the Dempster-Shafer theory of evidence and its implications for the rule of combination, Berkeley Cognitive Science Report No. 33, University of California, Berkeley, CA, 1985. 63 Jean Dezert and Florentin Smarandache - An introduction to DSmT [56] L. Zadeh, A simple view of the Dempster-Shafer theory of evidence and its implication for the rule of combination, AI Magazine 7, No.2, pp. 85-90, 1986. [57] L. Zhang, Representation, independence, and combination of evidence in the Dempster-Shafer Theory, Advances in the Dempster-Shafer Theory of Evidence, R.R. Yager, J. Kacprzyk and M. Fedrizzi, Eds., John Wiley and Sons, Inc., New York, pp. 51-69, 1994. Jean Dezert The French Aerospace Lab ONERA/DTIM/SIF 29 Avenue de la Division Leclerc 92320 Châtillon, France e-mail:jean.dezert@onera.fr Florentin Smarandache Math. and Sciences Dept. University of New Mexico 200 College Road, Gallup, NM 87301, U.S.A. e-mail:smarand@unm.edu 64