# Quantifying Deep Learning Model Uncertainty in Conformal Prediction

Hamed Karimi,1 Reza Samavi1,2

###### Abstract

Precise estimation of predictive uncertainty in deep neural networks is a
critical requirement for reliable decision-making in machine learning and
statistical modeling, particularly in the context of medical AI. Conformal
Prediction (CP) has emerged as a promising framework for representing the
model uncertainty by providing well-calibrated confidence levels for
individual predictions. However, the quantification of model uncertainty in
conformal prediction remains an active research area, yet to be fully
addressed. In this paper, we explore state-of-the-art CP methodologies and
their theoretical foundations. We propose a probabilistic approach in
quantifying the model uncertainty derived from the produced prediction sets in
conformal prediction and provide certified boundaries for the computed
uncertainty. By doing so, we allow model uncertainty measured by CP to be
compared by other uncertainty quantification methods such as Bayesian (e.g.,
MC-Dropout and DeepEnsemble) and Evidential approaches.

## Introduction

Accurate estimation of predictive uncertainty plays a crucial role in high-
stakes real-world applications, particularly in the field of medical AI, where
precise and reliable classification of diseases and conditions is paramount.
Machine learning models have demonstrated their potential in aiding medical
professionals with accurate diagnosis and treatment decisions. However,
relying solely on point predictions without considering the associated
uncertainty can lead to erroneous conclusions and suboptimal patient care.

To illustrate the significance of model uncertainty quantification in medical
AI, let us consider a classification task involving the identification of
different types of skin lesions based on diagnostic images. The machine
learning model is trained on a large dataset of annotated skin lesion images,
along with corresponding clinical information. The goal of the model is to
classify new, unseen images into specific categories, such as malignant
melanoma, benign nevi, or basal cell carcinoma. Suppose the model predicts a
given skin lesion as malignant melanoma, indicating a high probability of
malignancy. Without an understanding of the associated uncertainty, medical
professionals may proceed with aggressive treatment or surgical intervention,
potentially subjecting patients to unnecessary procedures. There are inherent
uncertainties in the prediction, stemming from various sources, such as
variations in imaging quality, complex morphological features, or overlapping
characteristics between different lesion types. Therefore, for a prediction to
be acceptable, in addition to the ability to achieve high predictive accuracy,
it is also crucial to have a measure of the predictive uncertainty.

Although there are popular approaches to quantify the model predictive
uncertainty, e.g. Bayesian methods such as MC-Dropout (Gal and Ghahramani
2016) and DeepEnsemble (Lakshminarayanan, Pritzel, and Blundell 2016), and
Evidential approaches (Sensoy, Kaplan, and Kandemir 2018; Yuan et al. 2020;
Sensoy et al. 2021), the lack of formal guarantees is a major limitation in
the state-of-the-art methods of uncertainty quantification. To resolve this
issue, Conformal Prediction (CP) or Conformal Inference (Vovk, Gammerman, and
Shafer 2005; Papadopoulos et al. 2002) provides a compelling framework as a
post-processing technique to address this challenge by offering a reliable
indicator of uncertainty.

Rather than providing a single deterministic prediction, CP constructs a
finite Prediction Set or Uncertainty Set that encompasses a plausible subset
of class labels for a given unseen input data point in any pretrained
classifier. This prediction set reflects the inherent uncertainty associated
with the model’s predictions. In addition to a point estimation of the most
likely predictive probability as a measure of confidence, the size of a
prediction set is considered as an indicator of the model uncertainty in
classifying a new data point. Larger prediction sets indicate higher model
uncertainty associated with the input data. However, in case of using the
prediction set size as an uncertainty indicator, the measure is not scaled to
be compared with other state-of-the-art uncertainty quantification methods.

Returning to our medical AI example, instead of a definite prediction of
malignant melanoma (a single true label), CP offers a prediction set
indicating the most likely class labels of the skin lesion with the respected
probabilities, while providing a guarantee that the true label is a member of
this set with a high probability. This additional information enables medical
professionals to make more informed decisions, considering the potential risks
and uncertainties associated with the model’s predictions. CP is also fast,
computationally efficient, and generally applicable to every dataset
(arbitrary data distribution) and classification model (Lei et al. 2018).
Nevertheless, the quantification of model uncertainty in conformal prediction
for classification tasks remains an active research area, with several
challenges and limitations. To the best of our knowledge, there is no scaled
and reliable quantification of model uncertainty achieved by CP method. The
uncertainty quantification is highly crucial when there is an intent to
represent the amount of model uncertainty or perform comparative evaluations.
Thus, we aim to propose a novel approach to quantify the model uncertainty
based on the produced prediction sets and improve the reliability and accuracy
of uncertainty estimation.

In this paper, we are making the following two contributions in the context of
conformal prediction: (1) we investigate existing methodologies for model
uncertainty estimation within conformal prediction for classification tasks,
and analyze their strengths and limitations, (2) we propose a novel technique
for uncertainty quantification of CP, aiming to facilitate the comparative
evaluations between CP-based methods and other state-of-the-art uncertainty
estimation methods. We use the formal guarantee of true label coverage
(Romano, Sesia, and Candes 2020) in the prediction set to devise a solid
probabilistic theory along with certified boundaries of the model uncertainty.
The proposed quantification method can enhance the accuracy and reliability of
uncertainty estimation in real-world applications. By advancing the field of
model uncertainty quantification in conformal prediction for classification
tasks, this research endeavors to equip medical professionals with a more
reliable and guaranteed method to quantify the model uncertainty and support
their decision-making process.

## Background on Conformal Prediction

The validity of CP method depends on the assumption that the calibration data
points are iid and exchangeable, i.e. data points are selected independently
from the same distribution. In conformal procedure for a pretrained model, we
use split conformal prediction as a method of splitting the test (unseen) data
into validation data and a small amount of additional unseen data (around 500
to 1000 data points) called calibration data or holdout set. CP uses this
calibration data and an arbitrary conformal score function to generate the
prediction sets. The conformal score is a measure of the discrepancy between
model predictive outcomes and true labels which is used to compare an unseen
data point in the validation set with those in the calibration set. Note that
CP is not restricted to a specific conformal score function and
classification/regression tasks. In the following, we discuss how to apply
conformal prediction to a pretrained model.

In conformal prediction, we generally take any heuristic notion of model
uncertainty associated with the input data point in any data distribution and
any model, and transform this uncertainty to a rigorous form. To this aim, we
generally consider an unseen data point $x\in\mathcal{X}_{cal}$ from a small
set of i.i.d. (independent and identically distributed) data as calibration
set, and the corresponding model output $y\in\mathcal{Y}=\\{1,2,\cdots,K\\}$.
To construct the prediction set as a rigorous uncertainty estimation, we
require to:

  1. 1.

Identify a heuristic notion of uncertainty using the pretrained model.

  2. 2.

Devise a conformal score function $s(x,y)\in\mathbb{R}$. Larger value of the
score function indicates higher model uncertainty.

  3. 3.

Compute $\widehat{q}$ as the $\frac{\lceil(n+1)(1-\delta)\rceil}{n}$ quantile
of the calibration scores $\\{s_{i}=(x_{i},y_{i})\\}_{i=1}^{n}$ using the
coverage error level $\delta$ and unseen calibration data with the size $n$.

  4. 4.

Use this quantile $\widehat{q}$ to form the prediction sets for testing data
$x_{val}\in\mathcal{X}_{val}$ as,

$\mathcal{C}(x_{val},\widehat{q})=\\{y:s(x_{val},y)\leq\widehat{q}\\}\ .$ (1)

The prediction set $\mathcal{C}(x_{val},\widehat{q})$ is a subset of all
possible $K$ labels that the model finds plausible for the image $x_{val}$.
The prediction set contains a relatively small number of labels and is
guaranteed to include the true label with a user-specified probability (e.g.,
90%) in a relatively small prediction set of labels (Lei et al. 2018). This
inclusion probability is expressed as an arbitrary coverage error level
$\delta$ with which we set the probability that the prediction set contains
the true label, to $1-\delta$. This validity attribute is called marginal
coverage, since the probability is averaged over the stochasticity in the
unseen data points. CP satisfies the true label coverage property as its
validity criterion (Vovk, Gammerman, and Saunders 1999) which will be formally
discussed in Theorem 2.

According to split conformal prediction method, we formally have
$\mathcal{X}_{cal}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$ as a small set of i.i.d. and
unseen calibration data ($n\approx 500$ to $1000$), in which
$x_{i}\in\mathbb{R}^{d}$ is a feature vector of size $d$ as $i$th input data
point, and $y_{i}\in\mathcal{Y}=\\{1,2,\cdots,K\\}$ is the corresponding true
label out of $K$ possible target labels. Moreover,
$(x_{val},y_{val})\in\mathcal{X}_{val}$ is a validation data point which is
unseen during the training process. After computing the conformal scores
associated with the calibration data, $\widehat{q}$ is obtained as the
$1-\delta$ quantile of conformal scores in which $\delta$ is a user-specified
error level of true label coverage. Consider
$\mathcal{C}(x_{val},\widehat{q}):\mathbb{R}^{d}\times\mathbb{R}\rightarrow
2^{\mathcal{Y}}$ is a function that takes an unseen input data vector and
$1-\delta$ quantile of their corresponding conformal scores, and then produces
a prediction set containing a subset of possible labels. Assuming the data
exchangeability, this prediction set is statistically certified to marginally
cover the true label associated with a validation data point with the
probability of at least $1-\delta$.

######  Theorem 1 (Conformal Coverage Guarantee (Vovk, Gammerman, and Shafer
2005; Papadopoulos et al. 2002)).

Consider $\\{(x_{i},y_{i})\in\mathcal{X}_{cal}\\}_{i=1}^{n}$ and
$(x_{val},y_{val})\in\mathcal{X}_{val}$ are i.i.d. and unseen data as $n$
calibration data points and a validation data point, respectively. Let
$\delta$ be the user-chosen coverage error level, $\widehat{q}$ is the
$1-\delta$ quantile of calibration conformal scores, and
$\mathcal{C}(x_{val},\widehat{q})\subseteq\mathcal{Y}$ be the function of
producing prediction set. If $\mathcal{C}(x_{val},\widehat{q})$ gradually
grows to include all possible labels in $\mathcal{Y}$ when having large enough
$\widehat{q}$, then, the probability of the true label being covered in the
prediction set is guaranteed in the following bounds:

$1-\delta\leq\mathcal{P}(y_{val}\in\mathcal{C}(x_{val},\widehat{q}))\leq
1-\delta+\frac{1}{n+1}\ .$ (2)

The proof and the related conditions of this theorem are available in (Vovk,
Gammerman, and Shafer 2005; Lei et al. 2018).

When constructing valid prediction sets, three distinct properties are
required to be satisfied: (1) the marginal coverage property of the true label
that guarantees the prediction set includes the true label with the
probability of at least $1-\delta$ based on Equation 2, (2) the set size
property to reflect the desirability of a smaller size for the prediction set,
and (3) the adaptivity property that necessitates the set size for unseen data
is modified to represent instance-wise model uncertainty, i.e., the set size
is smaller when the model encounters easier test data rather than the
inherently harder ones. Note that the difficulty of a test data point is based
on the rank of its true label in the sorted set of outcome probabilities.
These properties affect each other; for example, the set size property tries
to make the sets smaller, while the adaptivity property tries to make the sets
larger for harder data points when the model is uncertain, or choosing the
fixed-size sets may satisfy the coverage property, but without adaptivity.

As an example, to construct the prediction sets, we require to have a
pretrained model $\mathcal{M}_{\Theta}$ with the parameter set $\Theta$
accompanied by its heuristic notion of uncertainty to form an arbitrary
conformal score function, e.g., one minus the softmax probability
$\mathcal{M}_{\Theta}(x,y_{true})$ associated with true label $y_{true}$ given
the input data point $x$. However, the softmax probabilities are unreliable
due to being overconfident or underconfident (Guo et al. 2017; Nixon et al.
2019). Thus, split conformal prediction method offers using a small
calibration set of unseen data (not seen during the training process) to apply
conformal score function and statistically achieve coverage guarantee. For the
calibration data, we compute the aforementioned conformal scores which is
higher when the model is more uncertain in the prediction. Then, we compute
$\widehat{q}$ as $1-\delta$ quantile of the calibration conformal scores. For
instance, if $\delta=0.1$ is set for calibration data, at least $90\%$ of
softmax probabilities associated with the true labels are certified to be
above the $1-\widehat{q}$. Eventually, for each validation data point
$x_{val}\in\mathcal{X}_{val}$ (unseen testing data points), we include all the
labels with the softmax probability above $1-\widehat{q}$ into the prediction
set $\mathcal{C}(x_{val},\widehat{q})$ as,

$\mathcal{C}(x_{val},\widehat{q})=\\{y:\mathcal{M}_{\Theta}(x_{val})\geq
1-\widehat{q}\\}\ .$ (3)

Therefore, the softmax probability associated with the true label is
statistically certified to be above $1-\widehat{q}$ with the probability of
$90\%$, so that the marginal true label coverage is guaranteed based on
Equation 2 in Theorem 2.

Considering the size of the prediction set as the only uncertainty measure is
not reliable due to the probabilistic nature of conformal method, i.e., the
existence of the true label in the prediction sets is stochastic w.r.t. the
coverage error level $\delta$. In the following section, we will propose a new
quantification approach for the model uncertainty which considers the
probabilistic existence of true labels.

## Uncertainty Quantification in Prediction Sets

Following Theorem 2, consider $\delta$ as the error level of true label
coverage, $\widehat{q}$ as the computed $1-\delta$ quantile of conformal
scores over calibration data with size $n$, and
$\mathcal{C}(x_{val},\widehat{q}):\mathbb{R}^{d}\times\mathbb{R}\rightarrow
2^{\mathcal{Y}}$ as the prediction set function given the unseen validation
data point $(x_{val},y_{val})\in\mathcal{X}_{val}$. The result of the function
is a prediction set associated with $x_{val}$ with the size
$|\mathcal{C}(x_{val},\widehat{q})|=m\geq 0$ and the maximum size of the
number of all possible target labels, i.e., $m\leq|\mathcal{Y}|=K$. The true
label $y_{val}$ is included in $\mathcal{C}(x_{val},\widehat{q})$ with some
probabilistic boundaries. Thus, the model uncertainty
$U_{\mathcal{C}}(x_{val})$ associated with the validation data point $x_{val}$
based on the corresponding prediction set $\mathcal{C}(x_{val},\widehat{q})$
can be quantified based on the following theorem:

######  Theorem 2 (Conformal Uncertainty Quantification).

Suppose an unseen validation data point
$(x_{val},y_{val})\in\mathcal{X}_{val}$ is fed to a pretrained classifier with
$K$ possible target labels. Let $\delta$ be the coverage error level of the
true label $y_{val}$, and $\mathcal{C}(x_{val})$ be the corresponding
prediction set of size $m\in\mathbb{Z}^{[0,K]}$ achieved by $1-\delta$
quantile of calibration data with size $n$. Then, the conformal model
uncertainty $U_{\mathcal{C}}(x_{val})$ associated with $x_{val}$ is quantified
to be $0<U_{\mathcal{C}}(x_{val})\leq 1$, and guaranteed in the following
marginal upper bound $\mathcal{H}_{\mathcal{C}}$ and lower bound
$\mathcal{L}_{\mathcal{C}}$ as:

  * •

if $m=0$, then:

$U_{\mathcal{C}}(x_{val})=1\ ,$ (4)

  * •

if $0<m<K$, then:

$\displaystyle
U_{\mathcal{C}}(x_{val})\geq\frac{m}{K}(1-\delta)+\delta-\frac{1}{n+1}=\mathcal{L}_{\mathcal{C}}\quad\text{and}$
(5) $\displaystyle
U_{\mathcal{C}}(x_{val})\leq\frac{m(n+2)}{K(n+1)}+\delta(1-\frac{m}{K})=\mathcal{H}_{\mathcal{C}}\
,$ (6)

  * •

and if $m=K$, then:

$1-\frac{1}{n+1}\leq U_{\mathcal{C}}(x_{val})\leq 1\ .$ (7)

###### Proof.

First, we require to compute a baseline model uncertainty
$\widehat{u}_{\mathcal{C}}$ associated with the produced prediction set
$\mathcal{C}(x_{val})$ given $x_{val}$. The size of the prediction set $m$ is
restricted between 0 and $K$, i.e., $0\leq m\leq K$. As in CP, $m$, i.e., the
size of the prediction set, is an indicator of the uncertainty, we compute the
baseline uncertainty measure as,

$\widehat{u}_{\mathcal{C}}=\frac{m}{K}\ ,$ (8)

where $K$ is the number of all possible target labels. Then, we have the
baseline model uncertainty $\widehat{u}_{\mathcal{C}}\in\mathbb{R}^{[0,1]}$
which is scaled to be compared with other uncertainty measures.

Theorem 2 has three cases with respect to $m$ as the size of prediction set
$\mathcal{C}(x_{val})$: If $m=0$, the model is fully uncertain that could not
select any target label to include into the prediction set based on the
computed $\widehat{q}$. Thus, although in this case,
$\widehat{u}_{\mathcal{C}}=0$, this zero-size prediction set is treated as a
special case and interpreted as the maximum model uncertainty which is
$U_{\mathcal{C}}(x_{val})=1$.

In the general case of $0<m<K$, we have two distinct probabilistic events, the
true label is either included in the prediction set denoted by $P_{1}$, i.e.,
$P_{1}:y_{val}\in\mathcal{C}(x_{val})$, or not included in the prediction set
denoted by $P_{0}$, i.e., $P_{0}:y_{val}\notin\mathcal{C}(x_{val})$. These two
inclusion events $P_{1}$ and $P_{0}$ are mutually exclusive, i.e., disjoint
events, so that only one of the events can happen at the same time. We can
compute the model uncertainty as the probability of the model being uncertain
denoted by $P_{u}$ when either $P_{1}$ or $P_{0}$ holds as,

$\displaystyle\begin{split}U_{\mathcal{C}}(x_{val})&=\mathcal{P}(P_{u}\land(P_{1}\lor
P_{0}))\\\ &=\mathcal{P}((P_{u}\land P_{1})\lor(P_{u}\land P_{0}))\
.\end{split}$ (9)

As the two events $P_{1}$ and $P_{0}$ are disjoint, their corresponding joint
events $P_{u}\land P_{1}$ and $P_{u}\land P_{0}$ are also mutually exclusive.
Therefore, we have:

$\displaystyle\begin{split}U_{\mathcal{C}}(x_{val})&=\mathcal{P}((P_{u}\land
P_{1})\lor(P_{u}\land P_{0}))\\\ &=\mathcal{P}(P_{u}\land
P_{1})+\mathcal{P}(P_{u}\land P_{0})\ .\end{split}$ (10)

Each joint event can be written based on its own conditional probability of
the model being uncertain (i.e., $P_{u}$) given the inclusion of the true
label in the prediction set (i.e., $P_{1}$ or $P_{0}$) as,

$\displaystyle\begin{split}\mathcal{P}(P_{u}\land
P_{1})&=\mathcal{P}(P_{u}|P_{1}).\mathcal{P}(P_{1})\quad\text{and}\\\
\mathcal{P}(P_{u}\land P_{0})&=\mathcal{P}(P_{u}|P_{0}).\mathcal{P}(P_{0})\
,\end{split}$ (11)

where $\mathcal{P}(P_{0})=\delta$ and $\mathcal{P}(P_{1})=1-\delta$ based on
the user-specified $\delta$ as the error level of true label coverage in CP
method. Then, the following equation holds:

$U_{\mathcal{C}}(x_{val})=\mathcal{P}(P_{u}|P_{1}).\mathcal{P}(P_{1})+\mathcal{P}(P_{u}|P_{0}).\mathcal{P}(P_{0})\
.$ (12)

If $P_{0}$ holds, it means $y_{val}\notin\mathcal{C}(x_{val})$. The prediction
set without the true label does not yield to an acceptable predictive
outcomes. In this case, we can consider the model to be fully uncertain such
that $\mathcal{P}(P_{u}|P_{0})=1$. Otherwise, if $P_{1}$ holds, it means
$y_{val}\in\mathcal{C}(x_{val})$. In this case, the true label is included in
the prediction set and the baseline uncertainty $\widehat{u}_{\mathcal{C}}$ is
an indicator of the model uncertainty associated with the prediction set such
that $\mathcal{P}(P_{u}|P_{1})=\widehat{u}_{\mathcal{C}}$. We can now rewrite
Equation 12 as,

$U_{\mathcal{C}}(x_{val})=\widehat{u}_{\mathcal{C}}.\mathcal{P}(P_{1})+\mathcal{P}(P_{0})\
.$ (13)

According to Theorem 2, the following upper and lower bounds hold for the
probabilities $\mathcal{P}(P_{1})$ and $\mathcal{P}(P_{0})$ (i.e.,
$1-\mathcal{P}(P_{1})$) to guarantee the true label coverage in the prediction
set as,

$\displaystyle 1-\delta\leq\mathcal{P}(P_{1})\leq
1-\delta+\frac{1}{n+1}\quad\text{and}$ (14)
$\displaystyle\delta-\frac{1}{n+1}\leq\mathcal{P}(P_{0})\leq\delta\ .$ (15)

Now, we can use the baseline uncertainty $0<\widehat{u}_{\mathcal{C}}<1$, and
the upper and lower bounds in Equations 14 and 15 to construct the bounds for
the model uncertainty $U_{\mathcal{C}}(x_{val})$ based on Equation 13 as,

$\displaystyle\widehat{u}_{\mathcal{C}}.\mathcal{P}(P_{1})+\mathcal{P}(P_{0})\geq\widehat{u}_{\mathcal{C}}(1-\delta)+\delta-\frac{1}{n+1}\quad\text{and}$
(16)
$\displaystyle\widehat{u}_{\mathcal{C}}.\mathcal{P}(P_{1})+\mathcal{P}(P_{0})\leq\widehat{u}_{\mathcal{C}}(1-\delta+\frac{1}{n+1})+\delta\
,$ (17)

where $\widehat{u}_{\mathcal{C}}=\frac{m}{K}$. Finally, we have:

$\displaystyle\begin{split}&U_{\mathcal{C}}(x_{val})\geq\frac{m}{K}(1-\delta)+\delta-\frac{1}{n+1}=\mathcal{L}_{\mathcal{C}}\quad\text{and}\\\
&U_{\mathcal{C}}(x_{val})\leq\frac{m(n+2)}{K(n+1)}+\delta(1-\frac{m}{K})=\mathcal{H}_{\mathcal{C}}\
,\end{split}$ (18)

where $\mathcal{L}_{\mathcal{C}}$ and $\mathcal{H}_{\mathcal{C}}$ denote the
model uncertainty lower and upper bounds, respectively.

In the last case that $m=K$, we compute Equation 18 by setting $m=K$, but
noting that we now have all the possible labels in the prediction set
representing that the model is highly uncertain and could not exclude any of
the labels, i.e., could not make the set size smaller. Therefore, the upper
bound of the model uncertainty $U_{\mathcal{C}}(x_{val})$ is maximum and set
to be $\min(1,U_{\mathcal{C}}(x_{val}))$ as,

$\min(1,U_{\mathcal{C}}(x_{val}))=\min(1,\frac{n+2}{n+1})=1\ .$ (19)

Then, we have:

$1-\frac{1}{n+1}\leq U_{\mathcal{C}}(x_{val})\leq 1\ .$ (20)

∎

In the following section, we discuss the validity and interpretations of the
proposed uncertainty quantification method in conformal prediction.

### Interpretation of the Uncertainty Quantification

According to the proposed Theorem 2, we can quantify the model uncertainty
from the produced prediction sets in CP. This quantification represents the
amount of uncertainty that a conformal model encounters when producing a
prediction set of classifying an unseen validation data point. based on the
proposed Theorem 2, the model uncertainty is highly affected by two different
measures: (1) the size of the produced prediction set, so that the larger set
size indicates the higher model uncertainty associated with an unseen data
point, and (2) the error level $\delta$ of true label coverage, so that the
higher error level $\delta$ gives rise to lower value of $1-\delta$ which
represents a lower probability of true label inclusion in the prediction set.
When true label is not included in the prediction set, the model is expected
to be highly uncertain in the prediction, therefore, the model shows higher
uncertainty as the probability of true label inclusion in the prediction set
is decreased.

Figures 1a and 1b indicate the model uncertainty quantified for different
sizes of an arbitrary prediction set based on the variation of coverage error
level $\delta$ with the number of possible labels $K=10$ and $K=100$,
respectively. For any arbitrary number of possible class labels, e.g., $K=10$
or $K=100$, we can obviously observe that the quantified model uncertainty is
consistently increasing with the growth in both prediction set size $m$ and
the error level $\delta$ of true label coverage. The model uncertainty is
increased when the size of the prediction set is increasing which is an
indicator of higher uncertainty. Furthermore, by increasing the error level
$\delta$, the probability of true label inclusion in the prediction set is
decreased and the model should become more uncertain in the prediction.

(a) Possible class labels: $K=10$

(b) Possible class labels: $K=100$

Figure 1: The conformal model uncertainty associated with prediction sets of
different sizes $m$ based on the variation of error level $\delta$

In the proposed Theorem 2, we quantify the upper bound
$\mathcal{H}_{\mathcal{C}}$ and the lower bound $\mathcal{L}_{\mathcal{C}}$
for the conformal model uncertainty $U_{\mathcal{C}}(x_{val})$. There is a
certified interval of uncertainty variations in the proposed quantification
method denoted by $d_{\mathcal{C}}$ that is caused by the upper
$\mathcal{H}_{\mathcal{C}}$ and the lower $\mathcal{L}_{\mathcal{C}}$ bounds.
We can compute the magnitude of these uncertainty variations as,

$d_{\mathcal{C}}=|\mathcal{H}_{\mathcal{C}}-\mathcal{L}_{\mathcal{C}}|=\frac{1+\widehat{u}_{\mathcal{C}}}{n+1}=\frac{K+m}{K(n+1)}\
,$ (21)

where $\widehat{u}_{\mathcal{C}}$ denotes the baseline uncertainty in Equation
8, $K$ denotes the number of possible labels, $m$ denotes the prediction set
size, and $n$ denotes the size of calibration data set.

(a) Possible class labels: $K=10$

(b) Possible class labels: $K=100$

Figure 2: The model uncertainty variations $d_{\mathcal{C}}$ associated with
prediction sets of different sizes $m$ based on the variation of calibration
data size $n$

This magnitude of the uncertainty variations indicates the tightness and the
accuracy of the proposed uncertainty estimation. Higher $d_{\mathcal{C}}$
represents a larger variation interval of the model uncertainty. Figures 2a
and 2b demonstrate the amount of the uncertainty variation $d_{\mathcal{C}}$
based on the calibration set size $n$ and the prediction set size $m$ for the
number of possible class labels $K=10$ and $K=100$, respectively. We can
observe that for a fixed amount of calibration set size, when the prediction
set size is increased, $d_{\mathcal{C}}$ as the amount of uncertainty
variations is increased as well. This observation shows that a smaller
prediction set yield to a tighter certified bound for the model uncertainty
which represents a more accurate estimation of uncertainty. Moreover, when the
calibration set size is increased, the amount of uncertainty variations
$d_{\mathcal{C}}$ is significantly decreased to form a tighter bound of
uncertainty estimation since by having larger set of calibration data, the
model can produce more accurate $\widehat{q}$ as the $1-\delta$ quantile of
the conformal scores in the calibration data.

## Related Work

A naive approach to generate prediction sets for test data is to use a score
function, e.g., softmax function, and include labels from the most likely to
the least likely probabilities until their cumulative summation exceeds the
threshold $1-\delta$. In this approach, the true label coverage cannot be
guaranteed since the output probabilities are overconfident and uncalibrated
(Nixon et al. 2019). Furthermore, the lower probabilities in image classifiers
are significantly miscalibrated which gives rise to larger prediction sets
that may misrepresent the model uncertainty. There are also a few methods to
generate prediction sets, but not based on conformal prediction (Pearce et al.
2018; Zhang, Wang, and Qiao 2018). However, these methods do not have finite
marginal coverage guarantees as described in Theorem 2.

The coverage guarantee can be achieved using a new threshold and calibration
data samples as holdout set. In this regard, Romano et al. (Romano, Sesia, and
Candes 2020) proposed a method to make CP more stable in the presence of noisy
small probability estimates in image classification. The authors developed a
conformal method called Adaptive Prediction Set (APS) to provide marginal
coverage of true label in the prediction set which is also fully adaptive to
complex data distributions using a novel conformity score, particularly for
classification tasks. For example, with $\delta=0.1$, if selecting prediction
sets that contain $0.85$ estimated probability can achieve $90\%$ coverage on
the calibration data, APS will utilize the threshold $0.85$ to include labels
in the prediction sets. However, APS still produces large prediction sets
which cannot precisely represent the model uncertainty.

To mitigate the large set size, the authors in (Angelopoulos et al. 2020)
introduced a regularization technique called Regularized Adaptive Prediction
Sets (RAPS) to relax the impact of the noisy probability estimates which yield
to significantly smaller and more stable prediction sets. RAPS modifies APS
algorithm by penalizing the small conformity scores associated with the
unlikely labels after Platt scaling (Platt et al. 1999). RAPS regularizes the
APS method, therefore, RAPS acts exactly as same as APS when setting the
regularization parameter to 0. Both APS and RAPS methods are always certified
to satisfy the marginal coverage in Equation 2 regardless of model,
architecture, and dataset. Both methods also require negligible computational
complexity in both finding the appropriate threshold using the calibration
data with the size of around $n\approx 1000$ and inference phase. However,
RAPS could outperform the state-of-the-art APS by achieving marginal coverage
of true labels with significantly smaller prediction sets. Thus, RAPS can
produce adaptive but smaller prediction sets as an estimation of the model
uncertainty given unseen image data samples.

## Conclusion

In this paper, we have addressed the problem of model uncertainty
quantification in conformal prediction. Through our investigation, we proposed
a novel technique to enhance the reliability and accuracy of uncertainty
estimation. We used the existing statistical guarantee of the true label
coverage in the prediction sets to quantify the model uncertainty in a
probabilistic view, and certify upper and lower bounds for the uncertainty
quantification. Our findings highlight the important implications of accurate
uncertainty quantification, representing its benefits for decision-making and
risk assessment in real-world applications.

While our research has made notable contributions, there are still
opportunities for further exploration. Future work should focus on addressing
challenges such as high-dimensional data, imbalanced datasets, and
incorporating domain knowledge into uncertainty quantification in conformal
prediction. Additionally, investigating interpretability and explainability of
uncertainty measures can provide actionable insights. We encourage continued
research to foster the development of more reliable and accurate uncertainty
quantification methods within the conformal prediction framework.

## References

  * Angelopoulos et al. (2020) Angelopoulos, A.; Bates, S.; Malik, J.; and Jordan, M. I. 2020.  Uncertainty sets for image classifiers using conformal prediction.  _arXiv preprint arXiv:2009.14193_.
  * Gal and Ghahramani (2016) Gal, Y.; and Ghahramani, Z. 2016.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In _international conference on machine learning_ , 1050–1059. PMLR.
  * Guo et al. (2017) Guo, C.; Pleiss, G.; Sun, Y.; and Weinberger, K. Q. 2017.  On calibration of modern neural networks.  In _International Conference on Machine Learning_ , 1321–1330. PMLR.
  * Lakshminarayanan, Pritzel, and Blundell (2016) Lakshminarayanan, B.; Pritzel, A.; and Blundell, C. 2016.  Simple and scalable predictive uncertainty estimation using deep ensembles.  _arXiv preprint arXiv:1612.01474_.
  * Lei et al. (2018) Lei, J.; G’Sell, M.; Rinaldo, A.; Tibshirani, R. J.; and Wasserman, L. 2018.  Distribution-free predictive inference for regression.  _Journal of the American Statistical Association_ , 113(523): 1094–1111.
  * Nixon et al. (2019) Nixon, J.; Dusenberry, M. W.; Zhang, L.; Jerfel, G.; and Tran, D. 2019.  Measuring Calibration in Deep Learning.  In _CVPR Workshops_ , volume 2.
  * Papadopoulos et al. (2002) Papadopoulos, H.; Proedrou, K.; Vovk, V.; and Gammerman, A. 2002.  Inductive confidence machines for regression.  In _Machine Learning: ECML 2002: 13th European Conference on Machine Learning Helsinki, Finland, August 19–23, 2002 Proceedings 13_ , 345–356. Springer.
  * Pearce et al. (2018) Pearce, T.; Brintrup, A.; Zaki, M.; and Neely, A. 2018.  High-quality prediction intervals for deep learning: A distribution-free, ensembled approach.  In _International conference on machine learning_ , 4075–4084. PMLR.
  * Platt et al. (1999) Platt, J.; et al. 1999.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  _Advances in large margin classifiers_ , 10(3): 61–74.
  * Romano, Sesia, and Candes (2020) Romano, Y.; Sesia, M.; and Candes, E. 2020.  Classification with valid and adaptive coverage.  _Advances in Neural Information Processing Systems_ , 33: 3581–3591.
  * Sensoy, Kaplan, and Kandemir (2018) Sensoy, M.; Kaplan, L.; and Kandemir, M. 2018.  Evidential deep learning to quantify classification uncertainty.  _Advances in neural information processing systems_ , 31.
  * Sensoy et al. (2021) Sensoy, M.; Saleki, M.; Julier, S.; Aydogan, R.; and Reid, J. 2021.  Misclassification risk and uncertainty quantification in deep classifiers.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2484–2492.
  * Vovk, Gammerman, and Saunders (1999) Vovk, V.; Gammerman, A.; and Saunders, C. 1999.  Machine-learning applications of algorithmic randomness.
  * Vovk, Gammerman, and Shafer (2005) Vovk, V.; Gammerman, A.; and Shafer, G. 2005.  _Algorithmic learning in a random world_ , volume 29.  Springer.
  * Yuan et al. (2020) Yuan, B.; Yue, X.; Lv, Y.; and Denoeux, T. 2020.  Evidential deep neural networks for uncertain data classification.  In _International Conference on Knowledge Science, Engineering and Management_ , 427–437. Springer.
  * Zhang, Wang, and Qiao (2018) Zhang, C.; Wang, W.; and Qiao, X. 2018.  On reject and refine options in multicategory classification.  _Journal of the American Statistical Association_ , 113(522): 730–745.