Didier Dubois
email: dubois@irit.fr

Hélène Fargier
email: fargier@irit.fr

Henri Prade
email: prade@irit.fr

Multiple-sources information fusiona practical inconsistency-tolerant approach

Keywords: fusion, possibility theory, inconsistency, maximal consistent subsets

A multiple-sources information system should be able to provide the user with the most possibly accurate answers about the values of the attributes describing the objects of interest. In this paper, the attribute values, which are supposed to range on linearly ordered domains, may be imprecisely given by the sources, which moreover may not be fully reliable. After a brief background on the general principles underlying the fusion of imprecise information in the framework of possibility theory, the case of single-valued attributes is first considered, before dealing with the multiple-valued case. The handling of known relations linking attributes, in a fusion process, is also briefly discussed.

Introduction

Information fusion plays an important role in advanced information systems. Indeed, the use of several sources of information often allows to deliver answers to the users, which are more precise than the ones that each source could provide individually. However, the different sources of information are not always equally reliable, and the pieces of information they give may be partially inconsistent. There exists different theoretical frameworks for modelling the combination of uncertain information (e.g., Abidi and Gonzales, 1992;[START_REF] Luo | Multisensor Integration and Fusion for Intelligent Machines and Systems[END_REF][START_REF] Gebhardt | Parallel combination of information sources[END_REF]. Beside probabilistic approaches which have been extensively studied and used in multiple-sensors fusion, or in expert opinion aggregation (e.g., [START_REF] Cooke | Experts in Uncertainty[END_REF], logical settings have been considered more recently, in particular for databases fusion (e.g., [START_REF] Cholvy | Reasoning about merged information[END_REF]. The possibility theory framework is used in this paper since it is rather well-suited for representing "poor" information when uncertainty can only be expressed in a qualitative manner; see (Dubois andPrade, 1994, 1995) for a general introduction. This paper proposes a discussion of the practical use of a simplified version of a possibilistic approach, which however can handle inconsistencies and take into account the different levels of reliability of the sources. The problems raised by the exploitation in the combination process of expert knowledge, given under the form of relations linking the variables whose values are provided by the sources, is also discussed, as well as the case of multiple-valued attributes.

Possibilistic information fusion

Let us consider some single-valued attribute represented by a parameter x ranging on a referential U, for a given object. U is supposed to be linearly ordered; e.g., U is a subset of the real line. Let A i represent the piece of information issued from source i to be understood as x ∈ A i . As it is often the case in practice, A i is assumed to be an interval, or more generally a fuzzy interval, which restricts the possible values of x. In practice, precise values provided by sources may be only indicative; if it is the case, it is better to replace them by some genuine interval acknowledging some possible error. In the approach developed in this paper, the fuzzy interval A i will be also supposed to have a trapezoidal membership function with core N i and support S i , which will be written A i = (N i ,S i ).

When fusing information coming from two sources, two situations may be encountered:

-either the pieces of information are sufficiently consistent and it can be assumed that the two sources are reliable, which allows for the crosschecking and the refinement of information; -or the pieces of information are not sufficiently consistent and we are forced to admit that at least one of the sources is wrong. The hypothesis that the two sources are reliable leads to use a conjunctive combination. Let µ A i (u) be the degree of possibility that x = u knowing that la source asserts that x ∈ A i . There are two main types of conjunctive combination:

• Idempotent combination: the result is µ A 1 ∩A 2 (u) = min(µ A 1 (u), µ A 2 (u)) for all u ∈ U.
This combination can be straightforwardly extended to n sources and does not assume any dependency between the sources (information can be provided in a redundant and repeated way). However the number of sources which are agreeing on some possible values of x is not taken into account in this case.

• Product-based combination: the result is

µ A 1 ∩A 2 (u) = µ A 1 (u) • µ A 2 (u) for all u ∈ U.
This combination, which, as the previous one, can be justified in the setting of a probabilistic approach, requires independent sources, which is not always the case in practice. A more cautious hypothesis is that at least one of the source is right. In this case the pieces of information are combined disjunctively:

N.B. Nilpotent combination operators such that

µ A 1 ∩ A 2 (u) = max(0, µ A 1 (u) + µ A 2 (u) -1)
µ A 1 ∪A 2 (u) = max(µ A 1 (u), µ A 2 (u)) for all u ∈ U.
This assumes that the values rejected by both sources can be rejected and only these ones. For a general presentation of fusion operations, see (Dubois andPrade, 1994, 1995).

The proposed approach to fusion

Principle

In a previous work [START_REF] Dubois | Possibility theory and data fusion in poorly informed environments[END_REF], adaptive combination operators have been proposed, which are intermediary between disjunctive and conjunctive modes, and whose expression depends on the degree of consistency ht(A 1 ∩A 2 ) between the two sources. These combination operators may be computationally heavy to handle and do not preserve the shape of the fuzzy intervals. It is why we propose here a simplified approach (for trapezoidal membership functions), which enables us to have a combination process which is less costly. Since we can never exclude that one of the sources is wrong, the combination will perform the union of the supports S 1 and S 2 of A 1 and A 2 . Besides, if their cores N 1 and N 2 are overlapping, their intersection will be performed, in order, as far as possible, to single out a small subset of highly plausible values for the parameter under study.

Otherwise, the pieces of information will be combined disjunctively. Moreover, since the referential is ordered, we can further assume that the trapezoidal shape of the membership functions should be preserved, which leads to replacing S 1 ∪S 2 and N 1 ∪N 2 by their convex hulls, denoted by

[S 1 ∪S 2 ], [N 1 ∪N 2 ]
. Let ⊕ denote the combination of pieces of information A 1 and A 2 , then we have:

A 1 ⊕ A 2 = ([N 1 ∩ N 2 ], [S 1 ∪ S 2 ]) if N 1 ∩ N 2 ≠ Ø = ([N 1 ∪ N 2 ], [S 1 ∪ S 2 ]) otherwise. If N 1 = [a 1 ,b 1 ], N 2 = [a 2 ,b 2 ]
and a 1 ≤ a 2 , then:

• N 1 ∩ N 2 ≠ Ø if and only if b 1 ≥ a 2 ; • [N 1 ∩ N 2 ] = [a 2 , min(b 1 ,b 2 )] otherwise. • [N 1 ∪ N 2 ] = [a 1 , max(b 1 ,b 2 )]. Let us point out that if N 1 ∩ N 2 ∩ N 3 ≠ Ø, (A 1 ⊕ A 2 ) ⊕ A 3 = A 1 ⊕ (A 2 ⊕ A 3 ), i.e., the
combination is associative in this case and can be extended to n sources. Unfortunately, associativity no longer holds with inconsistent sources. However, the combination can be adapted to the case of n sources, as explained now.

Let A 1 , …, A n , be n pieces of fuzzy information. Let K be a maximal subset (in the sense of inclusion) made of consistent sources, then we can compute:

A 1 ⊕ A 2 ⊕… ⊕ A n = (Á i∈K N i , [ª i=1,n S i ])
If there are several such maximal subsets K* j of sources then we shall take

[ª j Á i∈K* j N i ]
in place of Á i∈K N i .

Justifying the fusion procedure

Viewing the core N j of each piece of information as the set of models of a logical formula, the collection of these pieces of information can be regarded as a propositional knowledge base. If the intersection of these cores is empty, the corresponding knowledge base is inconsistent. In presence of an inconsistent knowledge base, one may either look for a consistent subbase by eliminating formulas, or extends the notion of logical deduction in a way which is inconsistency-tolerant. The first approach supposes that we have reasons for choosing the formulas to be eliminated (it might be here sources for which we would be sure of their lack of reliability). We assume that this is not the case and we are led to adopt the second attitude. A consequence from an inconsistent knowledge base will be considered as sure if this is a consequence from all maximal consistent subbases [START_REF] Rescher | On inference from inconsistent premises[END_REF][START_REF] Benferhat | Some syntactic approaches to the handling of inconsistent knowledge bases -Part 1: The flat case[END_REF]. Building a maximal consistent subbase amounts to keep the greatest number of formulas, and thus to eliminate as little information as possible. If we do not know what formula (or source) to eliminate, we would have no reason of choosing between the maximal consistent subbases. From a semantical point of view, this amounts to consider that the models of an inconsistent knowledge base are only made of the union of the models of all the maximal consistent subbases. This corresponds exactly, in terms of sources, to the combination of cores described above, namely ª j Á i∈K* j N i where Á i∈K* j N i is the set of models of K* j . The idea is here of applying a logical approach to fusion problems. It should be pointed out that performing Á i∈K* j N i relies on an hypothesis of optimistic combination as already said. It is impossible that all the sources in a super-set of K* j are altogether reliable. The chosen combination avoids to have to decide about a sub-group of sources which are not wrong, and assumes the greatest possible number of reliable sources, for improving information.

Algorithm

The K* j 's can be obtained by means of a sorting procedure on the cores taking advantage of the ordered structure of U. We have to look for the maximal consistent subsets of {N 1 , …, N n }. Let N i = [a i ,b i ]. We have the following result:

The m maximal consistent subsets of {N 1 , …, N n } are K 1 , …, K m , such that K j = A j -B j where A j = {N k , a k ≤ c s(j) } and B j = {N k , b k < c s(j) }, where the c s(j) are obtained using the following procedure: i) Rank in increasing order the 2n numbers {a i , i= 1, n} ∪ {b i , i= 1, n}; let c 1 ≤… ≤ c 2n denote the result.

Moreover, let us denote type

(i) = a if c i is of the form a k and = b if c i is of the form b k .
ii) and let s(1),…, s(m) be the m positions in the sequence of c i such that type(s(j)) = b and type(s(j)

-1) = a. Indeed any intersection of intervals is of the form [a i , b j ] (with maybe i = j). The intersections of maximal consistent subsets of {N 1 , …, N n } have a minimal size in the sense of inclusion. Thus, let [a i , b j ] be such minimal interval. If we could find b k such that a i < b k < b j or a k such that a i < a k <b j this means that N k is included in any maximal consistent subset including N i and N j , and that the interval [a i , b j ] is not minimal, which leads to a contradiction. Then any position j in the sequence of c i such that type(j) = b and type(j -1) = a, determines a maximal consistent subset and any maximal consistet subset is characterized by such a position in the sequence. The maximal consistent subset of intersections [a i , b j ] is defined by the subset of the N k 's which contain [a i , b j ], then a k ≤ a i (which is equivalent to a k ≤ b j since [a i , b j ] is minimal) and b k ≥ b j . Thus all the N k such that a k are ranked before b j except those whose b k are also before b j , i.e., K j = A j -B j .

This leads to the following algorithm starting from the sequence c 1 ≤… ≤ c 2n . Algorithm:

List = Ø K = Ø for i = 1, 2n -1
If type(i) = a add to K N k such that c i = a k if also type(i + 1) = b add K to List If not delete from K N k such that c i = b k end for List will contain all the maximal consistent subsets of{N 1 , …, N n }. NB : if a i = b i , the ordering should be done as if a i < b i . If a i = b j the ordering should be done as if a i < b j for taking into account the intersection between N i and N j which then reduces to a point.

Example

N 1 = [1, 8]; N 2 = [2, 4]; N 3 = [3, 9], N 4 = [5, 10], N 5 = [5, 6]; N 6 = [7, 11].
We have the ordering: a 1 , a 2 , a 3 , b 2 , a 4 , a 5 , b 5 , a 6 , b 1 , b 3 , b 4 , b 6 . The algorithm first finds K = {N 1 , N 2 , N 3 }. Then finding b 2 , K is kept in List. N 2 is deleted from K, and N 4 and N 5 are added. Then the algorithm finds b 5 and adds {N 1 , N 4 , N 3 , N 5 } to List. It deletes N 5 from K and then adds N 6 , then finds b 1 . Then {N 1 , N 3 , N 4 , N 6 } is added to List. We might stop there, but the algorithm still makes K empty. to get a more precise result, it presupposes an independence assumption between the sources since it is based on a counting. If [ª i=1,n S i ] is found to be too large, one can apply the above method to the supports instead of the cores and take [ª j Á i∈K*j

S i ] as support for the result, where K*j denotes a maximal consistent subset of {S 1 , …, S n }.

Sources with unequal reliability levels

The information about the reliability of a source can be expressed under two different forms:

-either one can estimate the probability that a source is reliable (because one can have access to the proportion of times when it provided wrong information in the past, for instance), -or we have a more qualitative information only, such as the considered source has 'a small reliability', or is 'very reliable', or is more reliable than another one. This seems to be often the case in practice.

In any case, it is assumed that the set of sources can be partitioned into subgroups of sources of equal reliability which can be linearly ordered from the more reliable to the less reliable one. This reliability ordering can depend on the considered attribute, since some sources may be more reliable for some topics than for others.

The proposed fusion procedure consists in i) applying the approach of Section 3 inside each subgroup where the sources play the same role; ii) combining the partial results by starting with the most reliable group using the following principle. Let i and j be two groups of sources such that i is more reliable than j. Then if the information given by i is consistent with the information given by j a conjunctive combination is performed. Otherwise only the information given by source i is kept.

When the information to be combined is represented under the form of fuzzy intervals A i and A j , a weighted combination is performed, where the importance of the most reliable source is 1 and the importance of the other source is the degee of consistency between the two sources (height(A i ∩A j )).

Let us assume for instance that we have two groups of sources: "confidential" sources and "public" sources. The former are supposed to be more reliable than the latter. After the fusion step inside each group we get two fuzzy intervals represented by the two pairs (N 1 , S 1 ) and (N 2 , S 2 ) for the "confidential" and the "public" sources respectively. Then, after fusion we shall get the following result (N, S):

N = N 1 ∩ N 2 if N 1 ∩ N 2 ≠ Ø = N 1 otherwise S = [S 1 ∪ S 2 ].
The disjunctive fusion of supports is justified in order not to neglect any information, since it may happen that a less reliable source has the right information.

Remark: In case of two sources of unequal reliability, we might think of applying an approach based on conditioning in the spirit of Bayesian updating. This would lead to consider the least reliable sources as providing an a priori information to be revised by the information coming from the most reliable sources. The above proposal agrees with the conditioning view. But this latter approach does not provide any result if the sources are altogether inconsistent.

In some situations, it may happen that multiple pieces of information are given by the same source (possibly at different time instants). Three approaches may be considered for this problem of multiple values inside a source i) if information may become obsolete one may consider that the most recent information is the right one. This view albeit natural is not always suitable;

ii) regard each piece of information as provided by a particular source; iii) perform partial fusion inside each source, before merging the unique, thus obtained, pieces of information (one by source).

The two latter approaches are not equivalent for the cores. In general, the results obtained by each of the two methods are not comparable: any of the two may give more precise results than the other in some cases.

Examples : Source 1 gives N 1 and N 2 such that N 1

∩ N 2 ≠ Ø, source 2 gives N 3 such that N 2 ∩ N 3 ≠ Ø,
and N 3 ∩ N 1 = Ø. Then we get

N 1 N 2 N 3 N 1 ∩ N 2 N 1 ∩ N 2 ∪ N 3 N 1 ∩ N 2 ∪ N 2 ∩ N 3 N 1 N 2 N 3 ⊃
If source 1 gives N 1 and N 2 such that N 1 ∩ N 2 ≠ Ø, source 2 gives N 3 and N 4 such that N 3 ∩ N 4 ≠ Ø ;

assume N 2 ∩ N 3 ≠ Ø, the other intersections being empty, then we can obtain :

N 1 ∩ N 2 ⊃ N 3 N 4 N 1 N 2 N 1 ∩ N 2 ∪ N 3 ∩ N 4 N 1 N 2 N 3 N 4 N 1 ∩ N 2 ∪ N 2 ∩ N 3 ∪ N 3 ∩ N 4 N 3 ∩ N 4
it is enough to combine the two previous cases for obtaining results which are not comparable. Let 3 sources source 1 :

N 1 N 2 source 2 : N 3 N 4 source 3 : N 5 Hypothesis : N 1 ∩ N 2 ≠ Ø, N 2 ∩ N 5 ≠ Ø, N 3 ∩ N 4 ≠ Ø, N 2 ∩ N 3 ≠ Ø (all other intersections empty).
Then the inside-source combination followed by a combination of the partial results gives R

1 = (N 1 ∩ N 2 ) ∪ (N 3 ∩ N 4 ) ∪ N 5 . The direct combination gives R 2 = (N 1 ∩ N 2 ) ∪ (N 2 ∩ N 5 ) ∪ (N 2 ∩ N 3 ) ∪ (N 3 ∩ N 4 ). Clearly R 1 ⊄ R 2 since N 5 ⊄ R 2 , and R 2 ⊄ R 1 since N 2 ∩ N 3 ⊄ R 1 .
Consequently the choice of a preliminary fusion step for the values given by the same source before the global fusion step should be motivated by the nature of the pieces of information coming from the same source, when they make a whole, proper to the source. By contrast, if the pieces of information are felt as heterogeneous, without any explicit link between them, it would be better to consider each piece of information as a particular source.

Interaction of expertise and fusion

Let us assume that we have at our disposal some (fully reliable) expertise linking the parameters which can be estimated by the sources, through relations or equations. If an equation applies to pieces of information given by source S 1 for an object, it should also applies to the corresponding pieces of information given by source S 2 which describes the same object.

The available expertise should enable us to improve the description of the considered object by modifying the result of the fusion. The question is to know if the expertise should be applied first inside each source and then we perform the fusion of the pieces of information refined thanks to the expertise, or if we only apply the expertise to the result of the fusion performed on the initial data. In case of conjunctive combination (as performed on the cores in the approach of Section 3), the two methods give the same result. This is no longer true with disjunctive fusion (which is applied to the supports), as shown by the following example:

Fusing conjunctive information

Multiple-valued attributes

An attribute is said to be multiple-valued if it can take several values simultaneously. For instance, the attribute "age of the child(ren) of a person" may include several values if the person has several children. The represention of this type of data (called 'conjunctive data' ) when it is pervaded with uncertainty, requires the use of possibility distributions on the power set 2 U , the set of subparts of referential U. Then a multiple-valued attribute x will be associated with the possibility distribution π x such that

∀ E ⊆ U, π x (E) = Possibility(x = E).
Clearly, the representation of imprecision for multiple-valued attributes is exponential, in general.

Since the referential U is supposed to be linearly ordered, we might assume that π x (E) > 0 holds only if E is an interval, but this is not entirely satisfactory. Disjoint unions of intervals cannot be excluded.

Practically, we have to use a simplified, thus approximate, representation proposed by [START_REF] Dubois | Incomplete conjunctive information[END_REF] and Yager (1987Yager ( , 1988)). Let us first consider the case of an all-or-nothing distribution (π x (E) ∈ {0,1} thus an "enclosing" approximation of E(x), which is more imprecise (values which are not possible may be regarded as possible). However the gain in simplicity for the representation is spectacular since we have only to handle pairs of fuzzy sets, which can be compared with one fuzzy set for singlevalued attributes.

Fusing multiple-valued attribute information

Regarding information fusion, principles remain the same as for single-valued attributes but they lead to different algorithms on the approximate representation. The fusion of multiple-valued attributes does not seem to have received much attention in the scientific literature, although it leads to fusion methods which are dual from the previous ones. Indeed a conjunctive combination of conjunctive intervals is a set union, and a disjunctive combination of conjunctive intervals is a set intersection. For instance, if source i provides information (E *i , E* i ) for i = 1 or 2, and if these pieces of information are consistent, it is easy to see that the conjunctive combination gives

(E *1 ,E* 1 ) ∩ (E *2 , E* 2 ) = (E *1 ∪E *2 , E* 1 ∩E* 2 )
We can see that there are more values which are certain and less values which are possible, This shows that the imprecision has diminished. Indeed

{E, E *1 ∪ E *2 ⊆ E ⊆ E* 1 ∩ E* 2 } = {E, E *1 ⊆ E ⊆ E* 1 } ∩ {E', E *2 ⊆ E ⊆ E* 2 } (since E ⊆ E" and E' ⊆ E" ⇔ E ∪ E' ⊆ E" E ⊆ E' and E ⊆ E" ⇔ E ⊆ E' ∩ E").
Thus the above result is indeed the approximation of E 1 (x) ∩ E 2 (x). In the same way, the disjunctive

combination E 1 (x) ∪ E 2 (x), to be used if E 1 (x) ∩ E 2 (x) = Ø leads to compute (E *1 , E* 1 ) ∪ (E *2 ,E* 2 ) = (E *1 ∩E *2 , E* 1 ∪E* 2 )
This can be similarly justified. The precision has decreased since there are more possible values and less certain ones.

Note that the case where E The delicate point is the search for maximal consistent subsets. It seems that this problem has never been considered in the literature as far as we know. For the moment, it is unclear if efficient methods can be found, although the problem can be stated rigorously.

1 (x) ∩ E 2 (x) = Ø

Conclusion

This paper has sketched a simple approach to information fusion, which allows for a treatment of inconsistencies between sources. Some questions which are not often addressed in the literature, such as the handling of multiple-valued attributes, or of relations between (single-valued) attributes. A comparaison with other combination modes existing in the possibility theory is still to be made. Moreover, the proposed approach is mainly based on the manipulation of the cores and the supports of the distributions; a generalization to any level cuts would be of interest.

  k = max{|K|, Á i∈K N i ≠ Ø} be the maximal number of consistent sources; the maximality in the sense of inclusion can be replaced by a cardinality criterion which only keeps the consistent subsets of cardinality k. Nevertheless, athough this enables us

  Example : Data provided by the sources: Source A : X = [10, 12], Y = [ 2,3], Z = [0, 15] Source B : X = [0, 11], Y = [3, 4], Z = [1, 6]

  ) and let E(x) = {E, π x (E) = 1} the set of conjunctive values possible for x. An approximate representation of E(x) can be made by means of two nested subsets (E * , E*) with E * ⊆ E* such that E * = Á{E ∈ E(x)}; E* = ª{E ∈ E(x)}. E * is the set of individual values certainly taken byx. The complement of E* is the set of individual values completely excluded for x. We may have E * = Ø (one does not know any value for sure); one may also have E* = U (none value is known for impossible). In the general case where π x can take intermediary degrees of possibility, π x can be approximated by a pair of nested fuzzy sets such that∀ u ∈ U, µ E * (u) = inf u∉E 1 -π x (E), µ E* (u) = sup u∈E π x (E).It is easy to see that∀ E ∈ E(x), E * ⊆ E ⊆ E*but the converse is wrong: one may have E * ⊆ E ⊆ E* and π x (E) = 0. It can be checked that (Dubois and Prade, 1988) we have µ E * (u) > 0 ⇒ µ E* (u) = 1 i.e., in terms of core and support S(E * ) ⊆ N(E*); individual values which are somewhat certain are among the completely possible ones. (E * , E*) is

  1 ) ∪ S(E *2 ) ⊄ S(E* 1 ) ∩ S(E* 2 ) If N(E *i ) = [a i , b i ], N(E* i ) = [c i , d i ], we have to check separately N(E *i ) ⊄ N(E* 1 ) ∩ N(E* 2 ) for i = 1,2.

  ∪ E *2 ⊄ E* 1 ∩ E* 2 (an individualvalue which is certain becomes impossible) which entails (but not the converse) E 1 (x) ∩ E 2 (x) = Ø.The disjunctive combination may become useless if E *1 ∩ E *2 = Ø and E* 1 ∪ E* 2 = U, since everything then becomes possible. The advantage of the approximate representation of the imprecision of multiple-valued attribute information is that it leads to partial reuse of fusion algorithms from the single-valued case. Let us assume that we take for E* i and E *i a representation by pairs (core, support), we will then have an imprecise conjunctive information under the form of four nested subsets:N(E *i ) ⊆ S(E *i ) ⊆ N(E* i ) ⊆ S(E* i ) due to theproperty recalled in 6.1. The information combination in the multiplevalued case is made in a similar way as in the singlevalued case. The inconsistency test in the general case (with intermediary levels of possibility) becomes :(E *1 , E* 1 ) is inconsistent with (E *2 , E* 2 ) if

	can be
	tested on the approximate representation by means
	of the following sufficient condition for
	inconsistency
	(E *1 , E* 1 ) is inconsistent with (E *2 , E* 2 ) if and
	only if E *1

Source C : X = [3, 7], Y = 2, Z = [1,5] Result of the fusion:

Result obtained by applying the expertise to the result of the fusion :

But the correct method modifies the information first by applying the expertise for each source; it gives for the same initial data :

and the result of the final fusion is :

The first treatment, computationally simpler, does not propagate the constraints as much as possible and thus lead to evaluations which have a support which may be too large.