# Conformal Credal Self-Supervised Learning

Julian Lienen
Department of Computer Science
Paderborn University
Paderborn 33098, Germany
<EMAIL_ADDRESS>&Caglar Demir
Department of Computer Science
Paderborn University
Paderborn 33098, Germany
<EMAIL_ADDRESS>&Eyke Hüllermeier
Institute of Informatics
University of Munich (LMU)
Munich 80538, Germany
<EMAIL_ADDRESS>
###### Abstract

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.

##  1 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 pseudo-labeling
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^{\prime}$) as a criterion for hypothesis rejection, i.e., whether to
include a value $y^{\prime}$ 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 (C2S2L).
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 pseudo-labeling
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.

##  2 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 student-teacher 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.

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

###  3.1 Credal Pseudo-Labeling

In supervised classification, one typically assumes instances
$\boldsymbol{x}\in\mathcal{X}$ of an instance space $\mathcal{X}$ to be
associated with a ground-truth in the form of a conditional probability
distribution $p^{*}(\cdot\,|\,\boldsymbol{x})\in\mathbb{P}(\mathcal{Y})$ over
the class space $\mathcal{Y}=\\{y_{1},...,y_{K}\\}$. Training a probabilistic
classifier $\hat{p}:\mathcal{X}\longrightarrow\mathbb{P}(\mathcal{Y})$
commonly involves the optimization of a probabilistic surrogate loss function
$\mathcal{L}:\mathbb{P}(\mathcal{Y})\times\mathbb{P}(\mathcal{Y})\longrightarrow\mathbb{R}_{+}$
(e.g., cross-entropy) comparing the model prediction $\hat{p}$ to a proxy
distribution $p$ reflecting the true target $p^{*}(\cdot\,|\,\boldsymbol{x})$.
Although it would be desirable, most classification datasets do not give
direct access to $p^{*}$, but only to a realization $y\in\mathcal{Y}$ of the
random variable $Y\sim p^{*}(\cdot\,|\,\boldsymbol{x})$, whence a degenerate
distribution $p_{y}$ with $p_{y}(y)=1$ and $p_{y}(y^{\prime})=0$ for
$y^{\prime}\neq 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 distribution $\hat{p}$, 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
$\mathcal{Q}\subseteq\mathbb{P}(\mathcal{Y})$, i.e., as set of (candidate)
probability distributions. This set $\mathcal{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
$\mathcal{Q}=\mathbb{P}(\mathcal{Y})$), complete certainty
($\mathcal{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] $\pi:\mathcal{Y}\longrightarrow[0,1]$, which induce a
possibility measure $\Pi:2^{\mathcal{Y}}\longrightarrow[0,1]$ by virtue of
$\Pi(Y)=\max_{y\in\mathcal{Y}}\pi(y)$ for all $Y\subseteq\mathcal{Y}$.
Possibility degrees can be interpreted as upper probabilities, so that a
possibility distribution $\pi$ specifies the following set of probability
distributions:

$\mathcal{Q}_{\pi}:=\Big{\\{}p\in\mathbb{P}(\mathcal{Y})\,|\,\forall
Y\subseteq\mathcal{Y}:P(Y)=\sum_{y\in Y}p(y)\leq\max_{y\in
Y}\pi(y)=\Pi(Y)\Big{\\}}\enspace.$ (1)

To guarantee $\mathcal{Q}_{\pi}\neq\emptyset$, the distribution $\pi$ is
normalized such that $\max_{y\in\mathcal{Y}}\pi(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
$\mathcal{Q}\subseteq\mathbb{P}(\mathcal{Y})$. To this end, CSSL derives a
possibility distribution $\pi$ by an ad-hoc heuristic that assigns full
plausibility $\pi(\hat{y})=1$ to the class $\hat{y}$ for which the predicted
probability is highest, and determines a constant plausibility degree $\alpha$
for all other classes $y^{\prime}\neq\hat{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.

###  3.2 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 (“batch-
wise”) 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
$\mathcal{D}_{\text{train}}=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{N}\subset(\mathcal{X}\times\mathcal{Y})^{N}$
and calibration data
$\mathcal{D}_{\text{calib}}=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{L}\subset(\mathcal{X}\times\mathcal{Y})^{L}$
comprising $N$ resp. $L$ i.i.d. observations. For a given query (resp. test)
instance $\boldsymbol{x}_{N+1}$, the goal of conformal prediction is to
provide an uncertainty quantification with provable guarantees about the
likeliness of each possible candidate $\hat{y}\in\mathcal{Y}$ being the true
outcome associated with $\boldsymbol{x}_{N+1}$. This is done by measuring the
conformity of $(\boldsymbol{x}_{N+1},\hat{y})$ with
$\mathcal{D}_{\text{calib}}$ for each candidate label $\hat{y}$.

To this end, conformal prediction calculates a non-conformity measure
$\alpha:(\mathcal{X}\times\mathcal{Y})^{m}\times(\mathcal{X}\times\mathcal{Y})\longrightarrow\mathbb{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
$\alpha(\mathcal{D},(\boldsymbol{x},y))$ involves the training of an
underlying predictor (a model $\hat{p}$ in our case) on $\mathcal{D}$, whose
prediction $\hat{p}(\boldsymbol{x})$ is then compared to $y$. In a
probabilistic learning scenario, common choices are

$\alpha(\mathcal{D},(\boldsymbol{x},y))=\max_{y_{j}\neq
y}\hat{p}_{\mathcal{D}}(\boldsymbol{x})(y_{j})-\hat{p}_{\mathcal{D}}(\boldsymbol{x})(y)$
(2)

and

$\alpha(\mathcal{D},(\boldsymbol{x},y))=\frac{\max_{y_{j}\neq
y}\hat{p}_{\mathcal{D}}(\boldsymbol{x})(y_{j})}{\hat{p}_{\mathcal{D}}(\boldsymbol{x})(y)+\gamma}\enspace,$
(3)

where $\hat{p}_{\mathcal{D}}$ is a probabilistic classifier trained on
$\mathcal{D}$, $\hat{p}(\cdot)(y^{\prime})$ denotes the output probability for
class $y^{\prime}$ and $\gamma\geq 0$ is a sensitivity parameter [52]. In our
case, we set $\mathcal{D}$ to the training data $\mathcal{D}_{\text{train}}$.

In ICP, non-conformity scores $\alpha_{i}$ are calculated for all
$(\boldsymbol{x}_{i},y_{i})\in\mathcal{D}_{\text{calib}}$, i.e., it is
determined for each calibration instance how well it conforms with the
underlying training data $\mathcal{D}_{\text{train}}$. For the uncertainty
quantification of the prediction for a query instance $\boldsymbol{x}_{N+1}$,
the non-conformity
$\alpha^{\hat{y}}_{N+1}:=\alpha(\mathcal{D}_{\text{train}},(\boldsymbol{x}_{N+1},\hat{y}))$
is calculated for each candidate label $\hat{y}\in\mathcal{Y}$. Given the non-
conformity values $\alpha_{1},\ldots,\alpha_{L}$ associated with the
calibration data, these non-conformity values can be used to construct
p-values for each candidate label $\hat{y}$, comparable to the notion of
p-values in traditional statistics:

$\pi_{N+1}(\hat{y})=\frac{|\\{\alpha_{i}\geq\alpha^{\hat{y}}_{N+1}\,|\,i\in\\{1,...,L\\}\\}|}{L+1}\enspace.$
(4)

Consequently, one can define a conformal predictor $\Gamma_{\delta}$ with
confidence $1-\delta$ by

$\Gamma_{\delta}(\mathcal{D}_{\text{calib}},\boldsymbol{x}_{N+1})=\Big{\\{}\hat{y}\in\mathcal{Y}:\pi_{N+1}(\hat{y})\geq\delta\Big{\\}}.$
(5)

Such a $\Gamma_{\delta}$ can be shown to cover the true label $y_{N+1}$
associated with $\boldsymbol{x}_{N+1}$ with high probability:

$\Pr\Big{(}y_{N+1}\in\Gamma_{\delta}(\mathcal{D}_{\text{calib}},\boldsymbol{x}_{N+1})\big{)}\geq
1-\delta\enspace,$ (6)

where the probability is taken over $\boldsymbol{x}_{N+1}$ and
$\mathcal{D}_{\text{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 $\delta\in(0,1)$, and $N\in\mathbb{N}_{+}$. Nevertheless, practically
speaking, small calibration datasets $\mathcal{D}_{\text{calib}}$ may be
problematic if a certain granularity in the confidence degree is desired [33].

####  3.2.1 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 $\pi$ (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 $\pi$ induce possibility measures
$\Pi$, such that

$\Pi(A):=\sup_{\hat{y}\in A}\pi(\hat{y}),\qquad A\subseteq\mathcal{Y}\,.$ (7)

With $\sup_{\hat{y}\in\mathcal{Y}}\pi(\hat{y})=1$ for all
$\mathcal{D}_{\text{train}}$ and assuming that $\pi$ is stochastically no
smaller than the uniform distribution $\mathcal{U}(0,1)$ under any underlying
(ground-truth) probability distribution, probabilistic predictors satisfy the
strong validity property defined as follows:

$\Pr\big{(}\Pi(A)\leq\delta,y_{N+1}\in A\big{)}\leq\delta$ (8)

holds for any $\delta\in(0,1)$, $A\subseteq\mathcal{Y}$, training data
$\mathcal{D}_{\text{train}}$ and any underlying true probability distribution.

###  3.3 Conformal Credal Pseudo-Labeling

Strongly valid possibility distributions $\pi$ 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 $\pi$ defined in
(4), this distribution needs to be normalized such that
$\max_{\hat{y}\in\mathcal{Y}}\pi(\hat{y})=1$ to ensure strong validity and
that $\mathcal{Q}_{\pi}\neq\emptyset$. A commonly applied normalization is
suggested in [12]:

$\pi(\hat{y})=\frac{\pi(\hat{y})}{\max_{y^{\prime}\in\mathcal{Y}}\pi(y^{\prime})}\enspace.$
(9)

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.

##  4 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.

###  4.1 Overview

Figure 1: Overview over C2S2L: While learning on the labeled batch
$\mathcal{B}_{l}$ is performed conventionally, the labels for the unlabeled
batch $\mathcal{B}_{u}$ are constructed by an inductive conformal prediction
(ICP) procedure provided calibration data $\mathcal{D}_{\text{calib}}$,
optionally employing consistency regularization (CR).

In our approach, which we call conformal credal self-supervised learning
(C2S2L), 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
$\mathcal{B}_{l}=\\{(\boldsymbol{x}_{i},p_{y_{i}})\\}_{i=1}^{B}$ and unlabeled
instances $\mathcal{B}_{u}=\\{\boldsymbol{x}_{i}\\}_{i=1}^{\mu B}$, where
$\mu\geq 1$ is the multiplicity of unlabeled over labeled instances in each
batch. Here, we consider degenerate distributions $p_{y_{i}}$ as target
information in $\mathcal{B}_{l}$. For the instances
$(\boldsymbol{x},p_{y})\in\mathcal{B}_{l}$, we compute the Kullback-Leibler
divergence $D_{KL}(p_{y}\,||\,\hat{p}(\boldsymbol{x}))$ as loss
$\mathcal{L}_{l}$.

For the unlabeled instances $\boldsymbol{x}\in\mathcal{B}_{u}$, we derive
conformal predictions in an inductive manner based on a previously separated
calibration dataset $\mathcal{D}_{\text{calib}}$. To this end, a (strongly
valid) possibility distribution $\pi$ over all possible labels
$y\in\mathcal{Y}$ is determined for the prediction $\hat{p}(\boldsymbol{x})$,
which is used to construct a credal target set $\mathcal{Q}_{\pi}$ according
to (1). Finally, $\mathcal{Q}_{\pi}$ is compared to the prediction
$\hat{p}(\boldsymbol{x})$ in terms of a generalized probabilistic loss
$\mathcal{L}^{*}:2^{\mathbb{P}(\mathcal{Y})}\times\mathbb{P}(\mathcal{Y})\longrightarrow\mathbb{R}_{+}$,
which we shall detail in Section 4.2.

Altogether, the training objective is given by

$\mathcal{L}=\underbrace{\frac{1}{|\mathcal{B}_{l}|}\sum_{(\boldsymbol{x}_{i},p_{y_{i}})\in\mathcal{B}_{l}}D_{KL}(p_{y_{i}}\,||\,\hat{p}(\boldsymbol{x}_{i}))}_{\mathcal{L}_{l}}\,+\,\lambda_{u}\underbrace{\frac{1}{|\mathcal{B}_{u}|}\sum_{\boldsymbol{x}_{i}\in\mathcal{B}_{u}}\mathcal{L}^{*}(Q_{\pi_{i}},\hat{p}(\boldsymbol{x}_{i}))}_{\mathcal{L}_{u}}\enspace,$
(10)

where $\lambda_{u}\geq 0$ weights the importance of the unlabeled loss part
$\mathcal{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.

###  4.2 Generalized Credal Learning

As set-valued targets are provided as (pseudo-)supervision for the unlabeled
instances, a generalization of a single-point probability loss $\mathcal{L}$
is required. Here, we follow [42] and leverage a generalized empirical risk
minimization approach by minimizing the optimistic superset loss [9, 30]

$\mathcal{L}^{*}(\mathcal{Q}_{\pi},\hat{p}):=\min_{p\in\mathcal{Q}_{\pi}}\mathcal{L}(p,\hat{p})\enspace,$
(11)

with $\mathcal{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 $\mathcal{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 $\pi$ and denote
$\pi_{i}:=\pi(y_{i})$. Without loss of generality, let the possibilities be
ordered, i.e., $0\leq\pi_{1}\leq\ldots,\leq\pi_{K}=1$. Then, it has been shown
that the following holds for any distribution $p\in\mathcal{Q}_{\pi}$ with
$p_{i}:=p(y_{i})$ [17]:

$p\in\mathcal{Q}_{\pi}\Leftrightarrow\sum_{k=1}^{i}p_{k}\leq\pi_{i}\enspace,\qquad
i\in\\{1,...,K\\}$ (12)

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 $\mathcal{Q}_{\pi}$) with minimal
distance to a given query point ($\hat{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

0: Predicted distribution $\hat{p}\in\mathbb{P}(\mathcal{Y})$, (normalized)
possibility distribution $\pi:\mathcal{Y}\longrightarrow[0,1]$

if $\hat{p}\in\mathcal{Q}_{\pi}$ then return $D_{KL}(\hat{p}\,||\,\hat{p})=0$

Initialize set of unassigned classes $Y=\mathcal{Y}$

while $Y$ is not empty do

Determine $y^{*}\in Y$ with highest $\pi(y^{*})$, such that the probabilities
$\bar{p}(y)=\left(\pi(y^{*})-\sum_{y^{\prime}\notin
Y}p^{r}(y^{\prime})\right)\cdot\frac{\hat{p}(y)}{\sum_{y^{\prime}\in
Y^{\prime}}\hat{p}(y^{\prime})}$ for all $y\in Y^{\prime}:=\\{y\in
Y\,|\,\pi(y)\leq\pi(y^{*})\\}$ do not violate the constraints in Eq. 12

Assign $p^{r}(y)=\bar{p}(y)$ for all $y\in Y^{\prime}$

$Y=Y\setminus Y^{\prime}$

end while

return $D_{KL}(p^{r}\,||\,\hat{p})$

Algorithm 1 lists the procedure to determine the loss
$\mathcal{L}^{*}(\mathcal{Q}_{\pi},\hat{p})$. The key idea is to consider each
face of the convex polytope being associated with a particular possibility
constraint $\pi_{i}$. The algorithm then determines the optimal face on which
the prediction $\hat{p}$ can be projected without violating the constraint for
any $\pi_{j}\leq\pi_{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\in\mathcal{Q}_{\pi}$ with minimal
$D_{KL}$ to $\hat{p}$. Hence, we can state the following theorem.

######  Theorem 4.1 (Optimality).

Given a credal set $\mathcal{Q}_{\pi}$ induced by a normalized possibility
distribution $\pi:\mathcal{Y}\longrightarrow[0,1]$ with
$\max_{y\in\mathcal{Y}}\pi(y)=1$ according to (1), Algorithm 1 returns the
solution of $\mathcal{L}^{*}(\mathcal{Q}_{\pi},\hat{p})$ as defined in (11)
for an arbitrary distribution $\hat{p}\in\mathbb{P}(\mathcal{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.

###  4.3 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 state-of-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
$\boldsymbol{x}\in\mathcal{X}$ is augmented by a weak (e.g., horizontal
flipping) and a strong (e.g., RandAugment [16] or CTAugment [6]) augmentation
policy $\mathcal{A}_{w}:\mathcal{X}\longrightarrow\mathcal{X}$ and
$\mathcal{A}_{s}:\mathcal{X}\longrightarrow\mathcal{X}$, respectively. The
strongly-augmented representation $\mathcal{A}_{s}(\boldsymbol{x})$ is then
used to construct a pseudo-label based on
$\hat{p}(\mathcal{A}_{s}(\boldsymbol{x}))$, which is finally compared to
$\hat{p}(\mathcal{A}_{w}(\boldsymbol{x}))$ to compute the loss.

In our approach, we adopt this scheme for spatial input domains $\mathcal{X}$
such as images. As the uncertainty quantification in the inductive conformal
prediction procedure is conducted to construct a pseudo-label on
$\mathcal{A}_{s}(\boldsymbol{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.

##  5 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.

###  5.1 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 C2S2L, we distinguish two variants employing either the non-conformity
measure (2) or (3), which we refer to as C2S2L-diff and C2S2L-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.

###  5.2 Generalization Performance

Table 1: Averaged accuracies over $3$ seeds for different numbers of labels.
Bold entries indicate the best performing method per column.

| CIFAR-10 | CIFAR-100 | SVHN | STL-10
---|---|---|---|---
| 40 lab. | 250 lab. | 4000 lab. | 400 lab. | 2500 lab. | 10000 lab. | 40 lab. | 250 lab. | 1000 lab. | 1000 lab.
UDA | 86.44 $\pm$2.70 |  94.81 $\pm$0.22 | 95.31 $\pm$0.10 | 49.41 $\pm$2.96 | 68.33 $\pm$0.31 | 75.98 $\pm$0.45 | 84.82 $\pm$10.6 | 96.41 $\pm$1.04 | 97.14 $\pm$0.24 | 83.94 $\pm$1.49
FixMatch | 87.14 $\pm$2.61 | 93.81 $\pm$1.02 | 95.08 $\pm$0.18 | 47.73 $\pm$1.88 | 66.82 $\pm$0.26 | 76.66 $\pm$0.18 | 86.26 $\pm$14.2 | 96.23 $\pm$1.50 |  97.32 $\pm$0.09 | 85.34 $\pm$0.92
FixMatch DA | 89.54 $\pm$5.90 | 94.00 $\pm$0.56 | 95.13 $\pm$0.21 | 51.31 $\pm$2.67 | 69.98 $\pm$0.30 | 76.67 $\pm$0.08 | 86.00 $\pm$16.3 | 95.85 $\pm$1.62 | 97.02 $\pm$0.16 | 85.59 $\pm$1.21
FlexMatch | 91.21 $\pm$3.46 | 94.08 $\pm$0.64 | 94.62 $\pm$0.27 | 49.99 $\pm$0.39 |  71.47 $\pm$1.06 | 77.01 $\pm$0.17 | 85.78 $\pm$1.37 | 96.52 $\pm$0.29 | 96.54 $\pm$0.30 | 85.24 $\pm$1.49
CSSL |  91.70 $\pm$4.77 | 94.59 $\pm$0.15 | 95.41 $\pm$0.04 | 52.54 $\pm$1.60 | 67.81 $\pm$0.64 | 77.56 $\pm$0.22 |  87.27 $\pm$5.69 | 95.54 $\pm$1.63 | 96.69 $\pm$0.75 | 85.07 $\pm$1.11
C2S2L-diff | 90.13 $\pm$3.33 | 93.56 $\pm$0.21 | 95.43 $\pm$0.06 |  54.13 $\pm$1.97 | 69.33 $\pm$0.78 | 77.40 $\pm$0.18 | 86.52 $\pm$6.84 | 95.67 $\pm$1.51 | 96.97 $\pm$0.23 | 85.26 $\pm$0.79
C2S2L-prop | 89.24 $\pm$2.56 | 94.34 $\pm$0.27 |  95.48 $\pm$0.06 | 53.48 $\pm$2.75 | 67.90 $\pm$0.37 |  77.72 $\pm$0.08 | 85.38 $\pm$7.67 |  96.87 $\pm$0.20 | 97.04 $\pm$0.38 |  85.67 $\pm$1.14

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.

As can be seen, C2S2L 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, C2S2L appears to
be superior compared to CSSL.

###  5.3 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
$\mathbbm{1}(\pi(y)\leq\delta)$ given the pseudo-supervisions $\pi$ for the
unlabeled training instances with true labels $y$ (for confidence levels
$\delta\in\\{0.05,0.1,0.25\\}$). To ensure fairness, we compute these scores
for trained models so as not to give an advantage to C2S2L, which can in
contrast to CSSL rely on the strong validity guarantee throughout the
training.

As shown in Table 2, the two variants of C2S2L 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, C2S2L-prop leads to
better calibrated credal sets compared to C2S2L-diff.

Table 2: The final validity as specified in Eq. 8 of all credal pseudo-labels
for different confidences $\delta$ averaged over $3$ random seeds. Bold
entries indicate the best method per column, the standard deviation is a
factor of $1e^{-3}$.

| CIFAR-10 | SVHN
---|---|---
| 250 lab. | 1000 lab. | 250 lab. | 1000 lab.
$\delta$ | $0.05$ | $0.1$ | $0.25$ | $0.05$ | $0.1$ | $0.25$ | $0.05$ | $0.1$ | $0.25$ | $0.05$ | $0.1$ | $0.25$
CSSL | 0.027 $\pm$0.6 | 0.033 $\pm$1.1 |  0.042 $\pm$0.7 | 0.033 $\pm$1.1 | 0.037 $\pm$4.8 | 0.042 $\pm$1.1 | 0.038 $\pm$0.6 | 0.044 $\pm$1.4 | 0.053 $\pm$0.8 | 0.030 $\pm$1.6 | 0.034 $\pm$6.1 | 0.040 $\pm$2.1
C2S2L-diff | 0.026 $\pm$2.9 | 0.032 $\pm$1.9 | 0.047 $\pm$4.7 | 0.029 $\pm$1.5 | 0.034 $\pm$1.5 | 0.042 $\pm$0.6 | 0.028 $\pm$1.0 | 0.035 $\pm$1.1 | 0.042 $\pm$1.3 | 0.024 $\pm$1.2 | 0.028 $\pm$1.6 | 0.032 $\pm$1.2
C2S2L-prop |  0.022 $\pm$2.1 |  0.031 $\pm$1.5 | 0.043 $\pm$1.7 |  0.024 $\pm$2.7 |  0.029 $\pm$3.4 |  0.039 $\pm$1.9 |  0.014 $\pm$1.1 |  0.020 $\pm$1.1 |  0.024 $\pm$0.3 |  0.021 $\pm$1.1 |  0.023 $\pm$2.7 |  0.029 $\pm$1.5

Figure 2: The credal set efficiency in terms of the mean possibilities $\pi$
for each class, averaged over all pseudo-labels in each iteration for all $3$
seeds.

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 C2S2L over the course of the training. As can be seen, C2S2L 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 C2S2L.

##  6 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 guarantees 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 $\boldsymbol{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.

## Acknowledgments and Disclosure of Funding

This work was partially supported by the German Research Foundation (DFG)
within the Collaborative Research Center “On-The-Fly Computing” (CRC 901
project no. 160364472). Moreover, the authors gratefully acknowledge the
funding of this project by computing time provided by the Paderborn Center for
Parallel Computing (PC2).

## References

  * [1] Eric Arazo, Diego Ortego, Paul Albert, Noel E. O’Connor, and Kevin McGuinness.  Pseudo-labeling and confirmation bias in deep semi-supervised learning.  In Proc. of the International Joint Conference on Neural Networks, IJCNN, Glasgow, United Kingdom, July 19-24, pages 1–8. IEEE, 2020\.
  * [2] Philip Bachman, Ouais Alsharif, and Doina Precup.  Learning with pseudo-ensembles.  In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems, NIPS, Montreal, Quebec, Canada, December 8-13, pages 3365–3373, 2014.
  * [3] Sohail Bahmani and Bhiksha Raj.  A unifying analysis of projected gradient descent for $\ell_{p}$-constrained least squares.  CoRR, abs/1107.4623, 2011.
  * [4] Vineeth Balasubramanian, Shen-Shyang Ho, and Vladimir Vovk.  Conformal Prediction for Reliable Machine Learning: Theory, Adaptations and Applications.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 2014\.
  * [5] Anthony Bellotti.  Approximation to object conditional validity with inductive conformal predictors.  In Lars Carlsson, Zhiyuan Luo, Giovanni Cherubin, and Khuong An Nguyen, editors, Conformal and Probabilistic Prediction and Applications, virtual, September 8-10, volume 152 of Proceedings of Machine Learning Research, pages 4–23. PMLR, 2021.
  * [6] David Berthelot, Nicholas Carlini, Ekin D. Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel.  ReMixMatch: Semi-supervised learning with distribution matching and augmentation anchoring.  In Proc. of the 8th International Conference on Learning Representations, ICLR, Addis Ababa, Ethiopia, April 26-30. OpenReview.net, 2020\.
  * [7] David Berthelot, Nicholas Carlini, Ian J. Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raffel.  MixMatch: A holistic approach to semi-supervised learning.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurIPS, Vancouver, BC, Canada, December 8-14, pages 5050–5060, 2019.
  * [8] Lukas Biewald.  Experiment tracking with weights and biases, 2020.  Software available from wandb.com.
  * [9] Vivien Cabannes, Alessandro Rudi, and Francis R. Bach.  Structured prediction with partial labelling through the infimum loss.  In Proceedings of the 37th International Conference on Machine Learning, ICML, virtual, July 13-18, volume 119, pages 1230–1239. PMLR, 2020\.
  * [10] Zongsheng Cao, Qianqian Xu, Zhiyong Yang, Xiaochun Cao, and Qingming Huang.  Dual quaternion knowledge graph embeddings.  In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI, Virtual Event, February 2-9, pages 6894–6902. AAAI Press, 2021.
  * [11] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021, pages 9630–9640. IEEE, 2021.
  * [12] Leonardo Cella and Ryan Martin.  Valid inferential models for prediction in supervised learning problems.  In International Symposium on Imprecise Probability: Theories and Applications, ISIPTA, Granada, Spain, July 6-9, volume 147 of Proceedings of Machine Learning Research, pages 72–82. PMLR, 2021.
  * [13] Leonardo Cella and Ryan Martin.  Validity, consonant plausibility measures, and conformal prediction.  Int. J. Approx. Reason., 141:110–130, 2022.
  * [14] Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien.  Semi-Supervised Learning.  The MIT Press, 2006.
  * [15] Adam Coates, Andrew Y. Ng, and Honglak Lee.  An analysis of single-layer networks in unsupervised feature learning.  In Proc. of the 14th International Conference on Artificial Intelligence and Statistics, AISTATS, Fort Lauderdale, FL, USA, April 11-13, volume 15 of JMLR Proceedings, pages 215–223. JMLR.org, 2011\.
  * [16] Ekin Dogus Cubuk, Barret Zoph, Jon Shlens, and Quoc Le.  RandAugment: Practical automated data augmentation with a reduced search space.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, virtual, December 6-12, 2020.
  * [17] M. Delgado and S. Moral.  On the concept of possibility-probability consistency.  Fuzzy Sets and Systems, 21(3):311–318, 1987.
  * [18] Caglar Demir, Julian Lienen, and Axel-Cyrille Ngonga Ngomo.  Kronecker decomposition for knowledge graph embeddings.  2022\.
  * [19] Caglar Demir, Diego Moussallem, Stefan Heindorf, and Axel-Cyrille Ngonga Ngomo.  Convolutional hypercomplex embeddings for link prediction.  In Proc. of The 13th Asian Conference on Machine Learning, ACML, virtual, November 17-19, volume 157 of Proceedings of Machine Learning Research, pages 656–671. PMLR, 2021.
  * [20] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel.  Convolutional 2d knowledge graph embeddings.  In Proc. of the Thirty-Second AAAI Conference on Artificial Intelligence, the 30th innovative Applications of Artificial Intelligence, and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence, New Orleans, Louisiana, USA, February 2-7, pages 1811–1818. AAAI Press, 2018.
  * [21] Carl Doersch, Abhinav Gupta, and Alexei A. Efros.  Unsupervised visual representation learning by context prediction.  In Proc. of the IEEE International Conference on Computer Vision, ICCV, Santiago, Chile, December 7-13, pages 1422–1430. IEEE Computer Society, 2015.
  * [22] Jingfei Du, Edouard Grave, Beliz Gunel, Vishrav Chaudhary, Onur Celebi, Michael Auli, Veselin Stoyanov, and Alexis Conneau.  Self-training improves pre-training for natural language understanding.  In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021, pages 5408–5418. Association for Computational Linguistics, 2021.
  * [23] Didier Dubois and Henri Prade.  Possibility theory, probability theory and multiple-valued logics: A clarification.  Annals of Mathematics and Artificial Intelligence, 32:35–66, 2004\.
  * [24] Marguerite Frank and Philip Wolfe.  An algorithm for quadratic programming.  Naval Research Logistics Quarterly, 3:95–110, 1956.
  * [25] Yarin Gal and Zoubin Ghahramani.  Dropout as a Bayesian approximation: Representing model uncertainty in deep learning.  In Proc. of the 33nd International Conference on Machine Learning, ICML, New York City, NY, USA, June 19-24, volume 48 of JMLR Workshop and Conference Proceedings, pages 1050–1059. JMLR.org, 2016\.
  * [26] Golnaz Ghiasi, Tsung-Yi Lin, and Quoc V. Le.  DropBlock: A regularization method for convolutional networks.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS, Montreal, Quebec, Canada, December 3-8, pages 10750–10760, 2018.
  * [27] Clément Godard, Oisin Mac Aodha, Michael Firman, and Gabriel J. Brostow.  Digging into self-supervised monocular depth estimation.  In Proc. of the IEEE/CVF International Conference on Computer Vision, ICCV, Seoul, Korea (South), October 27 - November 2, pages 3827–3837. IEEE, 2019.
  * [28] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko.  Bootstrap your own latent - A new approach to self-supervised learning.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, virtual, December 6-12, 2020.
  * [29] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d’Amato, Gerard de Melo, Claudio Gutierrez, José Emilio Labra Gayo, Sabrina Kirrane, Sebastian Neumaier, Axel Polleres, et al.  Knowledge graphs.  arXiv preprint arXiv:2003.02320, 2020.
  * [30] Eyke Hüllermeier and Weiwei Cheng.  Superset learning based on generalized loss minimization.  In Proc. of the European Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD, Porto, Portugal, September 7-11, Proc. Part II, volume 9285 of LNCS, pages 260–275. Springer, 2015\.
  * [31] Eyke Hüllermeier and Willem Waegeman.  Aleatoric and epistemic uncertainty in machine learning: an introduction to concepts and methods.  Mach. Learn., 110(3):457–506, 2021.
  * [32] Martin Jaggi.  Revisiting frank-wolfe: Projection-free sparse convex optimization.  In Proc. of the 30th International Conference on Machine Learning, ICML, Atlanta, GA, USA, June 16-21, volume 28 of JMLR Workshop and Conference Proceedings, pages 427–435. JMLR.org, 2013.
  * [33] Ulf Johansson, Ernst Ahlberg, Henrik Boström, Lars Carlsson, Henrik Linusson, and Cecilia Sönströd.  Handling small calibration sets in mondrian inductive conformal regressors.  In Proc. of the Statistical Learning and Data Sciences - Third International Symposium, SLDS, Egham, UK, April 20-23, volume 9047 of Lecture Notes in Computer Science, pages 271–280. Springer, 2015.
  * [34] Byol Kim, Chen Xu, and Rina Foygel Barber.  Predictive inference is free with the jackknife+-after-bootstrap.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, virtual, December 6-12, 2020.
  * [35] Kyungyul Kim, Byeongmoon Ji, Doyoung Yoon, and Sangheum Hwang.  Self-knowledge distillation with progressive refinement of targets.  In 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021, pages 6547–6556. IEEE, 2021.
  * [36] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, Toronto, Canada, 2009.
  * [37] Tomáš Kroupa.  How many extreme points does the set of probabilities dominated by a possibility measure have.  In Proc. of 7th Workshop on Uncertainty Processing WUPES, volume 6, pages 89–95, 2006.
  * [38] Dong-Hyun Lee.  Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks.  In Workshop on Challenges in Representation Learning, International Conference on Machine Learning, ICML, Atlanta, GA, USA, June 16-21, volume 3, 2013.
  * [39] Jing Lei, Max G’Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman.  Distribution-free predictive inference for regression.  Journal of the American Statistical Association, 113(523):1094–1111, 2018.
  * [40] Lisha Li, Kevin G. Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar.  Hyperband: A novel bandit-based approach to hyperparameter optimization.  J. Mach. Learn. Res., 18:185:1–185:52, 2017.
  * [41] Yan Li, Xiaofeng Cao, and Honghui Chen.  Fully projection-free proximal stochastic gradient method with optimal convergence rates.  IEEE Access, 8:165904–165912, 2020.
  * [42] Julian Lienen and Eyke Hüllermeier.  Credal self-supervised learning.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, virtual, December 6-14, pages 14370–14382, 2021.
  * [43] Julian Lienen and Eyke Hüllermeier.  From label smoothing to label relaxation.  In Proc. of the 35th AAAI Conference on Artificial Intelligence, virtual, February 2-9, 2021.
  * [44] Julian Lienen and Eyke Hüllermeier.  Instance weighting through data imprecisiation.  Int. J. Approx. Reason., 134:1–14, 2021.
  * [45] Ilya Loshchilov and Frank Hutter.  SGDR: Stochastic gradient descent with warm restarts.  In Proc. of the 5th International Conference on Learning Representations, ICLR, Toulon, France, April 24-26. OpenReview.net, 2017.
  * [46] Subhabrata Mukherjee and Ahmed Hassan Awadallah.  Uncertainty-aware self-training for few-shot text classification.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, virtual, December 6-12, 2020.
  * [47] Rafael Müller, Simon Kornblith, and Geoffrey E. Hinton.  When does label smoothing help?  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurIPS, Vancouver, BC, Canada, December 8-14, pages 4696–4705, 2019.
  * [48] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng.  Reading digits in natural images with unsupervised feature learning.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NIPS, Granada, Spain, November 12-17, Workshop on Deep Learning and Unsupervised Feature Learning, 2011\.
  * [49] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich.  A review of relational machine learning for knowledge graphs.  Proceedings of the IEEE, 104(1):11–33, 2015.
  * [50] Avital Oliver, Augustus Odena, Colin Raffel, Ekin Dogus Cubuk, and Ian J. Goodfellow.  Realistic evaluation of deep semi-supervised learning algorithms.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS, Montreal, Quebec, Canada, December 3-8, pages 3239–3250, 2018.
  * [51] Harris Papadopoulos.  Inductive conformal prediction: Theory and application to neural networks.  INTECH Open Access Publisher Rijeka, 2008.
  * [52] Harris Papadopoulos, Volodya Vovk, and Alexander Gammerman.  Conformal prediction with neural networks.  In 19th IEEE International Conference on Tools with Artificial Intelligence, ICTAI, Patras, Greece, October 29-31, Volume 2, pages 388–395. IEEE Computer Society, 2007.
  * [53] Hieu Pham, Zihang Dai, Qizhe Xie, and Quoc V. Le.  Meta pseudo labels.  In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pages 11557–11568. Computer Vision Foundation / IEEE, 2021.
  * [54] Zhongzheng Ren, Raymond A. Yeh, and Alexander G. Schwing.  Not all unlabeled data are equal: Learning to weight data in semi-supervised learning.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, virtual, December 6-12, 2020.
  * [55] Mamshad Nayeem Rizve, Kevin Duarte, Yogesh S. Rawat, and Mubarak Shah.  In defense of pseudo-labeling: An uncertainty-aware pseudo-label selection framework for semi-supervised learning.  In Proc. of the 9th International Conference on Learning Representations, ICLR, virtual, May 3-7. OpenReview.net, 2021.
  * [56] Chuck Rosenberg, Martial Hebert, and Henry Schneiderman.  Semi-supervised self-training of object detection models.  In Proc. of the 7th IEEE Workshop on Applications of Computer Vision / IEEE Workshop on Motion and Video Computing, WACV/MOTION, Breckenridge, CO, USA, January 5-7, pages 29–36. IEEE Computer Society, 2005\.
  * [57] Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla.  You CAN teach an old dog new tricks! on training knowledge graph embeddings.  In Proc. of the 8th International Conference on Learning Representations, ICLR, Addis Ababa, Ethiopia, April 26-30. OpenReview.net, 2020\.
  * [58] Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen.  Regularization with stochastic transformations and perturbations for deep semi-supervised learning.  In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems, NIPS, Barcelona, Spain, December 5-10, pages 1163–1171, 2016.
  * [59] Glenn Shafer and Vladimir Vovk.  A tutorial on conformal prediction.  J. Mach. Learn. Res., 9:371–421, 2008.
  * [60] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li.  FixMatch: Simplifying semi-supervised learning with consistency and confidence.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, virtual, December 6-12, 2020.
  * [61] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and Zbigniew Wojna.  Rethinking the Inception architecture for computer vision.  In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR, Las Vegas, NV, USA, June 27-30, pages 2818–2826. IEEE Computer Society, 2016.
  * [62] Jafar Tanha, Maarten van Someren, and Hamideh Afsarmanesh.  Semi-supervised self-training for decision tree classifiers.  Int. J. Mach. Learn. Cybern., 8(1):355–370, 2017.
  * [63] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard.  Complex embeddings for simple link prediction.  In Proc. of the 33nd International Conference on Machine Learning, ICML, New York City, NY, USA, June 19-24, volume 48 of JMLR Workshop and Conference Proceedings, pages 2071–2080. JMLR.org, 2016\.
  * [64] Jesper E. van Engelen and Holger H. Hoos.  A survey on semi-supervised learning.  Mach. Learn., 109(2):373–440, 2020.
  * [65] Vladimir Vovk.  Conditional validity of inductive conformal predictors.  Mach. Learn., 92(2-3):349–376, 2013.
  * [66] Vladimir Vovk, Alex Gammerman, and Glenn Shafer.  Algorithmic Learning in a Random World.  Springer-Verlag, Berlin, Heidelberg, 2005.
  * [67] Qizhe Xie, Zihang Dai, Eduard H. Hovy, Thang Luong, and Quoc Le.  Unsupervised data augmentation for consistency training.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, virtual, December 6-12, 2020.
  * [68] Qizhe Xie, Minh-Thang Luong, Eduard H. Hovy, and Quoc V. Le.  Self-training with noisy student improves imagenet classification.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 10684–10695. Computer Vision Foundation / IEEE, 2020.
  * [69] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.  Embedding entities and relations for learning and inference in knowledge bases.  arXiv preprint arXiv:1412.6575, 2014.
  * [70] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  In Proc. of the British Machine Vision Conference, BMVC, York, UK, September 19-22, 2016.
  * [71] Gianluca Zeni, Matteo Fontana, and Simone Vantini.  Conformal prediction: a unified review of theory and new challenges.  CoRR, abs/2005.07972, 2020.
  * [72] Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki.  Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, virtual, December 6-14, pages 18408–18419, 2021.
  * [73] Zhedong Zheng and Yi Yang.  Rectifying pseudo label learning via uncertainty estimation for domain adaptive semantic segmentation.  Int. J. Comput. Vis., 129(4):1106–1120, 2021.
  * [74] Damjan Škulj.  Normal cones corresponding to credal sets of lower probabilities, 2022\.

##  Appendix A Appendix

###  A.1 Pseudo-Code of C2S2L

Algorithm 2 C2S2L with consistency regularization

0: Batch of labeled instances with degenerate ground truth distributions
$\mathcal{B}_{l}=\\{(\boldsymbol{x}_{i},p_{i})\\}_{i=1}^{B}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{B}$,
unlabeled batch ratio $\mu$, batch
$\mathcal{B}_{u}=\\{\boldsymbol{x}_{i}\\}_{i=1}^{\mu B}$ of unlabeled
instances, unlabeled loss weight $\lambda_{u}$, model
$\hat{p}:\mathcal{X}\longrightarrow\mathbb{P}(\mathcal{Y})$, strong and weak
augmentation functions
$\mathcal{A}_{s},\mathcal{A}_{w}:\mathcal{X}\longrightarrow\mathcal{X}$,
calibration data
$\mathcal{D}_{\text{calib}}\subset(\mathcal{X}\times\mathcal{Y})^{L}$,
inductive conformal prediction procedure
$ICP:(\mathcal{X}\times\mathcal{Y})^{L}\times\mathbb{P}(\mathcal{Y})\longrightarrow(\mathcal{Y}\longrightarrow[0,1])$

1:
$\mathcal{L}_{l}=\frac{1}{B}\sum_{(\boldsymbol{x},p)\in\mathcal{B}_{l}}D_{KL}(p\,||\,\hat{p}(\mathcal{A}_{w}(\boldsymbol{x})))$

2: Initialize pseudo-labeled batch $\mathcal{U}=\emptyset$

3: for all $\boldsymbol{x}\in\mathcal{B}_{u}$ do

4: Derive possibility distribution
$\pi=ICP(\mathcal{D}_{\text{calib}},\hat{p}(\mathcal{A}_{w}(\boldsymbol{x})))$

5: Apply normalization to $\pi$ such that $\max_{y\in\mathcal{Y}}\pi(y)=1$
(e.g., as in Eq. 9)

6: Construct credal set $\mathcal{Q}_{\pi}$ as in Eq. 1

7: $\mathcal{U}=\mathcal{U}\cup\\{(\boldsymbol{x},Q_{\pi})\\}$

8: end for

9: $\mathcal{L}_{u}=\frac{1}{\mu
B}\sum_{(\boldsymbol{x},Q_{\pi})\in\mathcal{U}}\mathcal{L}^{*}(Q_{\pi},\hat{p}(\mathcal{A}_{s}(\boldsymbol{x})))$
{Can be solved via generalized credal learning procedure (Alg. 1 in main
paper)}

10: return $\mathcal{L}_{l}+\lambda_{u}\mathcal{L}_{u}$

###  A.2 Experimental Details

####  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 optimization111We used the
Bayesian optimization implementation as offered by Weights & Biases [8] with
default parameters. with $20$ runs for each combination of dataset and number
of labels on a separate validation split. Moreover, we use Hyperband [40] with
$\eta=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: Hyperparameter search spaces considered in the optimization. Method | Parameter | Values
---|---|---
All | Initial learning rate | $\\{0.005,0.01,0.03,0.05,0.1\\}$
Unlabeled batch multiplicity $\mu$ | $\\{3,7\\}$
Weight decay | $\\{0.0005,0.0001\\}$
Unlabeled loss weight $\lambda_{u}$ | $\\{1\\}$
FixMatch (DA), UDA | Confidence threshold $\tau$ | $\\{0.7,0.8,0.9,0.95\\}$
Temperature | $\\{0.5,1\\}$
FlexMatch | Cutoff threshold | $\\{0.8,0.9,0.95\\}$
Threshold warmup | $\\{\text{True},\text{False}\\}$
C2S2L-diff | Calibration split | $\\{0.1,0.25,0.5\\}$
C2S2L-prop | Calibration split | $\\{0.1,0.25,0.5\\}$
Non-conf. sensitivity $\gamma$ | $\\{0.01,0.1,1\\}$

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 PyTorch222https://pytorch.org/, BSD-style
license, where we reused the official implementations if available. We
proceeded from a popular FixMatch re-implementation in
PyTorch333https://github.com/kekmodel/FixMatch-pytorch, MIT license 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 Additional Results

####  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 C2S2L variants
demonstrate favorable calibration properties, whereas C2S2L-prop often
outperforms all other methods.

Table 4: Averaged ECE scores with $15$ bins over $3$ seeds for different
numbers of labels. Bold entries indicate the best performing method per
column. The standard deviation is a factor of $1e^{-2}$.

| CIFAR-10 | CIFAR-100 | SVHN | STL-10
---|---|---|---|---
| 40 lab. | 250 lab. | 4000 lab. | 400 lab. | 2500 lab. | 10000 lab. | 40 lab. | 250 lab. | 1000 lab. | 1000 lab.
UDA | 0.159 $\pm$7.9 |  0.051 $\pm$0.2 | 0.046 $\pm$0.1 | 0.420 $\pm$2.6 | 0.232 $\pm$0.5 | 0.173 $\pm$0.5 | 0.124 $\pm$1.1 | 0.037 $\pm$1.3 | 0.030 $\pm$0.1 | 0.140 $\pm$0.9
FixMatch | 0.136 $\pm$4.3 | 0.059 $\pm$1.0 | 0.048 $\pm$0.1 | 0.417 $\pm$2.3 | 0.254 $\pm$0.5 | 0.168 $\pm$0.1 | 0.275 $\pm$34.9 | 0.038 $\pm$1.3 |  0.027 $\pm$0.1 | 0.128 $\pm$0.8
FixMatch DA | 0.131 $\pm$11.1 | 0.057 $\pm$0.6 | 0.047 $\pm$0.1 |  0.347 $\pm$2.4 | 0.234 $\pm$0.4 | 0.169 $\pm$0.1 |  0.101 $\pm$3.1 | 0.041 $\pm$1.5 | 0.029 $\pm$0.1 | 0.127 $\pm$0.8
FlexMatch | 0.114 $\pm$3.7 | 0.057 $\pm$0.5 | 0.052 $\pm$0.2 | 0.404 $\pm$0.3 | 0.232 $\pm$0.5 | 0.169 $\pm$0.2 | 0.126 $\pm$1.3 | 0.039 $\pm$0.3 | 0.033 $\pm$0.4 | 0.130 $\pm$0.9
CSSL |  0.079 $\pm$4.4 | 0.053 $\pm$0.1 | 0.045 $\pm$0.0 | 0.368 $\pm$0.8 | 0.233 $\pm$0.6 | 0.167 $\pm$0.2 | 0.121 $\pm$5.1 | 0.041 $\pm$1.1 | 0.032 $\pm$0.1 | 0.126 $\pm$0.9
C2S2L-diff | 0.139 $\pm$3.2 | 0.058 $\pm$0.1 | 0.045 $\pm$0.1 | 0.352 $\pm$1.6 |  0.222 $\pm$0.3 | 0.165 $\pm$0.1 | 0.117 $\pm$7.2 | 0.044 $\pm$1.2 | 0.030 $\pm$0.3 | 0.129 $\pm$0.6
C2S2L-prop | 0.101 $\pm$2.2 | 0.054 $\pm$0.2 |  0.044 $\pm$0.1 |  0.347 $\pm$2.3 | 0.227 $\pm$0.2 |  0.162 $\pm$0.2 | 0.128 $\pm$8.6 |  0.033 $\pm$0.1 | 0.028 $\pm$0.2 |  0.124 $\pm$0.8

####  A.3.2 Learning Curves

Figure 3: Test accuracies over the course of the training. The results are
averaged over $3$ different random seeds.

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, C2S2L-prop shows a similar training
efficiency as CSSL, whereas C2S2L-diff realizes a more cautious learning than
all other methods. This becomes particularly visible for SVHN. Here,
C2S2L-prop shows an even improved training efficiency compared to CSSL.
Remarkably, the C2S2L 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 C2S2L-diff in the first iterations. Together with the
validity gains in the pseudo-label quality, especially C2S2L-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 C2S2L more thoroughly. If not stated otherwise, we set the
initial learning rate to $0.03$, $\lambda_{u}=1$, $\mu=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 $\pi:\mathcal{Y}\longrightarrow[0,1]$ to satisfy
$\max_{y\in\mathcal{Y}}\pi(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:

$\pi(\hat{y})=\left\\{\begin{array}[]{cl}1&\text{if
}\hat{y}=\operatorname*{argmax}_{y^{\prime}\in\mathcal{Y}}\pi(y^{\prime}),\\\
\pi(\hat{y})&\text{otherwise.}\end{array}\right.$ (13)

It is easy to see that (13) leads to smaller credal sets due to
$0\leq\pi(\cdot)\leq 1$.

Table 5: Test accuracies per normalization and C2S2L variant for $250$ labels each. The presented results and their standard deviations are computed over $3$ seeds. | CIFAR-10 | SVHN
---|---|---
| Norm. 1 | Norm. 2 | Norm. 1 | Norm. 2
C2S2L-diff | 92.38 $\pm$1.14 | 92.71 $\pm$0.81 | 95.93 $\pm$1.78 | 95.70 $\pm$1.81
C2S2L-prop | 92.26 $\pm$2.30 | 91.84 $\pm$1.13 | 96.61 $\pm$1.08 | 95.72 $\pm$1.50

LABEL:table:abl:normalization 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
C2S2L by default.

Figure 4: Test accuracy and the standard deviation per calibration size for
the two variants of C2S2L. 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, C2S2L-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
$\alpha(\mathcal{D},(\boldsymbol{x},y))$ in Eq. 3 involves the parameter
$\gamma\geq 0$, which represents the sensitivity towards the influence of the
prediction $\hat{p}_{\mathcal{D}}(\boldsymbol{x})(y)$ on the scoring for a
given tuple $(\boldsymbol{x},y)$.

Table 6: Averaged test accuracies and their standard deviations over $3$ random seeds for various $\gamma$ values used in C2S2L-prop. For each dataset, we considered $250$ labeled examples to be given. $\gamma$ | CIFAR-10 | SVHN
---|---|---
$0.01$ |  93.64 $\pm$0.33 | 95.60 $\pm$2.17
$0.1$ | 93.24 $\pm$1.16 | 95.91 $\pm$1.76
$0.5$ | 93.19 $\pm$1.02 |  96.82 $\pm$0.10
$1$ | 93.01 $\pm$1.23 | 96.61 $\pm$0.08
$10$ | 92.29 $\pm$1.94 | 95.41 $\pm$2.07

In LABEL:table:abl:sensitivity, we report results of C2S2L-prop for
$\gamma\in\\{0.01,0.1,0.5,1,10\\}$. While smaller $\gamma$ values lead to
better results for CIFAR-10, SVHN benefits from slightly higher $\gamma$
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 C2S2L-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.

Table 7: Overview of the datasets considered in the KGE experiments. | # Entities | # Relations | $|\mathcal{D}_{\text{train}}|$ | $|\mathcal{D}_{\text{val}}|$ | $|\mathcal{D}_{\text{test}}|$
---|---|---|---|---|---
UMLS | 136 | 93 | 10,432 | 1,304 | 1,965
KINSHIP | 105 | 51 | 17,088 | 2,136 | 3,210

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 C2S2L-diff, we initially divided
$\mathcal{D}_{\text{train}}$ into training, calibration and unlabeled splits
with 40:40:20 ratios, respectively. For the conventional pseudo-labeling
procedure, we divided $\mathcal{D}_{\text{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, C2S2L 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.

##### Link Prediction Results

Table LABEL:table:umls_kinship_1vsall reports the link prediction performance
on UMLS and KINSHIP. Overall, the results suggest that incorporating C2S2L 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 8: Link prediction results on UMLS and KINSHIP. The 40:40:20 split ratio for C2S2L-diff and a 40:60 for conventional pseudo-labeling (PL). Bold entries denote best results per method, dataset and metric. | UMLS | KINSHIP
---|---|---
| MRR | H@1 | H@3 | MRR | H@1 | H@3
DistMult-PL | 0.229 | 0.128 | 0.243 | 0.262 | 0.160 | 0.284
DistMult-C2S2L | 0.246 | 0.161 | 0.265 | 0.274 | 0.170 | 0.299
ComplEx-PL | 0.282 | 0.160 | 0.358 | 0.333 | 0.226 | 0.382
ComplEx-C2S2L | 0.253 | 0.191 | 0.261 | 0.344 | 0.255 | 0.381
QMult-PL | 0.269 | 0.157 | 0.309 | 0.323 | 0.228 | 0.351
QMult-C2S2L | 0.294 | 0.217 | 0.309 | 0.328 | 0.238 | 0.363

Table LABEL:table:umls_kinship_1vsall_40_10_split reports the link prediction
performances for the 40:10:50 (C2S2L) 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.

Table 9:  Link prediction results on UMLS and KINSHIP. The 40:10:50 split ratio for C2S2L-diff and a 40:60 for pseudo-labelling (PL). Bold entries denote best results per method, dataset and metric. | UMLS | KINSHIP
---|---|---
| MRR | H@1 | H@3 | MRR | H@1 | H@3
DistMult-PL | 0.229 | 0.128 | 0.243 | 0.262 | 0.160 | 0.284
DistMult-C2S2L | 0.246 | 0.161 | 0.265 | 0.275 | 0.170 | 0.299
ComplEx-PL | 0.282 | 0.160 | 0.358 | 0.333 | 0.226 | 0.382
ComplEx-C2S2L | 0.253 | 0.191 | 0.261 | 0.335 | 0.232 | 0.378
QMult-PL | 0.269 | 0.157 | 0.309 | 0.323 | 0.228 | .351
QMult-C2S2L | 0.294 | 0.217 | 0.309 | 0.328 | 0.238 | 0.363
Table 10:  Link prediction results on UMLS and KINSHIP. The 30:20:50 split ratio for C2S2L-diff and a 50:50 for pseudo-labelling (PL). Bold entries denote best results per method, dataset and metric. | UMLS | KINSHIP
---|---|---
| MRR | H@1 | H@3 | MRR | H@1 | H@3
DistMult-PL | 0.263 | 0.164 | 0.268 | 0.302 | 0.198 | 0.328
DistMult-C2S2L | 0.240 | 0.161 | 0.253 | 0.245 | 0.140 | 0.267
ComplEx-PL | 0.308 | 0.205 | 0.351 | 0.392 | 0.302 | 0.431
ComplEx-C2S2L | 0.228 | 0.159 | 0.241 | 0.255 | 0.148 | 0.285
QMult-PL | 0.330 | 0.223 | 0.362 | 0.381 | 0.292 | 0.422
QMult-C2S2L | 0.224 | 0.150 | 0.225 | 0.221 | 0.118 | 0.242

Motivated by the findings in the results shown in
LABEL:table:umls_kinship_1vsall and
LABEL:table:umls_kinship_1vsall_40_10_split, we reduced the training set for
C2S2L 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: C2S2L 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.

####  A.4.1 Proof of Theorem 1

Figure 5: Schematic illustration of a credal set $\mathcal{Q}_{\pi}$ as a
convex polytope in a barycentric coordinate space of all distributions
$\mathbb{P}(\mathcal{Y})$ for three and four classes. $\mathcal{Q}_{\pi}$ is
induced by a normalized possibility distribution $\pi$ with
$1=\pi(y_{1})\geq\ldots\geq\pi(y_{K})\geq 0$.

In the following, we consider possibility distributions
$\pi:\mathcal{Y}\longrightarrow[0,1]$, where $\pi_{i}:=\pi(y_{i})$ abbreviates
the possibility of class $y_{i}$. Without loss of generality, we assume the
possibilities be ordered and normalized, i.e.,
$0\leq\pi_{1}\leq\ldots\leq\pi_{K}=1$ for $K$ classes. Furthermore, we also
denote the respective probability of a class $y_{i}$ given a distribution
$p\in\mathbb{P}(\mathcal{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 $\mathcal{Q}_{\pi}$ 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 $\mathcal{Q}_{\pi}$ to a query
distribution $\hat{p}$. In order to proof Theorem 4.1 that states the
optimality of this approach, we will introduce the following three lemmas:

  1. 1.

Termination

  2. 2.

Optimal projection

  3. 3.

Optimal face

######  Lemma A.1 (Termination).

Given a normalized possibility distribution
$\pi:\mathcal{Y}\longrightarrow[0,1]$, Algorithm 1 terminates for an arbitrary
probability distribution $\hat{p}\in\mathbb{P}(\mathcal{Y})$.

###### Proof.

In case of $\hat{p}\in\mathcal{Q}_{\pi}$, we immediately return with a result.
For $\hat{p}\not\in\mathcal{Q}_{\pi}$, we fix the probabilities of all $y\in
Y^{\prime}$ in each iteration of Algorithm 1, which are then removed from $Y$.
Thereby, at least for the class $\bar{y}\in Y$ with smallest possibility
$\pi(\bar{y})$

$\bar{p}(\bar{y})=\left(\pi(\bar{y})-\sum_{y^{\prime}\not\in
Y}p^{r}(y^{\prime})\right)\cdot\frac{\hat{p}(\bar{y})}{\hat{p}(\bar{y})}\leq\pi(\bar{y})$

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^{\prime}=\\{\bar{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}\in\mathbb{P}(\mathcal{Y})$ as determined in Algorithm
1. In this course, $\bar{Y}\subseteq\mathcal{Y}$ denotes the set of arbitrary,
but already fixed probabilities $p^{r}(y)$ for $y\in\bar{Y}$. This set shall
represent classes with optimal probability scores determined in previous
iterations. Without loss of generality, we assume that $\forall
y\in\bar{Y}:\pi(y)\leq\min_{y^{\prime}\in\mathcal{Y}\setminus\bar{Y}}\pi(y^{\prime})$.
Moreover, for a certain possibility degree $\pi_{i}$, let us define the set of
classes with at most $\pi_{i}$ possibility as

$Y_{\pi_{i}}:=\\{y\in\mathcal{Y}\,|\,\pi(y)\leq\pi_{i}\\}\enspace.$ (14)

For the remaining classes in $\mathcal{Y}\setminus\bar{Y}$, let $p^{r}$ be
constructed as follows:

$p^{r}(y)=\begin{cases}\left(\pi_{i}-\sum_{y^{\prime}\in\bar{Y}}p^{r}(y^{\prime})\right)\cdot\frac{\hat{p}(y)}{\sum_{y^{\prime}\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y^{\prime})}&\text{if }y\in
Y_{\pi_{i}}\setminus\bar{Y}\\\
\left(1-\pi_{i}\right)\cdot\frac{\hat{p}(y)}{\sum_{y^{\prime}\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y^{\prime})}&\text{if }y\in\mathcal{Y}\setminus
Y_{\pi_{i}}\end{cases}\,.$ (15)

Moreover, we use the notion of a half space associated with a possibility
constraint $\pi_{i}$, which is defined as follows.

######  Definition 1 (Half-space).

For a possibility constraint $\pi_{i}$ of a (normalized) possibility
distribution $\pi:\mathcal{Y}\longrightarrow[0,1]$ with
$\max_{y\in\mathcal{Y}}\pi(y)=1$, we define

$\text{half-
space}_{\pi_{i}}:=\bigg{\\{}p\in\mathbb{P}(\mathcal{Y})\,|\,\sum_{y\in\mathcal{Y}:\pi(y)\leq\pi_{i}}p(y)=\pi_{i}\bigg{\\}}$

as half-space associated with $\pi_{i}$.

Given distributions $p^{r}$ of the form (15) for a possibility constraint
$\pi_{i}$, which is by construction element of $\text{half-space}_{\pi}$ (due
to $\forall y\in\bar{Y}:\pi(y)\leq\pi_{i}$), we can make the following
statement about its optimality.

######  Lemma A.2 (Optimal projection).

Given a set $\bar{Y}\subseteq\mathcal{Y}$ of classes with arbitrarily fixed
probabilities, a (normalized) possibility distribution
$\pi:\mathcal{Y}\longrightarrow[0,1]$ with $\max_{y\in\mathcal{Y}}\pi(y)=1$
and the set $\text{half-space}_{\pi_{i}}$, the projection
$p^{r}(y)\in\text{half-space}_{\pi_{i}}$ as defined before is optimal in the
sense that $\nexists p\in\text{half-space}_{\pi_{i}}$ with
$p(y)=p^{r}(y)\,\forall y\in\bar{Y}$ for which $\exists y\in
Y_{\pi_{i}}\setminus\bar{Y}:p(y)\neq p^{r}(y)$ such that
$D_{KL}(p\,||\,\hat{p})<D_{KL}(p^{r}\,||\,\hat{p})$.

###### Proof.

Let us define $A:=\sum_{y\in\bar{Y}}p^{r}(y)$ as the sum of the (previously)
fixed probabilities. From the definition of $p^{r}$, we know:

$\displaystyle\begin{split}D_{KL}(p^{r}\,||\,\hat{p})&=\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\frac{(1-\pi_{i})\hat{p}(y)}{\sum_{y^{\prime}\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y^{\prime})}\log\frac{\frac{(1-\pi_{i})\hat{p}(y)}{\sum_{y^{\prime}\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y^{\prime})}}{\hat{p}(y)}\\\ &\quad+\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}\frac{(\pi_{i}-A)\hat{p}(y)}{\sum_{y^{\prime}\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y^{\prime})}\log\frac{\frac{(\pi_{i}-A)\hat{p}(y)}{\sum_{y^{\prime}\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y^{\prime})}}{\hat{p}(y)}\\\
&\quad+\sum_{y\in\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}\\\
&=\frac{(1-\pi_{i})}{\sum_{y^{\prime}\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y^{\prime})}\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y)\right)\log\frac{(1-\pi_{i})}{\sum_{y^{\prime}\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y^{\prime})}\\\
&\quad+\frac{(\pi_{i}-A)}{\sum_{y^{\prime}\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y^{\prime})}\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y)\right)\log\frac{(\pi_{i}-A)}{\sum_{y^{\prime}\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y^{\prime})}\\\
&\quad+\sum_{y\in\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}\\\
&=(1-\pi_{i})\log\frac{(1-\pi_{i})}{\sum_{y^{\prime}\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y^{\prime})}+(\pi_{i}-A)\log\frac{(\pi_{i}-A)}{\sum_{y^{\prime}\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y^{\prime})}\\\
&\quad+\sum_{y\in\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}\\\
\end{split}$ (16)

Now, suppose $\exists p\in\text{half-space}_{\pi_{i}}$ with
$p(y)=p^{r}(y)\,\forall y\in\bar{Y}$ for which $\exists y\in
Y_{\pi_{i}}\setminus\bar{Y}:p(y)\neq p^{r}_{\pi_{i}}(y)$ such that
$D_{KL}(p\,||\,\hat{p})<D_{KL}(p^{r}\,||\,\hat{p})$, which would lead to a
contradiction of the lemma.

$\displaystyle\quad D_{KL}(p\,||\,\hat{p})-D_{KL}(p^{r}\,||\,\hat{p})$
$\displaystyle=\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p(y)\log\frac{p(y)}{\hat{p}(y)}+\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p(y)\log\frac{p(y)}{\hat{p}(y)}+\sum_{y\in\bar{Y}}p(y)\log\frac{p(y)}{\hat{p}(y)}$
$\displaystyle\quad-\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}-\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}-\sum_{y\in\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}$
$\displaystyle=\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p(y)\log\frac{p(y)}{\hat{p}(y)}+\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p(y)\log\frac{p(y)}{\hat{p}(y)}$
$\displaystyle\quad-\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}-\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}$
$\displaystyle\geq\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p(y)\right)\log\frac{\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p(y)\right)}{\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y)\right)}+\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p(y)\right)\log\frac{\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p(y)\right)}{\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y)\right)}$
$\displaystyle\quad-\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}-\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}$

Here, the last equation can be derived from the log sum inequality444For
$a_{1},\dots,a_{n},b_{1},\dots,b_{n}\in\mathbb{R}_{+}$, the log sum inequality
states that $\sum_{i\in[n]}a_{i}\log\frac{a_{i}}{b_{i}}\geq a\log\frac{a}{b}$,
whereby $a:=\sum_{i\in[n]}a_{i}$ and $b:=\sum_{i\in[n]}b_{i}$.. As we are
projecting onto the half space associated with $\pi_{i}$, we can further see
that $\sum_{y\in\mathcal{Y}\setminus Y_{\pi_{i}}}p(y)=1-\pi_{i}$ and
$\sum_{y\in Y_{\pi_{i}}\setminus\bar{Y}}p(y)=\pi_{i}-A$, which also applies to
$p^{r}$ for the same class subsets.

As a result, together with (16), we get

$\displaystyle=\left(1-\pi_{i}\right)\log\frac{\left(1-\pi_{i}\right)}{\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y)\right)}+\left(\pi_{i}-A\right)\log\frac{\left(\pi_{i}-A\right)}{\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y)\right)}$
$\displaystyle\quad-\left(1-\pi_{i}\right)\log\frac{\left(1-\pi_{i}\right)}{\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y)\right)}-\left(\pi_{i}-A\right)\log\frac{\left(\pi_{i}-A\right)}{\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y)\right)}=0\nless 0\enspace,$

which leads to a contradiction. ∎

For the next lemma, we introduce the notion of a face as follows:

######  Definition 2 (Face).

For a possibility constraint $\pi_{i}$ of a (normalized) possibility
distribution $\pi:\mathcal{Y}\longrightarrow[0,1]$ and distributions
$p\in\mathbb{P}(\mathcal{Y})$ with
$\sum_{y\in\mathcal{Y}:\pi(y)\leq\pi_{i}}p(y)=\pi_{i}$ (i.e., $p\in\text{half-
space}_{\pi_{i}}$), we define

$\text{face}_{\pi_{i}}:=\bigg{\\{}p\,|\,\sum_{k=1}^{j}p_{k}\leq\pi_{j},\quad
j\in\\{1,...,i\\}\bigg{\\}}$

as face associated with $\pi_{i}$.

Effectively, $\text{face}_{\pi_{i}}$ considers the subspace of $\text{half-
space}_{\pi_{i}}$ that does not violate any of the possibility constraints
$\pi_{j}\leq\pi_{i}$. One can readily see that each iteration of Algorithm 1
determines the highest possibility constraint $\pi(y^{*})$ whose projection
$p^{r}$ as defined before is element of $\text{face}_{\pi(y^{*})}$. Given this
fact, we show the optimality of this selected face in the next lemma.

######  Lemma A.3 (Optimal face).

Given a set $\bar{Y}\subseteq\mathcal{Y}$ of classes with arbitrarily fixed
probabilities, a (normalized) possibility distribution
$\pi:\mathcal{Y}\longrightarrow[0,1]$ with $\max_{y\in\mathcal{Y}}\pi(y)=1$
and an arbitrary distribution $\hat{p}\notin\mathcal{Q}_{\pi}$, Algorithm 1
selects $\text{face}_{\pi_{i}}$ in each iteration that is optimal in the sense
that $\nexists j\neq i$ with
$p^{*}\in\operatorname*{argmin}_{p\in\text{face}_{\pi_{j}}}D_{KL}(p\,||\,\hat{p})$,
$p^{*}(y)=p^{r}(y)\,\forall y\in\bar{Y}$ and $\exists y\in
Y_{\pi_{i}}\setminus\bar{Y}:p^{*}(y)\neq p^{r}(y)$, such that
$D_{KL}(p^{*}\,||\,\hat{p})<D_{KL}(p^{r}\,||\,\hat{p})$ for
$p^{r}\in\operatorname*{argmin}_{p\in\text{face}_{\pi_{i}}}D_{KL}(p\,||\,\hat{p})$.

###### Proof.

Again, we define $A:=\sum_{y\in\bar{Y}}p^{r}(y)$. Now, let us assume $\exists
j\neq i$ with the properties described in this lemma, which leads us to a
contradiction. To proof it, we can distinguish three cases.

  1. Case 1:

$\pi_{j}>\pi_{i}$. It is easy to see that a violation with respect to Eq. 12
for possibility $\leq\pi_{j}$ exists, i.e., the projection constructed as in
(15) for $\pi_{j}$ is not element of $\text{face}_{\pi_{j}}$. In this case,
the distribution
$p^{*}\in\operatorname*{argmin}_{\text{face}_{\pi_{j}}}D_{KL}(p\,||\,\hat{p})$
is located on an “edge” of the face, i.e., $\exists
m:\sum_{k=1}^{m}p^{*}_{k}=\pi_{m}$.

If $m=i$, then Lemma A.2 implies that $p^{*}(y)=p^{r}(y)\,\forall y\in
Y_{\pi_{i}}$, which contradicts the assumptions.

In case of $m\neq i$, we can derive the following results using a similar
scheme as in the proof of Lemma A.2:

$\displaystyle\quad D_{KL}(p^{*}\,||\,\hat{p})-D_{KL}(p^{r}\,||\,\hat{p})$
$\displaystyle=\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{*}(y)\log\frac{p^{*}(y)}{\hat{p}(y)}+\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{*}(y)\log\frac{p(y)}{\hat{p}(y)}+\sum_{y\in\bar{Y}}p(y)\log\frac{p(y)}{\hat{p}(y)}$
$\displaystyle\quad-\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}-\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}-\sum_{y\in\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}$
$\displaystyle\geq\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{*}(y)\right)\log\frac{\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{*}(y)\right)}{\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y)\right)}+\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{*}(y)\right)\log\frac{\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{*}(y)\right)}{\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y)\right)}$
$\displaystyle\quad-\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}-\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{r}(y)\log\frac{p^{r}(y)}{\hat{p}(y)}$

As we know that $p^{*}$ does not violate any possibility constraints in
$Y_{\pi_{j}}\supset Y_{\pi_{i}}$ due to $p^{*}\in\text{face}_{\pi_{j}}$, but
is also not on the same edge as implied by $\pi_{i}$, it holds that

$\sum_{y\in Y_{\pi_{i}}\setminus\bar{Y}}p^{*}(y)<\pi_{i}-A\enspace.$

Moreover, as we know that there is no possibility violation by
$p^{r}(y)\,\forall\in Y_{\pi_{i}}$ associated with $\pi$ (cf. Lemma A.2), it
must hold $\sum_{Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y)>\pi_{i}-A$. Otherwise,
$\hat{p}$ would be element of $\mathcal{Q}_{\pi}$.

Altogether, one can readily follow

$\displaystyle\begin{split}&=\underbrace{\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{*}(y)\right)}_{>1-\pi_{i}}\log\frac{\overbrace{\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}p^{*}(y)\right)}^{>1-\pi_{i}}}{\left(\sum_{y\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y)\right)}+\underbrace{\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{*}(y)\right)}_{<\pi_{i}-A}\log\frac{\overbrace{\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}p^{*}(y)\right)}^{<\pi_{i}-A}}{\left(\sum_{y\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y)\right)}\\\
&\quad-(1-\pi_{i})\log\frac{(1-\pi_{i})}{\sum_{y^{\prime}\in\mathcal{Y}\setminus
Y_{\pi_{i}}}\hat{p}(y^{\prime})}-(\pi_{i}-A)\log\frac{(\pi_{i}-A)}{\sum_{y^{\prime}\in
Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y^{\prime})}>0\nless
0\enspace,\end{split}$ (17)

leading to a contradiction.

  2. Case 2:

$\pi_{j}=\pi_{i}$. Lemma A.2 implies the optimality of $p^{r}$ in this case.

  3. Case 3:

$\pi_{j}<\pi_{i}$. Here, one can again distinguish whether there exists a
violation of $p^{r}$ constructed for $\pi_{j}$ or not. In the first case, we
can apply exactly the same idea as before by showing that the projection
$p^{*}\in\operatorname*{argmin}_{p\in\text{face}_{\pi_{j}}}D_{KL}(p\,||\,\hat{p})$
is located on an edge that is associated with a $\pi_{m}$ with $m<i$.

In case there is no violation, we know that $\sum_{k=1}^{j}p^{*}_{k}=\pi_{j}$.
This leads to $\sum_{k=1}^{i}p^{*}_{k}\leq\pi_{i}$. Together with
$\sum_{Y_{\pi_{i}}\setminus\bar{Y}}\hat{p}(y)>\pi_{i}-A$, one can derive a
similar equation as in Eq. 17 to show that

$D_{KL}(p^{*}\,||\,\hat{p})-D_{KL}(p^{r}\,||\,\hat{p})\geq 0\nless 0\enspace,$

leading again to a contradiction.

∎

By combining the previous results, we are ready to proof the optimality of
Algorithm 1.

See 4.1

###### Proof.

Combining the three previous lemmas, as well as the fact that the solution of
$\operatorname*{argmin}_{p\in\mathcal{Q}_{\pi}}D_{KL}(p\,||\,\hat{p})$ is
always characterized by an extreme point on one of the faces of the convex
polytope $\mathcal{Q}_{\pi}$ for $\hat{p}\not\in\mathcal{Q}_{\pi}$, 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\not\in Y$.

In case of $\hat{p}\in\mathcal{Q}_{\pi}$, Algorithm 1 returns
$D_{KL}(\hat{p}\,||\,\hat{p})=0$, which is optimal by definition of $D_{KL}$.
∎

####  A.4.2 Complexity

The complexity of Algorithm 1 requires a proper specification of how $y^{*}$
is determined in the while loop. In our implementation, we sort the classes
$y\in\mathcal{Y}=\\{y_{1},\ldots,y_{K}\\}$ according to their possibilities
$\pi(y)$ in a descending manner first, which can be done in $\mathcal{O}(K\log
K)$. Then, the while loop iterates over the sorted classes and can continue
with the next while-loop until a matching constraint $\pi(y^{*})$ could be
determined. This violation check involves iterating over all classes $y\in Y$
with $\pi(y)\leq\pi(y^{*})$. By sorting the elements in advance, this becomes
efficient.

##### Worst-Case Complexity

In the worst-case, every iteration of Algorithm 1 has to iterate over all
remaining elements in $Y$. As said before, checking violations of the
possibility constraints requires iterating over all involved classes. Thus,
the worst-case complexity can be (loosely) bounded by

$\sum_{i=0}^{K-1}(i+1)(K-i)=\frac{K^{3}}{6}+\frac{K^{2}}{2}+\frac{K}{3}=\mathcal{O}(K^{3})\enspace.$

##### Average-Case Complexity

Although we are not providing a rigorous analysis of the average-case
complexity here, we characterize the efficiency of our algorithm in several
cases.

We can observe that the worst case applies whenever the projection of a query
distribution $\hat{p}\not\in\mathcal{Q}_{\pi}$ on the convex polytope
$\mathcal{Q}_{\pi}$ is the distribution $p^{*}$ with
$p^{*}(y_{i})=\pi(y_{i})-\pi(y_{i-1})$ for all $i\in\\{1,\ldots,K-1\\}$ and
$p^{*}(y_{K})=\pi(y_{K})$ for sorted classes $y_{i}$ according to their
possibilities. This is the case when $\hat{p}$ is in the cone associated with
this extreme point $p^{*}$ [74], which is given by

$\bigg{\\{}p\not\in\mathcal{Q}_{\pi}\,|\,p^{*}\in\operatorname*{argmin}_{p^{\prime}\in\mathcal{Q}_{\pi}}D_{KL}(p^{\prime}\,||\,p)\bigg{\\}}\enspace.$

This set, however, depends on the size of the faces resp. the credal set and
is typically rather small. Moreover, it gets proportionally smaller with
higher values of $K$.

In the (trivial) case of $\hat{p}\in\mathcal{Q}_{\pi}$, we achieve linear
complexity $\mathcal{O}(K)$ as we have to check the possibility constraints
for all $K$ classes only once. In the other cases, the complexity depends on
the face on which we need to project $\hat{p}$: When projecting on
$\text{face}_{\pi_{i}}$, we do not have to consider any class $y$ with
$\pi(y)\leq\pi_{i}$. Roughly speaking, the larger the faces associated with
high possibilities become, the higher the chance of (optimally) projecting
directly on this face and not requiring any loop iterations over classes with
smaller possibility values, leading to a sublinear amount of face projections
and thus reducing the cubic complexity.