Vu-Linh Nguyen
email: linh.nguyen@hds.utc.fr

Sébastien Destercke
email: sebastien.destercke@hds.utc.fr

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

Eyke H Üllermeier

Reliable Multi-class Classification based on Pairwise Epistemic and Aleatoric Uncertainty

We propose a method for reliable prediction in multi-class classification, where reliability refers to the possibility of partial abstention in cases of uncertainty. More specifically, we allow for predictions in the form of preorder relations on the set of classes, thereby generalizing the idea of setvalued predictions. Our approach relies on combining learning by pairwise comparison with a recent proposal for modeling uncertainty in classification, in which a distinction is made between reducible (a.k.a. epistemic) uncertainty caused by a lack of information and irreducible (a.k.a. aleatoric) uncertainty due to intrinsic randomness. The problem of combining uncertain pairwise predictions into a most plausible preorder is then formalized as an integer programming problem. Experimentally, we show that our method is able to appropriately balance reliability and precision of predictions.

Introduction

Classification algorithms are usually designed to produce "point predictions" in the form of single class labels. In cases of uncertainty, however, it might be more desirable to provide imprecise (or indeterminate) set-valued predictions, which are reliable in the sense of covering the true class with high probability-very much in the spirit of confidence intervals known from classical statistics, or credible sets in Bayesian analysis. This is especially true in safety-critical applications, such as medical diagnosis. Needless to say, the construction of appropriate imprecise predictions requires a suitable quantification of the underlying uncertainty.

In the literature on uncertainty modeling, a general distinction is made between epistemic uncertainty, due to a lack of knowledge, and aleatoric uncertainty, due to inherent randomness. Thus, while epistemic uncertainty is in principle reducible, aleatoric uncertainty is not. [START_REF] Senge | [END_REF] recently argued that a distinction between these two types of uncertainty is useful in machine learning, too, where epistemic uncertainty is typically caused by a limited amount of training data, whereas aleatoric uncertainty is due to overlapping class distributions (leading to almost equal posterior probabilities of several classes).

In this paper, we propose a method for producing reliable or "cautious" predictions in the form of preorder relations R on the set of classes Ω = {λ 1 , . . . , λ M }, where (λ i , λ j ) ∈ R suggests that, for an instance x, λ i is (weakly) preferred to λ j as a prediction. To this end, we build on the approach of [START_REF] Senge | [END_REF], which we lift from binary to multi-class classification using appropriate decomposition techniques [Bishop, 2006;[START_REF] Hüllermeier | Fuzzy-relational classification: Combining pairwise decomposition techniques with fuzzy preference modeling[END_REF]. Roughly speaking, preferences and uncertainties are first predicted for each pair of classes, and then combined into an overall relation R, in which aleatoric uncertainty translates into equivalence (indifference) between classes ((λ i , λ j ) ∈ R and (λ j , λ i ) ∈ R), and epistemic uncertainty into incomparability (neither (λ i , λ j ) ∈ R nor (λ j , λ i ) ∈ R). The approach we use for combining the pairwise information into a most plausible preorder is inspired by [START_REF] Masson | [END_REF] and formalized as an integer linear programming problem.

As we said, our main goal is to produce predictions in the form of (credal) sets of classes. Hence, in a final step, we map a preorder to its set of maximal elements. Yet, let us emphasize that a preorder provides very rich information, which could also be used for other purposes. In particular, this type of prediction can be seen as a generalization of set-valued predictions (a subset defining a specific partial order), which in turn can be seen as an extension of classification with reject option (where the prediction is either a singleton set or the entire Ω). In fact, a preorder provides a flexible means for expressing preferences for class predictions, and for partially abstaining from a definite decision. Due to the distinction between incomparability and indifference, it also offers an explanation for why a class is present or not in a prediction.

The rest of the paper is organized as follows. In the next section, we recall a method for reliable binary classification, which allows for distinguishing between aleatoric and epistemic uncertainty. In Section 3, we introduce our method for reliable multi-class classification based on preorder prediction. This approach is instantiated for logistic regression as a base learner in Section 4. Related work is briefly addressed in Section 5, and experimental results are presented in Section 6, prior to concluding the paper in Section 7.

Epistemic and Aleatoric Uncertainty

A main building block of our method is the assessment of the epistemic and aleatoric uncertainty involved in the discrimi-nation between a pair of classes. To this end, we are going to adopt the formal model proposed in [START_REF] Senge | [END_REF], which is based on the use of relative likelihoods, historically proposed by Birnbaum [Birnbaum, 1962] and then justified in other settings such as possibility theory [Walley and Moral, 1999]. For the sake of completeness, the essence of this approach is briefly recalled in the remainder of this section.

The approach proceeds from an instance space X , an output space Ω = {0, 1} encoding the two classes, and a hypothesis space H consisting of probabilistic classifiers h : X -→ [0, 1]. We denote by p h (1 | x) = h(x) and p h (0 | x) = 1 -h(x) the (predicted) probability that instance x ∈ X belongs to the positive and negative class, respectively. Given a set of training data

D = {(x i , y i )} N i=1 ⊂ X × Ω, the normal- ized likelihood of a model h is defined as π H (h) = L(h) L(h ml ) = L(h) max h ∈H L(h ) , (1)
where

L(h) = N i=1 p h (y i | x)
is the likelihood of h, and h ml ∈ H the maximum likelihood estimation on the training data. For a given instance x, the degrees of support (plausibility) of the two classes are defined as follows:

π(1 | x) = sup h∈H min π H (h), p h (1 | x) -p h (0 | x) ,(2) π(0 | x) = sup h∈H min π H (h), p h (0 | x) -p h (1 | x) .(3) So, π(1 | x)
is high if and only if a highly plausible model supports the positive class much stronger (in terms of the assigned probability mass) than the negative class (and π(0 | x) can be interpreted analogously)1 . Note that, with f (a) = 2a -1, we can also rewrite (2)-(3) as follows:

π(1 | x) = sup h∈H min π H (h), f (h(x)) , (4)
π(0 | x) = sup h∈H min π H (h), f (1 -h(x)) . (5)
Given the above degrees of support, the degrees of epistemic uncertainty u e and aleatoric uncertainty u a are defined as follows:

u e (x) = min π(1 | x), π(0 | x) , (6)
u a (x) = 1 -max π(1 | x), π(0 | x) . (7)
Thus, epistemic uncertainty refers to the case where both the positive and the negative class appear to be plausible, while the degree of aleatoric uncertainty (7) is the degree to which none of the classes is supported. These uncertainty degrees are completed with degrees s 1 (x) and s 0 (x) of (strict) preference in favor of the positive and negative class, respectively:

s 1 (x) =        1 -(u a (x) + u e (x)) if π(1 | x) > π(0 | x), 1-(ua(x)+ue(x)) 2 if π(1 | x) = π(0 | x), 0 if π(1 | x) < π(0 | x).
With an analogous definition for s 0 (x), we have s 0 (x) + s 1 (x) + u a (x) + u e (x) ≡ 1. In addition to defining a partition of unity, the quadruple (s 1 (x), s 0 (x), u e (x), u a (x)) has the following properties:

s 1 (x) (s 0 (x)) will be high if and only if, for all plausible models, the probability of the positive (negative) class is significantly higher than the one of the negative (positive) class; -u e (x) will be high if class probabilities strongly vary within the set of plausible models, i.e., if we are unsure how to compare these probabilities. In particular, it will be 1 if and only if we have h(x) = 1 and h (x) = 0 for two totally plausible models; -u a (x) will be high if class probabilities are similar for all plausible models, i.e., if there is strong evidence that h(x) ≈ 0.5. In particular, it will be close to 1 if all plausible models allocate their probability mass around h(x) = 0.5.

Reliable Multi-class Prediction

In this section, we present our approach to reliable multi-class prediction, which is based on the idea of binary decomposition and a stepwise simplification (approximation) of the information contained in the set of pairwise comparisons between classes-first in terms of a preorder and then in terms of a set.

Learning by Pairwise Comparison

In the multi-class setting, we are dealing with a set of Learning by pairwise comparison (LPC) a.k.a. all-pairs is a decomposition technique that trains one (binary) classifier h i,j for each pair of classes (λ i , λ j ), 1 ≤ i < j ≤ M [START_REF] Fürnkranz | Johannes Fürnkranz. Round robin classification[END_REF]. The task of h i,j , which is trained on D i,j = D i ∪ D j , is to separate instances with label λ i from those having label λ j . Suppose we solve these problems with the approach described in the previous section, instead of using a standard binary classifier. Then, given a new query instance x ∈ X , we can produce predictions in the form of a quadruple

M > 2 classes Ω = {λ 1 , . . . , λ M }. Suppose a set of training data D = {(x n , y n )} N n=1 ⊂ X × Ω to
I i,j (x) := s i,j λi (x), s i,j λj (x), u i,j e (x), u i,j a (x) , (8)
one for each pair of classes (λ i , λ j ). These predictions can also be summarized in three [0, 1] M ×M relations, a (strict) preference relation P , an indifference relation A, and an incomparability relation E:

P = s i,j λi (x) i,j , A = u i,j a (x) i,j , E = s i,j e (x) i,j
Recall that our approach is transductive in the sense that predictions are always derived per instance, i.e., for an individual query instance x. Likewise, all subsequent inference steps are tailored for that instance. Keeping this in mind, we will henceforth simplify notation and often omit the dependence of scores and relations on x.

Inferring a Preorder

The structure (P, A, E) provides a rich source of information, which we seek to represent in a condensed form. To this end, we approximate this structure by a preorder R. This approximation may also serve the purpose of correction, since the relational structure (P, A, E) is not necessarily consistent; for example, since all binary classifiers are trained independently of each other, their predictions are not necessarily transitive.

Recall that a preorder is a binary relation R ⊆ Ω × Ω that is reflexive. In the following, we will also use the following notation:

λ i R λ j (or simply λ i λ j ) if r i,j = 1, r j,i = 0 , λ i ∼ R λ j (or simply λ i ∼ λ j ) if r i,j = 1, r j,i = 1 , λ i ⊥ R λ j (or simply λ i ⊥ λ j ) if r i,j = 0, r j,i = 0 , where r i,j = 1 if (λ i , λ j ) ∈ R and r i,j = 0 if (λ i , λ j ) ∈ R.
Note that the binary relations , ∼, ⊥ are in direct correspondence with the relations P , A, and E, respectively.

How compatible is a relation R with a structure (P, A, E)? Interpreting the scores (8) as probabilities, we could imagine that a relation R is produced by randomly "hardening" the soft (probabilistic) structure (P, A, E), namely by selecting one of the relations λ i λ j , λ j λ i , λ i ∼ λ j , λ i ⊥ λ j with probability s i,j λi , s i,j λj , u i,j a , and u i,j e , respectively. Then, making a simplifying assumption of independence, the probability of ending up with R is given as follows:

p(R) = λi R λj s i,j λi λj R λi s i,j λj λi ⊥ R λj u i,j e λi∼ R λj u i,j a (9)
The most probable preorder R * then corresponds to

R * = arg max R∈R p(R) , ( 10
)
where R is the set of all preorders on Ω.

Let us now propose a practical procedure to determine R * , which is based on representing the optimization problems (10) as a binary linear integer program. To this end, we introduce the following variables:

X 1 i,j = r i,j (1 -r j,i ), X 2 i,j = r j,i (1 -r i,j ), X 3 i,j = (1 -r i,j )(1 -r j,i ), X 4 i,j = r i,j r j,i .
Then, by adding the constraints 4 l=1 X l i,j = 1 and X l i,j ∈ {0, 1}, we can rewrite the probability (9) as follows:

p(R) = i<j s i,j λi X 1 i,j s i,j λj X 2 i,j u i,j e X 3 i,j u i,j a X 4 i,j (11)
Furthermore, the transitivity property

r i,k + r k,j -1 ≤ r i,j , ∀ i = j = k. ( 12
)
can be easily be encoded by noting that r i,j = X 1 i,j + X 4 i,j

and r i,j = X 2 j,i + X 4 j,i if i < j and j < i, respectively.

Altogether, the most probable preorder R * ∈ R is determined by X * = (X 1 i,j , . . . , X 4 i,j ) i,j , which is the solution of the following optimization problem:

max i<j X 1 i,j ln s i,j λi + X 2 i,j ln s i,j λj (13) + X 3 i,j ln u i,j e + X 4 i,j ln u i,j a s.t. 4 l=1 X l i,j = 1, ∀ 1 ≤ i < j ≤ M , X 1 i,j , X 2 i,j , X 3 i,j , X 4 i,j ∈ {0, 1}, ∀ 1 ≤ i < j ≤ M , r i,k + r k,j -1 ≤ r i,j , ∀ i = j = k .
Note that if u i,j e = 0 for all pairs, then the solution will be a complete preorder between class probabilities, which is consistent with our interpretation. Similarly, if u i,j a = 0 and u i,j e = 0 for all pairs, we would obtain a linear ordering, as in [START_REF] Cheng | Probability estimation for multi-class classification based on label ranking[END_REF].

Obtaining Credible Sets from R *

Consider the preorder R * = R * (x) for an unlabelled query instance x, and suppose we seek a set-valued prediction Y (x) ⊆ Ω. A reasonable way to obtain such a prediction is to collect all non-dominated classes, i.e., to exclude only those classes λ j for which λ i R * λ j for at least one competing class λ i . A class label of that kind can be seen as a potentially optimal prediction for x. Adopting the above notation, the set-valued prediction can also be determined as

Y (x) = λ i ∈ Ω j<i X 1 j,i + i<j X 2 i,j = 0 , (14)
which means that it can immediately be derived from the solution of (13). Note that full uncertainty, i.e, Y (x) = Ω, only occur if all pairs (λ i , λ j ) are incomparable or indifferent.

How to obtain a set-valued prediction from the pairwise information is illustrated in the following example. Example 1 Assume that we have the output space Ω = {λ 1 , . . . , λ 5 } and pairwise information (8) for an unlabelled instance x given by the following quadruples: I 1,2 (x) = (0, 0.1, 0.6, 0.3), I 1,3 (x) = (0.6, 0, 0.1, 0.2), I 1,4 (x) = (0.9, 0, 0.1, 0), I 1,5 (x) = (0.4, 0, 0.3, 0.3), I 2,3 (x) = (0.6, 0, 0.2, 0.2), I 2,4 (x) = (0.7, 0, 0, 0.3), I 2,5 (x) = (0.9, 0, 0, 0.1), I 3,4 (x) = (0.6, 0, 0.2, 0.2), I 3,5 (x) = (0.9, 0, 0.1, 0), I 4,5 (x) = (0.05, 0.05, 0.4, 0.5).

Solving the optimization problem (13) gives the most probable preorder R * pictured in Figure 1 with the corresponding value

X * s.t. X 3 1,2 = X 1 1,3 = X 1 2,3 = X 1 3,4 = X 1 3,5 = X 4 4,5 = 1. Finally, from (14) we get Y (x) = {1, 2}.

Instantiation for Logistic Regression

Our approach outlined so far needs to be instantiated with a concrete hypothesis space H, i.e., a class of binary models h used to derive plausibility degrees (4) and ( 5), and a related learning algorithm. Here, we present an efficient instantiation for logistic regression. In general, estimating (4) and ( 5) can be difficult, and may require the use of approximation techniques (e.g., by fitting a surrogate model for π H (h))

Recall that logistic regression assumes posterior probabilities to depend on feature vectors x = (x 1 , . . . , x d ) ∈ R d in the following way:

h(x) = p(1 | x) = exp β 0 + d i=1 β i x i 1 + exp β 0 + d i=1 β i x i (15)
This means that learning the model comes down to estimating a parameter vector β = (β 0 , . . . , β d ), which is commonly done through likelihood maximization [Czepiel, 2002]. To avoid numerical issues (e.g, having to deal with the exponential function for large β) when maximizing the target function, we employ L 2 regularization. The corresponding version of the log-likelihood function ( 16) is strictly concave [Rennie, 2005]:

l(β) = N n=1 y n β 0 + d i=1 β i x i n (16) - N n=1 ln 1 + exp β 0 + d i=1 β i x i n - γ 2 d i=0 β 2 i ,
where the regularization term γ will be fixed to 1.

We now focus on determining the degree of support (4) for the positive class, and then summarize the results for the negative class (which can be determined in a similar manner). Associating each hypothesis h ∈ H with a vector β ∈ R d+1 , the degree of support (4) can be rewritten as follows:

π(1 | x) = sup β∈R d+1 min π(β), 2h(x) -1 (17)
It is easy to see that the target function to be maximized in ( 17) is not necessarily concave. Therefore, we propose the following approach.

Let us first note that whenever h(x) < 0.5, we have 2h(x) -1 ≤ 0 and min π H (h), 2h(x) -1 ≤ 0. Thus the optimal value of the target function (4) can only be achieved for some hypotheses h such that h(x) ∈ [0.5, 1]. For a given value α ∈ [0.5, 1], the set of hypotheses h such that h(x) = α corresponds to the convex set

β α = β β 0 + d i=1 β i x i = ln α 1 -α . ( 18
)
The optimal value π * α (1 | x) that can be achieved within the region (18) can be determined as follows:

π * α (1 | x) = sup β∈β α min π(β), 2α -1 (19) = min sup β∈β α π(β), 2α -1
Thus, to find this value, we maximize the concave loglikelihood over a convex set:

β * α = arg sup β∈β α l(β) (20)
As the log-likelihood function ( 16) is concave and has second-order derivatives, we tackle the problem with a Newton-CG algorithm [Nocedal and Wright, 2006]. Furthermore, the optimization problem (20) can be solved using sequential least squares programming2 [START_REF] Philip | [END_REF]. Since regions defined in ( 18) are parallel hyperplanes, the solution of the optimization problem (4) can then be obatined by solving the following problem:

sup α∈[0.5,1) π * α (1|x) = sup α∈[0.5,1) min π(β * α ), 2α -1 (21)
Following a similar procedure, we can estimate the degree of support for the negative class (5) as follows:

sup α∈(0,0.5] π * α (0|x) = sup α∈(0,0.5] min π(β * α ), 1 -2α (22)
Note that limit cases α = 1 and α = 0 cannot be solved, since the region ( 18) is then not well-defined (as ln(∞) and ln(0) do not exist). For the purpose of practical implementation, we handle ( 21) by discretizing the interval over α. That is, we optimize the target function for a given number of values α ∈ [0.5, 1) and consider the solution corresponding to the α with the highest optimal value of the target function π * α (1 | x) as the maximum estimator. Similarly, ( 22) can be handled over the domain (0, 0.5]. In practice, we evaluate ( 21) and ( 22) on uniform discretizations of cardinality 50 of [0.5, 1) and (0, 0.5], respectively. We can further increase efficiency by avoiding computations for values of α for which we know that 2α -1 and 1 -2α are lower than the current highest support value given to class 1 and 0, respectively.

Related Work

In the literature, different approaches have been proposed to produce credible (set-valued) predictions in the setting of supervised learning.

In [START_REF] Coz | [END_REF], the authors proceed from standard probabilistic predictions, i.e., a probability distribution on the set of classes (conditioned on an instance x). To produce a set-valued prediction, they invoke the principle of expected cost minimization, where the underlying cost measure combines the precision and correctness of the prediction (based on the F-measure as a performance metric). As an advantage of this approach, note that it can be used with standard methods for probabilistic prediction. Closer to our approach are methods based on imprecise probabilities, such as [START_REF] Corani | [END_REF], which augment probabilistic predictions into probability intervals or sets of probabilities, the size of which reflects the lack of information (reflecting epistemic uncertainty). Similar to this are approaches based on confidence bands in calibration models, for instance [START_REF] Kull | Reliability maps: a tool to enhance probability estimates and improve classification accuracy[END_REF]Xu et al., 2016]. They usually control the amount of imprecision by adjusting some certain parameters, e.g., a confidence value.

Conformal prediction [Shafer and Vovk, 2008;Balasubramanian et al., 2014] is a generic approach to reliable (setvalued) prediction that combines ideas from probability theory (specifically the principle of exchangeability), statistics (hypothesis testing, order statistics), and algorithmic complexity. The basic version of conformal prediction is designed for sequential prediction in an online setting, and comes with certain correctness guarantees (predictions are correct with probability 1-, where is a confidence parameter). Roughly speaking, given an instance x, it assigns a non-conformity score to each candidate output. Then, considering each of these outcomes as a hypothesis, those outcomes for which the hypothesis can be rejected with high confidence are eliminated. The set-valued prediction is given by the set of those outcomes that cannot be rejected.

Experiments

This section presents first experimental results to assess the performance of our approach to reliable classification.

Data Sets and Experimental Setting

We perform experiments on 15 data sets from the UCI repository (cf. Table 1), following a 10 × 10-fold cross-validation procedure. We compare the performance of our method (referred to as PREORDER) with two competitors. To make the results as comparable as possible, these methods are also implemented with pairwise learning using logistic regression as base learner. Thus, they essentially only differ in how the pairwise information provided by logistic regression is turned into a (reliable) multi-class prediction.

• VOTE: The first method is based on aggregating pairwise predictions via standard voting, which is a common approach in LPC. However, instead of simple weighted voting, we apply the more sophisticated aggregation technique proposed in [START_REF] Hüllermeier | Combining predictions in pairwise classification: An optimal adaptive voting strategy and its relation to weighted voting[END_REF], which shows better performance. Note that, by predicting the winner of the voting procedure, this approach always produces a precise prediction. • NONDET: As a baseline for set-valued predictions, we use the approach of [START_REF] Coz | [END_REF], which has been shown to exhibit competitive performance in comparison to other imprecise prediction methods [Zaffalon et al., 2012]. Recall that this approach produces nondeterministic predictions from precise probabilistic assessments. This requires turning pairwise probability estimates into conditional probabilities (p(λ 1 | x), . . . , p(λ M | x)) on the classes, a problem known as pairwise coupling. To this end, we apply the δ 2 method, which performs best among those investigated in [Wu et al., 2004]. Evaluation metrics for assessing set-valued predictions have to balance correctness (the true class y is an element of the predicted set Y ) and precision (size of the predicted set) in an appropriate manner. For example, in [Zaffalon et al., 2012], the authors argue that using the simple discounted accuracy (1/|Y | if y ∈ Y and 0 otherwise) is equivalent to saying that producing a set-valued prediction is the same as choosing within this set (uniformly) at random. This means that the discounted accuracy does not reward any cautiousness. Also, it can be shown that minimizing the expected discounted accuracy in expectation would never lead to imprecise predictions [START_REF]The costs of indeterminacy: How to determine them[END_REF]. Here, we therefore adopt the average utility-discounted accuracy measure, which has been proposed and formally justified in [Zaffalon et al., 2012]:

u(y, Y ) =    0 if y / ∈ Y α |Y | - β |Y | 2 otherwise
More specifically, we use the measures u 65 with (α, β) = (1.6, 0.6) and u 80 with (α, β) = (2.2, 1.2). Note that, in the case of precise decisions, both u 65 and u 80 reduce to standard accuracy.

Experimental Results

The average performances in terms of the utility-discounted accuracies are shown in Table 2, with ranks in parenthesis (note that we provide one set of ranks for u 65 , and another one for u 80 ). Firstly, we notice that PREORDER yields the best average ranks over the 15 data sets, both for u 80 and u 65 . Furthermore, a Friedman test [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF] on the ranks yields p-values of 0.0003138 and 0.002319 for u 80 and u 65 , respectively, thus strongly suggesting performance differences between the algorithms. The Nemenyi post-hoc test (see Table 3) further indicates that PREORDER is significantly better than VOTE regarding u 80 and NONDET in the case of u 65 . Since u 80 rewards cautious predictions stronger than u 65 does, it is not surprising that indeterminate classifiers do better in this case. Yet, even when considering u 65 , PRE-ORDER remains competitive with VOTE. This suggests that it tends to be more precise than NONDET, while still accurately recognizing those instances for which we have to be cautious.

Ideally, an imprecise classifier should abstain (i.e., provide set-valued predictions) on difficult cases, on which the precise classifier is likely to fail [START_REF]Nested dichotomies with probability sets for multi-class classification[END_REF]. The goal of Figure 2(a,b) is to verify this ability. Figure 2(a) displays, for each data set, the percentage of times the true class is in the prediction of PREORDER, given the prediction was imprecise, versus the accuracy of VOTE on those instances. Figure 2(b) does the same for NONDET. Both imprecise classifiers achieve high percentages (> 80) of correct partial predictions, while the corresponding percentages of VOTE vary in a wider range. Also, the accuracy of the latter significantly drops on those instances (for example, the average accuracy for data set g is 50% in Table 2, but drops to less than 30% in Figure 2(a)), confirming that the imprecise classifiers do indeed abstain on difficult cases. Finally, note that the points in Figure 2(a) are a bit more to the left than those in Figure 2(b), again suggesting that PREORDER is doing slightly better in recognizing difficult instances than NONDET.

For the two imprecise classifiers, we also compare the average proportion of partial predictions and the average (normalized) size of the predictions when at least one method produces a partial prediction. Figures 2(c) and 2(d) indicate that NONDET produces more partial predictions of (slightly) larger size.

Conclusion

This paper introduces an approach to cautious inference and reliable prediction in multi-class classification. The basic idea is to provide predictions in the form of preorder relations, which allow for representing preferences for some candidate classes over others, as well as indifference and incomparability between them; the two latter relations are in direct correspondence with two types of uncertainty, aleatoric and epistemic. This can be seen as a sophisticated way of partial abstention, which generalizes set-valued predictions and classification with reject option. Technically, our approach combines reliable binary classification with pairwise decomposition and approximate inference over preorders.

Practically, by projecting to the set of maximal elements, we only used preorder predictions for the purpose of setvalued classification. Our experiments on this type of problem are quite promising and suggest that our method is highly competitive to existing approaches to reliable prediction.

In future work, we plan to exploit more of the potential of preorder predictions, and to use such predictions in other contexts and problem settings. In active learning, for example, preorder predictions may provide very useful information for guiding the selection of queries. Since our approach applies as soon as a likelihood is defined, we also plan to study its extension to other kinds of likelihood such as evidential ones [Denoeux, 2014].

  be given, and denote by D m = {x | (x, λ m ) ∈ D} the observations from class λ m .

Figure 1 :

 1 Figure 1: Preorder induced by Example 1 (strict preference symbolized by directed edge, indifference by undirected edge, incomparability by missing edge).

  Figure 2: (a) Correctness of the PREORDER in the case of abstention versus accuracy of the VOTE. (b) Correctness of the NON-DET in the case of abstention versus accuracy of the VOTE. (c) Proportion of partial predictions when at least one method produces a partial prediction. (d) Average normalized size of the predictions in such cases.

Table 1 :

 1 Data sets used in the experiments

	#	name	# instances # features # labels
	a	iris	150	4	3
	b	wine	178	13	3
	c	forest	198	27	4
	d	seeds	210	7	3
	e	glass	214	9	6
	f	ecoli	336	7	8
	g	libras	360	91	15
	h	dermatology	385	34	6
	i	vehicle	846	18	4
	j	vowel	990	10	11
	k	yeast	1484	8	12
	l	wine quality	1599	11	6
	m	optdigits	1797	64	10
	n	segment	2300	19	7
	o wall-following	5456	24	4

Table 2 :

 2 Average utility-discounted accuracies (%)

		VOTE	PREORDER	NONDET
	#	acc.	u 80	u 65	u 80	u 65
	a	84.33(3, 1) 90.45(1) 83.29(2) 86.71(2) 76.88(3)
	b	96.35(1, 1) 95.89(2) 93.18(2) 93.47(3) 88.92(3)
	c	89.76(2, 1) 92.15(1) 88.82(2) 88.49(3) 81.57(3)
	d	88.81(3, 1) 92.15(1) 88.16(2) 90.03(2) 83.60(3)
	e	47.14(3, 3) 67.32(1) 57.24(1) 65.03(2) 52.98(2)
	f	75.57(3, 1) 80.66(1) 75.25(2) 77.02(2) 68.89(3)
	g	50.50(3, 3) 70.51(1) 63.91(1) 62.50(2) 53.02(2)
	h 96.43(2, 2) 97.70(1) 96.46(1) 96.01(3) 93.38(3)
	i	63.99(3, 1) 71.07(1) 62.17(2) 68.92(2) 57.17(3)
	j	39.57(3, 2) 51.10(1) 42.57(1) 48.22(2) 37.27(3)
	k	49.35(3, 2) 60.60(2) 50.04(1) 60.84(1) 49.22(3)
	l	58.10(3, 3) 69.65(2) 59.92(1) 71.02(1) 59.16(2)
	m 96.37(3, 2) 97.67(1) 96.81(1) 96.85(2) 95.46(3)
	n 84.51(3, 3) 91.87(1) 89.16(1) 90.01(2) 85.49(2)
	o	68.69(3, 3) 76.42(2) 70.79(1) 77.34(1) 70.39(2)
	aver. (u 80 , u 65 ) u 80	u 65	u 80	u 65
	rank (2.73, 1.93) 1.27	1.40	2.00	2.67

Table 3 :

 3 Nemenyi post-hoc test: null hypothesis H0 and p-value

	#	H 0	u 80	u 65
	1 V = P 0.00017 0.3101
	2 V = N	0.11017	0.1102
	3 P = N	0.11017 0.0015

Technically, we assume that, for each x ∈ X , there are hypotheses h, h ∈ H such that h(x) ≥ 0.5 and h (x) ≤ 0.5, which implies π(1 | x) ≥ 0 and π(0 | x) ≥ 0.

For an implementation in Python, see https://docs. scipy.org/doc/scipy/reference/generated/ scipy.optimize.minimize.html

Acknowledgments

This work was carried out in the framework of Labex MS2T and UML-NET projects, funded by the French Government (Reference ANR-11-IDEX-0004-02, ANR-14-CE24-0026).


L Schiano

M Ottavi

F Lombardi

S Pontarelli

A Salsano

On the Analysis of Reed Solomon Coding for Resilience to Transient/Permanent Faults in Highly Reliable Memories

Keywords: High Reliability Systems, Reliability Evaluation, Reed-Solomon Codes, Scrubbing, Dynamic Redundancy

Single Event Upsets (SEU) as well as permanent faults can significantly affect the correct on-line operation of digital systems, such as memories and microprocessors; a memory can be made resilient to permanent and transient faults by using modular redundancy and coding. In this paper, different memory systems are compared: these systems utilize simplex and duplex arrangements with a combination of Reed Solomon coding and scrubbing. The memory systems and their operations are analyzed by novel Markov chains to characterize performance for dynamic reconfiguration as well as error detection and correction under the occurrence of permanent and transient faults. For a specific Reed Solomon code, the duplex arrangement allows to efficiently cope with the occurrence of permanent faults, while the use of scrubbing allows to cope with transient faults.

Introduction

A generic approach to fault tolerance is seldom very efficient due to the diversity of applications and requirements as well as innovations in technology. For example, magnetic tape recorders have been extensively used to store the large amount of data commonly generated by the on-board instrumentation of satellites. However, their mechanical and electro-mechanical parts have insufficient flexibility to attain fault tolerance and reliability for long-term space missions. Moreover, the rapid growth in capacity of semiconductor memories and their compact size have permitted the development of Solid State Mass Memories (SSMMs), which are preferred over tape recorders due to their higher reliability [START_REF] Cardarilli | Design of a fault tolerant solid state mass memory[END_REF]. However, the requirements of low latency, high throughput and large storage capacity of a SSMM may not be fully met by space certified components. Commercial Off The Shelf (COTS) offer better performance in terms of storage capacity, access speed and power consumption as compared with space-certified components. COTS however lacks resilience to both transient and permanent faults which commonly occur in a space environment. Memories are usually made fault tolerant by using a combination of Error Detection And Correction (EDAC) codes [START_REF] Blahut | Theory and Practice of Error Control Codes[END_REF], and system-level techniques (such as sparing and scrubbing [START_REF] Saleh | Reliability of scrubbing recovery-techniques for memory systems[END_REF] [START_REF] Yang | Reliability of semiconductor rams with softerror scrubbing techniques[END_REF]). An EDAC code improves both the reliability of the storage system and data integrity (i.e. the probability that data is correctly stored in memory over a specified period of time); in this paper a class of maximum distance separable EDAC codes (known as Reed-Solomon codes, RS) is used. RS codes have been widely employed for transmission and storage due to their flexibility in the choice of dataword and codeword lengths. Modular sparing has been shown to improve the reliability of a memory system by replacing faulty modules or units (mostly affected by permanent faults). Scrubbing [START_REF] Saleh | Reliability of scrubbing recovery-techniques for memory systems[END_REF] which basically consists of periodically reading the content of the memory and correcting possible errors, improves data integrity by reducing the catastrophic accumulation of multiple transient errors (such as SEUs). Hence, the reliability of a memory system using these techniques is closely related to the occurrence of permanent faults (e.g. stuck-at, coupling etc), while data integrity is mainly related to the occurrence of transient faults resulting in errors (e.g. SEU), which can modify the value of the stored data.

The goal of this paper is to propose different arrangements (simplex and duplex) for a memory system which utilizes RS codes as EDAC; the objectives are to achieve resilience to both transient and permanent faults and retaining data integrity. In particular, the duplication of the memory modules (duplex) allows to cope with the occurrence of permanent faults, while the RS coding and the periodic execution of scrubbing allow to reduce the impact of transient faults. The performance of these fault tolerant memory systems is evaluated in terms of Bit Error Rate (BER) by Markov modeling for on-line reconfiguration.

The paper is organized as follows: Section 2 outlines the basic principles of RS codes, while in Section 3 the description of a simplex and the proposed duplex systems are provided. Preliminaries are given in Section 4. Section 5 illustrates the modeling method for estimating data integrity in both the simplex and the proposed duplex systems. Finally, in Section 6 analysis and conclusions are provided.

Review of Reed Solomon Coding

Reed Solomon codes [START_REF] Blahut | Theory and Practice of Error Control Codes[END_REF] are widely used for both data transmission and storage systems. A RS(n,k) code [START_REF] Blahut | Theory and Practice of Error Control Codes[END_REF] is defined by the integer values of the two parameters n and k, where n denotes the number of symbols of m bits (with n ≤ 2 m -1) of a codeword and k denotes the number of symbols of the related dataword. A RS(n,k) code can correct up to 2er + re ≤ nk erroneous bits, where er is the number of erasures and re is the number of random errors. For data transmission, a random error occurs when a symbol of the received codeword differs from the transmitted symbol in an unknown location of the codeword. An erasure is said to occur when the channel-side information (available from the receiver) allows to locate the erroneous symbol in the codeword. For a memory system, the following assumptions are applicable: 1) Transient faults (e.g. SEU) can occur in an unknown location (bit) of a codeword, therefore they can be effectively considered as random errors.

2) Permanent faults (e.g. stuck-at 0/1) can be located using either self-checking circuits, or on-line testing; therefore, they can be effectively considered as erasures.

Locating a permanent fault is necessary to exploit the error correction capability of the RS codes. Until the permanent fault is located, the error correction algorithm assumes the erroneous behavior to be caused by a random error, thus degrading the overall error correction capability of the provided code. When the permanent fault is located, the capability of the RS code can be fully exploited. The location of permanent faults can be achieved using different methods as found in the technical literature. For example, a permanent fault in a memory chip can be detected by monitoring the quiescent supply current (I ddq ) [START_REF] Soden | Iddq testing for submicron cmos ic technology qualification[END_REF].

Furthermore, a technique known as scrubbing can be applied [START_REF] Saleh | Reliability of scrubbing recovery-techniques for memory systems[END_REF] to deal with the simulataneous presence (accumulation) of random errors in a codeword. Memory scrubbing basically consists of periodically reading a codeword, correcting the possible erroneous symbols and rewriting the corrected codeword to the same memory location. The usage of memory scrubbing must be carefully tuned to the system requirements as it also introduces some drawbacks. These are an increase of hardware overhead due to the necessary control circuitry, a reduction in memory availability during the scrubbing operations and an increase in power consumption.

Simplex and Duplex Configurations

In this paper two configurations for a memory system based on Reed-Solomon coding, are considered:

1) A simplex system makes use of a Reed-Solomon code and related co-decoder. In this configuration, n coded symbols are read by the decoder and k data symbols are provided as output. 2) A duplex system with RS coding is shown in Fig. 1. This is based on the duplication of the memory module with an arbiter as decision circuit. This circuit operates as follows: initially, it attempts to recover from possible erasures occurring in either of the two words. Once the location of the erasures is established by the self-checking hardware, the arbiter masks erasures (provided that they do not occur in the same symbols of the words in the two modules). Following this operation, the arbiter separately decodes the two words to detect errors and correct them. Due to the limited correction capability of the code, mis-correction (i.e. correcting the erroneous word with yet another erroneous codeword) may occur. A flag is set when a correction has been performed and completed. Next, the arbiter proceeds by comparing the two words.

-If no flag is set, then one of the two words is provided as output (no error/fault present).

-If the two words are equal and at least one flag is set, then one of the two words is provided as output; in this case, the right correction has been performed. Note that the case of simultaneous mis-corrections (i.e. erroneous corrections leading to the same incorrect codeword) is not considered (masking error) due to its unlikely occurrence.

-If the two words are different and one of the two flags is set, then the word corresponding to the reset flag is provided as output. In this case, a mis-correction has occurred in the word corresponding to the module with the set flag.

-If the two words are different and both flags are set, the arbiter does not provide an output. Due to the duplex operation, the arbiter is not capable to discriminate between a correction and a mis-correction.

Preliminaries

Initially, the following definitions are introduced. Definition: λ is the fault exposure (or rate) of a single flipped bit (this is also known as SEU rate on a single bit). Definition: λ e is the erasure exposure of a symbol. Definition: T sc denotes the scrubbing operation period. Definition: BER is the Bit Error Rate i.e. the number of bits with errors divided by the total number of bits that have been read over a given time period (in percentage).

The systems considered in this paper have been modeled using Markov chains, which are particularly suitable for BER evaluation [START_REF] Schiano | Markov models of fault-tolerant memory systems under seu[END_REF]. To limit the problem of state explosion associated with Markov models of large and complex systems, only a word of a memory module (and its corresponding copy in the other module in the case of the duplex system) has been considered. However, the extension by considering the whole memory (memories) is straightforward and does not affect the ultimate correctness of the proposed models.

The following possible system operations and events have been considered as causing transitions in the Markov state diagrams:

1)A random error (bit-flip due to SEU) may occur in a word. This event leads the system to move to a neighboring state in which the effect of the bit-flip is considered.

2)Erasures have been considered over the symbols of the memory word encoded by the Reed Solomon code. Erasures cause the system to move to a neighboring state.

3)A scrubbing operation leads the system to a state characterized by the same number of permanent faults and no transient fault.

The following additional assumptions are made: -When considering reliability, the inability to produce a correct output is considered to be a failure.

-Random errors on the same symbol are not considered.

-As in previous works in the technical literature, the arbiter (as decision circuit) is always assumed to be error-free (i.e. it is a hard core component).

Proposed Markov Models

Consider initially the simplex arrangement for the memory system, which has been introduced in [START_REF] Cardarilli | Data integrity evaluations of reed solomon codes for storage systems[END_REF]. The states S(er, re) of the Markov Chain (CTMC) can be uniquely identified by the values of er and re The initial state at T = 0 (or Good state) is denoted as G = S(0, 0); in this state er = re = 0. Similarly, the unrecoverable error state (or Fail state) F = S(er, re) is a state in which (er + 2 × re) > nk.

The Markovian model of a RS coded simplex memory system capable to correct up to t random errors (where t = n-k 2 ) is shown in Fig. 2. Further details can be found in [START_REF] Cardarilli | Data integrity evaluations of reed solomon codes for storage systems[END_REF].

Figure 2. Markov model of a RS coded simplex memory system

According to the definition of BER and by considering that P S(n) (t) is the time dependent solution of the Markov Chain (i.e., the probability of being in state S(n) at time t), the BER of the system at time t can be written as [START_REF] Cardarilli | Data integrity evaluations of reed solomon codes for storage systems[END_REF]: Consider next the duplex memory system with the RS code. Six different parameters, depending on the erasures and random errors occurred, can be considered to characterize each state; they are defined in Fig. 3, which shows two corresponding words in the replicated modules, as follows:

BER(t) = m × (n -k) k × P S(n) (t) (1
-X is the number of erasures on the same symbols in both words.

-Y is the number of erasures in symbols belonging to one of the two words, while the same symbol in the replicated module is error-free.

-e1,e2 are the number of random errors (bit-flips) in either of the two words (word 1 or word 2 respectively), but not in the same symbol of the other word.

ec is the number of random errors which have occurred in corresponding symbols of the two codewords (independently on the position of the bit-flip in the symbol itself).

b is the number of occurrences of an erasure and a random error in same symbols of the two replicated modules.

Figure 4. Generic state of duplex system

A state transition in the Markov chain model is caused both by events (i.e. random errors and erasures) and memory operations (scrubbing). Fig. 4 shows all possible transitions from a generic state due to erasures and random errors. Note that the occurrence of a transition must satisfy the boundary conditions for the correct capabilities of the code employed. Therefore, from a generic state (characterized by the 6-tuple (X, Y, b, e1, e2, ec)) the possible transitions due to erasures are to the following states:

• A is characterized by the 6-tuple (X + 1, Y -1, b, e1, e2, ec). Transitions to state A are caused by an erasure on a symbol for which the same symbol in the duplicated module already has an erasure (at a rate λ e • Y ).

• B is characterized by the 6-tuple (X + 1, Y, b -1, e1, e2, ec). Transitions to state B are caused by the occurrence of an erasure on a symbol already affected by a random error (bit-flip), and for which the same symbol in the duplicated module presents an erasure too. The transition rate is given by λ e • Y .

• C is characterized by the 6-tuple (X, Y + 1, b, e1, e2, ec). Transitions to state C are caused by the occurrence of an erasure on a symbol such that this symbol and the same symbol in the duplicated word were not previously affected by random error or erasures. The transition rate is λ e • (n -X -Yb -e1 -e2ec).

• D, E are characterized by the 6-tuples (X, Y +1, b, e1-1, e2, ec) and (X, Y +1, b, e1, e2-1, ec), respectively. If an erasure occurs to a word previously corrupted by a random error (and whose homologous is error-free) then the system enters the D or E state. The transition rate is given by λ e •e1 or λ e • e2, respectively.

• F is characterized by the 6-tuple (X, Y, b + 1, e1, e2, ec -1). A permanent fault occurring (with rate λ e • ec) to a symbol such that this symbol and the same symbol in the duplicated word were previously affected by random error takes the system to state F .

• G, H are characterized by the 6-tuples (X, Y, b+1, e1-1, e2, ec) and (X, Y, b + 1, e1, e2 -1, ec), respectively. The system enters these states at the occurrence of an erasure on a previously error-free symbol, whose same symbol is affected by a random error. Transitions to G or H are characterized by a rate λ e • e1 or λ e • e2 respectively.

Similarly, if the boundary conditions are satisfied, the random errors (SEU causing bit-flips) cause the system to move to the following states:

• I is characterized by the 6-tuple (X, Y -1, b + 1, e1, e2, ec). Transitions to state I occur with rate (m•λ•Y ), where m is the number of bits per symbol . They are caused by a random error occurring on a symbol, whose same symbol is affected by an erasure.

• L, M are characterized by the 6-tuples (X, Y, b, e1 + 1, e2, ec) and (X, Y, b, e1, e2 + 1, ec), respectively. Transitions to these states occur following a random error on a symbol whose same symbol is error-free. Their rate is given by λ

• m • (n -x -y -b -e1 -e2 -ec).
• N, O are characterized by the 6-tuples (X, Y, b, e1 -1, e2, ec + 1) and (X, Y, b, e1, e2 -1, ec + 1), respectively. The occurrence of a random error on a symbol whose same symbol is already affected by a random error causes a transition to one of these states. The rates of these transitions are m • λ • e1 and m • λ • e2 respectively.

As per the analysis of BER for data storage, two system operations have been considered, namely read and scrubbing. The ability of the system to provide a correct output as result of a read operation is limited on each module by the condition (2re + er) ≤ nk. In the proposed duplex system, prior to any reading/scrubbing an erasure recovery operation is performed; therefore, the total number of erasures er is X while erasures on only one of the two homologous symbols (Y ) can thus be masked by the arbiter. As for the total random errors on each word, re is given by the sum of b, ec, and e1 or e2 respectively. Eventually all possible transitions shown in Fig. 4 may occur to characterize the next system configuration. However, either of the following conditions must be satisfied:

X + 2b + 2ec + 2e1 ≤ n -k X + 2b + 2ec + 2e2 ≤ n -k
Otherwise, the system reaches an unrecoverable error state (or Fail state). Read operations are not explicitly considered in the proposed model: a read operation corresponds to the so-called stopping time of a performed simulation. If the system is then in the Fail state, the read operation is unsuccessful. Else, a correct output is provided.

Similarly, a scrubbing operation is not successful when it is performed from a state which does not satisfy the boundary conditions, leading the system to the Fail state. Otherwise, a scrubbing operation causes a transition to a state characterized by the same number of permanent faults and no random error (thus to a state characterized by the 6-tuple (X, Y + b, 0, 0, 0, 0)). Scrubbing is executed at a prescribed frequency characterized by a rate 1 Tsc .

Analysis and Discussion

The solution and evaluation in terms of BER(t) of the proposed Markov models have been accomplished by using the SURE solver [START_REF] Butler | [END_REF]. In the evaluation, rates for transient fault were varied from 7.3 × 10 -7 errors/bit/day to a maximum of 1.7×10 -5 . As the rate of permanent faults depends on the reliability of the memory chips, then it can be established using for example the models of [START_REF] Cardarilli | Design of a fault tolerant solid state mass memory[END_REF], [1].

In particular, the following three cases are considered: 1) comparison of simplex and duplex RS(18,16) with no scrubbing and variable SEU rate; 2) analysis of duplex RS(18,16) for different T sc periods and under the worst case scenario of the SEU rate; 3) comparison of simplex and duplex RS(18,16), and simplex RS(18,16) under different rates for permanent faults.

For cases 1) and 2), it is assumed that data is stored in the memory for 2 days (T st = 48h); therefore BER has been calculated during this time interval. The first evaluation has been performed on the simplex and duplex systems with RS(18,16) without scrubbing, no permanent fault and at a rate for transient faults given by λ ∈ [7.3 × 10 -7 , 1.7 × 10 -5 ]. The BERs of the two systems are reported in Figure 5 and Figure 6; the values for the BER are in the same range for all considered transient fault rates (of course, the duplex arrangement is expected to be particularly resilient to permanent faults, as also shown later in this section). As for the duplex configuration, Figure 7 shows the improvement in BER due to scrubbing. For this example a worst case transient faults scenario has been considered by setting λ = 1.7 × 10 -5 . Using a duplex system with the RS(18,16) code, a scrubbing frequency of lower than once per hour is sufficient to maintain the BER below 10 -6 . This confirms previous results [START_REF] Cardarilli | Data integrity evaluations of reed solomon codes for storage systems[END_REF] on the simplex memory system using different RS codes. Note that a RS(18,16) code in a duplex memory system implies the same amount of redundant code symbols as in a simplex system with a RS(36,16) code. Therefore, also this case is considered. Figures 8,9, and 10 show the comparison of the RS(18,16) simplex, duplex and RS(36,16) simplex. These three cases are considered for the occurrence of permanent faults (over a period of 24 months for permanent storage of data in the memory). The RS(18,16) duplex has significantly better performance than the simplex memory, but it shows a degradation in performance compared with a simplex system employing a RS(36,16) code.

Consider next the decoder complexity. The time for Reed Solomon decoding (T d ) depends on the codeword length and on the number of code symbols as T d 3n + 10(nk); this complexity has been reported in [START_REF]Reed Solomon Compiler user guide[END_REF] for the performance of a RS codec IP core for FPGA implementation. The value of T d is in clock cycles for performing the decoding operation on a non time-continuous access profile as applicable to memory. Therefore, for a RS (36,16) decoder T d 108 + 200 = 308 while for a RS (18,16) T d 54 + 20 = 74, i.e. the decoding access time to the stored data is more than four times higher using the RS (36,16) arrangement than the simplex or duplex RS (18,16).

A further metric that has been evaluated, is the area of the decoder. The number of logic gates required for implementing a Reed Solomon decoder, is almost linearly dependent on m and the number of check symbols nk [START_REF]Reed Solomon Compiler user guide[END_REF]; therefore, a single RS(36,16) decoder will require more area than two RS(18,16) decoders for the duplex arrangement. The increase in area must be carefully evaluated when the physical constraints on electronic equipment are very tight; moreover, a substantial increase in decoder area also implies an increase in the non-fault tolerant components, thus ultimately degrading the overall reliability of the system. In conclusion, the novel Markov models presented in this paper have analytically shown that Reed Solomon codes can be efficiently employed in high reliable memory systems; albeit ultimately application dependent, redundancy and coding can be combined to attain data integrity and resilience to errors due to transient (SEU) and permanent faults. Different figures of merit such as BER and decoding complexity (in time and area) have been analyzed in depth. The proposed models have provided an accurate and flexible evaluation tool which can be used to assess the viability of SSMMs for long mission time in space exploration.

Figure 1 .

 1 Figure 1. Duplex system block diagram

)Figure 3 .

 3 Figure 3. State definition in the Markov chain

  x-y-b-e1-e2-ec) m

Figure 5 .Figure 6 .

 56 Figure 5. BER of simplex RS(18,16) under different SEU rates

Figure 7 .

 7 Figure 7. BER of duplex RS(18,16), fixed transient fault rate, variable scrubbing period

Figure 8 .Figure 9 .

 89 Figure 8. BER of simplex RS(18,16), different permanent fault rates, with no scrubbing.

Figure 10 .

 10 Figure 10. BER of simplex RS(36,16), different permanent fault rates, with no scrubbing.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Marianna Marino
email: marianna.marino@icn-groupe.fr.

Pierpaolo Parrotta
email: p.parrotta@maastrichtuniversity.nl.

Self-employment: Does parental cultural diversity matter?

Keywords: JEL Classification: L26, J21, D10 Parents' cultural diversity; self-employment experience

We find evidence that parents with different cultural background favour self-employment experiences of their children. The effect of parental cultural diversity turns out to be stronger for children with no siblings or having at least a parent with universitary degree.

Introduction

Economists have long examined the links between family background and labour market outcomes, such as earnings, intergenerational mobility and various occupation-related characteristics, including eventual self-employment status. Models have demonstrated that parental resources are a crucial factor that affect individuals' economic opportunities by influencing parents' decisions regarding investments in the human capital of their offspring (e.g., [START_REF] Becker | Human capital and the rise and fall of families[END_REF][START_REF] Haveman | The determinants of children attainments: A review of methods and findings[END_REF]. Indeed, an individual's ability to identify and exploit opportunities within business environments is substantially influenced by knowledge developed through both educational and professional experiences [START_REF] Lazear | Balanced Skills and Entrepreneurship[END_REF].

In addition to human capital investments, factors such as family structure, father's self-employment status and ethnicity appear to substantially affect the probability that an individual will be self-employed (see, e.g., [START_REF] Hout | Self-Employment, Family Background, and Race[END_REF]. Several empirical studies have suggested that after controlling for a number of parental characteristics, such as age, education, occupation, earnings, family ties, siblings and culture, children raised by parents who are self-employed are more likely to start a new business than children raised by parents who are not self-employed (see [START_REF] Dunn | Financial Capital, Human Capital, and the Transition to Self-Employment: Evidence from Intergenerational Links[END_REF].

However, existing studies have not explored whether individuals' self-employment decisions are linked to their parents' cultural diversity. Our objective is to fill this gap in the literature. Family experiences are frequently the source of an individual's first authentic exposure to a culturally heterogeneous (learning)

environment. An important question to address is whether this type of exposure promotes characteristics relevant to entrepreneurs, such as the balanced accumulation of knowledge and skills across different fields of expertise [START_REF] Lazear | Balanced Skills and Entrepreneurship[END_REF] and the development of creativity and a broad spectrum of perspectives [START_REF] Hong | Problem Solving by Heterogeneous Agents[END_REF]. Furthermore, by distinguishing among a number of characteristics of parents and their offspring, we clarify how individuals' self-employment experiences are affected by the cultural diversity of their parents.

The remainder of this paper is structured as follows: data; estimation strategy; results; and conclusions.

Data

We retrieve valuable information regarding individuals and their families between 1980 and 2006 from the Danish "Integrated Database for Labour Market Research." Our final sample consists of one observation for each second-generation immigrant observed during the sample period. The focus on second-generation immigrants is grounded on the fact that these immigrants represent a relatively homogeneous group of individuals who markedly differ from Danish natives (individuals with at least one Danish parent). This 1 sampling choice allows us to disentangle the influence of parental cultural diversity from effects that arise because a parent's Danish roots have led to the greater integration of an individual into Danish society.

In our data, we identify the following characteristics for each examined individual: (i) mother's and father's country of origin; (ii) gender and year of birth; (iii) place of residence (municipality); (iv) educational status, which was classified into three educational levels (basic, secondary and tertiary) and five fields of university degrees (engineering, humanities, medicine, social sciences and natural sciences, accounting for degrees at the bachelor's level or beyond); (v) parents' self-employment experience; and (vi) labour market status (unemployed or employed) prior to an eventual transition to self-employment. Furthermore, we define 34 language groups1 and 16 area groups2 used to determine parents' cultural diversity (a dummy variable) by categorizing the countries of origin of the parents of examined individuals based on information from the "Ethnologue: Languages of the World" language encyclopedia and the United Nations "Standard Country or Area Codes for Statistical Use" country classification system, respectively. Thus, we use the geographical area and main language3 of parents' countries of origin as proxies for parents' cultural backgrounds. Information regarding the characteristics of the examined individuals and their parents refers to the year before an individual is randomly selected or becomes self-employed.

Descriptive statistics are reported in Table 1. The final sample consists of 83,915 subjects. Statistical analysis indicated that 8.8 % of the examined individuals have experienced at least one transition to self-employment; 5.4 % (3 %) of the examined individuals have parents belonging to different language (geographical) categories; 47.7 % of the examined individuals are female; 28.6 % of the examined individuals are firstborn children; and only 6.9 % (4.7 %) of the examined individuals had obtained a university (secondary) degree. The correlation between the two variables of interest that indicate the cultural diversity of a subject's parents is approximately 75.7 % and is highly significant. Differences in mean values between individuals with and without self-employment experiences are statistically significant, too. However, these differences do not indicate the expected signs of the estimates because in our regression models we control for further variables like father's and mather's language or geographical group dummies.

Estimation strategy

We utilize a linear probability model (henceforth LPM) to investigate whether the cultural diversity of an individual's parents affects this individual's propensity to become self-employed. In this model, the dependent variable indicating whether a worker experiences self-employment is regressed on the aforementioned variables of interest, with a set of standard controls (dummies for birth year, firstborn child status, femaleness, education level, the field of an eventual university degree, municipality of residence, and each parent's language or area of provenience groups). The standard errors of this model are corrected for heteroskedasticity and clustered by family identifier.

Results

Table 2 reports results obtained for the entire sample and for sub-samples separated by parental characteristics when the aforementioned language categories are used to describe the diversity in the cultural backgrounds of subjects' parents. The first two columns, which provide estimates for the full sample, indicate the positive and significant effect of our key variable. In particular, it appears that culturally diverse parents increase the likelihood that an individual will become self-employed by approximately 1 %. This effect enlarges for "only children" (1.5 %) and for subjects "with at least one parent with a university degree" (3 %) but diminishes to insignificance in both complementary cases. This finding is unsurprising because both the absence of siblings and the presence of a highly educated parent can mitigate the impact of financial constraints. Estimates for the parameter of interest in the full sample appear to mainly reflect contributions from "males" and individuals who are "lower than tertiary" in educational level (see Table 3). In Tables 4 and5, the variable of interest is determined based on the aforementioned geographical categories, and all regressions utilize the specifications and sub-sampling criteria of Tables 3 and4, respectively. Examinations of Tables 4 and5 produce findings that are qualitatively similar to the results discussed above, indicating that the results of this study are not sensitive to the measure of cultural diversity that is utilized. Finally, crucial checks are performed in Table 6. In particular, in columns ( 1) and ( 5), we exclude transitions from unemployment to self-employment to ensure that we are evaluating the effect of interest in the context of true entrepreneurial behavior rather than choices that reflect desire to escape unemployment (i.e., perceptions of poor employability). In columns [START_REF] Dunn | Financial Capital, Human Capital, and the Transition to Self-Employment: Evidence from Intergenerational Links[END_REF] and ( 6), we verify that individuals' self-employment decisions are not simply driven by the self-employment experiences of their parents by excluding individuals with at least one parent with self-employment experience from the analyses. Columns ( 3) and [START_REF] Marino | Does labour Diversity Promote Entrepreneurship[END_REF], and ( 4) and ( 8) report estimates of Probit and Logit regressions, respectively. Probit and Logit estimates of the parameter of interest are significant and greater than those discussed in the main analysis, indicating thus that LPM estimates represent lower-bound results. These robustness checks produce results consistent with our main findings and therefore support the conclusion that parental cultural diversity positively affects individuals' self-employment choices.

(2) Note: Full sample: ( 1) and ( 2); only child: ( 3) and ( 4); with siblings: ( 5) and ( 6); a parent with universitary degree: ( 7) and ( 8); both parents with lower than tertiary education: ( 9) and ( 10). Family controls include father's and mather's language group dummies. The set of individual controls includes the control variables reported in the table and dummies for birth year and municipality of residence. Significance levels: ***1%, **5%, *10%.

(3) (4) (5) (6) (7)
(2)

(3) Note: Male: ( 1) and ( 2); female: (3) and ( 4); with universitary degree: ( 5) and ( 6), with lower than tertiary education: ( 7) and ( 8).

(4) (5) (6) (7)
Family controls include father's and mather's language group dummies. The set of individual controls includes the control variables reported in the table and dummies for birth year and municipality of residence. Significance levels: ***1%, **5%, *10%.

iii Table 4: Results, full sample and by parents' characteristics (geographical categories) Note: Full sample: ( 1) and ( 2); only child: (3) and ( 4); with siblings: ( 5) and ( 6); a parent with universitary degree: ( 7) and ( 8); both parents with lower than tertiary education: (9) and (10). Family controls include father's and mather's geographical group dummies. The set of individual controls includes the control variables reported in the table and dummies for birth year and municipality of residence. Significance levels: ***1%, **5%, *10%.

(2)

(5) Note: Male: ( 1) and ( 2); female: (3) and ( 4); with universitary degree: ( 5) and ( 6), with lower than tertiary education: [START_REF] Marino | Does labour Diversity Promote Entrepreneurship[END_REF] and [START_REF] Parrotta | The Nexus between labour Diversity and Firm's Innovation? Forthcoming in the Journal of Population Economics. Linguistic groups: Germanic West[END_REF]

(5) Note: Parents with no self-employment experience: (1) and ( 5); only transitions from employment: ( 2) and ( 6); Probit: ( 3) and ( 7); Logit: ( 4) and [START_REF] Parrotta | The Nexus between labour Diversity and Firm's Innovation? Forthcoming in the Journal of Population Economics. Linguistic groups: Germanic West[END_REF]. Family controls include father's and mather's geographical or language group dummies, alternatively. The set of individual controls includes the control variables reported in the table and dummies for birth year and municipality of residence. Significance levels: ***1%, **5%, *10%.

(6) (7)
vi

Table 1 :

 1 Descriptive Statistics

	Self-employed Non self-employed
	All

Note:

The correlation between the two alternative variables of interest is 0.7569 with significance level at 1 %. i

Table 2 :

 2 Results, full sample and by parents' characteristics (language categories)

Table 3 :

 3 Results, by own characteristics (language categories)

Table 5 :

 5 Results, by own characteristics (geographical categories)

Table 6 :

 6 . Family controls include father's and mather's geographical group dummies. The set of individual controls includes the control variables reported in the table and dummies for birth year and municipality of residence. Significance levels: ***1%, **5%, *10%. Robustness checks

	Geographical categories
	Language categories
	(1)

v

Please see the Appendix for additional information regarding the language categories.

The geographical groups are Oceania, Northern America, Southern America, Central America, Northern Europe, Southern Europe, Eastern Europe, Western Europe, Northern Africa, Southern Africa, Eastern Africa, Western Africa, Central Asia, South Asia, Western Asia, and Eastern Asia. For more details, please consult the following website: http://unstats.un.org/unsd/methods/m49/m49.htm.

See Parrotta et al. (2013) and[START_REF] Marino | Does labour Diversity Promote Entrepreneurship[END_REF].

Analyses of a sample of second-generation immigrants in Denmark from the 1980-2006 time period reveal evidence that parental cultural diversity influences individuals' self-employment experiences. Exposure to greater cultural diversity positively affects entrepreneurship and appears to promote the creativity and knowledge accumulation required to start a business. Specifically, we find that culturally diverse parents increase the likelihood that an individual will become self-employed by approximately 1 %. The effect of interest appears to be stronger among individuals who have no siblings or at least one parent with a university degree.

Acknowledgments

We thank Tomaso Duso, Dominique Foray, Dario Pozzoli for their valuable comments and suggestions.