Title: ON CONCEPT-BASED EXPLANATIONS IN DEEP NEURAL NETWORKS

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.

1. INTRODUCTION:

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 Figure 1 : The overview of our concept discovering algorithm. Given a 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. 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. Concept-SHAP 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.

2. COMPLETENESS OF CONCEPTS:

Problem setting: We are given a set of n training examples x 1 , x 2 , ..., x n P R i , corresponding labels y 1 , y 2 , ..., y n P R o , and a DNN f pxq 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 R d and feed forwarding from the intermediate layer to logit layer as hp¨q, yielding the decomposition f pxq " hpΦpxqq. We define the data matrix as X P R iˆn ; the corresponding feature matrix as ΦpXq P R dˆn , and the corresponding prediction matrix as f pXq P R oˆn . Assume that there is a set of m concepts denoted by vectors c 1 , c 2 , ..., c m that represented linear directions in some activation space Φp¨q P R d given by a concept discovery algorithm. We define the concept matrix as c " rc 1 c 2 . . . c m s.

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 R dˆr as P pΦpxq, vq " vpv J vq ´1v J Φpxq.

(1)

We define the completeness metric η p1q on a set of validation data with T data points as V " tpx 1 , y 1 q, ..., px T , y T 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 f pxq " hpΦpxqq, a set of concept vectors c 1 , ..., c m , and some loss metric L, we define the completeness score η p1q as:

EQUATION

where R " ř tx,yuPV Lphp0q, yq to ensure that η p1q p0q " 0. We omit the dependency of hp¨q, Φp¨q, f p¨q, and Lp¨q of ηp¨q for notation simplicity. When η p1q pc 1 , ..., c m q 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 X v " rx 1 x 2 . . . x T s. To quantify how much the prediction score varies across data samples, we use the sample variance of the predictions: v arpf pX v qq " Trp ĉ ovpf pX v qqq " Trppf pX v q Érf pX v qsqpf pX v q ´Êrf pX v qsq J q, where Êrf pX v qs " 1 T ř T i"1 f px i q, and Tr stands for the trace. Then, we define the second completeness metric following this assumption. Definition 2.2. Given a prediction model f pxq " hpΦpxqq, and a set of concept vectors c 1 , c 2 , ..., c m , we define the completeness score η p2q as:

EQUATION

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 Ñ pf p¨q, ? Lq, where L is the loss metric in equation 2 and f px i q " y i , @px i , y i q 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 Ñ pf p¨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.

3. DISCOVERING COMPLETE AND INTERPRETABLE CONCEPTS:

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Φpx i1 q Φpx i2 q . . . s , where x i1 , x i2 are samples that belong to cluster i. We denote the feature mean of cluster i as µ i " meanpτ i q. 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 L sparse,Cl pcq to encourage each concept is salient to minimum number of clusters, and we introduce concept-sparsity regularization L Sparse,Con pcq 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 x 1 , x 2 , ..., x n , and a pre-trained prediction model f pxq " hpΦpxqq, the overall objective function (to minimize) becomes: ´ηpcq `λ1 ¨LSparse,Cl pcq `λ2 ¨LSparse,Con pcq,

where λ 1 and λ 2 are loss coefficients. To formulate the cluster-sparsity regularization L sparse,Cl pcq and concept-sparsity regularization L Sparse,Con pcq, we first formally introduce the saliency score between concept c j to cluster τ k as:

ρpc j , τ k q " |xc j , µ k y| b ř K l"1 |xc j , µ l y| 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 c j to cluster τ k is large, c j can differentiate samples from cluster k from samples in a random cluster, and thus c j 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:

L sparse,Cl pcq " m ÿ j"1 K ÿ k"1 ρpc j , τ k q,

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:

L Sparse,Con pcq "

ÿ i‰j K ÿ k"1 ρpc i , τ k q ¨ρpc j , τ k q.

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

4. HOW IMPORTANT IS EACH CONCEPT?:

ConceptSHAP to quantify concept importance: Given a set of concepts C S " tc 1 , c 2 , ...c m u 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 C i , such that φ i quantifies how much of the completeness score ηpC S q is contributed by c i . 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 C S " tc 1 , c 2 , ...c m u and some completeness metric η, we define the ConceptSHAP φ i for concept c i as

φ i pηq " ÿ SĎCs\ci pm ´|S| ´1q!|S|! m! rηpS Y tc i uq ´η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 C S " tc 1 , c 2 , ...c m u and a completeness metric η, and some importance score φ i for each concept c i 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 φ i pηq " ηpC S q.

• Symmetry: For two equivalent concepts, which satisfy ηpu Y tc i uq " ηpu Y tc j uq for every subset u Ď C S ztc i , c j u, φ i pηq " φ j pηq.

• Dummy: If ηpu Y tc i uq " ηpuq for every subset u Ď C S ztc i u, then φ i pηq " 0.

• Additivity: If η and η 1 have importance value φpηq and φpη 1 q 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, φ i pη `η1 q " φ i pηq `φi pη 1 q 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. We then define the completeness score for class j as:

EQUATION

where V j is the set of validation data where ground truth label is j and R j " ř 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 f pxq, a set of concept vectors c 1 , c 2 , ..., c m that lie in the feature subspace in Φp¨q. We can define the ConceptSHAP for concept i with respect to class j as: φ i,j pηq " φ i pη j q.

(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,j pη j q " φ i pηq.

5. EXPERIMENTS:



5.1. SYNTHETIC DATA WITH GROUND TRUTH CONCEPTS:

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, y 1 "" pξ 1 ¨ξ3 q `ξ4 , y 2 " ξ 2 `ξ3 `ξ4 , y 3 " ξ 2 ¨ξ3 `ξ4 ¨ξ51 . Therefore, the minimum set of ground truth variable is tξ 1 , ..., ξ 5 u 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 x t , and if ξ 3t " 0, there will be no star in the image x t . 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.) Figure 3 : Visualization Result for the nearest neighbors of each discovered concepts in ourssupervised and TCAV along with ground truth concept 1 to 5 that is constructed to be the minimum set of ground truth variable. We note that only the shape is revelent of the concept, as the color and location can be random. We show that each of our discovered concepts in ours-supervised corresponds to one of ground truth concept 1 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 in the appendix due to space constraint.

Evaluation metrics: Let the known concepts be ξ 1 , ξ 2 , ..., ξ m, and assume we discover some concept vectors c 1 , ..., c m . We would like to evaluate how closely the discovered concept vectors align with the actual ground truth concepts. For a concept vector c i 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 c i as the weight vector applied on the binary classification problem where ξ j is the target. Scorepc i , ξ j q " max aPt´1,1u,bPR T ÿ t"1 1rpa ¨cT i Φpx t q ą bq "" ξ jt s T .

We then evaluate how well the set of discovered concepts c 1 ...c m matches the set of ground truth concepts ξ 1 , ..., ξ m as

AlignemntScorepY m i"1 tc 1 i u, Y m j"1 tξ j uq " 1 m `1 max P Ďr1,ms m m ÿ j"1

Accpc P rjs , ξ j q, 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. The Completeness and AlignemntScore for our methods compared to the baseline methods on synthetic dataset where ground truth can be obtained.

5.2. TEXT CLASSIFICATION:

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.

Concepts Nearest Neighbors ConceptSHAP Related Class:

Concept 1 plot is boring the characters are neurotic needlessly offensive 0.13 neg characters jess bhamra parminder nagra and jules paxton keira average chop socky all of the cast are likeable characters Concept 2 that keeps on reappearing to the scene where you think she deserved a more studied finale than that i think 0.29 neg think no sometimes hatred and isolation are deeper are more Concept 3 i think the most frustrating thing is that the performances 0.15 neg you might think to see organs yanked out of the many people think has an underlying meaning the love between Concept 4 don't wait for it to be a classic watch it 0.43 pos has real potential and will be one to watch in i recommend you to watch it if you like mature Concept 5 children trying to comfort them after that is all said 0.21 pos paid so well after all acting is one of the it after watching it you will say that it was 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.

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

6. RELATED WORK:

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.

7. CONCLUSIONS:

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. 

C.2 NUMBER OF CONCEPTS:

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. 

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

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

:

" notes Not, and the details of generating this dataset is in the appendix.

Figures and Tables:

Figure2: Two random training images and the respecting ground truth concepts that are positive along with a table that matches ground truth concepts to 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 are provided during training (in the unsupervised case), and the goal of the discovering concept algorithm is to correctly retrieve ground truth concepts ξ 1 to ξ 5 .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 f pxq " hpΦpxqq, a set of concept vectors c 1 , c 2 , ..., c m that lie in the feature subspace in Φp¨q. We then define the completeness score for class j as:

Figure 4: The Nearest Neighbors, ConceptSHAP, and related class for each concept obtained in AwA.

Figure 5: Additional Nearest Neighbors for each concept obtained in IMDB.

Figure 6: More Nearest Neighbors for each concept obtained in AwA.

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

Figure 9: Completeness score for different number of concepts in AwA.

Figure 10: Completeness score for different standard deviation of added noise in AwA.



Table content: <table><tr><td>Methods</td><td>η p1q</td><td colspan="2">η p2q AlignemntScore</td></tr><tr><td>ours-supervised 1</td><td colspan="2">0.96 0.20</td><td>0.90</td></tr><tr><td>ours-supervised 2</td><td>0.0</td><td>1.0</td><td>0.94</td></tr><tr><td>TCAV</td><td colspan="2">0.0 0.30</td><td>0.82</td></tr><tr><td colspan="3">ours-unsupervised 1 0.97 0.22</td><td>0.89</td></tr><tr><td colspan="3">ours-unsupervised 2 0.12 0.99</td><td>0.90</td></tr><tr><td>ACE</td><td colspan="2">0.0 0.37</td><td>0.75</td></tr><tr><td>PCA</td><td colspan="2">0.0 0.67</td><td>0.79</td></tr><tr><td>Raw Clustering</td><td colspan="2">0.49 0.83</td><td>0.66</td></tr></table>

Concepts and their nearest neighbors, ConceptSHAP values, and related class in IMDB.

Table content: <table/>

Peer review (iclr2020):
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). - I was wondering how the completeness and importance measures change when the input is perturbed slightly such that the classifier output doesn*t change? - How the concepts would change if the completeness measure is removed from the optimization in text and image-classification?