# Efficient Failure Pattern Identification of Predictive Algorithms

Bao Nguyen  School of Information and Communication Technology
Hanoi University of Science and Technology
Vietnam  College of Engineering & Computer Science
VinUni-Illinois Smart Health Center
VinUniversity
Vietnam  Viet Anh Nguyen  The Chinese University of Hong Kong

###### Abstract

Given a (machine learning) classifier and a collection of unlabeled data, how
can we efficiently identify misclassification patterns presented in this
dataset? To address this problem, we propose a human-machine collaborative
framework that consists of a team of human annotators and a sequential
recommendation algorithm. The recommendation algorithm is conceptualized as a
stochastic sampler that, in each round, queries the annotators a subset of
samples for their true labels and obtains the feedback information on whether
the samples are misclassified. The sampling mechanism needs to balance between
discovering new patterns of misclassification (exploration) and confirming the
potential patterns of classification (exploitation). We construct a
determinantal point process, whose intensity balances the exploration-
exploitation trade-off through the weighted update of the posterior at each
round to form the generator of the stochastic sampler. The numerical results
empirically demonstrate the competitive performance of our framework on
multiple datasets at various signal-to-noise ratios.

##  1 Introduction

Over the past few years, algorithmic predictive models have claimed many
successful stories in real-world applications, ranging from healthcare and
finance to jurisdiction and autonomous driving. These successes often take
place in an invariant environment where the training data and the test data
come from sufficiently similar distributions. If this similarity condition
does not hold, then it is well-known that the performance of the algorithmic
prediction can deteriorate significantly in the deployment phase. This
performance deterioration may trigger subsequent concerns, especially in
consequential domains such as self-driving cars and healthcare, where the
algorithmic predictions may affect system reliability and human safety. When a
predictive model performs unsatisfactorily in a systematic manner, then it is
called a failure pattern. For example, if an object detection system fails to
capture the object systematically under low-light conditions, then it is a
failure pattern. Detecting and correcting the failure patterns is arguably one
of the most daunting challenges in developing the future analytics systems.

Detecting failure patterns is also beneficial for many steps in the life-cycle
of an analytics product. For example, it is very common to develop analytics
systems using data collected from one country, say the United States, but the
systems can be deployed in another country, say Canada. Before field
deployment, the systems need to undergo intensive fine-tuning and
recalibration, and information regarding the failures can significantly reduce
the time and efforts spent on this step. Further, as foundation models are
increasingly used as a building block of future analytics systems, assessing
the blindspots of these pre-trained models is of crucial importance for
product development, deployment and continuous performance evaluation.

Detecting failure patterns, unfortunately, requires the true outcome or label
of the data samples. If the dataset is cleanly labeled, then the problem of
failure pattern detection can be simplified to a search problem. The situation
becomes more cumbersome if we have access to only an unlabeled dataset. It is
thus natural herein to incorporate the role of a human annotator into the
detection procedure. However, in many applications that require high-skilled
annotators, such as healthcare, it is time-consuming and cost-intensive to
query the annotator. Given a dataset containing unlabeled samples, we are
interested in designing an efficient routine to query these samples for their
true outcome or label, so that we can identify as many failure patterns as
possible with minimal annotation queries.

Contributions. We propose in this paper a directed sampling mechanism with the
goal of detecting failure patterns from an unlabeled dataset. This mechanism
has two main components:

  * •

a Gaussian process to model the predictive belief about the misclassification
probability for each unlabeled sample,

  * •

a determinantal point process sampling that balances the trade-off between
exploration and exploitation by taking a mixture between a similarity matrix
(reflecting exploration) and a posterior probability of misclassification
matrix (reflection exploitation).

Ultimately, we propose a human-machine collaborative framework that relies on
the machine’s proposed queries and the corresponding annotator’s feedback to
detect failure patterns, and consequently improve the reliability of the
predictive algorithm in variant environments.

This paper unfolds as follows: In Section 2, we survey existing efforts to
identify failure patterns in a given dataset. Section 3 formalizes our problem
and introduces the necessary notations. Section 4 depicts our approach using
Gaussian processes to build the surrogate for the Value-of-Interest, which
represents the belief about the misclassification probability for the
unlabeled samples. Section 5 focuses on the determinantal point process
sampler, which blends the Value-of-Interest (highlighting exploitation) with a
diversity term (highlighting exploration). Section 6 discusses how we can
choose the bandwidth, which is critical given the unsupervised nature of the
failure identification problem. Finally, Section 7 provides extensive
numerical results to demonstrate the superior performance of our directed
sampling mechanism in detecting failure patterns for various datasets.

In almost all related work about failure identification, a failure mode
(termed as “slice” in Eyuboglu et al. [2022]) of a pre-trained classifier on a
dataset is a subset of the dataset that meets two conditions: (i) the
classifier performs poorly when predicting samples in that subset, and (ii)
the subset captures a distinct concept or attribute that would be recognizable
to domain experts. If the true labels of all samples in that subset are
available, criterion (i) can be easily confirmed using popular performance
metrics for classification tasks. However, condition (ii) is subjective and
implicit. For instance, two medical experts may interpret a group of
misclassified brain scan images in two different ways, and both
interpretations may be reasonable and acceptable. For unlabeled data, it is
difficult to employ the existing definitions of the failure patterns.

Arguably, a failure mode is a subjective term that depends on the machine
learning task, on the users, and on the datasets. We do not aim to provide a
normative answer to the definition of a failure mode in this paper. Our paper
takes a pragmatic approach: given a choice of failure pattern definition of
users, we develop a reasonable method that can efficiently find the failure
patterns from the unlabeled data.

Notations.  We use $\mathbb{R}^{d}$ to denote the space of $d$-dimensional
vectors, and $\mathbb{S}_{+}^{d}$ to denote the set of $d$-by-$d$ symmetric,
positive semidefinite matrices. The transposition of a matrix $A$ is denoted
by $A^{\top}$, and the Frobenius norm of a matrix $A$ is denoted by
$\|A\|_{F}$.

##  2 Related work

Detecting failure patterns of a machine learning algorithm on a given dataset
is an emergent problem in the literature. d’Eon et al. [2022b] formulates a
single-stage optimization problem to identify the systematic error. Sohoni et
al. [2020] mitigates hidden stratification by detecting sub-class labels
before solving a group distributionally robust optimization problem(GDRO).
Eyuboglu et al. [2022] provides an evaluation method for slice discovery
methods (SDMs): given a trained classifier and a labeled dataset of the form
$(x_{i},y_{i})_{i=1}^{N}$, it outputs a set of slicing functions that
partitions the dataset into overlapping subgroups on which the model
underperforms. Nushi et al. [2018] proposes a hybrid approach to analyze the
failures of AI systems in a more accountable and transparent way. The hybrid
approach involves two main phases: (1) machine analysis to identify potential
failure modes, and (2) human analysis to validate and explain the identified
failure modes. Singla et al. [2021] concentrates on understanding the failures
of deep neural networks. The paper proposes a method for robust feature
extraction, which aims to identify the most important features that contribute
to the output of a deep neural network. Polyzotis et al. [2019] proposed
SliceFinder that automatically identifies subsets of the data that cause the
model to fail or perform poorly. It repeatedly draws random subsets of the
data and re-trains the model on each subset, then measures the model’s
performance. Finally, it employs a statistical test to identify data slices
that are significantly different from the overall distribution. Sagadeeva and
Boehm [2021] build a method using linear algebra techniques to speed up the
slice-finding process for identifying problematic subsets of data that cause a
model to fail.

Our paper is also closely related to the field of active learning. Active
learning examines how to obtain the largest amount of performance gains by
labeling as few samples as possible. Comprehensive surveys on active learning
can be found in Ren et al. [2021] and Budd et al. [2021]. There is, however, a
critical difference between the settings of our paper and those of active
learning: in our paper, we focus on identifying the failure pattern for a
fixed (invariant) classifier, whereas active learning focuses on improving the
model performance with model retraining after each batch of recommendations.
The numerical experiments in Section 7 demonstrate empirically that active
learning algorithms do not perform competitively at the failure identification
task.

Figure 1: Schematic view of our solution: We build a sampling mechanism to
recommend the next $s$ unlabeled samples to be labeled by the annotators. The
misclassification information is fed back to update the sampling density.
Throughout this sequential recommendation process, the predictive model does
not change.

##  3 Problem Statement

We suppose that a user is given a classification algorithm and a set of
unlabeled dataset. The classifier is denoted by
$\mathcal{C}:\mathcal{X}\to\mathcal{Y}$, which admits a feature space
$\mathcal{X}=\mathbb{R}^{d}$ as input, and outputs labels in the set
$\mathcal{Y}=\\{1,\ldots,C\\}$. The unlabeled dataset consists of $N$ samples,
which can be represented by $N$ vectors $x_{i}\in\mathbb{R}^{d}$ for
$i=1,\ldots,N$. For each sample $x_{i}$, the predicted label (termed the
pseudolabel) that is recommended by the algorithm is denoted by
$\widehat{y}_{i}=\mathcal{C}(x_{i})$; while its true label is denoted by
$y_{i}^{\mathrm{true}}$. The $i$-th sample in the dataset is accurately
classified if $\widehat{y}_{i}=y_{i}^{\mathrm{true}}$, and it is misclassified
if $\widehat{y}_{i}\neq y_{i}^{\mathrm{true}}$.

The main object of this paper is not the individual misclassified samples. Our
goal in this paper is to study the group effect of misclassified samples: when
they are sufficiently close to each other, they form a failure pattern or a
failure cluster, and together, they signal a systematic error of the
predictive algorithm on the given dataset. To give a formal definition of a
failure pattern, we need to construct a graph representation of the data. To
do this, we suppose the available data can form an abstract undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of
nodes whereas each node represents one sample from the dataset, and
$\mathcal{E}$ is the set of edges. Let
$\mathcal{G}^{\mathrm{mis}}=(\mathcal{V}^{\mathrm{mis}},\mathcal{E}^{\mathrm{mis}})$
be the pruned graph of $\mathcal{G}$ after removing the nodes representing
samples that are classified accurately. We can now rigorously define a general
failure pattern.

######  Definition 3.1 ($M$-C failure pattern).

Given a graph $\mathcal{G}^{\mathrm{mis}}$, an integer size threshold $M$, and
a connectivity criterion C, a failure pattern is a subgraph
$\mathcal{G}^{\mathrm{fail}}=(\mathcal{V}^{\mathrm{fail}},\mathcal{E}^{\mathrm{fail}})$
of $\mathcal{G}^{\mathrm{mis}}$ that satisfies the connectivity criterion C
and the cardinality of the set $\mathcal{V}^{\mathrm{fail}}$ is at least $M$.

Our framework gives the user tremendous flexibility in specifying the problem
and leveraging our tool to identify the related failure patterns:

  * •

First, the user can specify the semantic similarity between two nodes
represented by an edge connecting them. Moreover, this user-based graph
construction can capture the inherently subjective characteristics of the
definition of failure, which depends on the user’s perspective and the domain
of data. For a concrete example, if the user is confident that the embedding
space is rich enough to capture the similarity between samples, then one
possible approach is to construct $\mathcal{G}$ by the mutually nearest
neighbor graph under the Euclidean distance between embedding representations.

  * •

Secondly, users can specify preferred connectivity criteria among samples in a
failure pattern. For instance, the criterion of “completeness” can be employed
as a candidate for C. This criterion is one of the most stringent: it mandates
that each misclassified node must exhibit an edge (indicating semantic
similarity) with every other misclassified node in the pattern. However, users
can adjust the stringency by employing looser criteria, such as
“Super-$\kappa$ connectivity” or “connected connectivity”.

  * •

Third, the users can specify $M$ which depicts the amount of evidence required
in order to confirm a failure pattern. A large value of $M$ means a high level
of evidence required (represented by a high number of clustered misclassified
samples) to pinpoint a pattern. Moreover, one can also see that given a fixed
graph of misclassified samples $\mathcal{G}^{\mathrm{mis}}$, the number of
failure patterns in $\mathcal{G}^{\mathrm{mis}}$ is non-increasing in $M$.
Taking this perspective, one can also view $M$ as a parameter that is inverse-
proportional to the user’s degree of risk aversion: a low value of $M$
indicates that the user believes there are many misclassified patterns in the
dataset.

While identifying the failure patterns from an unlabeled dataset is becoming
increasingly pertinent in the current practice of machine learning deployment,
this problem is inherently challenging due to two main factors:

  1. 1.

Annotation cost: to determine if a data point is misclassified, we need to
have complete information about its true label, which is often obtained by
querying a team of human annotators. Unfortunately, in many consequential
domains such as healthcare and law enforcement, the cost of annotation can be
enormous for a large dataset.

  2. 2.

Signal-to-noise ratio: suppose that there are $F$ failure patterns represented
in the data graph $\mathcal{G}^{\mathrm{mis}}$ and they are denoted by
subgraphs
$\mathcal{G}^{\mathrm{fail}}_{f}=(\mathcal{V}^{\mathrm{fail}}_{f},\mathcal{E}^{\mathrm{fail}}_{f})$
for $f=1,\ldots,F$. The union $\cup_{f}\mathcal{V}^{\mathrm{fail}}_{f}$ gives
a collection of all misclassifed samples that belong to the failure patterns,
and the remainder set
$\mathcal{V}^{\mathrm{mis}}\backslash\cup_{f}\mathcal{V}^{\mathrm{fail}}_{f}$
contains all samples that are misclassified but do not belong to any failure
pattern. Because the goal of the user is to identify failure patterns, the
user can view the cardinality of the union set
$\cup_{f}\mathcal{V}^{\mathrm{fail}}_{f}$ as a measure of the amount of signal
in the dataset, and the cardinality of the remainder set
$\mathcal{V}^{\mathrm{mis}}\backslash\cup_{f}\mathcal{V}^{\mathrm{fail}}_{f}$
as a measure of the amount of noise therein. As such, we observe a typical
signal-to-noise ratio (SNR) indication: if the SNR is high, then the problem
tends to be easy; on the contrary, if the SNR is low then the problem tends to
be hard.

Unfortunately, crucial information to identify the failure patterns is not
known to the user ex-ante: for example, the user does not know how many
patterns there are in the dataset, nor does the user know the number of
misclassified samples and the SNR. To proceed, we make the assumptions:

######  Assumption 3.2.

We assume the followings:

  * •

the number of unlabeled samples $N$ in the given dataset is large and the cost
of using an annotator is expensive, thus it may be prohibitive to annotate the
whole dataset,

  * •

the inference cost of the predictive algorithm is negligible for any feature
$x\in\mathcal{X}$, which means we can obtain the pseudolabels
$\widehat{y}_{i}=\mathcal{C}(x_{i})$ for all data points,

  * •

the predictive algorithm $\mathcal{C}$ remains invariant throughout the
failure identification process, and thus the failure patterns do not change
over time.

The first assumption is critical because if the cost of annotating the whole
dataset is small, then the user does not need to use our proposed sampling
mechanism because the benefit of annotating the whole dataset outweighs the
resulting cost. The second assumption is reasonable in most practical settings
as it requires feed-forwarding the entire given dataset through the predictive
algorithm once. The last assumption ensures that our targets, the failure
patterns, do not alter over time and that the collected information and the
updated belief remain relevant for recommending the next batch of samples for
annotation.

We are interested in a dynamic (sequential) recommendation setting that
consists of $T$ rounds. In each round $t=1,\ldots,T$, the system recommends to
the user a set of $s$ unlabeled samples to query the annotator for the true
label. After the true labels are obtained, the user can recognize which newly-
annotated samples are misclassified, and the user, based on this arrival of
information, can (i) identify if a new failure pattern can be identified by
verifying the conditions in Definition 3.1, and then (ii) update the user’s
own belief about where the remaining failure pattern may locate. The posterior
belief is internalized to the recommendation mechanism to suggest another set
of $s$ unlabeled samples from the remaining pool to the next round.

We note that task (i) described above is purely algorithmic: after the arrival
of the misclassification information, the user can run an algorithm to search
for the newly-formed maximally connected subgraphs of misclassified samples
with size at least $M$. Task (ii), on the contrary, is more intricate because
it requires a dynamic update of belief. To achieve task (ii), we will employ a
Bayesian approach with Gaussian processes to form a belief about the locations
of the failure patterns, and this belief will also be used for the sampling
mechanism.

######  Remark 3.3 (Semantics of the failure pattern).

Herein, the failure patterns are defined using the closeness in the feature of
the samples. This is a convenient abstraction to alleviate the dependence of
the definition on specific tasks (such as image, text, or speech
classification). Defining patterns based on the feature space is also a common
practice in failure identification, see Eyuboglu et al. [2022] and d’Eon et
al. [2022b].

##  4 Gaussian Process for the Value-of-Interest

In this section, we describe our construction of a surrogate function called
the Value-of-Interest (VoI). Mathematically, we define
$\mathrm{VoI}:\mathcal{X}\times\mathcal{Y}\to[0,1]$ to quantify the degree of
interest assigned to each pair of feature-pseudolabel
$(x_{i},\widehat{y}_{i})$ data point. The notion of $\mathrm{VoI}$ aims to
capture the exploitation procedure: it emphasizes recommending samples with a
high tendency (or intensity) to confirm a misclassification pattern. Thinking
in this way, we aim to predict the probability that the feature-pseudolabel
pair will be part of a yet-to-confirmed failure pattern. For any generic
sample $(x,\hat{y})$, we model $\mathrm{VoI}$ using a sigmoid function of the
form

$\mathrm{VoI}(x,\hat{y})=\frac{1}{1+\exp(-g(x,\hat{y}))},$

for some function $g:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$. While
$\mathrm{VoI}$ is bounded between 0 and 1, the function $g$ can be unbounded,
and it is more suitable to model our belief about $g$ using a Gaussian process
(GP). In particular, we let $g\sim\mathrm{GP}(m,\leavevmode\nobreak\
\mathcal{K})$, where $m$ is the mean function and $\mathcal{K}$ is the kernel
or covariance function, both are defined on $\mathcal{X}\times\mathcal{Y}$. A
GP enables us to model the neighborhood influence among different samples
through the covariance function $\mathcal{K}$.

###  4.1 Posterior Update of the Predictive Probability

Using the Gaussian process model, we have

$\tilde{g}=\begin{bmatrix}g(x_{1},\hat{y}_{1})\\\ \vdots\\\
g(x_{N},\hat{y}_{N})\end{bmatrix}\sim\mathcal{N}(0,K),$

where for a slight abuse of notation, $m$ is a vector of mean values and the
covariance matrix $K\in\mathbb{S}_{+}^{N}$ is the Gram matrix with the
components

$K_{ij}=\mathcal{K}((x_{i},\hat{y}_{i}),(x_{j},\hat{y}_{j}))\quad\forall(i,j).$
(1)

We can re-arrange $g$ into another vector
$(\tilde{g}_{[t]},\tilde{g}_{[t]}^{*})$ where the subvector
$\tilde{g}_{[t]}=(g(x_{i},\hat{y}_{i}))_{i\in\mathcal{I}_{[t]}}$ represents
the value of $\tilde{g}$ at all samples that are queried by time $t$, while
$\tilde{g}_{[t]}^{*}=(g(x_{i},\hat{y}_{i}))_{i\in\mathcal{I}_{[t]}^{*}}$
represents the value of $\tilde{g}$ at all samples that are not queried yet by
time $t$. By a similar decomposition of the matrix $K$, we can rewrite

$\begin{bmatrix}\tilde{g}_{[t]}\\\
\tilde{g}_{[t]}^{*}\end{bmatrix}\sim\mathcal{N}\left(\begin{pmatrix}m_{[t]}\\\
m_{[t]}^{*}\end{pmatrix},\begin{bmatrix}K_{[t]}&K_{[t]}^{*}\\\
(K_{[t]}^{*})^{\top}&K_{[t]}^{**}\end{bmatrix}\right).$

By the law of conditional distribution for joint Gaussian distributions
[Murphy, 2012, §15.2.1], we have the distribution of $\tilde{g}_{[t]}^{*}$
conditional on $\tilde{g}_{[t]}=g_{[t]}^{\text{observe}}$ is also a Gaussian
distribution:

$\tilde{g}_{[t]}^{*}|g_{[t]}^{\text{observe}}\sim\mathcal{N}(m_{t}^{*},\Sigma_{t}^{*}),$

where the conditional mean is determined by

$\displaystyle m_{t}^{*}$
$\displaystyle=m_{[t]}^{*}+(K_{[t]}^{*})^{\top}K_{[t]}^{-1}(g_{[t]}^{\text{observe}}-m_{[t]})$
(2a) and the conditional variance is computed as $\displaystyle\Sigma_{t}^{*}$
$\displaystyle=K_{[t]}^{**}-(K_{[t]}^{*})^{\top}K_{[t]}^{-1}K_{[t]}^{*}.$ (2b)

The vector $m_{t}^{*}$ captures the posterior mean of the misclassification
probability of samples that are not yet queried by time $t$.

We now discuss how to estimate the expected value of
$\mathrm{VoI}(x_{i},\hat{y}_{i})$ for the unqueried sample $i$. Note that
$\mathrm{VoI}(x_{i},\hat{y}_{i})$ is a nonlinear function of
$g(x_{i},\hat{y}_{i})$, we can use a second-order Taylor expansion of
$\mathrm{VoI}$ around the conditional mean of $g$, and we obtain111See
Appendix B.2 for detailed derivation.

$\displaystyle\mathds{E}[\mathrm{VoI}(x_{i},\hat{y}_{i})|g_{[t]}^{\text{observe}}]\approx\alpha_{i}+\frac{1}{2}\Sigma_{t,i}^{*}\beta_{i}\triangleq\gamma_{t,i},$
(3)

with $\alpha_{i}$ and $\beta_{i}$ being computed as

$\alpha_{i}=(1+\exp(-m_{t,i}^{*}))^{-1},\quad\beta_{i}=\alpha_{i}(1-\alpha_{i})(1-2\alpha_{i}).$

In the above formulas, $m_{t,i}^{*}$ and $\Sigma_{t,i}^{*}$ are the mean and
the variance component of the vector $m_{t}^{*}$ and matrix $\Sigma_{t}^{*}$
corresponding to sample $i$. A disadvantage of the approximation (3) is that
the value $\gamma_{t,i}$ may become negative due to the possible negative
value of $\beta_{i}$. If this happens, we can resort to the first-order
approximation:

$\mathds{E}[\mathrm{VoI}(x_{i},\hat{y}_{i})|g_{[t]}^{\text{observe}}]\approx\alpha_{i},$

which guarantees positivity due to the definition of $\alpha_{i}$.

###  4.2 Covariance Specification.

Given any two samples $(x,\widehat{y})$ and
$(x^{\prime},\widehat{y}^{\prime})$, the covariance between $g(x,\widehat{y})$
and $g(x^{\prime},\widehat{y}^{\prime})$ is dictated by

$\mathrm{Cov}(g(x,\widehat{y}),g(x^{\prime},\widehat{y}^{\prime}))=\mathcal{K}((x,\widehat{y}),(x^{\prime},\widehat{y}^{\prime})).$

The bivariate function $\mathcal{K}$ is constructed using a kernel on the
feature-pseudolabel space $\mathcal{X}\times\mathcal{Y}$. We impose a product
kernel on $\mathcal{X}\times\mathcal{Y}$ of the form

$\mathcal{K}((x,\widehat{y}),(x^{\prime},\widehat{y}^{\prime}))=\mathcal{K}_{\mathcal{X}}(x,x^{\prime})\mathcal{K}_{\mathcal{Y}}(\widehat{y},\widehat{y}^{\prime}).$
(4)

In order to express a covariance function, we construct $\mathcal{K}$ as a
positive definite kernel.

######  Definition 4.1 (Positive definite (pd) kernel).

Let $\mathcal{Z}$ be any set. A symmetric function
$\mathcal{K}_{\mathcal{Z}}:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}$ is
positive definite if for any natural number $n$ and any choices of
$(z_{i})_{i=1}^{n}\in\mathcal{Z}$ and $(\alpha_{i})_{i=1}^{n}\in\mathbb{R}$,
we have

$\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_{i}\alpha_{j}\mathcal{K}_{\mathcal{Z}}(z_{i},z_{j})\geq
0.$

If $\mathcal{K}_{\mathcal{X}}$ and $\mathcal{K}_{\mathcal{Y}}$ are positive
definite kernels, then $\mathcal{K}$ is also a positive definite kernel
according to Schur product theorem [Schur, 1911, Theorem VII]. Thus, it now
suffices to construct individual pd kernel for $\mathcal{K}_{\mathcal{X}}$ and
$\mathcal{K}_{\mathcal{Y}}$. We choose $\mathcal{K}_{\mathcal{X}}$ as the
Gaussian kernel

$\mathcal{K}_{\mathcal{X}}(x,x^{\prime})=\exp\big{(}-\frac{1}{2h_{\mathcal{X}}^{2}}\|x-x^{\prime}\|_{2}^{2}\big{)},$
(5)

where $h_{\mathcal{X}}>0$ is the kernel width.

The main difficulty encountered when specifying the kernel is the categorical
nature of the pseudolabel. Imposing a kernel on $\mathcal{Y}$ hence may
require a significant effort to pin down a similarity value between any pair
of labels. To alleviate this difficulty, we first represent each label $y$ by
the respective conditional first- and second-moments, in which the moments are
estimated using the samples and their pseudolabels. More specifically, we
collect all samples whose pseudolabel is $y$, and we estimate the feature mean
vector and the feature covariance matrix as follows

$\displaystyle\widehat{\mu}_{y}=\frac{1}{N_{y}}\sum_{i:\hat{y}_{i}=y}x_{i}\in\mathbb{R}^{d},\quad\text{and}$
$\displaystyle\widehat{\Sigma}_{y}=\frac{1}{N_{y}}\sum_{i:\hat{y}_{i}=y}(x_{i}-\widehat{\mu}_{y})(x_{i}-\widehat{\mu}_{y})^{\top}\in\mathbb{S}_{+}^{d},$

where $N_{y}$ is the number of samples with pseudolabel $y$. We now anchor the
kernel on $\mathcal{Y}$ through the Gaussian kernel on the product space
$\mathbb{R}^{d}\times\mathbb{S}_{+}^{d}$ of the mean-covariance
representation, that is, for any generic label $y$ and $y^{\prime}$:

$\mathcal{K}_{\mathcal{Y}}(y,y^{\prime})=\exp\big{(}-\frac{\|\widehat{\mu}_{y}-\widehat{\mu}_{y^{\prime}}\|_{2}^{2}}{2h_{\mathcal{Y}}^{2}}\big{)}\exp\big{(}-\frac{\|\widehat{\Sigma}_{y}-\widehat{\Sigma}_{y^{\prime}}\|_{F}^{2}}{2h_{\mathcal{Y}}^{2}}\big{)}.$
(6)

Notice that this kernel is specified by a single bandwidth parameter
$h_{\mathcal{Y}}>0$. By combining Jayasumana et al. [2013, Theorems 4.3 and
4.4] and by the fact that the product of pd kernels is again a pd kernel, we
conclude that the kernel $\mathcal{K}$ defined using the formulas (4)-(6) is a
pd kernel.

######  Remark 4.2 (Feature-label metric).

Measuring the distance between two (categorical) classes by measuring the
distance between the corresponding class-conditional distributions was
previously used in Alvarez-Melis and Fusi [2020] and Hua et al. [2023]. Under
the Gaussian assumptions therein, the 2-Wasserstein distance between
conditional distributions simplifies to an explicit formula involving a
Euclidean distance between their mean vectors and a Bures distance between
their covariance matrices. Unfortunately, constructing a Gaussian kernel with
the Bures distance on the space of symmetric positive semidefinite matrices
may not lead to a pd kernel. To ensure that $\mathcal{K}_{\mathcal{Y}}$ is a
pd kernel, we need to use the Frobenius norm for the covariance part of (6).

######  Remark 4.3 (Intuition on using pseudolabel).

Exploiting the pseudolabel serves the following intuition: Suppose that an
input $x_{i}$ is misclassified. If there exists another input $x_{i}^{\prime}$
which is close to $x_{i}$, and its pseudolabel $\hat{y}_{i}^{\prime}$ is also
close to $\hat{y}_{i}$, then it is also likely that $x_{i}^{\prime}$ will also
be misclassified. Thus, our construction of the VoI implicitly relies on the
assumption that the pseudolabel is also informative to help predict failure
patterns. If a user finds this assumption impractical, it is straightforward
to remove this information from the specification of the kernel, and the
construction of the Gaussian process still holds with minimal changes.

######  Remark 4.4 (Dimensionality reduction).

If the feature space is high-dimensional ($d$ is large), we can apply a
dimensionality reduction mapping $\varphi(x_{i})$ to map the features to a
space of smaller dimensions $d^{\prime}\ll d$. The kernel
$\mathcal{K}_{\mathcal{Y}}$ will be computed similarly with
$\widehat{\mu}_{y}$ and $\widehat{\Sigma}_{y}$ are all $d^{\prime}$
dimensional.

###  4.3 Value Adjustment and Pattern Neighborhood Update

At time $t$, the algorithm recommends querying the true label of the samples
whose indices are in the set $\mathcal{I}_{t}$. If for $i\in\mathcal{I}_{t}$,
the sample $x_{i}$ is misclassified, that is $\hat{y}_{i}\neq
y_{i}^{\mathrm{true}}$, then we should update the observed probability to
$\mathrm{VoI}(x_{i},\hat{y}_{i})=1$. However, this would lead to updating
$g(x_{i},\hat{y}_{i})=+\infty$. Similarly, if $x_{i}$ is classified correctly
then we should update $g(x_{i},\hat{y}_{i})=-\infty$. To alleviate the
infinity issues, we set a finite bound $-\infty<L<0<U<+\infty$, and we update
using the rule

$g^{\text{observe}}(x_{i},\hat{y}_{i})=\begin{cases}U&\text{if $x_{i}$ is
misclassified},\\\ L&\text{otherwise.}\end{cases}$

Moreover, suppose that at time $t$, the annotator identifies that some samples
form a pattern. In that case, we intentionally re-calibrate all the values for
the samples in the pattern using

$g^{\text{observe}}(x_{i},\hat{y}_{i})=L\quad\text{if $i$ belongs to a failure
pattern}.$

In doing so, we intentionally adjust the misclassified sample $i$ to be a
correctly classified (or ‘good’) sample.

######  Remark 4.5 (Interpretation of VoI updates).

The VoI aims at capturing the probability that an unlabeled sample belongs to
an unidentified failure mode. There are three exemplary cases to guide the
design of the VoI: (i) if an unlabeled sample is near the misclassified
samples and those misclassified samples do not form a failure mode yet, then
VoI should be high. This signifies exploitation for confirmation: it is better
to concentrate on the region surrounding this unlabeled sample to confirm this
failure mode; (ii) if an unlabeled sample is near the correctly-classified
samples, then VoI should be low. This is an exploration process: this sample
may be in the correctly-classified region, and we should query in other
regions; (iii) if an unlabeled sample is near the misclassified samples and
those misclassified samples already formed a failure mode, then VoI should be
low. Again, this depicts an exploration process: it is better to search
elsewhere for other failure modes.

##  5 Determinant Point Process Sampler for Annotation Recommendation

Determinantal Point Processes (DDPs) is a family of stochastic models that
originates from quantum physics: DPPs are particularly useful to model the
repulsive behavior of Fermion particles [Macchi, 1975]. Recently, DPPs have
gained attraction in the machine learning community [Kulesza and Taskar, 2012,
Affandi et al., 2014, Urschel et al., 2017] thanks to its successes in
recommendation systems [Chen et al., 2018, Wilhelm et al., 2018, Gartrell et
al., 2017] and text and video summarization [Lin and Bilmes, 2012, Cho et al.,
2019, Gong et al., 2014], to name a few. Given $N$ samples, the corresponding
DPP can be formalized as follows.

######  Definition 5.1 ($L$-ensemble DPP).

Given a matrix $L\in\mathbb{S}_{+}^{N}$, an $L$-ensemble DPP is a distribution
over all $2^{N}$ index subsets $J\subseteq\\{1,\ldots,N\\}$ such that

$\mathrm{Prob}(J)=\det(L_{J})/\det(I+L),$

where $L_{J}$ denotes the $|J|$-by-$|J|$ submatrix of $L$ with rows and
columns indexed by $J$.

In this paper, we construct a DPP to help select the next batch of samples to
query the annotator for their true labels. We design the matrix $L$ that can
balance between exploration (querying distant samples in order to identify new
potential failure patterns) and exploitation (querying neighborhood samples to
confirm plausible failure patterns). Given $N$ samples, the exploration is
determined by a similarity matrix $S\in\mathbb{S}_{+}^{N}$ that captures
pairwise similarity of the samples

$S_{ij}=\kappa(x_{i},x_{j})\quad\forall(i,j)$

for some similarity metric $\kappa$. For example, we can use
$\kappa\equiv\mathcal{K}_{\mathcal{X}}$, where $\mathcal{K}_{\mathcal{X}}$ is
prescribed in (5) with the same bandwidth parameter $h_{\mathcal{X}}$.

Exploration. At time $t$, conditioned on the samples that are already queried
$\mathcal{I}_{[t]}$, we can recover a conditional similarity matrix
$S_{t}^{*}$ for the set of unqueried samples following [Borodin and Rains,
2005, Proposition 1.2]. Let $|\mathcal{I}_{[t]}|$ be the number of samples
that have been drawn so far, then $S_{t}^{*}$ is a
$(N-|\mathcal{I}_{[t]}|)$-dimensional positive (semi)definite matrix,
calculated as

$S_{t}^{*}=([(S+I_{\mathcal{I}_{[t]}^{*}})^{-1}]_{\mathcal{I}_{[t]}^{*}})^{-1}-I.$

Thus, the matrix $S_{t}^{*}$ will serve as a diversity-promoting term of the
conditional DPP at time $t$.

Exploitation. The exploitation is determined by a probability matrix
$P\in\mathbb{S}_{+}^{N-|\mathcal{I}_{[t]}|}$. At time $t$, we can use
$P_{t}^{*}=\mathrm{diag}(\gamma_{t,i})$, where $\gamma_{t,i}$ is the posterior
probability of being misclassified defined in (3). Notice that if
$\gamma_{t,i}$ is negative, we can replace $\gamma_{t,i}$ by the first-order
approximation to guarantee that $P_{t}^{*}$ is a diagonal matrix with strictly
positive diagonal elements. The matrix $P_{t}^{*}$ will induce exploitation
because it promotes choosing samples with a high posterior probability of
misclassification with the goal of confirming patterns.

Exploration-Exploitation Balancing Conditional DPP. We impose an additional
parameter $\vartheta\in[0,1]$ to capture the exploration-exploitation trade-
off. At time $t$, we use a DPP with the kernel matrix $L^{\vartheta}$ defined
as

$L_{t}^{\vartheta}=\vartheta S_{t}^{*}+(1-\vartheta)P_{t}^{*}$

for some mixture weight $\vartheta\in[0,1]$. In particular, when $\vartheta$
is equal to zero, the algorithm’s approach is entirely exploitative, and its
primary objective is to confirm failure patterns in the dataset. Conversely,
when $\vartheta$ is equal to one, the algorithm is entirely explorative, and
its main aim is to recommend a diverse set of samples from the dataset. It is
worth noting that the algorithm’s behavior can be adjusted by modifying the
value of $\vartheta$ to achieve an appropriate trade-off between exploration
and exploitation depending on the specific problem at hand. Because both
$S_{t}^{*}$ and $P_{t}^{*}$ are positive semidefinite matrices, the weighted
matrix $L_{t}^{\vartheta}$ is also positive semidefinite, and specifies a
valid DPP.

Query Suggestion. We choose a set of unlabeled samples for annotation using a
maximum a posteriori (MAP) estimate of the DPP specified by
$L_{t}^{\vartheta}$. We then find the $s$ samples from the unlabeled data by
solving the following problem

$\max\left\\{\det(L_{z})\leavevmode\nobreak\ :\leavevmode\nobreak\
z\in\\{0,1\\}^{N-|\mathcal{I}_{[t]}|},\leavevmode\nobreak\
\|z\|_{0}=s\right\\},$ (7)

where $L_{z}$ is a submatrix of
$L_{t}^{\vartheta}\in\mathbb{S}_{+}^{N-|\mathcal{I}_{[t]}|}$ restricted to
rows and columns indexed by the one-components of $z$. It is well-known that
the solution to problem (7) coincides with the MAP estimate of the DPP with a
cardinality constraint [Kulesza and Taskar, 2012].

Unfortunately, problem (7) is NP-hard [Kulesza and Taskar, 2012]. We thus use
heuristics to find a good solution to the problem in a high-dimensional
setting with a low running time. A common greedy algorithm to solve the MAP
estimation problem is to iteratively find an index that maximizes the marginal
gain to the incumbent set of chosen samples $z$. We then add the index $j$ to
the set of samples until reaching the cardinality constraint of $s$
prototypes. This greedy construction algorithm has a complexity cost of
$\mathcal{O}(s^{2}N)$ time for each inference. An implementation of this
algorithm is provided in Chen et al. [2018]. The greedy algorithm has been
shown to achieve an approximation ratio of $\mathcal{O}(\frac{1}{s!})$[Civril
and Magdon-Ismail, 2009]. Finally, to boost the solution quality, we add a
$2$-neighborhood local search that swaps one element from the incumbent set
with one element from the complementary set. This local search is performed
until no further improvement is found.

##  6 Bandwidth Selection

The product kernel $\mathcal{K}$ defined in (4) on the feature-pseudolabel
label space requires the specification of two hyper-parameters: the bandwidth
for the feature $h_{\mathcal{X}}$ and the bandwidth for the pseudolabels
$h_{\mathcal{Y}}$. Given $N$ feature-pseudolabel pairs $(x_{i},\hat{y}_{i})$
for $i=1,\ldots,N$ and the kernel $\mathcal{K}$ defined as in Section 4, we
denote the Gram matrix by $K\in\mathbb{S}_{+}^{N}$ with the components of $K$
satisfying (1). If the bandwidth parameters are too small compared to the
feature distance $\|x-x^{\prime}\|_{2}$ and the pseudolabel distance
$\sqrt{\|\widehat{\mu}_{y}-\widehat{\mu}_{y^{\prime}}\|_{2}^{2}+\|\widehat{\Sigma}_{y}-\widehat{\Sigma}_{y^{\prime}}\|_{F}^{2}}$
in the dataset, then the matrix $K$ tends toward an $N$-by-$N$ identity matrix
$I_{N}$. Notice that when $K$ is an identity matrix, the matrix multiplication
$(K^{*})^{\top}K^{-1}$ turns into a matrix of zeros, and the updates (2)
become $m_{t}^{*}=m_{[t]}^{*}$ and $\Sigma_{t}^{*}=K_{[t]}^{**}$. This means
that all observed information from previous queries is ignored. To alleviate
this, we impose a restriction on $h_{\mathcal{X}}$ and $h_{\mathcal{Y}}$ so
that

$\|K(h_{\mathcal{X}},h_{\mathcal{Y}})-I_{N}\|_{F}\geq\delta\|I_{N}\|_{F}$ (8)

for some value of $\delta>0$. In the above equation, we make explicit the
dependence of the Gram matrix $K$ on the hyper-parameters $h_{\mathcal{X}}$
and $h_{\mathcal{Y}}$, and the norm $\|\cdot\|_{F}$ is the Frobenius norm.
Condition (8) imposes that the Gram matrix needs to be sufficiently different
from the identity matrix, where the magnitude of the difference is controlled
by $\delta$. The next proposition provides the condition to choose
$h_{\mathcal{X}}$ and $h_{\mathcal{Y}}$ to satisfy this condition.

######  Proposition 6.1 (Hyper-parameter values).

For a fixed value of $\delta\in(0,\sqrt{N-1})$, the condition (8) is satisfied
if

$\frac{D_{\mathcal{X}}}{h_{\mathcal{X}}^{2}}+\frac{D_{\mathcal{Y}}}{h_{\mathcal{Y}}^{2}}\leq\ln{\frac{N-1}{\delta^{2}}},$

where $\mathcal{D}_{\mathcal{X}}$ and $\mathcal{D}_{\mathcal{Y}}$ are
calculated based on the dataset as

$\displaystyle D_{\mathcal{X}}$
$\displaystyle=\frac{\sum_{i>j}\|x_{i}-x_{j}\|_{2}^{2}}{{N\choose
2}},\quad\text{and}$ $\displaystyle D_{\mathcal{Y}}$
$\displaystyle=\frac{\sum_{i>j}\|\widehat{\mu}_{\hat{y}_{i}}-\widehat{\mu}_{\hat{y}_{j}}\|_{2}^{2}+\|\widehat{\Sigma}_{\hat{y}_{i}}-\widehat{\Sigma}_{\hat{y}_{j}}\|_{F}^{2}}{{N\choose
2}}.$

We suggest choosing $h_{\mathcal{X}}$ and $h_{\mathcal{X}}$ to equalize the
components

$\frac{D_{\mathcal{X}}}{h_{\mathcal{X}}^{2}}=\frac{D_{\mathcal{Y}}}{h_{\mathcal{Y}}^{2}}=\frac{1}{2}\ln{\frac{N-1}{\delta^{2}}}.$

We also notice that the value of $\delta=\sqrt{2}\times 10^{-6}$ is reasonable
for most practical cases encountered in the numerical experiments of this
paper. Hence, without other mention stated, we set $\delta$ to $\sqrt{2}\times
10^{-6}$.

##  7 Numerical Experiments

Datasets. For the numerical experiments, we utilize 15 real-world datasets
adapted from Eyuboglu et al. [2022]222Datasets are publicly available at
https://dcbench.readthedocs.io/en/latest. Each dataset in Eyuboglu et al.
[2022] consists of a pre-trained classifier and a collection of data points.
Each data point has three features: Activation (a 512-dimensional embedding
features of the image with respect to the pre-trained classifier), True Label
(an integer in the range $\\{0,\ldots,C\\}$ that represents the true class of
the data point), Probs (a $C$-dimensional vector that indicates the
probability of each class). By taking the argmax of the Probs vector for each
data point, we can determine the predicted label (pseudolabel) for that data
point.

We use the following construction of a failure pattern: Two samples are
connected by an edge if each sample is in the $k_{\mathrm{nn}}$-nearest
neighbors of the other. Because $\mathcal{X}$ is a feature space, we measure
the distance between two samples by taking the Euclidean distance between
$x_{i}$ and $x_{j}$. Notice that $k_{\mathrm{nn}}$ is a parameter that is
chosen by the user. Criterion C in Definition 3.1 is chosen as maximally
connected subgraphs. Further discussion about this specific selection of the
user is provided in Appendix A.1. Indicating the failure mode as above
requires the user to input two hyper-parameters, $k_{nn}$ and $M$. The
discussion about choosing values of $k_{nn}$ and $M$ in practical problems is
in Appendix A.3.

For each dataset, we construct a dataset that is suited for the task of
failure identification as follows: we choose different values of $k_{nn}$ to
construct the graph (cf. Section 3) and the evidence threshold $M$, then we
generate the ground truth information about the true failure patterns by
finding maximally connected components in $\mathcal{G}^{\mathrm{mis}}$. Each
sample in the dataset is now augmented to have four features: Activation, True
Label, Pseudo Label, and Pattern, where Pattern is an integer in the range
$\\{-1,1,\ldots,P\\}$, where $-1$ means that the sample does not belong to any
failure pattern, and $P$ is the number of failure patterns in the dataset.

During the experiment, the true labels and patterns of samples are hidden:
true labels are only accessible by querying the annotator, while pattern
information is used to compute the performance ex-post. Our 15 generated
datasets are classified into three classes based on the level of SNR: Low,
Medium, and High. The details are in Appendix A.2.

Comparison. We compare the following baselines:

  * •

Active learning algorithms: We consider two popular active learning methods,
namely BADGE [Ash et al., 2019] and Coreset [Sener and Savarese, 2017].
Because the classifier is fixed in our setting, the retraining stage in these
active learning algorithms is omitted.

  * •

Uniform Sampling (US) algorithm: At iteration $t$ with the set of remaining
unlabeled samples $\mathcal{I}_{[t]}^{*}$, we pick a size $s$ subset of
$\mathcal{I}_{[t]}^{*}$ with equal probability. This algorithm is a stochastic
algorithm; hence we take results from 30 random seed numbers and calculate the
average.

  * •

Five variants of our Directed Sampling (DS_$\vartheta$) algorithm, with
$\vartheta$ chosen from $\\{0,0.25,0.5,0.75,1\\}$. At $\vartheta=0$, our
algorithm is purely exploitative, emphasizing the confirmation of failure
patterns. At $\vartheta=1$, our algorithm is purely exploration, emphasizing
recommending diverse samples from the dataset.

Throughout, the batch size is set to $s=25$ for all competing methods. Codes
and numerical results are available at
https://github.com/nguyenngocbaocmt02/FPD.

Experiment 1 (Sensitivity). The goal of this experiment is to measure the
sensitivity of different recommendation algorithms. Hereby, sensitivity is
defined as the fraction between the number of queried samples until the
detection of the first failure pattern in the dataset and the total number of
samples. This value measures how slowly we identify the first failure pattern:
a lower sensitivity is more desirable.

We observed that the two active learning algorithms have the lowest
performance. We suspect that the objective of active learning algorithms is to
refine the decision boundaries to obtain better performance (accuracy),
whereas the primary concern herein is to isolate misclassified clusters. Thus,
active learning methods may not be applicable to the problem considered in
this paper.

We could see from Table 1 that the sensitivity of all methods decreases as the
SNR increases. All DS variants except the extreme with $\vartheta=1.0$
outperform the US method and active learning methods. The poor performance of
DS_1.0 is attributed to the lack of an exploitative term, which is also the
knowledge gathered from previous queries. Moreover, we notice that our
proposed algorithm, DS_0.25 and DS_0 have the smallest sensitivity of 0.11
overall. While DS_0.25 achieves the highest performance in datasets with low
noise magnitude, DS_0 is more effective in medium and high SNR contexts. This
can be attributed to the fact that when the SNR is low, there are many noise
samples. Consequently, if DS_0 gets trapped in a noisy misclassified region,
it may take considerable time to confirm whether this area contains any
patterns because the algorithm is purely exploitative when $\vartheta=0$. In
contrast, DS_0.25 overcomes this issue by incorporating an exploration term
that avoids focusing too much on any area.

Table 1: Benchmark of Sensitivity on different noise magnitudes. Bolds indicate the best methods. | Noise Magnitude
---|---
Methods | Low | Medium | High | Overall
US | 0.48$\pm$0.13 | 0.29$\pm$0.07 | 0.22$\pm$0.07 | 0.33$\pm$0.15
DS_0 | 0.22$\pm$0.27 | 0.04$\pm$0.02 | 0.03$\pm$0.01 | 0.11$\pm$0.18
DS_0.25 | 0.16$\pm$0.08 | 0.09$\pm$0.04 | 0.08$\pm$0.04 | 0.11$\pm$0.07
DS_0.5 | 0.27$\pm$0.20 | 0.15$\pm$0.16 | 0.07$\pm$0.04 | 0.16$\pm$0.17
DS_0.75 | 0.27$\pm$0.10 | 0.17$\pm$0.11 | 0.08$\pm$0.06 | 0.17$\pm$0.12
DS_1.0 | 0.50$\pm$0.10 | 0.35$\pm$0.12 | 0.22$\pm$0.07 | 0.36$\pm$0.15
BADGE | 0.56$\pm$0.10 | 0.35$\pm$0.07 | 0.27$\pm$0.06 | 0.40$\pm$0.15
Coreset | 0.62$\pm$0.08 | 0.44$\pm$0.07 | 0.27$\pm$0.08 | 0.44$\pm$0.16

Experiment 2 (Effectiveness). This experiment aims to confirm the ability to
recommend methods in detecting failure patterns subject to a limited number of
annotation queries. More specifically, we allow the number of queries to be
maximally $10\%$ and $20\%$ of the total number of samples in the dataset, and
we measure effectiveness as the percentage of detected patterns up to that
cut-off. A higher value of effectiveness indicates a higher capacity for
failure pattern identification.

When the maximum permitted number of queries is low (e.g., $10\%$), there is
no significant difference in the overall performance of all algorithms because
the queried information about the dataset is insufficient to confirm most
patterns, see Table 2. However, all versions of DS perform equally well and
are more effective than the US, BADGE, and Coreset. As the number of queries
increases to $20\%$ of the dataset in Table 3, all DS variants significantly
outperform US and active learning methods: the DS methods manage to detect
more than a third of all failure patterns. In high SNR datasets, DS_0.5 can
even detect over half of the patterns on average.

Table 2: Benchmark of Effectiveness (at $10\%$ of sample size) on different noise magnitudes. Bolds indicate the best methods. | Noise Magnitude
---|---
Methods | Low | Medium | High | Overall
US | 0.00$\pm$0.00 | 0.00$\pm$0.01 | 0.02$\pm$0.08 | 0.01$\pm$0.05
DS_0.0 | 0.10$\pm$0.09 | 0.24$\pm$0.06 | 0.38$\pm$0.10 | 0.24$\pm$0.14
DS_0.25 | 0.10$\pm$0.13 | 0.18$\pm$0.19 | 0.22$\pm$0.19 | 0.17$\pm$0.18
DS_0.5 | 0.05$\pm$0.10 | 0.18$\pm$0.19 | 0.27$\pm$0.16 | 0.17$\pm$0.18
DS_0.75 | 0.00$\pm$0.00 | 0.10$\pm$0.12 | 0.32$\pm$0.19 | 0.14$\pm$0.18
DS_1.0 | 0.00$\pm$0.00 | 0.00$\pm$0.00 | 0.00$\pm$0.00 | 0.00$\pm$0.00
BADGE | 0.00$\pm$0.00 | 0.00$\pm$0.00 | 0.00$\pm$0.00 | 0.00$\pm$0.00
Coreset | 0.00$\pm$0.00 | 0.00$\pm$0.00 | 0.00$\pm$0.00 | 0.00$\pm$0.00
Table 3: Benchmark of Effectiveness (at $20\%$ of sample size) on different noise magnitudes. Bolds indicate the best methods. | Noise Magnitude
---|---
Methods | Low | Medium | High | Overall
US | 0.00$\pm$0.03 | 0.02$\pm$0.07 | 0.16$\pm$0.20 | 0.06$\pm$0.14
DS_0.0 | 0.29$\pm$0.21 | 0.31$\pm$0.18 | 0.38$\pm$0.1 | 0.33$\pm$0.18
DS_0.25 | 0.10$\pm$0.13 | 0.26$\pm$0.13 | 0.50$\pm$0.11 | 0.28$\pm$0.21
DS_0.5 | 0.14$\pm$0.13 | 0.27$\pm$0.25 | 0.52$\pm$0.15 | 0.31$\pm$0.24
DS_0.75 | 0.05$\pm$0.10 | 0.24$\pm$0.27 | 0.43$\pm$0.08 | 0.24$\pm$0.23
DS_1.0 | 0.00$\pm$0.00 | 0.05$\pm$0.10 | 0.15$\pm$0.20 | 0.07$\pm$0.14
BADGE | 0.00$\pm$0.00 | 0.01$\pm$0.05 | 0.06$\pm$0.14 | 0.02$\pm$0.09
Coreset | 0.00$\pm$0.00 | 0.00$\pm$0.00 | 0.05$\pm$0.10 | 0.02$\pm$0.06

Conclusions. We proposed a sampling mechanism for the purpose of failure
pattern identification. Given a classifier and a set of unlabeled data, the
method sequentially suggests a batch of samples for annotation and then
consolidates the information to detect the failure patterns. The sampling
mechanism needs to balance two competing criteria: exploration (querying
diverse samples to identify new potential failure patterns) and exploitation
(querying neighborhood samples to collect evidence to confirm failure
patterns). We constructed a Gaussian process to model the exploitative
evolution of our belief about the failure patterns and used a DPP with a
weighted matrix to balance the exploration-exploitation trade-off. The
numerical experiments demonstrate that our sampling mechanisms outperform the
uniform sampling method in both sensitivity and effectiveness measures.

Acknowledgments.  We gratefully acknowledge the generous support from the
CUHK’s Improvement on Competitiveness in Hiring New Faculties Funding Scheme
and the CUHK’s Direct Grant Project Number 4055191.

## References

  * Affandi et al. [2014] Raja Hafiz Affandi, Emily Fox, Ryan Adams, and Ben Taskar.  Learning the parameters of determinantal point process kernels.  In _International Conference on Machine Learning_ , pages 1224–1232. PMLR, 2014.
  * Albahri et al. [2023] AS Albahri, Ali M Duhaim, Mohammed A Fadhel, Alhamzah Alnoor, Noor S Baqer, Laith Alzubaidi, OS Albahri, AH Alamoodi, Jinshuai Bai, Asma Salhi, et al.  A systematic review of trustworthy and explainable artificial intelligence in healthcare: assessment of quality, bias risk, and data fusion.  _Information Fusion_ , 2023.
  * Alvarez-Melis and Fusi [2020] David Alvarez-Melis and Nicolo Fusi.  Geometric dataset distances via optimal transport.  _Advances in Neural Information Processing Systems_ , 33:21428–21439, 2020.
  * Ash et al. [2019] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal.  Deep batch active learning by diverse, uncertain gradient lower bounds.  _arXiv preprint arXiv:1906.03671_ , 2019.
  * Borodin and Rains [2005] Alexei Borodin and Eric M Rains.  Eynard–Mehta theorem, Schur process, and their Pfaffian analogs.  _Journal of Statistical Physics_ , 121(3):291–317, 2005.
  * Brito et al. [1997] Maria R Brito, Edgar L Chávez, Adolfo J Quiroz, and Joseph E Yukich.  Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection.  _Statistics & Probability Letters_, 35(1):33–42, 1997.
  * Budd et al. [2021] Samuel Budd, Emma C Robinson, and Bernhard Kainz.  A survey on active learning and human-in-the-loop deep learning for medical image analysis.  _Medical Image Analysis_ , 71:102062, 2021.
  * Caton and Haas [2020] Simon Caton and Christian Haas.  Fairness in machine learning: A survey.  _arXiv preprint arXiv:2010.04053_ , 2020.
  * Chen et al. [2018] Laming Chen, Guoxin Zhang, and Eric Zhou.  Fast greedy MAP inference for determinantal point process to improve recommendation diversity.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Cho et al. [2019] Sangwoo Cho, Chen Li, Dong Yu, Hassan Foroosh, and Fei Liu.  Multi-document summarization with determinantal point processes and contextualized representations.  _arXiv preprint arXiv:1910.11411_ , 2019.
  * Civril and Magdon-Ismail [2009] Ali Civril and Malik Magdon-Ismail.  On selecting a maximum volume sub-matrix of a matrix and related problems.  _Theoretical Computer Science_ , 410(47-49):4801–4811, 2009.
  * d’Eon et al. [2022a] Greg d’Eon, Jason d’Eon, James R Wright, and Kevin Leyton-Brown.  The spotlight: A general method for discovering systematic errors in deep learning models.  In _2022 ACM Conference on Fairness, Accountability, and Transparency_ , pages 1962–1981, 2022a.
  * d’Eon et al. [2022b] Greg d’Eon, Jason d’Eon, James R. Wright, and Kevin Leyton-Brown.  The spotlight: A general method for discovering systematic errors in deep learning models.  In _2022 ACM Conference on Fairness, Accountability, and Transparency_ , FAccT ’22, page 1962–1981, New York, NY, USA, 2022b. Association for Computing Machinery.
  * Eyuboglu et al. [2022] Sabri Eyuboglu, Maya Varma, Khaled Saab, Jean-Benoit Delbrouck, Christopher Lee-Messer, Jared Dunnmon, James Zou, and Christopher Ré.  Domino: Discovering systematic errors with cross-modal embeddings.  _arXiv preprint arXiv:2203.14960_ , 2022.
  * Gartrell et al. [2017] Mike Gartrell, Ulrich Paquet, and Noam Koenigstein.  Low-rank factorization of determinantal point processes.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31, 2017.
  * Glomsrud et al. [2019] Jon Arne Glomsrud, André Ødegårdstuen, Asun Lera St Clair, and Øyvind Smogeli.  Trustworthy versus explainable ai in autonomous vessels.  In _Proceedings of the International Seminar on Safety and Security of Autonomous Vessels (ISSAV) and European STAMP Workshop and Conference (ESWC)_ , volume 37, 2019.
  * Gong et al. [2014] Boqing Gong, Wei-Lun Chao, Kristen Grauman, and Fei Sha.  Diverse sequential subset selection for supervised video summarization.  _Advances in neural information processing systems_ , 27, 2014.
  * Hua et al. [2023] Xinru Hua, Truyen Nguyen, Tam Le, Jose Blanchet, and Viet Anh Nguyen.  Dynamic flows on curved space generated by labeled data.  In _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23_ , 2023.
  * Jayasumana et al. [2013] Sadeep Jayasumana, Richard Hartley, Mathieu Salzmann, Hongdong Li, and Mehrtash Harandi.  Kernel methods on the Riemannian manifold of symmetric positive definite matrices.  In _proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 73–80, 2013.
  * Kulesza and Taskar [2012] Alex Kulesza and Ben Taskar.  Determinantal point processes for machine learning.  _Foundations and Trends® in Machine Learning_ , 5(2-3):123–286, 2012.
  * Lin and Bilmes [2012] Hui Lin and Jeff Bilmes.  Learning mixtures of submodular shells with application to document summarization.  In _Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence_ , 2012.
  * Macchi [1975] Odile Macchi.  The coincidence approach to stochastic point processes.  _Advances in Applied Probability_ , 7(1):83–122, 1975.
  * McInnes et al. [2018] Leland McInnes, John Healy, and James Melville.  Umap: Uniform manifold approximation and projection for dimension reduction.  _arXiv preprint arXiv:1802.03426_ , 2018.
  * Mehrabi et al. [2021] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan.  A survey on bias and fairness in machine learning.  _ACM Computing Surveys (CSUR)_ , 54(6):1–35, 2021\.
  * Murphy [2012] K.P. Murphy.  _Machine Learning: A Probabilistic Perspective_.  MIT Press, 2012.
  * Nushi et al. [2018] Besmira Nushi, Ece Kamar, and Eric Horvitz.  Towards accountable AI: Hybrid human-machine analyses for characterizing system failure.  In _Proceedings of the AAAI Conference on Human Computation and Crowdsourcing_ , volume 6, pages 126–135, 2018.
  * Pessach and Shmueli [2022] Dana Pessach and Erez Shmueli.  A review on fairness in machine learning.  _ACM Computing Surveys (CSUR)_ , 55(3):1–44, 2022\.
  * Polyzotis et al. [2019] Neoklis Polyzotis, Steven Whang, Tim Klas Kraska, and Yeounoh Chung.  Slice finder: Automated data slicing for model validation.  In _Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2019_ , 2019.
  * Ren et al. [2021] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang.  A survey of deep active learning.  _ACM Computing Surveys (CSUR)_ , 54(9):1–40, 2021\.
  * Rudin and Ustun [2018] Cynthia Rudin and Berk Ustun.  Optimized scoring systems: Toward trust in machine learning for healthcare and criminal justice.  _Interfaces_ , 48(5):449–466, 2018.
  * Sagadeeva and Boehm [2021] Svetlana Sagadeeva and Matthias Boehm.  Sliceline: Fast, linear-algebra-based slice finding for ML model debugging.  In _Proceedings of the 2021 International Conference on Management of Data_ , pages 2290–2299, 2021.
  * Schur [1911] J. Schur.  Bemerkungen zur theorie der beschränkten bilinearformen mit unendlich vielen veränderlichen.  _Journal für die reine und angewandte Mathematik_ , 1911(140):1–28, 1911.
  * Sener and Savarese [2017] Ozan Sener and Silvio Savarese.  Active learning for convolutional neural networks: A core-set approach.  _arXiv preprint arXiv:1708.00489_ , 2017.
  * Shaban-Nejad et al. [2021] Arash Shaban-Nejad, Martin Michalowski, John S Brownstein, and David L Buckeridge.  Guest editorial explainable ai: towards fairness, accountability, transparency and trust in healthcare.  _IEEE Journal of Biomedical and Health Informatics_ , 25(7):2374–2375, 2021.
  * Singla et al. [2021] Sahil Singla, Besmira Nushi, Shital Shah, Ece Kamar, and Eric Horvitz.  Understanding failures of deep networks via robust feature extraction.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12853–12862, 2021.
  * Sohoni et al. [2020] Nimit Sohoni, Jared Dunnmon, Geoffrey Angus, Albert Gu, and Christopher Ré.  No subclass left behind: Fine-grained robustness in coarse-grained classification problems.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 19339–19352, 2020.
  * Song et al. [2022a] Yunsheng Song, Jing Zhang, and Chao Zhang.  A survey of large-scale graph-based semi-supervised classification algorithms.  _International Journal of Cognitive Computing in Engineering_ , 3:188–198, 2022a.
  * Song et al. [2022b] Zixing Song, Xiangli Yang, Zenglin Xu, and Irwin King.  Graph-based semi-supervised learning: A comprehensive review.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2022b.
  * Urschel et al. [2017] John Urschel, Victor-Emmanuel Brunel, Ankur Moitra, and Philippe Rigollet.  Learning determinantal point processes with moments and cycles.  In _International Conference on Machine Learning_ , pages 3511–3520. PMLR, 2017.
  * Wagner and Koopman [2015] Michael Wagner and Philip Koopman.  A philosophy for developing trust in self-driving cars.  In _Road Vehicle Automation 2_ , pages 163–171. Springer, 2015.
  * Wilhelm et al. [2018] Mark Wilhelm, Ajith Ramanathan, Alexander Bonomo, Sagar Jain, Ed H Chi, and Jennifer Gillenwater.  Practical diversified recommendations on Youtube with determinantal point processes.  In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ , pages 2165–2173, 2018.
  * Wu et al. [2022] Xingjiao Wu, Luwei Xiao, Yixuan Sun, Junhang Zhang, Tianlong Ma, and Liang He.  A survey of human-in-the-loop for machine learning.  _Future Generation Computer Systems_ , 2022.
  * Xin et al. [2018] Doris Xin, Litian Ma, Jialin Liu, Stephen Macke, Shuchen Song, and Aditya Parameswaran.  Accelerating human-in-the-loop machine learning: Challenges and opportunities.  In _Proceedings of the second workshop on data management for end-to-end machine learning_ , pages 1–4, 2018.

##  Appendix A Additional Experiments

###  A.1 Motivation for the specific user’s defined failure mode definition

In this section, we provide the motivation, theoretical justification, and
practical effectiveness of the failure mode definition based on mutual nearest
neighbor graph333A mutual $k_{nn}$-nearest neighbor graph is a graph where
there is an edge between $x_{i}$ and $x_{j}$ if $x_{i}$ is one of the $k_{nn}$
nearest neighbors of $x_{j}$ and $x_{j}$ is one of the $k_{nn}$ nearest
neighbors of $x_{i}$. on embedding space.

  * •

We make a similar assumption with d’Eon et al. [2022a] and Sohoni et al.
[2020] that the classifier’s activations layer contains essential information
about the semantic features used for classification. The proximity between two
points in this embedding space could indicate their semantic similarity.
Hence, issuing an edge between two points as in the mutual nearest neighbor
graph likely guarantees that two connected points have much more semantic
similarity than other pairs. This would ensure semantic cohesion for the
points within a failure mode according to our definition.

  * •

Regarding the theoretical aspect, we use the mutual nearest neighbor graph,
which is effective in clustering and outliers detection (see Song et al.
[2022b], Song et al. [2022a] and Brito et al. [1997]). Moreover, Brito et al.
[1997, Theorem 2.2] stated that with the reasonable choice of $k_{nn}$,
connected components (a.k.a. maximally connected subgraphs) in a mutual
$k_{nn}$-graph are consistent for the identification of its clustering
structure.

  * •

In terms of more visual representation, we show images of four failure
patterns of dataset id_1 in Figure A.2 to show the effectiveness of this
definition on detecting semantic-cohesion clusters. We can observe that each
failure pattern has a common concept recognizable by humans and includes
images that are all misclassified. The top-left mode includes images of
blonde-haired girls with tanned skin. The top-right mode includes images of
girls wearing earrings. The bottom-left mode contains photos with tilted
angles, and the bottom-right mode contains images with dark backgrounds.

Figure A.2: Failure patterns existing in dataset id_1. One can observe four
distinct failure patterns in this dataset.

###  A.2 Datasets and Implementation Details

We describe fifteen datasets used in our work in Table 4.

Table 4: The description of 15 datasets that are used in the numerical experiments. Dataset | DcBench | Noise Magnitude | SNR | $M$ | $k_{nn}$ | Sample size | Number of misclassified samples
---|---|---|---|---|---|---|---
id_1 | p_72799 | Low | 0.15 | 10 | 7 | 6088 | 572
id_2 | p_122144 | Low | 0.22 | 10 | 7 | 6103 | 1076
id_3 | p_121880 | Low | 0.38 | 10 | 7 | 5969 | 1259
id_4 | p_122653 | Low | 0.47 | 10 | 7 | 6019 | 1088
id_5 | p_118660 | Low | 0.47 | 10 | 8 | 5994 | 1019
id_6 | p_122145 | Medium | 0.69 | 10 | 11 | 6135 | 1141
id_7 | p_121753 | Medium | 0.96 | 10 | 10 | 6138 | 1612
id_8 | p_122406 | Medium | 1.17 | 10 | 16 | 6072 | 937
id_9 | p_118049 | Medium | 1.38 | 10 | 12 | 5979 | 1051
id_10 | p_122150 | Medium | 1.39 | 10 | 10 | 6107 | 1304
id_11 | p_121948 | High | 1.75 | 10 | 15 | 6027 | 1438
id_12 | p_122417 | High | 1.85 | 10 | 19 | 6035 | 1096
id_13 | p_122313 | High | 1.91 | 10 | 15 | 6048 | 1011
id_14 | p_121977 | High | 2.19 | 10 | 17 | 6117 | 1153
id_15 | p_121854 | High | 3.78 | 10 | 24 | 6017 | 1554

Preprocessing: We single out 15 datasets from Eyuboglu et al. [2022], each
includes three features: Activation, True Label, and Pseudo Label. After that,
we preprocess the data using a standard scaler for the Activation feature.

Ground truth generation: It is necessary to assign values of $k_{nn}$ and $M$
to each preprocessed dataset. The value of $M$ expresses the level of evidence
required for confirming the failure patterns. A higher value of $M$ indicates
a greater emphasis on the patterns that exist most frequently in the dataset.
As $M$ decreases to 1, the problem transforms into identifying misclassified
data points, where each failure data point constitutes a pattern. Moreover,
the users choose $M$ so that they can perceive the shared concept of $M$
samples. If $M$ is too small, then the concept may not be distinctive enough
between clusters, while if $M$ is too large, the users may have a bottleneck
in identifying the shared concept. The value of $k_{nn}$ signifies the
coherence required for data points within a pattern. The users choose a
smaller $k_{nn}$ if they need strong tightness between samples in a failure
mode. Brito et al. [1997] recommended choosing $k_{nn}$ of order $\log(N)$ for
consistent identification of the clustering structure. A smaller value of
$k_{nn}$ imposes a more stringent condition to create an edge in the $k_{nn}$
graph. When $k_{nn}$ = 0, each data point is only connected with itself. If
$k_{nn}$ is sufficiently high, all misclassified data points merge to form a
single failure pattern. From Figure A.3, we notice that as the increase of
$k_{nn}$ and SNR, there is a tendency to appear big patterns with a large
number of data points. We could explain it as follows. When increasing
$k_{nn}$, more edges are additionally created, which could initially connect
separate patterns or augment more data points into the patterns. In practical
applications of this problem, it is important to note that the two parameters
$k_{nn}$ and $M$ rely heavily on the users, the machine learning tasks, and
the nature of the dataset. In this study, we have established a fixed value of
M equal to 10 for all datasets, and we have varied the value of $k_{nn}$ to
generate diverse scenarios of Signal-to-Noise Ratio (SNR). With the defined
value of $k_{nn}$, we have constructed the $k_{nn}$ graph of the re-scaled
Activation feature. Subsequently, we have employed a simple Depth First Search
algorithm on the sub-graph of only misclassified data points to collect all
maximally connected components with cardinality greater than $M$. These
components represent patterns that are the focus of the recommending
algorithms. We add one additional feature named Pattern to each data point
which indicates the pattern of it or $-1$ if it does not belong to any
patterns.

Finally, the complete dataset for our problem consists of four information:
Activation, True Label, Pseudo Label, and Pattern.

id_2 dataset (SNR = 0.22)

id_5 dataset (SNR = 0.47)

id_8 dataset (SNR = 1.17)

id_12 dataset (SNR = 1.85)

Figure A.3: The 2-D visualization of the Activation feature in four datasets.
To downsample from a 512-dimension vector to a 2-dimension vector, we utilize
the Supervised Dimension Reduction technique introduced by McInnes et al.
[2018].

###  A.3 Additional Numerical Results

In the main paper, we present the numerical results for groups categorized
into three levels of Signal-to-Noise Ratio (SNR). In this section, we offer a
comprehensive breakdown of the results for each individual dataset in Tables
5, 6, and 7, respectively.

We also provide charts that illustrate the progress of algorithms over
iterations in dataset id_10, as depicted in Figure A.4. The blue line
represents the percentage of queried samples, which appears linear due to the
fixed size of the queried batch at each iteration. The orange line indicates
the percentage of detected misclassified samples out of the total
misclassified ones in the dataset. The green line represents the percentage of
detected failure modes out of the total number of failure modes in the
dataset. It is evident that the orange line, corresponding to methods that
incorporate our exploiting component (Gaussian process component) such as
DS_0.0, DS_0.25, DS_0.5, and DS_0.75, consistently outperforms the blue lines
significantly. This trend clearly demonstrates the effectiveness of our
exploiting term in identifying misclassified samples.

However, DS_0.0 shows inferior performance, as evidenced by the green line
consistently falling below the blue line throughout the iterations, despite
its effectiveness in identifying misclassified samples. In contrast, DS_0.25,
DS_0.5, and DS_0.75 exhibit superb performance in detecting all failure
patterns within approximately 100 iterations (40% of the dataset samples).
This difference can be attributed to the absence of the exploration term in
DS_0.0 when dealing with a high SNR level in dataset id_10.

Table 5: Benchmark of Effectiveness (at 10% of sample size) on different noise magnitudes. Larger values are better. Bolds indicate the best methods for each dataset. Dataset | US | DS_0.0 | DS_0.25 | DS_0.5 | DS_0.75 | DS_1.0 | Coreset | BADGE
---|---|---|---|---|---|---|---|---
id_1 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_2 | 0.00±0.00 | 0.25±0.00 | 0.00±0.00 | 0.25±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_3 | 0.00±0.00 | 0.14±0.00 | 0.14±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_4 | 0.00±0.00 | 0.00±0.00 | 0.33±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_5 | 0.00±0.00 | 0.12±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_6 | 0.00±0.00 | 0.33±0.00 | 0.17±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_7 | 0.00±0.00 | 0.25±0.00 | 0.25±0.00 | 0.25±0.00 | 0.25±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_8 | 0.01±0.03 | 0.17±0.00 | 0.00±0.00 | 0.17±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_9 | 0.00±0.00 | 0.20±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_10 | 0.00±0.00 | 0.25±0.00 | 0.50±0.00 | 0.50±0.00 | 0.25±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_11 | 0.00±0.00 | 0.33±0.00 | 0.00±0.00 | 0.00±0.00 | 0.33±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_12 | 0.01±0.04 | 0.25±0.00 | 0.25±0.00 | 0.25±0.00 | 0.25±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_13 | 0.00±0.00 | 0.33±0.00 | 0.33±0.00 | 0.33±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_14 | 0.01±0.04 | 0.50±0.00 | 0.00±0.00 | 0.25±0.00 | 0.50±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
id_15 | 0.07±0.17 | 0.50±0.00 | 0.50±0.00 | 0.50±0.00 | 0.50±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
Overall | 0.01±0.05 | 0.24±0.14 | 0.17±0.18 | 0.17±0.18 | 0.14±0.18 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00
Table 6: Benchmark of Effectiveness (at 20% of sample size) on different noise magnitudes. Larger values are better. Bolds indicate the best methods for each dataset. Dataset | US | DS_0.0 | DS_0.25 | DS_0.5 | DS_0.75 | DS_1.0 | Coreset | BADGE
---|---|---|---|---|---|---|---|---
id_1 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_2 | 0.01±0.04 | 0.25±0.00 | 0.00±0.00 | 0.25±0.00 | 0.25±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_3 | 0.00±0.00 | 0.29±0.00 | 0.14±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_4 | 0.01±0.06 | 0.67±0.00 | 0.33±0.00 | 0.33±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_5 | 0.00±0.00 | 0.25±0.00 | 0.00±0.00 | 0.12±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_6 | 0.00±0.00 | 0.67±0.00 | 0.17±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_7 | 0.02±0.08 | 0.25±0.00 | 0.25±0.00 | 0.25±0.00 | 0.25±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_8 | 0.01±0.03 | 0.17±0.00 | 0.17±0.00 | 0.17±0.00 | 0.00±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_9 | 0.02±0.06 | 0.20±0.00 | 0.20±0.00 | 0.20±0.00 | 0.20±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_10 | 0.05±0.10 | 0.25±0.00 | 0.50±0.00 | 0.75±0.00 | 0.75±0.00 | 0.25±0.00 | 0.00±0.00 | 0.005±0.100
id_11 | 0.06±0.12 | 0.33±0.00 | 0.33±0.00 | 0.67±0.00 | 0.33±0.00 | 0.00±0.00 | 0.00±0.00 | 0.003±0.100
id_12 | 0.12±0.12 | 0.25±0.00 | 0.50±0.00 | 0.25±0.00 | 0.50±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_13 | 0.04±0.11 | 0.33±0.00 | 0.67±0.00 | 0.67±0.00 | 0.33±0.00 | 0.00±0.00 | 0.00±0.00 | 0.000±0.000
id_14 | 0.11±0.12 | 0.50±0.00 | 0.50±0.00 | 0.50±0.00 | 0.50±0.00 | 0.25±0.00 | 0.25±0.00 | 0.100±0.120
id_15 | 0.48±0.09 | 0.50±0.00 | 0.50±0.00 | 0.50±0.00 | 0.50±0.00 | 0.50±0.00 | 0.00±0.00 | 0.150±0.230
Overall | 0.06±0.14 | 0.33±0.18 | 0.28±0.21 | 0.31±0.24 | 0.24±0.23 | 0.07±0.14 | 0.02±0.06 | 0.020±0.090
Table 7: Benchmark of Sensitivity on different noise magnitudes. Smaller values are better. Bolds indicate the best methods in each dataset. Dataset | US | DS_0.0 | DS_0.25 | DS_0.5 | DS_0.75 | DS_1.0 | Coreset | BADGE
---|---|---|---|---|---|---|---|---
id_1 | 0.55±0.00 | 0.76±0.00 | 0.23±0.00 | 0.57±0.00 | 0.44±0.00 | 0.62±0.00 | 0.76±0.00 | 0.660±0.009
id_2 | 0.35±0.00 | 0.09±0.00 | 0.23±0.00 | 0.05±0.00 | 0.14±0.00 | 0.51±0.00 | 0.60±0.00 | 0.600±0.100
id_3 | 0.59±0.00 | 0.05±0.00 | 0.07±0.00 | 0.42±0.00 | 0.31±0.00 | 0.49±0.00 | 0.55±0.00 | 0.550±0.007
id_4 | 0.44±0.00 | 0.13±0.00 | 0.06±0.00 | 0.11±0.00 | 0.22±0.00 | 0.57±0.00 | 0.60±0.00 | 0.530±0.006
id_5 | 0.53±0.00 | 0.08±0.00 | 0.21±0.00 | 0.19±0.00 | 0.23±0.00 | 0.33±0.00 | 0.57±0.00 | 0.470±0.006
id_6 | 0.48±0.00 | 0.03±0.00 | 0.04±0.00 | 0.47±0.00 | 0.29±0.00 | 0.32±0.00 | 0.55±0.00 | 0.400±0.007
id_7 | 0.37±0.00 | 0.03±0.00 | 0.10±0.00 | 0.07±0.00 | 0.07±0.00 | 0.35±0.00 | 0.37±0.00 | 0.340±0.004
id_8 | 0.30±0.00 | 0.08±0.00 | 0.12±0.00 | 0.03±0.00 | 0.30±0.00 | 0.46±0.00 | 0.45±0.00 | 0.400±0.006
id_9 | 0.28±0.00 | 0.03±0.00 | 0.14±0.00 | 0.13±0.00 | 0.15±0.00 | 0.45±0.00 | 0.48±0.00 | 0.330±0.005
id_10 | 0.20±0.00 | 0.02±0.00 | 0.05±0.00 | 0.04±0.00 | 0.04±0.00 | 0.14±0.00 | 0.36±0.00 | 0.280±0.006
id_11 | 0.26±0.00 | 0.01±0.00 | 0.13±0.00 | 0.15±0.00 | 0.06±0.00 | 0.31±0.00 | 0.32±0.00 | 0.300±0.005
id_12 | 0.13±0.00 | 0.02±0.00 | 0.04±0.00 | 0.04±0.00 | 0.07±0.00 | 0.21±0.00 | 0.22±0.00 | 0.290±0.003
id_13 | 0.22±0.00 | 0.05±0.00 | 0.05±0.00 | 0.04±0.00 | 0.19±0.00 | 0.29±0.00 | 0.40±0.00 | 0.340±0.006
id_14 | 0.18±0.00 | 0.03±0.00 | 0.11±0.00 | 0.10±0.00 | 0.03±0.00 | 0.11±0.00 | 0.18±0.00 | 0.230±0.004
id_15 | 0.23±0.00 | 0.02±0.00 | 0.05±0.00 | 0.05±0.00 | 0.04±0.00 | 0.19±0.00 | 0.26±0.00 | 0.210±0.003
Overall | 0.34±0.14 | 0.10±0.18 | 0.11±0.07 | 0.16±0.17 | 0.17±0.12 | 0.36±0.15 | 0.44±0.16 | 0.400±0.150

US

DS_0.0

DS_0.25

DS_0.5

DS_0.75

DS_1.0

BADGE

Coreset

Figure A.4: The percentage of misclassified detected samples, the percentage
of detected patterns, and the percentage of queried samples along with queried
iterations in dataset id_10

###  A.4 Analysis of sampling complexity

Each iteration in our framework consists of two main phases. The first phase
determines which samples to be labeled next, the most costly computation in
this phase is the matrix inversion and computing matrix determinant. The
maximum size of the matrix is $N$, so the time complexity is $O(N^{3})$. If we
use the optimized CW-like algorithm for matrix inversion, then the complexity
can be as low as $O(N^{2.373})$. The second phase includes updating
information and confirming detected failure modes. Updating information
involves matrix inversions and multiplications, with cost $O(N^{2.373})$. A
low-cost Depth First Search is implemented to check detected failure modes,
which costs $O(N)$. In conclusion, the cost of an iteration is $O(N^{2.373})$.

###  A.5 Principal hyper-parameters AND user-defined hyper-parameters

Our proposed framework is applied to human-machine cooperation systems.
Therefore, some terms depend on the user such as the failure mode definition
which is defined by two factors: (i) how to determine whether two samples have
a common concept; (ii) what the structure of a failure pattern is. In our
experiments, we consider the case that the user defines an edge (common
concept) by using the mutual $k_{nn}$-graph under the Euclidean distance on
the embedding space. The connectivity criterion is maximally connected
subgraphs (a.k.a. connected components). With this indication, the user also
provides two hyper-parameters $k_{nn}$ and $M$. The meaning of $k_{nn}$ and
$M$ are mentioned in Appendix A.2. From the algorithmic viewpoint, our
approach depends mainly on one main hyper-parameter $\vartheta$. The parameter
$\vartheta$ regulates the exploration-exploitation trade-off in the sampling
procedure ($\vartheta=0$ means pure exploitation, $\vartheta=1$ means pure
exploration). We experimented with five values of $\vartheta$ throughout the
paper.

##  Appendix B Proofs

###  B.1 Proofs of Proposition 6.1

###### Proof of Proposition 6.1.

We first show that the value of $\delta$ should be upper-bounded by
$\sqrt{N-1}$. To see this, note that $K(h_{\mathcal{X}},h_{\mathcal{Y}})$ is a
Gram matrix, so its diagonal elements are all ones, and the off-diagonal
elements are in the range $(0,1]$. We have an upper bound that:

$\|K(h_{\mathcal{X}},h_{\mathcal{Y}})-I_{N}\|_{F}\leq\sqrt{N(N-1)}.$

To ensure the existence of $h_{\mathcal{X}},h_{\mathcal{Y}}$, the value of
$\delta$ must fulfill:

$\delta\|I_{N}\|_{F}<\sqrt{N(N-1)}\implies\delta<\sqrt{N-1}.$

Next, we show that condition for $h_{\mathcal{X}}$ and $h_{\mathcal{Y}}$.
Squaring both sides of (8) gives

$\|K(h_{\mathcal{X}},h_{\mathcal{Y}})-I_{N}\|_{F}^{2}\geq\delta^{2}\|I_{N}\|_{F}^{2}=\delta^{2}N.$

Because the diagonal elements of $K(h_{\mathcal{X}},h_{\mathcal{Y}})$ are all
ones, the above condition is equivalent to

$\displaystyle\sum_{i>j}\exp\big{(}-\frac{\|x_{i}-x_{j}\|_{2}^{2}}{h_{\mathcal{X}}^{2}}-\frac{\|\widehat{\mu}_{\hat{y}_{i}}-\widehat{\mu}_{\hat{y}_{j}}\|_{2}^{2}+\|\widehat{\Sigma}_{\hat{y}_{i}}-\widehat{\Sigma}_{\hat{y}_{j}}\|_{F}^{2}}{h_{\mathcal{Y}}^{2}}\big{)}\geq\frac{\delta^{2}N}{2}.$
(9)

Using Jensen inequality for the exponential function, which is convex, we have
the following lower bound:

$\displaystyle\frac{1}{{N\choose
2}}\sum_{i>j}\exp\big{(}-\frac{\|x_{i}-x_{j}\|_{2}^{2}}{h_{\mathcal{X}}^{2}}-\frac{\|\widehat{\mu}_{\hat{y_{i}}}-\widehat{\mu}_{\hat{y_{j}}}\|_{2}^{2}+\|\widehat{\Sigma}_{\hat{y_{i}}}-\widehat{\Sigma}_{\hat{y_{j}}}\|_{F}^{2}}{h_{\mathcal{Y}}^{2}}\big{)}$
$\displaystyle\qquad\geq\exp\big{(}-\frac{\sum_{i>j}\|x_{i}-x_{j}\|_{2}^{2}}{h_{\mathcal{X}}^{2}{N\choose
2}}-\frac{\sum_{i>j}\|\widehat{\mu}_{\hat{y}_{i}}-\widehat{\mu}_{\hat{y}_{j}}\|_{2}^{2}+\|\widehat{\Sigma}_{\hat{y}_{i}}-\widehat{\Sigma}_{\hat{y}_{j}}\|_{F}^{2}}{h_{\mathcal{Y}}^{2}{N\choose
2}}\big{)}.$

Therefore, if $h_{\mathcal{X}}$ and $h_{\mathcal{Y}}$ satisfy

$\displaystyle\exp\big{(}-\frac{\sum{i>j}\|x_{i}-x_{j}\|_{2}^{2}}{h_{\mathcal{X}}^{2}{N\choose
2}}-\frac{\sum_{i>j}\|\widehat{\mu}_{\hat{y}_{i}}-\widehat{\mu}_{\hat{y}_{j}}\|_{2}^{2}+\|\widehat{\Sigma}_{\hat{y}_{i}}\widehat{\Sigma}_{\hat{y}_{j}}\|_{F}^{2}}{h_{\mathcal{Y}}^{2}{N\choose
2}}\big{)}\geq\frac{\delta^{2}}{N-1},$

then they also satisfy the condition (9). Defining the quantities
$D_{\mathcal{X}}$ and $D_{\mathcal{Y}}$ as in statement of the proposition, we
find that $h_{\mathcal{X}}$ and $h_{\mathcal{Y}}$ should satisfy

$\Leftrightarrow\frac{D_{\mathcal{X}}}{h_{\mathcal{X}}^{2}}+\frac{D_{\mathcal{Y}}}{h_{\mathcal{Y}}^{2}}\leq\ln{\frac{N-1}{\delta^{2}}}.$

This completes the proof. ∎

###  B.2 Taylor Expansion for Value-of-Interest VoI

We first use a second-order Taylor expansion to approximate
$f(X)=\mathrm{VoI}(X)=(1+\exp(-g(X))^{-1}$ around the point $X=\mu$:

$\displaystyle f(X)$ $\displaystyle=f(\mu)+(X-\mu)^{\top}\nabla
f(\mu)+\frac{1}{2}(X-\mu)^{\top}\nabla^{2}f(\mu)(X-\mu)+\mathcal{O}(\|\Delta_{X}\|^{3})$
$\displaystyle=f(\mu)+(X-\mu)^{\top}\nabla
f(\mu)+\frac{1}{2}\mathrm{Tr}[\nabla^{2}f(\mu)(X-\mu)(X-\mu)^{\top}]+\mathcal{O}(\|\Delta_{X}\|^{3}).$

Moreover, we set $\mu$ as the expected value $\mathds{E}[X]$, and taking
expectations on both sides of the above equation gives

$\displaystyle\mathds{E}[f(X)]$
$\displaystyle=\mathds{E}\big{[}f(\mu)\big{]}+\mathds{E}\big{[}(X-\mu)^{\top}\nabla
f(\mu)\big{]}+\frac{1}{2}\mathds{E}\big{[}\mathrm{Tr}[\nabla^{2}f(\mu)(X-\mu)(X-\mu)^{\top}]\big{]}+\mathcal{O}(\|\Delta\|^{3})$
$\displaystyle=f(\mu)+\frac{1}{2}\Sigma_{t,i}^{*}\nabla^{2}f(\mu)+\mathcal{O}(\|\Delta\|^{3}),$

where the second equality follows from the relationship

$\mathds{E}\big{[}(X-\mu)^{\top}\nabla
f(\mu)\big{]}=\mathds{E}\big{[}(X-\mu)\big{]}^{\top}\nabla
f(\mu)=(\mathds{E}[X]-\mu)]^{\top}\nabla f(\mu)=0,$

and from the definition of the covariance matrix

$\mathds{E}\big{[}(X-\mu)(X-\mu)^{\top}\big{]}=\Sigma_{t,i}^{*}.$

It now suffices to verify the expressions for $\alpha_{i}$ and $\beta_{i}$.
Note that $\alpha_{i}=f(\mu)=(1+\exp(-\mu))^{-1}$ and $\beta_{i}$ is the
second-order derivative

$\displaystyle\beta_{i}$
$\displaystyle=\nabla^{2}f(\mu)=\alpha_{i}(1-\alpha_{i})(1-2\alpha_{i}),$

where the second equality follows from the property of the sigmoid function.

##  Appendix C SOCIAL IMPACT

One important social impact of this research lies in its potential to improve
the accuracy and reliability of machine learning classifiers. By identifying
misclassification patterns, the framework enables the refinement and
improvement of classifiers, reducing the likelihood of wrong predictions in
various domains. This can have wide-ranging implications, such as improving
the performance of automated systems in critical areas where accurate
classification is of utmost importance like healthcare diagnosis [Shaban-Nejad
et al., 2021, Rudin and Ustun, 2018, Albahri et al., 2023], or autonomous
vehicles [Glomsrud et al., 2019, Wagner and Koopman, 2015].

Another significant social impact of this research is its potential to address
biases and fairness issues in machine learning systems [Caton and Haas, 2020,
Mehrabi et al., 2021, Pessach and Shmueli, 2022]. By identifying
misclassification patterns, the framework can shed light on potential biases
in the data or algorithmic models. This knowledge is crucial for developing
fairer and more equitable machine learning systems which are obligatory for
bringing machine learning models to practical implementations.

Moreover, the collaborative nature of the framework promotes human-machine
interaction, fostering a symbiotic relationship that combines human expertise
and algorithmic capabilities. This approach not only empowers human annotators
by involving them in the decision-making process but also allows them to
contribute their domain knowledge and intuition [Wu et al., 2022, Xin et al.,
2018].