Sébastien Destercke
email: desterc@hds.utc.fr

HEUDIASYC Benjamin Quost
email: quostben@hds.utc.fr

Correcting binary imprecise classifiers: local vs global approach

This paper proposes a simple strategy for combining binary classifiers with imprecise probabilities as outputs. Our combination strategy consists in computing a set of probability distributions by solving an optimization problem whose constraints depend on the classifiers outputs. However, the classifiers may provide assessments that are jointly incoherent, in which case the set of probability distributions satisfying all the constraints is empty. We study different correction strategies for restoring this consistency, by relaxing the constraints of the optimization problem so that it becomes feasible. In particular, we propose and compare a global strategy, where all constraints are relaxed to the same level, to a local strategy, where some constraints may be relaxed more than others. The local discounting strategy proves to give very good results compared both to single classifier approaches and to classifier combination schemes using a global correction scheme.

Introduction

In complex multi-class classification problems, a popular approach consists in decomposing the initial problem into several simpler problems, training classifiers on each of these sub-problems, and then combining their results. The advantages are twofold: the sub-problems obtained are generally easier to solve and thus may be addressed with simpler classification algorithms, and their combination may yield better results than using a single classification algorithm.

In this paper, we consider a classical decomposition strategy where each simple problem is binary; then, each classifier is trained to separate two subsets of classes from each other. When the binary classifiers return conditional probabilities estimating whether an instance belongs to a given class subset or not, these conditional probabilities are seldom consistent, due to the fact that they are only approximations of the (admittedly) true but unknown conditional probabilities. Usually, this inconsistency problem is tackled by considering some optimization problem whose solution is a consistent probability whose conditional probabilities are close to each of the estimated ones [START_REF] Hastie | Classification by pairwise coupling[END_REF][START_REF] Wu | Probability estimates for multi-class classification by pairwise coupling[END_REF]. This consistent probability is then considered as the final predictive model.

Imprecise probabilities are concerned with the cases where the available information is not sufficient (or too conflicting) to identify a single probability, and are therefore well adapted to the problem mentioned above. Due to their robustness, imprecise probabilistic models appear particularly interesting in those cases where some classes are difficult to separate, where some classes are poorly represented in the training set or when the data are very noisy. In a previous work [START_REF] Destercke | Combining binary classifiers with imprecise probabilities[END_REF], we proposed an alternative solution to classifier combination using imprecise probability theory [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF]. In this framework, binary classifiers return lower and upper bounds instead of a single evaluation. The case of precise outputs is retrieved when lower and upper bounds coincide.

As even imprecise outputs can turn out to be inconsistent, we initially proposed to apply a global discounting factor (found through a heuristic) to the classifiers. In this paper, we reformulate the problem so that discounting factors can be found by the means of efficient linear programming techniques. This also allows us to easily affect a discounting factor specifically to each classifier, thus adopting a local correction approach. In Section 2, we remind the necessary elements about imprecise probabilities and their use in binary classifiers combination. Section 3 then describes and discusses our discounting strategies, both the global and local one. Finally, we compare in Section 4 the two strategies for the special case of one-vs-one classifiers on several classical real data sets.

Imprecise probability: a short introduction

Let X = {x 1 , . . . , x M } be a finite space of M elements describing the possible values of (ill-known) variables (here, X represents the set of classes of an instance). In imprecise probability theory, the partial knowledge about the actual value of a variable X is described by a convex set of probabilities P, often called credal set [START_REF] Levi | The Enterprise of Knowledge[END_REF].

Expectation and probability bounds

A classical way to describe this set consists in providing a set of linear constraints restricting the set of possible probabilities in P (Walley's lower previsions [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF] correspond to bounds of such constraints). Let L(X ) denote the set of all realvalued bounded functions over X , and let K ⊆ L(X ). Provided K is not empty, one can compute expectation and probability bounds on a function f ∈ K.

When one starts from some lower bound E : K → R, it is possible to associate to it a (convex) set P(E) of probabilities such that

P(E) = {p ∈ P X |E(f ) ≥ E(f ) for all f ∈ K}, (1)
where P X denotes the set of all probability masses over X . Alternatively, one can start from a given set P and compute the lower expectation E : L(X ) → R and upper expectation E : L(X ) → R such that

E(f ) = sup p∈P E(f ) and E(f ) = inf p∈P E(f ),
These functions are dual, in the sense that E(f ) = -E(-f ).

In Walley's terminology [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF], E is said to avoid sure loss iff P(E) = ∅, and to be coherent iff for any f ∈ K we have E(f ) = inf p∈P(E) E(f ), i.e. E is the lower envelope of P(E).

Lower and upper probabilities of an event A ⊆ X correspond to expectation bounds over the indicator function 1 (A) (with 1 (A) (x) = 1 if x ∈ A, and 0 otherwise). When no confusion is possible, we will denote them P (A) and P (A) and they are computed as P (A) = inf P ∈P P (A) and P (A) = sup

P ∈P P (A).

Imprecise probabilities and binary classifiers

The basic task of classification is to predict the class or output value x of an object knowing some of its characteristics or input values y ∈ Y, with Y the input feature space. Usually, it is assumed that to a given input y correspond a probability mass p(x|y) modeling the class distribution, knowing that the instance y has been observed. Then, classifying the instance amounts to estimating p(x|y) as accurately as possible from a limited set of labeled (training) samples. A binary classifier on a set of classes X aims at predicting whether an instance class belongs to a subset A ⊆ X or to a (disjoint) subset B ⊆ X (i.e., A∩B = ∅). For probabilistic classifiers, the prediction takes the form of an estimation of the conditional probability P (A|A∪B, y) that the instance belongs to A (notice that P (B|A ∪ B, y) = 1 -P (A|A ∪ B, y) by duality).

In the case of imprecise classifiers, the prediction may be expressed as a set of conditional probabilities, expressed for example as a pair of values bounding P (A|A ∪ B) 1 . Let us denote by α j , β j the bounds provided by the j th classifier:

α j ≤ P (A j |A j ∪ B j ) ≤ β j (2)
and, by complementation, we have

1 -β j ≤ P (B j |A j ∪ B j ) ≤ 1 -α j . (3)
Combining binary classifiers then consists in defining a set P of probability distributions over X compatible with the available set of conditional assessments. To get a joint credal set from these constraints, we will turn them into linear constraints over unconditional probabilities. Assuming that P (A j ∪ B j ) > 0, we first transform Equations ( 2) and (3) into

α j ≤ P (A j ) P (A j ∪ B j ) ≤ β j and 1 -β j ≤ P (B j ) P (A j ∪ B j ) ≤ 1 -α j .
These two equations can be transformed into two linear constraints over unconditional probabilities:

α j 1 -α j P (B j ) ≤ P (A j ) and P (A i ) ≤ β j 1 -β j P (B j ),
or equivalently

0 ≤ (1 -α j ) xi∈Aj p i -α j xi∈Bj p i , (4)
0 ≤ β j xi∈Bj p i -(1 -β j ) xi∈Aj p i , (5)
where p i := p(x i ). Such constraints define the set of probability distributions that are compatible with the classifier outputs. Then, the probability bounds on this set may be retrieved by solving a linear optimization problem under Constraints ( 4) and ( 5), for all classifiers. Note that the number of constraints grows linearly with the number N of classifiers, while the number of variables is equal to the number M of classes. As the quantity of classifiers usually remains limited (between M and M 2 ), the linear optimization problem can be efficiently solved using modern optimisation techniques.

Example 1. Let us assume that N = 3 classifiers provided the following outputs:

P ({x 1 }|{x 1 , x 2 }) ∈ [0.1, 1 /3], P ({x 1 }|{x 1 , x 3 }) ∈ [ 1 /6, 0.4], P ({x 2 }|{x 2 , x 3 }) ∈ [ 2 /3, 0.8].
These constraints on conditional probabilities may be transformed into the following constraints over (unconditional) probabilities p 1 , p 2 , and p 3 :

1 /9p 2 ≤ p 1 ≤ 1 /2p 2 , 1 /5p 3 ≤ p 1 ≤ 2 /3p 3 , 2p 3 ≤ p 2 ≤ 4p 3 ,
Note that the induced set of probability distributions is not empty, since p 1 = 0.1, p 2 = 0.6 and p 3 = 0.3 is a feasible solution. Getting the minimal/maximal probabilities for each class then comes down to solve 6 optimization problems (i.e., minimising and maximising each of the unconditional probabilities p i , under the constraints mentioned above), which yields

p 1 ∈ [0.067, 0.182] p 2 ∈ [0.545, 0.735] p 3 ∈ [0.176, 0.31].
Here, we can safely classify the instance into x 2 .

Note that, in some cases, the classifiers may provide outputs that are not consistent. This is particularly the case when the classifiers are trained from distinct (non-overlapping) training sets, or when some of them provide erroneous information. Then, P = ∅. A solution may still be found provided by (some of) the constraints be relaxed in order to restore the system consistency.

Vacuous mixture as discounting operator

In some situations, it may be desirable to revise the information provided by a source of information, in particular when the source is known to be unreliable to some extent. Then, the knowledge induced by the source may be weakened according to this degree of unreliability. In most uncertainty theories, this socalled discounting operation consists in combining the original information with a piece of information representing ignorance through a convex combination.

In imprecise probability theory, the piece of information representing ignorance is the vacuous lower expectation E inf , defined such that for any f ∈ L(X ),

E inf (f ) = inf x∈X f (x).
Given a state of knowledge represented by a lower expectation E on K, the -discounted lower expectation E for any f ∈ K is

E (f ) = (1 -)E(f ) + E inf (6)
with ∈ [0, 1]. We may interpret E as a compromise between the information E (which is reliable with a probability 1 -) and ignorance. Note that we retrieve E when the source is fully reliable ( = 0), and ignorance when it cannot be trusted ( = 1).

Decision rules

Imprecise probability theory offers many ways to make a decision about the possible class of an object [START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF]. Roughly speaking, classical decision based on maximal expected value can be extended in two ways: the decision rule may result in choosing a single class or in a set of possible (optimal) classes. We will consider the maximin rule, which is of the former type, and the maximality rule, of the latter type. First, let us remind that for any x i ∈ X , the lower and upper probabilities P ({x i }), P ({x i }) are given by the solutions of the constrained optimisation problem P ({x i }) = min p i and P ({x i }) = max p i under the Constraints (4)-( 5), and the additional constraints xi∈X p i = 1, p i > 0. Then, the maximin decision rule amounts to classify the instance into class x such that

x := arg min

xi∈X P ({x i }).
Using this rule requires to solve M linear systems with 2N + M + 1 constraints and to achieve M comparisons.

The maximality rule follows a pairwise comparison approach: a class is considered as possible if it is not dominated by another one. Under the maximality rule, a class x i is said to dominate x j , written x i M x j , if E(f i→j ) > 0 with f i→j (x i ) = 1, f i→j (x j ) = -1 and f i→j (x) = 0 for any other element x ∈ X . The set of optimal classes obtained by this rule is then

X := {x i ∈ X | ∃x j s.t. x j M x i }.
This rule has been justified (and championed) by Walley [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF]. Note that finding X requires at most to solve M 2 -M linear programs (one for each pair of classes). Using the maximality rule may seem computationally expensive; however, its computation is easier in a binary framework, as shows the next property.

Proposition 1. 0.5 < P (x i |x i ∪ x j ) ⇒ x j ∈ X Proof. If 0.5 < P (x i |x i ∪ x j ), then p i > p j according to Equation (4). Assuming constraints (4) and ( 5) are feasible, i.e. induce a non-empty set P, computing E(f i→j ) > 0 comes down to solve the following optimisation problem:

min p i -p j (7)
with P ∈ P. Since any probability in P is such that p i > p j , the value of p i -p j is guaranteed to be positive, hence x j is preferred to x i (x i x j ).

Note that Proposition 1 only holds if the associated constraint has not been discounted.

Discounting strategies for inconsistent outputs

As remarked in Section 2.2, multiple classifiers may provide inconsistent outputs, in which case the constraints induced define an empty credal set P. In this section, we explore various discounting strategies to relax these constraints in order to make the set of probability distributions non-empty.

-discounting of binary classifiers

In this paper, we perform an -discounting for each classifier, in order to relax Constraints (4)-( 5) as described by Equation [START_REF] Levi | The Enterprise of Knowledge[END_REF]. For the j th classifier, we obtain from Constraints (4)-( 5) that E f j = 0 and E f j = 0 with

f j (x) =    1 -α j if x ∈ A j -α j if x ∈ B j 0 else and f j (x) =    1 -β j if x ∈ A j -β j if x ∈ B j 0 else .
This gives the following discounted equations:

j (-α j ) ≤ (1 -α j )P (A j ) -α j P (B j ), (8)
j (1 -β j ) ≥ (1 -β j )P (A j ) -β j P (B j ). (9)
Remark that the two discounted equations are here linear in variables p i and j . The constraints become empty when j = 1 and are then equivalent to state

P (A j |A j ∪ B j ) ∈ [0, 1]
. This means that there always exists a set of coefficients { j } j=1,...,N that makes the problem feasible.

The question is now how to compute the discounting rates j , j = 1, . . . , N such that the constraints induce a non-empty credal set P while minimizing the discounting in some sense. We propose the following approach to find the coefficients j : min N j=1 j under the constraints xi∈X p i = 1, 0 ≤ p i ≤ 1 for all i = 1, . . . , M , 0 ≤ j ≤ 1 for all j = 1, . . . , N , and Constraints ( 8)- [START_REF] Wu | Probability estimates for multi-class classification by pairwise coupling[END_REF]. It is interesting to notice that this new approach is similar to strategies proposed to find minimal sets of infeasible constraints in linear programs [START_REF] Chinneck | Finding a useful subset of constraints for analysis in an infeasible linear program[END_REF].

Credal discounting vs -discounting

In a previous paper [START_REF] Destercke | Combining binary classifiers with imprecise probabilities[END_REF], we proposed a discounting strategy that was applied to directly to bounds α j , β j before transforming Equation ( 2). The obtained discounted equation for the jth classifier is

(1 -j )α j ≤ P (A j |A j ∪ B j ) ≤ j + (1 -j )β j , j = 1, . . . , N.
However, applying such a discounting (or other correction) operation results in quadratic constraints once Equation ( 2) is "deconditioned" and transformed in Constraints ( 8)- [START_REF] Wu | Probability estimates for multi-class classification by pairwise coupling[END_REF]. Discounted constraints on P (B j |A j ∪ B j ) are obtained by complementation. Remark further that for each constraint, all the coefficients of the square terms p 2 i and 2 j are zero. This implies that the associated quadratic form is indefinite. Therefore, computing the minimum-norm vector of coefficients 1 , . . . , N by solving an optimisation problem is very difficult, and searching the space of all solutions is very greedy. To overcome this problem, all the discounting factors were assumed to be equal, and were computed empirically by searching the parameter space (if 1 = • • • = N , a dichotomic search can be performed).

In the present approach, we have N discounting rates to compute. However, they may be determined by solving a linear optimization problem under linear constraints, which may be addressed more efficiently than searching the space of discounting coefficients.

Global vs local discounting

In this work, we advocate a local discounting approach, where each classifier is associated with a specific rate i . In order to illustrate why this approach seems preferable to a global strategy, where all discounting rates are assumed to be equal, we concentrate on the one-vs-one problem (i.e., each classifier was trained to separate a single class from another). Let us now consider the following simple example:

Example 2. Consider X = {x 1 , x 2 , x 3 , x 4 } and the following results:

P (x i |x i , x j ) ∈ [0.6, 1]
for all pair 1 ≤ i < j ≤ 4, except for P (x 1 |x 1 , x 4 ) ∈ [0, 0.4]. Thus, all classifier outputs are consistent with p 1 > p 2 > p 3 > p 4 , except P (x 1 |x 1 , x 4 ) from which one would conclude p 4 > p 1 . Now, if we were to discount all of them in the same way, we would obtain as a minimal discounting ij = 1 /6 (and ij = 1, with ij the discounting value of P (x i |x i , x j )), with p 1 = p 2 = p 3 = p 4 = 1 /4 being the only feasible solution. Thus, in this case, all the information provided by the classifiers is lost, and we are unable to choose between one of the four classes. Now, assume that each classifier is discounted separately from the others; then, taking 14 = 1 /3 restores consistency (e.g., p 1 = 0.5, p 2 = 0.31, p 3 = 0.2, p 4 = 0.09 is a solution) while still preserving the ordering p 1 > p 2 > p 3 > p 4 .

Experiments

In this section, we present some experiments performed on classical and simulated data sets. We considered both decision rules presented in Section 2.4 to make decisions. Since the maximality rule provides a set of possible classes, we need to define a way to evaluate the accuracy of the decision system in this case. Section 4.1 addresses this topic.

Evaluating classifiers performances

Combined classifiers used with a maximin rule can be directly compared to classical classifiers or to more classical combinations, as both return a single class as output. In this case, accuracy is simply measured as a classical accuracy that will be referred to acc in the following. However, one of the main assets of imprecise probabilistic approaches is the (natural) ability to return sets of classes when information is ambiguous or not precise enough to return a single class. In this case, comparing the imprecise classification output with a classical unique decision is not straightforward.

A first (naive) solution consists in considering the classification as fully accurate whenever the actual class of an evaluated data point belongs to the predicted set of possible classes X. It amounts to consider that the final decision is left to the user, who always makes the good choice. The error rate thus computed is an optimistic estimate of the accuracy of the classifier. This estimate will thereafter be referred to as set accuracy, or s -acc.

Another solution is to use a discounted accuracy. Assume we have T observations for which the actual classes x i , i = 1, . . . , T are known, and for which T sets of possible classes X 1 , . . . , X T have been predicted. The discounted accuracy d -acc of the classifier is then

d -acc = 1 T T i=1 ∆ i g(| X i |) ,
with ∆ i = 1 if x i ∈ X i , zero otherwise and g an increasing function such that g(1) = 1. Although g(x) = x is a usual choice for the discounted accuracy, it has recently been shown [START_REF] Zaffalon | Utility-based accuracy measures to empirically evaluate credal classifiers[END_REF] that this choice leads to consider imprecise classification as being equivalent to make a random choice inside the set of optimal classes. This comes down to consider that a Decision Maker is risk neutral, i.e., does not consider that having imprecise classification in case of ambiguity is an advantage. This also implies that the robustness of an imprecise classification is rewarded by concave (or risk-averse) functions g.

In our case, we used the function g(•) = log M (•) that satisfies g(1) = 1 and takes account of the number of classes. Indeed, in the case of two classes, we should have g(2) = 2, because predicting two-classes out of two is not informative. However, as M increases, predicting a small number of classes becomes more and more interesting. This is why we pick log M . We used various UCI data sets that are briefly presented in Table 1. For each of these datasets, we considered the classical one-vs-one decomposition scheme, in which each classifier is trained to separate one class from another. We used as base classifiers CART decision trees (so that comparisons between the precise and the imprecise approaches can be done) and the imprecise Dirichlet model [START_REF] Bernard | An introduction to the imprecise dirichlet model[END_REF] to derive lower and upper conditional probability bounds. This model depends on a hyper-parameter s that settles how quickly the probability converges to a precise value. More precisely, if a j , b j are the two classes for the jth binary classifier, and if n aj , n bj are the number of training data having respectively a j and b j for classes in the leaf of the decision tree reached by the instance, then the bounds are

Datasets and experimental setup

α j = n aj n j + s , β j = n aj + s n j + s ,
where n j = n aj + n bj . Then, s can be interpreted as the number of "unseen" observations, and α j = β j if s = 0. Table 2 summarises the results obtained for s = 4. We compared our method to a single CART decision tree (DT) and to Naive Bayes classifiers (NB). We also displayed the accuracy obtained with maximin rule as well as the set accuracy and the discounted accuracy obtained with the maximality rule, both for the global and local correction methods. We used a 10-fold cross validation. The significance of the differences between the results was evaluated using a Wilcoxon-signed rank test at level 95%. The best results (outside set accuracy) are underlined and results that are not significantly different are printed in bold. Note that we excluded s-acc since it is strongly biased in favor of imprecise decisions. Two main remarks can be made. First, the one-versus-one decomposition strategy provides good results for most data sets, as it gives better results on 6 data sets out of 9. Second, it is clear that the local discounting strategy gives significantly better results than the global discounting strategy. The local strategy dominates the global one on most data sets and gives results very close to the global one otherwise (here, for the "waveform" and "anneal" datasets).

Let us remark that the parameter s, which is directly proportional to the amount of imprecision, has remained the same for all data sets. However, the resulting imprecision also depends on the data. This partly explains the differences between the set accuracy and the discounted accuracy obtained on the datasets: for instance, the resulting imprecision is moderate for "glass" and "yeast", but zero for "anneal" and "primary tumor").

In order to provide an idea of the impact of increasing the overall degree of imprecision, Figure 1 shows the evolution of the discounted accuracy as a function of log 2 (s) (let us remind that since g(| X i |) = log M (| X i |), the classifier reaches a score of 0.5 when it retains all the classes for all the instances). It shows that moderately increasing the imprecision can give better results (the maximum is reached for s = 8) and that the discounted accuracy starts to decrease once the degree of imprecision becomes too large. Similar behaviors could be observed for other data sets.

Conclusions

We addressed the problem of pattern classification using binary classifier combination. We adopted imprecise probability theory as a framework for representing the imprecise outputs of the classifiers. More particularly, we consider classifiers that provide sets of conditional probability distributions. It encompasses both cases of precise and imprecise probabilistic outputs (including possibilistic, evidential [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempster-shafer theory[END_REF] and credal classifiers [START_REF] Zaffalon | The naive credal classifier[END_REF]). The combination of such classifiers is done by considering classifier outputs as constraints. We presented a local discounting approach for relaxing some of these constraints when the classifiers provide inconsistent outputs. Our strategy computes the discounting rates by solving linear optimization problems, which can be efficiently solved by standard techniques. Experiments demonstrate that our method give good results compared to the single classifier approach. Moreover, it performs almost always better than the global discounting approach that was presented in a former paper. In future works, we wish to extend our experimentation (by using precise classifiers and genuine imprecise classifiers) and to make a deeper analysis of their results (e.g., checking in which cases inconsistencies happen, verifying that imprecise classification correspond to instances that are hard to classify). We also wish to investigate on the properties of our approach from the point of view of decision making under uncertainty.

Fig. 1 .

 1 Fig. 1. Evolution of d -acc for data set glass

Table 1 .

 1 UCI data sets used in experiments

	Data set	#classes	#input	#samples
	name	M	features
	glass	6	9	214
	satimage	6	36	6435
	segment	7	19	2310
	vowel	11	10	990
	waveform	3	8	5000
	yeast	10	8	1484
	zoo	7	18	101
	primary tumor	21	17	339
	anneal	5	38	898

Table 2 .

 2 UCI data sets used in experiments

	Data set	NB	DT		local			global
				acc	s-acc	d-acc	acc	s-acc	d-acc
	glass	70.55	71.00	74.77	79.59	74.29	73.73	78.55	73.79
	satimage	84.34	80.06	87.27	90.43	88.16	86.37	89.15	87.78
	segment	96.19	85.88	95.58	97.36	96.63	96.37	96.88	96.50
	vowel	78.88	72.10	80.32	82.84	81.32	77.58	77.88	77.27
	waveform	71.10	80.94	73.24	81.70	75.11	73.44	81.86	75.28
	yeast	48.84	45.33	57.13	68.32	61.94	55.11	62.39	59.19
	zoo	95.17	90.17	96.17	96.17	94.59	96.17	96.17	94.59
	p. tumor	38.05	48.38	45.75	45.75	45.75	42.22	42.22	42.22
	anneal	95.99	93.10	81.74	81.74	81.74	81.86	81.86	81.86

From now on, we will drop the y in the conditional statements, as the combination always concerns a unique instance which input features remain the same.


Yosra Mazigh

NAIVE EVIDENTIAL CLASSIFIER (NEC): APPLICATION TO SEMOLINA MILLING VALUE

des systèmes complexes

We introduce the notion of naive evidential classifier. This classifier, which has a structure mirroring the naive Bayes classifier, is based on the Transferable Belief Model and use mass assignments as its uncertainty model. This new method is based achieves more robust inferences, mainly by explicitly modeling imprecision when data are in little amount or are imprecise. After introducing the model and its inference process based on Smet's generalized Bayes theorem (GBT), we specify some possible methods to learn its parameters, based on the Imprecise Dirichlet Model (IDM) or on predictive belief functions. Some experimental results on an agronomic application are then given and evaluated.

Introduction

When modeling and processing uncertainty, computing on multivariate spaces is an important issue. If X 1 , . . . , X N is a set of variables assuming their values over some finite spaces X 1 , . . . , X N , defining directly a joint uncertainty model over the Cartesian product X 1 × . . . × X N and making some inferences with this model is often impossible in practice. The use of graphical models based on network architecture can solve this problem by decomposing the joint uncertainty model into several pieces of conditional models. This decomposition is possible thanks to conditional independence property. Note that outside their computational tractability, another attractive feature of such models is their readability for non-experts, thanks to their graphical aspects.

The aim of this paper is first to introduce the notion of the Naive Ev-idential Classifier (NEC) as the counterpart of the Naive Bayes (NB) in evidential theory. It uses the directed evidential network structure (DEVN) proposed by Ben Yaghlane in 1 and preforms inference by using the modified binary join tree (MBJT) algorithm, which uses the disjunctive rule of combination (DRC) and the generalized Bayesian theorem (GBT), both proposed by Smets in. [START_REF] Smets | Belief Functions: the Disjunctive Rule of Combination and the Generalized Bayesian Theorem[END_REF] In Section 2, we briefly present the Basics of NEC. Section 3 then provides some details about the practical instanciation and use of the NEC structure. Finally, Section 4 presents some preliminary experiments on an agronomical problem. Due to lack of spaces, only the essential elements are provided, and the reader is referred to references for details.

Naive Evidential Classifier (NEC)

NEC the TBM counterpart of the Naive Bayes (NB) classifier. Thereby, it is a graphical model having two parts: a qualitative and a quantitative one. Recall that the aim of a classifier is learn a mapping from input values X 1 , . . . , X N ∈ X 1 × . . . × X N to an output class C ∈ C from available (training) data, in order to predict the classes of new instances.

Graphical structure

NEC maintain the same graphical presentation as NB. In the figure 1, the root C is class to predict and the leafs from X 1 to X n present features. to each node will be associated a prior mass as follows:

• A prior mass distribution m(C) in the root (class) node.

• Both a prior mass distribution m(X) and a conditional mass distribution m X [C](x i ) in each leaf node associated to an edge.

Section 3 explains how these masses can be learnt. The propagation of beliefs for NEC, ensured by a Modified Binary Joint Tree Structure, is illustrated in Figure 2 for nodes C and X 2 . We refer to 1 for details. Mass distributions in the model can be elicited from experts or constructed from observed data (the usual case in classification). We propose two methods to infer such distributions: the Imprecise Dirichlet model (IDM) 2 and Denoeux's multinomial model, [START_REF] Denoeux | Constructing belief functions from sample data using multinomial confidence regions[END_REF] obtaining respectively the NEC1 and NEC2 paremeterization.

The imprecision of mass distributions obtained by each methods is governed by hyperparameters, respectively the positive real number s ∈ R + for the IDM and the confidence level α ∈ [0, 1] for Denoeux's model. The higher these parameters, the higher the imprecision of mass distributions.

Classification and evaluation

As imprecision is an interesting feature of evidence theory, we propose an imprecise classification based on pairwise comparisons. [START_REF] Destercke | A Decision Rule for Imprecise Probabilities Based on Pair-Wise Comparison of Expectation Bounds[END_REF] Using the mass on C obtained for an instance x 1 , . . . , x N by propagation on the NEC, a class c 1 is told to dominate c 2 , denoted by c 1 c 2 if the belief of c 1 is larger than the belief of c 2 (bel(c 1 ) ≥ bel(c 2 )) and the plausibility of c 1 is larger than the plausibility of c 2 (pl(c 1 ) ≥ pl(c 2 )) for all the distributions. The retained set Ω m of possible classes is then the one of non-dominated classes, i.e. Ω m = {c ∈ C| ∃c , c c}. Evaluations are then made through the use of set accuracy and of discounted accuracy (see [START_REF] Corani | Jncc2: The java implementation of naive credal classifier 2[END_REF] ). Roughly speaking, if ĉ is the true class, set-accuracy counts 1 each time ĉ ∈ Ω m , while the discounted accuracy counts 1 /|Ωm| with |Ω m | the cardinality of Ω. Both counts 0 when ĉ ∈ Ω m , and classical accuracy is recovered when |Ω m | = 1

Experiments On Durum Wheat

In this section we present preliminary results on an agronomic application of NEC consisting in the prediction of the semolina milling value of the durum wheat. Being able to predict this value from easy to measure parameters would be very valuable both for farmers and industrials, the former because it would help in grain selection, the latter to quickly assess wheat quality.

The database contains 256 samples issued from IATE experimental mill, where the output class was the semolina value (discretized in four classes specified by experts) and the input parameters were the Hectolitre Weight (HLW), The Thousand Kernel Weight(TKW) and Vitreousness. NEC1 and NEC2 are both evaluated according to set and discounted accuracy measures, and a ten-fold cross validation method was used.

Figures 3 and4 show the variations of set-and discounted-accuracy as a function of the parameters v (IDM) and α (Denoeux's model). A Fig. 3. Discounted Accuracy as a Function of v and α first remark is that NEC1 tends to have worse performances than NEC2, an observation that can be explained by the fact that the IDM is more "simple" than Denoeux's model. Hence NEC 1 is easier to compute, while NEC2 gives better predictions. Another noticeable fact is that set-accuracy does not necessarily decrease as the model gets more imprecise (Figure 4 left). This is due to the non-motonicity of the used decision rule (i.e., a more imprecise m does not mean a bigger Ω m ), and this could be solved by choosing another (more imprecise) rule such as interval-dominance. [START_REF] Destercke | A Decision Rule for Imprecise Probabilities Based on Pair-Wise Comparison of Expectation Bounds[END_REF] Figure 5 displays the confusion matrix for both classifiers (where the precise classification was chosen as the most plausible, i.e., c = arg max c∈C pl({c})). Again, both classifiers appear to be at odds, and it is difficult to say which is better. However, as is supported by the relatively low level of well-classed items, this difficulty to differentiate probably also comes from the poor explanatory power of input variables, and more refined modelling (planned in the future) as well as tests on other data sets would be needed to make further conclusions.

Finally, to choose the best configuration, we propose to retain the best one according to discounted accuracy (as it reflects balance between imprecision and prediction quality), that is to say the NEC1 classifier with v = 53.

Conclusion

In this paper, we have introduced the idea of Naive Evidential Classifier as well as tools to instantiate and evaluate it. A preliminary application has been achieved on an agronomical problem. Considering the quality of available data, first results are encouraging, however much work remains to be done:

• concerning the model itself, it would be desirable to realx the independence assumption anduse an augmented tree model; • concerning the application, a refined statistical analysis of the data may allow to extract more relevant information or identify subgroups of interest (e.g., differentiating big and small grains or varieties of wheat); • concerning the general evaluation of the model, it remains to apply it to usual benchmarks and to confront it to other classical classifiers.

Fig. 1 .

 1 Fig. 1. A generalized presentation of the naive evidential classifier NEC

Fig. 2 .

 2 Fig. 2. The propagation process in the MBJT using the GBT and the DRC

Fig. 4 .

 4 Fig. 4. Set Accuracy as a Function of v and α

Fig. 5 .

 5 Fig. 5. Confusion Matrix: (a)given by NEC1 with v = 53; and (b)given by NEC2 with α = 0.0000001


Sébastien Destercke

Violaine Antoine

Combining Imprecise Probability Masses with Maximal Coherent Subsets: Application to Ensemble Classification

published or not. The documents may come

Introduction

When multiple sources provide information about the ill-known value of some variable X it is necessary to aggregate these pieces of information into a single model. In the case where the initial uncertainty models are precise probabilities and where the aggregated model is constrained to be precise as well, there are only a few options to combine the information (see [START_REF] Cooke | Experts in uncertainty[END_REF] for a complete review)

The situation changes when one considers imprecision-tolerant uncertainty theories, such as possibility theory, evidence theory or imprecise probability theory (see [START_REF] Dubois | Decision-making Process: Concepts and Methods, chapter Formal representations of uncertainty[END_REF]). As they extend both set-theoretic and probabilistic approaches 1 , these theories can use aggregation operators coming from both frameworks, i.e., they can generalise intersections and unions of sets as well as averaging methods.

Sébastien Destercke UMR Heudiasyc, Université de Technologie de Compiègne, 60200 Compiègne, France e-mail: sebastien.destercke@hds.utc.fr Violaine Antoine LISTIC, Polytech Annecy-Chambéry, 74944 Annecy le Vieux, France e-mail: violaine.antoine@univ-savoie.fr 1 Except possibility theory, that does not encompass probabilities as special cases.

When there is (strong) conflict between information pieces, both conjunctive (intersection) and disjunctive (union) aggregation face some problems: conjunction results are often empty and disjunction results are often too imprecise to be really useful. A theoretically attractive solution to these problems is to use maximal coherent subsets (MCS) [START_REF] Rescher | On inference from inconsistent premises[END_REF], that is to consider subsets of sources who are consistent and that are maximal with this property. Aggregation can then be done by combining conjunction within maximal coherent subsets with other aggregation operators, e.g., disjunction. Practically, the main difficulty that faces this approach is to identify MCS, a NP-hard problem in the general case.

Different solutions have been proposed to combine inconsistent pieces of information within the framework of imprecise probability theory. In [START_REF] Nau | The aggregation of imprecise probabilities[END_REF] and [START_REF] Troffaes | Generalising the conjunction rule for aggregating conflicting expert opinions[END_REF], hierarchical models are considered. In [START_REF] Benavoli | An aggregation framework based on coherent lower previsions: Application to zadeh's paradox and sensor networks[END_REF] and [START_REF] Karlsson | On the behavior of the robust bayesian combination operator and the significance of discounting[END_REF], Bayesian-like methods (i.e., using conditional probabilities) of aggregation are proposed. In [START_REF] Moral | Aggregation of imprecise probabilities[END_REF] and [START_REF] Walley | The elicitation and aggregation of beliefs[END_REF], non-Bayesian methods are studied (although [START_REF] Walley | The elicitation and aggregation of beliefs[END_REF] considers that combination methods should commute with Bayesian updating). In the two latter references, MCS are proposed as a solution to combine information pieces that are partially inconsistent, but no practical methods are given to identify MCS.

In this paper, we concentrate on imprecise probability masses and propose a practical approach to apply MCS inspired combination methods to such models. We work in a non-Bayesian framework. Section 2 recalls the necessary background on imprecise probabilities and information fusion. Section 3 describes our approach, of which the most important part is the algorithm to identify MCS. Finally, Section 4 presents an application to ensemble classification, in which resulting classification models are combined using MCS.

Preliminaries

The theory of imprecise probabilities [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF] is a highly expressive framework to represent uncertainty. This section presents the basics of imprecise probabilities.

Imprecise probabilities

Consider a variable X taking values in a finite domaine D x of n elements {x 1 , x 2 , . . . , x n }. Basically, imprecise probabilities characterize uncertainty about X by a closed convex set P of probabilities defined on D x . To this set P can be associated Lower and upper probabilities that are mappings from the power set 2 Dx to [0, 1]. They are respectively denoted P and P and are defined, for an event A ⊆ D x , as P (A) = inf p∈P P (A) and P (A) = sup p∈P P (A). These two measures are dual, in the sense that P (A) = 1 -P (A c ), with A c the complement of A. Hence, all the information is contained in only one of them.

Alternatively, one can start from a lower measure P and compute the convex set P P = {P ∈ P(D x )|P (A) ≥ P (A), ∀A ⊆ D x } of dominating probability measures (P(D x ) is the set of all probabilities on D x ). Note that the lower value P * (A) = inf P ∈P P P (A) need not coincide with P (A) in general. If the equality P * = P holds, then P is said to be coherent. In this paper, we will deal exclusively with coherent lower probabilities. Note that lower probabilities are not sufficient to represent every possible convex sets of probabilities.To represent any convex set P, one actually needs to consider bounds on expectations (see [START_REF] Walley | Statistical reasoning with imprecise Probabilities[END_REF]).

Imprecise probability masses (IPM)

Usually, the handling of generic sets P (and sets represented by lower probabilities) represent a heavy computational burden. In practice using simpler models alleviate this computational burden to the cost of a lower expressivity. Imprecise probability masses [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF] (IPM) are such simpler models.

IPM can be represented as a family of intervals

L = {[l i , u i ], i = 1, . . . , n} veri- fying 0 ≤ l i ≤ u i ≤ 1∀i.
The interval bounds are interpreted as probability bounds over singletons. They induce a set

P L = {p ∈ P(D x )|l i ≥ p(x i ) ≥ u i , ∀x i ∈ D x }.
An extensive study of IPM and their properties can be found in [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF].

A set L of IPM is said to be proper if the condition n i=1 l i ≥ 1 ≥ n i=1 u i holds, and P L = ∅ if and only if L is proper. Considered sets are always proper, other types having no interest. To guarantee that lower and upper bounds are reachable for each singleton x i by at least one probability in P L , the intervals must verify:

i =j l j + u i ≤ 1 and i =j u j + l i ≥ 1 ∀i. (1)
If L is reachable, lower and upper probabilities of P L can be computed as follows:

P (A) = max( xi∈A l i , 1 - xi / ∈A u i ), P (A) = min( xi∈A u i , 1 - xi / ∈A l i ). ( 2
)
If L is not reachable, a reachable set L is obtained by applying Eq. (2) to singletons.

Basic combinations of imprecise probabilities

When M sources provide information, there are three basic ways to combine this information: through a conjunction, a disjunction or a weighted mean. When information is given by credal sets P i , i = 1, . . . , M , computing these basic combination results present some computational difficulties [START_REF] Moral | Aggregation of imprecise probabilities[END_REF]. Computations become much easier if we consider a set L 1 , . . . , L M of IPM. In this case, if l i,j , u i,j denote respectively the lower and upper probability bounds on element x i given by source j, (approximated) combinations are as follows:

• Weighted mean (L ): l i, = j=1,M w j l i,j , u i, = j=1,M w j u i,j • Disjunction (L ∪ ): l i,∪ = min j=1,M l i,j , u i,∪ = max j=1,M u i,j • Conjunction (L ∩ ): l i,∩ = max( max j=1,M l i,j , 1 - k =i min j=1,M u i,j ), (3)
u i,∩ = min( min j=1,M u i,j , 1 - k =i max i=1,M l i,j )
In general, the bounds obtained by conjunction (3) may be non-proper, i.e. may result in an empty P L∩ . L 1 , . . . , L M have a non-empty intersection iff the following conditions [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF] hold:

max j=1,M l i,j ≤ min j=1,M u i,j for every i ∈ [1, n] (4) i=1,n max j=1,M l i,j ≤ 1 ≤ i=1,n min j=1,M u i,j (5)
The first condition ensures that intervals have a non-empty intersection for every singleton, while the second makes sure that the result is a proper probability interval.

Maximal coherent subsets (MCS) and IPM

This section describes the methods to identify and combine MCS.

(I1 ∩ I2) (I2 ∩ I3 ∩ I4)
Fig. 1 Maximal coherent subsets on Intervals

When sources provide sets P 1 , . . . , P M , finding MCS comes down to find every subset K ⊆ [1, M ] such that i∈K P i = ∅ and such that K is maximum with this property (i.e., adding a new set would make the intersection empty). Usually, identifying every possible coherent subset among P 1 , . . . , P M is NP-hard, making it a difficult problem to solve in practice.

A particularly interesting case where MCS can be found easily is when each sources provide intervals [a i , b i ], i = 1, . . . , M . In this case, Algorithm 1 given in [START_REF] Dubois | Multi-source information fusion: a way to cope with incoherences[END_REF] finds MCS. It requires to sort values {a i , b i |i = 1, . . . , M } (complexity in O(M log M )), and is then linear in the number of sources.

Algorithm 1: Maximal coherent subsets of intervals

Input: M intervals Output: List of S maximal coherent subsets K j 1 List = ∅, j=1, K = ∅ ; 2 Order in an increasing order This algorithm can be applied directly to IPM intervals to check MCS satisfying Condition (4) (which is necessary for a subset of IPM to have a non-empty intersection). Indeed, consider a singleton x i and the set of intervals

{a i |i = 1, . . . , M } ∪ {b i |i = 1, . . . , M } ; 3 Rename them {c i |i = 1, . . . , 2M } with type(i) = a if c i = a k and type(i) = b if c i = b k ; 4 for i = 1, . . . , 2M -1 do 5 if type(i) = a then 6 Add Source k to K s.t. c i = a k ; 7 if type(i + 1) = b then 8 Add K to List (K j = K) ; 9 j = j + 1 ; 10 else 11 Remove Source k from K s.t. c i = b k ; Source1 x 1 x 2 x 3 u i,1 0.6 0.5 0.2 l i,1 0.4 0.3 0. Source2 x 1 x 2 x 3 u i,
L i = [l i,j , u i,j ], j = 1, M : if K ⊆ [1, M ] is not a MCS of L i ,
then the credal sets {P j |j ∈ K} do not form a MCS. Hence, iteratively applying Algorithm 1 as exposed in Algorithm 2 allows to easily identify possible MCS among sets P L1 , . . . , P L M . In each iteration (Line 2), Algorithm 2 refines the MCS found in the previous one (stored in List) by finding MCS for probaiblity intervals of singleton x i (Line 5).

Algorithm 2: MCS identification for IPM

Input: M IPM Output: List of S possible maximal coherent subsets K j 1 List = {{1, M }} ; 2 for i = 1, . . . , n do 3 K=∅; 4 foreach subset E in List do 5 Run Algorithm 1 on [l i,j , u i,j ], j ∈ E ; 6 Add resulting list of MCS to K; 7 List= K;
Example 1. Consider the IPM defined on D x = {x 1 , x 2 , x 3 } and summarised in Table 1. Running Algorithm 2 then provides successively the following MCS: K = {{1, 2, 3}, {2, 3, 4}} after the first iteration (i = 1 in Line 2 of Algorihm 2); K = {{1, 2}, {3}, {2, 4}} after the second iteration, and K is not changed during the third iteration. Some subsets K 1 , . . . , K S of sources resulting from Algorithm 2 do not satisfy Condition [START_REF] Destercke | The role of generalised p-boxes in imprecise probability models[END_REF]. If K is such a set, then one can either make an (exponential) exhaustive search of MCS within K , or correct IPM in K in a minimal way, so that they satisfy [START_REF] Destercke | The role of generalised p-boxes in imprecise probability models[END_REF]. In this last case we can transform [START_REF] Moral | Aggregation of imprecise probabilities[END_REF] bounds l i,j and u i,j , j ∈ K , i ∈ [1, n] into l i,j = l i,j and u i,j = u i,j + (1 -) with the minimal value such that

i=1,n max j∈K l i,j ≤ 1 ≤ i=1,n min j∈K u i,j . (6)
This strategy makes the identification of MCS easy. Roughly speaking, it applies Algorithm 1 to probabilistic (expectation) bounds coming from sources but bearing on common events (functions). Note that the same strategy can be applied to models based on peculiar families of events (functions), such as p-boxes [START_REF] Destercke | The role of generalised p-boxes in imprecise probability models[END_REF].

Combination with MCS

Once MCS K 1 , . . . , K S of sources have been identified, they can be used to combine inconsistent information. Without loss of generality, consider the indexing such that |K 1 | ≥ . . . ≥ |K S | where |K i | is the cardinality of K i (i.e., the number of sources within it).

We then propose two ways of combining the probability sets P L1 , . . . , P L M . In both of them, we consider the IPM L K , = 1, . . . , S obtained by combining IPM in K according to the conjunctive rule [START_REF] Cooke | Experts in uncertainty[END_REF].

The first rule combines disjunctively the first n IPM L Ki , that is

l i,∪∩n = min =1,n l i,K , u i,∪∩n = max =1,n u i,K (7)
where l i,K , u i,K are the probability bounds given by L K on x i . The second rule combines by a weighted mean the first n, L Ki , that is

l i,∪∩n = =1,n w ,n l i,K , u i,∪∩n = =1,n w ,n u i,K (8)
where w ,n = |K | / i=1,n |Ki| is the importance of K in number of sources (a similar strategy is used in [START_REF] Moral | Aggregation of imprecise probabilities[END_REF]). If n = S the rules simply combine every MCS.

Application to ensemble classification

Combination is an essential feature of ensemble classification. As classifiers often disagree together, using a MCS based approach to combine the different sources appears sensible. We have therefore tested our approach in the following way: we have trained forest of decision trees; for a given instance and for each decision trees, we have built an IPM model using the Imprecise Dirichlet model (IDM) with an hyperparameter s = 4 (see [START_REF] Bernard | An introduction to the imprecise dirichlet model for multinomial data[END_REF] for details) and taking the samples in the tree leaves as observations. We then combined the different IPM with the two rules ( 7) and ( 8) (n=5) and selected the final class according to the maximin and maximality criterion (see [START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF] for details). The former results in a unique decision while the latter results in a set of possible optimal decisions. Classifier performances are estimated using discounted accuracy: assume we have T observations whose classes x i , i = 1, . . . , T are known and for which T (possibly imprecise) predictions X 1 , . . . , X T have been made. The discounted accuracy d -acc of the classifier is then

d -acc = 1 T T i=1 ∆ i f (| X i |) , (9)
with ∆ i = 1 if x i ∈ X i , zero otherwise and f an increasing function such that

f (1) = 1. Set accuracy (s -acc) is obtained with f (| X i |) = 1.
Results are summarized in Table 2. Numbers of trees in the forest are {10, 20, 50} and the data sets are Zoo, Segment and Satimage (taken from UCI), all of them with 7 classes. Results were compared to a classical voting strategy. We have also indicated the average CPU time needed to apply the different combination rules. From the results, it appears that using a conjunctive rule between provided imprecise probabilistic models does not improve much the results of classical voting. This is not surprising as we use precise decision trees and IDM to build our models, and it would be worthwhile to check whether these conclusions still hold when using credal classifiers. The interest of using imprecise probabilistic models appears when we allow for some imprecision, that is when we adopt a partially disjunctive rule (Rule (7) with n=5). In this latter case, allowing for imprecise classification increases the percentage of well-recognized instances while not decreasing too much the precision. Finally, we can notice that the average computational time does not increase much when the number of sources increases.

Conclusion

In this paper, we have proposed an efficient way to find MCS with imprecise probability masses, and have applied it to the combination of multiple classifiers. First results indicate that using a disjunctive approach to combine conjunctively merged MCS may quickly result in poorly informative models, hence it may be safer in general to adopt other strategies (e.g., combining only a limited number of MCS or using a weighted mean). Note that the algorithms presented here can be applied to other imprecise probabilistic models as well, as long as they are defined by probability bounds bearing on the same events (or by expectation bounds bearing on the same function).

Table 1

 1 Examples of IPM

		Source3	Source4
		x 1 x 2 x 3	x 1 x 2 x 3
	2 0.55 0.55 0.2	u i,3 0.5 0.2 0.6	u i,4 0.35 0.6 0.35
	l i,2 0.35 0.35 0.	l i,3 0.3 0. 0.4	l i,4 0.15 0.4 0.15

Table 2

 2 Results summary. d-acc: discounted accuracy, s-acc: set accuracy, acc: standard accuracy (with maximin)

	data Tree Single Votes	Rule (7) (n=1)	Rule (7) (n=5)	Rule (8) (n=5) avg CPU
	set nb tree	d-acc s-acc acc	d-acc s-acc acc	d-acc s-acc acc	time
	Sat 10 0.81 0.88	0.87 0.88 0.87	0.64 0.98 0.81	0.87 0.89 0.87	15.16
	20 0.81 0.89	0.88 0.89 0.88	0.61 0.98 0.82	0.88 0.90 0.88	23.80
	50 0.81 0.89	0.89 0.90 0.89	0.63 0.97 0.85	0.89 0.90 0.89	61.28
	Zoo 10 0.91 0.92	0.86 0.86 0.86	0.69 0.96 0.80	0.88 0.92 0.92	0.28
	20 0.91 0.93	0.79 0.79 0.79	0.60 0.99 0.68	0.85 0.91 0.88	0.50
	50 0.91 0.93	0.90 0.92 0.91	0.69 0.96 0.87	0.86 0.88 0.88	2.34
	Seg 10 0.93 0.96	0.96 0.96 0.96	0.72 1.00 0.84	0.95 0.97 0.96	5.59
	20 0.93 0.95	0.95 0.95 0.95	0.66 0.99 0.81	0.95 0.96 0.95	8.03
	50 0.93 0.96	0.96 0.96 0.96	0.64 0.98 0.84	0.96 0.96 0.96	17.64