An Ambiguity Measure for Recognizing the Unknowns in Deep Learning

Roozbeh Yousefzadeh
Huawei Hong Kong Research Center
[email protected]

Abstract

We study the understanding of deep neural networks from the scope in which they are trained on. While the accuracy of these models is usually impressive on the aggregate level, they still make mistakes, sometimes on cases that appear to be trivial. Moreover, these models are not reliable in realizing what they do not know leading to failures such as adversarial vulnerability and out-of-distribution failures. Here, we propose a measure for quantifying the ambiguity of inputs for any given model with regard to the scope of its training. We define the ambiguity based on the geometric arrangements of the decision boundaries and the convex hull of training set in the feature space learned by the trained model, and demonstrate that a single ambiguity measure may detect a considerable portion of mistakes of a model on in-distribution samples, adversarial inputs, as well as out-of-distribution inputs. Using our ambiguity measure, a model may abstain from classification when it encounters ambiguous inputs leading to a better model accuracy not just on a given testing set, but on the inputs it may encounter at the world at large. In pursuit of this measure, we develop a theoretical framework that can identify the unknowns of the model in relation to its scope. We put this in perspective with the confidence of the model and develop formulations to identify the regions of the domain which are unknown to the model, yet the model is guaranteed to have high confidence.

1 Introduction

How can a model know what it does not know? How can we develop models that can reliably relate inputs to their knowledge and abstain from processing inputs that are ambiguous to them? In many applications of deep learning, e.g., in object detection, we encounter inputs that are hard to process and evaluate, i.e., corner cases. Consider the case of autonomous driving where a model may encounter ambiguous images, e.g., a pedestrian with an unusual clothing, etc. These are potentially points that may lead to accidents and it would be useful to automatically quantify whether a model is uncertain about its decisions. Moreover, a model may encounter inputs that are adversarially designed to mislead it [30]. We also have cases of out-of-distribution inputs [14]. All these cases can be considered various types of input ambiguity for a given model, i.e., the unknowns of the model, potentially leading to its failure. If we have tools to detect such inputs when we encounter them, we can have the model make more conservative decisions or abstain all together. For example, an autonomous car could decide to slow down or stop by the side of the road, if it is unsure about what it sees in the road ahead.

Refer to caption — Figure 1: We propose a unified ambiguity framework to identify the knowns and unknowns of deep learning models.

The problem is that usually unknowns of a model is unknown to itself. In other words, AI models usually do not know what they do not know [22]. Indeed, the question of recognizing the unknowns of a model is central in many applications of AI models. In the literature, we have separate fields that study adversarial vulnerabilities [11] and out-of-distribution generalization [31]. We also have studies that aim to improve the accuracy of models by reducing their mistakes on in-distribution testing samples, e.g., by model calibration [23], uncertainty quantification [26], misclassification detection [15]. However, we do not have a unified framework to connect all of these failure modes. Imagine we want to deploy a trained model in the real world while concerned about all the above sorts of failures. It seems very expensive and impractical to deploy a model while having a pipeline of supplementary models for weeding out adversarial and out-of-distribution inputs along with corner cases. Often, models offered for adversarial or out-of-distribution detection are more expensive than the main model at hand [27], e.g., the recent OOD detection methods require the images to be processed with a diffusion model, or many of the other OOD detection methods rely on ensembles of models as large as the original model. Hence, the pipeline of supplementary models is extremely expensive compared to the model itself. If we set aside the question of computational feasibility, another interesting question is whether these failure detection methods can work in harmony with each other to weed out the failure modes of a specific model at hand? The answer seems to be currently no, as [16] demonstrated that most of these failure detection methods do not generalize well, and moreover, for some of these failure detection methods, even the evaluation metrics used in the literature are not appropriate.

To address these issues, we propose an ambiguity measure that can relate these seemingly separate fields of study into a unified framework by leveraging the geometric information available in the feature space that models learn from their training set, specifically, in relation to the decision boundaries and convex hulls, the information that is freely available to any model designer, but it is often neglected. Our contributions can be summarized as the following:

1.

We first develop a theoretical framework to evaluate the unknowns of the trained models in relation to their confidence. With certain guarantees we quantify the portions of the domain which are unknown to the trained models, yet the models are guaranteed to process them with high confidence.
2.

We propose an ambiguity measure that is based on the geometric arrangements in the feature space of a trained model and the common failure modes of the models. We use image classification models as our case study and provide the necessary algorithms to compute the ambiguity measure fast, in a fraction of a second for models as large as Swin Transformer trained on Imagenet [9]. Through experiments, we also show that our proposed measure is able to detect a considerable portion of the mistakes made by the models, along with adversarial inputs, and out-of-distribution images.
3.

Our ambiguity measure provides an automatically generated text describing why an image is ambiguous, relating the ambiguity to samples in the training set and to the decision boundaries of the model.
4.

We show that there is valuable geometric information in the feature space of deep networks which has been often neglected, especially with regard to the convex hull of training sets.

2 Geometric information available in the last hidden layer of trained models

Let us consider a classification model $\mathcal{M}$ trained on a training set $\mathcal{D}^{tr}$ . This model may have $d$ dimensions for its input space and $n$ dimensions for its output corresponding to $n$ distinct classes

z=\mathcal{M}(x),

where $z$ is the output of the model for input $x$ , and the element of $z$ with largest value will indicate the classification for $x$

\mathcal{C}(x)=\{i:z_{i}=\max_{k}z_{k}\}.

We use $\Phi$ to denote the latent space in the last hidden layer of a given model. This feature space has $f$ dimensions. For example, a typical Swin Transformer trained on Imagenet has $f=1,536$ and $n=1,000$ in its last hidden layer. When $\mathcal{M}$ processes an input $x$ , it maps the $x$ to its latent space

x_{\phi}=\mathcal{M}_{\phi}(x),

(1)

and then $x_{\phi}$ will be processed via

z=W_{\phi}x_{\phi}+b_{\phi},

(2)

where $W_{\phi}$ and $b_{\phi}$ are the weight matrix and bias vector of the last hidden layer of the model.

2.1 Why study the learned feature space?

Our main motivation in this approach is to understand and verify the learning of a given trained model, i.e., what the model has learned from its training data and how it uses its learning to process the new inputs.

The success of deep networks is largely attributed to the features they extract from their inputs. For images, contents of interest usually cannot be explained in terms of individual pixels. Rather, for both humans and the models, the spatial relationship between the groups of pixels is the key to identifying what is depicted in an image. Similarly, for natural language processing, the sequence of words matter in the meaning created from individual words. Another way to describe this phenomenon is that inputs, such as image and text (and many other types of data), have a lower dimensional structure, and in order to learn from such data, one has to learn that underlying structure. This has been a subject of study from various perspectives in machine learning often under the term representation learning [3, 8]. Studying the underlying structure of the data also has a rich literature in various fields of mathematics [1, 12].

In pursuit of understanding the underlying structure, it is important to note that deep networks often make mistakes, and their learning from the data sometimes has certain flaws, i.e., they may fail to learn certain structures in the data. Moreover, training sets may have certain biases and flaws of their own which may affect the learning of the models trained on them. For example, in a facial recognition dataset, certain groups of people may not be well represented and that could affect the feature space learned by the models [17].

Here, we study the learned feature spaces not as flawless manifolds that represent the ideal way of learning. Rather, we study a given feature space to view what a model has learned from its data, and to verify the knowns and unknowns of the given model. We provide systematic methods that can interpret the learning of a trained model, and explain how it views the testing samples in relation to what it has learned.

2.2 Feature space: further compression via SVD

The feature space that we consider is based on the Singular Value Decomposition (SVD) of $\Phi$ . We use SVD to project the points in the latent space of the last hidden layer to a lower dimensional space denoted by $\Psi$ . SVD decomposes the matrix $W_{\phi}$ into three matrices:

W_{\phi}=U\Sigma V^{T},

where $U$ is a unitary $n\times n$ matrix, $\Sigma$ is a diagonal $n\times f$ matrix, and V is a unitary $f\times f$ matrix. We use $V^{T}$ to project the points in the latent space:

x_{\psi}=V^{T}x_{\phi}.

(3)

Given a point $x_{\psi}$ in feature space $\Psi$ , one can obtain the output of the model via

z=U\Sigma x_{\psi}+b_{\phi}.

(4)

Benefits of decomposing the last hidden layer: The results we present in this paper are all in the $\Psi$ space. We note that analyzing the original space of $\Phi$ yields to results that are slightly less accurate compared to the results obtained from $\Phi$ . The better accuracy is explainable via the rotation and scaling operations of SVD [12] which may pose the geometric arrangement of data in a way that is more suitable for our classification task. This is evident in Figure 2 where for the orange histogram ( $\Psi$ ), the separation between the closest class and the other classes is more pronounced. Indeed, if we were to use the distance to the convex hull of closest class as our classification criteria, the accuracy of our model would be 94.40% for $\Psi$ , 94.35% for $\Phi$ , and 94.33% for $\Phi@U$ while the accuracy obtained from the softmax score is 94.37%. This indicates that for accurate classification, one can rely merely on the convex hull of training set in the feature space without considering the decision boundaries of this model.

The other benefit obtained from the SVD is that $\Psi$ has a smaller number of dimensions compared to $\Phi$ . For example, a Swin transformer has 1,536 dimensions in $\Phi$ while its corresponding $\Psi$ has only 1,000 dimensions. This makes our optimization problems, regarding the convex hulls and decision boundaries, less expensive. We note that SVD has been used in the last hidden layer of language models before, not to change the geometric arrangements, but to make the computation of softmax scores faster [28, 7].

2.3 The intuition behind our geometric approach

Let us consider a deep network trained for classification of 3 classes. Figure 3 depicts the feature space in the $\Psi$ space of such model which we extracted from 3 output classes of a Swin Transformer trained on ImageNet. This figure, not only shows the decision boundaries of the model in this feature space, it also depicts the convex hull of training samples for each class. When classifying a testing sample $x$ , a typical model maps the sample to the $\Psi$ space, and then, determines which partition the $x_{\psi}$ belongs to. The partitioning step is performed via equation (4) where partitions are separated by a finite set of hyperplanes [33].

The linear operation performed via equation (4) partitions the feature space via a set of hyperplanes. Since $W_{\phi}$ and $b_{\phi}$ are fixed for a trained model, the partitioning of the feature space (i.e., the location of decision boundaries) is also fixed. It follows that once we compute the $x_{\psi}$ for a given $x$ , equation (4) merely determines which partition the $x_{\psi}$ has fallen within. This, however, neglects the rich geometric information available in the feature space, most importantly the relationship between the $x_{\psi}$ and the convex hull of training set for each class. The other valuable information in the feature space is the arrangement with regard to the decision boundaries.

To make our point more clear, consider the red and purple points in Figure 3, each of them being a testing sample. The purple point falls within the convex hull of class 1 and it is relatively far from the decision boundaries. Being inside the convex hull indicates that this sample falls within the range of training samples for class 1, i.e., the model has some frame of reference for classifying this sample as class 1. Being away from the decision boundaries with other classes signifies that there is little chance of confusion on which partition/class this sample may belong to.

Now, let us consider the red point in Figure 3 which falls in the partition for class 2. This sample is far from the convex hull of training set for class 2, and at the same time, it is very close to the decision boundaries with the other 2 classes. One can argue, quite reasonably, that the model should be less confident about the classification of the red point compared to the classification of the purple point. While the red sample has fallen in the partition for class 2, it does not seem to be closely similar to any of the training samples for class 2. Yet, it can be easily flipped to any of the other classes, if it were slightly perturbed or if the decision boundaries of the model were slightly different than their current configuration.

These two concepts, the relationship with the convex hull of training set and the relationship with the decision boundaries, are the basis for our ambiguity measure.

3 Computing the distances to the convex hulls and the decision boundaries

3.1 Convex hulls

Assuming that training set has at least one sample for each class, one would be able to compute the distance to the convex hull of each class.

x_{\psi}^{\mathcal{H},k}=\mathcal{P}^{\mathcal{H}}(x_{\psi},\mathcal{H}_{\psi}^{tr},k),

(5)

where $\mathcal{P}$ is a function that maps the $x_{\psi}$ to the convex hull of training set for class $k$ . Using this projection, we can compute a vector of distances where each of its elements corresponds to one of the classes in training set

d^{\mathcal{H}}_{\psi}(x):\forall k\in\{1:n\},\quad d^{\mathcal{H}}_{\psi}(x_{\psi})[k]=\|x_{\psi}-\mathcal{P}^{\mathcal{H}}(x_{\psi},\mathcal{H}_{\psi}^{tr},k)\|_{F},

(6)

We will be particularly interested in the first two smallest values of this vector.

To compute the projection of a sample to the convex hull of a set of points, we use the approximation algorithm by [13, 4] which has a guarantee for small error and a running time of $\mathcal{O}(|\mathcal{D}|\frac{n}{\bar{\epsilon}^{2}})$ where $|\mathcal{D}|$ is the number of points in the convex hull, $n$ is the number of dimensions, and $\bar{\epsilon}$ is a parameter to bound the error. We note that the problem of projecting to a convex hull is convex and there are exact algorithms that can solve it reasonably fast [24], but not as fast as the approximation algorithm.

In practice, solving this optimization problem in a 1,000 dimensional feature space of a Swin Transformer trained on Imagenet takes about 100 milliseconds on a GPU.

3.2 Decision boundaries

3.2.1 Existence, intersections, and properties

Here, we are concerned with the decision boundaries in the compressed feature space $\Psi$ . For simplicity of notations, we rewrite the equation (4) as

z=W_{\psi}x_{\psi}+b_{\phi},

where $W_{\psi}=U\Sigma$ .

The decision boundary between any two classes $i$ and $j$ in the compressed feature space, denoted by $x^{f(i,j)}_{\psi}$ can be defined as the set of points satisfying the following two conditions

W_{\psi}[i]x^{cf(i,j)}_{\psi}+b_{\phi}[i]=W_{\psi}[j]x^{f(i,j)}_{\psi}+b_{\phi}[j]

(7)

W_{\psi}[i]x^{cf(i,j)}_{\psi}+b_{\phi}[i]\geq W_{\psi}[k]x^{cf(i,j)}_{\psi}+b_{\phi}[k]\quad,\quad\forall k\notin\{i,j\}

(8)

These two equations define a subspace within the $\Psi$ , but it is important to realize that this space may be empty. If the subspace is empty for the decision boundary between two specific classes, it means that those classes do not have an interface.

Theoretically, it is possible for all class pairs to have an interface even when $n>>f$ .

The following is wrong. Talk about the dimensions of subspace. relate that to n and f.

Theoretically, as long as $n\leq f$ , it is possible for each pair of classes to have an interface, i.e., existence of all decision boundaries is possible, but not necessarily guaranteed. However, when we have $f<n$ , it may not be possible for some of the classes to have a direct interface with each other. Rather, the first class may be separated from the second classes via other intermediary classes. This is not necessarily undesirable as it would mean there is little chance of confusion between the two classes. For example, a model trained on Imagenet might have a decision boundary between two different types of fish, but perhaps, it may not have a decision boundary between the planes and alligators. Hence, it would be informative to understand and verify which classes do or do not have decision boundaries between them.

In an $f$ -dimensional ambient space, the decision boundary between two classes may be a hyperplane of $f-1$ dimensions. These decision boundaries eventually intersect with each other as well as with the boundaries of the domain. The intersection of two or more hyperplanes may be a non-empty subspace of lower dimensions defining the decision boundary between multiple classes.

In our compressed feature space, dimensionality of feature space is always equal to the number of classes, i.e., $f=n$ . We note that in practice almost all models have architectures with $f>n$ in their last hidden layer. There are some architectures that have $f<n$ , e.g., certain variations of Swin Transformers, however, the accuracy of those architecture have proved have proved to be lower compared to accuracy of equivalent architectures with $f>n$ .

A separate paper provides a theoretical analysis and discussion on the existence, intersections, and properties of decision boundaries in the feature space. Moreover, we provide a fast algorithm that can project the samples to the decision boundaries of trained models.

3.2.2 Projecting a point to the decision boundaries

Given a sample $x$ with classification $i=\mathcal{C}(x)$ , we would be interested to project the $x$ to the closest point on the decision boundaries with other classes. This is interesting because it would tell us how far a given sample is located from the decision boundaries of other classes, and it would also give us the direction the sample has to take to reach those decision boundaries. Perhaps the direction that a sample has to take to reach a decision boundary is very different than the direction it has to take to reach the convex hull of training set.

To project the point $x_{\psi}$ to the closest point on the decision boundary between classes $i$ and $j$ , we minimize the following objective

\min_{x^{cf(i,j)}_{\psi}}\|x^{cf(i,j)}_{\psi}-x_{\psi}\|_{2}

(9)

subject to the constraints in equations (7)-(8). In our notation, $x^{f}$ denotes flip points while $x^{cf}$ denotes closest flip points (closest to some reference $x$ ). In practice, solving this optimization problem in a 1,000 dimensional feature space of a Swin Transformer trained on Imagenet takes about 50 milliseconds on a GPU.

3.2.3 Special cases

As we noted earlier, a direct interface might not exist between certain classes in which case the optimization problem above will become infeasible. One easy way to verify the infeasibility of our optimization problem is to solve its dual form. When the dual form is unbounded, the primal problem is guaranteed to be infeasible.

When the problem is infeasible, we can relax the formulation aiming for a proxy point that would tell us how far $x_{\psi}$ has to move in order to flip to the other class $j$ . Since classes $i$ and $j$ do not have a direct interface, it means that $x_{\psi}$ has to flip from class $i$ to some other class(es) before eventually flipping to the class $j$ . This implies a farther distance, hence, we seek to find a point on the interface with class $j$ and not necessarily with class $i$ . For this, we rewrite the equations (7)-(8) as

W_{\psi}[j]x^{cf(i,j)}_{\psi}+b_{\phi}[j]\geq W_{\psi}[k]x^{cf(i,j)}_{\psi}+b_{\phi}[k]\quad,\quad\forall k\notin\{j\},

(10)

and subject the objective function (9) to this relaxed constraint.

It is possible to generalize this to decision boundaries between the class $i$ and multiple classes specified in $\gamma$ . In this case, we can minimize equation (9) subject to the following constraint

W_{\psi}[i]x^{cf(i,\gamma)}_{\psi}+b_{\phi}[i]=W_{\psi}[j]x^{f(i,\gamma)}_{\psi}+b_{\phi}[j]\quad,\quad\forall j\in\gamma

(11)

W_{\psi}[i]x^{cf(i,\gamma)}_{\psi}+b_{\phi}[i]\geq W_{\psi}[k]x^{cf(i,\gamma)}_{\psi}+b_{\phi}[k]\quad,\quad\forall k\notin\{i,\gamma\}

(12)

3.2.4 Calculating the vector of distances

To formalize the projection to the decision boundaries as a function, we use the following notation

x^{cf(i,\gamma)}_{\psi}=\mathcal{P}^{f}(x_{\psi},\gamma),

(13)

where $\gamma$ denotes a set of classes that we want to find their joint decision boundary with class $i$ .

Using the function in equation 13, we can find the distance between a point and the decision boundaries of all other $n-1$ classes. This ultimately gives us a vector of $n-1$ distances to each of the decision boundaries

d^{f}_{\psi}(x_{\psi}):\forall k\in\{1:n\backslash i\},\quad d^{f}_{\psi}(x_{\psi})[k]=\|x_{\psi}-\mathcal{P}^{f}(x_{\psi},k)\|_{F},

(14)

while $d^{f}_{\psi}(x_{\psi})[i]=0$ .

4 Characterising the unknowns of the models

Let us first characterize the notion of the unknowns of a trained model within its learned feature space.

4.1 Boundaries of the domain in feature space

In the pixel space, boundaries of the domain are well known. We can think of the pixel space as a hypercube of unit 1 dimensions as it is customary to normalize the pixel values to be between 0 and 1 or some other values.

Remark 4.1.

While we consider the pixel domain as a continuous hypercube, we note that pixel space is usually a discrete space as pixel values have representations such as UINT8. In any case, the assumption of continuous space does not affect our conclusions as the discrete space will be a subset of continuous space.

To realize the limits of the feature space $\Psi$ , we can derive the following based on the Hölder’s inequality

\begin{split}\|x_{\psi}\|_{\infty}&=\|V^{T}x_{\phi}\|_{\infty}\\ &\leq\|V^{T}\|_{2,\infty}\|x_{\phi}\|_{2}\\ &=\|x_{\phi}\|_{2},\end{split}

(15)

since $V^{T}$ (from the SVD) is orthonormal, and therefore, $\|V^{T}\|_{2,\infty}=1$ .

Now, we have to identify the limits of the $\|x_{\phi}\|_{2}$ as the output of the $\mathcal{M}_{\phi}(.)$ . For this, we can solve the following optimization problem

\max_{x}\|\mathcal{M}_{\phi}(x)\|_{2},

(16)

subject to $x$ being within the boundaries of the pixel space. The maximum value of this objective function will give us the upper bound on $\|x_{\phi}\|_{2}$ which can then be plugged back into equation (15) to find the limit of the hypercube that defines our feature space $\Psi$ . The hypercube is centered at the origin while each dimension of it is $2\|x_{\psi}\|_{\infty}$ .

For solving the optimization problem in equation (16), we note that $\mathcal{M}_{\phi}$ is a function of all the layers preceding the last layer. Depending on the architecture of the model, these layers could include ReLU layers, pooling layers, normalization layers, attention layers, etc. This composition of function as a whole is a non-concave function. Nevertheless, we can solve our maximization problem using standard optimization tools, perhaps the same algorithms that are used for training the models.

Remark 4.2.

To directly identify the limits of $\Phi$ (instead of $\Psi$ ), and avoid the compression performed via SVD, the norm of the objective function in equation (16) can be changed from the 2-norm to infinity norm.

Remark 4.3.

For some specific models, the feature space $\Phi$ is strictly non-negative, e.g., when a model has a ReLU layer at the very end. Most models do not have that property and their last hidden layer may have positive and negative values.

4.2 Unknowns may constitute a large portion of the domain of a trained model

The arguments regarding the unknowns of the models are generally applicable to the pixel space as much as the feature space. In both spaces, the convex hull of training set usually occupies a small fraction of the bounded domain. Testing samples are outside the $\mathcal{H}^{tr}$ , yet their distance from the $\mathcal{H}^{tr}$ usually does not exceed 30% of the diameter of the $\mathcal{H}^{tr}$ [32]. For some models, this percentage is less than 5% in the feature space.

At the same time, vast areas of the domain may be unrelated to the scope of a given model whether the domain is the pixel space or for other types of machine learning applications [6]. For example, if we consider the pixel space for a model trained on the CIFAR-10 dataset, the same pixel space contains all sorts of images unrelated to the model’s scope, e.g., radiology images, images of other object types, etc. All these irrelevant images exist in that same domain. What has become known as the adversarial inputs are also in that same domain.

To get a handle on how much of the domain is covered by the convex hull of training set, we estimate its volume using the approximation algorithm by [29]. This is one of the fastest approximation methods available [19] and it makes our computation significantly faster since we are dealing with high dimensions and high number of samples. The running time of this algorithm is $\mathcal{O}(\bar{n}^{4})$ where $\bar{n}$ is the number of dimensions.

4.3 Existence of cases of improper confidence

A simple example of improper over-confidence is the adversarial inputs which has been the subject of extensive, yet inconclusive, studies over the past few years. Another example is the case of out-of-distribution inputs where a model may confidently classify images that are unrelated to the scope of its training, e.g., an object detection model may classify a radiology image of liver as an aeroplane with 100% confidence. First, let us provide a formulation which can quickly give us egregious cases of over confidence for a model:

\max_{\hat{x}_{\psi}}\|x_{\psi}-\hat{x}_{\psi}\|_{2}

(17)

subject to:

\begin{gathered}\hat{x}_{\psi}\in\Psi,\\ \hat{x}_{\psi}\notin\mathcal{H}^{tr},\\ softmax(U\Sigma\hat{x}_{\psi}+b_{\phi})[i]>0.9\end{gathered}

(18)

Solving this formulation is not hard, especially if we use a good initial solution that is inside the partition $i$ yet far from $x_{\psi}$ . We leave the numerical examples for the future.

4.4 Establishing the closeness to decision boundaries as the indicator of model’s confidence

In this section, we prove that only in the vicinity of decision boundaries a model has low confidence, and in all other regions of the domain, a model is guaranteed to have high confidence.

Theorem 4.4.

Given an input $x$ for a trained model $\mathcal{M}(.)$ , if in the feature space of $\mathcal{M}$ , the distance of $x$ from the closest decision boundary is at least $\delta$ ,

\forall x\in\Phi:d^{f,min}_{\phi}(x)\geq\delta,

then, the confidence (top softmax score) of $M(.)$ in classifying $x$ will be at least

\max softmax(\mathcal{M}(x))\geq\frac{e^{\delta\|W[j]-W[i]\|_{2}}}{e^{\delta\|W[j]-W[i]\|_{2}}+(n-1)},

where $W$ is the weight matrix used for the classification of the feature space, $n$ is the number of classes, $i$ is the classification of $x$ , and $j$ is the class with closest decision boundary.

Proof.

We know $x$ is not on any decision boundaries, hence it will have a specific classification. Let us denote the classification of $x$ to be some class $i=\mathcal{C}(x)$ . Without any loss of generality, we consider the feature space to be $\Phi$ while the same proof will apply to $\Psi$ as well.

Let us denote the point on the closest decision boundary as $x_{\phi}^{f}$ . Such decision boundary will be a flip between class $i$ and at least one other class. We denote the other class with $j$ while noting that $j$ may not be unique. From the theorem statement, we have

\|v\|_{2}=\delta\quad,\quad v=x_{\phi}^{f}-x_{\phi}.

From equation (2), we can write $z=Wx_{\phi}+b$ and $z^{f}=Wx_{\phi}^{f}+b$ . Plugging the definition of $v$ will give us

z=W(x_{\phi}^{f}-v)+b=Wx_{\phi}^{f}-Wv+b=z^{f}-Wv.

We have $z^{f}[i]=z^{f}[j]$ since $x^{f}$ is a flip point between classes $i$ and $j$ . Based on this, we can write

\begin{split}z[i]-z[j]&=z^{f}[i]-z^{f}[j]-(W[i]v-W[j]v)\\ &=0-(W[i]v-W[j]v)\\ &=(W[j]-W[i])v\\ &=\|W[j]-W[i]\|_{2}\|v\|_{2}\cos{\theta}\\ &=\delta\|W[j]-W[i]\|_{2},\end{split}

(19)

where $W[i]$ denotes the $i^{th}$ row of $W$ , and $\theta$ is the angle between the vectors $W[j]-W[i]$ and $v$ . It is easy to show that these two vectors are always parallel leading to $\cos{\theta}=1$ . To realize this, note that the decision boundary between classes $i$ and $j$ is a hyperplane with coefficients $W[j]-W[i]$ . Since this hyperplane is the closest decision boundary to $x_{\phi}$ , no other decision boundary can block the access of $x_{\phi}$ to this hyperplane, hence, $v$ , the direction to the closest point on this hyperplane should be perpendicular to the hyperplane. Being perpendicular to a hyperplane means having the same direction as its vector of coefficients which makes $v$ parallel to $W[j]-W[i]$ .

Now, via equation (19), we have the difference between the elements $i$ and $j$ of the logit vector $z$ . Hence, we can derive a bound on the softmax score (confidence) of $\mathcal{M}(x)$ . The top softmax score for $x$ , corresponding to class $i$ , is

\begin{split}\max softmax(x)&=\frac{e^{z[i]}}{\sum\limits_{\forall k\in\{1:n\}}e^{z[k]}}\\ &\geq\frac{e^{z[i]}}{e^{z[i]}+(n-1)e^{z[j]}}\\ &=\frac{e^{z[j]}e^{\delta\|W[j]-W[i]\|_{2}}}{e^{z[j]}e^{\delta\|W[j]-W[i]\|_{2}}+(n-1)e^{z[j]}}\\ &=\frac{e^{\delta\|W[j]-W[i]\|_{2}}}{e^{\delta\|W[j]-W[i]\|_{2}}+(n-1)}\end{split}

(20)

∎

Corollary 4.4.1.

Given a specific model with known $W$ , the bound in equation (20) can be reduced to the following class agnostic bound

\max softmax(\mathcal{M}(x))\geq\frac{e^{\delta\rho(W)}}{e^{\delta\rho(W)}+(n-1)},

(21)

where

\rho(W)=\min_{i\neq j}\|W[j]-W[i]\|_{2},\forall i,j\in\{1:n\}.

(22)

Proof.

Computing the $\rho(W)$ is straightforward via equation (22). This equation provides the smallest possible value for $\|W[j]-W[i]\|_{2}$ for any choice of $i\neq j$ . We previously established that $i$ and $j$ cannot be identical. Furthermore, the function $\frac{e^{x}}{e^{x}+c}$ is monotonically increasing with respect to $x$ because its derivative w.r.t. $x$ is strictly positive. Therefore, the minimum value of $\|W[j]-W[i]\|_{2}$ will provide a lower bound for the right hand side of equation (20). ∎

We can extend the Theorem 4.4 to derive an upper bound on the confidence of the model based on the distance of inputs from the decision boundaries.

Theorem 4.5.

Given an input $x$ for a trained model $\mathcal{M}(.)$ , if in the feature space of $\mathcal{M}$ , the distance of $x$ from the closest decision boundary is at most $\delta$ ,

\forall x\in\Phi:d^{f,min}_{\phi}(x)\leq\delta,

then, the confidence (top softmax score) of $M(.)$ in classifying $x$ will be at most

\max softmax(\mathcal{M}(x))\leq\frac{e^{\delta\rho^{\prime}(W)}}{e^{\delta\rho^{\prime}(W)}+1},

(23)

where

\rho^{\prime}(W)=\max_{i\neq j}\|W[j]-W[i]\|_{2},\forall i,j\in\{1:n\}.

(24)

Proof.

Proof is similar to the previous proofs and is left out for brevity. ∎

We can use the above theorems in two ways. First, we can consider a specific lower bound for the confidence and determine what distance should the samples maintain from the decision boundaries for a given confidence lower bound. This can then be used to estimate for what fraction of the domain a model has high confidence. Second, if we know how far the samples are from the decision boundaries, we can compute the minimum confidence of the model for those samples.

To make this relationship more tangible, let us consider two examples.

Example 4.6.

Consider a ViT model trained on the CIFAR-10 dataset. We obtain the $\rho(W)$ for this model as $0.876$ . Since the model has 10 classes, we have $n=10$ . The relationship between the confidence of the model and the distance to the decision boundaries becomes

\max softmax(\mathcal{M}(x))\geq\frac{e^{0.876\delta}}{e^{0.876\delta}+9}.

Feature space of this model is a 768-dimensional hypercube. To give a perspective about distances in the feature space of this model, we note that its diameter has size 110. The diameter of $\mathcal{H}^{tr}_{\phi}$ is 10.40. The average diatance to the decision boundaries is $5$ . Given the bound above, choosing the distance threshold as $\delta=3$ yields

\max softmax(\mathcal{M}(x))\geq 60\%.

This means that any sample that with distance to decision boundaries $\geq 3$ will be classified by the model with softmax score of at least 60%. Alternatively, if we require the confidence to be at least 90%, the distance from the decision boundaries should be at least $5.07$ . Note that these are lower bounds, and there may exist points with high confidence that are closer to the decision boundaries. However, as long as the $5.07$ distance is maintained from the decision boundaries for any input, the confidence of the ViT model for the input is guaranteed to be at least 90%.

On the other hand, using Theorem 4.5, we obtain $\rho^{\prime}(W)=0.9692$ leading to

\max softmax(\mathcal{M}(x))\leq\frac{e^{0.9692\delta}}{e^{0.9692\delta}+1},

which implies that for any sample with $d^{f,min}_{\phi}\leq 0.42$ , the top softmax score of the model cannot be larger than 60%.

Remark 4.7.

The theorem and the corollary proved above hold all over the domain inside and outside the convex hull of training set. Therefore, it is only the closeness to decision boundaries that can explain the low confidence of a model when classifying an input.

Remark 4.8.

From equation (19), we can conclude that the closest class to a given input is not necessarily the class with the second largest softmax score.

4.5 Characterizing the decision boundaries and the fraction of the domain occupied by them

In previous section, we established that closeness to decision boundaries is the only source of low confidence for a model. We now aim to identify the decision boundaries and gauge the fraction of the domain occupied by them. A certain offset from the decision boundaries will indicate the fraction of the domain that a model would have low confidence.

Theorem 4.9.

Given a hypercube $\Phi=[0,1]^{n}$ with $n\geq 2$ as the feature space of a classification model where $W$ and $b$ define the model’s output via equation (2), the decision boundary between any two classes $i$ and $j$ , denoted by $\Delta^{i,j}_{\phi}$ , is a polytope of $\leq n-1$ dimensions. Volume of this polytope can be computed via Algorithm 1 and it is upper bounded by

\begin{split}&vol(\Delta^{i,j}_{\phi})\leq\\ &\frac{\|W[i]-W[j]\|_{2}}{(n-1)!\prod\limits_{k=1}^{n}(W[i,k]-W[j,k])}\sum_{K\subseteq\{1,\dots,n\}}(-1)^{|K|}\big{(}\max(0,-b[i]+b[j]-w.\mathbbm{1}_{K})\big{)}^{n-1}.\end{split}

(25)

Proof.

The decision boundary between any two arbitrary classes $i$ and $j$ , is a subset of the domain defined by

\begin{split}x&\in\Phi\\ (W[i]-W[j])x&=-b[i]+b[j]\\ W[i]x+b[i]&\geq W[k]x+b[k],\quad\forall k\notin\{i,j\}.\end{split}

(26)

It is possible for this subset to be empty as we noted before in Section 3.2.1 in which case $\Delta^{i,j}_{\phi}$ would not occupy any portion of the $\Phi$ . However, if the subset is non-empty, it will be a convex polytope of at most $n-1$ dimensions. Each vertex of this polytope will be an intersection of the $\Delta^{i,j}_{\phi}$ with either the boundaries of the $\Phi$ or with the decision boundaries of other classes. These intersections define the vertices of the polytope. To identify the vertices of the $\Delta^{i,j}_{\phi}$ , we can use the simplex method in Algorithm 1 inspired by the revised simplex algorithm in [24]. This algorithm initially identifies a vertex of the feasible domain, then finds a direction where one of the constraints is binding, and moves in that direction until it finds the next vertex. This will continue until all the vertices are obtained as we know the number of vertices of this polytope is finite and upper bounded by $(n-[\frac{n}{2}])\binom{n}{\frac{n}{2}}$ [25]. Having all the vertices of $\Delta^{i,j}_{\phi}$ , we can compute its volume analytically using formulas in [18, 5].¹¹1One way to perform this computation is to break the polytope into a set of simplexes, and then compute the volume of each simplex using the Gram determinant.
If $\Delta^{i,j}_{\phi}$ only intersects with the boundaries of the $\Phi$ and does not have any intersections with other decision boundaries, $\Delta^{i,j}_{\phi}$ would be the intersection of a hyperplane and a hypercube, and its volume can be computed analytically via the right hand side of equation (25) derived by [2, 20]. However, if $\Delta^{i,j}_{\phi}$ intersects with any other decision boundaries, i.e., the last line of equation (26) becomes binding for one or more instances of $k$ , then the volume of $\Delta^{i,j}_{\phi}$ will be strictly less than the right hand side of equation (25). ∎

Algorithm 1 Identifying the decision boundaries in the feature space

1:model

\mathcal{M}(.)

with

W

and

b

in its last hidden layer and

\Phi

as its feature space, classes

i

and

j

2:vertices of polytope

\Delta^{i,j}_{\phi}

defining the decision boundary between classes

i

and

j

in the feature space of

\mathcal{M}(.)

\Phi=[-a,a]^{n}\leftarrow

identify

a

as the length of

\Phi

by solving equation (16) with infinity norm

4:initialize

\mathcal{S}=\emptyset

\mathcal{S}\leftarrow

identify

s

as a basic feasible solution of equations (26)

d\leftarrow

identify a direction from

s

along which one constraint in equation (26) is binding

7:while

d\neq\emptyset

\mathcal{S}\leftarrow

move

s

along

d

as far as equations (26) are satisfied

d\leftarrow

identify a direction from

s

along which one new constraint in equation (26) is binding

10:end while

Remark 4.10.

If $\Delta^{i,j}_{\phi}$ does not have any intersections with other decision boundaries, e.g., the case of binary classification, then the equation (25) becomes an equality directly providing the volume of $\Delta^{i,j}_{\phi}$ with no need for Algorithm 1.

Now that we can identify the exact location of decision boundaries and their volume, we can proceed to identify the slices of the domain surrounding the decision boundaries which are guaranteed to have high or low confidence.

4.6 Regions of guaranteed high confidence in the feature space

We are interested to identify the regions of the domain where a model is guaranteed to have high confidence, i.e., softmax score. Let us formally define such regions as

\Phi(\geq\tau)\coloneqq\{x_{\phi}\>|\>x_{\phi}\in\Phi,\max softmax(\mathcal{M}(x_{\phi}))\geq\tau\}.

In Theorems 4.4-4.5, we established that maintaining a certain distance from the decision boundaries will lead to lower bounds on the softmax score of any given model. Later, in Theorem 4.9, we established the location of decision boundaries in the feature space and the corresponding volume that they occupy. It follows from these two sets of theorems that in the offsets of certain distance from the decision boundaries, a model is guaranteed to have low confidence, and in the regions away from those offsets, a model is guaranteed to have high confidence. We can formally identify the fraction of these regions using the following starting with the case of binary classification.

Theorem 4.11.

Given a model $\mathcal{M}(.)$ with feature space $\Phi=[-a,a]^{n}$ and two output classes, the fraction of feature space that is classified with softmax score of at least $\tau$ is lower bounded by

1-\frac{\sqrt{2}}{a}\delta\leq 1-\frac{2\delta}{(2a)^{n}}vol(\Delta_{\phi}^{i,j})\leq vol(\Phi(\geq\tau)),

(27)

where the lower bound corresponds to the volume of all the points which maintain a minimum distance of

\delta=\frac{1}{\rho(W)}\log\big{(}\frac{\tau(1-n)}{\tau-1}\big{)}

(28)

from the decision boundaries in $\Phi$ .

Proof.

The model has $2$ classes and one decision boundary, $\Delta_{\phi}^{i,j}$ , dividing the $\Phi$ into two sections. The vertices of the polytope defining $\Delta_{\phi}^{i,j}$ can be identified via Algorithm 1, and its volume can be computed precisely via the right hand side of equation (25). From Theorem 4.5, the offset of $\delta$ would guarantee classification with softwax score of at least $\tau$ for any point in the $\Phi$ . The volume of the regions that have a minimum distance of $\leq\delta$ from the decision boundaries is less than or equal to the volume of decision boundaries times $2\delta$ . Therefore, the remainder of the volume of the $\Phi$ is guaranteed to have softmax score $\geq\tau$ .

Moreover, $\Delta_{\phi}^{i,j}$ is the intersection of a hyperplane and a hypercube and its volume is upper bounded by $\sqrt{2}(2a)^{n-1}$ [2]. Replacing this for $vol(\Delta_{\phi}^{i,j})$ yields the leftmost side of the bound. ∎

Remark 4.12.

We note that the volume of the offset surrounding the $\Delta_{\phi}^{i,j}$ can be computed precisely by shifting the hyperplane between classes $i$ and $j$ by $\pm\delta$ , and computing the corresponding vertices with the $\Phi$ resulting in a hypersimplex. The volume of the hypersimplex will be the exact value for $vol(\Delta_{\phi}^{i,j})$ . Nevertheless, computing the volume of $\Delta_{\phi}^{i,j}$ and multiplying it with $2\delta$ may be a reasonably close approximation in the binary classification case.

We now extend this to the multi-classification case. First, let us define a notation for the area surrounding any given decision boundary

\Delta_{\phi}^{(i,j)\pm\delta}\coloneqq\{x_{\phi}\>|\>x_{\phi}\in\Phi,\frac{|(W[i]-W[j])x_{\phi}+b[i]-b[j]|}{\|W[i]-W[j]\|_{2}}\leq\delta\},

(29)

Theorem 4.13.

Given a trained model $\mathcal{M}(.)$ and its feature space $\Phi=[-a,a]^{n}$ , the fraction of feature space that is classified with softmax score of at least $\tau$ is lower bounded by

\mathcal{R}(\Phi(\geq\tau))\geq 1-\frac{1}{(2a)^{n}}vol(\Gamma\Delta),

(30)

where $\Gamma\Delta$ denotes the union of all the decision boundaries and their offsets

\Gamma\Delta=\bigcup_{i=1}^{n-1}\bigcup_{j=i+1}^{n}\Delta_{\phi}^{(i,j)\pm\delta},

(31)

and $\delta$ is the offset from the decision boundaries defined by equation (28).

Proof.

From Theorem 4.5, the offset of $\delta$ from the decision boundaries guarantees classification with softwax score of at least $\tau$ for any point in the $\Phi$ . A given model with $n$ output classes has $\binom{n}{2}$ distinct decision boundaries. For each decision boundary, the region that maintains a distance of $\leq\delta$ from it is defined by $\Delta_{\phi}^{(i,j)\pm\delta}$ and its computable via an extension of Algorithm 1. The union of these regions defines all the points in $\Phi$ that have a distance of $\leq\delta$ from at least one decision boundary. The complement of the volume of this union will be the lower bound on the desired fraction of feature space. ∎

4.7 Regions of guaranteed overconfidence: High confidence for the unknowns

In a separate study, we empirically establish that the scope of a model is tightly related to the convex hull of its training set in the feature space. For the purpose of the current study, we take it for granted that the scope of a trained model is tightly related to the convex hull of its training set

x\in\Phi:\|x-\mathcal{H}^{tr}\|_{2}\leq\delta,

(32)

for some $\delta$ that is relatively small compared to the dimensions of $\mathcal{H}^{tr}$ and $\Phi$ .

In section 4.2, we discussed, based on empirical evidence, that the convex hull of training set may occupy a small fraction of the feature space and vast areas in the feature space may be unrelated to the scope of a given model. Now, we integrate these notions with the confidence of the models to identify the regions in the feature space that are unrelated to the scope, yet, the model is guaranteed to have high confidence.

To identify these regions, we incorporate the convex hull of training set into our previous theorems. In Theorems 4.11-4.13, we devised a method to identify the regions of the feature space that are guaranteed to be classified with high confidence. Now, we aim to identify the high confidence regions that maintain a certain distance from the convex hull of training set. Such regions would be the improper confidence of the trained model: overconfidence for the inputs irrelevant to the scope of the model.

We first approximate the convex hull of training set with the smallest hyperrectangle that contains it.

Definition 4.14.

Given the feature space $\Phi=[-a,a]^{n}$ , and the convex hull $\mathcal{H}^{tr}_{\phi}\in\Phi$ : we define $\Phi^{\mathcal{H}}$ as the smallest hyperrectangle, with the same orientation as $\Phi$ , that contains the $\mathcal{H}^{tr}$ :

\Phi^{\mathcal{H}}\coloneqq[l_{i},u_{i}]_{i=1}^{f}\>|\>l_{i}=\min(x^{j}_{\phi}[i],\forall x_{\phi}^{j}\in\mathcal{D}^{tr}_{\phi}),u_{i}=\max_{j}(x^{j}_{\phi}[i],\forall x_{\phi}^{j}\in\mathcal{D}^{tr}_{\phi})

Moreover, $\Phi^{\mathcal{H}+\delta^{h}}$ denotes the hyperrectangle with an outer offset of $\delta^{h}$ from $\Phi^{\mathcal{H}}$ :

\Phi^{\mathcal{H}+\delta^{h}}\coloneqq[l_{i}^{\prime},u_{i}^{\prime}]_{i=1}^{f}\>|\>l_{i}^{\prime}=\max(l_{i}-\delta^{h},-a),u_{i}=\min(u_{i}+\delta^{h},a).

It follows that any point outside the $\Phi^{\mathcal{H}+\delta^{h}}$ would have a distance of at least $\delta^{h}$ from the $\mathcal{H}^{tr}_{\phi}$ . We consider the small offset of $\delta^{h}$ around the $\mathcal{H}^{tr}_{\phi}$ to still be relevant to the scope of the trained model. The value of $\delta^{h}$ shall be chosen empirically by verifying how far from the $\mathcal{H}^{tr}_{\phi}$ inputs can still be relevant to the scope of the model.

We are now set to formalize the regions of the domain that maintain a distance of $\delta^{h}$ from $\mathcal{H}^{tr}_{\phi}$ (being unknown to the model), and yet, the model is guaranteed to have high confidence about any inputs in those regions. In the following, $\mathcal{R}^{cu}$ denotes the ratio of the volume of the domain that has such characteristics.

Theorem 4.15.

Given a model $\mathcal{M}(.)$ with feature space $\Phi=[-a,a]^{n}$ and two output classes, the fraction of feature space that maintains a minimum distance of $\delta^{h}$ from the $\mathcal{H}^{tr}_{\phi}$ and is classified with softmax score of at least $\tau$ is lower bounded by

\mathcal{R}^{cu}\geq 1-\frac{1}{(2a)^{n}}\big{(}vol(\Phi^{\mathcal{H}})+vol(\Gamma\Delta)-vol(\Phi^{\mathcal{H}}\cap\Gamma\Delta)\big{)},

(33)

where $\delta$ is defined in equation (28) and $\delta^{h}$ is a small positive number defining the offset from the $\mathcal{H}^{tr}_{\phi}$ .

Proof.

We know from Theorem 4.4 that maintaining distance of $\delta$ from the decision boundaries guarantees classification with softmax score of at least $\tau$ anywhere in $\Phi$ . $\Gamma\Delta$ , calculated via equation (31), is the union of all regions that have a distance of $\leq\delta$ from the decision boundaries in $\Phi$ , i.e., regions that are classified with low confidence. All of these low confidence regions shall be excluded from the $\mathcal{R}^{cu}$ as they have softmax score $\leq\tau$ . The entire $\Phi^{\mathcal{H}}$ is also excluded from $\mathcal{R}^{cu}$ as they are close to the $\Phi^{\mathcal{H}}$ and considered known to the model. However, these two have an overlap which should not be deducted from the domain twice. $\Phi^{\mathcal{H}}\cap\Gamma\Delta$ is the portion of $\Gamma\Delta$ that intersects with $\Phi^{\mathcal{H}}$ which we add back to $\mathcal{R}^{cu}$ . The remainder of the $\Phi$ is unknown to the model, yet, the model is guaranteed to have high confidence. ∎

Previously, we showed how each of these components can be computed. Later, we will use these formulations to evaluate the percentage of domains that are unknown to the models yet the models, unjustifiably have high confidence about them. We see that these regions are considerably large.

5 Unknowns of the trained models in relation to common failure modes

Here, we consider four specific modes of failure, two of which fall under the umbrella of confusion.

5.1 Confusion between classes

By confusion, we refer to cases where a model may be undecided about which class applies to a given input. One such confusion would occur when a point is on or close to a decision boundary. Another, more complicated case will arise when we encounter overlapping classes. That is, when we have two or more classes where their training set overlap each other. The overlap region in particular would be a source of confusion. Such overlaps appear less often in computer vision tasks, but they are quite common in social applications of AI, e.g., the Adult Income dataset [10]. To quantify the confusion for overlapping classes, we consider the distance to the convex hull of classes.

5.1.1 Separable classes

The first type of confusion is when training samples of each class are separable from other classes in the feature space. In such cases, closeness to the decision boundary that has separated the classes would be an indication for a model’s confusion. For this, we measure the distance to the closest decision boundary

d^{f,min}_{\psi}(x_{\psi})=\min_{j\in\{1:n\backslash i\}}d^{f(i,j)}_{\psi}(x_{\psi})

(34)

This measure is inversely related to ambiguity of an input.

5.1.2 Overlapping classes

In some cases, we encounter datasets where classes have some overlap. Such overlap could be in the original domain and/or in the feature space. To reflect this in our ambiguity measure, we consider the difference between the distance to the two closest convex hulls. In other words, we first sort the vector $d^{\mathcal{H}}_{\psi}(x)$ , then subtract the first element of the sorted vector from its second element

d^{c}_{\psi}(x_{\psi})=d^{\mathcal{H},sorted}_{\psi}(x)[1]-d^{\mathcal{H},sorted}_{\psi}(x)[0]

(35)

This measure is inversely related to the ambiguity. Because the vector, $d^{\mathcal{H},sorted}_{\psi}(x)$ , is sorted, its first element is not larger than its second element, and hence, we have $d^{c}_{\psi}(x)\geq 0$ for any input.

When there is an overlap between two classes of training set, and a sample falls into that overlap, its distance from the convex hull of each class will be zero, and the resulting $d^{c}_{\psi}(x)$ will be zero as well, leading to $\zeta(x)\rightarrow\infty$ .

One could consider limiting this measure to the samples that are inside the overlapping regions, i.e., disregard it whenever a sample does not coincide with an overlapping region. However, we find this measure to be insightful even when a sample is outside the convex hull of classes. Outside the convex hull of classes, this measure will go to zero when a sample is equidistant from the two closest classes as shown in Figure 4. This, again, may imply confusion between the two classes. In our ablation studies, we will demonstrate how insightful this measure can be. Moreover, we show that instead of computing the difference between the two distances in equation (35), one can use a ratio of distances.

5.2 Excessive extrapolation

This case occurs when a model processes an input that excessively outside the convex hull of training set. We measure this via the minimum distance to the convex hull of classes

d^{\mathcal{H},min}_{\psi}(x_{\psi})=\min_{j\in\{1:n\}}d^{\mathcal{H},j}_{\psi}(x_{\psi}).

(36)

This measure is directly related to ambiguity.

5.3 Gaps in the model’s knowledge

Geometrically, this type of failure refers to the possible holes that may exist within the training samples. For example, consider a model that makes clinical decisions for patients. The training set of such model may only consist of patients ages 5-10 and patients aged 80-90 years old. When this model is deployed to make a decision for a patient that is 40 years old, it might be interpolating between its training samples, yet, in the dimension of age, the 40 years old testing sample may be too far from any of the training samples. We characterize this notion of knowledge gap by identifying the ball with the largest radius centered at the sample $x_{\psi}$ not containing any of training samples. The radius of such ball is our proxy for the knowledge gap:

d_{\psi}^{g}(x_{\psi})=\max_{\rho}\rho:\forall y_{\psi}\in\mathcal{D}^{tr}_{\psi}:\|x_{\psi}-y_{\psi}\|_{2}\geq\rho

(37)

This measure is directly related to ambiguity.

5.4 Our ambiguity measure

We are now ready to incorporate all of the above geometric information into a unified ambiguity measure.

\zeta(x)=\Big{(}\frac{(d^{\mathcal{H},min}_{\psi}(x)+\epsilon)(d_{\psi}^{g}(x)+\epsilon)}{d^{f,min}_{\psi}(x)d^{c}_{\psi}(x)}\Big{)}^{\alpha},

(38)

where $\epsilon$ and $\alpha$ are positive scalars to normalize the ambiguity measure. The purpose of $\epsilon$ is to extend the ambiguity measure inside the convex hull of training set. When we encounter a sample that falls inside the $\mathcal{H}^{tr}$ (while not coinciding with any of the training samples), its corresponding $d^{\mathcal{H},min}_{\psi}$ will be zero, yet the other three measures can reflect useful information in $\zeta$ . Our recommendation is to choose $\epsilon\ll 1$ . For the $\alpha$ , it can be chosen such that ambiguity is bounded between 0 and 1 for a set of samples.

Remark 5.1.

The order of $\zeta(.)$ for a set of distinct inputs is preserved for any choice of $\epsilon>0$ and $\alpha>0$ .

The measure provided by equation (38) is well defined even in its extremes. We know that all distances are lower bounded by zero, therefore, the value of $\zeta(.)$ for any input in the domain is non-negative. When $d^{g}_{\psi}\rightarrow 0$ , it follows that $d^{\mathcal{H},min}_{\psi}\rightarrow 0$ , and as a result, the ambiguity measure goes to $\epsilon^{2}$ indicating that the input is not ambiguous. As the distance to the convex hull increases, the ambiguity increases linearly. By contrast, when $d^{f,min}_{\psi}\rightarrow 0$ and/or $d^{c}_{\psi}\rightarrow 0$ , the ambiguity goes to infinity, i.e., the input is highly ambiguous. We almost never deal with these extreme cases, and almost always, these distances are positive values that are not too small or too large.

Models trained with special training methods: An underlying assumption here is that training set contains samples with hard labels. There are training methods, such as Mixup [34] that trains using soft labels. Such methods define the location of decision boundaries in between the samples. This does not contradict our approach because in such instances, we still have the original training samples with their hard labels, and moreover, the interpolated samples with soft labels are not visually meaningful, i.e., they only define the location of decision boundaries.

Models trained with unlabeled data: In self-supervised learning and in contrastive learning, it is possible to train a model on training samples without labels. Such methods are successful because the number of classes are large and the probability of encountering false positive samples is very small, i.e., any two random pair of samples that one picks from an unlabeled training set are unlikely to be from a same class. Such models, trained with contrastive learning, need to be fine-tuned eventually with labeled training samples in order to define the location of decision boundaries. This last stage will provide the frame of reference we need to compute our ambiguity measure. In other words, when a model is fine-tuned and the location of its decision boundaries are defined, we can go back to the unlabeled training set and label the samples using the fine-tuned model. Once we obtain the labeled training set, we can proceed with computing our ambiguity measure for any testing sample.

5.5 A simplified version of ambiguity measure: rule of thumb

As a rule of thumb alternative to the measure provided in equation (38), one can consider using the following simplified measure

\bar{\zeta}(x)=\Big{(}\frac{d^{\mathcal{H},min}_{\psi}(x)+\epsilon}{d^{f,min}_{\psi}(x)}\Big{)}^{\alpha}.

(39)

We show in our experiments that this rule of thumb works quite effectively in performing a wide range of tasks regarding the model failures albeit not as good as the equation 38.

We have considered other rules of thumb as well, e.g., subtracting the two distances of $d^{\mathcal{H},min}_{\psi}(x)$ and $d^{f,min}_{\psi}(x)$ instead of dividing them. Overall, we did not see a significant difference in predictive power of the measure in our empirical experiments. We chose the ratio instead of the difference, because it appeared to be more intuitive and slightly better in its predictive power.

5.6 Ambiguity explanation

We can generate an automatic text explaining why an input is ambiguous or not. Generally, this text will describe each component of the ambiguity measure in a percentile form in comparison to other samples.

The structure of the text is as following:

"Classification of this input is . This image is ambiguous/unambiguous because its ambiguity measure is higher/lower than % of all samples. The ambiguity of this input has four components:

•

Its distance to the convex hull of training set is > percentile
•

Its distance to closest decision boundary > percentile
•

It is close to both classes and
•

The radius of gap around this sample > percentile

5.7 Abstention model

At the deployment time, for any given input, the model first computes the ambiguity measure. If the ambiguity measure is larger than the chosen threshold, the model abstains from classifying. Otherwise, it will return the classification of input along with the ambiguity measure.

Algorithm 2 Unknown aware inference

1:model

\mathcal{M}(.)

, input

x

, ambiguity function

\zeta(.)

, ambiguity threshold

\tau

2:Classification of

x

3:Calculate

x_{\psi}

using equations (1) and (3)

4:Compute

\zeta(x)

using equation (38)

5:if

\zeta(x)>\tau

then

6: return unsure: abstaining from classification

7: return ambiguity explanation (Section 5.6)

8:else

9: return classification:

\mathcal{M}(x)

, ambiguity measure:

\zeta(x)

10:end if

The threshold $\tau$ can be chosen based on the statistics of ambiguity measure computed for a set of samples perhaps from a validation set. For example, one can compute the ambiguity of inputs on a validation set, and then set the $\tau$ that best separates the misclassifications of that validation set from its correct classifications. Alternatively, for any model that is already used in practice for a while, there will be some samples of its failure modes available at hand. One can compute the ambiguity of those failures and set the $\tau$ that best identifies those failures. In choosing the $\tau$ , limiting the rate of false positives may also be a consideration.

If we do not have access to a validation set or any samples of previous failures, we can compute the ambiguity measure for the training samples, and then choose some threshold based on the ambiguity distribution. For example, we may set the threshold as the 99th percentile of the ambiguity of training samples.

5.8 Ambiguity model

To build an ambiguity model, we may train a classifier on the geometric information of each point in the feature space. The training objective could be to detect undesirable inputs that the model may be exposed to, or the cases where the model is likely to make a mistake. In other words, such ambiguity model will aim to detect and weed out the inputs that the model may not be fit to process them.

Algorithm 3 presents a formal procedure to train such a model. This procedure relies on having access to a set of normal in-distribution samples $\mathcal{D}^{p}$ , and a set of undesirable samples that the model is likely to fail on them $\mathcal{D}^{n}$ . The set of undesirable samples in $\mathcal{D}^{n}$ could consist of any undesirable samples that we might have available. For example, if $\mathcal{M}$ has been deployed in practice, it might have made some mistakes already which we can include in $\mathcal{D}^{n}$ . Or if we have encountered some OOD or adversarial inputs, we can include them. If we are concerned about specific types of OOD inputs or certain types of adversarial attacks, such samples could be gathered/generated and then included in $\mathcal{D}^{n}$ as well.

As in the case of abstention models, we rely on the geometric information available in the feature space. For any given input, we can compute the geometric information using equations (34)-(37). Assembling these measurements together as a unified vector for each input in $\mathcal{D}^{p}$ and $\mathcal{D}^{n}$ leads to two new datasets: $\mathcal{G}^{p}$ and $\mathcal{G}^{n}$ which only reflect the geometric information for each of the samples.

About the $\mathcal{A}(.)$ , one can use any appropriate classification model. Our task, here, is binary classification and we do not expect $\mathcal{G}_{\psi}^{n}$ to have high dimensions. Clearly, $\mathcal{G}_{\psi}^{p}$ and $\mathcal{G}_{\psi}^{n}$ can be split into a training/validation/testing portions when we train the $\mathcal{A}(.)$ . We have experimented with models such as XGBoost, Random Forests, and SVMs, most of which perform reasonably well. We train ambiguity models to detect a variety of failure modes such as detecting corner cases, misclassifications, adversarial inputs, and OOD.

Algorithm 3 Creating an ambiguity model to detect undesirable (ambiguous/adversarial/OOD) inputs

1:model

\mathcal{M}

, set of normal samples

\mathcal{D}^{p}

, set of undesirable samples

\mathcal{D}^{n}

2:ambiguity detection model

\mathcal{A}

\mathcal{D}^{p}_{\psi},\mathcal{D}^{n}_{\psi}\leftarrow

map all samples of

\mathcal{D}^{p}

and

\mathcal{D}^{n}

to feature space

\Psi

\mathcal{G}_{\psi}^{p}\leftarrow

compute

d^{\mathcal{H},min}_{\psi}(.)

d_{\psi}^{g}(.)

d^{f,min}_{\psi}(.)

, and

d^{c}_{\psi}(.)

for

\mathcal{D}^{p}_{\psi}

\mathcal{G}_{\psi}^{n}\leftarrow

compute

d^{\mathcal{H},min}_{\psi}(.)

d_{\psi}^{g}(.)

d^{f,min}_{\psi}(.)

, and

d^{c}_{\psi}(.)

for

\mathcal{D}^{n}_{\psi}

6:train a model

\mathcal{A}(.)

to classify

\mathcal{G}_{\psi}^{p}

from

\mathcal{G}_{\psi}^{n}

7:return

\mathcal{A}(.)

We note that in the literature, there are models specifically designed for adversarial detection that are trained merely on the inputs in the feature space [21]. That would be equivalent to omitting lines 2-3 of the algorithm above, training the detection model not on $\mathcal{G}_{\psi}^{p}$ and $\mathcal{G}_{\psi}^{n}$ , rather training the model on $\mathcal{D}_{\psi}^{p}$ and $\mathcal{D}_{\psi}^{n}$ . We will see in our experimental results that computing the geometric arrangements enables the model to identify a variety of undesirable inputs (not just adversarial) better than merely from the projections to the feature space.

6 Results

In this section, we present our results on a ResNet model pre-trained on the CIFAR-10 dataset and a Swin Transformer pretrained on Imagenet. In the appendix, we provide results obtained from other pretrained models as well.

To be added. Stay tuned.

References

[1] Claire Fisher Adler. Modern Geometry. McGraw-Hill, 1967.
[2] Keith Ball. Cube slicing in ${R}^{n}$ . Proceedings of the American Mathematical Society, 97(3):465–473, 1986.
[3] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8), 2013.
[4] Avrim Blum, Sariel Har-Peled, and Benjamin Raichel. Sparse approximation via generating point sets. ACM Transactions on Algorithms, 15(3):1–16, 2019.
[5] Benno Büeler, Andreas Enge, and Komei Fukuda. Exact volume computation for polytopes: A practical study. In Polytopes—Combinatorics and Computation, pages 131–154. Springer, 2000.
[6] Xuenan Cao and Roozbeh Yousefzadeh. Extrapolation and AI transparency: Why machine learning models should reveal when they make decisions beyond their training. Big Data & Society, 10(1), 2023.
[7] Patrick Chen, Si Si, Sanjiv Kumar, Yang Li, and Cho-Jui Hsieh. Learning to screen for fast softmax inference on large vocabulary neural networks. In International Conference on Learning Representations, 2019.
[8] Uri Cohen, SueYeon Chung, Daniel D Lee, and Haim Sompolinsky. Separability and geometry of object manifolds in deep neural networks. Nature Communications, 11(1):1–13, 2020.
[9] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255, 2009.
[10] Dua Dheeru and Efi Karra Taniskidou. UCI machine learning repository, 2017.
[11] Micah Goldblum, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Mądry, Bo Li, and Tom Goldstein. Dataset security for machine learning: Data poisoning, backdoor attacks, and defenses. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2), 2023.
[12] Gene H Golub and Charles F Van Loan. Matrix Computations. JHU Press, Baltimore, 4th edition, 2012.
[13] Sariel Har-Peled, Nirman Kumar, David M Mount, and Benjamin Raichel. Space exploration via proximity search. Discrete & Computational Geometry, 56:357–376, 2016.
[14] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. In International Conference on Learning Representations, 2017.
[15] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. In International Conference on Learning Representations, 2017.
[16] Paul F Jaeger, Carsten Tim Lüth, Lukas Klein, and Till J. Bungert. A call to reflect on evaluation practices for failure detection in image classification. In International Conference on Learning Representations, 2023.
[17] Saachi Jain, Hannah Lawrence, Ankur Moitra, and Aleksander Madry. Distilling model failures as directions in latent space. In International Conference on Learning Representations, 2023.
[18] Jim Lawrence. Polytope volume computation. Mathematics of Computation, 57(195):259–271, 1991.
[19] László Lovász and Santosh Vempala. Simulated annealing in convex bodies and an ${O}^{*}(n^{4})$ volume algorithm. Journal of Computer and System Sciences, 72(2):392–417, 2006.
[20] Jean-Luc Marichal and Michael J Mossinghoff. Slices, slabs, and sections of the unit hypercube. Online Journal of Analytic Combinatorics, 3:1–11, 2008.
[21] Mazda Moayeri and Soheil Feizi. Sample efficient detection and classification of adversarial attacks via self-supervised embeddings. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7677–7686, 2021.
[22] Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Gorur, and Balaji Lakshminarayanan. Do deep generative models know what they don’t know? In International Conference on Learning Representations, 2019.
[23] Jeremy Nixon, Michael W. Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Measuring calibration in deep learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, 2019.
[24] Jorge Nocedal and Stephen Wright. Numerical Optimization. Springer, New York, 2nd edition, 2006.
[25] Patrick E O’Neil. Hyperplane cuts of an n-cube. Discrete Mathematics, 1(2):193–195, 1971.
[26] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D. Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model’s uncertainty? Evaluating predictive uncertainty under dataset shift. In Advances in Neural Information Processing Systems, 2019.
[27] Jie Ren, Peter J Liu, Emily Fertig, Jasper Snoek, Ryan Poplin, Mark Depristo, Joshua Dillon, and Balaji Lakshminarayanan. Likelihood ratios for out-of-distribution detection. In Advances in Neural Information Processing Systems, pages 14680–14691, 2019.
[28] Kyuhong Shim, Minjae Lee, Iksoo Choi, Yoonho Boo, and Wonyong Sung. SVD-softmax: Fast softmax approximation on large vocabulary neural networks. Advances in Neural Information Processing Systems, 2017.
[29] Miklós Simonovits. How to compute the volume in high dimension? Mathematical Programming, 97:337–374, 2003.
[30] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
[31] Nanyang Ye, Kaican Li, Haoyue Bai, Runpeng Yu, Lanqing Hong, Fengwei Zhou, Zhenguo Li, and Jun Zhu. OoD-Bench: Quantifying and understanding two dimensions of out-of-distribution generalization. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022.
[32] Roozbeh Yousefzadeh. Deep learning generalization and the convex hull of training sets. arXiv preprint arXiv:2101.09849, 2020.
[33] Roozbeh Yousefzadeh. Decision boundaries and convex hulls in the feature space that deep learning functions learn from images. arXiv preprint arXiv:2202.04052, 2022.
[34] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018.