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

1 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. [Senge et al., 2014] 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 [Senge et al., 2014], which we lift from binary to multi-class classification using appropriate decomposition techniques [Bishop, 2006; H¨ullermeier and Brinker, 2007]. 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 [Masson et al., 2016] 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.

2 Epistemic and Aleatoric Uncertainty

A main building block of our method is the assessment of the epistemic and aleatoric uncertainty involved in the discrimination between a pair of classes. To this end, we are going to adopt the formal model proposed in [Senge et al., 2014], 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 ph(1 | x) = h(x) and ph(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 = {(xi, yi)}Ni=1 ⊂ X ×Ω, the normalized likelihood of a model h is defined as

where L(h) = ∏Ni=1 ph(yi | x) is the likelihood of h, and hml ∈ 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:

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:

Given the above degrees of support, the degrees of epistemic uncertainty ue and aleatoric uncertainty ua are defined as follows:

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 s1(x) and s0(x) of (strict) preference in favor of the positive and negative class, respectively:

1 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.

With an analogous definition for s0(x), we have s0(x) + s1(x) + ua(x) + ue(x) ≡ 1. In addition to defining a partition of unity, the quadruple (s1(x), s0(x), ue(x), ua(x)) has the following properties:

• s1(x) (s0(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;
• ue(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;
• ua(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.

3 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.

3.1 Learning by Pairwise Comparison

In the multi-class setting, we are dealing with a set of M > 2 classes Ω = {λ1, . . . , λM}. Suppose a set of training data D = {(xn, yn)}Nn=1 ⊂ X × Ω to be given, and denote by Dm = {x | (x, λm) ∈ D} the observations from class λm.

Learning by pairwise comparison (LPC) a.k.a. all-pairs is a decomposition technique that trains one (binary) classifier hi,j for each pair of classes (λi, λj), 1 ≤ i < j ≤ M [F¨urnkranz, 2002]. The task of hi,j, which is trained on Di,j = Di ∪Dj, 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

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:

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.

3.2 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:

where ri,j = 1 if (λi, λj) ∈ R and ri,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 si,j λi , si,j λj , ui,j a , and ui,j e , respectively. Then, making a simplifying assumption of independence, the probability of ending up with R is given as follows:

The most probable preorder R∗ then corresponds to

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:

Then, by adding the constraints ∑4l=1 Xl i,j = 1 and Xl i,j ∈ {0, 1}, we can rewrite the probability (9) as follows:

Furthermore, the transitivity property

can be easily be encoded by noting that ri,j = X1 i,j + X4 i,j and ri,j = X2 j,i + X4 j,i if i < j and j < i, respectively.

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

Note that if ui,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 ui,j a = 0 and ui,j e = 0 for all pairs, we would obtain a linear ordering, as in [Cheng and H¨ullermeier, 2012].

3.3 Obtaining Credible Sets fromR∗

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

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:

Solving the optimization problem (13) gives the most probable preorder R∗ pictured in Figure 1 with the corresponding value X∗ s.t. X3 1,2 = X1 1,3 = X1 2,3 = X1 3,4 = X1 3,5 = X4 4,5 = 1. Finally, from (14) we get Y (x) = {1, 2}.

4 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 = (x1 , . . . , xd ) ∈ Rd in the following way:

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 L2 regularization. The corresponding version of the log-likelihood function (16) is strictly concave [Rennie, 2005]:

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 β ∈ Rd+1 , the degree of support (4) can be rewritten as follows:

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

The optimal value π∗α(1 | x) that can be achieved within the region (18) can be determined as follows:

Thus, to find this value, we maximize the concave loglikelihood over a convex set:

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 programming 2 [Philip and Elizabeth, 2010]. Since regions defined in (18) are parallel hyperplanes, the solution of the optimization problem (4) can then be obatined by solving the following problem:

Following a similar procedure, we can estimate the degree of support for the negative class (5) as follows:

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.

5 RelatedWork

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

In [Coz et al., 2009], 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.

2 For an implementation in Python, see https://docs.

scipy.org/doc/scipy/reference/generated/ scipy.optimize.minimize.html

Closer to our approach are methods based on imprecise probabilities, such as [Corani et al., 2014], 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 [Kull and Flach, 2014; 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.

6 Experiments

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

6.1 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 [H¨ullermeier and Vanderlooy, 2010], 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 [Coz et al., 2009], 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 [Yang et al., 2017]. Here, we therefore adopt the average utility-discounted accuracy measure, which has been proposed and formally justified in [Zaffalon et al., 2012]:

More specifically, we use the measures u65 with (α, β) = (1.6, 0.6) and u80 with (α, β) = (2.2, 1.2). Note that, in the case of precise decisions, both u65 and u80 reduce to standard accuracy.

6.2 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 u65, and another one for u80). Firstly, we notice that PREORDER yields the best average ranks over the 15 data sets, both for u80 and u65. Furthermore, a Friedman test [Demˇsar, 2006] on the ranks yields p-values of 0.0003138 and 0.002319 for u80 and u65, 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 u80 and NONDET in the case of u65. Since u80 rewards cautious predictions stronger than u65 does, it is not surprising that indeterminate classifiers do better in this case. Yet, even when considering u65, PREORDER 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 [Yang et al., 2014]. 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.

7 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].

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), and was partially supported by the German Research Foundation (DFG, SFB 901).