ON CONCEPT-BASED EXPLANATIONS
Year: 2019

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. 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 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.

heading: 1 INTRODUCTION
text: Deep neural networks (DNNs) have shown great success in numerous tasks (Goodfellow et al., 2016), from understanding images (Zoph et al., 2017) to answering questions (Devlin et al., 2018). 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 at particular decisions. Such conceptbased thinking, by extracting similarities from numerous examples and grouping them systematically based on 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 self-interpretable Bayesian generative model (Bouchacourt & Denoyer, 2019). A key motivating question we ask in this paper is whether we could build on such unsupervised approaches to 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 a crucial unanswered question in concept-based explanation, which is how to evaluate whether a set of concepts are sufficient for prediction. Previous concept-based explanations
select concepts that are salient to a particular class (Kim et al., 2018). However, selecting a 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 et al., 2018), which is acknowledged to be valuable for evaluating explanations (Yang et al., 2019). In this work, we propose such a completeness metric for a 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 a 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, we 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, we show that under a stringent degeneracy condition on 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-interpretability 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 a set of highly-complete concepts are discovered, we use game-theoretic notions to aggregate over sets to define contextualized importance of a concept, which we call ConceptSHAP. ConceptSHAP is shown to be the only scoring method that satisfies a set of axioms, which accounts for the contribution of each concept to the completeness score. We also derive a class-specific 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 our completeness-aware concept discovery method, we 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 is able to retrieve the ground truth concepts better than all compared methods. We also demonstrate examples from real-world language and vision datasets to show that our concept discovery algorithm provides additional insights on the behavior of the model.

heading: 2 COMPLETENESS OF CONCEPTS
text: Problem setting: We are given a set of n training examples x1,x2, ...,xn P Ri, corresponding labels y1, y2, ..., yn P Ro, and a DNN fpxq that is learned to map the labels (with dimension o)
from given inputs (with dimension i). We choose an intermediate layer of the DNN, and define the operation for generating the intermediate features from input as Φpxq P Rd and feed forwarding from the intermediate layer to logit layer as hp¨q, yielding the decomposition fpxq “ hpΦpxqq. We define the data matrix as X P Riˆn; the corresponding feature matrix as ΦpXq P Rdˆn, and the corresponding prediction matrix as fpXq P Roˆn. Assume that there is a set of m concepts denoted by vectors c1, c2, ..., cm that represented linear directions in some activation space Φp¨q P Rd given by a concept discovery algorithm. We define the concept matrix as c “ rc1 c2 . . . cms. 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.
Assumption 1: If the given set of concepts is complete, then using a 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 input embedding Φpxq onto the subspace spanned by v P Rdˆr as
P pΦpxq,vq “ vpvJvq´1vJΦpxq. (1)
We define the completeness metric ηp1q on a set of validation data with T data points as V “ tpx1, y1q, ..., pxT , yT qu based on the assumption that projecting input features onto the span of a complete set of concepts should not reduce the model prediction performance. Definition 2.1. Given a prediction model fpxq “ hpΦpxqq, a set of concept vectors c1, ..., cm, and some loss metric L, we define the completeness score ηp1q as:
ηp1qpc1, ..., cmq “ R´
ř
tx,yuPV LphpP pΦpxq, cqq, yq R´ ř tx,yuPV Lpfpxq, yq , (2)
where R “ ř tx,yuPV Lphp0q, yq to ensure that ηp1qp0q “ 0. We omit the dependency of hp¨q, Φp¨q, fp¨q, and Lp¨q of ηp¨q for notation simplicity. When ηp1qpc1, ..., cmq is high, the network maintains a high accuracy even after projection, which supports that the set of discovered concepts hold sufficient information for prediction.
Assumption 2: 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 Xv “ rx1 x2 . . . xT s. To quantify how much the prediction score varies across data samples, we use the sample variance of the predictions: v̂arpfpXvqq “ Trp ˆcovpfpXvqqq “ TrppfpXvq ´ ÊrfpXvqsqpfpXvq ´ ÊrfpXvqsqJq, where ÊrfpXvqs “ 1T řT i“1 fpxiq, and Tr stands for the trace. Then, we define the second completeness metric following this assumption. Definition 2.2. Given a prediction model fpxq “ hpΦpxqq, and a set of concept vectors c1, c2, ..., cm, we define the completeness score ηp2q as:
ηp2qpc1, ..., cmq “ 1´ v̂arphpΦpXvq ´ P pΦpXvq, cqqq
v̂arphpΦpXvqqq , (3)
Based on our assumption 2, the variance of the prediction gets lower after useful concept information is removed from the data, yielding a high completeness score ηp2q.
We now show that under degenerate assumptions, the top k PCA vectors of Φpxq maximize the completeness score for a set of concept vectors. Top PCA vectors are designed to capture as much information in data as possible, a 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 pΦp¨q, } ¨ }F q Ñ pfp¨q, ? Lq, where L is the loss metric in equation 2 and fpxiq “ yi, @pxi, yiq P V (i.e. the loss is minimized), the first m PCA vectors maximizes ηp1q.
Proposition 2.2. When h is an isometry function that maps from pΦp¨q, } ¨ }F q Ñ pfp¨q, } ¨ }F q, and each dimension of Φpxq is uncorrelated with unit variance, the first m PCA vectors maximize ηp2q.
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 as a generalization of the 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 error 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 semantically-meaningful to humans, which will be further explained in the next section.

heading: 3 DISCOVERING COMPLETE AND INTERPRETABLE CONCEPTS
text: Our goal is to discover a set of maximally-complete concepts, where each concept is also interpretable and semantically-meaningful. Ghorbani et al. (2019) has listed meaningfulness, coherency, and saliency as the desired properties for concept-based explanations. Our work on completeness is a crucial addition to the set: not only concept are meaningful coherent and salient, we ensure they are sufficient to models prediction.
We assume that we are given some candidate clusters of concepts (which can be given by human labeling or self-discovery) and each cluster shares some feature attributes that are coherent and semantically-meaningful to humans (which matches the two desired properties in Ghorbani et al. (2019)). We define the feature matrix of cluster i as τi “ rΦpxi1q Φpxi2q . . . s , where xi1,xi2 are samples that belong to cluster i. We denote the feature mean of cluster i as µi “ meanpτiq. 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., 2019). In either case, we would not know which sets of clusters contain useful information to the model that we try to explain. We aim to find a minimum set of concepts that are maximally-complete to the prediction model. Additionally, we constraint that each concept is salient to one cluster only so that each concept direction is semantically-meaningful 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 η (which can be ηp1q or ηp2q), such that the set of concepts fully explain the model behavior. Besides, we introduce two regularization terms for interpretability (can be considered as generalization of the orthogonality constraint of PCA). We introduce cluster-sparsity regularization Lsparse,Clpcq to encourage each concept is salient to minimum number of clusters, and we introduce concept-sparsity regularization LSparse,Conpcq 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 τ1, τ2, ..., τK , a set of training examples x1,x2, ...,xn, and a pre-trained prediction model fpxq “ hpΦpxqq, the overall objective function (to minimize) becomes:
´ ηpcq ` λ1 ¨ LSparse,Clpcq ` λ2 ¨ LSparse,Conpcq, (4)
where λ1 and λ2 are loss coefficients. To formulate the cluster-sparsity regularization Lsparse,Clpcq and concept-sparsity regularization LSparse,Conpcq, we first formally introduce the saliency score between concept cj to cluster τk as:
ρpcj , τkq “ |xcj , µky| b
řK l“1 |xcj , µly|2
.
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 cj to cluster τk is large, cj can differentiate samples from cluster k from samples in a 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 L1 norm of saliency score for every concept-cluster pair (which can be seen as the
sparse filtering objective in Ngiam et al. (2011)), leading to the cluster-sparsity regularization loss:
Lsparse,Clpcq “ m ÿ
j“1
K ÿ k“1 ρpcj , τkq,
which encourages sparse saliency scores. To constrain that different concepts are not salient to the same cluster, we penalize the pairwise saliency score product between every pair of concepts for the same cluster, leading to the concept-sparsity regularization loss:
LSparse,Conpcq “ ÿ
i‰j
K ÿ k“1 ρpci, τkq ¨ ρpcj , τkq.
If 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, we typically assume we have more clusters compared to concepts (i.e. K ą m).

heading: 4 HOW IMPORTANT IS EACH CONCEPT?
text: ConceptSHAP to quantify concept importance: Given a set of concepts CS “ tc1, c2, ...cmu with a high completeness score, we would like to evaluate the importance of each individual concept, specifically, by quantifying how much each individual concept contributes to the final completeness score. Let φi denote the importance score for concept Ci, such that φi quantifies how much of the completeness score ηpCSq is contributed by ci. Motivated by its successful applications in quantifying attributes in what-if scenarios for complex systems, we adapt Shapley values (Shapley, 1988; Lundberg & Lee, 2017), to fairly assign the importance of each concept (which we abbreviate as ConceptSHAP):
Definition 4.1. Given a set of concepts CS “ tc1, c2, ...cmu and some completeness metric η, we define the ConceptSHAP φi for concept ci as
φipηq “ ÿ
SĎCs\ci
pm´ |S| ´ 1q!|S|! m! rηpSYtciuq ´ ηpSqs,
The main benefit of using Shapley value to assign importance is that Shapley value can be shown to uniquely satisfy a set of desired axioms, listed in the following proposition:
Proposition 4.1. Given a set of concepts CS “ tc1, c2, ...cmu and a completeness metric η, and some importance score φi for each concept ci that depends on the completeness metric η. φi 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, řm
i“1 φipηq “ ηpCSq.
• Symmetry: For two equivalent concepts, which satisfy ηpuY tciuq “ ηpuY tcjuq for every subset u Ď CSztci, cju, φipηq “ φjpηq.
• Dummy: If ηpuY tciuq “ ηpuq for every subset u Ď CSztciu, then φipηq “ 0.
• Additivity: If η and η1 have importance value φpηq and φpη1q respectively, then the importance value of the sum of two completeness metric should be equal to the sum of the two importance values, i.e, φipη ` η1q “ φipηq ` φipη1q for all i.
The efficiency axiom distributes the completeness score of all concepts to the individual concepts. The symmetry axiom guarantees that two concepts that behaves the same get the same importance score for fairness. 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.
Per-class saliency of concepts: In multi-class classification, it may be more informative to obtain a 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 fpxq “ hpΦpxqq, a set of concept vectors c1, c2, ..., cm that lie in the feature subspace in Φp¨q. We then define the completeness score for class j as:
η p1q j pc1, ..., cmq “
Rj ´ ř tx,yuPVj LphpP pΦpxq, cqq, yq R´ ř tx,yuPV Lpfpxq, yq , (5)
where Vj is the set of validation data where ground truth label is j and Rj “ ř tx,yuPVj Lphp0q, yq. Given the completeness for a specific class, we define the ConceptSHAP for concept i with respect to class j as: Definition 4.3. Given a prediction model fpxq, a set of concept vectors c1, c2, ..., cm that lie in the feature subspace in Φp¨q. We can define the ConceptSHAP for concept i with respect to class j as:
φi,jpηq “ φipηjq. (6)
For each class j, we may select the concepts with the highest conceptSHAP score with respect to class j. We note that ř
j ηj “ η and thus with the additivity axiom, ř j φi,jpηjq “ φipηq.

heading: 5 EXPERIMENTS

heading: 5.1 SYNTHETIC DATA WITH GROUND TRUTH CONCEPTS
text: Setting: We construct a 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-dimensional binary variable assigned as ground truth candidate concepts ξ1, ..., ξ15 that is generated with Bernoulli independently for each dimension with p “ 0.5. From ground truth concepts pξq, we generate input data x and output label y. For the label target y, we construct a 15-dimensional multi-label target for each sample, where the target y is a function that depends on the first 5 dimension of the 15-dimensional ξ. For example, y1 “„ pξ1 ¨ ξ3q ` ξ4, y2 “ ξ2 ` ξ3 ` ξ4, y3 “ ξ2 ¨ ξ3 ` ξ4 ¨ ξ51. Therefore, the minimum set of ground truth variable is tξ1, ..., ξ5u by construction. For the input data x, we construct a toy image dataset where each concept ξi is mapped to a specific shape, and the image contains the specific shape if and only if the concept ξi “ 1. For example, if ξ3t “ 1, a star (with random color and location) will occur in the image xt, and if ξ3t “ 0, there will be no star in the image xt. The map of concept to shape and two example images are given in Figure 2.
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-unsupervised 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 a convolutional neural network with 6 layers which achieves 0.999 accuracy, and take the first fully connected layer as the feature layer (which is Φpxq in the problem definition.)
1„ notes Not, and the details of generating this dataset is in the appendix.
Evaluation metrics: Let the known concepts be ξ1, ξ2, ..., ξm̂, 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 ci to align with a ground truth concept ξj , 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 ci as the weight vector applied on the binary classification problem where ξj is the target.
Scorepci, ξjq “ max aPt´1,1u,bPR
T ÿ
t“1
1rpa ¨ cTi Φpxtq ą bq ““ ξjts T .
We then evaluate how well the set of discovered concepts c1...cm matches the set of ground truth concepts ξ1, ..., ξm̂ as
AlignemntScorepYmi“1tc1iu,Ym̂j“1tξjuq “ 1m̂` 1 maxPĎr1,msm m̂ ÿ
j“1 AccpcP rjs, ξjq,
which measures the best average accuracy by assigning the best concept vector to differentiate each ground truth concept.
Results: We summarize the results in Table 1, where ours-supervised and TCAV takes supervised clusters as input, and ours-unsupervised, ACE, Raw-Clustering takes the clustered segments as input. For supervised clusters, we randomly choose examples where ξj “ 1 for cluster j. The term supervised and unsupervised refers to whether the actual ground truth concept set ξj is given or not. For ourssupervised 1, we maximize ηp1q in equation 4; for ours-supervised 2, we maximize ηp2q in equation 4. We see that both ours-supervised 1 and ours-supervised 2 obtain higher AlignemntScore compared to TCAV. ours-unsupervised 1 and ours-unsupervised 2 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 1 does not necessary lead to a higher value in completeness 2, and vice versa. Nevertheless, by jointly optimizing completeness 1 or completeness 2 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 3 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 to the same concept when k is large.

heading: 5.2 TEXT CLASSIFICATION
text: 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 as training data and 25k reviews are used for evaluation. For each review, it is either classified as a positive or negative review. We use a pre-trained model with a BERT language model (Devlin et al., 2018) from Keras, which achieves 0.94 testing accuracy. To obtain the input cluster, we use a 10-word sliding window to obtain sub-sentences over the IMDB sentences. We then obtain the embedding for all 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 ηp1q 0.99.
Results: 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-neighbor 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 we highlight in blue. Nearest neighbors of concept 1 mostly contains the word “characters”, nearest neighbors of concept 2 and concept 3 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 a 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-sentences 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
neighbors explicitly mentioned the word “watch” with a 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 1, and the last 2 concepts are significant to the class “positive” with TCAV score 1.

heading: 5.3 IMAGE CLASSIFICATION
text: 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 of one of 50 animals. We train an Inception-V3 model pre-trained on 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 8 concepts with ηp1q 0.99.
Results: For each of the 8 discovered concepts, we show the top nearest neighbor patches, the ConceptSHAP 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, we find that the concepts 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 in trees or pastures. We note that out of 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 to “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 be meaningful and coherent to humans. We note that in some cases the related class of a 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 is that the salient concepts for image classification shares similarity in texture instead of shape, which coincides with the finding in Geirhos et al. (2018).

heading: 6 RELATED WORK
text: Various approaches have been proposed to explain the decision making of pre-trained models. Most works fall under two categories: (i) feature-based explanation methods, that attribute the decision to important input features (Ribeiro et al., 2016; Lundberg & Lee, 2017; Smilkov et al., 2017; Chen et al., 2018), and (ii) sample-based explanation methods, that attribute the decision to previously observed samples (Koh & Liang, 2017; Yeh et al., 2018; Khanna et al., 2019; Arik & Pfister, 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-grounded evaluations (Samek et al., 2016; 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 a concept with respect to a specific class. Zhou et al. (2018) decompose the prediction of a data sample into linear combinations of concept components. Ghorbani 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. Chan 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 a 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 semantically-meaningful. For example, Chorowski et al. (2019) show that when learning with speech data, the latent dimension is closely related to the phonemes, which can be seen as human-relatable concepts in speech data; or Radford et al. (2017) show that when learning with language data, a single unit is closely related to the sentiment.

heading: 7 CONCLUSIONS
text: Concept-based explanations can be a key direction to understand how DNNs make decisions. In this paper, we study concept-based explainability in a 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-used PCA method under certain assumptions. Next, we study two additional constraints to ensure the interpretability of discovered concept. Through experiments in toy data, text, and image domain, we demonstrate that our method is 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 to train an inherently-interpretable model. A future direction may be to explore whether jointly learning the concepts and the model can lead to better interpretability.

heading: APPENDIX A PROOF

heading: Proof of Proposition 2.1
text: Proof. By the basic properties of PCA, the first m PCA vectors (principal components) minimize the reconstruction `2 error. Define the concatenation of the m PCA vectors as a matrix p and } ¨ } as the `2 norm, the basic properties of PCA is equivalent to that for all c “ rc1 c2 . . . cms ,
ÿ
xĎVX
}P pΦpxq,pq ´ Φpxq}2F ď ÿ
xĎVX
}P pΦpxq, cq ´ Φpxq}2F .
By the isometry of h from the Frobenius norm to ? L, we have
ÿ
xĎVX
LphpP pΦpxq,pqq, hpΦpxqqq ď ÿ
xĎVX
LphpP pΦpxq, cqq, hpΦpxqqq,
and since fpxq is equal to Y, we can rewrite to ÿ
x,yĎV LphpP pΦpxq,pqq, yq ď
ÿ
x,yĎV LphpP pΦpxq, cqq, yq
and subsequently get that for any c
R´ ř tx,yuĎV LphpP pΦpxq,pqq, yq R´ ř tx,yuĎV Lpfpxq, yq ě R´ ř tx,yuĎV LphpP pΦpxq, cqq, yq R´ ř tx,yuĎV Lpfpxq, yq .

heading: Proof of Proposistion 2.2
text: Proof. We note that the completeness only depends on the span of c1, ...cm. If we assume the matrix c to have rankm
1 ď m, we may find a set of orthonormal basis (by QR decomposition) c1, ...cm1 that is orthonormal with the same completeness score. Therefore, for any set of given concepts c1, ...cm, we can replace them with a set of orthonormal concepts c1, ...cm1 without loss of generality. By the basic properties of PCA, the first m PCA vectors p1, ...,pm maximizes the total projection data variance on the projected space with at most m orthonormal vectors, which can be formalized as
m ÿ i“1 v̂arpΦpXvqJpiq ě
m1 ÿ i“1 v̂arpΦpXvqJciq, (7)
By using the notation cpjq for the jth entry of vector c, we may rewrite total projected variance as
m1 ÿ i“1 v̂arpΦpXvqJciq “ m1 ÿ i“1 v̂arpΦpXvqJciq d ÿ j“1 pcpjqi q 2
“ m1 ÿ
i“1
d ÿ j“1 v̂arpΦpXvqJciqpcpjqi q 2
“ d ÿ
j“1
m1 ÿ i“1 v̂arpΦpXvqJcicpjqi q
“ d ÿ
j“1 v̂arp
m1 ÿ i“1 ΦpXvqJcicpjqi q
“ d ÿ
j“1 v̂arpP pΦpXvq, cqpjqq
“ v̂arpP pΦpXvq, cqq.
(8)
The fourth equality holds since ΦpXvqci and ΦpXvqcj are uncorrelated, which can be shown by calculating the co-variance between ΦpXvqci and ΦpXvqcj as:
pΦpXvqci ´ ÊX rΦpXvqJcisqpΦpXvqJcj ´ ÊX rΦpXvqJcjsq
“ d ÿ
t“1 pΦpXvqptqcptqi ´ ÊX rΦpXvq ptqc ptq i sq
h ÿ s“1 pΦpXvqpsqcpsqj ´ ÊX rΦpXvq psqc psq j sq
“ d ÿ
t“1
d ÿ s“1 ÊX rΦpXvqptqΦpXvqpsqscptqi c psq j ´ d ÿ t“1 d ÿ s“1 ÊX rΦpXvqptqsÊX rΦpXvqpsqscptqi c psq j
“ d ÿ
t“1
d ÿ s“1 ˆcovpΦpXvqptq,ΦpXvqpsqqcptqi c psq j “ d ÿ t“1 v̂arpΦpXvqptqqcptqi c ptq j “ 0.
Where the last two equations follow by each dimension of ΦpXvq is uncorrelated with unit variance and ci and cj is uncorrelated. By plugging in equation 8 into equation A, we may obtain
v̂arpP pΦpXvq,pqq ě v̂arpP pΦpXvq, cqq.
Define ĉ as the concatenated matrix for the orthonormal basis for orthogonal complement of c, and define call by concatenating c and ĉ. We know ΦpXvq ´ P pΦpXvq, cq “ P pΦpXvq, ĉq by fundamental properties of linear projections. Since all vectors in c is orthogonal to vectors in ĉ and by pluggin in equation 8 for c “ call, we get v̂arpP pΦpXvq, cqq ` v̂arpP pΦpXvq, ĉqq “ v̂arpP pΦpXvq, callqq “ v̂arpΦpXvqq. By combining the observations we get
v̂arpΦpXvq ´ P pΦpXvq, cqq “ v̂arpP pΦpXvq, ĉqq “ v̂arpΦpXvqq ´ v̂arpP pΦpXvq, cqq ě v̂arpΦpXvqq ´ v̂arpP pΦpXvq,pqq “ v̂arpP pΦpXvq, p̂qq “ v̂arpΦpXvq ´ P pΦpXvq,pqq.
and following the isometry of D, we have
v̂arphpΦpXvq ´ P pΦpXvq,pqqq ď v̂arphpΦpXvq ´ P pΦpXvq, cqqq,
and thus the first m PCA vectors maximizes η2.

heading: APPENDIX B ADDITIONAL EXPERIMENTS RESULTS AND SETTINGS
text: Detailed Experiment Settings in Toy Example The complete list of the target y is y1 “„ pξ1 ¨ ξ3q ` ξ4, y2 “ ξ2 ` ξ3 ` ξ4, y3 “ ξ2 ¨ ξ3 ` ξ4 ¨ ξ5, y4 “ ξ2 XOR ξ3, y5 “ ξ2 ` ξ5, y6 “„ pξ1` ξ4q` ξ5, y7 “ pξ2 ¨ ξ3q XOR ξ5, y8 “ ξ1 ¨ ξ5` ξ2, y9 “ ξ3, y10 “ pξ1 ¨ ξ2q XOR ξ4, y11 “„ pξ3 ` ξ5q, y12 “ ξ1 ` ξ4 ` ξ5, y13 “ ξ2 XOR ξ3, y14 “„ pξ1 ¨ ξ5 ` ξ4q, y15 “ ξ4 XOR ξ5. We create the dataset in matplotlib, where the color of each shape is sampled independently from green,red,blue,black,orange,purple,yellow, and the location is sampled randomly with the constraint that different shapes do not coincide with each other. For hyper-parameter selection, we simply set λ1 “ λ2 “ 10.0. We fix this hyper-parameter throughout all experiments to prevent exhaustive tuning and over-fitting. Scaling the hyper-parameter 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 5 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 as XOR, which has 0 TCAV score for inputs.
For a more concrete example, consider the case Y “ X1 XOR X2, and assume that we have 3 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 a linear concept direction, the completeness measure for tX1, X2u would be 1, while the completeness measure for completeness measure for tX1, X3u and tX2, X3u 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 tX1, X2u, we can still get Y “ X1 XOR X2. On the other hand, if we project the activation space onto tX1, X3u, 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 hp.q in our problem setting), which may capture the non-linear 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 (Lundberg & 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 is 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 in 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.
Additional Nearest Neighbors for IMDB We show addition nearest neighbors for each concept obtained in IMDB in Figure 5. 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 in concept 4 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 AwA We show addition nearest neighbors for each concept obtained in AwA in Figure 6. The nearest neighbors all share the same texture. Interestingly, some of the nearest neighbors of 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.

heading: APPENDIX C ADDITIONAL EXPERIMENTS
text: Throughout this section, we refer to ηp1q when the term completeness score is mentioned for the simplicity of presentation.

heading: C.1 HYPER-PARAMETERS
text: We run a controlled experiment on different λ “ λ1 “ λ2 values for our concept discovery algorithm to show the robustness of our algorithm against different hyper-parameters. We also perform an ablation study when we do not optimize for the completeness score, which we call ours_unsup˚ and ours_sup˚. We summarize the result in Figure 7. We observe that our method outperforms the baselines for λ P r0.5, 50s. This shows that our concept discovery algorithm is robust with respect to the hyper-parameter λ. We also observe that for the controlled version where the completeness score is 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.

heading: C.2 NUMBER OF CONCEPTS
text: We show the performance metric when different number of concepts are 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 are low 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 1 to 9. Only ours-sup and ours-unsup achieves a high completeness score when the concept number is larger or equal to 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 to reach a high alignment score. On the other hand, our method which obtains a high completeness score achieves a high alignment score.
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 is 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 in Proposition 2.1 that PCA maximizes the completeness under isometry of the model. We point out that a 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 a 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.

heading: C.3 ROBUSTNESS AGAINST NOISE
text: We would also be interested in how the completeness metric may change when the input is slightly perturbed. We perform an experiment on AwA where a Gaussian random noise is added to all the input in the validation set. We plot the completeness score against different standard deviation for each dimension of the added noise in Figure 10. We observe that the completeness score is still above 0.96 even when a multivariate Gaussian noise with standard deviation 10 in each dimension is added to 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.

heading: C.4 OPTIMIZING WITHOUT COMPLETENESS
text: 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_unsup˚ and ours_sup˚ in section C.1, 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 0 for AwA dataset. We further visualize the top nearest neighbors for the concepts that are optimized without the completeness metric in Figure 11. We observe that while some concepts are the same as ours when the completeness is optimized, it contains more concepts on wheels and bars which does not seem to 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 0.

Review summaries:
The 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.

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).