# A Holistic Approach to Unifying Automatic Concept Extraction and Concept
Importance Estimation

Thomas Fel⋆,1,2, Victor Boutin⋆1,2,
Mazda Moayeri3, Rémi Cadène1, Louis Bethune2 Léo Andéol2, Mathieu
Chalvidal1,2,
Thomas Serre1,2
1Carney Institute for Brain Science, Brown University
2Artificial and Natural Intelligence Toulouse Institute
3Department of Computer Science, University of Maryland
<EMAIL_ADDRESS>
###### Abstract

In recent years, concept-based approaches have emerged as some of the most
promising explainability methods to help us interpret the decisions of
Artificial Neural Networks (ANNs). These methods seek to discover intelligible
visual “concepts” buried within the complex patterns of ANN activations in two
key steps: (1) concept extraction followed by (2) importance estimation. While
these two steps are shared across methods, they all differ in their specific
implementations. Here, we introduce a unifying theoretical framework that
comprehensively defines and clarifies these two steps. This framework offers
several advantages as it allows us: (i) to propose new evaluation metrics for
comparing different concept extraction approaches; (ii) to leverage modern
attribution methods and evaluation metrics to extend and systematically
evaluate state-of-the-art concept-based approaches and importance estimation
techniques; (iii) to derive theoretical guarantees regarding the optimality of
such methods.

We further leverage our framework to try to tackle a crucial question in
explainability: how to efficiently identify clusters of data points that are
classified based on a similar shared strategy. To illustrate these findings
and to highlight the main strategies of a model, we introduce a visual
representation called the strategic cluster graph. Finally, we present Lens, a
dedicated website that offers a complete compilation of these visualizations
for all classes of the ImageNet dataset.

00footnotetext: $\star$ The authors contributed equally.

##  1 Introduction

The black-box nature of Artificial Neural Networks (ANNs) poses a significant
hurdle to their deployment in industries that must comply with stringent
ethical and regulatory standards [1]. In response to this challenge,
eXplainable Artificial Intelligence (XAI) focuses on developing new tools to
help humans better understand how ANNs arrive at their decisions [2, 3]. Among
the large array of methods available, attribution methods have become the go-
to approaches [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]. They yield heatmaps in
order to highlight the importance of each input feature (or group of features
[15]) for driving a model’s decision. However, there is growing consensus that
these attribution methods fall short of providing meaningful explanations [16,
17, 18, 19] as revealed by multiple user studies [20, 21, 22, 23, 24, 25, 20].
It has been suggested that for explainability methods to become usable by
human users, they need to be able to highlight not just the location of
important features within an image (i.e., the where information) but also
their semantic content (i.e., the what information).

One promising set of explainability methods to address this challenge includes
concept-based explainability methods, which are methods that aim to identify
high-level concepts within the activation space of ANNs [26]. These methods
have recently gained renewed interest due to their success in providing human-
interpretable explanations [27, 28, 29, 30] (see section 2 for a detailed
description of the related work). However, concept-based explainability
methods are still in the early stage, and progress relies largely on
researchers’ intuitions rather than well-established theoretical foundations.
A key challenge lies in formalizing the notion of concept itself [31].
Researchers have proposed desiderata such as meaningfulness, coherence, and
importance [27] but the lack of formalism in concept definition has hindered
the derivation of appropriate metrics for comparing different methods.

This article presents a theoretical framework to unify and characterize
current concept-based explainability methods. Our approach builds on the
fundamental observation that all concept-based explainability methods share
two key steps: (1) concepts are extracted, and (2) importance scores are
assigned to these concepts based on their contribution to the model’s decision
[27]. Here, we show how the first extraction step can be formulated as a
dictionary learning problem while the second importance scoring step can be
formulated as an attribution problem in the concept space. To summarize, our
contributions are as follows:

  * •

We describe a novel framework that unifies all modern concept-based
explainability methods and we borrow metrics from different fields (such as
sparsity, reconstruction, stability, FID, or OOD scores) to evaluate the
effectiveness of those methods.

  * •

We leverage modern attribution methods to derive seven novel concept
importance estimation methods and provide theoretical guarantees regarding
their optimality. Additionally, we show how standard faithfulness evaluation
metrics used to evaluate attribution methods (i.e., Insertion, Deletion [32],
and $\mu$Fidelity [33]) can be adapted to serve as benchmarks for concept
importance scoring. In particular, we demonstrate that Integrated Gradients,
Gradient Input, RISE, and Occlusion achieve the highest theoretical scores for
3 faithfulness metrics when the concept decomposition is on the penultimate
layer.

  * •

We introduce the notion of local concept importance to address a significant
challenge in explainability: the identification of image clusters that reflect
a shared strategy by the model (see Figure 1). We show how the corresponding
cluster plots can be used as visualization tools to help with the
identification of the main visual strategies used by a model to help explain
false positive classifications.

Figure 1: Strategic cluster graphs for the espresso and zucchini classes. The
framework presented in this study provides a comprehensive approach to uncover
local importance using any attribution methods. Consequently, it allow us to
estimate the critical concepts influencing the model’s decision for each
image. As a results, we introduced the Strategic cluster graph, which offers a
visual representation of the main strategies employed by the model in
recognizing an entire object class. For espresso (left), the main strategies
for classification appear to be: $\bullet$ bubbles and foam on the coffee,
$\bullet$ Latte art, $\bullet$ transparent cups with foam and black liquid,
$\bullet$ the handle of the coffee cup, and finally $\bullet$ the coffee in
the cup, which appears to be the predominant strategy. As for zucchini, the
strategies are: $\bullet$ a zucchini in a vegetable garden, $\bullet$ the
corolla of the zucchini flower, $\bullet$ sliced zucchini, $\bullet$ the
spotted pattern on the zucchini skin and $\bullet$ stacked zucchini.

##  2 Related Work

Kim et al. [26] were the first to propose a concept-based approach to
interpret neural network internal states. They defined the notion of concepts
using Concept Activation Vectors (CAVs). CAVs are derived by training a linear
classifier between a concept’s examples and random counterexamples and then
taking the vector orthogonal to the decision boundary. In their work, the
concepts are manually selected by humans. They further introduce the first
concept importance scoring method, called Testing with CAVs (TCAV). TCAV uses
directional derivatives to evaluate the contribution of each CAV to the
model’s prediction for each object category. Although this approach
demonstrates meaningful explanations to human users, it requires a significant
human effort to create a relevant image database of concepts. To address this
limitation, Ghorbani et al. [27] developed an unsupervised method called
Automatic Concept Extraction (ACE) that extracts CAVs without the need for
human supervision. In their work, the CAVs are the centroid of the activations
(in a given layer) when the network is fed with multi-scale image segments
belonging to an image class of interest. However, the use of image segments
could introduce biases in the explanations [34, 35, 36, 37]. ACE also
leverages TCAV to rank the concepts of a given object category based on their
importance.

Zhang et al. [28] proposed a novel method for concept-based explainability
called Invertible Concept-based Explanation (ICE). ICE leverages matrix
factorization techniques, such as non-negative matrix factorization (NMF), to
extract Concept Activation Vectors (CAVs). Here, the concepts are localized as
the matrix factorization is applied on feature maps (before the global average
pooling). In ICE, the concepts’ importance is computed using the TCAV score
[26]. Note that the Singular Value Decomposition (SVD) was also suggested as a
concept discovery method [28, 30]. CRAFT (Concept Recursive Activation
FacTorization for explainability) uses NMF to extract the concepts, but as it
is applied after the global pooling average, the concepts are location
invariant. Additionally, CRAFT employs Sobol indices to quantify the global
importance of concepts associated with an object category.

##  3 A Unifying perspective

#### Notations.

Throughout, $||\cdot||_{2}$ and $||\cdot||_{F}$ represent the $\ell_{2}$ and
Frobenius norm, respectively. We consider a general supervised learning
setting, where a classifier $\bm{f}:\mathcal{X}\to\mathcal{Y}$ maps inputs
from an input space $\mathcal{X}\subseteq\mathbb{R}^{d}$ to an output space
$\mathcal{Y}\subseteq\mathbb{R}^{c}$. For any matrix
$\mathbf{X}\in\mathbb{R}^{n\times d}$, $\bm{x}_{i}$ denotes the $i^{th}$ row
of $\mathbf{X}$, where $i\in\\{1,\ldots,n\\}$ and
$\bm{x}_{i}\in\mathbb{R}^{d}$. Without loss of generality, we assume that
$\bm{f}$ admits an intermediate space $\mathcal{H}\subseteq\mathbb{R}^{p}$. In
this setup, $\bm{h}:\mathcal{X}\to\mathcal{H}$ maps inputs to the intermediate
space, and $\bm{g}:\mathcal{H}\to\mathcal{Y}$ takes the intermediate space to
the output. Consequently, $\bm{f}(\bm{x})=(\bm{g}\circ\bm{h})(\bm{x})$.
Additionally, let $\bm{a}=\bm{h}(\bm{x})\in\mathcal{H}$ represent the
activations of $\bm{x}$ in this intermediate space. We also abuse notation
slightly: $\bm{f}(\mathbf{X})=(\bm{g}\circ\bm{h})(\mathbf{X})$ denotes the
vectorized application of $\bm{f}$ on each element $\bm{x}$ of $\mathbf{X}$,
resulting in $(\bm{f}(\bm{x}_{1}),\ldots,\bm{f}(\bm{x}_{n}))$.

Prior methods for concept extraction [27], namely ACE, ICE [28] and CRAFT
[29], can be distilled into two fundamental steps:

  1. (i)

Concept extraction: A set of images $\mathbf{X}\in\mathbb{R}^{n\times d}$
belonging to the same class is sent to the intermediate space giving
activations $\mathbf{A}=\bm{h}(\mathbf{X})\in\mathbb{R}^{n\times p}$. These
activations are used to extract a set of $k$ CAVs using K-Means [27], PCA (or
SVD) [28, 30] or NMF [28, 29]. Each CAV is denoted $\bm{v}_{i}$ and
$\mathbf{V}=(\bm{v}_{1},\ldots,\bm{v}_{k})\in\mathbb{R}^{p\times k}$ forms the
dictionary of concepts.

  2. (ii)

Concept importance scoring: It involves calculating a set of $k$ global
scores, which provides an importance measure of each concept $\bm{v}_{i}$ to
the class as a whole. Specifically, it quantifies the influence of each
concept $\bm{v}_{i}$ on the final classifier prediction for the given set of
points $\mathbf{X}$. Prominent measures for concept importance include TCAV
[26] and the Sobol indices [29].

The two-step process described above is repeated for all classes. In the
following subsections, we theoretically demonstrate that the concept
extraction step (i) could be recast as a dictionary learning problem (see
3.1). It allows us to reformulate and generalize the concept importance step
(ii) using attribution methods (see 3.2).

###  3.1 Concept Extraction

#### A dictionary learning perspective.

The purpose of this section is to redefine all current concept extraction
methods as a problem within the framework of dictionary learning. Given the
necessity for clearer formalization and metrics in the field of concept
extraction, integrating concept extraction with dictionary learning enables us
to employ a comprehensive set of metrics and obtain valuable theoretical
insights from a well-established and extensively researched domain.

The goal of concept extraction is to find a small set of interpretable CAVs
(i.e., $\mathbf{V}$) that allows us to faithfully interpret the activation
$\mathbf{A}$. By preserving a linear relationship between $\mathbf{V}$ and
$\mathbf{A}$, we facilitate the understanding and interpretability of the
learned concepts [26, 38]. Therefore, we look for a coefficient matrix
$\mathbf{U}\in\mathbb{R}^{n\times k}$ (also called loading matrix) and a set
of CAVs $\mathbf{V}$, so that
$\mathbf{A}\approx\mathbf{U}\mathbf{V}^{\mathsf{T}}$. In this approximation of
$\mathbf{A}$ using the two low-rank matrices $(\mathbf{U},\mathbf{V})$,
$\mathbf{V}$ represents the concept basis used to reinterpret our samples, and
$\mathbf{U}$ are the coordinates of the activation in this new basis.
Interestingly, such a formulation allows a recast of the concept extraction
problem as an instance of dictionary learning problem [39] in which all known
concept-based explainability methods fall:

$\displaystyle(\mathbf{U}^{\star},\mathbf{V}^{\star})=\operatorname*{arg\,min}_{\mathbf{U},\mathbf{V}}||\mathbf{A}-\mathbf{U}\mathbf{V}^{\mathsf{T}}||^{2}_{F}~{}~{}s.t~{}~{}$
$\displaystyle\forall~{}i,\bm{u}_{i}\in\\{\mathbf{e}_{1},\ldots,\mathbf{e}_{k}\\}~{}~{}\text{(K-Means
:
{{\color[rgb]{0.12109375,0.12109375,0.390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.12109375,0.390625}ACE}}~{}\cite[cite]{[\@@bibref{Number}{ghorbani2019towards}{}{}]})},$
(1)
$\displaystyle(\mathbf{U}^{\star},\mathbf{V}^{\star})=\operatorname*{arg\,min}_{\mathbf{U},\mathbf{V}}||\mathbf{A}-\mathbf{U}\mathbf{V}^{\mathsf{T}}||^{2}_{F}~{}~{}s.t~{}~{}$
$\displaystyle\mathbf{U}^{\mathsf{T}}\mathbf{U}=\mathbf{V}^{\mathsf{T}}\mathbf{V}=\mathbf{I}~{}~{}~{}\text{(PCA:~{}\cite[cite]{[\@@bibref{Number}{zhang2021invertible,
graziani2023concept}{}{}]})},$ (2)
$\displaystyle(\mathbf{U}^{\star},\mathbf{V}^{\star})=\operatorname*{arg\,min}_{\mathbf{U},\mathbf{V}}||\mathbf{A}-\mathbf{U}\mathbf{V}^{\mathsf{T}}||^{2}_{F}~{}~{}s.t~{}~{}$
$\displaystyle\mathbf{U}\geq 0,\mathbf{V}\geq 0~{}~{}~{}\text{(NMF :
{{\color[rgb]{0.390625,0.12109375,0.12109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.12109375,0.12109375}CRAFT}}~{}\cite[cite]{[\@@bibref{Number}{fel2023craft}{}{}]}~{}\&
{{\color[rgb]{0.12109375,0.390625,0.12109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.390625,0.12109375}ICE}}~{}\cite[cite]{[\@@bibref{Number}{zhang2021invertible}{}{}]})
}$ (3)

with $\bm{e}_{i}$ the $i$-th element of the canonical basis, $\mathbf{I}$ the
identity matrix. In this context, $\mathbf{V}$ is the _dictionary_ and
$\mathbf{U}$ the _representation_ of $\mathbf{A}$ with the atoms of
$\mathbf{V}$. $\bm{u}_{i}$ denote the $i$-th row of $\mathbf{U}$. These three
methods extract the concept banks $\mathbf{V}$ differently, thereby
necessitating different interpretations.

In ACE, the CAVs are defined as the centroids of the clusters found by the
K-means algorithm. Specifically, a concept vector $\bm{v}_{i}$ in the matrix
$\mathbf{V}$ indicates a dense concentration of points associated with the
corresponding concept, implying a repeated activation pattern. The main
benefit of ACE comes from its reconstruction process, involving projecting
activations onto the nearest centroid, which ensures that the representation
will lie within the observed distribution (no out-of-distribution instances).
However, its limitation lies in its lack of expressivity, as each activation
representation is restricted to a single concept ($||\bm{u}||_{0}=1$). As a
result, it cannot capture compositions of concepts, leading to sub-optimal
representations that fail to fully grasp the richness of the underlying data
distribution.

On the other hand, the PCA benefits from superior reconstruction performance
due to its lower constraints, as stated by the Eckart-Young-Mirsky[40]
theorem. In PCA, the CAVs are the eigenvector of the covariance matrix: they
indicate the direction in which the data variance is maximal. An inherent
limitation is that the PCA will not be able to properly capture stable
concepts that do not contribute to the sample variability (e.g. the dog-head
concept might not be considered important by the PCA to explain the dog class
if it is present across all examples). Neural networks are known to cluster
together the points belonging to the same category in the last layer to
achieve linear separability ([41, 29]). Thus, the orthogonality constraint in
the PCA might not be suitable to correctly interpret the manifold of the deep
layer induced by points from the same class (it is interesting to note that
this limitation can be of interest when studying all classes at once). Also,
unlike K-means, which produces strictly positive clusters if all points are
positive (e.g., the output of ReLU), PCA has no sign constraint and can
undesirably reconstruct out-of-distribution (OOD) activations, including
negative values after ReLU.

In contrast to K-Means, which induces extremely sparse representations, and
PCA, which generates dense representations, the NMF (used in CRAFT and ICE)
strikes an harmonious balance as it provides moderately sparse representation.
This is due to NMF relaxing the constraints imposed by the K-means algorithm
(adding an orthogonality constraint on $\mathbf{V}$ such that
$\mathbf{V}\mathbf{V}^{\mathsf{T}}=\mathbf{I}$ would yield an equivalent
solution to K-means clustering [42]). This sparsity facilitates the encoding
of compositional representations that are particularly valuable when an image
encompasses multiple concepts. Moreover, by allowing only additive linear
combinations of components with non-negative coefficients, NMF inherently
fosters a parts-based representation. This distinguishes NMF from PCA, which
offers a holistic representation model. Interestingly, the NMF is known to
yield representations that are interpretable by humans [28, 29]. Finally, the
non-orthogonality of these concepts presents an advantage as it accommodates
the phenomenon of superposition [38], wherein neurons within a layer may
contribute to multiple distinct concepts simultaneously.

To summarize, we have explored three approaches to concept extraction, each
necessitating a unique interpretation of the resulting Concept Activation
Vectors (CAVs). Among these methods, NMF (used in CRAFTand ICE) emerges as a
promising middle ground between PCA and K-means. Leveraging its capacity to
capture intricate patterns, along with its ability to facilitate compositional
representations and intuitive parts-based interpretations, NMF stands out as a
compelling choice for extracting meaningful concepts from high-dimensional
data. These advantages have been underscored by previous human studies, as
evidenced by works such as Zhang et al.[28] and Fel et al.[29].

| Relative $\ell_{2}$ ($\downarrow$) | Sparsity ($\uparrow$) | Stability ($\downarrow$) | FID ($\downarrow$) | OOD ($\downarrow$)
---|---|---|---|---|---
| Eff / R50 / Mob | Eff / R50 / Mob | Eff / R50 / Mob | Eff / R50 / Mob | Eff / R50 / Mob
PCA | 0.60 / 0.54 / 0.73 | 0.00 / 0.00 / 0.0 | 0.41 / 0.38 / 0.43 | 0.47 / 0.17 / 0.24 | 2.44 / 0.36 / 0.16
KMeans | 0.72 / 0.66 / 0.84 | 0.95 / 0.95 / 0.95 | 0.07 / 0.08 / 0.04 | 0.46 / 0.21 / 0.33 | 1.76 / 0.29 / 0.15
NMF | 0.63 / 0.57 / 0.75 | 0.68 / 0.44 / 0.64 | 0.17 / 0.14 / 0.16 | 0.38 / 0.21 / 0.24 | 1.98 / 0.29 / 0.15

Table 1: Concept extraction comparison. Eff, R50 and Mob denote
EfficientNetV2[43], ResNet50[44], MobileNetV2[45]. The concept extraction
methods are applied on the last layer of the networks. Each results is
averaged across 10 classes of ImageNet and obtained from a set of 16k images
for each class.

#### Evaluation of concept extraction

Following the theoretical discussion of the various concept extraction
methods, we conduct an empirical investigation of the previously discussed
properties to gain deeper insights into their distinctions and advantages. In
our experiment, we apply the PCA, K-Means, and NMF concept extraction methods
on the penultimate layer of three state-of-the-art models. We subsequently
evaluate the concepts using five different metrics (see Table 1). All five
metrics are connected with a desired characteristics of a dictionary learning
method. They include achieving a high-quality reconstruction (Relative l2),
sparse encoding of concepts (Sparsity), ensuring the stability of the concept
base in relation to $\mathbf{A}$ (Stability), performing reconstructions
within the intended domain (avoiding OOD), and maintaining the overall
distribution during the reconstruction process (FID). All the results come
from 10 classes of ImageNet (the one used in Imagenette [46]), and are
obtained using $n=16k$ images for each class.

We begin our empirical investigation by using a set of standard metrics
derived from the dictionary learning literature, namely Relative $l_{2}$ and
Sparsity. Concerning the Relative $\ell_{2}$, PCA achieves the highest score
among the three considered methods, confirming the theoretical expectations
based on the Eckart–Young–Mirsky theorem [40], followed by NMF. Concerning the
sparsity of the underlying representation $\bm{u}$, we compute the proportion
of non-zero elements $||\bm{u}||_{0}/k$. Since K-means inherently has a
sparsity of $1/k$ (as induced by equation 1), it naturally performs better in
terms of sparsity, followed by NMF.

We deepen our investigation by proposing three additional metrics that offer
complementary insights on the extracted concepts. Those metrics are the
Stability, the FID, and the OOD score. The Stability (as it can be seen as a
loose approximation of algorithmic stability [47]) measures how consistent
concepts remain when they are extracted from different subsets of the data. To
evaluate Stability, we perform the concept extraction methods $N$ times on
$K$-fold subsets of the data. Then, we map the extracted concepts together
using a Hungarian loss function and measure the cosine similarity of the CAVs.
If a method is stable, it should yield the same concepts (up to permutation)
across each $K$-fold, where each fold consists of $1000$ images. K-Means and
NMF demonstrate the highest stability, while PCA appears to be highly
unstable, which can be problematic for interpreting the results and may
undermine confidence in the extracted concepts.

The last two metrics, FID and OOD, are complementary in that they measure: (i)
how faithful the representations extracted are w.r.t the original
distribution, and (ii) the ability of the method to generate points lying in
the data distribution (non-OOD). Formally, the FID quantifies the
1-Wasserstein distance [48] $\mathcal{W}_{1}$ between the empirical
distribution of activation $\mathbf{A}$, denoted $\mu_{\bm{a}}$, and the
empirical distribution of the reconstructed activation
$\mathbf{U}\mathbf{V}^{\mathsf{T}}$ denoted $\mu_{\bm{u}}$. Thus, FID is
calculated as $\text{FID}=\mathcal{W}_{1}(\mu_{\bm{a}},\mu_{\bm{u}})$. On the
other hand, the OOD score measures the plausibility of the reconstruction by
leveraging Deep-KNN [49], a recent state-of-the-art OOD metric. More
specifically, we use the Deep-KNN score to evaluate the deviation of a
reconstructed point from the closest original point. In summary, a good
reconstruction method is capable of accurately representing the original
distribution (as indicated by FID) while ensuring that the generated points
remain within the model’s domain (non-OOD). K-means leads to the best OOD
scores because each instance is reconstructed as a centroid, resulting in
proximity to in-distribution (ID) instances. However, this approach collapses
the distribution to a limited set of points, resulting in low FID. On the
other hand, PCA may suffer from mapping to negative values, which can
adversely affect the OOD score. Nevertheless, PCA is specifically optimized to
achieve the best average reconstructions. NMF, with fewer stringent
constraints, strikes a balance by providing in-distribution reconstructions at
both the sample and population levels.

In conclusion, the results clearly demonstrate NMF as a method that strikes a
balance between the two approaches as NMF demonstrates promising performance
across all tested metrics. Henceforth, we will use the NMF to extract concepts
without mentioning it.

#### The Last Layer as a Promising Direction

The various methods examined, namely ACE, ICE, and CRAFT, generally rely on a
deep layer to perform their decomposition without providing quantitative or
theoretical justifications for their choice To explore the validity of this
choice, we apply the aforementioned metrics to each block’s output in a
ResNet50 model. Figure 2 illustrates the metric evolution across different
blocks, revealing a trend that favors the last layer for the decomposition.
This empirical finding aligns with the practical implementations discussed
above.

Figure 2: Concept extraction metrics across layers. The concept extraction
methods are applied on activations probed on different blocks of a ResNet50
(B2 to B5). Each point is averaged over 10 classes of ImageNet using $16$k
images for each class. We evaluate $3$ concept extraction methods: PCA ( ),
NMF ( ) and KMeans ( ).

###  3.2 Concept importance

In this section, we leverage our framework to unify concept importance scoring
using the existing attribution methods. Furthermore, we demonstrate that
specifically in the case of decomposition in the penultimate layer, it exists
optimal methods for importance estimation, namely RISE [32], Integrated
Gradients [7], Gradient-Input [6], and Occlusion [13]. We provide theoretical
evidence to support the optimality of these methods.

#### From concept importance to attribution methods

The dictionary learning formulation allows us to define the concepts
$\mathbf{V}$ in such a way that they are optimal to reconstruct the
activation, i.e., $\mathbf{A}\approx\mathbf{U}\mathbf{V}^{\mathsf{T}}$.
Nevertheless, this does not guarantee that those concepts are important for
the model’s prediction. For example, the “grass” concept might be important to
characterize the activations of a neural network when presented with a St-
Bernard image, but it might not be crucial for the network to classify the
same image as a St Bernard [26, 16, 50]. The notion of concept importance is
precisely introduced to avoid such a confirmation bias and to identify the
concepts used to classify among all detected concepts.

Figure 3: C-Deletion, C-Insertion curves. Fidelity curves for C-Deletion
depict the model’s score as the most important concepts are removed. The
results are averaged across 10 classes of ImageNet using a ResNet50 model.

We use the notion of Concept ATtribution methods (which we denote as _CAT_ s)
to assess the concept importance score. The CATs are a generalization of the
attribution methods: while attribution methods assess the sensitivity of the
model output to a change in the pixel space, the concept importance evaluates
the sensitivity to a change in the concept space. To compute the CATs methods,
it is necessary to link the activation $\bm{a}\in\mathbb{R}^{p}$ to the
concept base $\mathbf{V}$ and the model prediction $\bm{y}$. To do so, we feed
the second part of the network ($\bm{g}$) with the activation reconstruction
($\bm{u}\mathbf{V}^{\mathsf{T}}\approx\bm{a}$), so that
$\bm{y}=\bm{g}(\bm{u}\mathbf{V}^{\mathsf{T}})$. Intuitively, a CAT method
quantifies how a variation of $\bm{u}$ will impact $\bm{y}$. We denote
$\bm{\varphi}_{i}(\bm{u})$ the $i$-th coordinate of $\bm{\varphi}(\bm{u})$, so
that it represents the importance of the $i$-th concept in the representation
$\bm{u}$. Equipped with these notations, we can leverage the sensitivity
metrics introduced in standard attribution methods to re-define the current
measures of concept importance, as well as introduce the new CATs borrowed
from the attribution methods literature:

$\displaystyle\nabla_{\bm{u}_{i}}\bm{g}(\bm{u}\mathbf{V}^{\mathsf{T}})\qquad\qquad\qquad\qquad\qquad\qquad~{}~{}~{}~{}~{}~{}\text{(used
in TCAV:
{{\color[rgb]{0.12109375,0.12109375,0.390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.12109375,0.390625}ACE}},
{{\color[rgb]{0.12109375,0.390625,0.12109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.12109375,0.390625,0.12109375}ICE}})},$
(4) $\displaystyle\displaystyle\frac{\mathbb{E}_{\mathbf{m}_{\sim
i}}(\mathbb{V}_{\mathbf{m}}(\bm{g}((\bm{u}\odot\mathbf{m})\mathbf{V}^{\mathsf{T}})|\mathbf{m}_{\sim
i}))}{\mathbb{V}(\bm{g}((\bm{u}\odot\mathbf{m})\mathbf{V}^{\mathsf{T}}))}\qquad\qquad\qquad\qquad~{}~{}\text{(Sobol
:
{{\color[rgb]{0.390625,0.12109375,0.12109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.12109375,0.12109375}CRAFT}}),}$
(5)
$\displaystyle(\bm{u}_{i}-\bm{u}_{i}^{\prime})\times\int_{0}^{1}\nabla_{\bm{u}_{i}}\bm{g}((\bm{u}^{\prime}\alpha+(1-\alpha)(\bm{u}-\bm{u}^{\prime}))\mathbf{V}^{\mathsf{T}})d\alpha\qquad\text{Int.Gradients},$
(6)
$\displaystyle\displaystyle\underset{\bm{\delta}\sim\mathcal{N}(0,\mathbf{I}\sigma)}{\mathbb{E}}(\nabla_{\bm{u}_{i}}\bm{g}((\bm{u}+\bm{\delta})\mathbf{V}^{T}))\qquad\qquad\qquad\qquad\qquad\qquad~{}~{}\text{Smooth
grad}.$ (7) $\displaystyle\ldots$

The complete derivation of the 7 new CATs is provided in the appendix. In the
derivations, $\nabla_{\bm{u}_{i}}$ denotes the gradient with respect to the
$i$-th coordinate of $\bm{u}$, while $\mathbb{E}$ and $\mathbb{V}$ represent
the expectation and variance, respectively. In Eq. 5, $\mathbf{m}$ is a mask
of real-valued random variable between $0$ and $1$ (i.e
$\mathbf{m}\sim\mathcal{U}([0,1]^{p})$). We note that, when we use the
gradient (w.r.t to $\bm{u}_{i}$) as an importance score, we end up with the
directional derivative used in the TCAV metric [26], which is used by ACE and
ICE to assess the importance of concepts. CRAFT leverages the Sobol-Hoeffding
decomposition (used in sensitivity analysis), to estimate the concept
importance. The Sobol indices measure the contribution of a concept as well as
its interaction of any order with any other concepts to the output variance.
Intuitively, the numerator of Eq. 5 is the expected variance that would be
left if all variables but $\bm{u}_{i}$ were to be fixed.

#### Evaluation of concept importance methods

Our generalization of the concept importance score, using the Concept
ATtributions (CATs), allows us to observe that current concept-based
explainability methods are only leveraging a small subset of concept
importance methods. In Appendix A, we provide the complete derivation of $7$
new CATs based on the following existing attribution methods, notably:
Gradient input [6], Smooth grad [5], Integrated Gradients [7], VarGrad [51],
Occlusion [13], HSIC [10] and RISE [32].

With the concept importance scoring now formulated as a generalization of
attribution methods, we can borrow the metrics from the attribution domain to
evaluate the faithfulness [52, 32, 33] of concept importance methods. In
particular, we adapt three distinct metrics to evaluate the significance of
concept importance scores : the C-Deletion [32], C-Insertion [32], and
C-$\mu$Fidelity [33] metrics. In C-Deletion, we gradually remove the concepts
(as shown in Figure 3), in decreasing order of importance, and we report the
network’s output each time a concept is removed. When a concept is removed in
C-Deletion, the corresponding coordinate in the representation is set to
$\bm{0}$. The final C-Deletion metrics are computed as the area under the
curve in Figure 3. For C-Insertion, this is the opposite: we start from a
representation vector filled with zero, and we progressively add more
concepts, following an increasing order of importance.

Figure 4: C-Deletion, C-Insertion and C-$\mu$Fidelity across layer. We report
the $3$ metrics to evaluate CATs for each block (from B2 to B5) of a ResNet50.
We evaluate $8$ Concept Attribution methods, all represented with different
colors (see legend in Figure 3). The average trend of these eight methods is
represented by the black dashed line ( ). Lower C-Deletion is better, higher
C-Insertion and C-$\mu$Fidelity is better.

For the C-$\mu$Fidelity, we calculate the correlation between the model’s
output when concepts are randomly removed and the importance assigned to those
specific concepts. The results across layers for a ResNet50 model are depicted
in Figure 4. We observe that decomposition towards the end of the model is
preferred across all the metrics. As a result, in the next section, we will
specifically examine the case of the penultimate layer.

#### A note on the last layer

Based on our empirical results, it appears that the last layer is preferable
for both improved concept extraction and more accurate estimation of
importance. Herein, we derive theoretical guarantees about the optimality of
concept importance methods in the penultimate layer. Without loss of
generality, we assume $y\in\mathbb{R}$ the logits of the class of interest. In
the penultimate layer, the score $y$ is a linear combination of activations:
$y=\bm{a}\mathbf{W}+\mathbf{b}$ for weight matrix $\mathbf{W}$ and bias
$\mathbf{b}$. In this particular case, all CATs have a closed-form (see
appendix B), that allows us to derive $2$ theorems. The first theorem tackles
the CATs optimality for the C-Deletion and C-Insertion methods (demonstration
in Appendix D). We observe that the C-Deletion and C-Insertion problems can be
represented as weighted matroids. Therefore the greedy algorithms lead to
optimal solutions for CATs and a similar theorem could be derived for
C-$\mu$Fidelity.

######  Theorem 3.1 (Optimal C-Deletion, C-Insertion in the penultimate
layer).

When decomposing in the penultimate layer, Gradient Input, Integrated
Gradients, Occlusion, and Rise yield the optimal solution for the C-Deletion
and C-Insertion metrics. More generally, any method $\bm{\varphi}(\bm{u})$
that satisfies the condition
$\forall(i,j)\in\\{1,\ldots,k\\}^{2},(\bm{u}\odot\mathbf{e}_{i})\mathbf{V}^{\mathsf{T}}\mathbf{W}\geq(\bm{u}\odot\mathbf{e}_{j})\mathbf{V}^{\mathsf{T}}\mathbf{W}\implies\bm{\varphi}(\bm{u})_{i}\geq\bm{\varphi}(\bm{u})_{j}$
yields the optimal solution.

######  Theorem 3.2 (Optimal C-$\mu$Fidelity in the penultimate layer).

When decomposing in the penultimate layer, Gradient Input, Integrated
Gradients, Occlusion, and Rise yield the optimal solution for the
C-$\mu$Fidelity metric.

Therefore, for all $3$ metrics, the concept importance methods based on
Gradient Input, Integrated Gradient, Occlusion and Rise are optimal, when used
in the penultimate layer.

Figure 5: From global (class-based) to local (image-based) importance. Global
importance can be decomposed into reliability and prevalence scores.
Prevalence quantifies how frequently a concept is encountered, and reliability
indicates how diagnostic a concept is for the class. The bar-charts are
computed for the class “Espresso” on a ResNet50 (see Figure 1, left panel)

In summary, our investigation of concept extraction methods from the
perspective of dictionary learning demonstrates that the NMF approach,
specifically when extracting concepts from the penultimate layer, presents the
most appealing trade-off compared to PCA and K-Means methods. In addition, our
formalization of concept importance using attribution methods provided us with
theoretical guarantee for $4$ different CATs. Henceforth, we will then
consider the following setup : a NMF on the penultimate layer to extract the
concepts, combined with a concept importance method based on Integrated
Gradient.

###  3.3 Unveiling main strategies

So far, the concept-based explainability methods have mainly focused on
evaluating the global importance of concepts, i.e., the importance of concepts
for an entire class [26, 29]. This point can be limiting when studying
misclassified data points, as we can speculate that the most important
concepts for a given class might not hold for an individual sample (local
importance). Fortunately, our formulation of concept importance using
attribution methods gives us access to importance scores at the level of
individual samples (i.e., $\bm{\varphi}(\bm{u})$). Here, we show how to use
these local importance scores to efficiently cluster data points based on the
strategy used for their classification.

The local (or image-based) importance of concepts can be integrated into
global measures of importance for the entire class with the notion of
prevalence and reliability (see Figure 5). A concept is said to be prevalent
at the class level when it appears very frequently. A prevalence score is
computed based on the number of times a concept is identified as the most
important one, i.e., $\operatorname*{arg\,max}\bm{\varphi}(\bm{u})$. At the
same time, a concept is said to be reliable if it is very likely to trigger a
correct prediction. The reliability is quantified using the mean
classification accuracy on samples sharing the same most important concept.

#### Strategic cluster graph.

In the strategic cluster graph (Figure 1 and Figure 6), we combine the notions
of concept prevalence and reliability to reveal the main strategies of a model
for a given category, more precisely, we reveal their repartition across the
different samples of the class. We use a dimensionality reduction technique
(UMAP [53]) to arrange the data points based on the concept importance vector
$\bm{\varphi}(\bm{u})$ of each sample. Data points are colored according to
the associated concept with the highest importance –
$\operatorname*{arg\,max}\bm{\varphi}(\bm{u})$. Interestingly, one can see in
Figure 1 and Figure 6 that spatially close points represent samples classified
using similar strategies – as they exhibit similar concept importance – and
not necessarily similar embeddings. For example, for the “lemon” object
category (Figure 6), the texture of the lemon peel is the most prevalent
concept, as it appears to be the dominant concept in $90\%$ of the samples
(see the green cluster in Figure 6). We also observe that the concept “pile of
round, yellow objects” is not reliable for the network to properly classify a
lemon as it results in a mean classification accuracy of $40\%$ only (see top-
left graph in Figure 6).

In Figure 6 (right panel), we have exploited the strategic cluster graph to
understand the classification strategies leading to bad classifications. For
example, an orange ($1^{st}$ image, $1^{st}$ row) was classified as a lemon
because of the peel texture they both share. Similarly, a cathedral roof was
classified as a lemon because of the wedge shape structure of the structure
($4^{th}$ image, $1^{st}$ row).

Figure 6: Strategic cluster graph for the lemon category. Left: U-MAP of lemon
samples, in the concept space. Each concept is represented with its own color
and is exemplified with example belonging to the cluster. The concepts are
$\bullet$ the lemon wedge shape, $\bullet$ a pile of round, yellow objects,
$\bullet$ green objects hanging on a tree, and finally $\bullet$ the peel
texture, which is the predominant strategy. The reliability of each concept is
shown in the top-left bar-chart. Right: Example of images predicted as lemon
along with their corresponding explanations. These misclassified images are
recognized as lemons through the implementation of strategies that are
captured by our proposed strategic cluster graph.

##  4 Discussion

This article introduced a theoretical framework that unifies all modern
concept-based explainability methods. By breaking-down and formalizing the two
essential steps in these methods, concept extraction and concept importance
scoring, allowed us to better understand the underlying principles driving
concept-based explainability. We leveraged this unified framework to propose
new evaluation metrics for assessing the quality of extracted concepts.
Through experimental and theoretical analyses, we justified the standard use
of the last layer of an ANN for concept-based explainabilitions. Finally, we
harnessed the parallel between concept importance and attribution methods to
gain insights into global concept importance (at the class level) by examining
local concept importance (for individual samples). We proposed the strategic
cluster graph, which provides insights into the strategy used by an ANN to
classify images. We have provided an example use of this approach to better
understanding the failure cases of a system.Overall, our work demonstrates the
potential benefits of the dictionary learning framework for automatic concept
extraction and we hope this work will pave the way for further advancements in
the field of XAI.

## References

  * Tripicchio and D’Avella [2020] Paolo Tripicchio and Salvatore D’Avella.  Is deep learning ready to satisfy industry needs?  _Procedia Manufacturing_ , 51:1192–1199, 2020.
  * Doshi-Velez and Kim [2017] Finale Doshi-Velez and Been Kim.  Towards a rigorous science of interpretable machine learning.  _ArXiv e-print_ , 2017.
  * Jacovi et al. [2021] Alon Jacovi, Ana Marasović, Tim Miller, and Yoav Goldberg.  Formalizing trust in artificial intelligence: Prerequisites, causes and goals of human trust in ai.  In _Proceedings of the 2021 ACM conference on fairness, accountability, and transparency_ , pages 624–635, 2021.
  * Simonyan et al. [2013] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  In _Workshop, Proceedings of the International Conference on Learning Representations (ICLR)_ , 2013.
  * Smilkov et al. [2017] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg.  Smoothgrad: removing noise by adding noise.  In _Workshop on Visualization for Deep Learning, Proceedings of the International Conference on Machine Learning (ICML)_ , 2017.
  * Shrikumar et al. [2017] Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje.  Learning important features through propagating activation differences.  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 2017.
  * Sundararajan et al. [2017] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 2017.
  * Selvaraju et al. [2017] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * Fel et al. [2021] Thomas Fel, Remi Cadene, Mathieu Chalvidal, Matthieu Cord, David Vigouroux, and Thomas Serre.  Look at the variance! efficient black-box explanations with sobol-based sensitivity analysis.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Novello et al. [2022] Paul Novello, Thomas Fel, and David Vigouroux.  Making sense of dependence: Efficient black-box explanations using dependence measure.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Fel et al. [2022a] Thomas Fel, Melanie Ducoffe, David Vigouroux, Remi Cadene, Mikael Capelle, Claire Nicodeme, and Thomas Serre.  Don’t lie to me! robust and efficient explainability with verified perturbation analysis.  _Workshop on Formal Verification of Machine Learning, Proceedings of the International Conference on Machine Learning (ICML)_ , 2022a.
  * Graziani et al. [2021] Mara Graziani, Iam Palatnik de Sousa, Marley MBR Vellasco, Eduardo Costa da Silva, Henning Müller, and Vincent Andrearczyk.  Sharpening local interpretable model-agnostic explanations for histopathology: improved understandability and reliability.  In _Medical Image Computing and Computer Assisted Intervention (MICCAI)_. Springer, 2021.
  * Zeiler and Fergus [2014a] Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In _Proceedings of the IEEE European Conference on Computer Vision (ECCV)_ , 2014a.
  * Fong and Vedaldi [2017] Ruth C. Fong and Andrea Vedaldi.  Interpretable explanations of black boxes by meaningful perturbation.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * Idrissi et al. [2023] Marouane Il Idrissi, Nicolas Bousquet, Fabrice Gamboa, Bertrand Iooss, and Jean-Michel Loubes.  On the coalitional decomposition of parameters of interest, 2023.
  * Adebayo et al. [2018] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim.  Sanity checks for saliency maps.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2018\.
  * Sixt et al. [2020] Leon Sixt, Maximilian Granz, and Tim Landgraf.  When explanations lie: Why many modified bp attributions fail.  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 2020.
  * Slack et al. [2021] Dylan Slack, Anna Hilgard, Sameer Singh, and Himabindu Lakkaraju.  Reliable post hoc explanations: Modeling uncertainty in explainability.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 34, 2021.
  * Rao et al. [2022] Sukrut Rao, Moritz Böhle, and Bernt Schiele.  Towards better understanding attribution methods.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Hase and Bansal [2020] Peter Hase and Mohit Bansal.  Evaluating explainable ai: Which algorithmic explanations help users predict model behavior?  _Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)_ , 2020.
  * Shen and Huang [2020] Hua Shen and Ting-Hao Huang.  How useful are the machine-generated interpretations to general users? a human evaluation on guessing the incorrectly predicted labels.  In _Proceedings of the AAAI Conference on Human Computation and Crowdsourcing_ , volume 8, pages 168–172, 2020.
  * Colin et al. [2021] Julien Colin, Thomas Fel, Rémi Cadène, and Thomas Serre.  What i cannot predict, i do not understand: A human-centered evaluation framework for explainability methods.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021\.
  * Kim et al. [2022] Sunnie S. Y. Kim, Nicole Meister, Vikram V. Ramaswamy, Ruth Fong, and Olga Russakovsky.  HIVE: Evaluating the human interpretability of visual explanations.  In _Proceedings of the IEEE European Conference on Computer Vision (ECCV)_ , 2022.
  * Nguyen et al. [2021] Giang Nguyen, Daeyoung Kim, and Anh Nguyen.  The effectiveness of feature attribution methods and its correlation with automatic evaluation scores.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021\.
  * Sixt et al. [2022] Leon Sixt, Martin Schuessler, Oana-Iuliana Popescu, Philipp Weiß, and Tim Landgraf.  Do users benefit from interpretable vision? a user study, baseline, and dataset.  _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2022.
  * Kim et al. [2018] Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, et al.  Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav).  In _International conference on machine learning_. Proceedings of the International Conference on Machine Learning (ICML), 2018.
  * Ghorbani et al. [2019] Amirata Ghorbani, James Wexler, James Y Zou, and Been Kim.  Towards automatic concept-based explanations.  In _Advances in Neural Information Processing Systems_ , pages 9273–9282, 2019.
  * Zhang et al. [2021] Ruihan Zhang, Prashan Madumal, Tim Miller, Krista A Ehinger, and Benjamin IP Rubinstein.  Invertible concept-based explanations for cnn models with non-negative concept activation vectors.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 11682–11690, 2021.
  * Fel et al. [2023] Thomas Fel, Agustin Picard, Louis Bethune, Thibaut Boissin, David Vigouroux, Julien Colin, Rémi Cadène, and Thomas Serre.  Craft: Concept recursive activation factorization for explainability.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023.
  * Graziani et al. [2023] Mara Graziani, An-phi Nguyen, Laura O’Mahony, Henning Müller, and Vincent Andrearczyk.  Concept discovery and dataset exploration with singular value decomposition.  In _ICLR 2023 Workshop on Pitfalls of limited data and computation for Trustworthy ML_ , 2023.
  * Genone and Lombrozo [2012] James Genone and Tania Lombrozo.  Concept possession, experimental semantics, and hybrid theories of reference.  _Philosophical Psychology_ , 25(5):717–742, 2012\.
  * Petsiuk et al. [2018] Vitali Petsiuk, Abir Das, and Kate Saenko.  Rise: Randomized input sampling for explanation of black-box models.  In _Proceedings of the British Machine Vision Conference (BMVC)_ , 2018.
  * Bhatt et al. [2020] Umang Bhatt, Adrian Weller, and José M. F. Moura.  Evaluating and aggregating feature-based model explanations.  In _Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)_ , 2020.
  * Haug et al. [2021] Johannes Haug, Stefan Zürn, Peter El-Jiz, and Gjergji Kasneci.  On baselines for local feature attributions.  _arXiv preprint arXiv:2101.00905_ , 2021.
  * Hsieh et al. [2021] Cheng-Yu Hsieh, Chih-Kuan Yeh, Xuanqing Liu, Pradeep Ravikumar, Seungyeon Kim, Sanjiv Kumar, and Cho-Jui Hsieh.  Evaluations and methods for explanation through robustness analysis.  In _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2021.
  * Kindermans et al. [2019] Pieter-Jan Kindermans, Sara Hooker, Julius Adebayo, Maximilian Alber, Kristof T Schütt, Sven Dähne, Dumitru Erhan, and Been Kim.  The (un) reliability of saliency methods.  2019\.
  * Sturmfels et al. [2020] Pascal Sturmfels, Scott Lundberg, and Su-In Lee.  Visualizing the impact of feature attribution baselines.  _Distill_ , 2020.
  * Elhage et al. [2022] Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield-Dodds, Robert Lasenby, Dawn Drain, Carol Chen, et al.  Toy models of superposition.  _arXiv preprint arXiv:2209.10652_ , 2022.
  * Mairal et al. [2014] Julien Mairal, Francis Bach, Jean Ponce, et al.  Sparse modeling for image and vision processing.  _Foundations and Trends® in Computer Graphics and Vision_ , 8(2-3):85–283, 2014.
  * Eckart and Young [1936] Carl Eckart and Gale Young.  The approximation of one matrix by another of lower rank.  _Psychometrika_ , 1(3):211–218, 1936.
  * Papyan et al. [2020] Vardan Papyan, XY Han, and David L Donoho.  Prevalence of neural collapse during the terminal phase of deep learning training.  _Proceedings of the National Academy of Sciences_ , 117(40):24652–24663, 2020.
  * Ding et al. [2005] Chris Ding, Xiaofeng He, and Horst D Simon.  On the equivalence of nonnegative matrix factorization and spectral clustering.  In _Proceedings of the 2005 SIAM international conference on data mining_ , pages 606–610. SIAM, 2005.
  * Zhang et al. [2018] Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel.  Efficient neural network robustness certification with general activation functions.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2018\.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * Sandler et al. [2018] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4510–4520, 2018.
  * [46] Jeremy Howard.  Imagenette dataset.  URL https://github.com/fastai/imagenette/.
  * Bousquet and Elisseeff [2002] Olivier Bousquet and André Elisseeff.  Stability and generalization.  _The Journal of Machine Learning Research_ , 2002.
  * [48] Cédric Villani et al.  _Optimal transport: old and new_ , volume 338.  Springer.
  * Sun et al. [2022] Yiyou Sun, Yifei Ming, Xiaojin Zhu, and Yixuan Li.  Out-of-distribution detection with deep nearest neighbors.  In _International Conference on Machine Learning_ , pages 20827–20840. PMLR, 2022.
  * Ghorbani et al. [2017] Amirata Ghorbani, Abubakar Abid, and James Zou.  Interpretation of neural networks is fragile.  In _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , 2017.
  * Hooker et al. [2019] Sara Hooker, Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim.  A benchmark for interpretability methods in deep neural networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Jacovi and Goldberg [2020] Alon Jacovi and Yoav Goldberg.  Towards faithfully interpretable nlp systems: How should we define and evaluate faithfulness?  _Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL)_ , 2020.
  * 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.
  * Fel et al. [2022b] Thomas Fel, Lucas Hervier, David Vigouroux, Antonin Poche, Justin Plakoo, Remi Cadene, Mathieu Chalvidal, Julien Colin, Thibaut Boissin, Louis Bethune, Agustin Picard, Claire Nicodeme, Laurent Gardes, Gregory Flandin, and Thomas Serre.  Xplique: A deep learning explainability toolbox.  _Workshop on Explainable Artificial Intelligence for Computer Vision (CVPR)_ , 2022b.
  * Ancona et al. [2018] Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross.  Towards better understanding of gradient-based attribution methods for deep neural networks.  In _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2018.
  * Sotoudeh and Thakur [2019] Matthew Sotoudeh and Aditya V. Thakur.  Computing linear restrictions of neural networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Zeiler and Fergus [2014b] Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In _Proceedings of the IEEE European Conference on Computer Vision (ECCV)_ , 2014b.
  * Whitney [1992] Hassler Whitney.  On the abstract properties of linear dependence.  _Hassler Whitney Collected Papers_ , pages 147–171, 1992.

##  Appendix A Attribution methods for Concepts

In the following section, we will re-derive the different attribution methods
in the literature. We use the Xplique library and adapted each methods [54].
We quickly recall that we seek to estimate the importance of each concept for
a set of concept coefficients
$\bm{u}=(\bm{u}_{1},\ldots,\bm{u}_{k})\in\mathbb{R}^{k}$ in the concept basis
$\mathbf{V}\in\mathbb{R}^{p\times k}$. This concept basis is a re-
interpretation of a latent space $\mathcal{H}\subseteq\mathbb{R}^{p}$ and the
function $\bm{g}:\mathbb{R}^{p}\to\mathbb{R}$ is a signal used to compute
importance from (e.g., logits value, cosine similarity with a sentence…). Each
Attributions method will map a set of concept values to an importance score
$\bm{\varphi}:\mathbb{R}^{k}\to\mathbb{R}^{k}$, a greater score
$\bm{\varphi}(\bm{u})_{i}$ indicates that a concept $\bm{u}_{i}$ is more
important.

Saliency (SA) [4] was originally a visualization technique based on the
gradient of a class score relative to the input, indicating in an
infinitesimal neighborhood, which pixels must be modified to most affect the
score of the class of interest. In our case, it indicates which concept in an
infinitesimal neighborhood has the most influence on the output:

$\bm{\varphi}^{(SA)}(\bm{u})=\nabla_{\bm{u}}\bm{g}(\bm{u}V^{\mathsf{T}}).$

Gradient $\odot$ Input (GI) [6] is based on the gradient of a class score
relative to the input, element-wise with the input, it was introduced to
improve the sharpness of the attribution maps. A theoretical analysis
conducted by [55] showed that Gradient $\odot$ Input is equivalent to
$\epsilon$-LRP and DeepLIFT [6] methods under certain conditions – using a
baseline of zero, and with all biases to zero. In our case, it boils down to:

$\bm{\varphi}^{(GI)}(\bm{u})=\bm{u}\odot\nabla_{\bm{u}}\bm{g}(\bm{u}\mathbf{V}^{\mathsf{T}}).$

Integrated Gradients (IG) [7] consists of summing the gradient values along
the path from a baseline state to the current value. The baseline $\bm{u}_{0}$
used is zero. This integral can be approximated with a set of $m$ points at
regular intervals between the baseline and the point of interest. In order to
approximate from a finite number of steps, we use a trapezoidal rule and not a
left-Riemann summation, which allows for more accurate results and improved
performance (see [56] for a comparison). For all the experiments $m=30$.

$\bm{\varphi}^{(IG)}(\bm{u})=(\bm{u}-\bm{u}_{0})\int_{0}^{1}\nabla_{\bm{u}}\bm{g}((\bm{u}_{0}+\alpha(\bm{u}-\bm{u}_{0}))\mathbf{V}^{\mathsf{T}})\mathop{}\\!\mathrm{d}\alpha.$

SmoothGrad (SG) [5] is also a gradient-based explanation method, which, as the
name suggests, averages the gradient at several points corresponding to small
perturbations (drawn i.i.d from an isotropic normal distribution of standard
deviation $\sigma$) around the point of interest. The smoothing effect induced
by the average helps to reduce the visual noise, and hence improves the
explanations. In our case, the attribution is obtained after averaging $m$
points with noise added to the concept coefficients. For all the experiments,
we took $m=30$ and $\sigma=0.1$.

$\bm{\varphi}^{(SG)}(\bm{u})=\underset{\bm{\delta}\sim\mathcal{N}(0,\mathbf{I}\sigma)}{\mathbb{E}}(\nabla_{\bm{u}}\bm{g}(\bm{u}+\bm{\delta})).$

VarGrad (VG) [51] was proposed as an alternative to SmoothGrad as it employs
the same methodology to construct the attribution maps: using a set of $m$
noisy inputs, it aggregates the gradients using the variance rather than the
mean. For the experiment, $m$ and $\sigma$ are the same as SmoothGrad.
Formally:

$\bm{\varphi}^{(VG)}(\bm{u})=\underset{\bm{\delta}\sim\mathcal{N}(0,\mathbf{I}\sigma)}{\mathbb{V}}(\nabla_{\bm{u}}\bm{g}(\bm{u}+\bm{\delta})).$

Occlusion (OC) [57] is a simple – yet effective – sensitivity method that
sweeps a patch that occludes pixels over the images using a baseline state and
use the variations of the model prediction to deduce critical areas. In our
case, we simply omit each concept one-at-a-time to deduce the concept’s
importance. For all the experiments, the baseline state $\bm{u}_{0}$ was zero.

$\bm{\varphi}^{(OC)}(\bm{u})_{i}=\bm{g}(\bm{u}\mathbf{V}^{\mathsf{T}})-\bm{g}(\bm{u}_{[i=\bm{u}_{0}]}\mathbf{V}^{\mathsf{T}})$

Sobol Attribution Method (SM) [9] then used for estimating concept importance
in [29] is a black-box attribution method grounded in Sensitivity Analysis.
Beyond modeling the individual contributions of image regions, Sobol indices
provide an efficient way to capture higher-order interactions between image
regions and their contributions to a neural network’s prediction through the
lens of variance. In our case, the score for a concept $\bm{u}_{i}$ is the
expected variance that would be left if all variables but $i$ were to be fixed
:

$\bm{\varphi}^{(SM)}(\bm{u})_{i}=\frac{\mathbb{E}(\mathbb{V}(\bm{g}((\bm{u}\odot\mathbf{M})\mathbf{V}^{\mathsf{T}})|\mathbf{M}_{\sim
i}))}{\mathbb{V}(\bm{g}((\bm{u}\odot\mathbf{M})\mathbf{V}^{\mathsf{T}}))}.$

With $\mathbf{M}\sim\mathcal{U}([0,1])^{k}$. For all the experiments, the
number of designs was $32$ and we use the Jansen estimator of the Xplique
library.

HSIC Attribution Method (HS) [10] seeks to explain a neural network’s
prediction for a given input image by assessing the dependence between the
output and patches of the input. In our case, we randomly mask/remove concepts
and measure the dependence between the output and the presence of each concept
through $N$ binary masks. Formally:

$\bm{\varphi}^{(HS)}(\bm{u})=\frac{1}{(N-1)^{2}}\mathrm{Tr}(KHLH).$

With $H,L,K\in\mathbb{R}^{N\times N}$ and
$K_{ij}=k(\mathbf{M}_{i},\mathbf{M}_{j})$, $L_{ij}=l(\bm{y}_{i},\bm{y}_{j})$
and $H_{ij}=\delta(i=j)-N^{-1}$. Here, $k(\cdot,\cdot)$ and $l(\cdot,\cdot)$
denote the chosen kernels and $\mathbf{M}\sim\\{0,1\\}^{p}$ the binary mask
applied to the input $\bm{u}$.

RISE (RI) [32] is also a black-box attribution method that probes the model
with multiple version of a masked input to model the most important features.
Formally, with $\bm{m}\sim\mathcal{U}([0,1])^{k}$. :

$\bm{\varphi}^{(RI)}_{i}(\bm{u})=\mathbb{E}(\bm{g}(\bm{u}\odot\bm{m})|\bm{m}_{i}=1).$

##  Appendix B Closed-form of Attributions for the last layer

Without loss of generality, we focus on the decomposition in the last layer,
that is $\bm{a}=\bm{u}\mathbf{V}^{\mathsf{T}}$ with parameters
$(\mathbf{W},\mathbf{b})$ for the weight and the bias respectively, hence we
obtain $\bm{y}=(\bm{u}\mathbf{V}^{\mathsf{T}})\mathbf{W}+\mathbf{b}$ with
$\mathbf{W}\in\mathbb{R}^{p}$ and $\mathbf{b}\in\mathbb{R}$.

We start by deriving the closed form of Saliency (SA) and naturally Gradient-
Input (GI):

$\displaystyle\bm{\varphi}^{(SA)}(\bm{u})$
$\displaystyle=\nabla_{\bm{u}}\bm{g}(\bm{u}\mathbf{V}^{\mathsf{T}})=\nabla_{\bm{u}}(\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}+\mathbf{b})$
$\displaystyle=\mathbf{W}^{\mathsf{T}}\mathbf{V}$ .
$\displaystyle\bm{\varphi}^{(GI)}(\bm{u})$
$\displaystyle=\nabla_{\bm{u}}\bm{g}(\bm{u}\mathbf{V}^{\mathsf{T}})\odot\bm{u}=\nabla_{\bm{u}}(\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}+\mathbf{b})\odot\bm{u}$
$\displaystyle=\mathbf{W}^{\mathsf{T}}\mathbf{V}\odot\bm{u}$ .

We observe two different forms that will in fact be repeated for the other
methods, for example with Integrated-Gradient (IG) which will take the form of
Gradient-Input, while SmoothGrad (SG) will take the form of Saliency.

$\displaystyle\bm{\varphi}^{(IG)}(\bm{u})$
$\displaystyle=(\bm{u}-\bm{u}_{0})\odot\int_{0}^{1}\nabla_{\bm{u}}\bm{g}((\bm{u}_{0}+\alpha(\bm{u}-\bm{u}_{0}))\mathbf{V}^{\mathsf{T}})\mathop{}\\!\mathrm{d}\alpha$
$\displaystyle=\bm{u}\odot\int_{0}^{1}\nabla_{\bm{u}}((\alpha\bm{u}))\mathbf{V}^{\mathsf{T}}\mathbf{W}+\mathbf{b}+(\alpha-1)\bm{u}_{0}\mathbf{V}^{\mathsf{T}}\mathbf{W})\mathop{}\\!\mathrm{d}\alpha$
$\displaystyle=\bm{u}\odot\int_{0}^{1}\alpha\mathbf{W}^{\mathsf{T}}\mathop{}\\!\mathrm{d}\alpha=\bm{u}\odot\mathbf{W}^{\mathsf{T}}\mathbf{V}\left[\frac{1}{2}\alpha^{2}\right]_{0}^{1}$
$\displaystyle=\frac{1}{2}\bm{u}\odot\mathbf{W}^{\mathsf{T}}\mathbf{V}.$

$\displaystyle\bm{\varphi}^{(SG)}(\bm{u})$
$\displaystyle=\underset{\bm{\delta}\sim\mathcal{N}(0,\mathbf{I}\sigma)}{\mathbb{E}}(\nabla_{\bm{u}}\bm{g}(\bm{u}+\bm{\delta}))=\underset{\bm{\delta}\sim\mathcal{N}(0,\mathbf{I}\sigma)}{\mathbb{E}}(\nabla_{\bm{u}}((\bm{u}+\bm{\delta})\mathbf{V}^{\mathsf{T}}\mathbf{W}+\mathbf{b}))$
$\displaystyle=\underset{\bm{\delta}\sim\mathcal{N}(0,\mathbf{I}\sigma)}{\mathbb{E}}(\nabla_{\bm{u}}(\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}))$
$\displaystyle=\mathbf{W}^{\mathsf{T}}\mathbf{V}$ .

The case of VarGrad is specific, as the gradient of a linear system being
constant, its variance is null.

$\displaystyle\bm{\varphi}^{(VG)}(\bm{u})$
$\displaystyle=\underset{\bm{\delta}\sim\mathcal{N}(0,\mathbf{I}\sigma)}{\mathbb{V}}(\nabla_{\bm{u}}\bm{g}(\bm{u}+\bm{\delta}))=\underset{\bm{\delta}\sim\mathcal{N}(0,\mathbf{I}\sigma)}{\mathbb{V}}(\nabla_{\bm{u}}((\bm{u}+\bm{\delta})\mathbf{V}^{\mathsf{T}}\mathbf{W}+\mathbf{b}))$
$\displaystyle=\underset{\bm{\delta}\sim\mathcal{N}(0,\mathbf{I}\sigma)}{\mathbb{V}}(\mathbf{W}^{\mathsf{T}}\mathbf{V})$
$\displaystyle=0$ .

Finally, for Occlusion (OC) and RISE (RI), we fall back on the Gradient Input
form (with multiplicative and additive constant for RISE).

$\displaystyle\bm{\varphi}^{(OC)}_{i}(\bm{u})$
$\displaystyle=\bm{g}(\bm{u}\mathbf{V}^{\mathsf{T}})-\bm{g}(\bm{u}_{[i=\bm{u}_{0}]}\mathbf{V}^{\mathsf{T}})=\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}+\mathbf{b}-(\bm{u}_{[i=\bm{u}_{0}]}\mathbf{V}^{\mathsf{T}}\mathbf{W}+\mathbf{b})$
$\displaystyle=(\sum_{j}^{r}\bm{u}_{j}\mathbf{V}_{j}^{\mathsf{T}})\mathbf{W}-(\sum_{j\neq
i}^{r}\bm{u}_{j}\mathbf{V}_{j}^{\mathsf{T}})\mathbf{W}$
$\displaystyle=\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}$

thus
$\bm{\varphi}^{(OC)}(\bm{u})=\bm{u}\odot\mathbf{W}^{\mathsf{T}}\mathbf{V}$

$\displaystyle\bm{\varphi}^{(RI)}_{i}(\bm{u})$
$\displaystyle=\mathbb{E}(\bm{g}(\bm{u}\odot\bm{m})|\bm{m}_{i}=1)=\mathbb{E}((\bm{u}\odot\bm{m})\mathbf{V}^{\mathsf{T}}\mathbf{W}+\mathbf{b}|\bm{m}_{i}=1)$
$\displaystyle=\mathbf{b}+\sum_{j\neq
i}^{r}\bm{u}_{j}\mathbb{E}(\bm{m}_{j})\mathbf{V}_{j}^{\mathsf{T}}\mathbf{W}+\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}$
$\displaystyle=\mathbf{b}+\frac{1}{2}(\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}+\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W})$

##  Appendix C $\mu$ Fidelity optimality

Before showing that some methods are optimal with regard to C-Deletion and
C-Insertion, we start with a first metric that studies the fidelity of the
importance of concepts: $\mu$Fidelity, whose definition we recall

$\mu F=\underset{\begin{subarray}{c}S\subseteq\\{1,\ldots,k\\}\\\
|S|=m\end{subarray}}{\rho}(\sum_{i\in
S}\bm{\varphi}(\bm{u})_{i},\bm{g}(\bm{u})-\bm{g}(\bm{u}_{[\bm{u}_{i}=\bm{u}_{0},i\in
S]}))$

With $\rho$ the Pearson correlation and $\bm{u}_{[\bm{u}_{i}=\bm{u}_{0},i\in
S]}$ means that all $i$ components of $\bm{u}$ are set to zero.

######  Theorem C.1 (Optimal $\mu$Fidelity in the last layer).

When decomposing in the last layer, Gradient Input, Integrated Gradients,
Occlusion, and Rise yield the optimal solution for the $\mu$Fidelity metric.
In a more general sense, any method $\bm{\varphi}(\bm{u})$ that is of the form
$\bm{\varphi}_{i}(\bm{u})=a(\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W})+b$
with $a\in\mathbb{R}^{+},b\in\mathbb{R}$ yield the optimal solution, thus
having a correlation of 1.

###### Proof.

In the last layer case, $\mu$Fidelity boils down to:

$\displaystyle\mu F$
$\displaystyle=\underset{\begin{subarray}{c}S\subseteq\\{1,\ldots,k\\}\\\
|S|=m\end{subarray}}{\rho}\big{(}\sum_{i\in
S}\bm{\varphi}(\bm{u})_{i},\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}+\mathbf{b}-(\sum_{i\notin
S}\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W})-\mathbf{b}\big{)}$
$\displaystyle=\underset{\begin{subarray}{c}S\subseteq\\{1,\ldots,k\\}\\\
|S|=m\end{subarray}}{\rho}\big{(}\sum_{i\in
S}\bm{\varphi}(\bm{u})_{i},\sum_{i\in
S}\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}\big{)}$

We recall that for Gradient Input, Integrated Gradients, Occlusion,
$\bm{\varphi}_{i}(\bm{u})\propto\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}$,
thus

$\displaystyle\mu F$
$\displaystyle=\underset{\begin{subarray}{c}S\subseteq\\{1,\ldots,k\\}\\\
|S|=m\end{subarray}}{\rho}\big{(}\sum_{i\in
S}\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W},\sum_{i\in
S}\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}\big{)}=1$

For RISE, we get the following characterization:

$\displaystyle\mu F$
$\displaystyle=\underset{\begin{subarray}{c}S\subseteq\\{1,\ldots,k\\}\\\
|S|=m\end{subarray}}{\rho}\big{(}\sum_{i\in
S}\mathbf{b}+\frac{1}{2}(\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}+\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}),\sum_{i\in
S}\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}\big{)}$
$\displaystyle=\underset{\begin{subarray}{c}S\subseteq\\{1,\ldots,k\\}\\\
|S|=m\end{subarray}}{\rho}\big{(}|S|(\mathbf{b}+\frac{1}{2}(\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}))+\sum_{i\in
S}\frac{1}{2}\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W},\sum_{i\in
S}\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}\big{)}$
$\displaystyle=\underset{\begin{subarray}{c}S\subseteq\\{1,\ldots,k\\}\\\
|S|=m\end{subarray}}{\rho}\big{(}a(\sum_{i\in
S}\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W})+b,\sum_{i\in
S}\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}\big{)}=1$

with
$a=\frac{1}{2},b=m(\mathbf{b}+\frac{1}{2}(\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}))$.

∎

##  Appendix D Optimality for C-Insertion and C-Deletion

In order to prove the optimality of some attribution methods on the
C-Insertion and C-Deletion metrics, we will use the Matroid theory of which we
recall some fundamentals.

Matroids were introduced by Whitney in 1935 [58]. It was quickly realized that
they unified properties of various domains such as graph theory, linear
algebra or geometry. Later, in the ’60s, a connection was made with
combinatorial optimization, nothing that they also played a central role in
combinatorial optimization.

The power of this tool is that it allows us to show easily that greedy
algorithms are optimal with respect to some criterion on a broad range of
problems. Here, we show that insertion is a greedy algorithm (since the
concepts inserted are chosen sequentially based on the model score).

For the rest of this section, we assume $E=\\{e_{1},\ldots,e_{k}\\}$ the set
of the canonical vectors in $\mathbb{R}^{k}$, with $e_{i}$ being the element
associated with the $i^{th}$ concept.

######  Definition D.1 (Matroid).

A matroid $M$ is a tuple $(E,\mathcal{J})$, where E is a finite ground set and
$\mathcal{J}\subseteq 2^{E}$ is the power set of $E$, a collection of
independent sets, such that:

  1. 1.

$\mathcal{J}$ is nonempty, $\emptyset\in\mathcal{J}$.

  2. 2.

$\mathcal{J}$ is downward closed; i.e., if $S\in\mathcal{J}$ and
$S^{\prime}\subseteq S$, then $S^{\prime}\in\mathcal{J}$

  3. 3.

If $S,S^{\prime}\in\mathcal{J}^{2}$ and $|S|<|S^{\prime}|$, then $\exists s\in
S^{\prime}\setminus S$ such that $S\cup\\{s\\}\in\mathcal{J}$

In particular, we will need uniform matroids:

######  Definition D.2 (Uniform Matroid).

Let $E$ be a set of size $k$ and let $n\in\\{1,\ldots,k\\}$. If $\mathcal{J}$
is the collection of all subsets of $E$ of size at most $n$, then
$(E,\mathcal{J})$ is a matroid, called a uniform matroid and denoted
$M^{(n)}$.

Finally, we need to characterize the concept set chosen at each step.

######  Definition D.3 (Base of Matroid).

Let $M=(E,\mathcal{J})$ be a matroid. A subset $B$ of $E$ is called a basis of
$M$ if and only if:

  1. 1.

$B\in\mathcal{J}$

  2. 2.

$\forall e\in E\setminus B,~{}B\cup\\{e\\}\notin\mathcal{J}$

Moreover, we denote $\mathcal{B}(M)$ the set of all the basis of $M$.

At each step, the insertion metric selects the concepts of maximum score given
a cardinality constraint. At each new step, the concepts from the previous
step are selected and it add a new concept from the whole available set, the
one not selected so far with the highest score. This criterion requires an
additional ingredient: the _weight_ associated to each element of the matroid
- here an element of the matroid is a concept.

#### Ponderated Matroid

Let $M^{(n)}=(E,\mathcal{J})$ be a uniform matroid and $w:E\to\mathbb{R}$ a
weighting function associated to an element of $E$ (a concept). The goal of
C-Insertion at step $n$ is to find a basis (a set of concepts) $B^{\star}$
subject to $|B|=n$, that maximizes the weighting function :

$\forall B\in\mathcal{J},~{}~{}\sum_{e\in B^{\star}}w(e)\geq\sum_{e\in
B}w(e).$

Such a basis is called the basis of maximum weights (MW) of the weighted
matroid $M^{(n)}$. We will see that the greedy algorithm associated with this
weighting function gives the optimal solution to the MW problem on
C-Insertion. First, let’s define the _Greedy algorithm_.

Algorithm 1 Greedy algorithm

A $n$-uniform weighted matroid $M^{(n)}=(E,\mathcal{J},w)$

Sort the concepts by their weight $w(e_{i})$ in non-increasing order, and
store them in a list $\bar{e}$ such that
${\forall(i,j)\subseteq\\{1,\ldots,k\\}^{2},w(\bar{e}_{i})\geq
w(\bar{e}_{j})~{}\text{if}~{}i<j}$.

$B^{\star}=\\{\\}$

for $k=1$ to $n$ do

$B^{\star}=B^{\star}\cup\bar{e}_{i}$

end for

return $B^{\star}$

######  Theorem D.4 (Greedy Algorithm is an optimal solution to MW.).

Let $M=(E,\mathcal{J},w)$ a weighted matroid. The greedy Algorithm 1 returns a
maximum basis of $M$.

###### Proof.

First, by definition, $B^{\star}$ is a basis and thus an independent set,
i.e., $B^{\star}\in\mathcal{B}(M)$ (as $\forall(e,e^{\prime})\in
E^{2},~{}\langle e,e^{\prime}\rangle=0$). Now, suppose by contradiction that
there exists a base $B^{\prime}$ with a weight strictly greater than
$B^{\star}$. We will obtain a contradiction with respect to the augmentation
axiom of the matroid definition. Let $e_{1},\ldots,e_{k}$ be the elements of
$M$ sorted such that $w(e_{i})>w(e_{j})$ whenever $i<j$. Let $n$ be the rank
of our weighted uniform matroid $M^{(n)}$. Then we can write
$B^{\star}=(e_{i_{1}},\ldots,e_{i_{n}})$ and
$B^{\prime}=(e_{j_{1}},\ldots,e_{j_{n}})$ with $j_{k}<j_{l}$ and $i_{k}<i_{l}$
for any $k<l$.

Let $\ell$ be the smallest positive integer such that $i_{\ell}$ > $j_{\ell}$.
In particular, $\ell$ exists and is at most $n$ by assumption. Consider the
independent set $S_{\ell-1}=\\{e_{i_{1}},\ldots e_{\ell-1}\\}$ (in particular,
$S_{\ell-1}=\emptyset$ if $\ell=1$). According to the augmentation axiom
(Definition D.2, I3), there exist $k\in\\{1,\ldots,\ell\\}$ such that
$S_{\ell-1}+e_{j_{k}}\in\mathcal{J}$ and $e_{j_{k}}\notin S_{\ell-1}$.
However, $j_{k}\leq j_{\ell}<i_{\ell}$, thus $w(e_{j_{k}})\leq
w(e_{j_{\ell}})<w(e_{i_{\ell}})$. This contradicts the definition of the
greedy algorithm. ∎

Now, we notice that for the last layer, Insertion is a weighted matroid. We
insist that this result is _only true for the concepts in the penultimate
layer_ , as our demonstrations rely on the linearity of the decomposition.
Here, the weight is given by the score of the model, which is a linear
combination of concepts.

######  Theorem D.5 (Optimal Insertion in the last layer).

When decomposing in the last layer, Gradient Input, Integrated Gradients,
Occlusion, and Rise yield the optimal solution for the C-Insertion metric. In
a more general sense, any method $\bm{\varphi}(\bm{u})$ that satisfies the
condition
$\forall(i,j)\in\\{1,\ldots,k\\}^{2},(\bm{u}\odot\mathbf{e}_{i})\mathbf{V}^{\mathsf{T}}\mathbf{W}\geq(\bm{u}\odot\mathbf{e}_{j})\mathbf{V}^{\mathsf{T}}\mathbf{W}\implies\bm{\varphi}(\bm{u})_{i}\geq\bm{\varphi}(\bm{u})_{j}$
yield the optimal solution.

###### Proof.

Each $n$ step of the C-Insertion algorithm corresponds to the $n$-uniform
weighted matroid with weighting function $w(e_{i})=(\bm{u}\odot
e_{i})\mathbf{V}^{\mathsf{T}}\mathbf{W}+b=\bm{u}_{i}\mathbf{V}^{\mathsf{T}}\mathbf{W}+b$.
Therefore, any $\bm{\varphi}(\cdot)$ method that produces the same ordering as
$w(\cdot)$ will yield the optimal solution. It easily follows that Gradient
Input, Integrated Gradients, Occlusion are optimal as they all boil down to
$\bm{\varphi}_{i}(\bm{u})=\bm{u}_{i}\mathbf{V}^{\mathsf{T}}\mathbf{W}+b$.
Concerning RISE, suppose that $w(e_{i})\geq w(e_{j})$, then
$\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}+b\geq\bm{u}_{j}\mathbf{V}_{j}^{\mathsf{T}}\mathbf{W}+b$,
and
$\bm{\varphi}_{i}^{(RI)}(\bm{u})-\bm{\varphi}_{j}^{(RI)}(\bm{u})=\mathbf{b}+\frac{1}{2}(\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}+\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W})-\mathbf{b}+\frac{1}{2}(\bm{u}\mathbf{V}^{\mathsf{T}}\mathbf{W}+\bm{u}_{j}\mathbf{V}_{j}^{\mathsf{T}}\mathbf{W})=\bm{u}_{i}\mathbf{V}_{i}^{\mathsf{T}}\mathbf{W}-\bm{u}_{j}\mathbf{V}_{j}^{\mathsf{T}}\mathbf{W}\geq
0.$ Thus, RISE importance will order in the same manner and is also optimal. ∎

######  Corollary D.6 (Optimal Deletion in the last layer).

When decomposing in the last layer, Gradient Input, Integrated Gradients,
Occlusion, and Rise yield the optimal solution for the C-Deletion metric.

###### Proof.

It is simply observed that the C-Deletion problem seeks a minimum weight basis
and corresponds to the same weighted matroid with weighting function
$w^{\prime}(\cdot)=-w(\cdot)$. ∎