Yang Gen

Destercke Sébastien

Marie-Hélène Masson

Nested Dichotomies with probability sets for multi-class classification

Binary decomposition techniques transform a multi-class problem into several simpler binary problems. In such techniques, a classical issue is to ensure the consistency between the binary assessments of conditional probabilities. Nested dichotomies, which consider tree-shaped decomposition, do not suffer from this issue. Yet, a wrong probability estimate in the tree can strongly biase the results and provide wrong predictions. To overcome this issue, we consider in this paper imprecise nested dichotomies, in which binary probabilities become imprecise. We show in experiments that the approach has many advantages: it provides cautious inferences when only little information is available, and allows to make efficient computations with imprecise probabilities even when considering generic cost functions.

Introduction

The usual goal of machine learning algorithms is to learn, from a set of data, a model that will provide accurate predictions on new data. Most current techniques focus on achieving a better rate of accuracy while preserving the determinacy of predictions, even if they are based on few information. However, in some applications of machine learning (e.g. medical diagnosis, image recognition for intelligent vehicles, risk analysis), the reliability of predictions is as essential as their accuracy. In such cases, providing indeterminate but more reliable predictions makes sense. For example, in the problem of obstacle recognition for vehicles, it is preferable to state "I do not know" rather than predicting "no obstacles" if the available information is not sufficient to reliably say that there is an obstacle.

There are two main approaches to make indeterminate predictions in a classification problem: integrating costs of indeterminacy in the decision making [START_REF] Del Coz | Learning nondeterministic classifiers[END_REF] and considering imprecise probabilities as estimates rather than precise probabilities [START_REF] Corani | Compression-based aode classifiers[END_REF]. The former approach, close in spirit to rejection methods [START_REF] Bartlett | Classification with a reject option using a hinge loss[END_REF], does not really allow to differentiate between rejection due to ambiguity (almost uniform probability estimated from lots of data) and rejection due to lack of information (probability issued from little and/or imprecise data). It also tends to mix costs of errors (e.g., of predicting no obstacle when there is a pedestrian) with costs of being indeterminate (e.g., costs of partial predictions). On the other hand, the latter approach based on imprecise probabilistic estimates [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF] perfectly makes the difference between indeterminacy due to ambiguity and lack of information (the less data we have, the larger the estimated probability set) and uses costs only to model error costs. However, integrating costs of errors in such methods is computationally challenging, which is an important drawback, since applications where indeterminacy and reliability are important will typically include such costs.

In this paper, we propose a classification method relying on imprecise probabilities and extending the notion of nested dichotomies [START_REF] Fox | Applied Regression Analysis, Linear Models, and Related Methods[END_REF] (a particular binary decomposition) to such models. This method has the advantage that it can make indeterminate classification, while having a computational burden similar to its precise counterpart, even when non-trivial costs are considered in the decision making.

We first introduce some basic notions of multi-class classification and establish some notations in Section 2. We then present the "nested dichotomies" technique in Section 3, before detailing in Section 4 how imprecise probabilities can be integrated in the method to provide indeterminate (set-valued) predictions. Finally, experiments provided in Section 5 show that using our approach provide cautious but informative predictions, in the sense that we add indeterminacy mainly when determinate predictions are unreliable.

Context and definitions

Notations

We consider the multi-class classification problem, where we want to learn the conditional probability function px [1;n] . For simplification purpose, we will drop the subscript x and will denote px(y) by p(y) when there is no risk of confusion.

(•) : Y → [0, 1] of the class y ∈ Y (Y = {ω1, . . . , ω k }) given m input features x ∈ X = X 1 × . . . × X m . p is usually learnt from a set of data D = (xi, yi) i∈
For each class y ∈ Y , we assume that a cost function cy : Y → R is defined, where cy(y ′ ) is the cost of predicting y when y ′ is the true class. The expected cost EY (cy) of predicting/selecting y is then defined as follow:

EY (cy) = y ′ ∈Y p(y ′ )cy(y ′ )
A common cost for y is the unitary cost such that cy(y ′ ) = 1 if y ′ = y and 0 otherwise. It is related to the indicator function Iy (Iy(y ′ ) = 1 if y = y ′ , 0 otherwise) through the equality cy = -Iy + 1. By using this, we have EY (Iy) = p(y) = -EY (cy) + 1.

Making prediction can also be seen as establishing a preference order ≻ over the classes to find the most preferred one. This order is derived from the expected cost such that y ≻ z (read "y is preferred to z") if the expected cost of choosing y is less than the one of z :

y ≻ z ⇔ EY (cy) < EY (cz) (1)
Since EY is linear, y ≻ z is also equivalent to :

y ≻ z ⇔ EY (cz -cy) > 0. (2)
Eq. ( 2) can be interpreted as follows: y is preferred to z when exchanging y for z is costly (i.e., has a positive expected cost). We could note that, if cy, cz are unitary, this is equivalent to compare the probability values p(y), p(z) (y ≻ z if p(y) > p(z)). The selected class is therefore the maximal element of the ordering ≻, i.e., arg maxy∈Y EY (cy). This is this view (constructing an order ≻) that we will extend when using probability sets.

Example 1 The interest of cost functions is to model the costs of making a wrong decision (i.e., making a prediction different from the truth). For example, consider the problem of obstacle recognition where a vehicle needs to recognize in situation x whether it faces a pedestrian (p), a bicycle (b) or nothing (n) (i.e. Y = {p, b, n}).

As both pedestrian and bicycle are obstacles to be avoided, a confusion between p and b is not very important. Predicting p or b when there is nothing becomes more costly (the vehicle makes a manoeuvre which is not necessary). Finally, predicting n when there is an obstacle p or b is a big mistake that could cause an accident. This kind of information can easily be expressed using non unitary cost functions. The following table provides an example of 3 cost functions modelling these information, as well as an example of their difference :

truth cy(y ′ ) y ′ = p y ′ = b y ′ = n cp 0 1 2 c b 1 0 2 cn 4 4 0 cp -cn -4 -3 2 c b -cn -3 -4 2 c b -cp 1 -1 0
With these cost functions, we have translated the fact that a confusion between a pedestrian and a bicycle has little effect, whereas a confusion with the absence of obstacle is penalizing.

Binary decomposition

Binary decomposition techniques [START_REF] Dietterich | Solving multiclass learning problems via error-correcting output codes[END_REF] have proved to be good approaches to solve the multi-class problem (for a review of methods, see [START_REF] Aly | Survey on multiclass classification methods[END_REF]). Such techniques propose to decompose the original (difficult) multi-class problem into a set of simpler and easier-to-solve binary problems. Binary decomposition consists in forming ℓ pairs of events {Ai, Bi} (i ∈ [1, ℓ]) where Ai ∩ Bi = ∅ and Ai, Bi ⊆ Y and to estimate whether a class y belong to Ai or Bi for all i = 1, . . . , l instead of directly estimating the joint p(y) for each y ∈ Y . Therefore, for each pair we must solve a binary classification problem and estimate p(Ai | {Ai, Bi}) = αi and p(Bi | {Ai, Bi}) = 1αi, using what is usually called the base classifier. From these conditional estimates can be derived the following constraints on the joint probability:

     y∈A i p(y) = αi y∈A i ∪B i p(y) (i = 1, . . . , l) y∈Y p(y) = 1 (3)
A frequent problem with such a general set of estimated conditional probabilities is that the constraints (3) are most of the time inconsistent [START_REF] Hastie | Classification by pairwise coupling[END_REF][START_REF] Wu | Probability estimates for multi-class classification by pairwise coupling[END_REF][START_REF] Destercke | Combining binary classifiers with imprecise probabilities[END_REF], in the sense that no feasible solution will exist. How to solve this inconsistency is not an obvious problem and there is no unique best solution, even when one allows probabilities to become imprecise [START_REF] Destercke | Combining binary classifiers with imprecise probabilities[END_REF]. A usual strategy is to find a joint probability by minimizing a given distance [START_REF] Hastie | Classification by pairwise coupling[END_REF][START_REF] Wu | Probability estimates for multi-class classification by pairwise coupling[END_REF] to the estimates p(Bi | {Ai, Bi}). One particular type of binary decomposition does not have this problem and always provide consistent constraints: nested dichotomies [START_REF] Fox | Applied Regression Analysis, Linear Models, and Related Methods[END_REF], on which we will focus. As the constraints induced by this decomposition are ensured to be consistent, we drop theˆsign and will use p in the rest of the paper.

Nested dichotomies : how it works

The principle of nested dichotomies is to form a tree structure using the class values y ∈ Y . A nested dichotomy consists in recursively partitioning a tree node C ⊆ Y into two subsets A and B, until every leaf-nodes correspond to a single class value (card(C) = 1). The root node is the whole set of classes Y . As shows the next example, this partitioning makes it straightforward to get the global multi-class problem probability distribution (in contrast with other decompositions [START_REF] Hastie | Classification by pairwise coupling[END_REF][START_REF] Wu | Probability estimates for multi-class classification by pairwise coupling[END_REF]).

Example 2 Let us consider again the example of obstacle recognition. Figure 1 pictures a nested dichotomy tree together with the conditional probability constraints.

Y = {p, b, n} C = {p, b} {p} p(p | C) = 0.6 {b} p(b | C) = 0.4 p({p, b}) = 0.7 {n} p(n) = 0.3 Figure 1. A probabilistic nested dichotomy
In this example, in order to estimate the original multi-class problem probability p(y = p), we need to calculate :

p(y = p) = p(y ∈ {p, b} | Y ) × p(y = p | y ∈ {p, b}) = 0.7 × 0.6 = 0.42.

We can see that to compute the joint probability of a given class, we just need to multiply the conditional probabilities of the branches that links this class (leaf node) to the root (Y ). The full joint can then be obtained by doing that for every class.

The construction of the dichotomy tree

The main issue when building the tree is that there are many possible tree structures to choose from. In the cases where we have prior knowledge about the class structure (such as in ordinal classification [START_REF] Huhn | Is an ordinal class structure useful in classifier learning?[END_REF]), the nested dichotomies are very adapted as they can naturally account for this additional information.

When there is no such prior knowledge, there are two ways to deal with this issue : one is to use an ensemble of dichotomy structures [START_REF] Frank | Ensembles of nested dichotomies for multiclass problems[END_REF]. We will not consider ensemble method in this work, as our goal is to study the extension of dichotomy tree to imprecise probabilities. Ensembling over such models is left for future works.

Another approach when no prior knowledge is available, is to use statistics or data mining on the training dataset. [START_REF] Lorena | Building binary-tree-based multiclass classifiers using separability measures[END_REF] reviews several ways to build binary tree using separability measures. The basic idea of such techniques is to group classes according to their statistical similarity, in order to build binary problems whose subsets of classes are well separated. A commonly used approach (retained in this paper) is to build a k × k distance matrix M between every pair ωi, ωj of classes and then to use hierarchical clustering techniques to obtain the tree. The next matrix

M p b n p 0 2 5 b 2 0 6 n 5 6 0
illustrates a distance matrix for our obstacle recognition example, where n is further away from the other classes, suggesting that p, b should be kept together.

Classification with nested dichotomies

Let us now detail how prediction and inferences can be obtained using conditional probabilities estimated for each partition (using a base probabilistic classifier). Note that for a given node C partitioned into A, B, we have

p(A | C) = 1 -p(B | C) by duality.
The inferences in nested dichotomies are made using the expected costs defined in Section 2.1. Assume we have a split {A, B} of a node C, and a real-valued cost function c : {A, B} → R defined on {A, B}. We can compute the (local) expectation associated with the node C by :

EC (c) = E p(|C) (c) = p(A | C)c(A) + p(B | C)c(B). (4)
Now, if we start from a cost function c : Y → R defined on the classes (i.e. leaf nodes), then using the law of iterated expectation with nested conditioning sets [4, P. 449], we can apply Eq. ( 4) recursively from the leafs to the root Y , in order to get the global expectation. This is because we can view any expected cost EC associated with a node C as a cost function c(y) = E(| C = y) on C.

Example 3

In Example 2, to decide between "pedestrian" and "nothing" with the tree pictured in Figure 1, we just need to compute the expected cost E {p,b,n} (cncp) as recalled in Section 2.1. Local expectation computations are noted under the nodes of Figure 2. Finally we have : As shown in the Figure 2, we have

Y = {p, b, n} C = {p, b} p p(p | C) = 0.6 b p(b | C) = 0.4 p({p, b}) = 0.7 n p(n) = 0.3 E {p,b,n} = 3.6 • 0.7 -2 • 0.3 4 3 -2 E {p,b} = 4 • 0.6 + 3 • 0.4 = 3.6
E {p,b,n} (cn -cp) = 0.7 • 3.6 -0.3 • 2 = 1.92 > 0
Therefore we have p ≻ n, as choosing n instead of p is costly.

Imprecise nested dichotomies

Clearly the accuracy of a nested dichotomy will heavily depends on the tree structure. Indeed, a wrong estimate of one conditional probability may biase the whole structure, leading to unreliable and potentially wrong inferences. Therefore it seems interesting to replace the precise estimates by interval-valued ones, the width of which reflects the lack of information. Such intervals define an imprecise probabilistic classifier that we study in this section. We will see that one advantage of this classifier, in contrast with other imprecise probabilistic classifiers [START_REF] Zaffalon | The naive credal classifier[END_REF], is that it can handle generic and unitary costs with the same computational complexity. Moreover, this complexity is of the same order as its precise counterpart. In the rest of this section, we explain how to make indeterminate predictions from such imprecise nested dichotomies.

Generalization to imprecise probability

We now allow every local model to be imprecise, that is to each node C can be associated an interval Given a cost function c, computing E and E can be done as in the precise case shown in section 3.2. For instance, the lower local expected cost of a node C becomes :

E C (c) = min p(A | C)c(A) + p(B | C)c(B); p(A | C)c(A) + p(B | C)c(B) (5)
Similarly to Section 3.2, the law of iterated expectation can be applied to compute E Y and EY [21, Sec. 6.3.5] [START_REF] De Cooman | Imprecise probability trees: Bridging two theories of imprecise probability[END_REF] recursively by going from the leaves to the root. The upper expected cost EY is obtained by replacing min by max in (5) since we have the duality

E(c) = -E(-c).
Moreover, as for the precise version, lower/upper probabilities of a class correspond to p(ω) = E(Iω) and p(ω) = E(Iω).

Example 4 We consider Example 3 in the imprecise probabilities framework : now all conditional probabilities estimated by the local base classifiers are interval-valued (see Figure 3). Let us see how the expected cost E Y (c bcp) is calculated :

Similarly than in the precise case, by using (5) and knowing that : As the example shows, computing with imprecise nested dichotomies is as easy as with precise one: lower and upper estimates are still multiplicative along a branch. This is in contrast with other imprecise models, where adding imprecision makes inferences computationally costly.

Decision making with imprecise nested dichotomies

Since E Y and EY are not linear, Eqs. ( 1) and ( 2) used as decision criteria in the precise case, are no longer equivalent in the imprecise one.

Actually, there are several ways to extend the classical expected cost criterion to imprecise probabilities [START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF]. They can be grouped in two groups depending on the type of decision : some rules give a unique output class (e.g. maximin), other may give a set of possible optimal classes (e.g. interval dominance, maximality). In our work, we concentrate on the second one, as we are interested in indeterminate but reliable predictions. These rules consist in constructing a partial order ≻ over classes and then to select the maximal ones in this order.

Definition 1 (Maximality) Under the maximality criterion,

ωi ≻M ωj ⇔ E(cω j -cω i ) > 0. (6)
This criterion extends Eq. ( 2). Eq. ( 6) can be interpreted as follows: ωi is preferred to ωj if exchanging ωi for ωj has a positive lower expected cost. The (possibly) imprecise decision YM obtained from this criterion is

YM = ωi ∈ Y | ∃ωj : ωi ≻M ωj .
In Example 4, we have that p ≻M b. Note that obtaining the order ≻ requires to perform k(k -1) computations (one for each pair). Also, while maximality has strong theoretical justifications [21, Sec. 3.9.], other decision criteria such as interval dominance may be preferred if computational time is an important issue (e.g., when the number of classes is high).

Definition 2 (Interval dominance) Under interval dominance criterion,

ωi

≻ID ωj ⇔ E(cω i ) < E(cω j ). (7)
The interval dominance criterion extends Eq. ( 1). The (possibly) imprecise decision YM obtained from this criterion is

YID = ωi ∈ Y | ∃ωj : ωi ≻ID ωj .
Using this rule as our prediction criterion requires to compare lower expectation bounds of every class cost with the minimal upper bound, thus requiring only 2k computations.

It is known that y ≻ID z implies y ≻M z, but not the reverse [START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF], hence interval dominance is more conservative than maximality. For instance, the tree pictured in Figure 3 is such that E p,b,n (cp) = 1.2 and E p,b,n (c b ) = 0.88, so we do not have p ≻ID b. This is due to the fact that probabilities used within P to reach upper and lower expectations are most of the time different, hence interval dominance comparisons are done for different probabilities, while maximality comparisons are not. The latter makes more sense in our framework, as we assume that there is one true but ill-known probability. Therefore, we will use the maximality criterion in our experiments.

Experiments

In this section, our method is tested on 14 datasets of the UCI machine learning repository [START_REF] Bache | UCI Machine Learning Repository[END_REF], whose details are given in Table 1. As base classifiers, we use the common naive Bayes classifier (NBC) and its imprecise counterpart, the naive credal classifier (NCC), which despite their simplicity provide good accuracies. For details on the NCC, we refer to [START_REF] Zaffalon | The naive credal classifier[END_REF]. This is sufficient in the present study, in which our goal is to compare the imprecise nested dichotomies to their precise and multi-class counterparts.

Experimental set-ups

Discretization

As NBC and NCCs cannot handle continuous variables natively, continuous features in data sets (data sets with C in second column of Table 1) were discretized. We chose to discretize all continuous features by dividing their domain in 8 intervals of equal width. We did not use a supervised discretization method such as Fayyad and Irani [START_REF] Fayyad | Multi-interval discretization of continuous-valued attributes for classification learning[END_REF], as the classes changes between the initial multi-class problem and each binary sub-problem.

Class distance

To apply Section 3.1 approach, we need to define a distance to establish the distance matrix used in the hierarchical clustering. Let us denote by pω i (X j = x) = occ j i (x) /occ i the empirical probability that feature X j takes value x given that the class is ωi, with occ j i (x) the number of samples (x, y) of data set D for which x j = x when y = ωi, and occi the number of samples for which y = ωi. Once these probabilities have been estimated (note that we have to estimate them to build the naive classifiers anyway), we define distance M i,i ′ between classes ωi and ω ′ i as

∀ωi, ω ′ i ∈ Y, M i,i ′ = j∈[1;m] H(pω i (X j ), p ω ′ i (X j )),
where H is the Hellinger distance. H is defined for two probability distributions P and Q as H(P, Q) = 1 -BC(P, Q), where BC is the Bhattacharyya coefficient :

BC(P, Q) = x∈X P (x)Q(x).
There are other distances between probability distributions we could use [START_REF] Cha | Comprehensive survey on distance/similarity measures between probability density functions[END_REF], yet our goal is not to make a comparative study of those distances, and we will see that the Hellinger distance provides good results.

Once the distance is defined, we use different hierarchical clustering linkage criteria (maximum, minimum, average [START_REF] Hastie | The elements of statistical learning[END_REF]Sec. 14.3], Ward [START_REF] Ward | Hierarchical grouping to optimize an objective function[END_REF]) to build the tree, and select the one yielding the best predictive accuracy on the learning dataset.

Tests and results

This section summarizes the results of the test. Each result is obtained by a 10-fold cross validation on the (possibly discretized) data set. As we can make indeterminate predictions, we will use performance measures adapted to the comparison of indeterminate and determinate classifiers. We will also concentrate on unitary costs, as such measures are only valid for unitary costs and as the used benchmark data sets do not come with pre-defined costs.

Performance comparison

In order to fairly compare precise methods and imprecise ones, we need to evaluate both the precision and the accuracy at the same time. The idea is to penalize the imprecise prediction according to its imprecision level. Hence, we use a utility-discounted accuracy (u65) introduced by [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF]. Let xi, yi(i = [1; n]) be the set of test data and Yi our (possibly imprecise) predictions, then u65 is

u65 = 1 n n i=1 -1.2d 2 i + 2.2di
,

where di = 1 Y i (y i ) /|Y i | is the discounted accuracy (1Y i (yi)
is the indicator functions that has value 1 if yi ∈ Yi and 0 otherwise). Compared to the discounted accuracy, u65 accounts for the fact that making the cautious statements that we are in Yi (without saying more) is preferable to give as precise prediction a purely random guess within Yi (see [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF] for details). Also, u65 is less in favour of indeterminate classifiers than the F1 measure proposed by Del Coz et al. [START_REF] Del Coz | Learning nondeterministic classifiers[END_REF], meaning that we remain quite fair to the determinate classifier.

In the experiments whose results are given in Table 2, we used three methods: nested dichotomies with the naive Bayes classifier (ND+NBC), nested dichotomies with the naive credal classifier (ND+NCC) and the naive credal classifier (NCC). This allows us to compare the precise and imprecise dichotomy, as well as the imprecise dichotomy with its multi-class counterpart. First, we can notice that our imprecise classifier yields the best average rank over the 14 data sets. However, using Demsar's approach [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF] by applying the Friedman test on the ranks of algorithm performances for each dataset, we find a value of 0.57 for the chisquared test with 2 degree of freedom, so the p-value is 0.75 and we cannot reject the null hypothesis, meaning that all methods have comparable performances in terms of accuracy. Yet, our approach has several advantages that we now detail.

Gain of accuracy on indeterminate predictions

The main goal of indeterminate classifiers is to make indeterminate predictions including the true class on cases (and ideally only on those) where the determinate classifier fails. To show that this is indeed the case here, Figure 4 displays, on the instances where the ND+NCC made indeterminate predictions, the percentage of times the true class is within the prediction, both for the ND+NBC and ND+NCC. We observe an important gain in accuracy on indeterminate predictions for all data sets, except on balance-scale for which the gain is lower. While an imprecise classifier will always be more accurate than its precise counterpart, we can notice that on those instances where the imprecise classifier is indeterminate, the accuracy of its precise counterpart is usually much lower than the average obtained for the whole data set displayed in Table 2 (e.g., page-blocks drops from 90% to 50%). This clearly shows that using imprecise estimates in the nested dichotomies is sensible, as indeterminate predictions are made on instances that are hard to classify for the precise method.

Comparison of indeterminacy with NCC

Figure 5 displays, for the ND+NCC and NCC, the percentage of indeterminate predictions. We can see that for all data sets, the ND+NCC method is more determinate than NCC, while keeping comparable performances (see Tab. 2). While the gain remains marginal in many data set, it can nevertheless be significant for some data sets (ecoli, glass, lymph, grub-damage, soybean, zoo).

Conclusions

In this paper, we have introduced the notion of imprecise nested dichotomies and how to perform efficient inferences from them. Our experiments show that nested dichotomies have a very interesting behaviour: they allow to be cautious on hard to predict instances for precise classifiers, while being more determinate than imprecise multi-class approaches. More importantly, they remain efficient even when integrating error costs in the inferences, while other imprecise probabilistic classifiers tipycally necessitate more complex computations to do that.

In future works, we intend to explore other approaches to build the dichotomy tree, as well as the application of ensemble approaches in the imprecise context. We would also like to explore to which measure the efficiency of imprecise nested dichotomies can be improved, e.g., by suing results on label trees [START_REF] Liu | Probabilistic label trees for efficient large scale image classification[END_REF]. Finally, we intend to apply nested dichotomies on structured classes (e.g., ordinal regression [START_REF] Huhn | Is an ordinal class structure useful in classifier learning?[END_REF]).

Figure 2 .

 2 Figure 2. Expectation computation for cncp.

  [p(A | C); p(A | C)], precise nested dichotomies being retrieved when p(A | C) = p(A | C) for every node C. By duality of the imprecise probabilities [21, Sec.2.7.4.], we have p(A | C) = 1p(B | C) and p(A | C) = 1p(B | C). Such an imprecise nested dichotomy can be associated to a set P of joint probabilities, obtained by considering all precise selection p(A | C) ∈ [p(A | C); p(A | C)] for each node C. This set can then be associated with lower and upper expectations [E Y (c); EY (c)]

EFigure 3 .

 3 Figure 3. Example of nested dichotomies with imprecise probabilities

Figure 4 .

 4 Figure 4. Accuracy of the methods "ND+NBC" and "ND+NCC" when a imprecise prediction is made by "ND+NCC".

Figure 5 .

 5 Figure 5. Percentage of set-valued predictions made by NCC and ND+NCC.

Table 1 .

 1 data set details

	Name	(C)ont/(D)isc features # instances # classes
	balance-scale	D	625	3
	car	D	1728	4
	lymph	D	148	4
	LEV	D	1000	5
	nursery	D	12960	5
	zoo	D	101	7
	soybean	D	562	15
	iris	C	150	3
	wine	C	178	3
	grub-damage	C	155	4
	page-blocks	C	5473	5
	glass	C	214	6
	ecoli	C	336	8
	pendigits	C	10992	10

Table 2 .

 2 Comparison of discounted accuracy (u65) for the methods ND+NBC, NCC and ND+NCC.

			u 65 (rank)
	Data	ND + NBC	NCC	ND + NCC
	balance-scale	91.68% (1)	90.72% (3)	90.98% (2)
	car	84.09% (3)	88.11% (1)	86.72% (2)
	lymph	80.41% (1)	59.02% (3)	67.58% (2)
	LEV	58.20% (3)	61.50% (1)	60.69% (2)
	nursery	90.58% (3)	91.02% (1)	90.99% (2)
	zoo	96.04% (1)	77.96% (3)	84.85% (2)
	soybean	81.85% (2)	84.12% (1)	80.68% (3)
	iris	94.67% (3)	95.47% (2)	95.60% (1)
	wine	96.63% (1)	94.72% (3)	95.06% (2)
	grub-damage	49.68% (3)	52.90% (2)	53.81% (1)
	page-blocks	91.36% (3)	92.01% (1)	91.69% (2)
	glass	60.75% (2)	60.51% (3)	65.43% (1)
	ecoli	76.49% (1)	58.11% (3)	74.83% (2)
	pendigits	70.25% (3)	87.3% (1)	71.61% (2)
	average rank	2.14	2	1.86

Heudiasyc Laboratory, Université de Technologie de Compiègne, France, email: gen.yang@hds.utc.fr

ACKNOWLEDGEMENTS

This work was carried out in the framework of the Labex MS2T, which was funded by the French National Agency for Research (Reference ANR-11-IDEX-0004-02).


come

Design of fuzzy adaptive control for MIMO nonlinear time-delay systems with unknown actuator nonlinearities and control direction

Abdesselem Boulkroune, Mohammed M'Saad, Hassan Chekireb


Liza Mouret

Grégory Da Costa

Arnaud Bondon

Sterols associated with Small Unilamellar Vesicles (SUV): intrinsic mobility role for 1 H NMR detection

Small unilamellar vesicles (SUV) of phospholipids are often used as a membrane model system for studying the interaction of molecules. When using NMR under the standard liquid state conditions, SUV phospholipid proton spectra can be recorded, exhibiting sharp signals. This is not only due to the fast vesicular tumbling, but rather to the combination of this tumbling with the individual motion of the lipids inside the bilayer. This appears evident because addition of cholesterol is responsible of broader resonances due to the slowing down of the lipid motion. On the other hand, no 1 H signal is detected for cholesterol in the bilayer. This lack of detection of the inserted molecules explains why generally SUV are not considered as a good model for NMR studies under the standard liquid state conditions. Here we use two other sterols in order to demonstrate that an increase of the molecular mobility inside the bilayer could allow the detection of their proton resonances. For desmosterol and lanosterol, which show higher mobility inside the bilayer, with increasing lateral diffusion rates, 1 H sterol signals are detected in contrast to cholesterol. For the fast diffusing lanosterol, no significant improvement in detection is observed using deuterated lipids, demonstrating that homonuclear dipolar coupling is fully averaged out. Furthermore, in the case of low mobility such as for cholesterol, the use of a fast magic angle spinning probe is shown to be efficient to recover the full proton spectrum.

Introduction

Interaction of molecules with the membrane is the first step in a wide range of cellular processes. Therefore, the characterization of these interactions represents an important approach for understanding various biological phenomena. Because of the complexity of native membranes, artificial models are often used for studying these interactions, with each model having its own advantages and limitations and being more or less convenient for each biophysical technique of analysis. Here, we focus on small unilamellar vesicles (SUV) as a membrane model for studying these interactions by nuclear magnetic resonance experiments. This model has been widely used in several biophysical studies based on various techniques such as fluorescence, circular dichroism or dynamic light scattering, and currently forms a standard model for analysing processes involving interactions with the membrane. NMR has been only sparingly used for the analysis of such interactions. Cholesterol was one of the first molecules studied in phospholipid SUV 1- 5 and the complete absence of inserted cholesterol 1 H signals led many authors to conclude that SUV are inappropriate for 1 H NMR experiments. 6 Consequently, it was only seldom used in NMR studies. Other models such as multilamellar vesicles (MLV) or oriented samples were favoured due to the wide development of solid-state NMR methods over the last 20 years. [7][8][9][10][11][START_REF] Brown | Modern Magnetic Resonance[END_REF][START_REF] Judge | [END_REF][14][15][16] However, the small diameter of SUV -between 30 nm and 50 nm -ensures a fast tumbling motion, with a correlation time in the microsecond range, which, combined with the individual movements of phospholipids, leads to an efficient averaging out of dipolar couplings and chemical shift anisotropy. This gives rise to sharp NMR resonances for the lipids under standard liquid state conditions, even in proton NMR. This is not true with larger vesicles (LUV) which display proton broad resonances for the lipids, highlighting the role of the vesicular tumbling. This strong sensitivity of the lipid signals linewidths has been used in the case of SUV to characterize the decrease of the individual motion of the phospholipids, induced for example by naphthalene derivative 17 or to obtain evidence of vesicles fusion induced by a peptide. 18 Studying molecules interacting with SUV is more complex since their signals are not always detected. However, few NMR studies have been reported using SUV, as already pointed out in a review 19 where we described these studies and, more specifically, discussed the conditions for good 1 H NMR detection of molecules interacting with lipids in SUV. For efficient averaging out of anisotropic interactions -essentially dipolar couplings for the 1 H nuclei -it is important to take into account not only the vesicle tumbling, but also the associationdissociation dynamics of the interacting molecules. In the review, as well as in a previous study on porphyrins and cytochrome c interactions with SUV, we discussed the role of association-dissociation dynamics in the 1 H detection of associated molecules, through the dissociation kinetic rate constant (k off ). 19,20 In fact, a high k off is required to ensure a good averaging out of dipolar couplings, thus allowing the detection of sharp resonances. As an example, the neurotensin structure in presence of SUV was recently solved by NMR under the standard liquid state conditions. 21 In this study, we focus in more detail on the role of the mobility of interacting molecules inside the bilayer for ensuring good 1 H NMR detection. For this purpose, we investigate different sterols incorporated in phospholipid SUV: cholesterol and two of its precursors, desmosterol and lanosterol. About sterol interactions with SUV, the impact of the kinetic rate constant can be ruled out because of its high value; it has been reported as less than 1 h -1 for cholesterol. [22][23][24] Although we failed to find similar data for the two other sterols, desmosterol and lanosterol, strong dynamic behaviour are not expected. The behaviour of these compounds inside a lipidic bilayer have already been studied using multilamellar vesicles (MLV) 25,26 and the main purpose of our study was to determine the condition of good proton NMR detection when using SUV. Cholesterol is a major constituent of eukaryotic cell membranes, especially plasma membranes, where it can account for up to 50% of the lipid fraction. It is absolutely essential for normal cell functioning, viability and proliferation. Despite extensive studies on cholesterol over the last 40 years, its biological role is still not fully understood. Its most important function seems to be its ability to modulate the physicochemical properties of the membrane. 27 It influences the lateral organization of the membrane constituents, contributing to the formation of caveolae and, along with sphingomyelin, the development of membrane domains called lipid rafts. [28][29][30][31] These modifications of membrane properties result from the ability of cholesterol to promote strong variations of the lipid phase. These variations brought about by cholesterol are complex and have been widely studied by several techniques. 25,[32][33][34][35][36][37][38][39][40][41][42][43] They still represent an important research area because they are at the origin of the various cholesterol properties in the cellular membrane. This aspect is not discussed here in more detail, since, for our purpose, we only consider cholesterol properties related to its slow motion, compared to other sterols, when incorporated into a bilayer as well as its ability to slow down lipid motion by stiffening the membrane and ordering the lipid acyl chains. 26,34,36,[44][45][46][47] The aim of our study is to show that, in addition to the fast tumbling of the small vesicles, fast internal motion inside the SUV is sufficient to sharpen enough the 1 H signals of interacting molecules for NMR experiments under standard liquid state conditions. With this in mind, we studied desmosterol and lanosterol incorporated in SUV. These two cholesterol precursors in the biosynthetic pathway have been studied in lipid membranes by Pulsed Field Gradient Magic Angle Spinning NMR, showing increased diffusion rates inside the bilayer. 48 Desmosterol differs from cholesterol by having only one double bond between C 24 and C 25 (Figure 1). Again, the modifications of the phase induced by this sterol are complex and dependent on lipid composition. Desmosterol seems to have only a weak effect on stabilizing raft formation 49 and altering the membrane lateral pressure profile 50 . The small structural difference with cholesterol induces an increasing mobility inside the bilayer, with higher diffusion rates not only for desmosterol but also for the membrane lipids. 48 Lanosterol differs more significantly from cholesterol than desmosterol. It has the same double bond between C 24 and C 25 as desmosterol. Otherwise, there is a double bond between C 8 -C 9 instead of C 5 -C 6 , and three additional methyl groups, two at the C 4 and one at the C 14 positions, which lead to a less planar structure of the molecule (Figure 1). This less flat structure seems to give rise to weaker interactions with the lipids, and produces a higher mobility for the molecule inside the bilayer [51][52][53] along with a lower membrane rigidity. 54 Lanosterol undergoes a higher lateral diffusion rate in the membrane than desmosterol 48 as well as a higher flip-flop rate than cholesterol. 55 It induces lower order parameters of the acyl lipid chains, whereas the order parameters are of the same magnitude for cholesterol and desmosterol inserted in the bilayer. 8,48,[56][57][58] Here, we focus on the increasing mobility of the three sterols inside the bilayer. By studying these sterols in SUV, we show that, when motion inside the bilayer is sufficiently high, the interacting molecule can be detected with good precision by 1 H NMR under standard liquid state conditions. As in many artificial membrane studies, DMPC (1,2-Dimyristoyl-sn-Glycero-3-Phosphocholine) was chosen since it mimics the saturated natural membrane lipids that are preferentially associated with cholesterol in lipid microdomains. The transition temperature between the gel and liquid crystalline phase is 23°C, which facilitates the preparation of multilamellar vesicles (MLV) at convenient working temperatures. We chose a molar ratio of 70:30 for the preparation of DMPC:Sterol vesicles since 30% corresponds to a typical cholesterol content in mammalian membrane cells.

Materials and methods

Materials

Cholesterol, desmosterol and lanosterol were purchased from Sigma-Aldrich Co. (St. Louis, MO). The phospholipids 1,2-Dimyristoyl-sn-Glycero-3-Phosphocholine (DMPC), 1,2-Dimyristoyl-d 54 -sn-Glycero-3-Phosphocholine (DMPC-d 54 ) and 1,2-Dioleoyl-sn-Glycero-3-Phosphocholine (DOPC) were purchased from Avanti Polar Lipids Inc. (Alabaster, AL). Sterols and lipids were used without further purification.

Preparation of vesicles

Lipids and sterols in appropriate amounts were mixed in chloroform and dried under vacuum to obtain a thin film. For desmosterol-lipid and lanosterol-lipid mixtures, the film was sometimes quite inhomogeneous, so further solubilisation in cyclohexane was required followed by a second and eventually a third evaporation under vacuum. 8 Multilamellar vesicles were then obtained by rehydrating the film, at concentrations between 10 mM and 125 mM of total lipids depending on the mixtures. D 2 O was used for rehydration, and MLV preparations then were placed without further transformation in the HR-MAS rotor for HR-MAS NMR experiments. SUV were obtained as previously described 59 by sonication of the MLV preparation at the chosen concentration for a few minutes at room temperature, using the micro-tip of a sonicator (U200S, UKA Labortechnic). Centrifugation was applied to eliminate titanium debris from the sonicator probe. SUV samples were always freshly prepared. Vesicles formation and stability during NMR acquisition at the working temperature were then directly checked on 1 H NMR spectra, which display sharp resonances with a choline headgroup methyl 1 H splitting due to the curvature differences between intra and extra layers of the vesicles 60 . Further control of the absence of aggregation was performed as previously by dynamic light scattering (4700/PCS100 Malvern) and 31 P NMR experiments, exhibiting resonance linewidths below 150 Hz as expected for SUV. 59 NMR measurements 1 H NMR measurements for SUV and MLV samples were carried out on two Bruker AVANCE 500 spectrometers operating at 500.12 MHz and 500.15 MHz and equipped with a 5 mm cryo-probe TXI and a 5 mm BBO probe, respectively. 31 P spectra were obtained with the 5 mm BBO probe. 1 H HR-MAS NMR measurements for MLV samples were performed on the second spectrometer with a triple-inverse HR-MAS probe, using 50 µl rotors and at a spinning frequency up to 12000 Hz. Different working temperatures were used, and the spectra are presented at 323K. Spectra using very high spinning rate at the magic angle were acquired on a Bruker Avance 750 spectrometer operating at 750.12 MHz with a MAS 1.3 mm triple resonance probe. In all experiments, the residual water HDO peak was suppressed by using presaturation.

Results and discussion

When cholesterol is incorporated into SUV made up of phospholipids, we firstly observe that the lipid signals are broadened with increasing amounts of cholesterol in the SUV. This is because cholesterol stiffens the membrane and reduces the phospholipid motion. As already described in many papers (see for example reference 40) several lipid movements, on different time scales, take place in a bilayer : rotation around chemical bounds (picoseconds), transgauche isomerisation (picoseconds), axial diffusion (rotation) around the lipid molecule axis (nanoseconds), wobbling of this axis (nanoseconds), lateral diffusion inside the bilayer (microseconds), flip-flop (from milliseconds to seconds) and undulatory membrane motion (from milliseconds to seconds). As already mentioned it has been largely described in the literature that incorporating cholesterol in the membrane has the effect of increasing the acyl-chain phospholipid order parameters. The axial diffusion and wobbling seems to remain unperturbed 33,61 whereas cholesterol drastically limits the trans-gauche isomerisation favouring the trans conformation 46 as well as it reduces the lateral diffusion of the lipids. 48 The resulting effect on SUV spectra has been previously discussed in several papers [62][63][64] and is illustrated in Figure 2 which compares the spectra of 1 H pure DMPC SUV with DMPC:Cholesterol SUV at molar ratios of 95:5 and 70:30. The acyl chain signals clearly broaden with increasing cholesterol content. The intensity ratio between the signals of methylene acyl chains and the terminal acyl chain methyl groups shows a strong reduction as the membrane stiffens owing to increased amounts of cholesterol. On the other hand, as mentioned in the introduction, no cholesterol signal is detected on these spectra. When using protonated lipids, a large number of cholesterol resonances are masked by the lipid signal themselves, as can be seen by comparing the spectra of protonated and deuterated DMPC:Cholesterol SUV 1 H at a ratio of 70:30 (see Figure 3; A.a and B.a). How-ever, even with protonated lipids, some cholesterol resonances should be detected outside the lipid signal range (Figure 4; A.a). The invisibility of the sterol signal in SUV has thus been generally attributed to the tumbling motion of the vesicles, which is not fast enough to average out dipolar couplings for the inserted molecule. However, averaging out of these couplings can be obtained by using MAS techniques with MLV, 3,4,32 as illustrated by the HR-MAS MLV spectrum showing cholesterol signals (see Figure 4; A.a). Nevertheless, when comparing SUV 1 H NMR spectra of DMPC:Sterol and DMPC-d 54 :sterol at 70:30 molar ratios (Figure 3), we can firstly see that, with protonated lipids, the broadening of phospholipid acyl chain signals progressively decreases when changing from cholesterol to desmosterol and lanosterol. For the methylene acyl chains signals, full width at half height decreases from 100 Hz for SUV with cholesterol to 70 Hz and 60 Hz for SUV with desmosterol and lanosterol, respectively. This should be compared to a width of 50 Hz for sterol-free vesicles. At the same time, the intensity ratio between the 1 H signals of methylene acyl chains and the terminal acyl chain methyl groups increases from about 1 for SUV with cholesterol, to 1.6 with desmosterol and 1.7 with lanosterol, compared to 1.8 for sterol-free SUV. While the CH 2 -O-P protons of the glycerol backbone are detected near 4.2 ppm in DMPC:Lanosterol, they mostly disappear in the DMPC:Cholesterol SUV spectrum. These results suggest that the phospholipids recover higher mobility with changing sterol type from cholesterol to desmosterol and lanosterol, in agreement with several previous studies showing a progressive lower ordering effect as well as an increase of the lipid lateral diffusion. 48,53,56 It can also be seen that desmosterol and lanosterol signals are detected, such as the olefinic proton of C 24 , which appears near 5.3 ppm. Proton signals of the C 26 and C 27 methyl groups are detected near 1.8 ppm, both in desmosterol and in lanosterol. The corresponding cholesterol signal is more shielded due to the absence of the double C 24 -C 25 bond; while this signal is masked by the lipid resonances in protonated SUV, it is visible at 1 ppm in deuterated SUV (Fig. 3,B.a). For lanosterol, the signals near 2.2 ppm, 1.2 ppm and 1 ppm corresponds to C 11 and C 12 protons, C 29 and C 6 protons and C 18 protons, respectively. These attributions are based on previous studies obtained by solid-state NMR, for 1 H and [START_REF] Judge | [END_REF] C cholesterol signals 65 and for [START_REF] Judge | [END_REF] C desmosterol and lanosterol signals in DMPC bilayers, 4 and comparison between the three sterol spectra ( 1 H and 1 H- [START_REF] Judge | [END_REF] C HSQC) in SUV and CDCl 3 (not shown here). As pointed out in the introduction, these two sterols have been shown to have a faster dynamic within the bilayer, with higher lateral diffusion and flip-flop rates. Once again several movements take place for the sterol molecules inside the bilayer. Cholesterol has been reported to exhibit fast axial diffusion and axis wobbling with correlation times in the nanosecond range. [66][67][68] An axial diffusion increase is unexpected for desmosterol, only slightly different from cholesterol by one double bond in the hydrophobic tail. The less flat structure of lanosterol, exhibiting several additional methyl groups, might result in different axial diffusion behaviour but no axial diffusion data were found in the literature neither wobbling ones. Measurements of the lateral diffusion coefficients have been carried out by Scheidt and coworkers using 1 H PFG MAS NMR experiments in DPPC (1,2-Dipalmitoyl-sn-Glycero-3-Phosphocholine) membranes. 48 They showed that DPPC and cholesterol diffusion rates are of about the same order (only slightly higher values for cholesterol) and decrease with the amount of cholesterol inserted. DPPC diffusion is faster with desmosterol or lanosterol in the membrane. For desmosterol, the diffusion rates are only slightly higher than for the phospholipid, while they become much faster for lanosterol, indicating weaker interaction with the phospholipids. The apparent diffusion coefficients has been reported to vary, at 320 K, from 8 to 16 × 10 -12 m 2 .s -1 for cholesterol and lanosterol respectively, with a median value at 12 × 10 - 12 m 2 .s -1 for desmosterol. 48 The flip-flop rate constants of cholesterol and lanosterol in DPPC bilayer at low sterol concentration and 323 K, where recently theoretically calculated by Parisio and co-workers, 55 quite in agreement with other molecular dynamic studies of cholesterol flip-flop, [69][70][71] showing an increase of the rate constants from 2 × 10 4 s -1 for cholesterol to 6.6 × 10 4 s -1 for lanosterol. Our results show that as motion increases for the inserted molecule, it becomes possible to detect its 1 H resonances in SUV. Considering that quite small differences in the diffusion coefficient and flip-flop rates, only a factor of two or three between cholesterol and lanosterol, highlights the fact that the fast vesicular tumbling is probably playing a major role for an efficient averaging out of dipolar couplings. But the several kinds of motion are important and should be high enough: the vesicular tumbling, the lipid motion and the inserted molecule motion. Figure 3 also presents a comparison of the protonated and deuterated SUV spectra, showing that deuteration yields sharper signals for desmosterol in the case of signals that are not overlapping with the lipid (C 24 and C 26,27 protons). On the other hand, deuteration only slightly reduces the signal linewidths in the case of lanosterol. 1 H homonuclear dipolar couplings depend on two components: intra-molecular couplings and inter-molecular couplings including sterol-lipid and sterol-sterol couplings. Using deuterated phospholipids prevents intermolecular homonuclear dipolar coupling between the sterol and the phospholipid acyl chain protons. Thus, with protonated lipids, residual 1 H dipolar couplings remain between lipid and sterol molecules for desmosterol in DMPC SUV, but not for the more mobile lanosterol. Hence, for molecules with sufficiently fast dynamic, we can clearly detect 1 H resonances in SUV even without using deuterated lipids. Experiments with DOPC SUV were also carried out with the intermediate desmosterol molecule to see if it is possible to obtain sharper signals using unsaturated phospholipids. Although these latter increase the membrane disorder and exhibit lower-order acyl chain parameters, 46,72 no major improvement was observed (not shown). In Figure 4, we compare the spectra of DMPC:Sterol MLV with HR-MAS and SUV in the standard liquid conditions without rotation. Clearly, whatever the nature of the sterol, good detection is observed in the case of MLV with magic angle spinning. Such a good detection in SUV is only observed with lanosterol, dipolar couplings being efficiently averaged out by the combination of SUV tumbling as well as lipid and molecular motion inside the bilayer. As previously described, 73,74 no improvement is obtained on the DMPC:Cholesterol SUV spectra when using HR-MAS with a spinning rate up to 12 kHz, the vesicular tumbling interfering with the MAS (not shown). We then checked the efficiency of higher MAS rate on SUV composed of DMPC:Cholesterol with molar ratio of 70:30. This Lipid:Cholesterol ratio corresponds to the worse spectrum in the standard liquid state conditions. The 1 H NMR spectrum, recorded at 750 MHz and 40 kHz spinning rate is shown in the Figure 5 and the corresponding MLV spectrum recorded at 500 MHz and 10 kHz is also displayed for comparison. Clearly, both spectra are pretty similar in term of linewidths. The increase of the spinning rate up to 40 kHz enables the detection of signals of inserted cholesterol in SUV. This opens the possibility of working with SUV as a model membrane even for molecules exhibiting very slow dynamics inside the bilayer. This should constitute an interesting approach when SUV is the most relevant membrane model, for example when studying molecules interacting with highly curved membranes.

Conclusions

SUV are generally believed as an unsuitable model membrane for NMR. We show in the present study that as long as the inserted molecules display sufficiently high mobility inside the bilayer sharp 1 H signal are obtained. By studying three sterols inserted in phospholipid SUV, we show that the 1 H signals sharpness is related to the molecule motion inside the bilayer. Cholesterol is invisible in SUV and broadens the lipid signals due to its slow motion inside the membrane and its stiffening and ordering effects on the bilayer, which also slows down the lipid motion. By contrast, while desmosterol and lanosterol display increasing mobility inside the membrane, they do not have such a broadening effect on the lipid signals and can be detected under NMR standard liquid state conditions. For molecules such as cholesterol with very low mobility inside the bilayer, we demonstrate that spinning at the magic angle with a very high spinning rate permits to recover the molecule proton resonances. Finally, SUV constitute an interesting model for studying molecule-membrane interactions provided that the interacting molecule has sufficiently fast dynamics. In the case of molecules with low dynamics inside the bilayer the use of fast magic angle spinning could be an efficient approach to work with SUV.

Figure 1 :Figure 2 : 1 HFigure 3 : 1 H

 12131 Figure 1: Structures of the three sterols and their classical nomenclature

Figure 4 : 1 HFigure 5 : 1 H

 4151 Figure 4 : 1 H NMR spectra of DMPC:Cholesterol (A), DMPC:Desmosterol (B), DMPC:Lanosterol (C), with molar ratio of 70:30, recorded at 323K, for (a) MLV with HR-MAS NMR at 12000Hz spin rate and (b) SUV under the standard liquid state NMR conditions. Intensity units are arbitrary. * * * * in A.a. are cholesterol peaks standing outside the lipid signal range, detected in MLV but not in SUV.

Acknowlegments

Financial support from the TGIR-RMN-THC Fr3050 CNRS for conducting the experiments on the 750 MHz spectrometer is gratefully acknowledged as well as Dr Sylvian Cadars (CEMHTI, Orléans) who was in charge of the project.