On Concept-Based Explanations in Deep Neural Networks
Authors: Chih-Kuan Yeh
Been Kim
Sercan Arik
Chun-Liang Li
Pradeep Ravikumar
Tomas Pfister
Venue:  (2020)
Keywords: concept-based explanations
interpretability

Abstract: Deep neural networks (DNNs) build high-level intelligence on low-level raw features. Understanding of this high-level intelligence can be enabled by deciphering the concepts they base their decisions on, as human-level thinking. In this paper, we study concept-based explainability for DNNs in a systematic framework. First, we define the notion of completeness, which quantifies how sufficient a particular set of concepts is in explaining a model's prediction behavior. Based on performance and variability motivations, we propose two definitions to quantify completeness. We show that under degenerate conditions, our method is equivalent to Principal Component Analysis. Next, we propose a concept discovery method that considers two additional constraints to encourage the interpretability of the discovered concepts. We use game-theoretic notions to aggregate over sets to define an importance score for each discovered concept, which we call \emph{ConceptSHAP}. On specifically-designed synthetic datasets and real-world text and image datasets, we validate the effectiveness of our framework in finding concepts that are complete in explaining the decision, and interpretable.

Under review as a conference paper at ICLR 2020
ON CONCEPT-BASED EXPLANATIONS IN DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Deep neural networks (DNNs) build high-level intelligence on low-level raw fea- tures. Understanding of this high-level intelligence can be enabled by deciphering the concepts they base their decisions on, as human-level thinking. this paper, we study concept-based explainability for DNNs in systematic framework. First, we define the notion of completeness, which quantifies how sufficient a particular set of concepts is in explaining a model's s prediction behavior. Based on performance and variability motivations, we propose two definitions to quantify completeness. under degenerate conditions, Analysis. Next, we propose a concept discovery method that considers two addi- tional constraints to encourage the interpretability of the discovered concepts. We use ghee-the notions to aggregate over sets to define an importance score for each discovered concept, which we call ConcepiSTIAP. On specifically-designeee synthetic datasets and real-world text and image datasets, we validate the effec- tiveness of our framework in finding concepts that are complete in explaining the decision, and interpretable.
method is equivalent to Principal Component
INTRODUCTION
Deep neural networks (DNNs) have shown great success in numerous tasks (Goodfellow et al. 2016h, from understanding images (Zoph et al.) (017) answering questions (Devlin et al. (018)) Yet, in many scenarios their lack of explainability serves as a bottleneck against their real-world impact, especially in high-stake decisions such as in medicine, transportation, and finance, where such explanations help identify systematic failure cases, comply with regulations, and provide feedback to model builders. This has thus led to increasing interest in human-like explanations of DNNs.
The most commonly-used methods to explain DNNs explain each prediction by quantifying the importance of each input feature (Ribeiro et al., 2016, Lundberg & Lee 2017). However, such explanations typically explain the behavior locally for each case, rather than globally explaining how the model makes its decisions. Also, input features (such as the raw pixel values), and weights on them, are not necessarily the most effective explanations for human understanding. Instead, "concept-based explanations" characterize the global behavior of a DNN in a way understandable to humans, by explaining how DNNs use concepts in arriving particular decisions. Such concept- based thinking, by extracting similarities from numerous examples and grouping them systematically based their resemblance, has been shown to play an essential role in human minds for making generalizations (Armstrong et al. 1983 Tenenbaum 1999). With a similar motivation, "concepts"" can explain the decision-making rationale of DNNs and their generalizable knowledge. A few recent studies have thus focused on bringing such concept-based explainability to DNNs. Based on the common implicit assumption that the concepts should lie in certain linear subspaces of some intermediate DNN activations, they aim to find such concepts efficiently and relate them to data. These have ranged from supervised approaches (Kim et al.) 2018 Zhou et al., 2018) that obtain concept representations given human-labeled data on salient concepts, to purely unsupervised approaches that provide concept explanations automatically without human labeling, ranging from k-means clustering of DNN activations (Ghorbani et al., 2019). to a ceff-interpretable Bayesian generative model (Bouchacourt & Denoyer 2019). A key motivating question we ask in this paper is whether could build on such unsupervised approaches extract concepts, but where in addition to ensuring that the concepts are representative of the DNN activations, we would also like to ensure the additional facet that they are sufficiently predictive of the DNN function itself.
This leads naturally to crucial unanswered question in concept- based explanation, which is how to evaluate whether set of concepts are sufficient for prediction. Previous concept-based explanations

---

Under review as a conference paper at ICLR 2020
o(x) Feature
(()(x),
Concepts
Projected Feature
Whale Zebra
Bat
Salient
ConceptSHAP important
Salient to
ConceptSHAP 0.3, important to blue whale
Salient
ConceptSHAP Important
The overview of our concept discovering algorithm. Given deep classification model, we first provide semantically meaningful clusters by segmentation followed by k-means clustering as in Ghorbani et al. (2019). Then, we discover complete and interpretable concepts under the constraint that each concept is salient to one (or a few) unique cluster, while projecting features onto the span of concept vectors does not deteriorate the classification performance. After the concepts of interest are retrieved, we can calculate the importance of each concept and the classes where each concept is the most important by ConceptSHAP.
Figure 1:
select concepts that are salient to a particular class (Kim et al. 2018). However, selecting set of salient concepts does not guarantee that these concepts are sufficient for prediction. The notion of explanations that are sufficient for prediction is also called the "completeness" of explanations (Gilpin al., 2018), which acknowledged to be valuable for evaluating explanations (Yang et al.. 2019). In this work, we propose such a completeness metric for given set of concept explanations. The completeness measurement can be applied to a set of concept vectors that lie in the span of some intermediate DNN layer activations, which is general assumption in previous concept-based explanation works (Kim et al., 2018). The core idea is that, by projecting the activations onto the span of concept vectors, keep just that information that can be explained by the concepts, and discard the information that are orthogonal to all concepts. Thus, when projecting activations onto the span of concept activation vectors result in no loss in prediction accuracy, we can learn concepts that are "complete" (i.e. sufficient for prediction).
Interestingly, show that under stringent degeneracy condition the DNNs, principal component analysis (PCA) on the DNN activations can be shown to maximize these concept completeness metrics. Of course such degeneracy assumptions likely do not hold in general, so that maximizing these completeness metrics could be viewed as a generalization of PCA that additionally takes the DNN model into account. However the resulting "principal components" are not guaranteed to be interpretable to humans. We thus build on the concept-interpretablliy principles proposed in Ghorbani et al. (2019), and additionally consider carefully designed objectives that favors concepts that are more semantically meaningful to humans. A key facet of our approach is that it can work without any human supervision, which reduces the human labeling cost to provide explanations.
After set of highly-complete concepts are discovered, we game-theoretic notions to aggregate over sets to define contextualized importance a concept, which we call ConceptSHAP Concept- SHAP is shown to be the only scoring method that satisfies set of axioms, which accounts for the contribution of each concept to the completeness score. We also derive a class -saasffc version of ConceptSHAP that decomposes the ConceptSHAP score with respect to each class in the multi-class classification setting, which can be used to find concepts that contribute the most with respect to a specific class. To verify the effectiveness of completeness-aware concept discovery method, create a synthetic dataset where we can obtain the ground truth concepts and test whether existing methods can retrieve them. We find that our method able retrieve the ground truth concepts better than all compared methods. We also demonstrate examples from real-world language and vision datasets show that our concept discovery algorithm provides additional insights on the behavior of the model.
COMPLETENESS OF CONCEPTS
Problem setting: We are given a set of n training examples X2, X,, R., corresponding labels y1, 12: -.. Va Ro, and a DNN f(x) that is learned map the labels (with dimension o)
2

---

Under review as a conference paper at ICLR 2020
from given inputs (with dimension t). We choose intermediate layer of the DNN, and define the
operation for generating the intermediate features from input as ((x) E Rd and feed forwarding from the intermediate layer to logit layer h(-), yielding the decomposition f(x) h (x(())) We
define the data matrix as E Rix;; the corresponding feature matrix as Φ (X) E RRdx and the corresponding prediction matrix as f(X) e Rex", Assume that there is set of m concepts denoted
by vectors C12 ..., Cm that represented linear directions in some activation space ((-) E 1 given by a concept discovery algorithm. We define the concept matrix as с == [c] C2 .... Cm
Next, we propose two mathematical definitions that capture the completeness of a given set of given concepts. Both definitions are based on the idea that completeness should quantify how sufficient a particular set of concepts are in explaining the model's behavior. A low completeness score of a set of concepts indicates that the corresponding concepts do not capture the model behavior fully, and that the model bases its decision on factors other than the given concepts. We propose two metrics of completenss based on two different assumptions, as we discuss below.
If the given set of concepts is complete, then using projection of the intermediate features from input onto the feature subspace spanned by the concepts, concept space, would not deteriorate the model performance. We define the projection of some imput embedding (xx) onto the subspace spanned by v E Rd as
Assumption I:
P(O(x).v) = v(v v(vTv)-'vv (xx).
(1)
We define the completeness metric 11(1) on a set of validation data with T data points as V [(x1, Vi),,.., (Xr,9T)) based on the assumption that projecting input features onto the span of complete set of concepts should not reduce the model prediction performance.
Definition 2.1. Given prediction model (x) h hx((x)), a set of concept vectors C1,, Cya and some loss metric L, define the completeness score (7 as:
(cI, Cm) - Exyyer (((P((()))))).))
R. [xxxjee L(f(x).))
where R= Exxeyeev ((h(O),)) y) to ensure that 1y (0) O. We omit the dependency of h(-), ((-). f()) and L(-) of 77(-) for notation simplicity. When 17 ()) ..., .... Cm) is high, the network maintains high accuracy even after projection, which supports that the set of discovered concepts hold sufficient information for prediction.
The second assumption is that if we remove all useful concept information for a classification task, the model should fail to discriminate different classes. Thus, when all salient information is removed from the network, predictions scores for examples in class A won't be much different from other examples in class A. We define the data matrix of validation set as as X, [x] X2... xr]. To quantify how much the prediction score varies across data samples, we use the sample variance of the predictions: vax))(X.)) Tr(c)v(((X.))) = Tx((f(X.) [[(((,))) where [[](Xx)) E fxx), and Tr stands for the trace. Then, define the second completeness metric following this assumption.
Assumption 2:
{[S(X,))))
Definition 2.2. Given prediction model f(x) h(o(x)), and a set of concept vectors C₁, C2, ... C.r
we define the completeness score 17 as:
(2) (CI,.,, Cm) =1=1 vår vār(h(((X.) - P()(X.).)))
vār(h((((.)))
Based on our assumption 2, the variance of the prediction gets lower after useful concept information removed from the data, yielding a high completeness score 12(
We now show that under degenerate assumptions, the top & PCA vectors of +(x) maximize the completeness score for a set of concept vectors. Top PCA vectors are designed to capture as much information in data as possible, set of concepts with high completeness score similarly preserve the necessary information in the data for the model to reach satisfactory predictions.
Proposition 2.1. When h is an isometry function that maps from (f(.), II (Ie) - (f(). VL) where L is the loss metric in equation 2 and f(x:) ye, V(I,, U.) V (L.e. the loss is minimized), the first
PCA vectors maximizes nf
3

---

Under review as a conference paper at ICLR 2020
When h is isometry function that maps from (9(),,1 -f()) 1- (I and each dimension of (xx) is uncorrelated with unit variance, the first m PCA vectors maximize 17
Proposition 2.2.
We underline the two main differences between the concept vectors that maximize the completeness score and the PCA vectors. First, the propositions depend on degeneracy assumptions such as isometry of a DNN, which may not hold in practice. Therefore, the concepts that maximize the completeness score takes the prediction of the DNN into account, which can be seen original PCA. Second, since the concept score only depends on the span of the set of concept vectors, any concept vectors whose span is equal to the span of the top PCA vectors also maximize the completeness score (i.e. the set of vectors that maximize the completeness is not unique). Each PCA vectors are constrained to minimize the reconstruction eтror and being orthogonal to other PCA directions. On the other hand, the discovered concept vectors that maximize the completeness can be designed so that each concept is interpretable and aimantically-meaningee further explained in the next section.
generalization of the
humans, which will be
3 DISCOVERING COMPLETE AND INTERPRETABLE CONCEPTS
concepts, where each concept is also interpretable Ghorbani et al. (2019) has listed meaningfulness, coherency, and saliency as the desired properties for concept- based explanations. Our work on completeness is crucial addition to the set: not only concept are meaningful coherent and salient, we ensure they are sufficient to models prediction.
Our goal is to discover a set of and mamantically-meninnghh
We assume that we are given some candidate clusters of concepts (which can be given by human labeling self-discovery) and each cluster shares some feature attributes that are coherent and comantically-meainngghh to humans (which matches the two desired properties in Ghorbani al. (2019). We define the feature matrix of cluster i as T, = [$(x,1 $(x2)) ........... J. where X,1 X42 samples that belong to cluster i. We denote the feature mean of cluster i as μ4 = mean (T;). Clusters can be obtained by human labeling (Kim et al. 2018) or by unsupervised grouping of relevant input features (e.g. segmentation of images based on grouping of pixels) (Ghorbani et al.) (201)). In either case, we would not know which sets of clusters contain useful information the model that we try to explain. We aim to find a minimum set of concepts that are meximallly-ooplle to the prediction model. Additionally, we constraint that each concept salient one cluster only that each concept direction is semantically-mannnnffi to humans. To discriminate different concepts (for coherency). we constraint that different concepts are not salient to the same cluster.
We now define our objective function for discovering a set of complete and interpretable concepts C. A primary goal is maximizing completeness 7) (which can be 1) or 1)(2),, such that the set of concepts fully explain the model behavior. Besides, introduce two regularization terms for interpretability (can be considered as generalization of the orthogonality constraint of PCA). We introduce cluster-sparsity regularization Lspanse.c(())) to encourage each concept is salient to minimum number of clusters, and we introduce joncept-sparsigy regularization Ispprre: (c) to encourage different concepts are not salient to the same cluster, i.e. each cluster to be salient to at most one concept. Given some clusters TI, T2: ... TK. set of training examples X1, X2, ...; Xn, and pre-trained prediction model f(x) = h (x)()))
)), the overall objective function (to minimize) becomes:
n((c) + λ1 LSparse.ci(c) + A2- LSSpars,Con(C))
where \ and A2 are loss coefficients. To formulate the cluster-sparsity regularization Leparse, (((()) and concept-sparsity regularization LSparse,Con (C), we first formally introduce the saliency score between concept c, to cluster 7
Kc,, pk)
p(c,, Tk)
V VEK Kcj,mi\3
We note that the saliency score is normalized such that the saliency score between any concept and all clusters has unit norm. When the saliency score between concept c, to cluster T. is large, Cj can differentiate samples from cluster k from samples in random cluster, and thus cj is salient to тk- To encourage that each concept can differentiate a small amount of clusters to random clusters, we regularize the I.1 norm of saliency score for every concept-cluster pair (which can be seen as the
4

---

Under review as a conference paper at ICLR 2020
sparse filtering objective in Ngiam et al. (2011), leading the cluster-sparsity regularization loss:
K
Lsparse, Ci (c)
Σ ==1
Σ
p(cj, Tk),
which encourages sparse saliency scores. To constrain that different concepts are not salient to the same cluster, penalize the pairwise saliency score product between every pair of concepts for the same cluster, leading to the concept-sparsity regularization loss:
K = Σ Σ (4
Sparee, Cooprrs,Coo&fee Con (c)
p(c,, Tu) p(c,,
there are two concepts that are both salient with respect to the same cluster, the pairwise saliency score will be large and thus the concept-sparsity regularization loss will be large. We note that each concept has to be salient to some cluster, but a cluster can be not salient to any concepts. Therefore, typically assume we have more clusters compared to concepts (i.e. K >> m.)
How IMPORTANT IS EACH CONCEPT?
ConceptSHAP to quantify concept importance: Given set of concepts Cs = C2
C2....
with high completeness score, would like evaluate the importance of each individual concept, specifically, by quantifying how much each individual concept contributes to the final completeness score. Let Φ; denote the importance score for concept C. such that Φi quantifies how much of the completeness score r7(ss) is contributed by C,. Motivated by its successful applications in quantifying attributes in what-if scenarios for complex systems, we adapt Shapley values (Shapley 1988 Lundberg & Lee 2017). fairly assign the importance of each concept (which abbreviate as ConceptSHAP):
Definition 4.1. Given set of concepts Cs = {c1, C.... } and some completeness metric we define the ConceptSHAP Φ; for concept c; as
(m |S| - S)!!!!
(b(T)
Σ
[In(S U (c:)) (S))..
m!!
SEC.
The main benefit of using Shapley value to assign importance is that Shapley value can be shown to uniquely satisfy set of desired axioms, listed in the following proposition:
Proposition 4.1. Given a set of concepts Cs = (2,,,2, cm and completeness metric n, and some importance score de for each concept c, that depends on the completeness metric n. 6s defined by conceptSHAP is the unique importance assignment that satisfy the following four axioms:
Efficiency: The sum of all importance value should sum up to the total completeness value, Em (b(1)) = n.Cs).
Symmetry: For two equivalent concepts, which satisfy 7fu (c:)) 1/(u (cg)) for every subset u S Cs) Cz}, Φs(1)) (n).
Dummy: Ifnuu u (c:)) vu()) for every subset E CsMec.) then Φs(1) 0.
Additivity: if and of have importance value Φ(T) and ((n') respectively, then the impor- tance value of the sum of two completeness metric should be equal to the sum of the two importance values, iee de(n v/') = db(()) + (x(11') ) for all
The efficiency axiom distributes the completeness score of all concepts to the individual concepts. The symmetry axiom guarantees that two concepts that behaves the score for faireess. The dummy axiom guarantees that concepts that do not affect the completeness gets 0 importance score. The additivity axiom guarantees that decomposibility in the completeness leads to decomposibility in the importance score, and scaling the completeness does not change relative importance ratio between concepts.
get the same importance
5

---

Under review as a conference paper at ICLR 2020
1:+ 6:
11:
Ground Truth Concept 3. 6. 11, 12
Ground Truth Concept
2: Y 7: 12
2,4, 2,4,677,,112,1415
3:
* 8:
13:
4:
9:
14:
5: 10: 15:
Two random training images and the respecting ground truth concepts that are positive along with table that matches ground truth concepts shape. Each object shape in the image corresponds to a ground truth concept (with random color and location), and the ground truth label depends solely on ground truth concept 1 to 5. Only the training image and ground truth label provided during training (in the unsupervised case), and the goal of the discovering concept algorithm correctly retrieve ground truth concepts & to çs-
Figure 2:
Per-class saliency of concepts: In multi-class classification, it may be more informative to obtain set of related concepts that contribute to the prediction for a specific class, instead of the global contribution (i.e. concepts that are important to all classes). To obtain the concept importance score for each class, we first define the completeness score with respect to one class by only considering data points that belongs to that class, which is formalized as:
Definition 4.2. Given a prediction model f(x) h(((x)), a of concept vectors C ... Cyz that lie in the feature subspace in (-)). We then define the completeness score for class j as:
R2 - -xx,eee,, L(h(P(((x), c)),
(CI, Cm.)
(5)
R - Exx,tev L(f(x). v)
where Vy is the set of validation data where ground truth label is j and R3- (xx,jee,, L(h(O), v). Given the completeness for specific class, we define the ConceptSHAP for concept with respect to class j as:
Definition 4.3. Given prediction model f(x), set of concept vectors C1, C2, Cm that lie in the feature subspace in (-). We can define the ConceptSHAP for concept with respect to class j as:
(n)(1) 6. (1;))
(6)
For each class j. we may select the concepts with the highest conceptSHAP score with respect to class j. We note that Σ, M2 77 and thus with the additivity axiom, Σ, oi d.(1).
EXPERIMENTS
5.1 SYNTHETIC DATA WITH GROUND TRUTH CONCEPTS
Setting: We construct synthetic image dataset with known complete concepts to evaluate whether the proposed automatic concept discovery algorithm can successfully extract the ground truth concept accurately. For each sample, we randomly sample 15 15-dimensional binary variable assigned ground truth candidate concepts {1, ... Eıs that is generated with Bernoulli independently for each dimension with p 0.5. From ground truth concepts (E), we generate input data x and output label y. For the label target y. we construct a I 15-dimensional multi-label target for each sample, where the target y is function that depends
the first 5 dimension of the 15-dimensional g. For example, 31 =~ (E1 {3) E1, 32 = E + {a + &s. ground truth variable {E1, ..., {b} by construction. For the input data x, we construct a toy image dataset where each concept &, is mapped to specific shape, and the image contains the specific shape and only the concept & 1. For example, if Est 1, a star (with random color and location) will occur in the image x,, and if E3e O, there will be star in the image x,. The map of concept to shape and two example images are given in Figure 2
E2 E3 + & EE Therefore, the minimum set of
For the input cluster image for our discover concept algorithm, we either provide the ground truth clustering or by superpixel segmentation followed by K-means clustering as in Ghorbani et al. (2019) , which we call the method as ours-supervised and ours-unsuerrvieed respectively. In total, we use 48k training samples and 12k evaluation samples, where each ground truth concept corresponds to some specific shape in the image. We train convolutional neural network with 6 layers which achieves 0.999 accuracy, and take the first fully connected layer as the feature layer (which is +(x) in the problem definition.).
notes Not, and the details of generating this dataset in the appendix.

---

Under review as a conference paper at ICLR 2020
Ground Truth
ours supervised
TCAV
Ground-Truth
Concept 1
Concept
Fround-Truth Concept
Concept 2
Ground-Truth Concept
Concept
Ground-Truth
Concept 4
Concept
Ground-Truth
Concept 5
Concept
Figure Visualization Result for the nearest neighbors of each discovered concepts ours- supervised and TCAV along with ground truth concept to 5 that is constructed to be the minimum set of ground truth variable. We note that only the shape revelent of the concept, as the color and location can be random. We show that each of our discovered concepts in oupe-suped corresponds to one of ground truth concept to 5 (with a random order). While TCAV also shows meaningful discovered concepts, they fail to retrieve all ground truth concepts that are used by the model. Higher resolution examples will be shown the appendix due to space constraint.
Evaluation metrics: Let the known concepts f1. E2. ... Ema and assume we discover some concept vectors C1, .... Cm We would like to evaluate how closely the discovered concept vectors align with the actual ground truth concepts. For a concept vector c; to align with a ground truth concept Ej. we assume that the ground truth concept can be linearly separated by the concept vector direction. More formally, we measure the accuracy of the best linear classifier with c, as the weight vector applied on the binary classification problem where Ej is the target.
T [[(a- (x,)), > b) = -x,rl
Score(c,,E))
max as 1E(-111)).e
T
We then evaluate how well the set of discovered concepts C1...Cm matches the set of ground truth concepts E Ei as
1 max PS[Lm)] m
n
AlignemntScore( ( (c)) (- m
Acc(Cpt).E)) E,),
which measures the best average accuracy by assigning the best concept vector to differentiate each ground truth concept.
We summarize the results Table where ours-supervised and TCAV takes supervised clusters as input, and ours-unsupervised, ACE, Raw-Clustering takes the clustered segments input. For supervised clusters, we randomly choose examples where & = for cluster j. The term supervised and unsupervised refers whether the actual ground truth concept set ε is given not. For ours- supervised 1, we maximize (2 in equation 4 for ours-supervised 2, we maximize 17(2) in equation 4 We see that both ours-supervised and ours-supervised 2 obtain higher AlignemntScore compared TCAV. ours-unsupervised 1 and ours-unsupervised also achieves higher AlignemntScore than all compared baselines, which demonstrates the effectiveness of our concept discovery algorithm. We further observe that that completeness 1 and 2 are complementary: maximizing completeness does not necessary lead to higher value in completeness 2, and vice versa. Nevertheless, by jointly completeness along with additional sparsity regularization with respect to given clusters, we are able to retrieve the correct ground truth concepts. Lastly, we show the nearest neighbors (of the super-pixel segments) for the discovered concepts of ours supervised and TCAV along with the ground truth concepts in Figure B to validate that our concept discovering algorithm does retrieve the correct concept. While we only show the top-2 nearest neighbors, we note that the top-k nearest neighbors examples all belong the same concept when k is large.
Results:
optimizing completeness
7

---

Under review as a conference paper at ICLR 2020
Methods
x7(3)
AlignemntScore
ours-supervised
0.96
0.20
0.90
our--supervised 2
0.0
1.0
0.94
TCAV
0.0
0.30
0.82
ours ours-unsupervised
0.97
0.22
0.89
ours-unsupervised2
0.12
0.99
0.90
ACE
0.0
0.37
0.75
PCA
0.0
0.67
0,79
Raw Clustering
0.49
0.83
0.66
Table 1:
The Completeness and AlignemntScore for our methods compared to the baseline methods on synthetic dataset where ground truth can be obtained.
5.2 TEXT CLASSTFICATION
Setting: We apply our method on the IMDB text classification dataset. The IMDB dataset contains text of 50k movie reviews, where 25k reviews is used training data and 25k reviews are used for evaluation. For each review, it is either classified as positive or negative review. We use pre-trained model with a BERT language model (Devlin al. 2018) from Keras, which achieves 0.94 testing accuracy. To obtain the input cluster, we use 10- [0-word sliding window to obtain sub-sentences over the IMDB sentences. We then obtain the embedding for sub-sentences, and perform k-means clustering on the positive sub-sentences and negative sub-sentences. We then run our concept discovering algorithm to obtain 5 concepts with (1 0.99.
Concepts
Nearest Neighbors
ConceptSHAP
Related Class
Concept
plot boring the characters are neurotic needlessly offensive characters jess bhamra parminder nagra and jules paxton keira average chop socky all of the cast are likeable characters
0.13
neg
Concept 2
that keeps reappearing the scene where you think
she deserved more studied finale than that think
0.29
neg
think no sometimes hatred and isolation are deeper are more
Concept 3
think the most frustrating thing is that the performances you might think see organs yanked many people think has an underlying meaning the love between
0.15
neg
the
Concept 4
don't t wait for to be a classic watch it has real potential and will be one watch in recommend you watch if you like mature
0.43
Concept 5
children trying to comfort them after that is all said paid well after all acting one of the it after watching you will say that it
0.21
Table 2: Concepts and their nearest neighbors, ConceptSHAP values, and related class in IMDB.
For the 5 discovered concepts, we show the top nearest neighbors to each concept, and the ConceptSHAP value and related class (determined by TCAV score) for each concept discovered. Additional nearest-neighhor examples are shown in the appendix. We note that for all concepts, the nearest sub-sentences of other concepts mostly contain a specific word, which highlight in blue. Nearest neighbors of concept mostly contains the word "characters", nearest neighbors of concept 2 and concept mostly contains the word "think", nearest neighbors of concept 4 mostly contains the word "watch". and nearest neighbors of concept 5 mostly contains the word "after". With closer look at each concept's ' nearest neighbors, we find that the nearest sub-sentences of the first concept usually contains negative adjectives alongside "characters", nearest sub-sentences of the second concept usually contains the word "think" at the first or last position followed by disagreement towards the movie, nearest sub-sentences of the third concept usually contains "think" in the middle of the sub-sentence followed by the reviewer's more neutral personal opinion, the nearest sub- sebbeenttnnes of the fourth concept often contain the phrase "watch it" where "it" refers to the movie, and the nearest sub-sentences of the fifth concept just contains the word "after". We find that the most salient concept by ConceptSHAP value is the concept 4, where all of the top nearest.
Results:
8

---

Under review as a conference paper at ICLR 2020
Concepts
Nearest Neighbors
SHAP
Related Classes
horse, lon
stripe
0.126
panda, hippopolarmus, wearus, walf
ripple
0.120
bobcal, collie,
stripe 2
0.124
leaf/
antelope. bat. deer. hamster, mouse, tiger,
branch
0.121
grizzly- bear, raccoon
grass
0.08
thick
dalmatian, leopard, otter, squirrel
snow
0.109
whale, delphin, mole, spider-monkey
ripple
0.105
persian-cal, polar-bear, minoceros, siamese-cat, skunk
dots
0.124
Figure 4: The Nearest Neighbors, ConceptSHAP, and related class for each concept obtained in AwA.
neighbors explicitly mentioned the word "watch" with positive sentiment in general. We perform TCAV test for all concepts with respect to the positive and negative class, and the first 3 concepts are significant to the class "negative" with TCAV score and the last 2 concepts are significant the class "positive" with TCAV score 1.
5.3 IMAGE CLASSIFICATION
Setting: We next perform experiments on Animals with Attribute (AwA) (Lampert et al. 2009) to classify animals with 50 classes, where we take 26905 images as training data and 2965 images as evaluation data. Each training data has a ground truth label one of 50 animals. We train an Inception-V? V3 model pre-trained Imagenet (Szegedy et al. 2016) which reaches 0.94 testing accuracy. To obtain the input clusters, we employ the method of Ghorbani et al. (2019), which performs superpixel segmentation and k-means clustering with images to get 334 input clusters. We then perform our discovering concepts algorithm given the clusters to obtain concepts with r7(1) 0.99.
For each of the 8 discovered concepts, show the top nearest neighbor patches, the Con- ceptSHAP value, and the related classes where the concept has at least twice as large ConceptSHAP value than any other concepts. From the nearest neighbor of each concept, learned by the network mostly consider textures and colors. Since we only learn 8 concepts for 50 classes, each concepts learned are useful to multiple classes. We find that the ripple texture that is the most common in ocean is significant to many marine animals. The leaf/ grass concepts are often significant to animals that live trees or pastures. We note that out the 8 concepts learned, there are two concepts representing stripes and two concepts representing ripples. While the concept "stripe 1" seems to contain thicker stripes compared "stripe 2", we do not observe significant difference between the top nearest neighbors of "ripple 1" and "ripple 2". Other than this, each discovered concept seems to meaningful and coherent to humans. We note that some cases the related class of concept may not necessarily contains the concept. One possible reason is that the concepts may be salient since they are "pertinent negative" to a certain class, which helps making the correct prediction since these concepts do not exist in images of a certain class. The main takeaway of this example that the salient concepts for image classification shares similarity in texture instead of shape, which coincides with the finding in Geirhos al. (0188)
Results:
find that the concepts

---

Under review as a conference paper at ICLR 2020
6 RELATED WORK
Various approaches have been proposed explain the decision making of pre- pre-trained models. Most works fall under two categories: (i) feature-based explanation methods, that attribute the decision to important input features (Ribeiro al. 2016 Lundberg & Lee 2017 Smilkov al. 2017 Chen et al.
2018), and (ii) sample-baser explanation methods, that attribute the decision to previously observed samples (Koh & Liang, 2017 Ych et al. 2018; Khanna et al. 2019 Arik & Plister, 2019). Among
these forms of interpretability, different evaluations of explanations are proposed, including more human-centric evaluations (Lundberg & Lee 2017 Kim et al. 2018) and functional ly- groouuddddd
evaluations (Samek et al., [016]] Kim et al.] 2016; Ancona et al. 2017 Yeh et al.. 2019). However, providing the most important input features or samples for a specific prediction does not necessary give insights on how the model behaves globally, which our work aims to address with concept-based explanations. For concept-based explanations, few recent works are related. TCAV (Kim et al. 2018) use human-labeled data and estimates the importance of concept with respect to specific class. Zhou et al. (2018) decompose the prediction of a data sample into linear combinations of concept components. GGhorbani et al. 2019) automate TCAV by replacing human-labeled data by automatically super-pixel segmentation followed by k-means clustering. [Bouchacourt & Denoyer (2019) discover concept by training a inherently explainable model which trains a concept classifier along with the prediction model. While all aforementioned works defines concept directions in the linear span of some activation layer of the model, our framework brings completeness and interpretability to concept discovery.
Our work is also closely related to methods that perform dimension reduction in neural network layers to obtain meaningful latent variables and understand neural network. CCan et al. (2015) cascade PCA layers to obtain satisfactory prediction performances. Raghu et al. (2017) apply SVD followed by CCA to compare two representations of deep model to help better understand the deep representations. Kingma & Welling (2013) perform deep dimension reduction for generative models where the latent space can be aemantically-mmnnnnnghh that when learning with speech data, the latent dimension is closely related to the phonemes, which can be seen as numan-relatablee concepts in speech data; or Raddford et al. (2017) show that when learning with language data, a single unit is closely related to the sentiment.
For example. Chorowski et al. (2019) show
CONCLUSIONS
Concept-based explanations can a key direction to understand how DNNs make decisions. In this paper, we study concept-based explainability in systematic framework. First, we define the notion of completeness, which quantifies how sufficient a particular set of concepts is in explaining the model's behavior. Based on performance and variability motivations, we propose two definitions to quantify completeness. We show that they yield the commonly assumptions. Next, we study two additional constraints ensure the interpretability of discovered concept. Through experiments in toy data, text, and image domain, we demonstrate that our method effective in finding concepts that are complete (in explaining the model's prediction) and that are interpretable. Note that although our work focuses on post-hoc explainability of pre-trained DNNs, joint training with our proposed objective function can also be used train an model. A future direction may be to explore whether jointly learning the concepts and the model can lead to better interpretability.
PCA method under certain
REFERENCES
Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross. Towards better understanding of gradient- based attribution methods for deep neural networks. arXiv preprint urXiv:1711.06100 2017.
Sercan Ömer Arik and Tomas Pfister. Attention-based prototypical learning towards interpretable, confident and robust deep neural networks. arXiv: 2019.
Sharon Lee Armstrong, Lila R. Gleitman, and Henry Gleitman. What some concepts might not be. Cognition, 13(3):263- 308, 1983. ISSN 0010-0277.
Diane Bouchacourt and Ludovic Denoyer. Educe: Explaining model decisions through unsupervised concepts extraction. arXiv preprint arXiv: 1905. 1852, 2019.
10

---

Under review as a conference paper at ICLR 2020
Tsung-Ham Chan, Kui Jia, Shenghua Gao, Jiwen Lu, Zinan Zeng, and Yi Ma. Pcanet: A simple deep learning baseline for image classification? IEEE transactions on image processing. 24(12): 5017-5032, 2015.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. L-shapley and c-shapley: Efficient model interpretation for structured data. arXiv: m00::80088000 808.02610, 2018.
Jan Chorowski, Ron J Weiss, Samy Bengio, and Aäron van den Oord. Unsupervised speech representation learning using wavenet autoencoders. arXiv preprint arXiv:/901.000 2019.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 181.v:810000480)) 2018.
Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A Wichmann, and Wieland Brendel. Imagenet- enns are biased towards texture; increasing shape bias improves accuracy and robustness. arXiv preprint arXiv: 181 12231, 2018.
Amirata Ghorbani, James Wexler, James Zou, and Been Kim. Towards automatic concept-based explanations. Advances in Neural Information Processing Systems, 2019.
Leilani H Gilpin, David Bau, Ben Z. Yuan, Ayesha Bajwa, Michael Specter, and Lalana Kagal. Explaining explanations: An overview of interpretability of machine learning. In 2018 IEEE 5th International Conference on data science and advanced analytics (DSAA), pp. 80-89. IEBE, 2018.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Rajiv Khanna, Been Kim, Joydeep Ghosh, and Sanmi Koyejo. Interpreting black box predictions using fisher kernels. The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3382 3390, 2019.
Been Kim, Rajiv Khanna, and Oluwasanmi Koyejo. Examples are not enough, learn to criticize! criticism for interpretability. In Advances in Neural Information Processing Systems, pp. 2280- 2288, 2016.
Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, al. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav). In International Conference Machine Learning, pp. 2673-2682, 2018.
Diederik P Kingma and Max Welling. 1rXiv:1312.6114, 2013.
Auto-encoding variational bayes, arXiv preprint
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1885-1894 JMLR. org, 2017.
Christoph Lampert, Hannes Nickisch, and Stefan Harmeling. Learning detect unseen object classes by between-class attribute transfer. In 2009 IEEE Conference Computer Vision and Puttern Recognition, pp. 951-958. IEEE, 2009.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pp. 4765-4774, 2017.
Jiquan Ngiam, Zhenghao Chen, Sonia A Bhaskar, Pang W Koh, and Andrew Y Ng. Sparse filtering. In Advances in neural information processing systems, pp. 1125-1133, 201
Alec Radford, Rafal Józefowicz, and Ilya Sutskever. Learning to generate reviews and discovering sentiment. 1wXiv:170..01444 2017.
Maithra Raghu, Justin Gilmer, Jason Yosinski. and Jascha Sohl-Dickstein. Sveca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability. In Advances in Neural Information Processing Systems, pp. 6076-6085, 2017.
11

---

Under review as a conference paper at ICLR 2020
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1 1135-1144. ACM, 2016.
Wojeiech Samek, Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, and Klaus-Robert Müller. Evaluating the visualization of what a deep neural network has learned. IEEE transactions on neural networks and learning systems, 28 (811):2660-222 -6736 2016.
Lloyd S. Shapley. value for n-person games, pp. 40.00. Cambridge University Press, 1988. doi: 00017/CB0977011558444600
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smoothgrad: removing noise by adding noise. arXiv preprint TrXxvv/706.08822 2017.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigmiew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826, 2016.
Joshua Brett Tenenbaum. A Bayesian framework for concept learning. PhD thesis, Massachusetts Institute Technology, 1999.
Fan Yang, Mengnan Du, and Xia Hu. Evaluating explanation without ground truth in interpretable machine learning. arXiv preprint arXiv:1907.06831, 2019.
Chih-Kual Yeh, Joon Kim, Ian En-Hsu Yen, and Pradeep K Ravikumar. Representer point selection for explaining deep neural networks. In Advances in Neural Information Processing Systems, pp. 2018
Khin Yeh, Cheng- Yu Hsieh, Arun Sai Suggala, David Inouye, and Pradeep Ravikumar. On the 2019.
(in)fidelity and sensitivity of explanations. arXiv preprint
Bolei Zhou, Yiyou Sun, David Bau, and Antonio Torralba. Interpretable basis decomposition for visual explanation. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 119-1344 2018
Barret Zoph, Vijay Vasudevan, Jonathon Shiens, and Quoc V. Le. Learning transferable architectures for scalable image recognition. arXiv: 1707.07012, 2017.
12

---

Under review as a conference paper at ICLR 2020
APPENDIX A PROOF
Proof of Proposition 2.1
Proof. By the basic properties of PCA, the first m PCA vectors (principal components) minimize the reconstruction l error. Define the concatenation of the m PCA vectors as matrix p and as the l norm, the basic properties of PCA is equivalent to that for all c [c] C2... cm.
Σ V
[P(((())
((x)
Σ IP(((x), (3 X
By the isometry of h from the Frobenius norm to vL, we have
Σ (((x)) & Σ (MMP((E))C)) XEVX
X
and since f(x) is equal to Y, we can rewrite to
Σ
L))
&
Σ L(M((((xx.c))..))
X.DEV
X.PEV
and subsequently get that for any
E(xwlev L(((P(((x),))).))
R - -(xxn/y (1)(P(((x),.))..)
R > (x.)eVV Lx](x).
> (xx))V L(J(x),
Proof of Proposistion 2.2
Proof. We note that the completeness only depends on the span of Cm....Cm- If we assume the matrix e to have rank m & m, we may find a of orthonormal basis (by QR decomposition) .m....Cm'' that is orthonormal with the same completeness score. Therefore, for any set of given concepts C1, we can replace them with a set of orthonormal concepts C₁, Cm without loss of generality. By the basic properties of PCA, the first PCA vectors p .... Pm maximizes the total projection data variance on the projected space with at most m orthonormal vectors, which can formalized as
Σ (a.) P:)
(T.)))))Tc)))
By using the notation el for the j entry of vector e, we may rewrite total projected variance as
m'
vār( (xx)) [c))
Σ
var (Xx) c2) Σ (c())
m
var (aX.)(X))) TT, (c,))²
d m
vår( (Xx)) Tc, ccc(
(8)
vär Σ ((X.) c,c(,))
Tx..)
Σ vār(P(@(X..,.))))
var())(((X.).)).
13

---

Under review as a conference paper at ICLR 2020
The fourth equality holds since ((X,)c, and ((X,)c, are uncorrelated, which can be shown by calculating the co-variance between & ((Xx)c, c, and ((Xx)e, as:
(o(X,)c, (x c.))( 9 Ex(o(x,) c,])
(0x Ex(
Σ (x) -x(((X.))0f1
d
Σ
Ex (xx)
(c)
Ex Ex[ 1xx
of
(=18=1
1=1==
Σ
(0
vär (X,, (c -0000 c 0.
Where the last two equations follow by each dimension of Φ (x.) is uncorrelated with unit variance and c, and cj is uncorrelated. By plugging in equation into equation A we may obtain
((r(P()(X.), p)) > vār(P(((X.).c)).
Define è the concatenated matrix for the orthonormal basis for orthogonal complement of and define Call by concatenating с and è. We know ((X)) P($(Xp).c) = (( è) by fundamental properties of linear projections. Since all vectors in is orthogonal to vectors in ? and by pluggin in equation for Calt, we get vår( (ar(P(((X.,)) c)) + (ar))) ē)) vår( P (X)),, Catt) vår + (x))). By combining the observations we get
(ar)) P()(())) = vár(P(((X.),,))
vår(o((,,)) vár(P((((...c)) c))
var() vār(P((((,,))
var(P(((X.)..))
= vår( - (( p)).
and following the isometry of D, we have
vār(h(((X..) (((((.))))))) p))) < vār(h(((X.)) ([C[((((X)--P((Xx...))))
and thus the first m PCA vectors maximizes 1/2-
14

---

Under review as a conference paper at ICLR 2020
APPENDIX B ADDITIONAL EXPERIMENTS RESULTS AND SETTINGS
Detailed Experiment Settings in Toy Example
The complete list of the target y is y1 =~ (f1 E Σ3 + E4 [b. y/
Ea) + 1/2 E2 Ea + E4: 1/3
{2 XOR E,, yo
E2 + [b: yo
+ (&1 + 66
(52 E3) XOR Eo. Vs- E1 E6 22, yo = E3. 9/0 = (5I {2) XOR E4, 311 =~
(Es (5)-)s)..0 V12 = E1 Ea E5 V13 E2 XOR Es. V/4
(G1 Es Ea). 915 Ea XOR Es.
We create the dataset in matplotlib, where the color of each shape is sampled independently from green, www.:llwl..ee.bbb.rreeaaoooee.a. www.ge.purpll.............
and the location is sampled randomly with the constraint that different shapes do not coincide with each other. For syper-parameter selection, we simply set A1 X2 10.0. We fix this tuning and over-fitting. Scaling the typer-paramees in the same order produces similar results. We use 1000 images in each cluster for all methods that are compared. For selecting the concepts in TCAV and ACE, we compare the number of labels where the concept has p-value < 0.16 and choose the top concepts (since even TCAV score 1.0 does not have p-value < 0.05). We note that we have tried many alternatives for choosing concepts for TCAV and ACE, but failed to achieve better performance for TCAV and ACE. The main reason may be that the ground truth y contains functional such XOR, which has O TCAV score for inputs.
throughout all experiments to prevent exhaustive
For a more concrete example, consider the case Y = X1 XOR X2, and assume that we have concepts candidates X1, X2, X3. All 3 concepts would have 0 TCAV score when each concept has independent Bernoulli distribution with p = 0.5. Therefore, TCAV will choose X1, X2, X3 with an equal probability. Although our method also produces linear concept direction, the completeness measure for {X1. X2] would be I, while the completeness measure for completeness measure for (X1,X3) and (X2, X3) would be far less than 1. The reason is that we project the activation space onto the concept space, and then pass through the remaining model to get our result. By projecting the activation space onto the span of (X1, X2), we can still get Y X2 XOR X2. On the other hand, if we project the activation space onto X3). the information of X2 would be loss, and thus we get a much worse completeness score. The key difference between our method and TCAV is that we feed the projected activations back into the original model (which is h(.) in our problem setting), which may capture the non-limes relationship between the projected space and the output. Such a non-linear relationship might be neglected in the TCAV score.
Implementation Details For calculating ConceptSHAP, we use the method in kernelSHAP (Lund- berg & Lee 2017) to calculate the Shapley values efficiently. Before calculating the nearest neighbor, we ensure that the dot product between each concept vector and its most salient cluster mean has a positive dot product (if it negative, we take the negative of the concept vector as the new concept vector, which does not effect the loss at all). For the input cluster proposals in AwA, we follow the code of ? and their hyper-parameters. For input cluster Imdb, we obtain 500 clusters from positive sub-sentences and 500 clusters from negative sub-sentences by k-means clustering. We train a linear classifier differentiating the cluster segments and random segments, and remove clusters with accuracy lower than 0.95. We also remove clusters that have less than 100 elements. For input cluster proposals in the toy dataset, we used k-means clustering with 20 clusters.
We show addition nearest neighbors for each concept obtained in IMDB in Figure We observe that some top nearest sub-sentences of concept 2 and concept 3 do not have the word "think" in it. The top nearest neighbors concept generally has a tone that encourages readers of the review to watch the movie, which is probably why it has the largest ConceptSHAP score.
Additional Nearest Neighbors for IMDB
Additional Nearest Neighbors for AwA We show addition nearest neighbors for each concept obtained in AwA in Figure/o The nearest neighbors all share the same texture. Interestingly, some of the nearest neighbors ripple 2 are not exactly ripple, but tree/leaves that share similar texture as ripple. Some nearest neighbors of dots contains dots from leaves instead of pure dots on animals. This again validates that the concepts are based on the texture of the image.
15

---

Under review as a conference paper at ICLR 2020
characters fun to watch and you can see the decided actually watch this film found the characters well fire against ice with characters named nekron and darkwolf and passion for the future the characters of jesse hawke different and thought the main characters suspiciously dressed like characters ranma you would think making him strong would characters for your enjoyment only watch neverending immoral relationships of the show's characters everybody seems kurosawa weaves a tale that has a cast of characters
Concept
go and
that keeps on reappearing to the scene where you think she deserved a more studied finale than that think think no sometimes hatred and isolation are deeper are more think established the trade in african slaves the first that has produced such excellent comedies seems to think think that by having this man's face on their chest that has since fell into disrepair and who would think will pull you in make you laugh make you think are sometimes entertaining by virtue of their very datedness flared
Concept 2
think the most frustrating thing is that the performances you might think to see organs yanked out of the noise when he eventually kills him by scraping his many people think has underlying meaning the love between i'll admit think uma thurman is the most beautiful like to think have a better grasp on asian think they were proper actor's rather than friends or son zizek may object that she also evidently enjoys rough also when watch gunga din think of star
Concept 3
make and its nice for your kids to watch and this movie and it becomes something you watch without have to type that geek because totally watch this ever made all of you must watch this perfection 10 ok then my friends at work said watch again into play and he is never boring to watch he what kind of movie you're about to watch father makes also forced 4 my friends watch it with around your head you will want to watch this
Concept 4
soon after their version of the film made and paid well after acting soon watching right after this little girl killed the first person very america for me was dreading watching this after all the it after watching you will say that was enjoyable movie after opening that would best the film again after several years without seeing this again after watching the was like
of the you will realize why
Concept 5
Figure Additional Nearest Neighbors for each concept obtained in IMDB.
16

---

Under review as a conference paper at ICLR 2020
stripe
ripple
stripe 2
leaf/
branch
grass
thick
snow
ripple
dots
Figure 6: More Nearest Neighbors for each concept obtained in AwA.
17

---

Under review as a conference paper at ICLR 2020
APPENDIX C ADDITIONAL EXPERIMENTS
Throughout this section, we refer to v7(1) when the term completeness score is mentioned for the simplicity of presentation.
C.I
We run a controlled experiment different À = A1 X2 values for our concept discovery algorithm to show the robustness of our algorithm against different ayper-parameters. We also perform an ablation study when we do not optimize for the completeness score, which we call ours _urs__nsup" and ours_supp ours_sup". We summarize the result in Figure] 7 We observe that our method outperforms the baselines for À E [0.5, 50]. This shows that concept discovery algorithm is robust with respect to the hyper- aiper-paramete A. We also observe that for the controlled version where the completeness score not optimized, the alignment score and completeness score is worse compared to the baselines. This shows that the completeness objective is essential in obtaining complete and correct concepts in our algorithm.
ours-unsup
ours-sup
ourg_unsup"
ours-unsup
oure-sup
terouuuuueee curs_uneup"
ours sup
sup"
0.9
0.8
0.7
0.6
0.25
0.5
0.5
50
0.5
1
5
10
50
lambda
lambda
(a) Alignment score for different À values.
(b) Completeness score for different values.
Figure The alignment score and completeness score for our method with different hyper-parameter for the toy dataset.
18

---

Under review as a conference paper at ICLR 2020
C.2 NUMBER OF CONCEPTS
We show the performance metric when different number of concepts retrieved for both our concept discovery algorithm and the baselines in the toy dataset as well as the AwA dataset respectively in figure 8 and 9 In the toy dataset, we observe that the completeness for all the baselines compared to the completeness of our method. On the other hand, the alignment score of our method increases more significantly compared to the baselines when the number of concepts increases from to 9. Only ours-sup and ours-umsup achieves a high completeness score when the concepi number is larger or equal 4, which may explain the superior performance of our method on the alignment score. As we have argued in the introduction, concepts that are not complete fails to "fully" interpret the model, and thus since most baseline methods are not complete, they fail reach a high alignment score. On the other hand, our method which obtains high completeness score achieves a high alignment score.
low
ours-sup
ours-unsup
TCAV
PCA
ACE
ours-sup
ours-unsup
TCAV
PCA
ACE
0.75
0.8
0.5
0.7
0.25
0.6
0.5
2
8
number of concepts
number of concepts
(a) Alignment score for different number of concepts. (b) Completeness score for different number of concepts.
Figure 8: The alignment score and completeness score for all methods with different number of discovered concepts are chosen for the toy dataset.
For the AwA dataset, we only show the completeness score for different algorithms with increasing number of concepts. We observe that the completeness of our method much higher than ACE and PCA. We note that PCA still achieves satisfactory completeness score when the number of concepts is high. This is not surprising since we proved Proposition 2.I that PCA maximizes the completeness under isometry of the model. We point out that larger number of total concepts makes the interpretation more understandable by human, and thus more interpretable. However, the explanation obtained by PCA is only close to complete (i.e. has completeness larger than 0.95) with 29 concepts. This experiment provides additional empirical support that PCA obtains worse completeness score compared to our method, which may only be caused that the isometry (and perfect accuracy) assumption not holding in practice. This further validates the effectiveness of our method against naive PCA.
PCA
ACE
ours
0.75
0.5
0.25
5
10
15
20
25
number of concepts
Figure 9: Completeness score for different number of concepts in AwA.
19

---

Under review as a conference paper at ICLR 2020
C.3 ROBUSTNESS AGAINST NOISE
We would also be interested in how the completeness metric may change when the input is slightly perturbed. We perform an experiment input in the validation set. We plot the completeness score against different standard deviation for each dimension of the added noise in Figure I0 We observe that the completeness score still above 0.96 even when a multivariate Gaussian noise with standard deviation 10 in each dimension is added the original input for all the validation set data. We further note that since the completeness score is calculated by all the validation data, perturbing only one validation point will cause negligible impact on the completeness score.
AwA where Gaussian random noise is added to all the
0.75
0.5
0.25
0
0.1
10
100
standard deviation
Figure 10: Completeness score for different standard deviation of added noise in AwA.
C.4 OPTIMIZING WITHOUT COMPLETENESS
We conduct an ablation study on how the result changes when we drop the completeness term in the main objective. The results for optimizing without completeness in the toy dataset has been shown by ours purs_unsup" and ours sup* in section C.I. which is much worse compared to ours with the completeness score optimized. We further show results of the concepts when optimizing without the completeness metric. We note that the completeness score is for AwA dataset. We further visualize the top nearest neighbors for the concepts that are optimized without the completeness metric in Figure II We observe that while some concepts are the same as ours when the completeness is optimized, it contains more concepts wheels and bars which does not seem be very related to the classification of animals. We notice that the top nearest neighbors are still coherent in general. This is not surprising since our cluster-sparsity regularizers enforces the discovered to be coherent, however, the result now may not be sufficient to models prediction since we dropped the completeness objective and the completeness score becomes O.
20

---

Under review as a conference paper at ICLR 2020
Figure 11: Nearest Neighbors for each concept obtained in AwA without the completeness metric.
21


Reviews:
[{"review_id": "Skl0BXmAcH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors are concerned with improving algorithms that propose sets of\nconcept vectors to help explain the prediction of a pre-trained network on a\nheld-out test examples. The paper examines \"completeness\" (Gilpin et al 2018) of\nthe context vector set---projecting activations on to the concept subspace does\nnot hurt predictive performance---as a desired criteria that was overlooked by\nprevious concept-based explanation methods. They show that PCA on activations\nyields complete concepts under some bijectivity assumption on the final layers\nof the network. They then discuss how to produce a set of concept vectors that\nmaximize completeness under sparsity priors when supervised or unsupervised\nclusters of candidate concepts are given. They also show that SHAP values can be\napplied to compute the relative importance of each concept to the overall\ncompleteness score.\n\nI find the focus of this research---on the completeness of concept\nexplanations---to be quite interesting and relevant to the interpretable machine\nlearning literature. The authors have approached this question from several\ndirections and have demonstrated a fluency with the existing literature and its\nlimitations. However, I think they could do much more to motivate their\nproposals by convincing the reader that (a) existing concept-based explanations\nare not complete in practice and (b) PCA in the activation space is not\nsufficient as a baseline method for proposing concepts. In the current revision,\nthe paper lacks coherency---the proposals in each section do not seem connected\nto one another---and it is difficult to assess from the experiments whether the\nproposed algorithms address a known problem in existing methods.\n\nFor example, the propositions in S2 rely on the ability of the post-concept\nfunction h to bijectively map between the Frobenius norm in the concept space to\nthe loss function in the logit space. Therefore it is logical to ask whether\nconcepts can be found directly via PCA on the concept space. The authors\nspeculate that this bijectivity of h is unlikely to hold in practice, and \ntherefore PCA would be insufficient. However I would have been more convinced by\nsome empirical evidence for this claim. What about the case where f is bijective\n(i.e. an invertible neural network); is PCA on the activation space sufficient\nto produce complete and useful concepts in\nthis case?\n\nI also wondered whether there is a corner case where the functional form of h\ncauses the components that capture the most variance in the activation space\n(i.e. top PCA vectors) to capture the least variance in the logits space. This\nseems plausible if h is an unconstrained linear mapping or non-linear mapping;\nthink about a simple whitening function that scales principal components in\ninverse proportion to their eigenvalue. In this case we may be better off using\nthe bottom PCA vectors than the top ones. Admittedly this is only thought\nexperiment, but is there any way for the authors to show that this does not happen\nin practice by characterizing the h functions we see for neural networks applied\nto application areas of interest: sentiment analysis and image classification? \n\nThe synthetic experiments seem useful to the overall story (although the data\ngenerating process is somewhat hard to parse at first), and I like that\nthere are many baseline methods in this study. It seems that PCA is neither\ncomplete nor aligned in this simple setting. It also seems that TCAV is not\ncomplete. Unfortunately the authors fail to show that similar trends hold in the\nnon-synthetic setting. My feeling is that a more comprehensive and thorough\nexperimental study---starting from a characterization of a problem with existing\nmethods---would strengthen the paper considerably.\n\n\nSome superficial comments:\nS1\n* \"This has thus lead to an increasing interest...\" It would be good to add\n  references to this claim.\n* \"Of course such degeneracy assumptions likely not hold\" -> \"Of course such\n  degeneracy assumptions likely do not hold\" -> \n* \"...which can explain how much does each concept contribute to the\n  completeness score\" -> \"...which accounts for the contribution of each concept\n  to the completeness score...\"\nS2\n* \"...that capture how complete is a given set of given concepts\" -> \"...that\n  capture the completeness of a given set of given concepts\"\n* \"...concepts hold sufficient info for prediction\" -> \"...concepts hold\n  sufficient information for prediction\"\n* \"...prediction scores for examples in class A won't be much different from\n  examples in class A\" -> \"...prediction scores for examples in class A won't be\n  much different from other examples in class A\"?\nS3\n* \"...each concept direction is semantically meaningful to human\" -> \"...each\n  concept direction is semantically meaningful to humans\" \nS5\n* \"y1 = ~...\" could you make a note that \"~\" denotes logical not? \n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "H1l_Q0B1jB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update: after reading the rebuttals, I raised my rating to weak accept. Authors provide an interesting and possible limitation of TCAV during rebuttal (in the XOR case TCAV might not be able to identify meaningful subspace). It would strengthen the paper by somehow proving it. Maybe you can visualize the TCAV vectors and your vectors in the simulation and use it to explain why TCAV selects unrelevant concept 11, or designs another simple experiments. \nAlso, if accepted, please consider more parameter stability analysis in the real datasets, including ablation studies of different regularizations. This helps readers understand the value of this method in the real data.\n\nOverall I like the paper much better after rebuttal, but still have a lukewarm feeling about it. I do not see lots of value in the current method, probably due to not very interesting or interpretable results in the real data. However, it does provide a new concept of completeness, and I agree with R1 that it's interesting and relevant. So I would change my rating to weak accept.\n\n====================================================================================================\nOriginal evaluation:\n\nThis paper can be seen as an extension to the paper Ghorbani et al., 2019 to try to extract \"complete\" unsupervised concepts as well as maintainting interpretability. Compared to Ghorbani et al., they have 2 modifications. First, they try to learn a set of concept vectors such that the resulting projected activations on this concept basis would not lose too much accuracy, which they call completeness. Second, to maintain interpretability for these vectors, they regularize these vectors to sparsely match to some input clusters (generated by the k-means) that human can examine, and regularize no two concept matches to the same cluster. They validate their concepts in the simulation, text and image datasets.\n\nOverall I feel the idea is interesting but a bit straightforward. The resulting concept vectors are also not very interpretable or interesting in the text and image domain, which seems to limit its utility to practioners. \n\nAlso, one of the problem is how to select the coefficients for the regularization. In the supplements authors mention that they choose lambda=10 and it produces \"reasonable\" results in the simulation. This decreases the credibility of the simulation that shows it outperforms the baselines such as TCAV, as it sounds like you set the parameters to get good metrics on this simulation. Moreover, in the real-world data there might not be an easy way to set these parameters. I think the authors could strengthen the paper by experimenting with different coefficients and examine the stability of the resulting explanations, or at least indicate how results differ if the coefficients are set differently. Or do an ablation study about how different objectives shape the resulting concepts.\n\nBesides, I will suggest to plot a figure to show number of concepts used v.s. the completeness score. It will motivate why choosing specific number of concepts in the experiements. Also experimenting with different number of concepts is helpful for readers to see the stability of this method as well. \n\nSome minor questions:\n1. The claim of the result of the image dataset says it focuses on the texture. I think it might be caused by the super-pixel segmentation, which already removes most of the edges and leaves with the texture clusters. \n2. Any intuition of why TCAV performs worse in the simulation? How do you select the top 5 vectors for the TCAV, and why does it select non-useful concept 11?\n3. In the definition saliency score (page 4), I am just wondering if the normalized vector could be better? So the resulting value would not be affected by different magnitude of u_k or concept vectors c_j.\n4. In the definition of the conceptSHAP score, shouldn't it be the average of conceptSHAP score across all the classes instead of the sum (inline equation near eq. 6)? If you have 1000 class, then the conceptSHAP score could be something around 1000, that will be wierd.\n\nWriting:\n- I am confused at first read in the 2nd paragraph of the section 3 in page 4. The word \"concept\" is overloaded and represent both as input concept clusters and the resulting concept vectors. Such as \"...candidate clusters of concepts...\" or \"... each concept is salient to one cluster ...\".\n- Typo: \"They main takeaway\" -> \"The main takeaway\"\n\nStrengths:\n+ Good related work\n+ Somewhat complete evaluation\nWeaknesses:\n- No analysis with so many hyparparameters (reg lambda, number of concepts), and thus not sure about the validity of the simulation\n- Idea is interesting but straightforward\n- Not very interpretable results", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byld0hD0FS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors build on the work by Ghorbani et al. in concept-based interpretability methods by taking into account the \"completeness\" of the concepts. This basically tests whether the models accuracy holds if the input is projected onto the span of the discovered concepts. They propose \"ConceptSHAP\", based on Shapley values, to assign importance to the learned concepts. These could be shown to satisfy some reasonable properties such as efficiency (sum of importances equals total completeness value), symmetry, additivity, dummy (a concept that does not change the completeness universally should have zero importance) as stated in Prop. 4.1. The method is finally tested on a variety of datasets, including a synthetic one, which shows that optimizing \"completeness\" helps in discovering a richer variety of important  concepts than prior work). \n- I was wondering how the completeness and importance measures change when the input is perturbed slightly such that the classifier output doesn't change? \n- How the concepts would change if the completeness measure is removed from the optimization in text and image-classification?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlcqwZ0tH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary \n\nThe paper proposes metrics for evaluating concept based explanations in terms of ‘completeness’ -- characterized by (1) whether the set of presented concepts if sufficient to retain the predictive performance of the original model and (2) how is performance affected when all information useful to a complete set of concepts (as per (1)) is removed from features at a specific layer. Assuming concept vectors lie in linear sub-spaces of the activations of the network at a specific layer, the underlying assumption is that if a given set of ‘concept’ vectors is complete, then using a projection of the intermediate features from input onto the sub-space spanned by concepts should not result in reduced / affected predictive performance. Based on these characterizations, the paper proposes an objective to discovering complete and interpretable set of concepts given a candidate cluster of concepts. Furthermore, the paper proposes metrics to quantify the importance of each concept (using Shapley values) and per-class importance of concepts. The authors conduct experiments on toy data, image and text classification datasets and show that their proposed approach can discover concepts that are complete and interpretable.\n\nStrengths\n\n- The paper is well-written and generally easy to follow. The authors do a good job of motivating the need for the completeness metric, characterizing it specifically in the case of concepts spanning sub-spaces of activations and subsequently utilizing the same to motivate an effective concept discovery method.\n\n- The proposed approach and angle being looked at in the paper is novel in the sense that while prior work has mostly focused on characterizing concepts which are salient. Ensuring that concepts are sufficient for predictive performance ensures the fidelity of the interpretability approach.\n\n- I like the fact that the authors decided to capture both aspects of the completeness criterion -- (1) projection to concept-space should not hurt performance and (2) how does removing concept-projected information from the features affect performance. Capturing both provides a holistic viewpoint of the features of the concerned layer -- (1) can explain features/decisions with an associated metric based on the ‘imperfect’ set of concepts and (2) captures the effectiveness of the information present in the features if we remove all concept-useful information.\n\n- The choice of using Shapley values in ConceptSHAP as a metrics provides a whole range of desirable properties in the metrics used indicate the quality of concepts at different levels of granularity -- per-class importance of concepts across classes adding up to the overall importance of a concept. Furthermore, the observation that under certain conditions, the top-k PCA vectors maximize the defined completeness scores is interesting as well.\n\nWeaknesses\n\nHaving said that, I’m interested to hear the thoughts of the authors on the below two points. My primary (not major) concern is the fact the proposed approach is only centered around ensuring and evaluating fidelity of the discovered concepts to the original model. \n\n- While the proposed approach and evaluation metrics are novel, and the results generally support the claims of the paper -- toy experiments result in recovery of the ground-truth concepts, concepts identified for text and image classification offer feasible takeaways -- there is still a lack of proper human-interpretability aspect of the discovered concepts. The proposed approach to discover complete concepts mostly acts similar to a pruning approach on top of a candidate set of concepts based solely on fidelity to the original model. The obtained concepts are mostly explained via feasible hypotheses. One possible experiment that can be used to capture the reliability aspect of the discovered concepts could be as follows -- “Given the set of concepts (and representative patches) and SHAP values across all (or most relevant) classes, are humans able to predict the output of the model?” Is it possible to setup and experiment of this sort? I believe it might help understand the utility of the SHAP values in this context (beyond the advantages in terms of manipulation and characterized completeness).\n\n- The experimental results for image classification are presented on the Animals with Attributes (AwA) dataset. AWA is a fine-grained dataset with only one class present per-image. I’m curious to what happens when the same approach is applied to datasets where images have multiple classes (and potentially distractor classes) present. Is it possible that it becomes harder to discover ‘complete’ concepts (subject to the availability of a decent approach to provide an initial set of candidate clusters). Do the authors have any thoughts on this and any potential experiments that might address this?\n\nReasons for rating\n\nBeyond the above points of discussion, I don’t have major weaknesses to point out. I generally like the paper. The authors do a good job of identifying the sliver in which they make their contribution and motivate the same appropriately. The proposed evaluation metrics and discovery objectives offer several advantages and can therefore generally serve as useful quantifiers of concept-based explanation approaches. The strengths and weaknesses highlighted above form the basis of my rating.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces an unsupervised concept learning and explanation algorithm, as well as a concept of "completeness" for evaluating representations in an unsupervised way.

There are several valuable contributions here, and the paper improved substantially after the rebuttal.  It would not be unreasonable to accept this paper.  But after extensive post-review discussion, we decided that the completeness idea was the most valuable contribution, but that it was insufficiently investigated.

To quote R3, who I agree with: " I think the paper could be strengthened considerably with a rewrite that focuses first on a shortcoming of existing methods in finding complete solutions. I also think their explanations for why PCA is not complete are somewhat speculative and I expect that studying the completeness of activation spaces in invertible networks would lead to some relevant insights"


Decision: Reject