# Uncertainty Estimation based on Geometric Separation

Gabriella Chouraqui<EMAIL_ADDRESS>
Department of Computer Science
Ben-Gurion University
Israel Liron Cohen<EMAIL_ADDRESS>
Department of Computer Science
Ben-Gurion University
Israel Gil Einziger<EMAIL_ADDRESS>
Department of Computer Science
Ben-Gurion University
Israel Liel Leman<EMAIL_ADDRESS>
Department of Computer Science
Ben-Gurion University
Israel

###### Abstract

In machine learning, accurately predicting the probability that a specific
input is correct is crucial for risk management. This process, known as
uncertainty (or confidence) estimation, is particularly important in mission-
critical applications such as autonomous driving. In this work, we put forward
a novel geometric-based approach for improving uncertainty estimations in
machine learning models. Our approach involves using the geometric distance of
the current input from existing training inputs as a signal for estimating
uncertainty, and then calibrating this signal using standard post-hoc
techniques. We demonstrate that our method leads to more accurate uncertainty
estimations than recently proposed approaches through extensive evaluation on
a variety of datasets and models. Additionally, we optimize our approach so
that it can be implemented on large datasets in near real-time applications,
making it suitable for time-sensitive scenarios.

Keywords: uncertainty estimation, geometric separation, calibration,
confidence evaluation.

##  1 Introduction

Machine learning models, such as neural networks, random forests, and gradient
boosted trees, are widely used in various fields, including computer vision
and transportation, and are transforming the field of computer science
Niculescu-Mizil and Caruana (2006); Zhang and Haghani (2015). However, the
probabilistic nature of classifications made by these models means that
misclassifications are inevitable. As a result, estimating the uncertainty for
a particular input is a crucial challenge in machine learning. In fact, many
machine learning models have some built-in measure of confidence that is often
provided to the user for risk management purposes. The field of _uncertainty
calibration_ aims to improve the accuracy of the confidence estimates made by
machine learning models Guo et al. (2017a).

Confidence evaluation, or the model’s prediction of its success rate on a
specific input, is a crucial aspect of mission-critical machine learning
applications, as it provides a realistic estimate of the probability of
success for a classification and enables informed decisions about the
_current_ situation. Even a highly accurate model may encounter an unexpected
situation, which can be communicated to the user through confidence
estimation. For example, consider an autonomous vehicle using a model to
identify and classify traffic signs. The model is very accurate, and in most
cases, its classifications are correct with high confidence. However, one day,
it encounters a traffic sign that is obscured, e.g., by heavy vegetation. In
this case, the model’s classification is likely to be incorrect. Estimating
confidence, or uncertainty, is a crucial tool for assessing unavoidable risks,
allowing system designers to address these risks more effectively and
potentially avoid unexpected and catastrophic consequences. For example, our
autonomous vehicle may reduce its speed and activate additional sensors until
it reaches higher confidence. Therefore, all popular machine learning models
have mechanisms for determining confidence that can be calibrated to maximize
the quality of confidence estimates Niculescu-Mizil and Caruana (2005); Guo et
al. (2017b); Kumar et al. (2019), and there is ongoing research to calibrate
models more effectively and enable more reliable applications Leistner et al.
(2009); Sun et al. (2007).

Existing calibration methods can be divided into two categories: post-hoc
methods that perform a transformation that maps the raw outputs of classifiers
to their expected probabilities Kull et al. (2019); Guo et al. (2017a); Gupta
and Ramdas (2021), and ad-hoc methods that adapt the training process to
produce better calibrated models Thulasidasan et al. (2019); Hendrycks et al.
(2019a). Post-hoc calibration methods are easier to apply because they do not
change the model and do not require retraining. However, ad-hoc methods may
lead to better model training in the first place and more reliable models.
With the success of both approaches, recent research has focused on using
ensemble methods whose estimates are a weighted average of multiple
calibration methods Ashukha et al. (2020); Ma et al. (2021); Zhang et al.
(2020); Pakdaman and Cooper (2016); Naeini et al. (2015). Another recent line
of work attempts to further refine the uncertainty estimations by refining the
grouping of confidence estimations, e.g., Perez-Lebel et al. (2022); Hebert-
Johnson et al. (2018).

In principle, post-hoc calibration can be viewed as cleaning up a signal,
namely the model’s original confidence estimate. Interestingly, if we follow
this logic, it is clear that the maximal attainable benefit lies in the
quality of the signal. To see this, consider a model that plots the same
confidence for all inputs. In this case, the best result that can be achieved
is to set that confidence to the model’s average accuracy over all inputs.
Therefore, finding better signals to calibrate is a promising direction for
research.

In this work, we introduce a novel approach for improving uncertainty
estimates in machine learning models _using geometry_. We first provide an
algorithm for calculating the maximal geometric _separation_ of an input.
However, calculating the geometric separation of an input requires evaluating
the whole space of training inputs, making it a computationally expensive
method that is not always feasible. Therefore, we suggest multiple methods to
accelerate the process, including a lightweight approximation called _fast-
separation_ and several data reduction methods that shorten the geometric
calculation.

We demonstrate that using our geometric-based method, combined with a standard
calibration method, leads to more accurate confidence estimations than
calibrating the model’s original signal across different models and datasets.
Even more, our approach yields better estimation even when compared to state-
of-the-art calibration methods Kumar et al. (2019); Gupta and Ramdas (2021);
Guo et al. (2017a); Zhang et al. (2020); Naeini et al. (2015); Kull et al.
(2017). Additionally, we show that our approach can be implemented in near
real-time on a variety of datasets through the use of multiple levels of
approximation and optimization. This is particularly useful for practical
applications that require rapid decision-making, such as autonomous driving.
The entire code is available at our Github Leman et al. (2022).

##  2 Related Work

As mentioned above, uncertainty calibration is about estimating the model’s
success probability of classifying a given example. Post-hoc calibration
methods apply some transformation to the model’s confidence (without changing
the model) such transformations include Beta calibration (Beta) Kull et al.
(2017), Platt scaling (Platt) Platt (1999), Temperature Scaling (TS) Guo et
al. (2017a); Kull et al. (2019), Ensemble Temperature Scaling (ETS) Zhang et
al. (2020), and cubic spline Gupta and Ramdas (2021). In brief, these methods
are limited by the best learnable mapping between the model’s confidence
estimations, and the actual confidence. That is, post-hoc calibration map each
confidence value to another calibrated value whereas our method introduces a
new signal that can be calibrated just like the model’s original signal.
Another work that uses a geometric distance in this context is Dalitz (2009).
There, the confidence score is computed directly from the geometric distance,
while we first fit a function on a subset of the data to learn the specific
behavior of the dataset and model. Moreover, the work in Dalitz (2009) only
applies to the k-nearest neighbor model, while our method is applicable to all
models.

The recently proposed Scaling Binning Calibrator (SBC) of Kumar et al. (2019)
uses a fitting function on the confidence values, divides the inputs into bins
of equal size, and outputs the function’s average in each bin. Histogram
Binning (HB) Gupta and Ramdas (2021) uses a similar idea but divides the
inputs into uniform-mass (rather than equal-size) bins. Interestingly, while
most post-hoc calibration methods are model agnostic, recent methods have
begun to look at a neural network non-probabilistic output called logits
(before applying softmax) Guo et al. (2017b); Ding et al. (2020); Wenger et
al. (2019). Thus, some new post-hoc calibration methods apply only to neural
networks.

Ensemble methods are similar to post-hoc calibration methods as they do not
change the model, but they consider multiple signals to determine the model’s
confidence Ashukha et al. (2020); Ma et al. (2021). For example, Bayesian
Binning into Quantiles (BBQ) Naeini et al. (2015) is an extension of HB that
uses multiple histogram binning models with different bin numbers, and
partitions then outputs scores according to Bayesian averaging. The same
methodology of Bayesian averaging is applied in Ensemble of Near Isotonic
Regression Pakdaman and Cooper (2016), but instead of histogram binning, they
use nearly isotonic regression models.

Ad-hoc calibration is about training models in new manners aimed to yield
better uncertainty estimations. Important techniques in this category include
mixup training Thulasidasan et al. (2019), pre-training Hendrycks et al.
(2019a), label-smoothing Müller et al. (2019), data augmentation Ashukha et
al. (2020), self-supervised learning Hendrycks et al. (2019b), Bayesian
approximation (MC-dropout) Gal and Ghahramani (2016); Gal et al. (2017), Deep
Ensemble (DE) Lakshminarayanan et al. (2017), Snapshot Ensemble Huang et al.
(2017a), Fast Geometric Ensembling (FGE) Garipov et al. (2018), and SWA-
Gaussian (SWAG) Maddox et al. (2019). A notable approach is to use geometric
distances in the loss function while training the model Xing et al. (2020).
The authors work with a representation space that maximizes intra-class
distances, minimizes inter-class distances, and uses the distances to estimate
the confidence. Ad-hoc calibration is perhaps the best approach in public as
it tackles the core of models’ calibration directly. However, because it
offers specific training methods, it is of less use to large and already
trained models, and the impact of each workshop is limited to a specific model
type (e.g., DNNs in Garipov et al. (2018)). In comparison, post-hoc and
ensemble methods (and our own method) often work for numerous models.

Our geometric method is largely inspired by the approach of robustness proving
in machine learning models. In this field, formal methods are used to prove
that specific inputs are robust to small adversarial perturbations. That is,
we formally prove that all images in a certain geometric radius around a
specific train-set image receive the same classification Narodytska et al.
(2018); Katz et al. (2017); Huang et al. (2017b); Gehr et al. (2018); Ehlers
(2017); Einziger et al. (2019). These works rely on formal methods produced in
an offline manner and thus apply only to training set inputs (known apriori).
Whereas confidence estimation reasons about the current input. However, the
underlying intuition, i.e., that geometrically similar inputs should be
classified in the same manner is also common to our work.

Indeed, our work shows that geometric properties of the inputs can help us
quantify the uncertainty in certain inputs and that, in general, inputs that
are less geometrically separated and are ’on the edge’ between multiple
classifications are more error-prone than inputs that are highly separated
from other classes. Thus our work reinforces the intuition behind applying
formal methods to prove robustness and supports the intuition that more robust
training models would be more dependable.

##  3 Geometric Separation

In this section, we define a geometric separation measure that reasons about
the distance of a given input from other inputs with different
classifications. Our end goal is to use this measure to provide confidence
estimations. Formally, a model receives a data input, $x$, and outputs the
pair $\langle\mathcal{C}(x),\mathit{conf}(x)\rangle$, where $\mathcal{C}(x)$
is the model’s classification of $x$ and $\mathit{conf}(x)$ reflects the
probability that the classification is correct. We estimate the environment
around $x$ where inputs are closer to inputs of certain classifications over
the others. Our work assumes that the inputs are normalized, and thus these
distances carry the same significance between the different inputs.

In Section 3.1, we define geometric separation and provide an algorithm to
calculate it. Our evaluation shows that geometric separation produces a
valuable signal that improves confidence estimations. However, calculating
geometric separation is too cumbersome for real-time systems, so we suggest a
lightweight approximation in Section 3.2. Finally, Section 3.3 explains how we
use the geometric signal to derive $\mathit{conf}(x)$. That is, mapping a real
number corresponding to the geometric separation to a number in $[0,1]$
corresponding to the confidence ratio.

###  3.1 Separation Measure

We look at the displacement of $x$ compared to nearby data inputs within the
training set. Intuitively, when $x$ is close to other inputs in
$\mathcal{C}(x)$ (i.e., inputs with the same classification as $x$) and is far
from inputs with other classifications, then the model is correct with a high
probability, implying that $\mathit{conf}(x)$ should be high. On the other
hand, when there are training inputs with a different classification close to
$x$, we estimate that $\mathcal{C}(x)$ is more likely to be incorrect.

Below we provide definitions that allow us to formalize this intuitive
account. In what follows, we consider a model $\mathcal{M}$ to consist of a
machine learning model (e.g., a gradient boosted tree or a neural network),
along with a labeled train set, $\mathit{Tr}$, used to generate the model. We
use an implicit notion of distance and denote by $\mathit{d}(x,y)$ the
distance between inputs $x$ and $y$, and by $\mathit{D}(x,A)$ the distance
between the input $x$ and the set $A$ (i.e., the minimal distance between $x$
and the inputs in $A$).

######  Definition 1 (Safe and Dangerous inputs).

Let $\mathcal{M}$ be a model. For an input $x$ in the sample space we define:

$\mathit{F}_{\mathcal{M}}(x):=\\{x^{\prime}\in\mathit{Tr}:\mathcal{C}(x^{\prime})=\mathcal{C}(x)\\}.$

We denote by $\overline{\mathit{F}}_{\mathcal{M}}(x)$ the set
$\mathit{Tr}\setminus\mathit{F}_{\mathcal{M}}(x)$. An input $x\in\mathcal{X}$
is labeled as _safe_ if
$D(x,\mathit{F}_{\mathcal{M}}(x))<D(x,\overline{\mathit{F}}_{\mathcal{M}}(x))$,
and it is labeled as _dangerous_ otherwise.

######  Definition 2 (Zones).

Let $x$ be a safe (dangerous) input. A _zone_ for $x$, denoted $z_{x}$, is
such that for any input $y$, if $d(x,y)<z_{x}$, then
$\mathit{D}(y,\mathit{F}_{\mathcal{M}}(x))<\mathit{D}(y,\overline{\mathit{F}}_{\mathcal{M}}(x))$
($\mathit{D}(y,\mathit{F}_{\mathcal{M}}(x))\geq\mathit{D}(y,\overline{\mathit{F}}_{\mathcal{M}}(x))$).
For each $x$ we denote the maximal such zone by $\mathcal{Z}(x)$.

In other words, a zone of a safe (dangerous) input $x$ is a radius around $x$
such that all inputs in this ball are closer to an input in
$\mathit{F}_{\mathcal{M}}(x)$ ($\overline{\mathit{F}}_{\mathcal{M}}(x)$) than
to any input in $\overline{\mathit{F}}_{\mathcal{M}}(x)$
($\mathit{F}_{\mathcal{M}}(x)$). $\mathcal{Z}(x)$ is the _maximal_ zone
attainable of $x$.

Figure 1: Geometric representation of safe and dangerous inputs, maximal
zones, and separation values. The various classifications are illustrated via
different shapes, and the safe (danger) zones of x (y) are illustrated via
green (red) circles.

Figure 1 provides a geometric illustration of the safe and danger zones of a
given input and of the separation values. For illustration purposes, the
figure uses the $L_{2}$ norm with two dimensions, whereas our data usually
includes many more dimensions. For example, a $30\times 30$ traffic sign image
will have 900 dimensions. In the figure, the shapes represent the
classification of training set inputs. In yellow, we see a new input ($x$ on
the left-hand-side and $y$ on the right-hand-side) which the model classifies
as a triangle. $x$ is a safe input because it is closer to other triangles in
the training set than it is to the squares. The green highlighted ball
represents its maximal zone. The input $y$ is dangerous because the closest
training set input is a square. The red highlighted ball represents its
maximal zone which dually represents how far we need to distance ourselves
from $y$ so that inputs classified as triangles may become closer than other
inputs.

######  Definition 3 (Separation).

The separation of a data input $x$ with respect to the model $\mathcal{M}$ is
$\mathcal{Z}(x)$ when $x$ is a safe input, and $-1\cdot\mathcal{Z}(x)$ when
$x$ is a dangerous input.

That is, the separation of $x$ encapsulates the maximal zone for $x$ (provided
by the absolute value) together with an indication of whether the input is
safe or dangerous (provided by the sign). The separation of $x$ depends only
on the classification of $x$ by the model and the train set. This is because
our definition partitions the inputs in $\mathit{Tr}$ into two sets: one with
$\mathcal{C}(x)$, $\mathit{F}_{\mathcal{M}}(x)$, and one with all other
classifications, $\overline{\mathit{F}}_{\mathcal{M}}(x)$. These sets vary
between models only when they disagree on the classification of $x$. Note that
$x$’s for which the distance from $\mathit{F}_{\mathcal{M}}(x)$ equals the
distance from $\overline{\mathit{F}}_{\mathcal{M}}(x)$ are considered
dangerous inputs, and their separation measure will be zero.

As mentioned, 2 and 3 use an implicit notion of distance and can accept any
distance metric (e.g., $L_{1},L_{2}$ or $L_{\infty}$). However, throughout
this work, we use $L_{2}$ as it is a standard measure for safety features in
adversarial machine learning Moosavi-Dezfooli et al. (2017), in addition to it
being easy to illustrate and intuitive to understand. Moreso, as our work
targets real-time confidence estimations using $L_{2}$ allows us to leverage
standard and well-optimized libraries. Accordingly, all our definitions and
calculations assume the $L_{2}$ metrics (Euclidean distances). Nevertheless,
Section 4.2.1 shows that other metrics are also feasible.

Next, we provide a formula for calculating the separation of a given input $x$
within the $L_{2}$ distance metric.

######  Definition 4.

Given a model $\mathcal{M}$ and an input $x$, define:

$\overline{\mathcal{S}}^{\mathcal{M}}(x)=\min_{x^{\prime\prime}\in\overline{\mathit{F}}_{\mathcal{M}}(x)}\max_{x^{\prime}\in\mathit{F}_{\mathcal{M}}(x)}\frac{\mathit{d}^{2}(x,x^{\prime\prime})-\mathit{d}^{2}(x,x^{\prime})}{2\mathit{d}(x^{\prime},x^{\prime\prime})}$

######  Lemma 1.

Let $x,x^{\prime},x^{\prime\prime}\in\mathbb{R}^{n}$ be inputs such that
$\mathit{d}(x,x^{\prime})<\mathit{d}(x,x^{\prime\prime})$. The maximal
distance $M(x,x^{\prime},x^{\prime\prime})$ for which if $y\in\mathbb{R}^{n}$
such that $\mathit{d}(x,y)<M(x,x^{\prime},x^{\prime\prime})$, then
$\mathit{d}(y,x^{\prime})<\mathit{d}(y,x^{\prime\prime})$ is

$\frac{\mathit{d}^{2}(x,x^{\prime\prime})-\mathit{d}^{2}(x,x^{\prime})}{2\mathit{d}(x^{\prime},x^{\prime\prime})}.$

Proof  Since any three points in space define a plane we focus on the plane
defined by these three points.

Figure 2: Illustration of the proof of 1

Figure 2 demonstrates a geometric positioning of the points and the main
constructions in the proof. The perpendicular bisector to the line between
$x^{\prime}$ and $x^{\prime\prime}$ divides the plane into two parts: one in
which all the points are closer to $x^{\prime\prime}$ than to $x^{\prime}$
(the lower part in the figure) and one in which all the points are closer to
$x^{\prime}$ than to $x^{\prime\prime}$ (the upper part in the figure). Our
goal is thus to establish the distance between $x$ and the lower part of the
plane. Hence, $M(x,x^{\prime},x^{\prime\prime})$ amounts to the distance from
$x$ to the perpendicular bisector to the line between $x^{\prime}$ and
$x^{\prime\prime}$. Using trigonometric calculations, it is straightforward to
verify that indeed

$M(x,x^{\prime},x^{\prime\prime})=\frac{\mathit{d}^{2}(x,x^{\prime\prime})-\mathit{d}^{2}(x,x^{\prime})}{2\mathit{d}(x^{\prime},x^{\prime\prime})}.$

######  Proposition 1.

$\overline{\mathcal{S}}^{\mathcal{M}}(x)$ is the separation of $x$ with
respect to the model $\mathcal{M}$ (in 3).

Proof  Let $x$ be a safe input, and $y$ be an input such that:

$\mathit{d}(x,y)<\min_{x^{\prime\prime}\in\overline{\mathit{F}}_{\mathcal{M}}(x)}\max_{x^{\prime}\in\mathit{F}_{\mathcal{M}}(x)}\frac{\mathit{d}^{2}(x,x^{\prime\prime})-\mathit{d}^{2}(x,x^{\prime})}{2\mathit{d}(x^{\prime},x^{\prime\prime})}.$

We first show that $y$ is closer to $\mathit{F}_{\mathcal{M}}(x)$ than to
$\overline{\mathit{F}}_{\mathcal{M}}(x)$. Let
$z^{\prime\prime}\in\overline{\mathit{F}}_{\mathcal{M}}(x)$, it suffices to
show that there exist $z^{\prime}\in\mathit{F}_{\mathcal{M}}(x)$ such that
$\mathit{d}(y,z^{\prime})<\mathit{d}(y,z^{\prime\prime})$. Notice that:

$\mathit{d}(x,y)<\max_{x^{\prime}\in\mathit{F}_{\mathcal{M}}(x)}\frac{\mathit{d}^{2}(x,z^{\prime\prime})-\mathit{d}^{2}(x,x^{\prime})}{2\mathit{d}(x^{\prime},z^{\prime\prime})}.$

Therefore, there exist a $z^{\prime}\in\mathit{F}_{\mathcal{M}}(x)$ for which:

$\mathit{d}(x,y)<\frac{\mathit{d}^{2}(x,z^{\prime\prime})-\mathit{d}^{2}(x,z^{\prime})}{2\mathit{d}(z^{\prime},z^{\prime\prime})}$

Thus, since $x$ is a safe input, using 1, we conclude that
$\mathit{d}(y,z^{\prime})<\mathit{d}(y,z^{\prime\prime})$. The proof follows
similar arguments for dangerous inputs, taking the distances as
$-\overline{\mathcal{S}}^{\mathcal{M}}$ and flipping the inequalities.

To show the maximality, observe that the intersection point marked by $w$ in
Figure 2, which is at distance $\overline{\mathcal{S}}^{\mathcal{M}}(x)$ from
$x$, can be easily shown to be of equal distances from
$\mathit{F}_{\mathcal{M}}(x)$ and $\overline{\mathit{F}}_{\mathcal{M}}(x)$.

While separation provides the maximal zone, it is expensive to calculate. As
can be seen in 4, to estimate the separation of one specific input, we go over
many triplets of inputs. The exact amount is unbounded and depends on the
dataset. Thus, separation is infeasible to compute in near real-time.
Therefore, when time or computation resources are limited, we require a
different and computationally simpler notion. Accordingly, the following
section provides an efficient approximation of the separation measure.

###  3.2 Fast-Separation Approximation

We approximate the separation of a given input using only its distance from
$\mathit{F}_{\mathcal{M}}(x)$ and its distance from
$\overline{\mathit{F}}_{\mathcal{M}}(x)$. This simplification allows us to
calculate a zone for any given input, which is not necessarily the maximal
one. The reliance on these two distances enables a faster calculation since we
do not perform an exhaustive search over many triplets of inputs. In
particular, we do not consider the geometric positioning of the inputs that
determine the distance from these sets.

######  Definition 5 (Fast-Separation).

Given a model $\mathcal{M}$, the fast-separation of an input $x$, denoted
$\underline{\mathcal{S}}^{\mathcal{M}}(x)$, is defined as:

$\underline{\mathcal{S}}^{\mathcal{M}}(x)=\frac{\mathit{D}(x,\overline{\mathit{F}}_{\mathcal{M}}(x))-\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))}{2}$

Notice that just as is the case for separation, if $x$ is a safe input, its
fast-separation value will be strictly positive and non-positive otherwise.

Figure 3 illustrates the notion of fast-separation. In particular, it
exemplifies why it only provides an approximation of the more accurate
separation measure. It encapsulates a zone that is less than or equal to that
of separation. Sub-figure (a) demonstrates a case in which
$\underline{\mathcal{S}}^{\mathcal{M}}(x)=\overline{\mathcal{S}}^{\mathcal{M}}(x)$,
while sub-figure (b) presents a case where
$\overline{\mathcal{S}}^{\mathcal{M}}(x)$ is considerably larger than
$\underline{\mathcal{S}}^{\mathcal{M}}(x)$.

(a)

(b)

Figure 3: Geometric representation of the induced zones of
$\underline{\mathcal{S}}^{\mathcal{M}}$ and
$\overline{\mathcal{S}}^{\mathcal{M}}$ for different input alignments.
$\underline{\mathcal{S}}^{\mathcal{M}}$ is represented by blue arrows and
$\overline{\mathcal{S}}^{\mathcal{M}}$ by green arrows.

The separation measure defined as the maximal safe zone is applicable to all
norms. However, the explicit formula $\overline{\mathcal{S}}^{\mathcal{M}}$,
given in 4 is only applicable in $L_{2}$. The following proposition
demonstrates that fast separation, $\underline{\mathcal{S}}^{\mathcal{M}}$,
calculates a zone that is always contained in the maximal zone for any
distance metric. Thus, it approximates the geometric separation for all
metrics as the proof only requires the triangle inequality.

######  Proposition 2.

For any metric $\ell$, and for any input $x$,
$\underline{\mathcal{S}}^{\mathcal{M}}(x)$ (calculated with respect to $\ell$)
is a zone of $x$. That is,
$|\underline{\mathcal{S}}^{\mathcal{M}}(x)|\leq\mathcal{Z}(x)$. Furthermore,
$\underline{\mathcal{S}}^{\mathcal{M}}(x)$ has the same sign as the separation
of $x$.

Proof  Let $x$ be a safe input, we show that
$\underline{\mathcal{S}}^{\mathcal{M}}(x)$ is a zone of $x$.

Let $y$ be a point such that

$\mathit{d}(x,y)<\underline{\mathcal{S}}^{\mathcal{M}}(x)=\frac{\mathit{D}(x,\overline{\mathit{F}}_{\mathcal{M}}(x))-\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))}{2}.$

We show that
$\mathit{D}(y,\mathit{F}_{\mathcal{M}}(x))<\mathit{D}(y,\overline{\mathit{F}}_{\mathcal{M}}(x))$.
Take $z^{\prime}\in\mathit{F}_{\mathcal{M}}(x)$ and
$z^{\prime\prime},w\in\overline{\mathit{F}}_{\mathcal{M}}(x)$ such that
$\mathit{d}(x,z^{\prime})=\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))$,
$\mathit{d}(x,z^{\prime\prime})=\mathit{D}(x,\overline{\mathit{F}}_{\mathcal{M}}(x))$,
and $\mathit{d}(y,w)=\mathit{D}(y,\overline{\mathit{F}}_{\mathcal{M}}(x))$.
Using the triangle inequality we get:

$\displaystyle\mathit{D}(y,\mathit{F}_{\mathcal{M}}(x))\leq\mathit{d}(y,z^{\prime})\leq\mathit{d}(x,z^{\prime})+\mathit{d}(x,y)$
$\displaystyle<\mathit{d}(x,z^{\prime})+\frac{\mathit{d}(x,z^{\prime\prime})-\mathit{d}(x,z^{\prime})}{2}=\frac{\mathit{d}(x,z^{\prime\prime})+\mathit{d}(x,z^{\prime})}{2}$
$\displaystyle=\mathit{d}(x,z^{\prime\prime})-\frac{\mathit{d}(x,z^{\prime\prime})-\mathit{d}(x,z^{\prime})}{2}<\mathit{d}(x,z^{\prime\prime})-\mathit{d}(x,y)$
$\displaystyle\leq\mathit{d}(x,w)-\mathit{d}(x,y)\leq\mathit{d}(y,w)=\mathit{D}(y,\overline{\mathit{F}}_{\mathcal{M}}(x))$

For dangerous inputs, the proof follows similar arguments, switching
$\mathit{F}_{\mathcal{M}}(x)$ and $\overline{\mathit{F}}_{\mathcal{M}}(x)$.

For the sign of $\underline{\mathcal{S}}^{\mathcal{M}}(x)$ it is easy to see
that for a safe (dangerous) input, $\underline{\mathcal{S}}^{\mathcal{M}}(x)$
will be positive (negative) and therefore has the same sign as the separation.

2 shows that $\underline{\mathcal{S}}^{\mathcal{M}}(x)$ induces a zone that is
always smaller than the maximal zone for any distance metric. In the case of
$L_{2}$, we have a formula for calculating the maximal zone
($\overline{\mathcal{S}}^{\mathcal{M}}(x)$), and the following proposition
provides an approximation bound.

######  Proposition 3.

The following holds for any point $x$:

$|\overline{\mathcal{S}}^{\mathcal{M}}(x)-\underline{\mathcal{S}}^{\mathcal{M}}(x)|\leq\frac{\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))+\mathit{D}(x,\overline{\mathit{F}}_{\mathcal{M}}(x))}{2}.$

Proof  We here prove the bound for safe inputs $x$, the proof for dangerous
inputs is similar. Let $x$ be a safe input. By definition:

$\displaystyle|\overline{\mathcal{S}}^{\mathcal{M}}(x)-\underline{\mathcal{S}}^{\mathcal{M}}(x)|=\overline{\mathcal{S}}^{\mathcal{M}}(x)-\underline{\mathcal{S}}^{\mathcal{M}}(x)=$
$\displaystyle=$
$\displaystyle\min_{x^{\prime\prime}\in\overline{\mathit{F}}_{\mathcal{M}}(x)}\max_{x^{\prime}\in\mathit{F}_{\mathcal{M}}(x)}\frac{\mathit{d}^{2}(x,x^{\prime\prime})-\mathit{d}^{2}(x,x^{\prime})}{2\mathit{d}(x^{\prime},x^{\prime\prime})}$
$\displaystyle\quad-\frac{\mathit{D}(x,\overline{\mathit{F}}_{\mathcal{M}}(x))-\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))}{2}$

Let $z^{\prime\prime}\in\overline{\mathit{F}}_{\mathcal{M}}(x)$ be an input
such that
$\mathit{d}(x,z^{\prime\prime})=\mathit{D}(x,\overline{\mathit{F}}_{\mathcal{M}}(x))$,
and let $z^{\prime}\in\mathit{F}_{\mathcal{M}}(x)$ be a input for which the
maximum on the expression above is obtained. Then, we have:

$\displaystyle|\overline{\mathcal{S}}^{\mathcal{M}}(x)-\underline{\mathcal{S}}^{\mathcal{M}}(x)|$
$\displaystyle\leq$
$\displaystyle\max_{x^{\prime}\in\mathit{F}_{\mathcal{M}}(x)}\frac{\mathit{d}^{2}(x,z^{\prime\prime})-\mathit{d}^{2}(x,x^{\prime})}{2\mathit{d}(x^{\prime},z^{\prime\prime})}-\frac{\mathit{d}(x,z^{\prime\prime})-\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))}{2}$
(1) $\displaystyle=$
$\displaystyle\frac{\mathit{d}^{2}(x,z^{\prime\prime})-\mathit{d}^{2}(x,z^{\prime})}{2\mathit{d}(z^{\prime},z^{\prime\prime})}-\frac{\mathit{d}(x,z^{\prime\prime})-\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))}{2}$
(2) $\displaystyle\leq$
$\displaystyle\frac{\mathit{d}(x,z^{\prime\prime})+\mathit{d}(x,z^{\prime})}{2}-\frac{\mathit{d}(x,z^{\prime\prime})-\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))}{2}$
(3) $\displaystyle=$
$\displaystyle\frac{\mathit{d}(x,z^{\prime})+\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))}{2}$
(4) $\displaystyle\leq$
$\displaystyle\frac{\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))+\mathit{D}(x,\overline{\mathit{F}}_{\mathcal{M}}(x))}{2}$
(5)

The first inequality (Equation 1) holds due to the definition of the minimum
function. The second inequality (Equation 3) is due to the triangle
inequality. The last inequality (Equation 5) holds because, since $x$ is a
safe input, the maximal distance between $x$ and $z^{\prime}$ can’t be greater
than the distance from $x$ to $\overline{\mathit{F}}_{\mathcal{M}}(x)$.

Notice that the above bound is tight, in the sense that there exists an
example witnessing the exact bound, as shown in Figure 4 below.

Figure 4: Example of a input $x$ with
$|\overline{\mathcal{S}}^{\mathcal{M}}(x)-\underline{\mathcal{S}}^{\mathcal{M}}(x)|=\frac{\mathit{D}(x,\overline{\mathit{F}}_{\mathcal{M}}(x))+\mathit{D}(x,\mathit{F}_{\mathcal{M}}(x))}{2}$

###  3.3 Calibration of the Geometric Separation

In this section, we use the geometric notions of
$\underline{\mathcal{S}}^{\mathcal{M}}(x)$ and
$\overline{\mathcal{S}}^{\mathcal{M}}(x)$ to derive confidence estimations
($\mathit{conf}(x)$). Notice that $\mathit{conf}(x)\in(0,1)$ while the
geometric notions are in $(-\infty,+\infty)$. Next, we explain how to
translate between the two.

For each value of $\underline{\mathcal{S}}^{\mathcal{M}}(x)$
($\overline{\mathcal{S}}^{\mathcal{M}}(x)$), we need to match a confidence
value. To do so, we split the data into a Validation set, $\mathit{Vs}$, which
is disjoint from the train and test sets. Such a methodology is commonly used
in post-hoc calibration methods Guo et al. (2017b); Platt (1999); Kull et al.
(2017); Mozafari et al. (2018); Tomani et al. (2022); Zhang et al. (2020);
Gupta and Ramdas (2021); Kumar et al. (2019). We then measure the accuracy for
inputs with similar $\underline{\mathcal{S}}^{\mathcal{M}}(x)$ (or
$\overline{\mathcal{S}}^{\mathcal{M}}(x)$) on $\mathit{Vs}$. At this point, we
have pairs $(y,z)$ where $y$ is a geometric separation value, and $z$ is the
desired confidence value (as measured by the accuracy on $\mathit{Vs}$). The
next step is to find a low-dimensionality function that maximizes accuracy.

Hence, we perform a fitting between $\underline{\mathcal{S}}^{\mathcal{M}}$
(or $\overline{\mathcal{S}}^{\mathcal{M}}$) values and the ratios of correct
classifications (on $\mathit{Vs}$) for each unique value. E.g., if for
$\underline{\mathcal{S}}^{\mathcal{M}}$ value of $10$ we see that 90% of the
points are classified correctly, then we’ll add the pair $\langle
10,0.9\rangle$ to the fitting function. Intuitively, we expect very low
confidence values for highly negative distances and approach 100% confidence
when the distances are large and positive.

##  4 Experimental Results

In this section, we evaluate the effectiveness of our geometric approach.
First, we explain the evaluation methodology in Section 4.1, including the
datasets and models. Then we continue our experiment results step by step by
gradually explaining the tradeoffs and design decisions we take throughout
this work.

###  4.1 Methodology

####  4.1.1 Datasets

Our evaluation uses the following standard datasets:

  * •

_Modified National Institute of Standards and Technology database (MNIST)_
LeCun and Cortes (2010). A dataset that consists of hand-written images
designed for training various image processing systems. It includes 70,000
28×28 grayscale images belonging to one of ten labels.

  * •

_Fashion MNIST (Fashion)_ Xiao et al. (2017). A dataset comprising of 28×28
grayscale images of 70,000 fashion products from 10 categories.

  * •

_German Traffic Signs Recognition Benchmark (GTSRB)_ Houben et al. (2013). A
large image set of traffic signs for the single-image, multi-class
classification problem. It consists of 50,000 RGB images of traffic signs,
belonging to 43 classes.

  * •

_American Sign Language (SignLang)_ Techperson (2017). A database of hand
gestures representing a multi-class problem with 24 classes of letters. It
consists of 30,000 28×28 grayscale images.

  * •

_Canadian Institute for Advanced Research (CIFAR10)_ Krizhevsky et al. (2009).
A dataset containing 32x32 RGB images of 60,000 objects from 10 classes.

For each dataset, we randomly partitioned the data into three subsets: train
set $\mathit{Tr}$ (60%), validation set $\mathit{Vs}$ (20%) and test set
$\mathit{Ts}$ (20%). As is standard practice, we used normalized datasets
(e.g., the same image size for all images), see Leman et al. (2022) for
details. The train set is used to calculate (fast-)separation and train the
model. The validation set is used to evaluate the confidence estimation
associated with each (fast-)separation value. These values, in turn, are used
to fit an isotonic function. Finally, the test set is used to evaluate the
confidence on new inputs that were _not_ present in the train and validation
sets.

####  4.1.2 Models

In our evaluation, we use the following popular machine learning models:
Random Forest (RF) Breiman (2001), Gradient Boosting Decision Trees (GB) Mason
et al. (1999), and Convolutional Neural Network (CNN) Gu et al. (2018). We
chose these models because they are different: RF and GB are tree-based, while
CNN is a neural network. For RF and GB, we configured the hyperparameters
(e.g., the maximal depth of trees) by cross-validation on the train set via
the random search technique Bergstra and Yoshua (2012). For CNN, we used the
configuration suggested by practitioners. Our specific configurations as well
as the accuracy scores of each of the models are detailed in Leman et al.
(2022).

####  4.1.3 Evaluation Algorithms

To evaluate our method, we compare our (fast-)separation-based confidence
estimation to the following methods: the built-in isotonic regression
calibration implemented by Sklearn library, ${Iso}$ Zadrozny and Elkan (2002);
the built-in Platt scaling calibration method implemented by Sklearn library,
${Platt}$ Platt (1999); the scaling-binning calibrator, ${SBC}$ Kumar et al.
(2019) implemented by the same authors repository; the histogram-binning,
${HB}$ Gupta and Ramdas (2021) implemented by the same authors repository; the
beta calibrator, ${Beta}$ Kull et al. (2017) implemented by Küppers et al.
(2020); the bayesian binning into quantiles calibrator, ${BBQ}$ Naeini et al.
(2015) implemented by Küppers et al. (2020); the temperature scaling
calibrator, ${TS}$ Guo et al. (2017a) implemented by Kerrigan et al. (2021);
and the ensemble temperature scaling calibrator, ${ETS}$ Zhang et al. (2020)
implemented by Kerrigan et al. (2021). Notice that $TS$ and $ETS$ are
calibration methods for neural networks thus we only apply those to CNNs.

Each method receives the same baseline model as an input yielding a slightly
different calibrated model. Note that our method is evaluated against the
uncalibrated model as our method does not affect the model. Moreover, it
allows us to compare our method against different calibration methods, as
shown in Table 2.

To evaluate the confidence predictions, we use the _Expected Calibration Error
(ECE)_ , which is a standard method to evaluate confidence calibration of a
model Xing et al. (2020); Krishnan and Tickoo (2020). Concretely, the
predictions sample of size $n$ are partitioned into $M$ equally spaced bins
$(B_{m})_{m\leq M}$, and ECE measures the difference between the sample
accuracy in the $m^{th}$ bin and the the average confidence in it Naeini et
al. (2015). Formally, ECE is calculated by the following formula:

$ECE=\sum_{m=1}^{M}\frac{\left|B_{m}\right|}{n}\left|\operatorname{acc}\left(B_{m}\right)-\operatorname{conf}\left(B_{m}\right)\right|$

where:
$\operatorname{acc}\left(B_{m}\right)=\frac{1}{\left|B_{m}\right|}\cdot\left|\\{x\in
B_{m}:\mathcal{C}(x)\leavevmode\nobreak\ \text{is correct}\\}\right|$, and
$\operatorname{conf}\left(B_{m}\right)=\frac{1}{\left|B_{m}\right|}\sum_{x\in
B_{m}}{\mathit{conf}(x)}$.

###  4.2 Empirical Study

####  4.2.1 Distance metrics

As mentioned in Section 3.1, the notion of geometric separation is applicable
to any norm. In fact, as shown in 2, the fast-separation approximation
provides a zone under any norm. Thus, we have evaluated the ECE obtained from
fast-separation under different norms. The results are given in Table 2. As
can be observed, the ECE is low regardless of the selection of norm indicating
the attractiveness of the geometric signal. However, while some norms are more
accurate for some datasets, there is no universally superior norm. Thus, the
following experiments focus on the $L_{2}$ norm from the reasons specified in
Section 3.1.

Dataset | Model | $L_{1}$ | $L_{2}$ | $L_{\infty}$
---|---|---|---|---
| CNN |  0.17 ±0.03 |  0.18 ±0.05 |  0.08 ±0.03
| GB | 0.28 ±0.09 | 0.36 ±0.07 | 0.37 ±0.06
MNIST | RF |  0.37 ±0.07 |  0.39 ±0.06 |  0.37 ±0.05
| CNN |  0.38 ±0.14 |  0.42 ±0.15 |  0.36 ±0.16
| GB | 1.08 ±0.19 | 0.65 ±0.11 | 0.41 ±0.09
GTSRB | RF |  0.54 ±0.19 |  0.37 ±0.04 |  0.32 ±0.05
| CNN |  0.05 ±0.03 |  0.05 ±0.04 |  0.05 ±0.03
| GB | 0.00 ±0.00 | 0.08 ±0.03 | 0.17 ±0.02
SignLang | RF |  0.00 ±0.00 |  0.08 ±0.02 |  0.14 ±0.03
| CNN |  0.74 ±0.07 |  0.79 ±0.15 |  0.55 ±0.12
| GB | 0.64 ±0.21 | 0.73 ±0.13 | 0.85 ±0.17
Fashion | RF |  0.68 ±0.13 |  0.74 ±0.16 |  0.83 ±0.14
| CNN |  1.20 ±0.19 |  1.20 ±0.30 |  3.03 ±0.79
| GB | 1.59 ±0.51 | 1.25 ±0.21 | 1.17 ±0.24
CIFAR10 | RF |  1.08 ±0.45 |  1.15 ±0.24 |  1.30 ±0.18

Table 1: ECE(%) measures with $95\%$ confidence intervals comparing the
results of the fast-separation-based method using $L_{1},L_{2}$ and
$L_{\infty}$ norms.

####  4.2.2 Fitting Function

As mentioned in Section 3.3, for our fitting function we can use any existing
calibration function. Post-hoc calibration methods based on fitting functions
typically use either a logistic (Sigmoid) or an isotonic regression Zadrozny
and Elkan (2002). Isotonic regression fits a non-decreasing free-form line to
a sequence of observations. In comparison, Sigmoid is a continuous step
function. We used both fitting functions on our fast-separation values and
obtained similar accuracy. We opt here to present the isotonic regression as
it provides the best empirical results, as motivated by Figure 5.

Figure 5 illustrates an example of the success ratio of the Random Forest
model for MNIST inputs with varying values of
$\underline{\mathcal{S}}^{\mathcal{M}}$ scores (similar behavior was observed
for the various models and datasets). We clustered inputs with a similar score
together (into 50 bins overall) as each classification is correct or not, and
we are looking for the average. The black line represents the Sigmoid
function, and the green line represents the isotonic regression. As can be
observed, both regressions are nearly identical on all the points with
positive $\underline{\mathcal{S}}^{\mathcal{M}}$ values. We eventually chose
isotonic regression because it better fitted the few points with negative
$\underline{\mathcal{S}}^{\mathcal{M}}$ values. Interestingly, these points
were consistently a poor fit for the Sigmoid regression rendering it slightly
less accurate on average. Also, observe that the transition is around the
value 0, indicating that the distinction between safe and dangerous points is
meaningful in confidence evaluation.

Figure 5: An illustration of the inputs to the fitting function (blue diamonds
and red dots), and the functions fitted by Sigmoid (black line) and isotonic
regression (green line). The inputs are for the MNIST dataset and the Random
Forest model.

###  4.3 Confidence Evaluation

Table 2: ECE(%) measures with $95\%$ confidence intervals when varying the
calibration method, model, and dataset.

Dataset | Model | $\mathbf{\underline{\mathcal{S}}^{\mathcal{M}}}$ | $\mathbf{\overline{\mathcal{S}}^{\mathcal{M}}}$ | Iso | Platt | SBC | HB | BBQ | Beta | TS | ETS
---|---|---|---|---|---|---|---|---|---|---|---
| CNN | 0.15±.01 | 0.15±0.01 |  0.17±0.01 |  0.52±0.04 |  8.91±0.16 |  0.32±0.02 |  0.22±0.01 |  0.64±0.02 |  0.20±0.01 |  0.20±0.01
| RF | 0.35±.02 | 0.36±0.02 | 0.92±0.03 | 1.49±0.02 | 3.92±0.11 | 0.46±0.02 | 1.13±0.03 | 0.37±0.02 | - | -
| GB | 0.34±.02 | 0.34±0.02 |  1.74±0.03 |  1.97±0.03 |  8.46±0.07 |  0.45±0.02 |  0.65±0.03 |  0.47±0.02 | - | -
MNIST | CNN | 0.37±.04 | 0.37±0.04 |  0.38±0.04 |  2.83±0.53 |  29.01±0.49 |  1.22±0.18 |  1.08±0.21 |  1.98±0.25 |  0.90±0.11 |  0.77±0.09
| RF | 0.37±.02 | 0.38±0.02 | 2.55±0.04 | 4.19±0.03 | 13.99±0.11 | 0.85±0.05 | 3.08±0.04 | 0.56±0.03 | - | -
| GB | 0.61±.03 |  0.63±0.03 |  10.04±0.07 |  19.63±0.83 |  31.25±0.12 |  1.42±0.05 |  9.28±0.11 |  5.36±0.10 | - | -
GTSRB | CNN | 0.09±.05 |  0.10±0.06 | 0.09±0.05 |  0.12±0.07 |  17.77±0.21 |  1.24±1.03 |  1.24±1.03 |  1.24±1.04 |  0.11±0.01 |  0.12±0.01
| RF | 0.08±.01 | 0.08±0.01 | 0.46±0.02 | 1.76±0.02 | 17.34±0.18 | 0.16±0.02 | 0.86±0.02 | 0.29±0.01 | - | -
| GB | 0.07±.01 | 0.07±0.01 |  4.01±0.06 |  5.93±0.06 |  31.01±0.08 |  0.46±0.03 |  0.78±0.05 |  0.70±0.03 | - | -
SignLang | CNN |  0.75±.03 |  0.75±0.04 | 0.71±0.03 |  6.60±0.72 |  7.36±0.20 |  1.10±0.05 |  2.18±0.15 |  9.15±0.10 |  0.82±0.04 |  0.89±0.04
| RF | 0.78±.04 | 0.82±0.04 | 1.03±0.05 | 3.75±0.04 | 3.52±0.10 | 1.07±0.05 | 1.23±0.05 | 0.83±0.03 | - | -
| GB | 0.79±.04 | 0.79±0.04 |  3.82±0.06 |  5.01±0.65 |  3.90±0.12 |  1.01±0.04 |  1.41±0.05 |  0.97±0.05 | - | -
Fashion | CNN | 1.12±.07 |  1.16±0.07 |  1.28±0.06 |  6.05±0.21 |  3.57±0.10 |  4.10±0.10 |  5.31±0.24 |  24.76±0.21 |  3.68±0.08 |  3.45±0.12
| RF | 1.37±.07 | 1.38±0.07 | 3.33±0.07 | 4.54±0.09 | 3.01±0.09 | 2.27±0.09 | 3.84±0.08 | 1.65±0.06 | - | -
| GB |  1.41±.07 | 1.38±0.06 |  7.70±0.08 |  8.58±0.09 |  2.63±0.09 |  2.40±0.10 |  1.51±0.07 |  2.94±0.08 | - | -
CIFAR10 |  |  |  |  |  |  |  |  |  |  |

Table 3: Relative improvement percentage of ECE of ${\underline{\mathcal{S}}^{\mathcal{M}}}$ over other calibration methods. Dataset | Model | Iso | Platt | SBC | HB | BBQ | Beta | TS | ETS
---|---|---|---|---|---|---|---|---|---
| CNN | 11.8% | 71.2% | 98.3% | 53.1% | 31.8% | 76.6% | 25.0% | 25.0%
| RF | 62.0% | 76.5% | 91.1% | 23.9% | 69.0% | 5.4% | - | -
| GB | 80.5% | 82.7% | 96.0% | 24.4% | 47.7% | 27.7% | - | -
MNIST | CNN | 2.6% | 86.9% | 98.7% | 69.7% | 65.7% | 81.3% | 58.9% | 51.9%
| RF | 85.5% | 91.2% | 97.4% | 56.5% | 88.0% | 33.9% | - | -
| GB | 93.9% | 96.9% | 98.0% | 57.0% | 93.4% | 88.6% | - | -
GTSRB | CNN | 0.0% | 25.0% | 99.5% | 92.7% | 92.7% | 92.7% | 18.2% | 25.0%
| RF | 82.6% | 95.5% | 99.5% | 50.0% | 90.7% | 72.4% | - | -
| GB | 98.3% | 98.8% | 99.8% | 84.8% | 91.0% | 90.0% | - | -
SignLang | CNN | -5.6% | 88.6% | 89.8% | 31.8% | 65.6% | 91.8% | 8.5% | 15.7%
| RF | 24.3% | 79.2% | 77.8% | 27.1% | 36.6% | 6.0% | - | -
| GB | 79.3% | 84.2% | 79.7% | 21.8% | 44.0% | 18.6% | - | -
Fashion | CNN | 12.5% | 81.5% | 68.6% | 72.7% | 78.9% | 95.5% | 69.6% | 67.5%
| RF | 58.9% | 69.8% | 54.5% | 39.6% | 64.3% | 17.0% | - | -
| GB | 81.7% | 83.6% | 46.4% | 41.2% | 6.6% | 52.0% | - | -
CIFAR10 |  |  |  |  |  |  |  |  |

This section presents the experimental results of the confidence estimation.

####  4.3.1 Estimating Confidence

Table 2 presents the main experimental results of our work. The table
summarizes ECEs for our method (with bin size $15$). Each entry in the table
describes the ECE and the 95% confidence interval. We highlight the most
accurate method for each experiment in bold. In this experiment, we perform
one hundred random splits of the data into train, validation, and test sets
for each model and dataset. We then measure the ECE of the confidence
estimation for all test set inputs, average the result and take the 95%
confidence intervals. 111For $Plat$ and $Iso$ we used the standard SKlearn
implementation. However, we used Pytorch for CNN models, and Pytorch does not
have $Plat$ and $Iso$, so we implemented them for our Pytorch-based CNN
models. First, observe that $\underline{\mathcal{S}}^{\mathcal{M}}$ and
$\overline{\mathcal{S}}^{\mathcal{M}}$ yield very similar ECEs, and that the
differences between them are usually statistically insignificant. Thus, we
conclude that $\underline{\mathcal{S}}^{\mathcal{M}}$ is a good approximation
of $\overline{\mathcal{S}}^{\mathcal{M}}$ despite being considerably simpler
to compute. The next interesting comparison is between
$\underline{\mathcal{S}}^{\mathcal{M}}$ and $Iso$. We use the same fitting
function (isotonic regression) in both cases, but $Iso$ performs the
calibration on the model’s natural uncertainty estimation, and
$\underline{\mathcal{S}}^{\mathcal{M}}$ performs the calibration on geometric
distances. Our $\underline{\mathcal{S}}^{\mathcal{M}}$ almost consistently
improves the confidence estimations across the board compared to $Iso$,
$Platt$, $SBC$, $HB$, $TS$, $ETS$, $Beta$, and $BBQ$. Specifically, we derive
improvements up to 99% in almost all tested models and datasets. Such results
demonstrate the potential of geometric signals to improve the effectiveness of
uncertainty estimation.

Table 3 describes the improvement of our fast-separation-based method over
recently proposed posthoc calibration techniques. The improvement is
calculated using the ratio of the difference between our ECE and the
competitor’s ECE. Observe that our method always improves the alternatives
except for CNNs on the Fashion dataset, where it loses by 5%. Such results
position our geometric method as a competitive approach for confidence
estimation. However, note that our fast-separtion can be used alongside the
existing methods.

####  4.3.2 Tabular Data

Fast-separation was designed for image data sets since they appear to be most
governed by geometry, that is, different images will likely be geometrically
separable. Nonetheless, as a controlled experiment, we also tested our method
on non-visual tabular data. Here, we have no apriori intuition that the
geometric signal is feasible. We used two datasets: Red wine quality Cortez et
al. (2009), which contains a total of twelve variables and 1,599 observations
and six classes, and airline passenger satisfaction Klein (2019), which
contains a total of twenty-five variables, 129,880 observations, and two
classes.

In most experiments, we saw a small improvement of ranging between 1% to 77%
in accuracy. Thus, we conclude that our method achieves good results on
tabular data as well. However, the improvement was not uniform and there were
a few cases where Iso was superior to our own. Thus, the geometric signal may
also be useful for non-visual data but further investigations are required to
adapt the method to various datasets.

##  5 Optimizing Performance

As shown in the previous section, the fast-separation approximation yields
competitive confidence estimations promptly for small and medium-sized
datasets. Nonetheless, our approach may still be too slow to handle large
datasets due to the need to calculate geometric notions on the entire training
set. To address this bottleneck, we explore the impact of several standard
methods for dimensionality reduction on the quality of our approach for
confidence estimation.

###  5.1 Handling Large Datasets

Large datasets are datasets with a large number of images or with large images
with many pixels. In such cases, each calculation of fast separation requires
potentially going over many comparisons that slow down the process. Here, we
explore ways to either reduce the image size, or to reduce the number of
images.222One can also directly manipulate the searching algorithm to improve
the calculation complexity of the nearest neighbor by, e.g., randomization or
special data structures. We leave exploring this option for future work. The
following list reviews various known techniques for reducing the
dimensionality of the data, the first four reduce the number of pixels, and
the last two reduce the number of images in the set used to calculate
geometric distances.

In order to have a fair comparison, we define the reduction parameter $t$ to
indicate the amount of data reduced in each method. In each method, a
reduction parameter $t$ implies that we reduce the dataset size by a factor of
$t^{2}$. E.g., in the Pooling technique, we can reduce 2x2 images into a pixel
reducing the image size, while K-means would reduce the number of images, and
both would reduce it by a factor of four so that the total number of pixels in
the set is the same for each reduction parameter value for all the methods.

Pooling Mosteller (1948) is an operation that calculates a function for
patches of a feature map and uses it to create a down-sampled (pooled) feature
map. For example, if one wants a 2-pool of an image, one reduces its size by
2x2, and every square of 2x2 is then represented as the output of the function
on the squared elements. Some broadly used functions for pooling are average
($pool$) and maximum ($maxpool$).

Principal Component Analysis ($PCA$) F.R.S. (1901) linearly transforms the
data into a new coordinate system where most of the variation in the data can
be described with fewer dimensions than the initial data. For reduction
parameter 2 we reduce each image to a new smaller image with a reduction
factor of four in the number of pixels.

Resizing using a Bilinear Interpolation ($RBI$) Smith (1981) is a
generalization of single dimension linear interpolation. RBI performs linear
interpolation in one direction and then again in the other direction. Resizing
using a Bilinear Interpolation is common in computer vision applications that
are based on convolutional neural networks. For a reduction parameter 2 we
resize the image to a new image in which both the length and width are two
times smaller, ending with an image four times smaller than the original one.

Sampling random pixels ($Rand_{pix}$) reduces the number of pixels in the
metadata by a random sample. Notice that this approach can be viewed as the
baseline for other pixel-reducing techniques. We chose the number of pixels
sampled to be the original pixel number divided by the squared reduction
parameter.

K-means MacQueen (1967) clustering is a vector quantization method aiming to
partition $n$ observations into $k$ clusters in which each observation belongs
to the cluster with the nearest mean (cluster centroid). K-means clustering
minimizes variances in the clusters (squared Euclidean distances). Here, we
set $k$ to be the reduced dimension of the compressed dataset. E.g., if the
original dataset had 10,000 images, and we set $k=1,000$, we get a reduction
factor of x10 from $10,000$ dimensions to $1,000$. When using this method we
first find the centroids of the dataset, and then use these as the metadata
for calculating geometric separation.

Sampling the training set ($Rand_{set}$) reduces the number of inputs in the
training set, by picking a random sample. We chose the sample size to be the
dataset size divided by the squared reduction parameter.

###  5.2 Experimental Results

|  |
---|---|---
|  |

(a)

(b)

(c)

(d)

(e)

Figure 6: Time comparison between various reduction methods on all datasets
with Random Forest model. The error bar show the 95% confidence interval over
10 shuffles. The colors denote the various reduction parameters.

To evaluate the effect of these reductions on our algorithm, we apply the
reduction to the whole dataset and then calculate the fast-separation values
on the reduced dataset. Note that the models are trained on the original
dataset, so accuracy is not affected. For RGB images, we further changed the
color to grayscale images, which reduced the size of images by a factor of 3
while keeping the image as close as possible to the original one. The
experiments were executed on a desktop PC with Intel(R) 16 Cores(TM) i7-10700
CPU @ 2.90GHz, and 16GB RAM.

Figures 6 and 7 show a comparison of the speed and accuracy of the various
methods in the Random Forest model. As shown in Figure 6, all data
optimizations increase the number of predictions per second, and we can
readily reach several hundred estimations per second which is a sufficient
speedup for our needs. All methods show almost the same speedup on the
algorithm for each hyperparameter value, except for k-means which sometimes
has a better speedup and RBI which has a slightly lower speedup. Since there
is little variability in the experiments, the confidence intervals are barely
visible.

Our experiments show that the time performance is not affected by the model.
Thus, Figure 6 presents only the results for the Random forest model, i.e.,
the average number of predictions per second. Observe that the number of
predictions per seconds is the same for all other models.

Importantly, this improvement in runtime does not come at a meaningful cost
for the confidence estimation, as shown in Figure 7. While the error in the
calibration estimation slightly changes across different methods and reduction
parameters, the changes seem insignificant. Specifically, in the SignLanguage
dataset we observe an increase in the ECE, which we believe is due to the fact
that the original dataset is already quite small, rendering the datasize
optimization pointless. Our experiments also show similar behavior across
different models. For example, Figure 8 shows that all three models obtain
similar errors with maxpooling with different parameters. Moreover, our
results outperform most state-of-the-art algorithms even with a 4-pool.

|  |
---|---|---
|  |

(a)

(b)

(c)

(d)

(e)

Figure 7: ECE comparison between various reduction methods on all datasets
with Random forest model. The error bar show the 95% confidence interval over
10 shuffles. The black line shows the ECE score of the method without any
reduction. The colors denote the various reduction parameters.

|  |
---|---|---

(a)

(b)

(c)

Figure 8: ECE measures with $95\%$ confidence intervals on 10 shuffles for
various datasets on several models after applying max-pooling with different
reduction parameters.

When using our method one needs to ship besides the model and the fitting
function also the dataset itself, since the calculation of the fast-separation
requires the calculation of distances to all images in the training set. This
may imply memory overhead, which can be critical when using big datasets.
Using a reduction of the dataset allows us to reduce the training set size
needed to be shipped. As we have shown, the reduced dataset still obtains
improved results, thus freeing memory usage of the algorithm. Users can also
predetermine the trade-off they would like between throughput or memory and
ECE and adjust the reduction parameters accordingly.

##  6 Conclusion

Our work introduces geometric separation-based algorithms for confidence
estimation in machine learning models. Specifically, we measure a geometric
separation score and use the specific model to translate each score value into
a confidence value using a standard post-hoc calibration method. Thus, inputs
close to training set examples of the same class receive higher confidence
than those close to examples with a different classification. Thus, our
algorithms depend on the specific model but as a black box resulting in
methods that work for all machine learning models.

Our evaluation shows that geometric separation improves confidence estimations
in visual workloads. However, calculating geometric separation is
computationally complex and time intensive. Thus, we suggest multiple
approximation techniques to speed up the process and bring it to practicality.
Our extensive evaluation shows that such approximations retain most of the
benefits of geometric separations and drastically improve confidence
estimation along with supporting many calculations per second, enabling real-
time applications. For example, we can process live camera feeds at multiple
hundreds of calculations per second.

Our work is unique because it extracts a new external signal to derive
confidence estimations. Thus, we can leverage the existing post-hoc
calibration techniques to calibrate our signal and meet various optimization
criteria. We showed that the same calibration method (Isotonic regression)
yields a lower ECE when performed on the geometric signal rather than on the
model’s original signal. The achieved accuracy improves on a diverse set of
recently proposed calibration methods. Notably, our approach reduces the error
in confidence estimations by up to 99% compared to alternative methods
(depending on the specific dataset and model).

Looking into the future, we plan to address the dependence of this work on
normalized inputs and tackle datasets with variable-sized images. In such
datasets, the geometric distances may also depend on the resolution and
alignment of the object. As a director, we plan to use the CNN middle layer
latent space as the feeding vector (rather than the original images) in the
geometric separation calculation. In any case, the ability to derive fast
approximations of geometric separation would be a valuable tool in future
research.

## References

  * Ashukha et al. (2020) A. Ashukha, A. Lyzhov, D. Molchanov, and D. Vetrov.  Pitfalls of In-Domain Uncertainty Estimation and Ensembling in Deep Learning.  In _International Conference on Learning Representations_ , 2020.
  * Bergstra and Yoshua (2012) J. Bergstra and B. Yoshua.  Random search for hyper-parameter optimization.  _Journal of machine learning research_ , 13(2), 2012.
  * Breiman (2001) L. Breiman.  Random Forests.  _Machine Learning_ , 45(1):5–32, 2001.
  * Cortez et al. (2009) P. Cortez, A. Cerdeira, F. Almeida, T. Matos, and J. Reis.  Modeling wine preferences by data mining from physicochemical properties.  2009\.  https://archive.ics.uci.edu/ml/datasets/wine+quality.
  * Dalitz (2009) C. Dalitz.  Reject options and confidence measures for knn classifiers.  _Schriftenreihe des Fachbereichs Elektrotechnik und Informatik der Hochschule Niederrhein_ , 8:16–38, 01 2009.
  * Ding et al. (2020) Z. Ding, X. Han, P. Liu, and M. Niethammer.  Local temperature scaling for probability calibration.  _CoRR_ , abs/2008.05105, 2020.
  * Ehlers (2017) R. Ehlers.  Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks.  In D. D’Souza and K. N. Kumar, editors, _Automated Technology for Verification and Analysis_ , volume 10482 of _Lecture Notes in Computer Science_ , pages 269–286. Springer, 2017.
  * Einziger et al. (2019) G. Einziger, M. Goldstein, Y. Sa’ar, and I. Segall.  Verifying Robustness of Gradient Boosted Models.  In _The Thirty-Third Conference on Artificial Intelligence,_ , pages 2446–2453. AAAI, 2019.
  * F.R.S. (1901) K. Pearson F.R.S.  Liii. on lines and planes of closest fit to systems of points in space.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ , 2(11):559–572, 1901.  doi: 10.1080/14786440109462720.
  * Gal and Ghahramani (2016) Y. Gal and Z. Ghahramani.  Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning.  In _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 1050–1059, 2016.
  * Gal et al. (2017) Y. Gal, J. Hron, and A. Kendall.  Concrete Dropout.  In _Advances in Neural Information Processing Systems_ , volume 30, 2017.
  * Garipov et al. (2018) T. Garipov, P. Izmailov, D. Podoprikhin, D. P. Vetrov, and A. G. Wilson.  Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018_ , pages 8803–8812, 2018.
  * Gehr et al. (2018) T. Gehr, M. Mirman, D. Drachsler-Cohen, P. Tsankov, S. Chaudhuri, and M.T. Vechev.  Ai2: Safety and robustness certification of neural networks with abstract interpretation.  pages 3–18, 05 2018.  doi: 10.1109/SP.2018.00058.
  * Gu et al. (2018) J. Gu, Z. Wang, J. Kuen, L. Ma, A. Shahroudy, B. Shuai, T. Liu, X. Wang, G. Wang, J. Cai, and T. Chen.  Recent Advances in Convolutional Neural Networks.  _Pattern Recognition_ , 77:354–377, 2018.
  * Guo et al. (2017a) C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger.  On Calibration of Modern Neural Networks.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 1321–1330, 2017a.
  * Guo et al. (2017b) C. Guo, G. Pleiss, Y. Sun, and K.Q. Weinberger.  On Calibration of Modern Neural Networks.  In _Proceedings of the 34th International Conference on Machine Learning_ , ICML, page 1321–1330, 2017b.
  * Gupta and Ramdas (2021) C. Gupta and A. Ramdas.  Distribution-free Calibration Guarantees for Histogram Binning without Sample Splitting.  In _International Conference on Machine Learning_ , pages 3942–3952. PMLR, 2021.
  * Hebert-Johnson et al. (2018) Ursula Hebert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum.  Multicalibration: Calibration for the (Computationally-identifiable) masses.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1939–1948. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/hebert-johnson18a.html.
  * Hendrycks et al. (2019a) D. Hendrycks, K. Lee, and M. Mazeika.  Using Pre-Training Can Improve Model Robustness and Uncertainty.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2712–2721, 2019a.
  * Hendrycks et al. (2019b) D. Hendrycks, M. Mazeika, S. Kadavath, and D. Song.  Using Self-Supervised Learning Can Improve Model Robustness and Uncertainty.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019b.
  * Houben et al. (2013) S. Houben, J. Stallkamp, J. Salmen, M. Schlipsing, and C. Igel.  Detection of Traffic Signs in Real-World Images: The German Traffic Sign Detection Benchmark.  _The 2013 International Joint Conference on Neural Networks (IJCNN)_ , (1288):1–8, 2013.
  * Huang et al. (2017a) G. Huang, Y. Li, G. Pleiss, Z. Liu, J. E. Hopcroft, and K. Q. Weinberger.  Snapshot ensembles: Train 1, get M for free.  In _5th International Conference on Learning Representations, ICLR_ , 2017a.
  * Huang et al. (2017b) X. Huang, M. Kwiatkowska, S. Wang, and M. Wu.  Safety Verification of Deep Neural Networks.  In _Computer Aided Verification_ , pages 3–29, 2017b.
  * Katz et al. (2017) G. Katz, C.W. Barrett, D.L. Dill, K. Julian, and M.J. Kochenderfer.  Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks.  In _Computer Aided Verification - 29th International Conference, CAV_ , pages 97–117, 2017.
  * Kerrigan et al. (2021) G. Kerrigan, P. Smyth, and M. Steyvers.  Combining human predictions with model probabilities via confusion matrices and calibration.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Klein (2019) T. Klein.  Airline Passenger Satisfaction.  2019\.  https://www.kaggle.com/datasets/teejmahal20/airline-passenger-satisfaction/.
  * Krishnan and Tickoo (2020) R. Krishnan and O. Tickoo.  Improving Model Calibration with Accuracy versus Uncertainty Optimization.  33:18237–18248, 2020.
  * Krizhevsky et al. (2009) A. Krizhevsky, V. Nair, and G. Hinton.  Cifar-10 (canadian institute for advanced research).  2009\.  URL http://www.cs.toronto.edu/~kriz/cifar.html.
  * Kull et al. (2017) M. Kull, F. T. Silva, and P. Flach.  Beta calibration: a well-founded and easily implemented improvement on logistic calibration for binary classifiers.  In _Artificial Intelligence and Statistics_ , pages 623–631. PMLR, 2017.
  * Kull et al. (2019) M. Kull, M. Perello Nieto, M. Kängsepp, T. Silva Filho, H. Song, and P. Flach.  Beyond Temperature Scaling: Obtaining Well-calibrated Multi-class Probabilities with Dirichlet Calibration.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Kumar et al. (2019) A. Kumar, P. Liang, and Te. Ma.  Verified Uncertainty Calibration.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 32, 2019.
  * Küppers et al. (2020) F. Küppers, J. Kronenberger, A. Shantia, and A. Haselhoff.  Multivariate confidence calibration for object detection.  In _The IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2020.
  * Lakshminarayanan et al. (2017) B. Lakshminarayanan, A. Pritzel, and C. Blundell.  Simple and scalable predictive uncertainty estimation using deep ensembles.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 6405–6416, 2017.
  * LeCun and Cortes (2010) Y. LeCun and C. Cortes.  MNIST handwritten digit database.  2010\.  http://yann.lecun.com/exdb/mnist/.
  * Leistner et al. (2009) C. Leistner, A. Saffari, P. M. Roth, and H. Bischof.  On Robustness of On-line Boosting - a Competitive Study.  In _12th International Conference on Computer Vision Workshops, ICCV_ , pages 1362–1369, 2009.
  * Leman et al. (2022) L. Leman, G. Chouraqui, L. Cohen, and G. Einzinger.  Geometric Uncertainty Github.  https://github.com/NoSleepDeveloper/Geometric-Calibrator, 2022.
  * Ma et al. (2021) C. Ma, Z. Huang, J. Xian, M. Gao, and J. Xu.  Improving Uncertainty Calibration of Deep Neural Networks via Truth Discovery and Geometric Optimization.  In _Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence_ , volume 161 of _Proceedings of Machine Learning Research_ , pages 75–85, 2021.
  * MacQueen (1967) J. B. MacQueen.  Some methods for classification and analysis of multivariate observations.  In L. M. Le Cam and J. Neyman, editors, _Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability_ , volume 1, pages 281–297. University of California Press, 1967.
  * Maddox et al. (2019) W. J. Maddox, P. Izmailov, T. Garipov, D. P. Vetrov, and A. G. Wilson.  A Simple Baseline for Bayesian Uncertainty in Deep Learning.  In _Advances in Neural Information Processing Systems_ , volume 32, page 12, 2019.
  * Mason et al. (1999) L. Mason, J. Baxter, P. Bartlett, and M. Frean.  Boosting Algorithms As Gradient Descent.  In _Proceedings of the 12th International Conference on Neural Information Processing Systems_ , NIPS, pages 512–518, 1999.
  * Moosavi-Dezfooli et al. (2017) S. Moosavi-Dezfooli, A. Fawzi, O. Fawzi, and P. Frossard.  Universal Adversarial Perturbations.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 86–94, 2017.
  * Mosteller (1948) F. Mosteller.  On pooling data.  _Journal of the American Statistical Association_ , 43(242):231–242, 1948.  doi: 10.1080/01621459.1948.10483259.  URL https://www.tandfonline.com/doi/abs/10.1080/01621459.1948.10483259.
  * Mozafari et al. (2018) A. S. Mozafari, H. S. Gomes, W. Leão, S. Janny, and C. Gagné.  Attended temperature scaling: a practical approach for calibrating deep neural networks.  _arXiv preprint arXiv:1810.11586_ , 2018.
  * Müller et al. (2019) R. Müller, S. Kornblith, and G. E Hinton.  When does label smoothing help?  In _Advances in Neural Information Processing Systems_ , volume 32, pages 4696–4705, 2019.
  * Naeini et al. (2015) M.P. Naeini, G.F. Cooper, and M. Hauskrecht.  Obtaining Well Calibrated Probabilities Using Bayesian Binning.  In _AAAI_ , page 2901–2907, 2015.
  * Narodytska et al. (2018) N. Narodytska, S.P. Kasiviswanathan, L. Ryzhyk, M. Sagiv, and T. Walsh.  Verifying Properties of Binarized Deep Neural Networks.  In _32nd AAAI Conference on Artificial Intelligence, AAAI 2018_ , pages 6615–6624, 2018.
  * Niculescu-Mizil and Caruana (2005) A. Niculescu-Mizil and R. Caruana.  Predicting Good Probabilities with Supervised Learning.  In _Proceedings of the 22nd International Conference on Machine Learning_ , ICML, page 625–632, 2005.
  * Niculescu-Mizil and Caruana (2006) A. Niculescu-Mizil and R. Caruana.  An Empirical Comparison of Supervised Learning Algorithms.  In _Proceedings of the 23rd International Conference on Machine Learning_ , ICML, pages 161–168, 2006.
  * Pakdaman and Cooper (2016) N. Pakdaman and G. Cooper.  Binary classifier calibration using an ensemble of near isotonic regression models.  In _2016 IEEE 16th International Conference on Data Mining (ICDM)_ , pages 360–369. IEEE, 2016.
  * Perez-Lebel et al. (2022) Alexandre Perez-Lebel, Marine Le Morvan, and Gaël Varoquaux.  Beyond calibration: estimating the grouping loss of modern neural networks.  working paper or preprint, December 2022.  URL https://hal.archives-ouvertes.fr/hal-03829870.
  * Platt (1999) J. Platt.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  _Advances in large margin classifiers_ , 10(3):61–74, 1999.
  * Smith (1981) P.R. Smith.  Bilinear interpolation of digital images.  _Ultramicroscopy_ , 6(1):201–204, 1981.  ISSN 0304-3991.  doi: https://doi.org/10.1016/S0304-3991(81)80199-4.  URL https://www.sciencedirect.com/science/article/pii/S0304399181801994.
  * Sun et al. (2007) Y. Sun, S. Todorovic, and J. Li.  Increasing the Robustness of Boosting Algorithms within the Linear-programming Framework.  _The Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology_ , 48(1):5–20, 2007.
  * Techperson (2017) Techperson.  Sign Language MNIST.  2017\.  https://www.kaggle.com/datamunge/sign-language-mnist/.
  * Thulasidasan et al. (2019) S. Thulasidasan, G. Chennupati, J. A. Bilmes, T. Bhattacharya, and S. Michalak.  On Mixup Training: Improved Calibration and Predictive Uncertainty for Deep Neural Networks.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurIPS_ , pages 13888–13899, 2019.
  * Tomani et al. (2022) C. Tomani, D. Cremers, and F. Buettner.  Parameterized temperature scaling for boosting the expressive power in post-hoc uncertainty calibration.  In _European Conference on Computer Vision_ , pages 555–569. Springer, 2022.
  * Wenger et al. (2019) J. Wenger, H. Kjellstrm, and R. Triebel.  Non-parametric calibration for classification.  _CoRR_ , abs/1906.04933, 2019.
  * Xiao et al. (2017) H. Xiao, K. Rasul, and R. Vollgraf.  Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms.  _CoRR_ , abs/1708.07747, 2017.
  * Xing et al. (2020) C. Xing, S. Arik, Z. Zhang, and T. Pfister.  Distance-Based Learning from Errors for Confidence Calibration.  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Zadrozny and Elkan (2002) B. Zadrozny and C. Elkan.  Transforming Classifier Scores into Accurate Multiclass Probability Estimates.  _Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , page 694–699, 08 2002.
  * Zhang et al. (2020) J. Zhang, B. Kailkhura, and T. YJ Han.  Mix-n-Match : Ensemble and Compositional Methods for Uncertainty Calibration in Deep Learning.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 11117–11128, 2020.
  * Zhang and Haghani (2015) Y. Zhang and A. Haghani.  A Gradient Boosting Method to Improve Travel Time Prediction.  _Transportation Research Part C: Emerging Technologies_ , 58:308–324, 2015.


# Treatment-wise Glioblastoma Survival Inference with Multi-parametric
Preoperative MRI

Xiaofeng Liu  Gordon Center for Medical Imaging, Massachusetts General
Hospital and Harvard Medical School, Boston, MA 02114 USA  Nadya Shusharina
Dept. of Radiation Oncology, Massachusetts General Hospital and Harvard
Medical School, Boston, MA 02114, USA  Helen A Shih  Dept. of Radiation
Oncology, Massachusetts General Hospital and Harvard Medical School, Boston,
MA 02114, USA  C.-C. Jay Kuo  Dept. of Electrical and Computer Engineering,
University of Southern California, Los Angeles, CA 90007, USA  Georges El
Fakhri  Dept. of Radiology and Biomedical Imaging, Yale University, New
Heaven, CT 06519, USA  Jonghye Woo  Gordon Center for Medical Imaging,
Massachusetts General Hospital and Harvard Medical School, Boston, MA 02114
USA

###### Abstract

In this work, we aim to predict the survival time (ST) of glioblastoma (GBM)
patients undergoing different treatments based on preoperative magnetic
resonance (MR) scans. The personalized and precise treatment planning can be
achieved by comparing the ST of different treatments. It is well established
that both the current status of the patient (as represented by the MR scans)
and the choice of treatment are the cause of ST. While previous related MR-
based glioblastoma ST studies have focused only on the direct mapping of MR
scans to ST, they have not included the underlying causal relationship between
treatments and ST. To address this limitation, we propose a treatment-
conditioned regression model for glioblastoma ST that incorporates treatment
information in addition to MR scans. Our approach allows us to effectively
utilize the data from all of the treatments in a unified manner, rather than
having to train separate models for each of the treatments. Furthermore,
treatment can be effectively injected into each convolutional layer through
the adaptive instance normalization we employ. We evaluate our framework on
the BraTS20 ST prediction task. Three treatment options are considered: Gross
Total Resection (GTR), Subtotal Resection (STR), and no resection. The
evaluation results demonstrate the effectiveness of injecting the treatment
for estimating GBM survival.

###### keywords:

Survival Prediction, Individualized Treatment Effect, Glioblastoma, Magnetic
Resonance Imaging.

##  1 Introduction

Glioblastoma (GBM) is one of the most aggressive malignant brain tumors, with
a particularly poor survival rate. Despite significant advances in medical
treatments for brain tumors, the median survival duration for GBM patients
remains limited [1]. The prognosis of GBM can vary widely depending on the
patient’s individual status and treatment approach.

We propose to develop a data-driven deep learning (DL) model to answer the
question of whether a GBM patient would have a longer survival time (ST) with
alternative treatments, based on the preoperative magnetic resonance (MR)
scans. Our goal is to enable treatment-specific ST prediction, allowing for a
comprehensive comparison of different treatments for a given patient. This
capability is highly desired in the field of precision medicine, as it
provides valuable insights for informed treatment planning.

The complementary status is a basis for an accurate prediction of ST. In
addition to the tabular electronic health record (EHR) [2], there is
increasing evidence that the multi-parametric MR scans have shown great
potential for GBM prognosis [3, 4]. Richer information can be expected from
multimodal imaging. However, previous studies in MR-based GBM survival
prediction have primarily focused on modeling a direct mapping from GBM
patient status (represented as MR scans) to ST with direct models [1],
ignoring the underlying causal relationship between treatments and ST.

In practice, the influence of both the current state of the patient and the
selection of treatment on the effect of the outcome is well justified [5, 6].
However, the previous direct models either focused on a single treatment [3,
4, 7] or did not incorporate the impact of the treatment [8, 9]. In
particular, without taking treatment into account, it is not possible to
achieve a comparison between treatments to instruct the following treatment
planning [10]. Although a possible solution is to have different direct models
for each treatment, there is only a limited amount of training data that can
be used for each model.

To the best of our knowledge, this is the first attempt at a DL-based
multimodal medical imaging study for individualized multi-treatment advisory,
which takes both comprehensive multi-parametric preoperative MR status
depictions and treatment selection into consideration for GBM survival
inference. By considering the patient’s MR scans and incorporating the
treatment information in a unified framework, our proposed approach aims to
unravel the intricate relationship between treatments and ST, thereby
facilitating more accurate and personalized treatment decisions.

To this end, in this work, we propose to address the above issues with a
treatment-conditioned GBM survival regression model using preoperative MR
scans. Instead of training independent models for each treatment, we are able
to use all treatment data in a unified manner. Specifically, we adopt a
multichannel convolutional backbone as the previous direct model [9] to
aggregate the information in registered multiparametric MR scans and the
corresponding segmentation map. Then, the treatment vector is integrated with
either concatenation in the fully connected layer or the adaptive instance
normalization (AdaIN) as in [11, 12, 13, 14, 15] in each convolutional layer
of the survival time prediction network. In particular, we normalize the mean
($\mu$) and variance ($\sigma$) of AdaIN layers to align with the relative-
pose code $z$ instead of the feature map itself. Injecting treatment at
earlier stages in a more interactive manner can potentially contribute to
fine-grained treatment-conditioned modeling.

We evaluate the performance of our framework on the BraTS2020 survival
prediction task [16], considering three potential types of tumor resection.
Our evaluation results demonstrate the effectiveness of our approach in
estimating GBM survival and the benefit of the introduction of treatment.

Figure 1: Illustration of our framework for the treatment-wise GBM survival
time estimation with multi-parametric preoperative MR scans and segmentation
mask. The treatment is injected by the AdaIN to every convolutional layer.

##  2 METHODS

The patient status $\bm{s}$ and treatment $\bm{t}$ are used to predict the
effect $\bm{y}$ in individualized treatment effect inference. Specifically, in
GBM survival analysis, multiparametric MR scans and the corresponding
segmentation masks have been widely used to represent the status $\bm{s}$,
which includes the location and radiomic features. In addition to the medical
imaging status, the choice of treatment may also affect survival. For
generality, we have a one-hot treatment vector $\bm{t}\in\mathbb{R}^{N}$ for
$N$ possible treatment choices. Although it can be simplified to 0/1 for the
binary treatment case, we aim to train a unified model
$f:\\{\bm{s},\bm{t}\\}\rightarrow\bm{y},\forall\bm{t}$.

For a fair comparison, we follow the previous work [9] and adopt the four
layers of convolutional neural networks for 3D multi-modality information
fusion. Then, we make use of three fully connected layers, each with a one-
dimensional output unit, to predict the scalar value of survival days.
Moreover, in the previous work [9], the patient age and manually crafted
radiomics features were concatenated with the first fully connected layer
representations, and then processed by either a neural network or conventional
machine learning methods. However, in the present work, we focus solely on
investigating the neural network approach and do not include the manually
crafted features. Nevertheless, these predictive features can be easily
incorporated if needed.

Instead, our objective is to investigate the impact of inducing treatment
$\bm{t}$ to achieve a more accurate ST estimation by modeling fine-grained
treatmentwise $p(\bm{y}|\bm{t})$ with a unified framework. Thus, a critical
problem is how to seamlessly induce treatment $\bm{t}$ into the status feature
extraction to model the conditional distribution. In previous conditional
generative works [17, 11], it has been shown that simple concatenation in a
fully connected layer can be less effective in combining two features, as the
previous convolution layers are not well-informed, and hard to learn their
correlation with limited subsequent parameters.

Therefore, following previous successful conditional modeling works[17, 11],
we propose to adopt adaptive instance normalization (AdaIN) [18] to induce
treatment $\bm{t}$ in each convolutional layer. Specifically, we process
$\bm{t}$ with three multi-layer perceptron (MLP) layers (all with 16-dim) to
produce a 16-dim vector $\bm{z}\in\mathbb{R}^{16}$ in the intermediate latent
space $\mathcal{Z}$, the learned affine transformations, i.e., the linear
layers of each layer, then specialize $\bm{z}$ to scalars of treatment-wise
scale and bias $\bm{t_{i}^{\prime}}=(t^{s}_{i},t^{b}_{i})$ in the $i$-th
convolutional layer to control the AdaIN operators. Note that the
dimensionality of $t^{s}_{i}$ or $t^{b}_{i}$ should match the number of
feature maps in that layer, which requires the dimension of the linear layer
to be twice that of $t^{s}_{i}$ or $t^{b}_{i}$. Specifically, we have the
following AdaIN operation in each layer:

$AdaIN(\bm{x}_{i},\bm{t^{\prime}})=t_{i}^{s}\frac{\bm{x}_{i}-\mu(\bm{x}_{i})}{\sigma(\bm{x}_{i})}+t_{i}^{b},$
(1)

where $\bm{x}_{i}$ is the extracted feature map after the $i$-th convolutional
layer. As a result, $\bm{x}_{i}$ is individually normalized and subsequently
scaled and biased using the corresponding scalar components from
$\bm{t_{i}^{\prime}}=(t^{s}_{i},t^{b}_{i})$. By doing so, it injects a
stronger inductive bias of $\bm{t}$ into the DL model. The model $f$ is
detailed in Fig. 1, which is trained by the mean absolute error (MAE), i.e.,
$|f(\bm{x},\bm{t})-\bm{y}|$.

Table 1: Numerical comparisons of different inputs and their combination
methods. The best results are indicated in bold. The standard deviation is
reported based on five random trials.

Status | Treatment |  | MAE (in days)
---|---|---|---
4 MR scans [9] | - | - | 165.8$\pm$6.2
4 MR scans [This paper] | $\surd$ | Concatenation | 140.2$\pm$9.0
4 MR scans [This paper] | $\surd$ | AdaIN |  132.7$\pm$7.8
4 MR scans + Segmentation mask [9] | - | - | 124.4$\pm$5.3
4 MR scans + Segmentation mask [This paper] | $\surd$ | Concatenation | 103.5$\pm$4.9
4 MR scans + Segmentation mask [This paper] | $\surd$ | AdaIN |  98.2$\pm$5.6

##  3 RESULTS

In the BraTS 2020 dataset [19, 16], the preoperative T1-weighted (T1),
T1-weighted with contrast enhancement (T1-CE), T2-weighted (T2), and fluid
attenuation inversion recovery (FLAIR) MR scans and the segmentation mask are
collected as the status. Survival days (5-1767d) are reported for 236
subjects. 119 were treated with Gross Total Resection (GTR), 10 with Subtotal
Resection (STR), and 107 had no treatment (NA). We use the subject-independent
5-fold cross-evaluation on the 236 subjects, in which both training and test
sets contain three treatments. Note that the split is different from the
previous direct model [9], which does not consider the distribution of
treatments. In addition, it is difficult to independently train a separate
model for STR with very limited samples. The training was performed on an
NVIDIA A100 GPU for 200 epochs.

We input status $\bm{x}=${multi-parametric MRs, segmentation} and treatment
$\bm{t}=${GTR, STR, NA} to predict the survival day $\bm{y}$. We adopt their
multi-channel 3D convolutional network as our backbone to process the four-
channel 3D MR scans, which can be extended to incorporate the segmentation
mask as five channels. Our framework was implemented using the PyTorch deep
learning toolbox [20]. For performance quantification, the MAE is reported in
Table 1. We can see that adding the treatment to the survival estimation can
significantly reduce MAE. Furthermore, the AdaIN injection shows a superior
capability to effectively combine the patient status and treatment compared to
the simple concatenation method at the first fully connected layer.

##  4 CONCLUSION

In this work, we introduced a novel and accurate survival estimation model for
GBM, using preoperative MRI data and segmentation maps to model the fine-
grained treatment-dependent distribution. Our framework efficiently injects
the treatment vector into the status representation extraction process.
Compared with conventional direct models that do not consider treatment [9],
or simply concatenate the treatment vector into the FC layers, our model
demonstrates superior and effective performance. Moreover, our approach can
serve as a simple add-on module to enhance more advanced backbones used in
direct models, such as vision transformers. In future work, we will replace
the manual segmentation map with the predictions of advanced DL-based tumor
segmentation models [21, 22, 23, 24, 25] to establish a fully automated
analysis pipeline.

###### Acknowledgements.

This work is supported by R01CA165221 and P41EB022544.

## References

  * [1] Kaur, G., Rana, P. S., and Arora, V., “State-of-the-art techniques using pre-operative brain mri scans for survival prediction of glioblastoma multiforme patients and future research directions,” Clinical and Translational Imaging 10(4), 355–389 (2022).
  * [2] Lacroix, M., Abi-Said, D., Fourney, D. R., Gokaslan, Z. L., Shi, W., DeMonte, F., Lang, F. F., McCutcheon, I. E., Hassenbusch, S. J., Holland, E., et al., “A multivariate analysis of 416 patients with glioblastoma multiforme: prognosis, extent of resection, and survival,” Journal of Neurosurgery 95(2), 190–198 (2001).
  * [3] Chang, K., Zhang, B., Guo, X., Zong, M., Rahman, R., Sanchez, D., Winder, N., Reardon, D. A., Zhao, B., Wen, P. Y., et al., “Multimodal imaging patterns predict survival in recurrent glioblastoma patients treated with bevacizumab,” Neuro-oncology 18(12), 1680–1687 (2016).
  * [4] Nie, D., Lu, J., Zhang, H., Adeli, E., Wang, J., Yu, Z., Liu, L., Wang, Q., Wu, J., and Shen, D., “Multi-channel 3d deep feature learning for survival time prediction of brain tumor patients using multi-modal neuroimages,” Scientific Reports 9(1), 1–14 (2019).
  * [5] Athey, S. and Imbens, G., “Recursive partitioning for heterogeneous causal effects,” Proceedings of the National Academy of Sciences 113(27), 7353–7360 (2016).
  * [6] Shalit, U., Johansson, F. D., and Sontag, D., “Estimating individual treatment effect: generalization bounds and algorithms,” in [International Conference on Machine Learning ], 3076–3085, PMLR (2017).
  * [7] Chaddad, A., Desrosiers, C., Hassan, L., and Tanougast, C., “A quantitative study of shape descriptors from glioblastoma multiforme phenotypes for predicting survival outcome,” The British journal of radiology 89(1068), 20160575 (2016).
  * [8] Baid, U., Rane, S. U., Talbar, S., Gupta, S., Thakur, M. H., Moiyadi, A., and Mahajan, A., “Overall survival prediction in glioblastoma with radiomic features using machine learning,” Frontiers in Computational Neuroscience , 61 (2020).
  * [9] Huang, H., Zhang, W., Fang, Y., Hong, J., Su, S., and Lai, X., “Overall survival prediction for gliomas using a novel compound approach,” Frontiers in Oncology 11, 724191 (2021).
  * [10] Tan, K., Huang, W., Liu, X., Hu, J., and Dong, S., “A multi-modal fusion framework based on multi-task correlation learning for cancer prognosis prediction,” Artificial Intelligence in Medicine 126, 102260 (2022).
  * [11] Liu, X., Che, T., Lu, Y., Yang, C., Li, S., and You, J., “Auto3d: Novel view synthesis through unsupervisely learned variational viewpoint and global 3d representation,” in [European Conference on Computer Vision ], 52–71, Springer (2020).
  * [12] Xu, X., Chen, Y.-C., and Jia, J., “View independent generative adversarial network for novel view synthesis,” in [Proceedings of the IEEE International Conference on Computer Vision ], 7791–7800 (2019).
  * [13] Huang, H., He, R., Sun, Z., Tan, T., et al., “Introvae: Introspective variational autoencoders for photographic image synthesis,” in [Advances in Neural Information Processing Systems ], 52–63 (2018).
  * [14] Nguyen-Phuoc, T., Li, C., Theis, L., Richardt, C., and Yang, Y.-L., “Hologan: Unsupervised learning of 3d representations from natural images,” arXiv preprint arXiv:1904.01326 (2019).
  * [15] Zakharov, E., Shysheya, A., Burkov, E., and Lempitsky, V., “Few-shot adversarial learning of realistic neural talking head models,” arXiv preprint arXiv:1905.08233 (2019).
  * [16] Bakas, S., Reyes, M., Jakab, A., Bauer, S., Rempfler, M., Crimi, A., Shinohara, R. T., Berger, C., Ha, S. M., Rozycki, M., et al., “Identifying the best machine learning algorithms for brain tumor segmentation, progression assessment, and overall survival prediction in the brats challenge,” arXiv preprint arXiv:1811.02629 (2018).
  * [17] Karras, T., Laine, S., and Aila, T., “A style-based generator architecture for generative adversarial networks,” in [IEEE / CVF Computer Vision and Pattern Recognition Conference ], 4401–4410 (2019).
  * [18] Huang, X. and Belongie, S., “Arbitrary style transfer in real-time with adaptive instance normalization,” in [Proceedings of the IEEE International Conference on Computer Vision ], 1501–1510 (2017).
  * [19] Bakas, S., “Multimodal brain tumor segmentation challenge 2020: Data
https://www.med.upenn.edu/cbica/brats2020/data.html,” (2020).

  * [20] Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A., “Automatic differentiation in pytorch,” (2017).
  * [21] Liu, X., Xing, F., El Fakhri, G., and Woo, J., “Memory consistent unsupervised off-the-shelf model adaptation for source-relaxed medical image segmentation,” Medical image analysis 83, 102641 (2023).
  * [22] Liu, X., Xing, F., Yang, C., El Fakhri, G., and Woo, J., “Adapting off-the-shelf source segmenter for target medical image segmentation,” in [International Conference on Medical Image Computing and Computer-Assisted Intervention ], 549–559, Springer (2021).
  * [23] Liu, X., Xing, F., El Fakhri, G., and Woo, J., “Self-semantic contour adaptation for cross modality brain tumor segmentation,” in [2022 IEEE 19th International Symposium on Biomedical Imaging ], 1–5 (2022).
  * [24] Liu, X., Xing, F., Shusharina, N., Lim, R., Kuo, C., Fakhri, G. E., and Woo, J., “Act: Semi-supervised domain-adaptive medical image segmentation with asymmetric co-training,” International Conference on Medical Image Computing and Computer Assisted Intervention (2022).
  * [25] Liu, X., Shih, H. A., Xing, F., Santarnecchi, E., El Fakhri, G., and Woo, J., “Incremental learning for heterogeneous structure segmentation in brain tumor mri,” in [International Conference on Medical Image Computing and Computer-Assisted Intervention ], 46–56, Springer (2023).