Benjamin Quost
email: quostben@hds.utc.fr

Marie-Hélène Masson
email: massonmar@hds.utc.fr

Thierry Denoeux
email: tdenoeux@hds.utc.fr

Refined classifier combination using belief functions

Keywords: Classification, classifier combination, information fusion, theory of belief functions, Dempster-Shafer theory

We address here the problem of supervised classification using belief functions. In particular, we study the combination of non-independent sources of information. In a companion paper [1], we showed that the cautious rule of combination [2], [3] may be best suited than the widely used Dempster's Rule to combine classifiers in the case of real data. Then, we considered combination rules intermediate between the cautious rule and Dempster's rule. We proposed a method for choosing the combination rule that optimizes the classification accuracy over a set of data. Eventually, we mentioned a generalized approach, in which a refined combination rule best suited to complex dependencies of the sources to combine is learnt.

Here, we extensively study this latter approach. It consists in clustering the sources according to some measure of similarity; then, one rule is learnt for combining the sources within the clusters, and another for combining the results thus obtained. We conduct experiments on various real data sets that show the interest of this approach.

I. INTRODUCTION

The theory of belief functions [START_REF] Shafer | A mathematical theory of evidence[END_REF], [START_REF] Smets | The Transferable Belief Model[END_REF] has been accepted as a powerful tool for solving classification problems [START_REF] Fabre | Presentation and description of two classification methods using data fusion based on sensor management[END_REF]- [START_REF] Quost | Pairwise Classifier Combination using Belief Functions[END_REF]. In this framework, experts express their belief on the value taken by an unknown variable using belief functions. Mathematical tools have been proposed for manipulating and aggregating such items. Dempster's rule of combination, also known as the conjunctive rule of combination (CoRC) [START_REF] Shafer | A mathematical theory of evidence[END_REF], [START_REF] Smets | The Transferable Belief Model[END_REF], [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] plays a central role in the theory of belief functions.

As pointed out in [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF], this rule requires that the belief functions combined be distinct. Hence, a cautious rule of combination (CaRC) was proposed in [START_REF] Denoeux | The cautious rule of combination for belief functions and some extensions[END_REF], [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF], allowing the combination of information coming from non distinct sources, by counting each elementary piece of information only once during the combination. It was also pointed out that both the CoRC and the CaRC may be seen as elements of infinite families of combination rules.

In a companion paper [START_REF] Quost | Adapting a Combination Rule to Non-independent Information Sources[END_REF], we considered a supervised classification problem. Given a set of classifiers C 1 , . . . C p giving partial information on the actual class of a test pattern x, we proposed a method to learn the rule of combination that gives the best classification results over a set of patterns. We then proposed to generalize this method, by clustering and combining sources according to their dependency. We showed the interest of this approach on a series of synthetic toy problems.

In this paper, we focus on this latter approach. We consider a set of classifiers that provide information on a pattern to be classified. We propose a measure of similarity between these sources; using this measure, clusters of sources may be identified. Then, we learn two rules of combination: one is used to combine information within the clusters; the other, to combine together the results obtained in the previous step.

In Section II, we recall the notions on belief functions that will be needed, and fix the notations. In Section III, we detail our method for clustering the sources and learning adequate combination rules. Results on real data sets are reported and commented in Section IV. Section V concludes the paper.

II. FUNDAMENTALS OF BELIEF FUNCTIONS

In this article, we adopt the Transferable Belief Model (TBM) [START_REF] Shafer | A mathematical theory of evidence[END_REF], [START_REF] Smets | The Transferable Belief Model[END_REF], [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized bayesian theorem[END_REF] as an interpretation of the theory of belief functions. The main notions are recalled in this section.

A. Basic Definitions 1) Representing Items of Evidence with Belief Functions:

Let C be a classifier giving information on the actual class of a test pattern x. This information may be represented by a basic belief assignment (bba) m, defined as a mapping from 2 Ω to [0; 1] satisfying A⊆Ω m(A) = 1 (the notation 2 Ω denotes the powerset of Ω). A subset A ⊆ Ω such that m(A) > 0 is called a focal set of m, and the basic belief mass (bbm) m(A) quantifies the belief that the actual class of x is in A: this belief cannot be given to more precise hypotheses B ⊆ A due to lack of information. The bbm m(∅) quantifies the belief that x belongs to none of the classes of the set Ω. A bba is said to be:

• dogmatic, if Ω is not a focal set;
• simple, if it has at most two focal sets, including Ω;

• categorical, if it is simple and dogmatic (therefore, if it has only one focal element that is not Ω); • normal, if ∅ is not a focal set, and subnormal otherwise;

• consonant, if all its focal sets A 1 , . . . , A N are nested:

∅ ⊆ A 1 ⊆ • • • ⊆ A N ⊆ Ω.
Any subnormal bba m can be normalized; the normalization operation is defined by:

m * (A) = m(A) 1 -m(∅) , ∀A ⊆ Ω. (1)
A bba m may also be represented by its associated plausibility, belief, commonality, or implicability functions, denoted by pl, bel, q, and b, respectively. Note that these functions are in one-to-one correspondence; they may be obtained from each other through linear transformations.

2) Conjunctive Combination and Decision Making: Two bbas m 1 and m 2 , provided by distinct sources of information C 1 and C 2 , may be combined using the conjunctive rule of combination (CoRC) ∩ [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF], also known as (the unnormalized) Dempster's rule:

m 1 ∩ 2 (A) = X∩Y =A m 1 (X)m 2 (Y ), ∀A ⊆ Ω. (2)
The resulting bba m 1 ∩ 2 summarizes all the information provided by C 1 and C 2 . Several other combination rules have been defined [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF], [START_REF] Yager | On the Dempster-Shafer framework and new combination rules[END_REF]; however, although these rules may prove useful in a variety of practical applications, they have often been criticized for lacking theoretical justification. When a decision needs to be taken, the bba m that quantifies knowledge of the actual class of x is transformed into a pignistic probability distribution [START_REF] Smets | The Transferable Belief Model[END_REF]: m is first normalized, and then each bbm m * (A) is divided equally between the ω k ∈ A:

BetP (ω k ) = ω k ∈A m * (A) |A| , ∀ω k ∈ Ω. (3)
Let us define the operator Bet by: BetP = Bet(m). This operator is clearly nonlinear. It should also be remarked that a same BetP generally corresponds to various bbas; we may then define:

Bet -1 (BetP ) = {m : Bet(m) = BetP } .
In Section II-C, we will present a method for selecting a bba in the set Bet -1 (BetP ), according to additional requirements.

B. Weights of Belief

Any non dogmatic bba may be represented by its weight function (wf) w [START_REF] Shafer | A mathematical theory of evidence[END_REF], [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF]. Transforming any representation of m into w is non-linear: for example, w may be computed from q by: w

(A) = A⊆B q(B) (-1) |B|-|A|+1 . (4)
The weights of belief satisfy w(A) ≥ 0, for all A ⊂ Ω. If w(A) ≤ 1, ∀A ⊂ Ω, the bba is said to be separable. The smaller is the weight w(A) < 1, the higher our confidence in A; weights w(A) > 1 may be interpreted as degrees of diffidence to A. In the case of consonant bbas, computing the wf becomes simpler [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]. Let the values pl k = pl({ω k }) be ordered by decreasing order:

1 ≥ pl 1 ≥ pl 2 ≥ • • • ≥ pl K > 0.
Then, using notations A k = {ω 1 , . . . , ω k }, we have:

w(A) =      pl 1 A = ∅, pl k+1 pl k A = A k , 1 ≤ k < K 1 otherwise . (5)
Only the subsets A k (1 ≤ k ≤ K) and ∅ may be focal elements of the resulting weight function: thus, it is consonant.

The ∩ -combination of two weight functions w 1 and w 2 may be processed by:

w 1 ∩ 2 (A) = w 1 (A)w 2 (A), ∀A ⊂ Ω. (6)
It becomes here obvious that the CoRC is commutative and associative. However, it is not idempotent: in particular, combining a separable wf with itself results in decreasing all the weights w(A) = 1. More generally, ∩ -combining the outputs of two non-independent classifiers generally results in counting several times the identical items of evidence.

1) Partial Orderings on Bbas:

The informational content of two bodies of evidence may be partially ordered by comparing their corresponding wfs [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]. Let m 1 and m 2 be two nondogmatic bbas; m 1 is w-more committed than m 2 , which we write m 1 ⊑ w m 2 , iff:

w 1 (A) ≤ w 2 (A), for all A ⊂ Ω.
This property is satisfied iff there exists a separable bba m 3 such that m 1 = m 2 ∩ m 3 [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF].

The q-ordering [START_REF] Dubois | The principle of minimum specificity as a basis for evidential reasoning[END_REF] is obtained by replacing w with q: m 1 is q-more committed than m 2 (m 1 ⊑ q m 2 ) iff q 1 (A) ≤ q 2 (A), for all A ⊂ Ω. It is weaker than the w-ordering, as we have

m 1 ⊑ w m 2 ⇒ m 1 ⊑ q m 2
while the converse is generally not true.

2) The Cautious Rule of Combination: Two bodies of evidence may proceed from common information; thus, a cautious approach to combining them should count each item only once [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF], [START_REF] Smets | Combining non-distinct evidences[END_REF], [START_REF] Smets | Data fusion in the Transferable Belief Model[END_REF]. In the most extreme case where the two bodies are identical, the result should be the body itself -equivalently, the combination rule should be idempotent.

The cautious rule of combination (CaRC) ∧ consists in applying the min to the wfs, instead of the product [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]:

w 1 ∧ 2 (A) = w 1 (A) ∧ w 2 (A), ∀A ⊂ Ω, (7)
where a∧b stands for min(a, b), and where

w 1 ∧ 2 = w 1 ∧ w 2 .
Thus, it is straightforward that w 1 ∧ 2 is the least w-committed of the weight functions that are more w-committed than both w 1 and w 2 . The CaRC is associative, commutative, and idempotent, as is the min operator. Whereas w 1 ∩ 2 (A) depends on both w 1 (A) and w 2 (A), the CaRC retains only the smallest weight to compute w 1 ∧ 2 (A) (that is, for separable bbas, the strongest support to A).

C. Least q-committed Bba Induced by a Probability Distribution

The q-ordering may be used to reverse the pignistic transform. To avoid giving unjustified support to any A ⊆ Ω, we may select m = Bet -1 qlc (BetP ), the least q-informative bba m in Bet -1 (BetP ):

m ∈ Bet -1 (BetP ), m ⊑ q m, for all m ∈ Bet -1 (BetP ).
In [START_REF] Dubois | A definition of subjective possibility[END_REF], it was shown that m is a consonant bba. It may be obtained by first computing pl({ω i }) for all 1 ≤ i ≤ K and then deducing pl(A), for all A ⊆ Ω with |A| > 1:

pl({ω i }) = K j=1 min (p i , p j ) , (8)
pl(A) = max ω k ∈A pl({ω k }). (9)
Remark that using [START_REF] Smets | The Transferable Belief Model[END_REF], the wf may be computed directly with (8): we need not use [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF]. This transformation will help us build bbas from probabilistic classifiers. Indeed, interpreting the output of such a classifier as a pignistic probability distribution over Ω, we may then define m = Bet -1 qlc (BetP ) as its credal output.

III. LEARNING THE COMBINATION RULE

Both the CoRC and the CaRC may be seen as "extremal" rules of combination: the former combines distinct evidence, the latter evidence that could have been induced by the same information. We stress here that information may be nondistinct without being exactly the same. Thus, one could select a combination rule that best suits a set of data.

Both the product and the min operator are triangular norms (t-norms) on [0; 1] [START_REF] Klement | Triangular norms[END_REF]. Let us consider a parameterized family of t-norms counting both these operators as members [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]. Thus, in the case of separable bbas, selecting a t-norm by picking a parameter value defines implicitly a combination rule that is intermediate between the CoRC and the CaRC. In this article, we consider Frank's family:

x ⊤s y = log s 1 + (s x -1) (s y -1) s -1 , (10)
where log s defines the logarithm function with base s. Here, parameter s defines the t-norm: the min operator is retrieved as s → 0, and the product as s = 1.

Remark that the parameter s does not represent a degree of dependency between the information to be merged. Thus, fitting the combination rule to the sources necessits first to estimate their degree of dependency, and then to find a corresponding parameter value. The relationship between both may be complex, and obviously depends on the t-norm used. We stress that the notion of dependency depends on the information considered. It is well known that estimating the degree of dependency between variables may be delicate: one should first identify its nature, and then evaluate the degree using a proper measure. For example, the correlation coefficient is inefficient for modelling nonlinear dependency.

In this paper, we consider supervised classification problems. Therefore, rather than considering the inputs of the classifiers (the variables), we propose to fit parameter values by maximizing the classification accuracy achieved after combination of their outputs. Thus, our method allows to find the combination rule that will give the best classification results, even if the dependency between the information sources is arbitrarily complex.

A. Fitting a Single Combination Rule to Training Data

In a companion paper [START_REF] Quost | Adapting a Combination Rule to Non-independent Information Sources[END_REF], we proposed a simple procedure for learning a combination rule that gives the best classification results over a set of data. It consists in parameterizing the combination rule, and then mining the parameter space for a value that minimizes some error criterion. We briefly describe this procedure in the following.

Given a set of training patterns, we train a classifier on each of the q variables. For each pattern x being classified, we thus have q bbas m i {x}. Combining the m i {x} for any parameter value s gives a bba m{x}, from which the pignistic probability distribution BetP {x} used to classify x is then obtained.

Given a value of s, we compute the average squared difference between the pignistic probabilities and binary indicator variables encoding class membership:

E = n j=1 betp{x j } -δ{x j } 2 ; (11)
here, for any pattern x j from a validation set, pignistic probabilities betp{x j } = (BetP {x j }(ω 1 ), . . . , BetP {x j }(ω K )) are obtained from m{x j }, and the crisp memberships of x j to the classes are given by δ{x j } = (δ 1 {x j }, . . . , δ K {x j }) (we have δ k {x j } = 1 if x j ∈ ω k , and 0 otherwise). We thus select the value s that minimizes E using a dichotomic search algorithm, stopping the search when the width of the interval to search is less than some constant (here, 10 -10 ).

B. Refined Combination of the Sources

The method presented in Section III-A consists in learning a single rule to combine classifiers with the best classification accuracy. It relies on the implicit assumption that all the sources share the same pairwise dependency. However, this assumption may be too simplistic. Indeed, some source C 1 may have a tendency to be highly redundant with some other source C 2 , yet being uncorrelated with another source C 3 . Choosing a single rule close to the CoRC could imply giving too much weight to the outputs of C 2 , while being too close to the CaRC could lead to ignore important information provided by C 3 .

To evaluate the dependency between two sources, we propose to compute a measure of discrepancy between their outputs. A distance d J between two (normal) bbas m 1 and m 2 was defined in [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF], by:

dJ (m1, m2) = v u u u t X A⊆Ω B⊆Ω (m1(A) -m2(A)) (m1(B) -m2(B)) 2/pA,B , (12)
where the weights p A,B are defined by:

p A,B = |A ∩ B| |A ∪ B| , ∀A = ∅, B = ∅. (13)
We propose to define the distance D i,j between two classifiers C i and C j as the average distance between the (paired) bbas they provided when evaluating a set of patterns:

D i,j = n k=1 d J (m i {x k }, m j {x k }). (14)
Thus, D i,j may be used as an indicator of the redundancy between the outputs of C i and C j . Remark that although d J appears to be perfectly suited to our purpose -as it was defined for evaluating the performance of a classification algorithm, other distances between two bbas may be used. We did not evaluate our method using such other measures. Let C 1 , . . . , C q be our set of classifiers. For each classifier, we evaluate all training patterns, and we compute the distance D i,j for each pair (C i , C j ). A hierarchy on the classifiers may be built upon these distances. Figure 1 shows the dendrogram representing this hierarchy, for the ecoli dataset (Section IV-B2 details how we generated this dendrogram). We then choose a cut value to cluster the set of classifiers. For instance, in Figure 1, cutting at a level 0.4 would give 3 clusters: {C 1 , C 2 }, {C 3 , C 4 , C 5 }, and {C 6 , C 7 }. Remark that this clustering step may be automated.

After the classifiers have been clustered according to these distances, we propose to first combine their outputs in the various clusters, and then to combine the resulting bbas together. Thus, two combination rules have now to be learnt: a within-cluster rule for processing the combination within the clusters, defined by a parameter value s 1 ; and a betweencluster rule for computing the final bba, defined by a parameter value s 2 . We propose to use a method similar to that described in Section III-A; except that we now select the pair of values ( s 1 , s 2 ) that minimizes E. Taking the ecoli data as an example, the outputs of C 1 and C 2 would first be combined using s 1 , as well as those of C 3 , C 4 , and C 5 , and those of C 6 and C 7 ; the three resulting bbas would then be combined using s 2 .

Our method necessits to combine the bbas for various parameter values; hence, the overall complexity depends pricipally on the size of the bbas, which is generally exponential in the number K of classes. However, the bbas considered here being consonant, they have K + 1 focal elements. Although this is not the case after the combination step, the complexity may be limitated by considering only the subsets of Ω with nonzero belief mass. Methods for reducing the combination complexity may be found in [START_REF] Denoeux | Approximating the Combination of Belief Functions using the Fast Moebius Transform in a coarsened frame[END_REF] and in the references therein.

IV. RESULTS

A. Description of the Data

We ran experiments on various real datasets, whose characteristics (number of classes, of features, and the numbers of patterns in the training and test sets) are presented in Table I. These datasets may be found in the UCI Machine Learning repository at http://archive.ics.uci.edu/ml/. We simplified the letter, optdigits, and pendigits datasets by selecting six classes in the former case (the 4th, 5th, 12th, 21st, 22nd and 24th ones), and five classes in the two latter (the 1st, 2nd, 5th, 6th and 10th).

B. Learning the Classifiers and the Refined Combination Rules 1) Training the Classifiers:

For each dataset, we trained a classifier (logistic regression) on each variable. For any test point x, we are thus able to provide q probability distributions p i on Ω. Then, we computed the q-least committed bbas m i whose pignistic probabilities are p i , using [START_REF] Smets | The Transferable Belief Model[END_REF] and [START_REF] Quost | Pairwise Classifier Combination using Belief Functions[END_REF]. These bbas were combined using the CoRC, the CaRC, an intermediate rule learnt as defined in Section III-A, and a refined combination involving two rules such as described in Section III-B.

2) Clustering the Sources: The dendrograms representing the hierarchies between classifiers were built upon the pairwise average distances D i,j using Ward's aggregation criterion. They are reported in Figures 1 to 7. The set of classifiers was then clustered: Table II provides the cut levels that were chosen by the user, in order to form between 3 and 5 clusters.

Basically, the dendrograms provide information about the relative pairwise dependencies of the classifiers. Taking the pageblocks dataset as an example, it may be remarked that all the classifiers except E 4 and E 5 have a tendency to provide bbas that are very close to each other. On the other hand, the dependencies between the classifiers of the letter or optdigits datasets are quite varied.

Note that interpreting the average distance between two classifiers remains delicate: indeed, the bbas they provide obviously depend on the classification algorithm employed. Moreover, d J may suffer (just like any other distance) from the curse of dimensionality, as the size of the frame Ω grows. 3) Learning the Within-Cluster and Between-Cluster Rules: The values s 1 and s 2 were then determined as follows. For each dataset, 5 × 1 cross-validation was used to form training/validation sets from the original training set. Candidate values were picked for s 1 and s 2 ; for each pair (s 1 , s 2 ), the error criterion defined by Eq [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF] was computed over the 5 validation sets and averaged. The values s 1 and s 2 minimizing this average were chosen. They are reported in Table III.

C. Numerical Results

Error rates obtained with the CoRC, the CaRC, the intermediate combination rule (InRC) described in Section III-A corresponding to the optimal parameter value s, and the refined combination strategy (ReRC) obtained with values s 1 and s 2 , are provided in Table III, together with 95% confidence intervals. The best result is underlined, and printed in bold as well as results that were not judged significantly different by a McNemar test [START_REF] Dietterich | Approximate statistical tests for comparing supervised classification algorithms[END_REF] at level 5%. Analyzing the results presented in Table III yields the following remarks. The interest of learning the rule of combination is clearly assessed by the good results given by the refined combination strategy: they are generally the best over the four combination rules evaluated (the only exception being the pendigits dataset). This suggests that the dependency between the combined classifiers may be complex enough to justify learning a complex, refined combination strategy, involving determining a within-cluster and a between-cluster rule instead of a single one.

The CoRC gives the best classification results for the pendigits dataset only, and it does not perform significantly worse that the best rule for the letter and optdigits datasets. Let us further remark that learning the combination rule (be it a single rule or a pair of within-cluster and between-cluster rules) never yielded the CoRC. This should draw attention to the fact that assuming independence between classifiers may be unreasonable. Henceforth, other fusion strategies may be preferable to Dempster's rule when combining information coming from various sources.

In addition, we may observe that the combination rules learnt for the ecoli, glass, and pageblocks datasets are very close to the cautious rule. Quite surprisingly, in the case of the pendigits and optdigits datasets, the within-cluster combination rule is closer to the CoRC than the between-cluster combination rule (in the former case, the within-cluster rule is the CoRC, and the between-cluster rule is the CaRC). This phenomenon is not yet entirely clear; a possible explanation could be that information combined within the clusters are rich and diverse, and hence the information resulting of the various within-cluster combinations are close to each other.

V. CONCLUSIONS

In this paper, we addressed the problem of supervised classification by classifier fusion, in the framework of belief functions theory. We presented a method for adapting a combination rule to a set of data. First, the discrepancy between each pair of classifiers was measured by computing the average distance between their outputs. Then, classifiers are clustered based on these average pairwise distances. The classifiers within the various clusters are combined using a within-cluster rule, and within-cluster combined outputs are then pooled using a between-cluster rule. Both rules are learnt by minimizing an error criterion over validation data.

We evaluated four combination rules on seven real data sets: the conjunctive rule of combination (also known as the unnormalized Dempster's rule), the cautious rule of combination, a single rule learnt to fit the data processed, and the refined combination scheme presented in this paper. Numerical results obtained show the interest of learning a complex combination strategy adapted to the dependency of the data.

Future work may focus on three points. First of all, the impact of the clustering phase on the classification results may be studied, and the clustering step may be automated. Learning the coefficients defining the combination rules requires searching the parameter space. Although this learning phase needs to be done only once, a fast procedure for determining accurately these values would be a plus. Eventually, one could also imagine refining further the combination strategy, by proposing a hierarchy between the classifiers: at each level of the hierarchy, classifiers could then be combined using an adequate combination rule. Such a combination strategy should allow fitting even more precisely the dependency of the classifiers.

Figure 1 .

 1 Figure 1. Dendrogram: distances between classifiers, ecoli data set.

  classifiers average distance between the outputs of the classifiers dendrogram, Glass dataset

Figure 2 .

 2 Figure 2. Dendrogram: distances between classifiers, glass data set.

  classifiers average distance between the outputs of the classifiers dendrogram, Letter1 dataset

Figure 3 .

 3 Figure 3. Dendrogram: distances between classifiers, letter data set.

17

 17

  25 20 15 16 7 3 10 4 19 11 21 28 29 2 6 12 22 30 8 23 9 1 5 13 26 24 14 18 classifiers average distance between the outputs of the classifiers dendrogram, Optdigits1 dataset

Figure 4 .

 4 Figure 4. Dendrogram: distances between classifiers, optdigits data set.

Figure 5 .

 5 Figure 5. Dendrogram: distances between classifiers, pageblocks data set.

  classifiers average distance between the outputs of the classifiers dendrogram, Pendigits1 dataset

Figure 6 .Figure 7 .

 67 Figure 6. Dendrogram: distances between classifiers, pendigits data set.


Sébastien Légaré

Jean Krivine

Jérôme Feret
email: jerome.feret@ens.psl.eu

Distinguishing Context Dependent Events in Quotients of Causal Stories

Keywords: Causality, Rule-based modelling, Visualisation, Graph folding, Concurrency '

Causality analysis of rule-based models allows the reconstruction of the causal paths leading to chosen events of interest. This potentially reveals emerging paths that were completely unknown at the time of creation of a model. However, current implementations provide results in the form of a collection of stories. For large models, this can amount to hundreds of story graphs to read and interpret for a single event of interest. In this work, we hence develop a method to fold a collection of stories into a single quotient graph. The main challenge is to find a trade-off in the partitioning of story events which will maximize compactness without loosing important details about information propagation in the model. The partitioning criterion proposed is relevant context, the context from an event's past which remains useful in its future. Each step of the method is illustrated on a toy rule-based model. This work is part of a longer term objective to automatically extract biological pathways from rule-based models.

Introduction

Rule-based modelling [1,2] is well suited to the construction of large models characteristic of systems biology. Rules distinguish themselves from reactions by focussing only on the part of molecules that changes during a transition, rather than fully defining the species involved. This lets rule-based models avoid combinatorial explosion issues and obviates the need to reduce models toward a predefined goal. Subsequent analysis can then reveal emerging properties that were initially completely unknown by the modellers.

Causality analysis is one of the most interesting analyses to perform on rule-based models. It allows the reconstruction of the causal paths, also called stories, leading to a chosen event of interest [START_REF] Vincent Danos | Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models[END_REF]. Considering a protein involved in some pathology for instance, it would provide a quantitative account of each upstream molecule's contribution to its activation. However, current implementations [START_REF] Vincent Danos | Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models[END_REF][START_REF] Laurent | [END_REF] present the results of causality analysis as a collection of individual stories. In a large systems biology model, this can amount to hundreds of story graphs to read and interpret for a single event of interest.

The goal of this work is to develop a compact representation that allows the visualisation of all the paths leading to an event of interest on a single graph. To do so, we fold a collection of stories by merging events that are deemed equivalent. The broader the definition of equivalence between events, the more compact the folded representation is. Yet, folding too much may merge events which are similar but play different roles in the propagation of information. Thus, a trade-off has to be found. Here, we refine each event in stories with some contextual information about its past, modulated by the usefulness of that context in its future. We use this additional information to define the quotient of events in families of stories. As a result, we obtain a quotient that remains compact but provides a better insight on the way information is processed in the models.

Kappa Rule-Based Model

The toy model below is written in Kappa language [START_REF] Boutillier | The Kappa platform for rule-based modeling[END_REF] and will be used to illustrate the method developed in this work. Such toy model does not represent the kind of large systems that can typically benefit from rule-based modelling. However, it features events whose context is not trivially determined and is hence well suited to highlight the details of the methodology. For a description of the Kappa syntax, see [START_REF] Boutillier | The Kappa platform for rule-based modeling[END_REF]. Briefly, bonds are noted as a shared number between brackets. For example, A(x [1]), C(x [1]) means that A and C are bound through their respective site x. A dot between brackets, like A(x[.]), means that a site is free of any bond. States are given between braces. For example, C(z{p}) means here that site z of C is phosphorylated. In the definition of rules, a forward slash indicates an edit. What appears before the slash is a precondition, the binding or state value that a site must take to allow the firing of a rule. After the slash is the new binding or state value taken by a site after the firing of the rule. Brackets and braces without a forward slash inside them represent required preconditions that are unchanged by the firing of the rule. Fig. 1 shows a sketch of the toy model, which can be described as follows. Kinases A and B can bind to protein C, each through a different binding site. Both A or B can phosphorylate site z of protein C once they are bound. Protein C can bind to D, but only after C was phosphorylated. A or B can then phosphorylate D as well, but only if they are in a same molecular complex as D. The phosphorylation of protein D is set as the event of interest. This simplified model is representative of scaffolding as it can occur in cell signalling. Protein C for instance could contain SH2 domains [START_REF] Wagner | Molecular mechanisms of sh2and ptb-domain-containing proteins in receptor tyrosine kinase signaling[END_REF] to recruit kinases which would in turn phosphorylate multiple residues within a complex.

Stories

Traces of computation from rule-based models can be sampled by the means of stochastic simulators [START_REF] Danos | Scalable simulation of cellular signaling networks[END_REF][START_REF] Faeder | Rule-based modeling of biochemical systems with BioNetGen[END_REF]. Yet, such traces are not convenient to understand the mechanisms of signal processing because they contain satellite events that are unnecessary. They also describe precisely the order in which events occurred even when these events are causally independent. However, traces may be post-processed in order to extract relevant information. Event structures [START_REF] Winskel | Event structures[END_REF] abstract away the interleaving order between causally independent events. Then, irrelevant events may be discarded by using operational research techniques [START_REF] Vincent Danos | Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models[END_REF] or heuristic approaches [START_REF] Laurent | [END_REF]. The remaining events are the necessary steps required to reach the event of interest. Their representation in the form of a graph is called a story. Note that stories represent concurrency, or parallelism. When a given node has more that one incoming edge, those edges share an and relationship. In story 3 for instance, events "C binds D" and "B binds C" are both required to enable "B phos D". Alternative paths cannot be represented within a story. They are rather shown as distinct stories.

Method

The story folding method presented in this work is implemented in the Python package Kappa-Pathways [START_REF] Légaré | KappaPathways[END_REF]. The package is currently under development and still requires the implementation of additional functionalities before fully fledged pathway extraction from rule-based models can be performed.

Quotient of stories with concurrency

The main goal of this work is to build a compact representation of the results obtained from causality analysis of rule-based models. To do so, we seek to fold any arbitrarily large collection of stories into a single quotient graph. The first intuitive way to partition story events is according to the Kappa rules that they represent. That is, looking at the four stories from Fig. 2, all nodes with the same label are merged together. Fig. 3, left shows the quotient obtained by simply partitioning story events according to their corresponding Kappa rule. While this graph does summarize some of the information from all the stories, it also clearly introduces ambiguities. For instance, readers could be mislead into thinking that completing event "A binds C" is sufficient to reach "A phos D", while in reality "C binds D" is also necessary. This ambiguity arise because when a node in the quotient graph has more than one incoming edge, it is impossible to know whether each edge comes from distinct stories or concurrent branches of a same story. Still, the graph from Fig. 3, right remains misleading. It suggests paths that are not coherent with the model. For instance, the path "A phos C" →"C binds D" →"B phos C" seems allowed by itself. According to the model, it is instead only possible if "B binds C" also occurs concurrently. This inconsistent interpretation of the quotient graph tells us that a partitioning of events simply based on Kappa rules folds the stories too much. The next section presents additional event partitioning criteria that solve those ambiguities.

Relevant context

Looking back at stories 1 and 2 from Fig. 2 provides a hint into why folding too much produces a quotient with paths that are inconsistent with the model. Those two stories both pass through a same type of event, namely "C binds D". However, their preceding events are different. Although the latest modification that both stories went through is the same, the accumulated state of the molecules involved up to that point is different. They may hence have different futures open to them. That is, not only the events themselves matter, but also the context that was built up in their past. Still, not all past context may be relevant. A good trade-off must be found in the information that is kept about the context of each event. Too much information leads to a blow-up in the quotient graph that may become unreadable or even too costly to compute, whereas too few information may not be discriminant enough. In this work, we propose that the appropriate amount of information to keep corresponds to the relevant context.

The relevant context of a given event consists in the context from its past which remains useful in its future. More precisely, this corresponds to the locally relevant context, which appears relevant within a same story. We also define the globally relevant context as the context from an event's past which is found useful in the future of other stories which pass through an event corresponding to the same Kappa rule. The information about context can be extracted from the trace that was used to produce the stories. The following steps describe how we obtain context for each event and determine its relevance.

Edit nodes

First, for each story, the modifications that are performed by every event are extracted from the trace as illustrated on Fig. 4. Each individual modification is called an edit and is represented by a separate node connected to the event which it originates from. Edit nodes are labelled according to the modification that they correspond to using the Kappa syntax. Edges are then added from edit nodes to the downstream events which require them later in the story. Edges that do not correspond to any edge from the original story are referred to as transitive edges.

Locally relevant context

Second, the locally relevant context is determined as illustrated on Fig. 5. The following substeps are performed iteratively from top to bottom on the graph with added edit nodes. a) The current node is selected as the first edit node from the top of the graph whose locally relevant context was not already computed, excluding edits coming from introduction nodes. b) The past context of the current node is gathered. It first consists in the immediate upstream edit nodes from the current node, ignoring transitive edges. Neighboring nodes are also added as the edit nodes coming from the same event or introduction node as any upstream node. Lastly, the context that was found for those upstream and neighbor nodes during previous iterations is added to the past context of the current node. c) The locally relevant context is found as any past context node that remains useful in the future of the current node. On the graph, this corresponds to any past context node that have at least one path to a node which is reachable from the current node. The path should however not pass through the current node or an edit node that is incompatible with the edit from the past context node. Fig. 5, left shows the first iteration of the steps described above on story 3 from Fig. 2. It provides the locally relevant context associated with event "A binds C". Two elements of context are found relevant, as displayed by the two green edges and the inscription z[.]{u} on the label of the highlighted current node. This indicates that the locally relevant context is that protein C must have its site z free of any bond, and also unphosphorylated. Those two edits from the past are useful for future events "C binds D" and "A phos C", respectively. Also note the red dashed edges which indicate past context nodes whose path to the future of the current node was blocked by incompatible edits.

Dphos

C(y[1]), B(y[1])

A C

A(x[.]) C(z{u}) C(z[.]) C(y[.]) C(x[.])

A binds C

A(x[1]), C(x

Globally relevant context

Third, the globally relevant context is evaluated. The goal is to harmonize what is considered relevant across all stories. Suppose an element of context which exists in the past of two different stories, but is found irrelevant in the first story and locally relevant in the second. Then, the first story must be revised, knowing that this given element of context is actually relevant when considering the whole system.

To do so, the total possible context of each edit is first computed. It corresponds to any context that was found locally relevant across all the edit nodes that represent a same edit among all stories. Then, the globally relevant context of a given edit node is found as the elements from the total context which exist in the past of that edit node within the story where it is found. Finally, elements of context are removed if they are found globally relevant across all edit nodes that represent a same edit. Fig. 6 shows the four stories now with edit nodes containing the globally relevant context associated with each event. It turns out that the only relevant context is whether protein C was bound to kinase A or B when it got phosphorylated. Looking back at the toy model, this is precisely what was expected. Note that this context, the binding to A or B, was not locally relevant in story 3 as seen on Fig. 5. It was instead added as globally relevant from stories 1 and 2. Also, the locally relevant context C(z[.]) from Fig. 5 was removed since it is equally present in all four stories and is hence not discriminating.

Quotient of contextualized stories

It is now possible to fold the contextualized stories from Fig. 6. Using edit nodes and their context defined in the previous, we can now partition the nodes in a way that will preserve the information propagation dictated by the model. Edit nodes across all stories are merged if they have the same edit and the same relevant context. Event nodes are merged if they correspond to the same Kappa rule and their target edit nodes also have the same relevant context.

Fig. 6. The four stories from Fig. 2 annotated with relevant context on edit nodes. Introduction nodes were removed for clarity. Fig. 7, left presents the resulting quotient. There are two nodes representing rule "C binds D". One corresponds to the case where C was priorly bound to A, and to other to the case where it was bound to B. There is no way to read this graph by following a path that is not allowed by the model. Fig. 7, right shows a more compact graph obtained by removing the contextual information about events that we have used to get a more precise quotient. We consider this last graph as the correct representation of the paths to the event of interest, as opposed to the two graphs from Fig. 3 which both lead to a wrong interpretation. This work describes a method to build a compact representation for the visualisation of causality analysis results in rule-based modelling. A collection of stories provided by a current implementation of causality analysis [START_REF] Vincent Danos | Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models[END_REF][START_REF] Laurent | [END_REF] is folded into a single quotient graph. The main challenge is to find a partitioning of story events which maximizes compactness of the quotient graph without loosing important details about how information propagates in the model. The appropriate partitioning criterion suggested here is the relevant context, the context from an event's past which remains useful in its future. By folding stories based on their events type and relevant context, a quotient graph is obtained that faithfully represents all the paths to an event of interest.

Scalability of the method is important since its true usefulness lies in its application to large models. While rigorous optimization and benchmarking was not performed yet, we tested the current implementation on a model of human cell signalling comprising about three thousand Kappa rules. This model is considered large because representing it in a reaction-based setting, like in a Petri net, would lead to a combinatorial explosion with millions of nodes. Calculation time of quotient graphs for events of interest from this model is usually of the order of several minutes on an average personal computer. Those graphs are typically easy to visualize with less than fifty ordered nodes. For cases where the graph becomes larger and confusing to read, quantitative data from the model's execution can be used to prune away least impactful paths.

The story folding method reported in this paper is a milestone in a longer term objective to automatically extract biological pathways from rule-based models. Other functionalities are planned to be implemented within the KappaPathways [START_REF] Légaré | KappaPathways[END_REF] package to reach that goal. Those include counterfactual analysis [START_REF] Laurent | Counterfactual resimulation for causal analysis of rule-based models[END_REF], the representation of inhibitions from negative influences and the ordering of events participating in feedback loops.

  %agent: A(x) %agent: B(y) %agent: C(x y z{u,p}) %agent: D(z s{u,p}) %init: 100 A() %init: 100 B() %init: 100 C() %init: 100 D() %obs: 'Dphos' |D(s{p})| %mod: [true] do $TRACK 'Dphos' [true];

Fig. 1 .

 1 Fig. 1. Sketch of the toy model used to illustrate the method developed in this work.

Fig. 2

 2 Fig. 2 shows the four stories corresponding to the four possible ways of obtaining phosphorylated D from the initial conditions of the toy model. Story 1 represents the case where kinase A phosphorylates both C and D. Story 2 is similar, but uses kinase B instead. Stories 3 and 4 represent cases where kinase A phosphorylates C and then kinase B phosphorylates D, or the other way around.

Fig. 2 .

 2 Fig. 2. The four possible stories to the phosphorylation of protein D in the toy model. Events are shown as rectangular nodes. Introduction nodes are shown as circles and represent the involvement of a new individual protein in the story. The event of interest appears as a red octagonal node. Edges represent precedence relationships. All graphs in this work were built with Graphviz [10].

Fig. 3 .

 3 Fig. 3. Quotients of the four stories from Fig. 2. Left) Quotient obtained by partitioning event nodes according to their corresponding Kappa rule. Right) Quotient with hyperedges representing concurrency. Introduction nodes were removed for clarity.

Fig. 3 ,

 3 Fig.3, right illustrates a simple solution to the representation of concurrency in the quotient graph. Before the folding operation, any story edges that have the same target are regrouped in a single hyperedge with many sources and one target. The ensuing quotient allows a clear distinction between concurrent and alternative paths.

Fig. 4 .

 4 Fig. 4. Addition of edit nodes to story 3 from Fig. 2. Edit nodes are shown in blue and their labels represent modified sites in Kappa syntax. Transitive edges are shown in gray.

Fig. 5 ,

 5 Fig.5, right shows the second iteration of locally relevant context determination. It now focusses on the context of event "A phos C". Only the edit node coming from event "A binds C" counts here as an immediate upstream node since the edge to C(z{u}) is transitive. C(z[.]) and C(z{u}) are nevertheless subsequently added as past context because the were found as relevant during the previous iteration.

Fig. 5 .

 5 Fig. 5. Highlight of the nodes and edges involved in the determination of the locally relevant context. The first (left) and second (right) iterations are shown on story 3 from Fig. 2. The current node of each iteration is shown in yellow with bold border. Past context nodes have a bold dashed border. Paths from past context nodes to any node reachable by the current node are shown with thick green edges. Paths that are blocked by an edit node that is incompatible with the edit from the past context node are shown with dashed red edges. The locally relevant context obtained at the end of each iteration is written in thin font on the label of the current node.

Fig. 7 .

 7 Fig. 7. Quotient graph obtained after considering relevant context. Left) Full version of the graph. Right) Compact version with edit nodes removed.

Acknowledgements

This work has been partially supported by French ANR project DCore ANR-18-CE25-0007.


Benjamin Quost
email: benjamin.quost@hds.utc.fr

Thierry Denoeux
email: thierry.denoeux@hds.utc.fr

Marie-Hélène Masson

Adapting a Combination Rule to Non-Independent Information Sources

Keywords: Classification, classifier combination, sensor fusion; theory of belief functions

In this article, we address the combination of non-independent sources to solve classification problems, within the theory of belief functions. We show that the cautious rule of combination [1, 2] is wellsuited to such problems. We propose a method to learn the combination rule from training data, and we generalize it in the case of complex dependence of the sources. We demonstrate the validity of our approach on several synthetic and realdata sets.

Introduction

The theory of belief functions [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Smets | The Transferable Belief Model[END_REF] is a powerful tool for modelling and manipulating knowledge. In this framework, beliefs held by experts are quantified by belief functions. Various mathematical tools have been proposed for manipulating such items; in particular, the conjunctive rule of combination (CoRC) [START_REF] Smets | The Transferable Belief Model[END_REF][START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] plays a central role in the theory of belief functions.

As pointed out in [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF], a major limitation of this rule comes from the requirement that the items of evidence combined be distinct. A cautious rule of combination (CaRC) was recently proposed [START_REF] Denoeux | The cautious rule of combination for belief functions and some extensions[END_REF][START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF], allowing the combi-nation of information coming from non distinct sources. In a nutshell, it consists in counting each elementary piece of information only once during the combination. It was also pointed out that both the CoRC and the CaRC may be seen as elements of infinite families of combination rules.

In this paper, we address a supervised classification problem, in which several classifiers C 1 , . . . C p provide partial information on the actual class of a test pattern x. To classify x, we need to combine the information given by each of those classifiers. We propose a method to learn the rule of combination that will give the best classification results over a set of patterns. We then propose to generalize this method, by clustering and combining sources according to their dependency. We demonstrate the interest of our approach by appling it to several synthetic and real datasets.

In Section 2, we recall basic knowledge of belief functions and fix notations. In Section 3, we propose a simple procedure to adapt the combination rule to a classification problem, and results are reported in Section 4. The method is generalized in Section 5, where numerical results are also presented. Section 6 concludes the paper.

Fundamentals of Belief Functions

Our approach is based on the Transferable Belief Model (TBM) [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Smets | The Transferable Belief Model[END_REF][START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized bayesian theorem[END_REF], the main notions of which are recalled in this section.

Basic Definitions

Representing Items of Evidence with Belief Functions

Let C be a classifier that provides information on the actual class of a test pattern x.

We suppose here that this information may be quantified by a basic belief assignment (bba) m, defined as a mapping from 2 Ω to [0; 1] which satisfies A⊆Ω m(A) = 1 (here, 2 Ω denotes the powerset of Ω). A subset A ⊆ Ω such that m(A) > 0 is called a focal set of m. The empty set ∅ may be a focal set: m(∅) quantifies the belief that x belongs to none of the classes of the set Ω. A bba is said to be:

• dogmatic, if Ω is not a focal set;

• simple, if it has at most two focal sets, including Ω;

• categorical, if it is simple and dogmatic ;

• normal, if ∅ is not a focal set, and subnormal otherwise;

• consonant, if all its focal sets A 1 , . . . , A N are nested:

∅ ⊆ A 1 ⊆ • • • ⊆ A N ⊆ Ω.
Note that any subnormal bba m can be normalized; the resulting bba is defined by:

m * (A) = m(A) 1 -m(∅) , ∀A ⊆ Ω. (1)
We may represent m by its associated plausibility, belief, commonality, or implicability function, denoted by pl, bel, q, and b, respectively. All are in one-to-one correspondence, and may be obtained from each other through linear transformations. For instance, we have:

m(A) = A⊆B (-1) |B|-|A| q(B). (2)

Conjunctive Combination and Decision Making

Two bbas m 1 and m 2 , provided by independent classifiers C 1 and C 2 , may be combined using the conjunctive rule of combination (CoRC) ∩ [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] : for all A ⊆ Ω,

m 1 ∩ 2 (A) = X∩Y =A m 1 (X)m 2 (Y ). (3)
The resulting bba m 1 ∩ 2 embeds all the information provided by C 1 and C 2 . Other combination rules have been defined [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF][START_REF] Yager | On the Dempster-Shafer framework and new combination rules[END_REF]; however, they are often criticized for lacking theoretical justification, though they may prove useful in a variety of practical applications.

Once a decision has to be made, a bba m is transformed into a pignistic probability distribution [START_REF] Smets | The Transferable Belief Model[END_REF]. The pignistic transform consists in normalizing m, and then dividing each mass m * (A) equally between the ω k ∈ A:

BetP (ω k ) = ω k ∈A m * (A) |A| , ∀ω k ∈ Ω. ( 4
)
We may then write BetP = Bet(m). This transform is clearly nonlinear. It should also be remarked that a same BetP generally corresponds to various bbas; we may then define:

Bet -1 (BetP ) = {m : Bet(m) = BetP } .
In Section 2.2.2, we will present a method for selecting a bba in Bet -1 (BetP ), according to additional requirements.

Weights of Belief

Any non dogmatic bba may be represented by its weight function (wf ) w [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Smets | The canonical decomposition of a weighted belief[END_REF]; for example, w may be computed from q by:

w(A) = A⊆B q(B) (-1) |B|-|A|+1 . (5)
The weights of belief satisfy w(A) ≥ 0, for all A ⊂ Ω. If w(A) ≤ 1, ∀A ⊂ Ω, the wf is said to be separable. The smaller is the weight w(A) < 1, the higher our confidence in A; weights w(A) > 1 may be interpreted as degrees of diffidence to A. In the case of consonant bbas, computing the wf becomes simpler [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]. Let the pl({ω k }) be ordered by decreasing order:

1 ≥ pl 1 ≥ pl 2 ≥ • • • ≥ pl K > 0. Then: w(A) =        pl 1 A = ∅, pl k+1 pl k A = A k , 1 ≤ k < K 1 otherwise . (6)
The nested focal sets of the resulting bba are thus

A k = {ω 1 , . . . , ω k }, for 1 ≤ k ≤ K, or ∅.
Let w 1 and w 2 be two wfs, and w 1 ∩ 2 denote the result of their ∩ -combination; then:

w 1 ∩ 2 (A) = w 1 (A)w 2 (A), ∀A ⊂ Ω. ( 7
)
The CoRC is commutative and associative. However, it is not idempotent: combining the wf corresponding to a separable bba with itself results in decreasing all the weights w(A) = 1. More generally, ∩ -combining the outputs of two non-independent classifiers generally results in counting several times same items of evidence.

Partial Orderings on Bbas

A partial ordering on the informational content of two non-dogmatic bbas m 1 and m 2 may be built, by comparing their corresponding wfs [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]. The bba m 1 is w-more committed than m 2 , which we write m 1 ⊑ w m 2 , iff:

w 1 (A) ≤ w 2 (A), for all A ⊂ Ω.
This property is satisfied iff there exists a separable bba m 3 such that

m 1 = m 2 ∩ m 3 [2].
The q-ordering [START_REF] Dubois | The principle of minimum specificity as a basis for evidential reasoning[END_REF] is obtained by replacing w with q: m 1 is q-more committed than m 2 (m 1 ⊑ q m 2 ) iff q 1 (A) ≤ q 2 (A), for all A ⊂ Ω. This latter ordering is weaker than the former: indeed, we have m 1 ⊑ w m 2 ⇒ m 1 ⊑ q m 2 , while the converse is generally not true.

Least q-committed Bba Induced by a Probability Distribution

The q-ordering may be used to reverse the pignistic transform. To avoid giving unjustified support to any A ⊆ Ω, it was proposed in [START_REF] Dubois | New semantics for quantitative possibility theory[END_REF] to select m = Bet -1 qlc (BetP ), the least q-informative bba m in Bet -1 (BetP ):

m ∈ Bet -1 (BetP ), m ⊑ q m, for all m ∈ Bet -1 (BetP ).
In [START_REF] Dubois | A definition of subjective possibility[END_REF], it was shown that m is a consonant bba, that may be obtained by first computing pl({ω i }) for all 1 ≤ i ≤ K; and then deducing pl(A), for all A ⊆ Ω with |A| > 1:

pl({ω i }) = K j=1 min (p i , p j ) , (8)
pl(A) = max ω k ∈A pl({ω k }). (9)
Remark that using [START_REF] Dubois | New semantics for quantitative possibility theory[END_REF], the wf may be computed directly with (8): we need not use (9).

The Cautious Rule of Combination

A cautious approach in combining two bodies of evidence would consist in counting each item only once [START_REF] Smets | Combining non-distinct evidences[END_REF][START_REF] Smets | Data fusion in the Transferable Belief Model[END_REF][START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF], considering that they may have been built on common information. In the most extreme case where the two bodies are identical, the result should be the body itself -hence, we seek an idempotent rule. As bringing new evidence aims at having more precise knowledge of the actual class of pattern x, the result should not be less committed than the inputs.

The cautious rule of combination (CaRC) ∧ consists in applying the min operator, instead of the product, to the wfs [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]:

w 1 ∧ 2 (A) = w 1 (A) ∧ w 2 (A), ∀A ⊂ Ω, ( 10
)
where a ∧ b stands for min(a, b), and where

w 1 ∧ 2 = w 1 ∧ w 2 .
The CaRC is associative, commutative, and idempotent, as is the min operator. Provided that m 1 and m 2 be separable, w 1 ∧ 2 is obviously at least as wcommitted as both w 1 and w 2 .

Thus, whereas w 1 ∩ 2 (A) depends on both w 1 (A) and w 2 (A), the CaRC retains only the smallest to compute w 1 ∧ 2 (A) (that is, for separable bbas, the strongest support to A).

3 Finding a Compromise Between the CoRC and the CaRC

Motivations

Both the CoRC and the CaRC may be seen as "extremal" rules of combination: the former combines independent bodies of evidence, the latter, wfs that could have been induced by identical information. However, information may be non-distinct, without being identical: for example, two sensors may observe different but correlated variables.

Therefore, an intermediate between the CoRC and the CaRC may be best suited to combine such information. If we restrict ourselves to the combination of separable bbas [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF], they may be defined as follows. Both the product and the min operators being triangular norms (t-norms) on [0; 1] [10], one may consider a parameterized family of t-norms, counting both the product and the minimum as members [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]. Selecting a t-norm, by picking a parameter value, would implicitly define a combination rule, intermediate between the CoRC and the CaRC in the case of separable bbas. One may consider, for instance, Frank's family:

x ⊤s y = log s 1 + (s x -1) (s y -1) s -1 , (11)
where log s defines the logarithm function with base s. Here, parameter s defines the t-norm: the min operator is retrieved as s → 0, and the product as s = 1.

Preliminary Results

We created several two-class datasets, by generating numbers from a 10-dimensional multivariate Gaussian distribution, as follows:

• each marginal distribution has mean

µ 1 = 0 in class ω 1 , µ 2 = 1 in class ω 2 ,
and variance σ 2 1 = σ 2 2 = 1 in both classes;

• in each class, the first 9 variables are pairwise linearly correlated with coefficient ρ, the last one is independent of the others.

We trained a classifier (logistic regression [START_REF] Hastie | The elements of statistical learning: data mining, inference and prediction[END_REF]) on each variable. For each test point x, we are thus able to provide p = 10 probability distributions p i on Ω. Then, we computed the q-least committed bbas m i whose pignistic probabilities are p i , using ( 6) and ( 8). We combine the m i , and eventually we classify x.

For various values of s, we computed the average misclassification rate on ten test sets, using the corresponding rule of combination. Figures 1, 2 and 3 show the misclassification rate as a function of s, together with 95% confidence intervals, for datasets generated using correlation coefficients ρ = 0.1, ρ = 0.3 and ρ = 0.9. In these figures, the CoRC and the CaCR correspond to the rightmost and the leftmost points of the x axis, respectively. For ρ = 0.1 and ρ = 0.9, the best results are obtained, respectively, using the CoRC and the CaRC. The former case shows that the CaRC is sensible to errors: it only considers the strongest support to each focal set, and thus may lead to a wrong decision if this support is erroneous. When ρ = 0.9, the first 9 classifiers have a tendency to provide erroneous evidence simultaneously; thus, using the CaRC enables the 10 th classifier to correct such errors, as its output weights as much as all the others. When ρ = 0.3, the best results are obtained for a value of s that corresponds to an intermediate rule of combination.

Learning the Combination Rule

Given a set of classifiers, we want to learn the combination rule that will give the best classification results on new data. We propose here a method to learn this rule, by selecting the parameter value optimizing the performances of the classifiers' ensemble on a set of data whose actual class is known.

Rather than computing error rates, we used a more sensitive criterion based on pignistic probabilities to estimate these performances. Let ⊤ s be the parameterized rule of combination (thereafter abbreviated as PaRC) defined by some parameter value s. Then, a bba m, quantifying our belief on the actual class of a test pattern x, is obtained by combining the outputs m i of the classifiers evaluating x:

m = m 1 ⊤ s . . . ⊤ s m p .
Then, finding an adequate value for parameter s can be done by solving:

s = arg min 0≤s≤1 n j=1 betp j -d j 2 ; ( 12
)
here, given any pattern x j from the validation set, betp j = (BetP j (ω 1 ), . . . , BetP j (ω K )) is the pignistic probability distribution obtained from m, and d j = (d j1 , . . . , d jn ) encodes its crisp membership to the classes (d jk = 1 if x j ∈ ω k , and 0 otherwise).

We propose to search the parameter space (restricted to ]0; 1]) for s. For example, we can use a dichotomic search algorithm, stopping when the width of the interval to search is less than some constant (e.g., 10 -10 ).

Results

We considered five synthetic datasets, generated as described in Section 3.2, characterised by ρ = {0.1, 0.3, 0.5, 0.7, 0.9}, and the realdata sets Ecoli, Glass, Segment, Vowel, and Waveform from the UCI Machine Learning Repository. To compute smoother estimates, we processed the mean of several values of the error defined by ( 12) obtained on various validation sets. These sets were either generated apart when possible -on each synthetic dataset, 5000 validation patterns were generated in each class -or obtained from the training sets via 5 × 2 cross-validation. For each dataset, we trained a classifier (logistic regression) on each variable, by the procedure described in Section 3.2. Error rates obtained with the CoRC, the CaRC, and the PaRC corresponding to the optimal parameter value, are provided in Table 2, together with 95% confidence intervals. The best re-sult is underlined, and printed in bold as well as results that were not judged significantly different by a McNemar test [START_REF] Dietterich | Approximate statistical tests for comparing supervised classification algorithms[END_REF] at level 5%. We may remark on the synthetic datasets that all error rates increase with the correlation of the features. This is not surprising, as less information becomes then available. The CoRC yields obviously the best results when the correlation is low, and the CaRC when it is high. The PaRC is close to the CoRC for ρ = 0.1; when ρ = 0.3 or ρ = 0.5, it is truly intermediate between the CoRC and the CaRC; when ρ = 0.7 and ρ = 0.9, learning the combination rule yields the CaRC itself.

On the real data sets, the CaRC was always learnt, except on the Waveform dataset for which an intermediate rule was learnt. The optimized rule gave the best results, except on the Vowel dataset, for which the CoRC performed better. The reason may be that the training and test distributions differ.

Refined Combination of Sources

The method presented above consists in adapting a unique combination rule to nonindependent data. It relies on the implicit assumption that all the classifiers have the same pairwise dependency, which may be too simplistic. For example, in the synthetic datasets we generated, all the sources share the same dependency but one, which is conditionally independent on the others.

A distance d J between two (normal) bbas m 1 and m 2 was defined in [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF], by:

d J (m 1 , m 2 ) = (m 1 -m 2 ) D (m 1 -m 2 ) ⊤ 2 , (13)
with an element D A,B of matrix D defined by:

D A,B = A ∩ B A ∪ B , ∀A = ∅, B = ∅. (14)
We computed the average distance between the outputs of each pair of classifiers, using ( 13)- [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized bayesian theorem[END_REF]. Figures 4 to 6 show the dendrograms representing the hierarchy built upon the shortest distance: at distance d J , two sets of classifiers are aggregated iff we can find a classifier in each set such that their distance to each other is d J . While for ρ = 0.1, the average distances range quite uniformly, for ρ = 0.3 and ρ = 0.9 we can see that the tenth classifier is clearly separated from the others.

Clustering the classifiers would lead to group the first nine, and leave the tenth one alone.

Hence, we can define a hierarchical rule of combination: the classifiers are clustered according to their pairwise average distances; their outputs are first combined in each cluster, and the resulting bbas are then combined.

We applied this combination strategy of the classifiers to the five synthetic data sets generated. We combined the first nine classifiers using a combination rule learnt as described in Section 3.3, and then we combined the tenth classifier using the CoRC. Table 3 shows the error rates (again, together with 95% confidence intervals) thus obtained. These rates were printed in bold when judged significantly 2.

These results are better than those obtained with other rules; the differences are significant except for ρ = 0.1. That demonstrates the interest of modeling all the knowledge on the dependency of the variables. One may also remark that the rule learnt is closer to the CaRC than previously: the reason is that the 10 th classifier (which is independent) is not considered in the learning step any more.

Conclusions

In this article, we addressed the problem of combining multiple sources for solving a classification problem. We concentrated on problems where the information sources are not independent. We studied the influence of the combination rule on classification results. We considered the commonly used Dempster's rule of combination [START_REF] Shafer | A mathematical theory of evidence[END_REF], and the cautious rule of combination [START_REF] Denoeux | The cautious rule of combination for belief functions and some extensions[END_REF][START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non-distinct bodies of evidence[END_REF]. The former requires that the combined sources be independent; the latter pools sources that may be provide identical information. We proposed to define a family of rules for separable bbas enclosing both as extremal cases, and to learn the rule that best suits the data processed.

On real data, the cautious rule often yields the best classification results, although we showed that Dempster's rule, or some rule intermediate between Dempster's rule and the cautious rule, may also give the best performances. Having demonstrated the validity of this method, we refined it by clustering classifiers using the average distance between their outputs. Thus, combination may be processed first within each cluster, the resulting bbas being then combined together.

Future work will focus on two points. First, we may cluster automatically the set of sources. In addition, searching the parameter space for several optimal values becomes computationally demanding when several rules have to be learnt. Efforts should be thus directed on deducing the combination rule of two (clusters of) classifiers using distances between classifier outputs.

  plotted as a function of the combination rule employed

Figure 1 :

 1 Figure 1: Misclassification rate plotted as a function of s; correlation coefficient ρ = 0.1.

  average misclassification rate plotted as a function of the combination rule employed

Figure 2 :

 2 Figure 2: Misclassification rate plotted as a function of s; correlation coefficient ρ = 0.3.

  plotted as a function of the combination rule employed

Figure 3 :

 3 Figure 3: Misclassification rate plotted as a function of s; correlation coefficient ρ = 0.9.

Figure 4 :

 4 Figure 4: Dendrogram of the average distances between the classifiers; ρ = 0.1.

Figure 5 :

 5 Figure 5: Dendrogram of the average distances between the classifiers; ρ = 0.3.

Figure 6 :

 6 Figure 6: Dendrogram of the average distances between the classifiers; ρ = 0.9.

Table 1

 1 gives the number of classes, of features, and the numbers of patterns in the training and test sets.

Table 1 :

 1 Description of the datasets.

	dataset	# classes # features
	Synthetic	2	10
	Ecoli	8	7
	Glass	6	9
	Segment	7	19
	Vowel	11	10
	Waveform	3	21
	dataset	number of patterns
		training	test
	Synthetic	2000	10000
	Ecoli	201	135
	Glass	139	75
	Segment	1400	910
	Vowel	528	462
	Waveform	1491	3509

Table 2 :

 2 Error rates of the CoRC, the CaRC and the PaRC, and 95% confidence intervals.

	data	CoRC	PaRC (b s)	CaRC
	Synth.	11.45	11.46 (0.75)	15.68

Table 3 :

 3 Error rates and confidence intervals given by a hierarchical rule of combination.

	dataset	results (b s)
	Synth.	11.34 (0.5)
	ρ = 0.1	[10.91;11.78]
	Synth. 17.66 (0.0625)
	ρ = 0.3	[17.14;18.19]
	Synth. 20.87 (4.75e-7)
	ρ = 0.5	[20.31;21.43]
	Synth.	22.68 (0)
	ρ = 0.7	[22.10;23.27]
	Synth.	23.91 (0)
	ρ = 0.9	[23.32;24.51]