Conformal Credal Self-Supervised Learning

In semi-supervised learning, the paradigm of self-training refers to the idea of learning from pseudo-labels suggested by the learner itself. Across various domains, corresponding methods have proven effective and achieve state-of-the-art performance. However, pseudo-labels typically stem from ad-hoc heuristics, relying on the quality of the predictions though without guaranteeing their validity. One such method, so-called credal self-supervised learning, maintains pseudo-supervision in the form of sets of (instead of single) probability distributions over labels, thereby allowing for a flexible yet uncertainty-aware labeling. Again, however, there is no justification beyond empirical effectiveness. To address this deficiency, we make use of conformal prediction, an approach that comes with guarantees on the validity of set-valued predictions. As a result, the construction of credal sets of labels is supported by a rigorous theoretical foundation, leading to better calibrated and less error-prone supervision for unlabeled data. Along with this, we present effective algorithms for learning from credal self-supervision. An empirical study demonstrates excellent calibration properties of the pseudo-supervision, as well as the competitiveness of our method on several benchmark datasets.


Introduction
In the recent years, machine learning applications, particularly deep learning models, have benefited greatly from the extensive amount of available data. While traditional supervised learning methods commonly rely on curated, precise target information, there is an essentially unlimited availability of unlabeled data. Semi-supervised learning [14] aims to leverage this source of information for further optimizing models, as successfully demonstrated by a wide range of algorithms [6,7,60,67]. Among other approaches, so-called self-training [38] emerged as a simple yet effective paradigm to facilitate learning from additional unlabeled data. To this end, the model to be trained is used to predict "pseudo-labels" for the unlabeled data, which are then added to the labeled training data.
When learning probabilistic classifiers, pseudo-labels can come in different forms. Traditionally, such supervision is typically in the form of a probability distribution, either degenerate ("one-hot" encoded, hard) [38,60] or non-degenerate (soft) [6,7]. As pointed out by Lienen and Hüllemeier [43], this form can be questioned from a data modeling perspective: Not only is a single distribution unlikely to match the true ground-truth, and may hence to bias the learner, but also incapable of expressing uncertainty about the ground-truth distribution. While uncertainty-aware approaches address these shortcomings by accompanying the targets with additional qualitative information (e.g., as in [55]), so-called credal self-supervised learning (CSSL) [42] replaces the targets by credal sets, i.e., sets of probability distributions assumed to guarantee (or at least likely) covering the true distribution. Such set-valued targets, for which CSSL employs a generalized risk minimization to enable learning, relieve the learner from committing to a single distribution, while facilitating uncertainty-awareness through increased expressivity.
Although all of the aforementioned approaches have demonstrated their effectiveness to the problem of semi-supervised learning, none of them entails meaningful guarantees about the validity of the pseudo-labels -their quality is solely subject to the model confidence itself without an objective error probability. Moreover, rather ad-hoc heuristics are considered to control the influence of vague beliefs on the learning process (e.g., by selecting pseudo-labels surpassing a confidence threshold). For instance, CSSL derives credal pseudo-supervision based on the predicted probability scores. Although it exhibits uncertainty-awareness by using entropy minimization (less entropy results in smaller sets), this may be misleading for overconfident yet poorly generalizing models. Again, no objective guarantee can be given for the validity of the credal set. This raises the quest for a pseudolabeling procedure providing exactly that kind of guarantee, i.e., validating pseudo-supervision beyond mere empirical effectiveness.
Fortunately, the framework of conformal prediction (CP) [59,66] provides a tool-set to satisfy such demands. As such, CP induces prediction regions quantifying the uncertainty for candidate values as outcome for a query instance by measuring their non-conformity ("strangeness") with previously observed data with known outcomes. Much like in classical hypothesis testing, it computes p-values for candidate outcomes (e.g., for each class y ) as a criterion for hypothesis rejection, i.e., whether to include a value y in the prediction set with a certain amount of confidence. Based on very mild technical assumptions, CP provides formal guarantees for the validity of prediction regions and is able to control the probability of an invalid prediction (not covering the true label).
In our work, we combine the technique of inductive conformal prediction, an efficient variant of CP, with the idea of credal self-supervised learning, leading to a method we dub conformal credal self-supervised learning (C 2 S 2 L). Instead of deriving credal sets based on an ad-hoc estimate of the model confidence, we proceed from a possibilistic interpretation of conformal predictions [13] to construct conformal credal labels. By this, pseudo-labels of that kind provide the validity guarantees implied by conformal predictors, laying a rigorous theoretical foundation for a set-valued pseudolabeling strategy. To enable learning from conformal credal self-supervision, we further provide an effective algorithmic solution for generalized empirical risk minimization on set-valued targets. An exhaustive empirical study on several benchmark datasets demonstrates the usefulness of our method for effective and reliable semi-supervised learning -leveraging well calibrated pseudo-supervision, it is shown to improve the state-of-the-art in terms of generalization performance.

Related Work
Semi-supervised learning describes the learning paradigm where the aim is to leverage the potential of unlabeled in addition to labeled data to improve learning and generalization. As it is easy to lose track of related work due to the wide range of proposed approaches in the recent years, we focus here on classification methods that are closely related to our work. For a more comprehensive overview, we refer to [14] and [64]. Nowadays, so-called self-training (or self-supervised) methods protrude among these methods by providing a simple yet effective learning methodology to make use of unlabeled data. Such methods can be found in a wide range of domains, including natural language processing [22] and computer vision [21,27,56,68]. As self-training can be considered as a general learning paradigm, where a model suggests itself labels to learn from, it has been wrapped around various model types, e.g., support vector machines [44], decision trees [62] and most prominently with neural networks [50]. Notably, it lays the foundation for so-called distillation models, e.g., in self-distillation [35] or studentteacher setups [53,68]. It is further popular for unsupervised pretraining, e.g., as described in [11,28].
Uncertainty-awareness [31] is a critical aspect for a cautious pseudo label selection to learn from, without exposing the model to the risk of confirmation biases [1]. This aspect has been considered in previous works by different means. [55] employs Bayesian sampling techniques, such as MC-Dropout [25] or DropBlock [26], to estimate uncertainty of a prediction, which is then used as an additional filter criterion. [54] uses an adaptive instance weighting approach to control the influence of individual pseudo labels. Moreover, credal self-supervised learning [42] expresses certainty by the size of maintained credal sets as pseudo-supervision. Also, learning from softened probability distribution can also be considered as a way to suppress overconfidence tendencies to learn in a more cautious way [1,7]. Lastly, several domain-specific adaptions have been proposed, e.g., for text classification [46] or semantic segmentation [73].
As prominently used throughout this work, conformal prediction [4,59,66] provides an elegant framework to naturally express model prediction uncertainty in a set-valued form. We refer the interested reader to [71] for a more comprehensive overview beyond the covered literature here. Whereas conformal prediction initially proceeded from a transductive form in an online setting [66], its high complexity called for more efficient variants. To this end, several variations have been proposed, where inductive conformal prediction [52] most prominently draw attention by assuming a separated calibration split available used for non-conformity measurement. Beyond this, several alternative approaches varying data assumption or algorithmic improvements have been proposed (e.g., as described in [34,39]). Recently, Cella and Martin [12, 13] suggest a reinterpretation of conformal transducer as plausibility contours, allowing to derive validity guarantees on predictive distributions rather than prediction regions, which is being used throughout our work.

Conformal Credal Pseudo-Labeling
In this section, we revisit credal pseudo-labeling and introduce conformal prediction as a framework for reliable prediction and an integral part of our conformal credal pseudo-labeling approach.

Credal Pseudo-Labeling
In supervised classification, one typically assumes instances x ∈ X of an instance space X to be associated with a ground-truth in the form of a conditional probability distribution p * (· | x) ∈ P(Y) over the class space Y = {y 1 , ..., y K }. Training a probabilistic classifierp : X −→ P(Y) commonly involves the optimization of a probabilistic surrogate loss function L : P(Y) × P(Y) −→ R + (e.g., cross-entropy) comparing the model predictionp to a proxy distribution p reflecting the true target p * (· | x). Although it would be desirable, most classification datasets do not give direct access to p * , but only to a realization y ∈ Y of the random variable Y ∼ p * (· | x), whence a degenerate distribution p y with p y (y) = 1 and p y (y ) = 0 for y = y is often considered as a proxy. Other data modeling techniques such as label smoothing [61] also consider "softened" versions of approaching p y .
What methods of this kind share is their reliance on a single probability distribution as target information. As already said, this information does not allow for representing any uncertainty about the ground-truth distribution p * : Predicting a precise distributionp, the learner pretends a level of certainty that is not warranted. This is a sharp conflict with the observation that, in practice, such predictions tend to be poorly calibrated and overconfident [47], and are hence likely to bias the learner.
To overcome these shortcomings, Lienen and Hüllermeier [42,43] suggest to the replace a single probabilistic prediction by a credal set Q ⊆ P(Y), i.e., as set of (candidate) probability distributions. This set Q is supposed to cover the ground-truth p * , very much like a confidence interval is supposed to cover a ground-truth parameter in classical statistics. Thus, the learner is able to represent its uncertainty about the ground-truth p * in a more faithful way. More specifically, the learner's (epistemic) uncertainty is in direct correspondence with the size of the credal set. It can represent complete ignorance about p * (by setting Q = P(Y)), complete certainty (Q = {p}), but also epistemic states in-between these extremes.
One way to specify credal sets is by means of so-called possibility distributions [23] π : Y −→ [0, 1], which induce a possibility measure Π : 2 Y −→ [0, 1] by virtue of Π(Y ) = max y∈Y π(y) for all Y ⊆ Y. Possibility degrees can be interpreted as upper probabilities, so that a possibility distribution π specifies the following set of probability distributions: To guarantee Q π = ∅, the distribution π is normalized such that max y∈Y π(y) = 1, i.e., there is at least one label y considered fully plausible.
When considering the setting of semi-supervised learning, credal labeling is employed as a pseudo labeling technique in credal self-supervised learning (CSSL) [42]: For each unlabeled instance, a credal set is maintained to express the current belief about p * in terms of a confidence region Q ⊆ P(Y). To this end, CSSL derives a possibility distribution π by an ad-hoc heuristic that assigns full plausibility π(ŷ) = 1 to the classŷ for which the predicted probability is highest, and determines a constant plausibility degree α for all other classes y =ŷ; the latter depends on the learner's confidence as well as the class prior and the prediction history.
Although CSSL has proven to provide competitive generalization performance, the credal set construction heuristic lacks a solid theoretical foundation and does not provide any quality guarantees. Especially in the case of overconfident models, the credal sets may not reflect uncertainty properly and misguide the learner. Moreover, the class prior and the prediction history employed in the specification of possibility distribution constitute yet another potential source of bias in the learning process. This raises the question whether credal pseudo-labeling can be based on a more solid theoretical foundation and equipped with validity guarantees. An affirmative answer to this question is offered by the framework of conformal prediction.

Inductive Conformal Prediction
Conformal prediction (CP) [66] is a distribution-free uncertainty quantification framework that judges a prediction for a query by its "non-conformity" with data observed before. While it has been originally introduced and extensively analyzed in an online setting, we refer to an offline ("batchwise") variant as typically considered in supervised learning settings. Several alternative variants of conformal prediction have been proposed in the past, most notably transductive and inductive methods. In its original formulation, the former requires a substantial amount of training and is clearly unsuitable in large-scale learning scenarios such as typical deep learning applications. This issue has been addressed in so-called inductive conformal prediction (ICP) [51] by alleviating the computational demands through additional calibration data.
Assume we are given training data observations. For a given query (resp. test) instance x N +1 , the goal of conformal prediction is to provide an uncertainty quantification with provable guarantees about the likeliness of each possible candidateŷ ∈ Y being the true outcome associated with x N +1 . This is done by measuring the conformity of (x N +1 ,ŷ) with D calib for each candidate labelŷ.
To this end, conformal prediction calculates a non-conformity measure α : (X × Y) m × (X × Y) −→ R, which indicates how well a pair of a query instance and a candidate label conforms to an observed sequence of m pairs. Typically, the non-conformity α(D, (x, y)) involves the training of an underlying predictor (a modelp in our case) on D, whose predictionp(x) is then compared to y. In a probabilistic learning scenario, common choices are α(D, (x, y)) = max yj =yp and wherep D is a probabilistic classifier trained on D,p(·)(y ) denotes the output probability for class y and γ ≥ 0 is a sensitivity parameter [52]. In our case, we set D to the training data D train .
In ICP, non-conformity scores α i are calculated for all (x i , y i ) ∈ D calib , i.e., it is determined for each calibration instance how well it conforms with the underlying training data D train . For the uncertainty quantification of the prediction for a query instance x N +1 , the non-conformity αŷ N +1 := α(D train , (x N +1 ,ŷ)) is calculated for each candidate labelŷ ∈ Y. Given the non-conformity values α 1 , . . . , α L associated with the calibration data, these non-conformity values can be used to construct p-values for each candidate labelŷ, comparable to the notion of p-values in traditional statistics: Consequently, one can define a conformal predictor Γ δ with confidence 1 − δ by Such a Γ δ can be shown to cover the true label y N +1 associated with x N +1 with high probability: where the probability is taken over x N +1 and D calib . This property is typically referred to as (marginal) validity, however, following [13], we refer to (6) as weak validity. Note that this holds for any underlying probability distribution, any δ ∈ (0, 1), and N ∈ N + . Nevertheless, practically speaking, small calibration datasets D calib may be problematic if a certain granularity in the confidence degree is desired [33].

Conformalized Predictive Distributions
While the notion of weak validity applies to set-valued prediction regions, its application as quantification of predictive distributions is not obvious. In the realm of probabilistic classification (as considered here), one may wonder how CP can be applied to provide a meaningful uncertainty quantification. Recently, Cella and Martin [12] proposed an interpretation of p-values π (cf. Eq. (4)) in terms of possibility degrees, i.e., upper probabilities of the event that the respective candidate label is the true outcome. Consequently, these possibilities π induce possibility measures Π, such that With supŷ ∈Y π(ŷ) = 1 for all D train and assuming that π is stochastically no smaller than the uniform distribution U(0, 1) under any underlying (ground-truth) probability distribution, probabilistic predictors satisfy the strong validity property defined as follows: holds for any δ ∈ (0, 1), A ⊆ Y, training data D train and any underlying true probability distribution.

Conformal Credal Pseudo-Labeling
Strongly valid possibility distributions π of this kind can be directly employed in the credal set formulation in (1) to bound the space of probability distributions. Relating to the self-training paradigm we consider in a semi-supervised setting, where a model suggests itself credal sets as pseudo-supervision to learn from, we refer to such credal sets as conformal credal pseudo-labels. Note that such pseudo-labels do not necessarily need to be constructed by an inductive conformal prediction procedure, but can used any CP methodology with the same guarantees.
To guarantee property (8) for the possibility distribution π defined in (4), this distribution needs to be normalized such that maxŷ ∈Y π(ŷ) = 1 to ensure strong validity and that Q π = ∅. A commonly applied normalization is suggested in [12]: By the described conformal credal labeling method, we replace the ad-hoc construction of sets in CSSL by a more profound technique with formal guarantees. More precisely, we build the learner's uncertainty-awareness on top of an objective quality criterion deduced from its accuracy on the calibration data. This not only provides strong validity guarantees, but also paves the path to a more rigorous theoretical analysis of self-supervised credal learning. Nevertheless, these guarantees come at a cost: By applying a conformal prediction procedure, one either provokes an increased computational overhead (for instance in a transductive CP setting) or a decrease in data efficiency by requiring additional calibration data. However, as will be seen in the empirical evaluation, the improved pseudo-label quality makes up for this in terms of generalization performance.

Conformal Credal Self-Supervised Learning
In the following, we provide an overview of our methodology for effective semi-supervised learning from conformal credal pseudo-labels. Figure 1: Overview over C 2 S 2 L: While learning on the labeled batch B l is performed conventionally, the labels for the unlabeled batch B u are constructed by an inductive conformal prediction (ICP) procedure provided calibration data D calib , optionally employing consistency regularization (CR).

Overview
In our approach, which we call conformal credal self-supervised learning (C 2 S 2 L), we combine credal self-supervised learning as proposed in [42] with conformal credal labels. We thus replace the credal set construction in CSSL to ensure guarantees of the pseudo-label's validity. Fig. 1 gives an overview of the algorithm, its pseudo-code can be found in the appendix.
In each iteration, we observe batches of labeled is the multiplicity of unlabeled over labeled instances in each batch. Here, we consider degenerate distributions p yi as target information in B l . For the instances (x, p y ) ∈ B l , we compute the Kullback-Leibler divergence D KL (p y ||p(x)) as loss L l .
For the unlabeled instances x ∈ B u , we derive conformal predictions in an inductive manner based on a previously separated calibration dataset D calib . To this end, a (strongly valid) possibility distribution π over all possible labels y ∈ Y is determined for the predictionp(x), which is used to construct a credal target set Q π according to (1). Finally, Q π is compared to the predictionp(x) in terms of a generalized probabilistic loss L * : 2 P(Y) × P(Y) −→ R + , which we shall detail in Section 4.2.
Altogether, the training objective is given by where λ u ≥ 0 weights the importance of the unlabeled loss part L u . As in [60] and [42], this approach can be embedded in a consistency regularization framework as previously considered -this will be further discussed in Section 4.3.

Generalized Credal Learning
As set-valued targets are provided as (pseudo-)supervision for the unlabeled instances, a generalization of a single-point probability loss L is required. Here, we follow [42] and leverage a generalized empirical risk minimization approach by minimizing the optimistic superset loss [9, 30] with L = D KL in our case. This generalization is motivated by the idea of data disambiguation [30], in which targets are disambiguated within imprecise sets according to their plausibility in the overall loss minimization context over all data points, leading to a minimal empirical risk with respect to the original loss L.
While credal sets as considered in CSSL are of rather simplistic nature, credal sets with arbitrary (but normalized) possibility distributions as introduced in Section 3.3 impose a more complex optimization problem. More precisely, consider a possibility distribution π and denote π i := π(y i ). Without loss of generality, let the possibilities be ordered, i.e., 0 ≤ π 1 ≤ . . . , ≤ π K = 1. Then, it has been shown that the following holds for any distribution p ∈ Q π with p i := p(y i ) [17]: The resulting set of inequality constraints induces a convex polytope [37], such that the optimization problem in (11) becomes the problem of finding the closest point in a convex polytope (here Q π ) with minimal distance to a given query point (p). We provide examples illustrating such convex credal polytopes in the appendix.
Optimization problems of this kind are not new, and many approximate solutions have been proposed in the past, including projected gradient algorithms [3], conditional gradient descent (alias Frank-Wolfe algorithms) [24, 32], and other projection-free stochastic methods [41]. However, we found that one can take advantage of the structure of the problem (12) to induce a precise and average-case efficient algorithmic solution to (11).

Algorithm 1 Generalized Credal Learning Loss
Algorithm 1 lists the procedure to determine the loss L * (Q π ,p). The key idea is to consider each face of the convex polytope being associated with a particular possibility constraint π i . The algorithm then determines the optimal face on which the predictionp can be projected without violating the constraint for any π j ≤ π i , which is guaranteed to provide the optimal solution for the classes y j . In an iterative scheme, this procedure is applied to all classes, leading to the distribution p ∈ Q π with minimal D KL top. Hence, we can state the following theorem. Theorem 4.1 (Optimality). Given a credal set Q π induced by a normalized possibility distribution π : Y −→ [0, 1] with max y∈Y π(y) = 1 according to (1), Algorithm 1 returns the solution of L * (Q π ,p) as defined in (11) for an arbitrary distributionp ∈ P(Y).
Due to space limitations, we provide the proof of Theorem 4.1 in the appendix. We further provide a discussion of the computational complexity of Algorithm 1 therein, showing that the worst case complexity is cubic in the number of labels -the average case complexity is much lower, however, making the method amenable to large data sets as demonstrated in our experimental evaluation.

Mitigating Confirmation Bias
In self-training, pseudo-labels can manifest the misbeliefs of an accurate learner, a problem that is commonly known as confirmation bias [1]. Posing wrong targets and "learning" from them harms the generalization performance and leads to poorly calibrated models. This issue constitutes one of the main challenges in semi-supervised self-training, requiring additional means to tackle it.
As one prominent countermeasure, consistency regularization [2,58] has been established as a stateof-the-art methodology to reduce the risk of confirmation biases. The key idea is to ensure consistent predictions for multiple perturbed versions of the same underlying object. This method has been successfully combined with pseudo-labeling, whereby [60] proposes a particularly simple scheme: An unlabeled instance x ∈ X is augmented by a weak (e.g., horizontal flipping) and a strong (e.g., RandAugment [16] or CTAugment [6]) augmentation policy A w : X −→ X and A s : X −→ X , respectively. The strongly-augmented representation A s (x) is then used to construct a pseudo-label based onp(A s (x)), which is finally compared top(A w (x)) to compute the loss.
In our approach, we adopt this scheme for spatial input domains X such as images. As the uncertainty quantification in the inductive conformal prediction procedure is conducted to construct a pseudolabel on A s (x), we apply the strong augmentation policy also to the calibration instances to ensure a tighter correspondence of the individual non-conformity scores. Note that our proposal does not inherently rely on consistency regularization as a confirmation bias countermeasure. While domains such as image classification benefit from this measure, other domains may not need it and could instead be approached directly.

Experiments
To demonstrate the effectiveness of our method, we present empirical results for the domain of image classification as an important and practically relevant application. We refer to the appendix for additional results, including a study on knowledge graphs to demonstrate generalizability of our approach, as well as a more comprehensive overview over experimental settings for reproducibility.

Experimental Setting
Following previous semi-supervised learning evaluation protocols [42,60], we performed experiments on CIFAR-10/-100 [36], SVHN [48] (without the extra data split) and STL-10 [15] with various numbers of sub-selected labels. To this end, we trained Wide ResNet-28-2 [70] models for CIFAR-10, SVHN and STL-10, whereas we considered Wide ResNet-28-8 as architecture for CIFAR-100. For each combination, we conducted a Bayesian optimization to tune the hyperparameters with 20 runs each on a separate validation split, while we report the final test performances per model trained with the tuned hyperparameters. Each model was trained for 2 18 iterations. We repeated each experiment 3 times with different seeds, whereby we re-used the best hyperparameters for all seeds due to the high computational complexity.
For C 2 S 2 L, we distinguish two variants employing either the non-conformity measure (2) or (3), which we refer to as C 2 S 2 L-diff and C 2 S 2 L-prop respectively. As baselines, we consider FixMatch [60] and its distribution alignment version as hard and soft probabilistic pseudo-labeling technique, respectively. Moreover, we compare our method to UDA [67] as another soft variant. Recently, FlexMatch [72] has been proposed as an advancement of FixMatch by adding curriculum learning encompassing uncertainty-awareness. Finally, we report results of CSSL [42] as methodically closest related work to our approach. In all cases, we employ RandAugment as strong augmentation policy to realize consistency regularization. As all of the mentioned approaches were embedded in the basic FixMatch framework, we achieve a fair comparison alleviating side-effects. Table 1 shows the generalization performance of all methods with respect to the accuracy for various amounts of labeled data. Note that the calibration set for the conformal credal variant is taken from the labeled instances, i.e., the effective number of instances to learn from is further decreased. In   the appendix, we provide a quantification of the network calibration, i.e., the quality of the predicted probability distributions.

Generalization Performance
As can be seen, C 2 S 2 L leads to competitive generalization when a sufficient amount of labeled instances is provided, often even performing best among the compared methods. In the label-scarce settings, the separation of a calibration set (which is taken from the labeled data part) has a stronger effect, and the performance is slightly inferior to CSSL. However, the performance still does not drop, which confirms the effectiveness of the improved pseudo-label quality over CSSL. In most other cases, C 2 S 2 L appears to be superior compared to CSSL.

Pseudo-Label Quality
To assess the quality of the (credal) pseudo-labels, we further computed the validity according to (8) by measuring the error rate in terms of 1(π(y) ≤ δ) given the pseudo-supervisions π for the unlabeled training instances with true labels y (for confidence levels δ ∈ {0.05, 0.1, 0.25}). To ensure fairness, we compute these scores for trained models so as not to give an advantage to C 2 S 2 L, which can in contrast to CSSL rely on the strong validity guarantee throughout the training.
As shown in Table 2, the two variants of C 2 S 2 L achieve a consistent improvement in the validity of the pseudo-labels over CSSL, although the supervision provided by the latter is already quite accurate and does not violate the strong validity property either. Moreover, C 2 S 2 L-prop leads to better calibrated credal sets compared to C 2 S 2 L-diff.
Furthermore, the efficiency of the credal sets, i.e., their sizes, has an effect on the learning behavior. Fig. 2 compares the credal set sizes of CSSL and C 2 S 2 L over the course of the training. As can be seen, C 2 S 2 L constructs smaller credal sets, which in combination with the improved validity leads to a more effective supervision. Furthermore, the credal sets sizes decrease with higher numbers of labels, which is due to a higher prediction quality involved in the credal set construction. Apart from the results on CIFAR-10 with 250 labels, one can further see that the credal set size deviates only slightly between the two non-conformity measures employed in C 2 S 2 L.

Conclusion
In the context of semi-supervised learning, previous pseudo-labeling approaches lack validity guarantees for the quality of the pseudo-supervision. Such methods often suffer from misleading supervision, leaving much potential unused. In our work, we address these shortcomings by a conformal credal labeling approach leveraging the framework of conformal prediction, which entails validity guar-antees for the constructed pseudo-labels in the form of credal sets. Our empirical study confirms the adequacy of this approach in terms of generalization performance, as well as the calibration and efficiency of pseudo-labels compared to previous methods.
In future work, we plan to investigate approaches to achieve conditional (per-instance) validity, i.e., conformal credal labels specifically tailored to (conditioned on) the query instance x N +1 , which would lead to even stronger guarantees for the quality of pseudo-labels. Approximations of this type of validity for conformal prediction have already been provided [5,65]. Moreover, a more rigorous analysis of the efficiency of alternative non-conformity scores needs to be performed, including their robustness to label noise as typically present in real-world data. [

A Appendix
A.1 Pseudo-Code of C 2 S 2 L Algorithm 2 C 2 S 2 L with consistency regularization Require: Batch of labeled instances with degenerate ground truth distributions of unlabeled instances, unlabeled loss weight λ u , modelp : X −→ P(Y), strong and weak augmentation functions A s , A w : Derive possibility distribution π = ICP (D calib ,p(A w (x)))

A.2.1 Settings
To conduct the experiments as presented in the paper, we followed the basic semi-supervised learning evaluation scheme as in [42,60]. However, as opposed to previous evaluations, we reduce the number of iterations to 2 18 with a batch size of 32, which allows for a proper hyperparamter optimization of all methods. To this end, we employ a Bayesian optimization 1 with 20 runs for each combination of dataset and number of labels on a separate validation split. Moreover, we use Hyperband [40] with η = 3 and 20 minimum epochs (that is, iterating over all unlabeled instances once) for early stopping. Due to the computational complexity of this procedure, we determined the best hyperparameter on a fixed seed and applied those parameters to all repetitions with different seeds for the same dataset and number of labels combination. Albeit not being ideal, such routine still improves fairness compared to previous evaluations which do not apply the same hyperparameter tuning procedure to all regarded baselines. Table 3 shows the considered parameter spaces. To train the models, we use SGD with a Nesterov momentum of 0.9. We further employ cosine annealing as learning rate schedule [45]. Moreover, we apply exponential moving averaging with a fixed decay of 0.999 to the weights.

A.2.2 Environment
We implemented all methods using PyTorch 2 , where we reused the official implementations if available. We proceeded from a popular FixMatch re-implementation in PyTorch 3 for the image classification experiments, which we carefully checked for any differences to the original repository, and embedded all other baselines into it. To conduct the experiments, we used several Nvidia A100 GPUs in a modern high performance cluster environment. Our code is publicly available at https://github.com/julilien/C2S2L (Apache-2.0 License).

A.3.1 Predictor Calibration
For completeness, we present the quality of the prediction probability distributions in the large-scale image classification experiments with respect to their expected calibration errors in Table 4. Both C 2 S 2 L variants demonstrate favorable calibration properties, whereas C 2 S 2 L-prop often outperforms all other methods.  In addition, we provide the learning curves in terms of test accuracy per training iteration averaged over 3 random seeds on CIFAR-10 and SVHN with 250 labels each in Fig. 3. As can be seen, C 2 S 2 Lprop shows a similar training efficiency as CSSL, whereas C 2 S 2 L-diff realizes a more cautious learning than all other methods. This becomes particularly visible for SVHN. Here, C 2 S 2 L-prop shows an even improved training efficiency compared to CSSL. Remarkably, the C 2 S 2 L variants have less labeled supervision available as part of it is separated in form of the calibration split, which can be one reason for the cautiousness of C 2 S 2 L-diff in the first iterations. Together with the validity gains in the pseudo-label quality, especially C 2 S 2 L-prop demonstrates its effectiveness to the task of semi-supervised learning.

A.3.3 Ablation Studies
In the following, we present further ablation studies to investigate properties of C 2 S 2 L more thoroughly. If not stated otherwise, we set the initial learning rate to 0.03, λ u = 1, µ = 7 and the weight decay to 0.0005. Also, we consider calibration size fractions of 0.25 by default.
Possibility Distribution Normalization Conformal Credal Pseudo-Labeling involves normalizing possibility distributions π : Y −→ [0, 1] to satisfy max y∈Y π(y) = 1. In Eq. (9) of the paper, we introduced a proportion-based normalization technique, to which we refer as normalization 1. As an alternative, one can consider the following normalization [12], to which we refer as normalization 2: It is easy to see that (13) leads to smaller credal sets due to 0 ≤ π(·) ≤ 1.  Table 5 shows the results. Although the second normalization strategy leads to smaller credal sets, it leads to inferior generalization performance for the proportion-based non-conformity measure, suggesting that an overly extreme credal set construction may be suboptimal. This supports the adequacy of the first normalization strategy as employed in C 2 S 2 L by default.  SVHN@250 labels

CIFAR-10@250 labels
Calibration size (fraction of labeled instances) Test accuracy Figure 4: Test accuracy and the standard deviation per calibration size for the two variants of C 2 S 2 L. The results are averaged over 3 different random seeds.
Calibration Split Size The calibration size used to determine the number of calibration instances affects the quality of the credal sets. Here, we consider calibration split proportions in {0.1, 0.25, 0.5, 0.9}. As can be seen in Fig. 4, the differences in the performances do not vary too much. On CIFAR-10 with 250 labels, no clear trend can be observed. However, the deviations of runs with a fraction of 0.25 appear significantly higher than for the other sizes. This could be due to the sacrifice of too many labeled instances without achieving too precise pseudo-supervision. Lower and higher calibration sizes may overcome this by benefiting from either of these two extremes (higher pseudo-label quality through many labeled instances or larger calibration sets). In case of SVHN, C 2 S 2 L-prop seems to be more sensitive to the calibration size and achieves the best results with a calibration size fraction of 0.25. Here, too small calibration sizes clearly lead to unsatisfying results, demonstrating again the influence of the pseudo-label quality on the overall generalization performance.
Proportion-based Non-Conformity Sensitivity The proportion-based non-conformity measure α (D, (x, y)) in Eq. (3) involves the parameter γ ≥ 0, which represents the sensitivity towards the influence of the predictionp D (x)(y) on the scoring for a given tuple (x, y). In Table 6, we report results of C 2 S 2 L-prop for γ ∈ {0.01, 0.1, 0.5, 1, 10}. While smaller γ values lead to better results for CIFAR-10, SVHN benefits from slightly higher γ values. These results show that this parameter indeed has an effect on the overall results, i.e., it is reasonable to consider it as a hyperparameter.

A.3.4 Knowledge Graph Embedding Experiments
We were interested in evaluating conformal credal self-supervised learning in the link prediction problem on knowledge graphs. Knowledge graphs represent structured collections of facts [29], which are stored in graphs connecting entities via relations. These collections of facts have been used in a wide range of applications, including web search, question answering, and recommender systems [49]. The task of identifying missing links in knowledge graphs is referred to as link prediction. Knowledge graph embedding (KGE) models have been particularly successful at tackling the link prediction task, among many others [49]. In semi-supervised link prediction, only a fraction of facts is given. The task is then to "enrich" the input graph to detect relations that connect entities, which are subsequently also used in the learning of graph embeddings.
Experimental Setting In our experiments, we follow a standard training and evaluation setup commonly used in the KGE domain [57,10]. We consider three multiplicative interaction-based KGE embedding models: DistMult [69], ComplEx [63], and QMult [19]. To train the models, we model the problem as a 1vsAll classification (see [18] and [57] for more details about the 1vsAll training regime). Here, we compare conventional pseudo-labeling as described in [38] to C 2 S 2 L-diff. In the following, we refer to the former as PL. We do not employ consistency regularization or any other confirmation bias mitigation technique, demonstrating the flexibility of our framework. In our experiments, we used the two benchmark datasets UMLS and KINSHIP [20], whose characteristics are provided in Table 7.
For each model (DistMult, ComplEx, and QMult), we applied a grid-search over the learning rates {0.01, 0.1, 0.001}, batch sizes {512, 1024} and the number of epochs {5, 50} to tune the parameters on a separate validation set. For C 2 S 2 L-diff, we initially divided D train into training, calibration and unlabeled splits with 40:40:20 ratios, respectively. For the conventional pseudo-labeling procedure, we divided D train into training, and unlabeled splits with 40:60 ratios, respectively. To ensure that each model is trained with the exact training split, we select the first 40% of all triples as training split.
As opposed to domains like image classification, where a small number of classes, for which labeled instances are provided, allows for a certain degree of interpolation, knowledge graphs involve a typically larger vocabulary of entities. By subselecting data from the knowledge graph, there is a much higher chance to miss some entities. Not observing parts of the vocabulary renders the   task of learning their embeddings effectively as an unsupervised learning problem. This is why our considered training splits are relatively large. Arguably, C 2 S 2 L gets an unfair advantage here by providing (labeled) calibration data beyond the labeled training data. However, this data is excluded from being used as pseudo-labeled training data either, and can not contribute to the learned embeddings directly. It leaves large parts of the knowledge graph unconnected as it prevents to enrich that part of the graph by pseudo-labels, having an influence on the generalizability of the learned KGE model. Table 8 reports the link prediction performance on UMLS and KINSHIP. Overall, the results suggest that incorporating C 2 S 2 L in knowledge graph embedding model leads to better generalization performance in 16 out of 18 metrics on two benchmark datasets. Also, the credal pseudo-label construction is effective as it improves the results over the PL baseline. To address our discussions about fairness in the split modeling, we conduct two more experiments with 40:10:50 and 30:20:50 split ratios to quantify the impact of the calibration signal in the link prediction task, where the PL baselines observes splits with ratios 40:60 and 50:50, respectively. Table 9 reports the link prediction performances for the 40:10:50 (C 2 S 2 L) and 40:60 (PL) split ratio. Interestingly, the results do not vary much (only in 3 out of 18 cases). This confirms that the labeled data split has critical influence on the overall results in KGE link prediction, whereas the contribution of the self-supervised part is limited. As said before, semi-supervised learning in knowledge graph embedding is much more depending on the training data compared to image classification.

Link Prediction Results
Motivated by the findings in the results shown in Tables 8 and 9, we reduced the training set for C 2 S 2 L by 25% and increased the training set for pseudo-labeling by 25%. This setting leads to better generalization performance for PL in all metrics, again giving further evidence for our reasoning about the splits. This case clearly demonstrates a limitation of our method: C 2 S 2 L is especially favorable in settings where a sufficient amount of labeled instances are provided, particularly when facing structural data such as knowledge graphs.

A.4 Generalized Credal Learning: Theoretical Results
In this section, we provide theoretical results on generalized credal learning as introduced in Section 4.2 of the main paper.  In the following, we consider possibility distributions π : Y −→ [0, 1], where π i := π(y i ) abbreviates the possibility of class y i . Without loss of generality, we assume the possibilities be ordered and normalized, i.e., 0 ≤ π 1 ≤ . . . ≤ π K = 1 for K classes. Furthermore, we also denote the respective probability of a class y i given a distribution p ∈ P(Y) by p i := p(y i ).
As described in Section 4.2, the set of inequalities that defines the boundary of a credal set Q π induces a convex polytope. In Fig. 5, such a credal set is illustrated for three and four classes in a barycentric visualization. The extreme points are marked with the respective probabilities.
In Algorithm 1, we provide an algorithm to solve the problem of finding the closest point in the convex polytope Q π to a query distributionp. In order to proof Theorem 4.1 that states the optimality of this approach, we will introduce the following three lemmas: 1. Termination 2. Optimal projection 3. Optimal face Lemma A.1 (Termination). Given a normalized possibility distribution π : Y −→ [0, 1], Algorithm 1 terminates for an arbitrary probability distributionp ∈ P(Y).
Proof. In case ofp ∈ Q π , we immediately return with a result. Forp ∈ Q π , we fix the probabilities of all y ∈ Y in each iteration of Algorithm 1, which are then removed from Y . Thereby, at least for the classȳ ∈ Y with smallest possibility π(ȳ) (1,0,0) (1-2 , 2 , 0) 2 1 3 Ƹ Figure 5: Schematic illustration of a credal set Q π as a convex polytope in a barycentric coordinate space of all distributions P(Y) for three and four classes. Q π is induced by a normalized possibility distribution π with 1 = π(y 1 ) ≥ . . . ≥ π(y K ) ≥ 0.
holds, which does not violate the possibility constraints as in Eq. (12). Here, the set of classes whose probabilities p r are set is given by Y = {ȳ}. Consequently, at least one element in Y is removed per step, which eventually results in an empty set Y and the termination of Algorithm 1.
In the next lemma, we characterize the optimality of a projection according to the distribution p r ∈ P(Y) as determined in Algorithm 1. In this course,Ȳ ⊆ Y denotes the set of arbitrary, but already fixed probabilities p r (y) for y ∈Ȳ . This set shall represent classes with optimal probability scores determined in previous iterations. Without loss of generality, we assume that ∀y ∈Ȳ : π(y) ≤ min y ∈Y\Ȳ π(y ). Moreover, for a certain possibility degree π i , let us define the set of classes with at most π i possibility as For the remaining classes in Y \Ȳ , let p r be constructed as follows: Moreover, we use the notion of a half space associated with a possibility constraint π i , which is defined as follows.
Given distributions p r of the form (15) for a possibility constraint π i , which is by construction element of half-space π (due to ∀y ∈Ȳ : π(y) ≤ π i ), we can make the following statement about its optimality.
Lemma A.2 (Optimal projection). Given a setȲ ⊆ Y of classes with arbitrarily fixed probabilities, a (normalized) possibility distribution π : Y −→ [0, 1] with max y∈Y π(y) = 1 and the set half-space πi , the projection p r (y) ∈ half-space πi as defined before is optimal in the sense that p ∈ half-space πi with p(y) = p r (y) ∀y ∈Ȳ for which ∃y ∈ Y πi \Ȳ : p(y) = p r (y) such that D KL (p ||p) < D KL (p r ||p).
Proof. Let us define A := y∈Ȳ p r (y) as the sum of the (previously) fixed probabilities. From the definition of p r , we know: Now, suppose ∃p ∈ half-space πi with p(y) = p r (y) ∀y ∈Ȳ for which ∃y ∈ Y πi \Ȳ : p(y) = p r πi (y) such that D KL (p ||p) < D KL (p r ||p), which would lead to a contradiction of the lemma. Here, the last equation can be derived from the log sum inequality 4 . As we are projecting onto the half space associated with π i , we can further see that y∈Y\Yπ i p(y) = 1 − π i and y∈Yπ i \Ȳ p(y) = π i − A, which also applies to p r for the same class subsets.
As a result, together with (16), we get which leads to a contradiction.
Effectively, face πi considers the subspace of half-space πi that does not violate any of the possibility constraints π j ≤ π i . One can readily see that each iteration of Algorithm 1 determines the highest possibility constraint π(y * ) whose projection p r as defined before is element of face π(y * ) . Given this fact, we show the optimality of this selected face in the next lemma.
Proof. Again, we define A := y∈Ȳ p r (y). Now, let us assume ∃j = i with the properties described in this lemma, which leads us to a contradiction. To proof it, we can distinguish three cases.
Case 1: π j > π i . It is easy to see that a violation with respect to Eq. (12) for possibility ≤ π j exists, i.e., the projection constructed as in (15) for π j is not element of face πj . In this case, the distribution p * ∈ argmin faceπ j D KL (p ||p) is located on an "edge" of the face, i.e., ∃m : m k=1 p * k = π m . If m = i, then Lemma A.2 implies that p * (y) = p r (y) ∀y ∈ Y πi , which contradicts the assumptions.
In case of m = i, we can derive the following results using a similar scheme as in the proof of Lemma A. As we know that p * does not violate any possibility constraints in Y πj ⊃ Y πi due to p * ∈ face πj , but is also not on the same edge as implied by π i , it holds that Moreover, as we know that there is no possibility violation by p r (y) ∀ ∈ Y πi associated with π (cf. Lemma A.2), it must hold Yπ i \Ȳp (y) > π i − A. Otherwise,p would be element of Q π .
Altogether, one can readily follow leading to a contradiction.
Case 2: π j = π i . Lemma A.2 implies the optimality of p r in this case.
Case 3: π j < π i . Here, one can again distinguish whether there exists a violation of p r constructed for π j or not. In the first case, we can apply exactly the same idea as before by showing that the projection p * ∈ argmin p∈faceπ j D KL (p ||p) is located on an edge that is associated with a π m with m < i.
In case there is no violation, we know that j k=1 p * k = π j . This leads to i k=1 p * k ≤ π i . Together with Yπ i \Ȳp (y) > π i − A, one can derive a similar equation as in Eq. (17) to show that D KL (p * ||p) − D KL (p r ||p) ≥ 0 ≮ 0 , leading again to a contradiction.
By combining the previous results, we are ready to proof the optimality of Algorithm 1. Theorem 4.1 (Optimality). Given a credal set Q π induced by a normalized possibility distribution π : Y −→ [0, 1] with max y∈Y π(y) = 1 according to (1), Algorithm 1 returns the solution of L * (Q π ,p) as defined in (11) for an arbitrary distributionp ∈ P(Y).
Proof. Combining the three previous lemmas, as well as the fact that the solution of argmin p∈Qπ D KL (p ||p) is always characterized by an extreme point on one of the faces of the convex polytope Q π forp ∈ Q π , leads to Theorem 4.1: In each iteration, we choose the optimal projection on the optimal face. Thus, we maintain the optimal probabilities p r (y) for all y ∈ Y .
In case ofp ∈ Q π , Algorithm 1 returns D KL (p ||p) = 0, which is optimal by definition of D KL .