domain: math phys info spi

text:
Jean Dezert
email: jean.dezert@onera.fr

Florentin Smarandache

Albena Tchamova
email: tchamova@bas.bg

Deqiang Han
email: deqhan@xjtu.edu.cn

Fast Fusion of Basic Belief Assignments Defined on a Dichotomous Frame of Discernment

Keywords: Information fusion, canonical decomposition, belief functions, PCR5 rule, PCR6 rule

In this paper, we propose a new fusion approach to combine basic belief assignments (BBAs) defined on a dichotomous frame of discernment based on their canonical decomposition. In a companion paper, we have already proved that the canonical decomposition of this type of BBA (called dichotomous BBA) is always possible and unique thanks to the proportional conflict redistribution rule No 5 (PCR5). More precisely, any dichotomous BBA is always the PCR5 combination of two simpler basic belief assignments named respectively the pro-evidence, and the contra-evidence. From this interesting canonical decomposition, we present a new way of combining many dichotomous BBAs and we show that the computational time for fusing these dichotomous BBAs based on their canonical decomposition is quasi-linear with the number of sources to combine, contrary to the direct fusion of the dichotomous BBAs altogether.

I. INTRODUCTION

The belief functions (BF) introduced by Shafer in the mid of 1970's [START_REF] Shafer | A mathematical theory of evidence[END_REF] from Dempster's works are well known and used in the artificial intelligence community to model epistemic uncertainty and to reason with it for information fusion and decision-making support. Dempster's rule to combine distinct sources of evidence characterized by their basic belief assignments (BBAs) defined on the same frame of discernment (FoD) is the historical and emblematic rule of combination in Dempster-Shafer Theory (DST). Unfortunately, Dempster's rule (denoted by DS rule for short) suffers of serious drawbacks in high conflict evidences as pointed out by Zadeh [START_REF] Zadeh | On the validity of Dempster's rule of combination[END_REF], [START_REF] Zadeh | A simple view of the Dempster-Shafer theory of evidence and its implication for the rule of combination[END_REF], but more importantly also in some very low conflict situations [START_REF] Dezert | On the validity of Dempster-Shafer theory[END_REF] as well. That is why many rules have been proposed in the literature [START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF] (Vol.2), among them the combination of two sources of evidence based on the proportional conflict redistribution principle No. 5 1 (PCR5 rule) justified theoretically in [START_REF] Smarandache | Information fusion based on new proportional conflict redistribution rules[END_REF], which has been shown successful in applications. However its complexity remains one of its limitations which prevents its use in fusion problems involving many sources of evidence to combine, and its non 1 Actually PCR6 rule is preferentially used for the combination of more than two sources altogether. For two sources, PCR5 and PCR6 rules coincide and because canonical decomposition involved only two sources, we only need to work with PCR5 rule to combine the pro-evidence with its contra-evidence. associativity property2 which make it not so appealing because the fusion order matters when sequential PCR5 fusion is applied instead of global combination of the sources altogether.

In this work, we show how the fusion of many sources of evidences represented by BBAs defined on a same dichotomous frame of discernment can be easily done based on the PCR5-based canonical decomposition of the BBAs. Such decomposition of BBA has been proposed recently in [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF].

We recall that another canonical decomposition based on conjunctive rule (but involving improper3 BBA) had been proposed in 1995 by Smets [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF], and extended later by Denoeux [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] to develop the so-called cautious rule of combination. In this new approach we use our well justified canonical decomposition based on PCR5 which is strictly based on a proper (i.e. normal) BBAs as defined by Shafer himself. We have shown that any dichotomous BBA is always the result of the PCR5 fusion of a simple proper pro-evidence BBA m p with a simple proper contra-evidence BBA m c , and that this decomposition is unique. Based on this important result, we address in this work the problem of combination of many dichotomous BBAs based on their canonical decomposition.

This paper is organized as follows. After a brief recall of basics of belief functions in section II, we present briefly the canonical decomposition for any dichotomous BBA based on PCR5 rule of combination in section III which is explained in more details with proofs, and examples in [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF]. The fusion of dichotomous BBAs based on the principle of canonical decompositions is detailed in section IV. Concluding remarks with perspectives are given in the last section.

II. BASICS OF BELIEF FUNCTIONS

Belief functions (BF) have been introduced by Shafer in [START_REF] Shafer | A mathematical theory of evidence[END_REF] to model epistemic uncertainty. We assume that the answer 4 of the problem under concern belongs to a known (or given) finite discrete frame of discernment (FoD) Θ = {θ 1 , θ 2 , . . . , θ n }, with n > 1, and where all elements of Θ are mutually exclusive and exhaustive 5 . The FoD is said dichotomous when it involves only two elements (one subset and its complement), that is Θ = {A, Ā} where Ā is the complement of A in Θ. The set of all subsets of Θ (including empty set ∅ and Θ) is the power-set of Θ denoted by 2 Θ . A proper Basic Belief Assignment (BBA) associated with a given source of evidence is defined [START_REF] Shafer | A mathematical theory of evidence[END_REF] as a mapping m(•) :

2 Θ → [0, 1] satisfying m(∅) = 0 and A∈2 Θ m(A) = 1.
In some BF related frameworks, like in Smets Transferable Belief Model (TBM) [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF], m(∅) is allowed to take a positive value. In this case, m(•) is said improper because it does not satisfy Shafer's definition [START_REF] Shafer | A mathematical theory of evidence[END_REF]. The quantity m(A) is called the mass of A committed by the source of evidence. Belief and plausibility functions are respectively defined from a proper BBA m(•) by

Bel(A) = B∈2 Θ |B⊆A m(B) (1)
and

P l(A) = B∈2 Θ |A∩B =∅ m(B) = 1 -Bel( Ā). ( 2
)
where Ā is the complement of A in Θ.

Bel(A) and P l(A) are interpreted respectively as lower and upper bounds of an unknown (subjective) probability measure P (A) in original Dempster's works [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF], [START_REF] Dempster | The generalization of bayesian inference[END_REF]. The quantities m(•) and Bel(•) are one-to-one and the following Möbius inverse formula holds (see [START_REF] Shafer | A mathematical theory of evidence[END_REF], p. 39)

m(A) = B⊆A⊆Θ (-1) |A-B| Bel(B) (3)
A is called a Focal Element (FE) of m(•) if m(A) > 0. When all focal elements are singletons, m(•) is called a Bayesian BBA [START_REF] Shafer | A mathematical theory of evidence[END_REF] and its corresponding Bel(•) function is equal to P l(•) and they are homogeneous to a (subjective) probability measure P (•). The vacuous BBA, or VBBA for short, representing a totally ignorant source is defined as 6

m v (Θ) = 1. A dichotomous BBA is a BBA defined on a dichotomous FoD. A dogmatic BBA is a BBA such that m(Θ) = 0. If m(Θ) > 0 the BBA m(•) is nondogmatic. A simple BBA
is a BBA that has at most two focal sets and one of them is Θ. A dichotomous non dogmatic mass of belief is a BBA having three focal elements A, Ā and A ∪ Ā with A and Ā subsets of Θ.

In his Mathematical Theory of Evidence [START_REF] Shafer | A mathematical theory of evidence[END_REF], Shafer proposed to combine s ≥ 2 distinct sources of evidence represented by BBAs m 1 (.), . . . , m s (.) over the same FoD Θ with Dempster's rule (i.e. the normalized conjunctive rule). For the combination of two BBAs, Dempster's rule formula [START_REF] Shafer | A mathematical theory of evidence[END_REF] is given by m DS (∅) = 0 and

∀X ∈ 2 Θ \ {∅} m DS (X) = 1 K 12 X 1 ,X 2 ∈2 Θ X 1 ∩X 2 =X m 1 (X 1 )m 2 (X 2 ) (4)
with

K 12 = 1 - X1,X2∈2 Θ |X1∩X2=∅ m 1 (X 1 )m 2 (X 2 )
. 6 The complete ignorance is denoted Θ in Shafer's book [START_REF] Shafer | A mathematical theory of evidence[END_REF].

The justification and behavior of Dempster's rule have been disputed over the years from many counter-examples involving high and low conflicting sources (from both theoretical and practical standpoints) as reported in [START_REF] Dezert | On the validity of Dempster-Shafer theory[END_REF], [START_REF] Tchamova | On the behavior of Dempster's rule of combination and the foundations of Dempster-Shafer theory[END_REF]- [START_REF] Smarandache | On the consistency of PCR6 with the averaging rule and its application to probability estimation[END_REF]. Many rules of combination exist in the literature 7 , among them we recommend the rule based on the proportional conflict redistribution principle No. 5 (PCR5 rule) [START_REF] Smarandache | Information fusion based on new proportional conflict redistribution rules[END_REF] which has been shown to be successful in applications and well justified theoretically. That is why we analyze it in details for solving the BF canonical decomposition problem (BF-CDP). PCR5 transfers the conflicting mass only to the elements involved in the conflict and proportionally to their individual masses, so that the specificity of the information is entirely preserved in this fusion process (see [START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF], Vol. 2 and Vol. 3 for full justification and examples):

m P CR5 (∅) = 0 and ∀X ∈ 2 Θ \ {∅} m P CR5 (X) = X 1 ,X 2 ∈2 Θ X 1 ∩X 2 =X m 1 (X 1 )m 2 (X 2 )+ X2∈2 Θ X2∩X=∅ [ m 1 (X) 2 m 2 (X 2 ) m 1 (X) + m 2 (X 2 ) + m 2 (X) 2 m 1 (X 2 ) m 2 (X) + m 1 (X 2 ) ] (5)
where all denominators in (5) are different from zero. If a denominator is zero, that fraction is discarded. The properties of PCR5 can be found in [START_REF] Dezert | Non bayesian conditioning and deconditioning[END_REF]. Extension of PCR5 for combining qualitative BBA's can be found in [START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF], Vol. 2 & 3.

A variant of PCR5, called PCR6 has been proposed by Martin and Osswald in [START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF], Vol. 2, for combining s > 2 sources. The general formulas for PCR5 and PCR6 rules are also given in [START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF], Vol. 2. PCR6 coincides with PCR5 when one combines two sources. The difference between PCR5 and PCR6 lies in the way the proportional conflict redistribution is done as soon as three (or more) sources are involved in the fusion.

From the implementation point of view, PCR6 is simpler to implement than PCR5. For convenience, very basic (not optimized) Matlab TM codes of PCR5 and PCR6 fusion rules can be found in [START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF], [START_REF] Smarandache | Fusion of sources of evidence with different importances and reliabilities[END_REF] and from the toolboxes repository on the web [17]. The main drawback of PCR5 and PCR6 rules is their combinatorial complexity when the number of source is big. Even for combining BBAs defined on a simple dichotomous frame of discernment, the computational time for combining more than 20 sources can take several hours8 . Our main motivation and contribution is to propose a faster fusion method to combine many dichotomous BBAs in order to overcome the combinatorial complexity problem by establishing a new effective (approximating) fusion method based on the new PCR5-based canonical decomposition principle. It is worth noting that our new method is very different of the method based on the clustering of non conflicting BBAs followed by a discounting step and the conjunctive rule presented in [START_REF] Zhou | A belief combination rule for a large number of sources, Infinite Study[END_REF].

III. CANONICAL DECOMPOSITION OF DICHOTOMOUS BBA

A FoD Θ = {A, Ā} is called dichotomous if it consists of only two elements A and Ā with A ∪ Ā = Θ and A ∩ Ā = ∅. A is different from Θ and from Empty-Set because we want to work with informative FoD. Indeed, the very special frame {Θ, ∅} does not bring any useful information since the only possible BBA with such frame is the vacuous BBA. So, we consider a given proper 9

BBA m(•) : 2 Θ → [0, 1] of the form m(A) = a, m( Ā) = b, m(A ∪ Ā) = 1 -a -b (6) with 0 < a < 1, 0 < b < 1 and a + b < 1.
The conditions 0 < a < 1 and 0 < b < 1 mean that A and Ā are focal elements of the BBA. The restriction a + b < 1 means that the BBA is nondogmatic.

This assumption of nondogmaticity of the BBA m(•) is necessary for Smets canonical decomposition [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF], but it is not essential for our PCR5-based canonical decomposition (as we will show in the sequel) because our decomposition also works directly with a dogmatic BBA. Of course any dogmatic BBA can always be modified as a non-dogmatic BBA by using a very small discounting number ( > 0) so that, in practice, Smets' decomposition can always be applied, but this is not sufficient to prove that Smets approach always provides relevant results. Why? just because we know (and we have proved) that Dempster's (normalized conjunctive rule) and even the conjunctive rule in Smets' TBM suffers of serious drawbacks -see justifications in our aforementioned references. That is why we explore in this work another way of making a canonical decomposition, which is, for now, limited to dichotomous BBA.

Our canonical decomposition problem consists in finding the two following simple proper BBAs m p and m c of the form

m p (A) = x, m p (A ∪ Ā) = 1 -x (7) m c ( Ā) = y, m c (A ∪ Ā) = 1 -y (8) with (x, y) ∈ [0, 1] × [0, 1], such that m = F usion(m p , m c ),
(A) = 1, m( Ā) = 0 (case (a, b) = (1, 0)), or m(A) = 0, m( Ā) = 1 (case (a, b) = (0, 1))
have infinitely many decompositions based on Dempster's rule 9 which means that m(∅) = 0.

of combination (see Lemma in [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF]). In [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF], we have shown that our canonical decomposition cannot be achieved from conjunctive, disjunctive, Yager's [START_REF] Yager | On the Dempster-Shafer framework and new combination rules[END_REF] or Dubois-Prade [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF] rules of combination, neither from averaging rule. However, such type of decomposition is unique and is always possible in all cases of dichotomous BBA m(•) using the PCR5 rule of combination. In [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF], we did prove the following Theorem.

m c ( Ā) = y, m c (A ∪ Ā) = 1 -y where x, y ∈ [0, 1].
Moreover, we also proved in [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF] that the canonical decomposition also exists even if the dichotomous BBA is dogmatic (i.e. Bayesian) and the following theorem also holds.

= P CR5(m p , m c ) with m p (A) = x, m p (A ∪ Ā) = 1 -x and m c ( Ā) = y, m c (A ∪ Ā) = 1 -y where x, y ∈ [0, 1].
Theorems 1 & 2 prove that the decomposition based on PCR5 always exists and it is unique for any dichotomous (nondogmatic, or dogmatic) BBA.

For the case of dichotomous dogmatic BBA considered in Theorem 2, the expression of solutions x and y can be established explicitly as follows -see [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF] for details For the case of dichotomous nondogmatic BBA considered in Theorem 1, one has to find x and y solutions of the system

a = x(1 -y) + x 2 y x + y = x 2 + xy -xy 2 x + y (9) b = (1 -x)y + xy 2 x + y = y 2 + xy -x 2 y x + y ( 10
)
under the constraints (a, b) ∈ [0, 1] 2 , and 0 < a + b < 1. In fact, it has been proved in [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF]

that x ∈ [a, a + b] ⊂ [0, 1] and y ∈ [b, a + b] ⊂ [0, 1],
but the explicit expression of x and y are very complicated to obtain analytically (even with modern symbolic computing systems like Mathematica TM , or Maple TM ) because after algebraic calculation, and for x = 1, one has to solve the following quartic equation which has at most four real solutions with only a valid one in [a, a + b]

x 4 + (-a -2)x 3 + (2a + b)x 2 + (a + b -ab -b 2 )x + (-a 2 -ab) = 0 (11)
and then compute y as y = a+b-x 1-x . Fortunately, the solutions can be easily calculated numerically by these computing systems, and even with Matlab TM system 10 as soon as the numerical values are committed to a and to b, and this is what we do in our simulations in the sequel.

The four solutions of this quartic equation provided by the computing system 11 are approximately

x 1 ≈ 0.7774780438 x 2 ≈ 0.9297589637 x 3 ≈ 1.4191515820 x 4 ≈ -0.5263885898
Clearly x 3 and x 4 are not acceptable solutions because they don't belong to [0, 1]. If we take x 1 ≈ 0.7774780438, then we will get y 1 = (a + bx 1 )/(1x 1 ) = (0.9x 1 )/(1x 1 ) ≈ 0.5506061437. The pair (x 1 , y 1 ) ∈ [0, 1] 2 is a solution of the decomposition problem of the BBA m(•). If we take x 2 ≈ 0.9297589637, then we will get Of course there are necessarily numerical approximations involved by the proposed decomposition because this decomposition is obtained by numerical solvers. This may have some little impact in the PCR5 fusion result but because PCR5 rule is numerically robust to small input changes (contrariwise to Dempster's rule) the PCR5 result will not change substantially with small changes (due to small numerical imprecisions) in the values of BBAs to combine.

y 2 = (a + b -x 2 )/(1 - x 2 ) = (0.9 -x 2 )/(1 -x 2 ) ≈ -0.4236692006. We see that y 2 / ∈ [0,
A. Particular cases 1) Case (a, b) = (0, 0) (i.e. m is the vacuous BBA): This is the most degenerate case where the BBA m(•) corresponds to the vacuous BBA. For averaging rule, conjunctive rule, Yager's, Dubois-Prade's, Dempster's and PCR5 rules one has x = 0 and y = 0 (conflict between canonical masses is zero). In fact the vacuous BBA m(•) can always be interpreted as the fusion of m p and m c , where m p and m c are also vacuous BBAs. This degenerate case has no particular interest in practice but to model the total ignorant state of knowledge. 10 thanks to the fsolve command. 11 We did get same solutions with Maple TM , and with Matlab TM .

2) Case when a = 0, or b = 0: In the case a = 0 and 0 < b ≤ 1, then for conjunctive rule, Yager's, Dubois-Prade's, Dempster's and PCR5 rules one has x = 0 and y = b (conflict between canonical masses is zero) and m(•) corresponds to the fusion of vacuous pro-evidence m p = m v with the contraevidence m c = m. In the case 0 < a ≤ 1 and b = 0, then for conjunctive rule, Yager's, Dubois-Prade's, Dempster's and PCR5 rules one has x = a and y = 0 (conflict between canonical masses is zero) and m(•) corresponds to the fusion of the pro-evidence m p = m with the vacuous contra-evidence m c = m v . These cases have no particular interest because they can be seen just as the combination of pro (or contra) BBA with the vacuous BBA.

3) Case when a = b ∈ (0, 0.5): In this case, the BBA m(A) = m( Ā) = a and m(A∪ Ā) = 1-2a can be canonically decomposed from PCR5 rule with the BBAs m p

(A) = 1 - √ 1 -2a, m p (A ∪ Ā) = √ 1 -2a and m c ( Ā) = 1 - √ 1 -2a, m c (A ∪ Ā) = √ 1 -2a
-see details and proof in [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF].

B. Benefits of canonical decomposition

The canonical decomposition based on PCR5 offers several interests and advantages that are briefly listed.

1) This canonical decomposition of m(•) into the proevidence m p (•) and the contra-evidence m c (•) allows to define the notion of internal conflict of a dichotomous source of evidence, denoted by K int (m), as

K int (m) m p (A)m c ( Ā) (13)
where m p (A) = x and m c ( Ā) = y are the canonical factors of the BBA m(•) based on PCR5 rule of combination.

2) The canonical decomposition also allows to adjust/revise easily a dichotomous source of evidence (if needed) according to the knowledge one has on it. For instance, if one knows that a source over (or under) estimate the hypothesis A, then one could apply an adjustment (based on some discounting or reinforcing factors) on the pro (or contra) evidence to de-bias this source of evidence. 3) This canonical decomposition can help to develop new fast rules of combination for the fusion of S ≥ 2 (dichotomous) distinct 12 BBAs

m s (•) = (m s (A), m s ( Ā), m s (A ∪ Ā)) = (a s , b s , 1 -a s -b s ), s = 1, 2, .
. . , S. This is presented next.

IV. FAST FUSION OF DICHOTOMOUS BBAS

In this section, we show how to combine many dichotomous BBAs defined on the same FoD Θ thanks to their canonical decompositions.

A. Principle of the fast fusion of dichotomous BBAs

The main idea for making the fast fusion of dichotomous BBAs is, at first, to decompose canonically each dichotomous BBA m s (.), for s = 1, 2, . . . , S into their pro and contra evidences m p,s = (m p,s (A), m p,s ( Ā), m p,s (A ∪ Ā)) = (x s , 0, 1-x s ) and m c,s = (m c,s (A), m c,s ( Ā), m c,s (A∪ Ā)) = (0, y s , 1y s ), and then to combine the pro-evidences m p,s for s = 1, 2, . . . , S altogether on one hand to get a global pro-evidence m p , and to combine the contra-evidences m c,s for s = 1, 2, . . . , S altogether on the other hand to get a global contra-evidence m c . The fusion step of pro and contra evidences is discussed in section IV-D. Once m p and m c are calculated, then one combines them with PCR5 fusion rule to get the final result. This general principle of the new fusion method is represented by the diagram of figure 1 for convenience. This new fusion approach is interesting because the fusion of the pro-evidence m p,s (resp. contra-evidences m c,s ) is quite simple because there is non conflict between m p,s (resp. between m c,s ), so that their fusion can be done quite easily and a large number of sources can be combined without a high computational burden. In fact, with this fusion approach, only one PCR5 fusion step of simple (combined) canonical BBAs is needed at the very end of the fusion process. It is worth noting that in this work there is no link with the canonical decomposition proposed by Shafer and then extended by Smets because here we use another fusion rule based on the proportional conflict redistribution principle.

B. Analysis of the effectiveness of this new fusion approach

Because the PCR5 rule 13 of combination is not associative, the fusion 14 of the canonical BBAs followed by their PCR5 fusion will not provide in general the same result as the direct fusion of the dichotomous BBAs altogether but only an approximate result, which is normal.

The main question is to know how good is the approximation obtained by this new fusion method based on the 13 The same remark holds for PCR6 rule with more than two BBAs. 14 We assume here that the fusion of all the pro-evidences (resp. contraevidences) is done with PCR5 rule which coincides in this case with the conjunctive rule because there is no conflict between the pro-evidences (resp. the contra-evidences). fusion of pro-evidences and contra-evidences with respect to the direct fusion of the BBAs with PCR5 (or PCR6 when considering more than two sources to combine). To answer to this important question we make a statistical analysis of the quality of the combined result m, with respect to the direct PCR5, or PCR6 fusion of all BBAs altogether.

The measure of the goodness is obtained by the normalized (Euclidean) Belief Interval distance d BI (m P CR5 , m) (for the case of two BBAs only), or by d BI (m P CR6 , m) if more than two sources are considered in the fusion process, where m is the result of the fusion principle based on canonical decompositions, and m P CR5 (resp. m P CR6 ) is the result of the combination of original BBAs altogether with PCR5 (resp. PCR6) rule. The d BI distance between two BBAs m 1 (•) and m 2 (•) defined on the powerset of a given FoD Θ = {θ 1 , . . . , θ n } has been proposed and justified in [START_REF] Han | Belief interval based distances measures in the theory of belief functions[END_REF], [START_REF] Dezert | Decisionmaking with belief interval distance[END_REF]. It is defined by

d BI (m 1 , m 2 ) N c • X∈2 Θ d 2 W (BI 1 (X), BI 2 (X)) ( 14
)
where 14) is given by

N c = 1/2 n-1 is a normalization factor to make d BI (m 1 , m 2 ) ∈ [0, 1], and d W (BI 1 (X), BI 2 (X)) is Wassertein's distance [23] between belief intervals BI 1 (X) [Bel 1 (X), P l 1 (X)] = [a 1 , b 1 ] and BI 2 (X) [Bel 2 (X), P l 2 (X)] = [a 2 , b 2 ]. Here, d 2 W (BI 1 (X), BI 2 (X)) entering in (
d 2 W ([a 1 , b 1 ], [a 2 , b 2 ]) a 1 + b 1 2 - a 2 + b 2 2 2 + 1 3 b 1 -a 1 2 - b 2 -a 2 2 2 ( 15
)
Figure 2 shows the normalized histogram (i.e. the empirical probability distribution) of the distance values d E BI (m P CR5 , m) based on 20000 random 15 generations of dichotomous BBAs m 1 and m 2 . One observes that the new fusion approach based on the canonical decompositions of BBAs (with the conjunctive fusion of pro-evidences, and the conjunctive fusion of contra-evidences) provides a solution which is very close to what we obtain from the direct application of PCR5 rule, with a mean of 0.0287 and a standard deviation of 0.0289. In 98.20% of cases, the final decision (based on the min of d E BI decision-making strategy explained in [START_REF] Dezert | Decisionmaking with belief interval distance[END_REF]) based on m P CR5 , or on m are in agreement. This means that the decision agreement (DA) rate is 98.20%.

Figures 3 show the normalized histograms of the d E BI (m P CR6 , m) values based also on 20000 random runs for the fusion of 6 dichotomous BBAs respectively. We use PCR6 rule instead of PCR5 rule to combine the 6 dichotomous BBAs altogether because PCR6 rule has been recognized to be more effective than PCR5 in applications [START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF] (Vol.2 -Chap.

2). As we can observe, the shape of the histograms is a bit different from the histogram of fig. 2, but what matters is that the mean value and the standard deviation of the d E BI distance are still low (0.1119 and 0.0392 respectively) indicating that the approximation obtained by this new fusion method is globally very good. Also the decision based on this new fusion approach is globally coherent with the decision taken by the direct PCR6 fusion of the BBAs (95.84% of decision coherence). decomposition based) method. As we can see, the DA factors are very high which means that most of the time the decisions taken from the direct fusion method and from the indirect fusion method are the same.

After a deep analysis of our simulation results, one can attest that the decision-making disagreement occurs when the numerical values of the mass of A and the mass of Ā are very close. This indicates a very high ambiguity in the decision to take in such situation which can be easily tracked in practice by evaluating the quality indicator of the decision-makingsee [START_REF] Dezert | Decisionmaking with belief interval distance[END_REF] for details.

In this paper we did not investigate the quality of the approximation of the fusion result based on this canonical decomposition when replacing the PCR5 fusion step of m p and m c by other rules of combination because the core of the canonical decomposition is based on PCR5.

C. Computational time of the new fusion method

Because of very high combinatorial complexity (and thus high computational time) required for applying the direct PCR6 fusion of many BBAs, we did only make the performance evaluation up to the fusion of ten BBAs only with PCR6. We conjecture that the performances of this new fusion method based on canonical decomposition will very slowly degrade with the increase of the number of BBAs involved in the fusion process. Of course the new fusion method based on this canonical decomposition does not suffer of combinatorial complexity limitation which is of great interest in some applications (like in multi-spectral imagery for detection and classification) because many (hundreds or even thousands) of dichotomous BBAs could be easily combined very quickly. Actually with this method what takes a bit time is only the canonical decomposition done by the numerical solver 16 .

Figure 4 shows the average (based on 50 random runs) computational time (in seconds) of the direct PCR6 fusion of the BBAs altogether (red plot), and the average computational time of the new fusion method based on canonical decomposition (blue plot). It is clear that the computational time of the direct PCR6 fusion method (the red curve) grows exponentially with the number of sources, whereas the computational time grows only slowly and quasi-linearly with the new method proposed in this work. Based on a set of 1000 random dichotomous BBAs, figure 5 shows that the computational time (in seconds) of the fusion based on the canonical decomposition is a quasi-linear 17 function of the number of BBAs to combine. Figures 4 and5 show the computational times including the canonical decomposition itself done on the fly. Of course, the canonical decomposition could be done off-line once for all and stored in the computer memory (if necessary) -see for instance the (x, y) values given in [START_REF] Dezert | Canonical decomposition of dichotomous basic belief assignment[END_REF] for convenience. If we have n dichotomous BBAs to combine, we have to make their canonical decomposition at first and because the n pro-evidence BBAs to combine (resp. contra evidence BBAs) have a very simple structure their conjunctive fusion m p (A) is obtained very quickly by the direct product of n real numbers, that is m p (A) = n i=1 m p,i (A), and we need 17 It is not strictly linear because the time for the numerical fsolve search of pro-evidence and contra-evidence factors for making the canonical decomposition is not constant. also a subtraction because m p (A ∪ Ā) = 1m p (A). The complexity of this fast suboptimal PCR fusion approach (once the canonical decomposition is available) is therefore 2(n -1) multiplications and 2 subtractions for making the conjunctive fusion of m p,i and the conjunctive fusion of m c,i , and 7 additions and 5 multiplications for making the PCR5 fusion of m p with m c . There is no need to use the commonality function or the Smets canonical decomposition to make the fusion of these dichotomous BBAs. These figures show clearly the real advantage of the fusion of dichotomous BBAs based on their canonical decompositions in term of computational time, and that is why we can say that the new proposed method is really a fast fusion method with respect to the direct PCR5 or PCR6 rule of combination when working with a dichotomous frame of discernment.

D. On the fusion of pro and contra evidences

In the previous analysis, we did use the conjunctive rule for the intermediary fusion step of pro-evidences in one hand, and the intermediary fusion step of contra-evidences in the other hand. It is worth noting that the intermediary step of fusion of pro-evidences, and the intermediary step of fusion of contraevidences can be done in parallel which offers a computational advantage with respect to the direct fusion method (if one has many sources to combine in a specific application). This parallelization cannot be achieved in general with the other existing rules of combination of evidences.

Because of the fusion principle depicted in Figure 1, this new fusion method offers also the possibility (if one prefers for some own specific reasons) of selecting other fusion rules for the intermediary fusion steps for combining the proevidences, and the contra-evidences. Of course the choice of the fusion rules used for the combination of pro-evidences and the combination of contra-evidences impacts the final result, but depending on the type of rules chosen we can obtain an associative rule, an idempotent rule, and even a new cautious rule. For example, let's consider the same type of fusion rule for combining the pro-evidences m p,s s = 1, . . . , S, and for combining contra-evidences m c,s s = 1, . . . , S and consider the following cases:

1) If we use the conjunctive rule [START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF] (Vol. Because there is no conflict between the pro-evidences (resp. contra-evidences), the fusion result of the pro-evidences (resp. the contraevidences) by PCR5 (or PCR6) rules is equivalent to the conjunctive fusion result. The conjunctive rule however is not idempotent in general but in very specific cases where only one focal element gets all the mass of belief. Because the averaging rule is not associative, the sequential fusion of pro-evidences (and contra-evidences) is not recommended, however the averaging rule allows to get an idempotent fusion rule based on canonical decompositions if needed.

3) We could also prefer to use the min rule to build a new cautious rule of combination which will be associative and idempotent. For this, we just have to take m p (A) = min s=1,...,S (x s ) and m p (A∪ Ā) = 1-m p (A). Similarly, m c ( Ā) = min s=1,...,S (y s ) and m c (A∪ Ā) = 1-m c ( Ā).

V. CONCLUSIONS

In this research paper, we did propose a new fusion method to combine very quickly many BBAs defined on a dichotomous frame of discernment thanks to their unique canonical decompositions. This new interesting method can be parallelized and offers the advantage to have a quasi-linear computational time with the number of sources. For now, this method is limited to the fusion of many BBAs that are defined on a simple (dichotomous) frame of discernment. After some unsuccessful attempts, it appears that the development of a fast fusion method based on the canonical decomposition principle for working with non-dichotomous frames of discernment is actually a very difficult problem that we want to address to the scientific community working with belief functions as a future research challenge. This very new method brings already a significant benefit for real application involving inter-criteria analysis for the evaluation of multiple-objective ant colony optimization algorithm for wireless sensor networks deployment that should be reported in a forthcoming publication.

  for a chosen rule of combination denoted by F usion(•, •). The simple BBA m p (•) is called the pro-BBA (or pro-evidence) of A, and the simple BBA m c (•) the contra-BBA (or contraevidence) of A. The BBA m p (•) is interpreted as a source of evidence providing an uncertain evidence in favor of A, whereas m c (•) is interpreted as a source of evidence providing an uncertain contrary evidence about A. This decomposition is possible with Dempster's rule only if 0 < a < 1, 0 < b < 1 and a + b < 1, and in this case we have x = a 1-b and y = b 1-a . However, any dogmatic BBA m(A) = a, m( Ā) = b with a + b = 1 is not decomposable from Dempster's rule for the case when (a, b) = (1, 0) and (a, b) = (0, 1) (see Theorem 4 in [7]), and the dogmatic BBAs m

Theorem 1 :

 1 Consider a dichotomous FoD Θ = {A, Ā} with A = Θ and A = ∅ and a nondogmatic BBA m(•) : 2 Θ → [0, 1] defined on Θ by m(A) = a, m( Ā) = b, and m(A ∪ Ā) = 1ab, where a, b ∈ [0, 1] and a + b < 1. Then the BBA m(•) has a unique canonical decomposition using PCR5 rule of combination of the form m = P CR5(m p , m c ) with proevidence m p (A) = x, m p (A∪ Ā) = 1-x and contra-evidence

Theorem 2 :

 2 Any dogmatic BBA defined by m(A) = a and m( Ā) = b, where a, b ∈ [0, 1] and a + b = 1, has a canonical decomposition using PCR5 rule of combination of the form m

•a 2 +4a 2 .b 2 +4b 2 .

 22 If a < b then x < y, and we have y = 1 and x = a+ √ • If a > b then x > y, and we have x = 1 and y = b+ √ • If a = b and a + b = 1 then a = b = 0.5 and x = y = 1.

Example 1 :

 1 Let consider Θ = {A, Ā} and m(A) = 0.6, m( Ā) = 0.3 and m(A∪ Ā) = 1-m(A)-m( Ā) = 0.1. Hence, a = 0.6 and b = 0.3. The quartic equation (11) becomes x 4 -2.6x 3 + 1.5x 2 + 0.63x -0.54 = 0

  1], and therefore the pair (x 2 , y 2 ) cannot be a solution of the decomposition problem of the BBA m(•). Therefore the canonical masses m p (•) and m c (•) are given by m p (A) ≈ 0.7774780438, m p (A ∪ Ā) ≈ 0.2225219562 m c ( Ā) ≈ 0.5506061437, m c (A ∪ Ā) ≈ 0.4493938563 It can be verified that the PCR5 combination of BBAs m p and m c , denoted by P CR5(m p , m c ), is equal to the BBA m(•).

Figure 1 .

 1 Figure 1. General principle of the fusion of dichotomous BBAs from their canonical decompositions.

Figure 2 .

 2 Figure 2. Normalized histogram of d E BI (m P CR5 , m) for 2 dichotomous BBAs case (20000 runs).

Figure 3 .

 3 Figure 3. Normalized histogram of d E BI (m P CR6 , m) for 6 dichotomous BBAs case (20000 runs). Several Monte Carlo simulations have been done with different numbers of dichotomous BBAs to combine. The results obtained based on 20000 runs Monte Carlo simulations are summarized in the Table I. The second column of Table I indicates the mean value, denoted by mean(d E BI ), of the normalized Euclidean belief Interval distance between the direct fusion of the BBAs by the PCR5 (when combining 2 BBAs only), or PCR6 rule (when combining more than two BBAs) and the new fusion rule based on their canonical decomposition. The third column of the Table I shows the corresponding standard deviation values denoted by std(d E BI ). The last column indicates the decision agreement (DA) factor between the decision taken from the direct fusion method, and the indirect (canonical

  Comparison of computational times (based on 50 random runs)with the direct PCR6 fusion of all BBAs with the fusion based on the canonical decompositions of BBAs

Figure 4 .

 4 Figure 4. Computing time versus number of BBAs to combine.

Figure 5 .

 5 Figure 5. Computing time versus number of BBAs to combine.

  [START_REF] Shafer | A mathematical theory of evidence[END_REF], denoted by Conj(., . . . , .) (as we did previously in our Monte Carlo simulations for histogram plots), thenm p = Conj(m p,1 , . . . , m p,S ) and one has m p (A ∪ Ā) = S s=1 (1x s ) and m p (A) = 1m p (A ∪ Ā).Because the conjunctive rule is associative the fusion of pro-evidences can be done sequentially. Similarly, for the fusion of contra-evidences using the conjunctive rule one has m c (A∪ Ā) = S s=1 (1-y s ) and m p ( Ā) = 1m c (A ∪ Ā).

2 )

 2 If we prefer to use the averaging rule, then we will have m p (A) = 1 S S s=1 x s and m p (A ∪ Ā) = 1m p (A) = 1 S S s=1 (1x s ), and m c ( Ā) = 1 S S s=1 y s and m c (A ∪ Ā) = 1m c ( Ā) = 1 S S s=1 (1y s ).

Table I COMPARATIVE

 I EVALUATION OF CANONICAL DECOMPOSITION FUSION METHOD W.R.T. THE DIRECT PCR-BASED FUSION METHOD.

	# of BBAs mean(d E BI ) std(d E BI ) Decision Agreement (%) 2 0.0287 0.0289 98.20
	3	0.0578	0.0373	97.52
	4	0.0838	0.0394	96.69
	5	0.1008	0.0397	96.05
	6	0.1119	0.0392	95.84
	7	0.1169	0.0385	95.40
	8	0.1200	0.0374	94.89
	9	0.1211	0.0365	94.25
	10	0.1204	0.0348	94.21

PCR5 is only quasi-associative.

We call a BBA improper when it does not satisfy Shafer's original definition. Smets called it a generalized simple BBA (GSBBA).

i.e. the solution, or the decision to take.

This is so-called Shafer's model of FoD[START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF].

see[START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF], Vol. 2 for a detailed list of fusion rules.

due to the exponential complexity of the PCR6 rule (as shown in Figure4). For our simulations, we did use a MacBook Pro 2.8 GHz Intel Core i7 with 16 Go 1600 MHz DDR3 memory running Matlab TM R2018a.

For this, we generate three random numbers uniformly distributed in [0, 1] and we normalize them to generate randomly a dichotomous BBA.


Thomas Podgorski

Sylvain Losserand

Gwennou Coupier
email: <gwennou.coupier@univ-grenoble-alpes.fr>

Corrigendum to "Migration velocity of red blood cells in microchannels" [Microvascular Research 124 (2019) 30-36]