A theoretical design of concept sets: improving the predictability of concept bottleneck models

Authors: max ruiz luyten
mihaela  van der schaar
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 11:25:34

Abstract: Concept-based learning, a promising approach in machine learning, emphasizes the value of high-level representations called concepts. However, despite growing interest in concept-bottleneck models (CBMs), there is a lack of clear understanding regarding the properties of concept sets and their impact on model performance. In this work, we define concepts within the machine learning context, highlighting their core properties: 'expressiveness' and 'model-aware inductive bias', and we make explicit the underlying assumption of CBMs. We establish theoretical results for concept-bottleneck models (CBMs), revealing how these properties guide the design of concept sets that optimize model performance. Specifically, we demonstrate that well-chosen concept sets can improve sample efficiency and out-of-distribution robustness in the appropriate regimes. Based on these insights, we propose a method to effectively identify informative and non-redundant concepts. We validate our approach with experiments on CIFAR-10 and MetaShift, showing that concept-bottleneck models outperform the foundational embedding counterpart, particularly in low-data regimes and under distribution shifts. We also examine failure modes and discuss how they can be tackled.

Main paper: 
 introduction: 
 Concept Bottleneck Models (CBMs) [23] offer a compelling trifecta of interpretability [19] , intervenability, and predictability [28] . They are inspired by the power of concepts: the fundamental building blocks of human thought that guide our learning, decision-making, inference, and communication [13] . In a nutshell, CBMs force these high-level representations to inform model predictions. For example, rather than directly predicting a car's action from raw images, a CBM first identifies key concepts such as the presence of a semaphore or a pedestrian crossing the road (C : X → C), and learns ĝ : C → Y to act based on them (ĝ • C)(x). Indeed, despite never having seen a Tesla Model X, one could reasonably classify them provided they can identify an SUV, a T logo, gull-wing doors, and the absence of exhaust pipes. This paradigm has found applications across various domains, including automated driving [12] , fine segmentation [31] , and clinical imaging [39, 22] .Despite their promise, the predictability of CBMs, particularly in relation to the properties of the concept set C, remains poorly understood. A deeper understanding of how the composition and characteristics of concept sets affect CBM performance is essential to enhance their practical utility and robustness in real-world applications.In this paper, we address this gap by systematically investigating the properties of concept sets C = {c 1 , . . . , c m } and their influence on model performance. We answer the following key questions:1. How do characteristics of the concept set impact the performance of the CBM? We identify the size of the concept set |C| and the degree of misspecification ε as primary drivers of the performance of the CBM, where ε := ||arg min f ∈H ℓ(f )arg min g∈H C ℓ(g • C)||, with H ⊆ {f : X → C}, H C ⊆ {g : C → Y} the hypotheses spaces. 2. What are the optimal conditions for the effectiveness of CBMs? We find that CBMs are particularly effective in small data regimes and under distribution shifts.To address these questions, we introduce in Section 3 a theoretical framework that links the properties of concept sets to CBM performance metrics. This framework identifies two core desiderata for concept sets: expressiveness and model-aware inductive bias. Expressiveness ensures each concept captures valuable information from inputs, benefiting the expected loss R(ĝ • C) as the sample size n → ∞. Model-aware inductive bias implies a beneficial inductive bias, improving performance in low-sample regimes (n ≈ 0). These properties highlight an implicit assumption in CBMs about the alignment between model outputs and human inductive biases.In Section 4, we dive into a theoretical analysis of CBMs. Our setting aligns with the recent trend of concept bottleneck models built on multimodal foundational models such as CLIP [30, 39, 41] .We derive a key theorem (Theorem 1) that compares the expected loss of concept-based models (R(ĝ • C), ĝ ∈ arg min g∈H C ℓ(g • C)) with the baseline counterpart (R( f ), f ∈ arg min f ∈H ℓ(f )).The theorem demonstrates that concept-based models can outperform baseline models if the concept set is well chosen by minimizing the size of the concept set |C| while controlling the misspecification term ε. This theoretical insight highlights the importance of selecting informative and non-redundant concepts, as proper concept selection can significantly affect sample efficiency and generalization performance.Based on these insights, we propose a method in Section 5 to generate informative and non-redundant concept sets. We also discuss potential failure modes of CBMs and how existing approaches can mitigate them. Finally, we empirically validate our framework in Section 6 with experiments on CIFAR-10 and MetaShift datasets, showing that appropriately designed CBMs outperform traditional models, particularly in low data and distribution shift scenarios.1. Theoretical Framework for Concept Sets: We introduce a novel theoretical framework for CBMs that elucidates the properties of concept sets, specifically focusing on expressiveness and model-aware inductive bias. This framework formalizes how these properties influence model performance, offering new insights into the design of effective concept sets. 2. Theoretical Analysis and Insights: We derive theoretical results that compare the expected loss of CBMs with their non-bottleneck counterparts. Our analysis reveals the conditions under which CBMs are most effective, particularly in low-data regimes and under distribution shifts. These results provide a clear understanding of the design choices that enhance CBM performance. 3. Empirical validation: We validate our results through experiments on CIFAR-10 and MetaShift datasets, designed to assess different aspects of concept sets and CBMs, and we affirm that appropriately designed concept sets can lead to increased model predictability and efficiency. 
related work: 
 Incorporation of human concepts into machine learning algorithms has been considered for a long time as a strategy to improve the explainability of the model through improved representation interpretability [21, 27, 20, 38] . Concept Bottleneck Models (CBMs) [23] are one of the most promising approaches to concept-based methods and have been adopted in various applications such as fine classification [31] and medical image analysis [39, 22] .Advances in concept identification Recent work has focused on increasing the flexibility of CBMs. For example, [30, 41, 40] explore the use of multimodal and large language models for concept identification to eliminate the need for predefined labels. These methods enhance the adaptability of CBMs to various tasks and domains, improving their practical utility.Performance Enhancement Strategies Recent works consider relaxing the bottleneck by post hoc concept discernment [41] or fitting the CBMs' residuals [36] to improve model accuracy while preserving the other properties of CBMs.Gaps and Our Contribution Despite the mixed successes of these efforts, there remains a gap in understanding concept bottleneck models and, in particular, how the properties of concept sets affect their performance.In summary, our contribution is orthogonal to previous work, providing a deeper theoretical understanding of the relationship between concept set properties and model performance.3 What are concepts?Although the notion of concept has been repeatedly used in the ML literature [23, 30, 10] , there is still a lack of a precise definition and delineation of their properties. To make them theoretically tractable entities, we begin by addressing what concepts are.According to cognition theory, concepts are mental representations that constitute a fundamental key building block in all aspects of cognition [15] . More specifically, they allow us to draw appropriate inferences about the type of entities we encounter in our everyday lives and are necessary for cognitive processes such as categorization, memory, decision-making, learning, and inference. Thus, the formalism should reflect that (1) concepts are representations and (2) concepts empower inferences for everyday tasks.Concepts are representations Let's denote a hypothetical set of concepts as C and a particular concept as c. As representations of some inputs X , concepts can be regarded as mappings from this space. To define the range of these mappings, we emphasize that concept representations indicate 'membership' in a class. In modern theories (e.g., Prototype Theory), concepts consist of fuzzy memberships instead of binary ones. For example [16] , humans consider "sink" as borderline a "kitchen utensil", or "octopuses" are just excluded from the concept of "fish". As such, concepts lend themselves to the fuzzy mathematical formulation of membership functions, a generalization of characteristic functions. Thus, the concept can be unequivocally represented as a mapping c : X → [0, 1].Concepts aid in everyday-task inference Not all membership functions qualify as concepts; the missing component is their usefulness in task-specific inference. For a new concept to be valuable, it must improve predictability for a subset of tasks relevant to humans. This can happen either by capturing new nuances of inputs (for example, new color tones) or integrating different concepts into a more comprehensive entity (e.g., grouping animals into families).Consider a task T , defined as a tuple1 (D, ℓ), where D = {(x i , y i ) ∼ iid P(X , Y)} is= ĝm (•, θ c ) • [c 1 , . . . , c m ], such that ĝm : C ∪ {c m } → Y is trained on the conceptualized input {(c j (x i )) j∈[m] } i∈[n] . Then, C ∪ {c m } is a concept set if there exists N 0 ≤ N 1 ∈ N such that R n ( fC ) > R n ( fC∪{cm} ) for N 0 ≤ n (expressiveness) R n ( f ) > R n ( fC∪{cm} ) for n ≤ N 1 (model-aware inductive-bias)This implies that the output model trained on the concept set generalizes better than the vanilla one in the low-sample domain (model-aware inductive bias) and better than the smaller concept set in the large-sample domain (expressiveness) 2 . We further examine the role of these properties in the Appendix B.2.Note that for human concept sets, the hypothesis space for the learned functions f , ĝm corresponds to the human model. This definition can be regarded not only as a qualifying condition for a membership function to be considered a concept, but also as a measure of its quality, e.g., through the ratio of risks. From this we could discover iteratively new concepts by greedily maximizing the decrease in risk for a new concept or even take a hierarchical approach by unveiling the most relevant concepts to identify a given set of already established concepts.The CBM Assumption An implicit assumption behind concept-based models that we make explicit is that such human concepts will also have predictive power for a given ML output model. The output model is conventionally linear for interpretability.Although expressiveness and model-aware inductive bias may not always transfer across different models, it is reasonable to assume that a representation providing valuable inductive bias for one model can be beneficial for others. Additionally, given ML tasks are by design relevant to humans, and on many ML tasks, humans show a non-trivial performance (e.g., image classification), it is reasonable to expect that human Concept Sets can benefit ML models too in these cases. However, an empirical validation (section 6) is required to check that the CBM assumption holds.Furthermore, since humans have been exposed to a highly varied distribution, concepts are unlikely to be entangled with spurious features, which we also test in our insight experiments.In some cases, it may be useful to evaluate the quality of a concept set without knowing the output model. We propose using an information-theory metric:D KL [P(Y |C ∪ {c m }(X))∥P(Y |C(X))] ≫ 0.A new concept should provide significant information on the output.In the subsequent sections, we will dive into the theoretical insights derived from this formalism and explore empirical validations through various experiments.Natural benefits of concepts Using a concept representation rather than a typical pre-trained model representation provides direct benefits. One notable advantage is that human concepts allow us to decouple the representation model from the output model. This flexibility means that we can replace the underlying concept identification model with a more advanced version in the future while keeping the output model unchanged. The concept set serves as a stable communication interface with fixed dimensionality and functionality. In addition, concepts can act as common representations across different feature sets, potentially harmonizing datasets and modalities. We expand on this discussion in the appendix B.3. 
theoretical results: 
 We now dive into the effect of concept-based representations and their theoretical advantages. This includes the potential for improved data efficiency, as the concept-based representation space is inherently more structured and informative, thereby reducing the amount of data required to achieve comparable performance. Additionally, we will delve into the mechanisms by which concept-based representations enhance model robustness to distribution shifts. In the process, it will also become apparent in what regimes it is undesirable to bottleneck a model on concepts and potential solutions.In our analysis, we focus on a recently popular approach to concept-based models, that is, concept bottleneck models based on multi-modal foundational models, such as CLIP [30, 39, 41] .To that end, we consider the input space X as the joint embedding space of inputs and concepts from a foundational model, where it is assumed [21, 41, 6 ] that concepts can be related to directions, and it is typical to use a linear output layer on top of such representation.Definition 2 (Risk). Let x, x (i) i.i.d. ∼ P(X ) for i ∈ [n], and let y (i) = f * (x (i) ). Given a loss L : Y × Y → R, the risk of a predictor f trained on the n samples (X, y) is given byEQUATIONNow, since the output layer is conventionally linear, we may write f * (x) = ω * x and f (x) = ωx. We further consider the l 2 loss, where the predictor takes the analytical form ω = Y X † , X † representing the Moore-Penrose pseudoinverse of X.Given concepts are represented by directions in this space, we can write a set of concepts C as a set of dual vectors {c (1) , . . . , c (k) } ∈ X * , we can consequently consider our conceptual representation as CX with C = [c (1) , . . . , c (k) ] T , and our overall concept model as fC = ĝc • C.We now turn to the Model-aware inductive bias condition and assess whether there are more explicit conditions that imply it in practice, and thus compute the risk for the concept embedding model and the baseline. Theorem 1. Under the above setting and assuming that P is an isotropic distribution on the d-dimensional input, then the risk of the concept-based model R( fC ) is given byR( fC ) = 1 -n d -|C| (d + 2)(d -1) R( fb ) + n 1 d + d -n (d + 2)(d -1) ε,where ε = ||ω * C ⊥ ∥| 2 F , and C ⊥ stands the orthogonal projection operator onto the orthogonal complement of the concept vector's span.We note that this result aligns with our intuition. Indeed, even without spurious features or distribution shifts, concepts yield a practical advantage over the baseline foundational embedding (first term), but only if concepts are adequately chosen (second term). Let's dive deeper into each of these two terms.Let us start with the ε term that corresponds to the misspecification of the concept set. Certainly, the larger the component of the actual predictor that does not belong to the subspace captured by the concepts, the lesser the quality of our concept model. Note how the ε coefficient grows with the number of examples n, which means that the misspecification term is more influential when more examples are available. Nonetheless, with a proper choice of the concept set, the ε can be nullified.When ε ≈ 0, the remaining terms directly compare the concept and the baseline risks R( fC ), R( fb ). In fact, in this situation, we have a strict benefit for using the concept model, that is, R( fC ) < R( fb ). Interestingly, provided ε ≈ 0, the remaining term suggests we should aim for the minimal set of concepts |C|, and we obtain a better scaling with the number of examples (i.e., increased sample efficiency). Now, let us focus on the setting of spurious features due to confounders. As a motivating example, imagine the image classification setting, in which the classes are confounded with an environment property (e.g., outdoor dogs vs indoor cats). In this case, the image setting acts as a confounder Z, manifesting as a spurious feature in the images. We note that such confounders are human concepts, which, per our previous discussion, are embodied by directions in the CLIP embedding z ∈ X * . Then, Theorem 2. In the presence of confounders {z 1 , z 2 , . . . , z k } ∈ X * , given a concept c ∈ X * , the bias in the ordinary least squares estimator satisfies||Bias( fC |X)|| 2 ∝ ||(⟨c, z 1 ⟩, . . . , (⟨c, z k ⟩)|| 2In particular, the classifier f{c} remains unbiased if and only if c ∈ span(z 1 , z 2 , . . . , z k ) ⊥ .Therefore, if the concept set consists only of a handful of non-spurious concepts, that is, semantically distinct from the confounders (which in the CLIP embedding metric translates into a small cosine similarity), we can expect the bias injected by the spurious feature to be significantly reduced.We must admit that our concept identifier can be imperfect, implying our foundational embedding consists of noisy covariates, requiring an errors-in-variables analysis [14] .Although the effect of noise on multiple covariates is complex, significant noise in any covariate influences the coefficients of all other covariates (see Appendix A.2), degrading the accuracy of the estimator.In the case of a single noisy feature x K = x * K + u, where x i represents the observed covariate with noise u, and y = x * ω * +ϵ is the actual model, the least-squares estimator ω is biased. Specifically, the estimated coefficient for this variable is attenuated byω K = σ * K σ * K +σ 2 u ω * K .Not only the estimated coefficient ω K is increasingly shrunk by the noise towards zero, but all the other coefficients ωi for noiseless features are also biased proportionally to the bias in the coefficient of the noisy regressor. This interdependence means that significant noise in any covariate distorts all coefficients. 
concept sets generation and identification: 
 While Theorem 1 refers to the properties that a concept set must satisfy, to use such a concept set, it is required that we have the concept mappings c : X → [0, 1] |C| . This can be achieved by collecting a dataset X × C and training a model in a supervised fashion, but this is a costly procedure. Instead, the appearance of foundational multimodal models in which one of the domains is natural language, such as CLIP [32] , provides a cheap and flexible approach to concept identification [30] . We will focus on the latter approach because of its increased versatility.From the concept set desiderata in Theorem 1, although powerful, direct foundational model embeddings encode information in a high-dimensional space that likely contains irrelevant information (which can act as spurious features) and noise. For example, CLIP embeddings capture syntactic and semantic nuances and may not necessarily accentuate the conceptual understandings that underpin human reasoning and decision-making processes for a given task. This hinders not only generalization but also the interpretability of the model.First, suppose that we already have a concept set C. Let us explicitly describe how to obtain the concept representation using a multimodal model.Through the model, concepts (language) and input (e.g., images or language in the case of serialized tabular data) can be embedded into a shared space. We can then use the appropriate metric (or similarity measure) in this space to compute the degree of presence of a concept for each given input.In the most common scenario, the distance consists of the cosine similarity, so if the textual concepts C = {t 1 , . . . , t M } and the dataset is D = {x 1 , . . . , x N }, the concept representation c(x) can be computed asc j (x) = ⟨E X (x), E T (t j )⟩ ||E X (x)|| 2 ||E T (t j )|| 2 ,with E X and E T being the input and text encoders respectively. This is the approach that we use in our experiment section.LLMs, especially if endowed with external sources of knowledge (such as ConceptNet [35] or Wikipedia articles), can be used to sample concepts that are commonly associated with a given task, thereby alleviating the burden of collecting domain expertise for the concept set generation, and potentially keeping the human out of the loop if necessary. See Appendix B.4 for a discussion on the choice of LLMs as base-concept samplers.As shown in Theorem 1, the properties of the set of concepts are crucial for the effectiveness of the embedding. In particular, we should aim to balance the following objectives: (1) achieve minimal misspecification ε, which amounts to choosing a complete enough set of concepts to capture as much valuable information in the inputs as possible while also aiming for (2) a set of concepts as small as possible. Additionally, there is an additional practical requirement for the chosen concepts: that the model we use is good enough to identify them to minimize the error-in-variable effect.Motivated by our theoretical desiderata, we propose a multistep approach.1. Initial generation of a complete concept set that satisfies (1). To achieve that, we propose employing a language model L to sample a sufficiently expressive set to achieve a sufficiently low misspecification ε. This can be promoted by conditioning the generation on the context task C T so that concepts are more relevant, which could include external knowledge such as ConceptNet and Wikipedia to promote further quality and diversityC K ⊂ C T . That is, ci ∼ L(c|C T ) 2.For each concept, we must ensure it can be properly identified and its presence is informative for T . That is, ci should be discarded if the entropy of the concept for that task Ω(c i (X)) is below a given threshold Ω m . 3. Finally, we should remove redundant concepts 3 . The approach for this step can vary depending on the output model we use. The conceptually most straightforward approach, based on Theorem 1 consists of empirically estimating the risk R( fC ) by averaging the mean square error 1N N p=1 M SE[ fC (•; θ(D p ))] on cross-validation samples {D p } N p=1 .All in all, the concept generation procedure can be summarized as follows. Starting from C 0 = ∅, while ε(C i ) > ε m we increase our concept set by 4C i = C i-1 ∪ c i , where c i ∼ L(c | C T ) conditioned on Ω(c i (X)) > Ω m R( fCi ) -R( fCi-1 ) > R mThere are settings where we cannot reach values of ε below our chosen threshold through any human concept set. For example, this can happen when there is a subset of relevant features for the task about which humans lack expertise.In such cases, concepts can be leveraged beyond a bottleneck, which might help in any case where the misspecification term dominates. An option is to employ concepts as additional features. Another is to fit the residuals of the CBM by a black box model on the original features to enhance performance [41] . In both cases, one could use concepts that should not influence predictions by including a mutual information penalty to the models trained on the raw input. 3 As per Theorem 1, a concept that does not decrease ε (e.g., if it is spanned by the other concepts or orthogonal to the target function) will be detrimental to the risk since it increases the first term. In practice, when the effect on ε is small, keeping such a concept should depend on the number of samples we have. In low sample regimes, we should be more aggressive in discarding it than when n grows, and the term ε starts to dominate. 4 In our experiments, we keep a concept if it improves the estimated risk, i.e., Rm = 0, or R( fC i ) -R( fC i-1 ) > 0, and we set the entropy threshold proportionally to the number of buckets n b used to estimate Ω to ensure not all samples fall into the same bucket (i.e. Ωm = 1 n b ). 
empirical validation: 
 To empirically validate our insights about concept-based representations, we designed a series of experiments to validate our analysis 5 . We aim to explore the key insights from our theoretical results, including the ability to effectively leverage scarce datasets and the impact of concept-based representations on robustness to distribution shifts.Datasets Our experiments utilize CIFAR-10 [25] to test the effect of concept representations on data efficiency. This dataset is used because of its extensive use in research: its familiarity enables us to gather insights more effectively. MetaShift [26] is a dataset to evaluate distribution shifts in machine learning models. It comprises 12,868 subsets across 410 classes, each representing unique contexts such as "cat with sink" or "cat with fence", using data from Visual Genome [24] . The dataset's graph structure connects subsets by similarity, enabling the quantification shifts and visualization of data conflicts. Thus, we use MetaShift to evaluate model robustness across diverse shifts.In Appendix D we discuss additional experiments, where we utilized three diverse datasets: CUB-200-2011 [37] , Food-101 [7] , and the Describable Textures Dataset (DTD) [9] for data efficiency analysis, CINIC-10 [11] for out-of-distribution generalization, and CIFAR-10 [25] to compare with label-free concept bottleneck models.Models We use VIT-B-32 for the multimodal CLIP [32] and GPT-4 [2] as the human concept sampler. We refer to the VIT-B-32 embedding as the vanilla embedding, which acts as the natural baseline. We primarily use a linear output layer on top of either the vanilla or the concept embedding. Still, we also assess a variety of output layers to understand which concept-based inductive bias is helpful.For all experiments, we provide a complete description, including the concept sets, in Appendix C.2.The effects of the concept and sample sizes. We start by assessing the agreement between theory and practice regarding the effect of the number of training examples and the concept set size on the model's generalization to examples from the same distribution in CIFAR10, as we plot in figure 1 . As we concluded from our interpretation of Theorem 1, we expect the first term, 1 -n d-|C| (d+2)(d-1) R( fb ) to dominate the risk in the low data regime n → 0, since in that case, theε coefficient n 1 d + d-n (d+2)(d-1) renders the second term negligible. 6 In this domain, an increase in the sample efficiency from the first term directly depends on the concept set size |C|, favoring smaller concept sets, which is in total agreement with the empirical results shown in figures 1 and 4 .Then, as the number of samples increases substantially n → ∞, the risks start to plateau, and the misspecification, embodied by ε, becomes the dominant term. Thus, we expect larger concept sizes to outperform smaller ones due to a smaller ε. This is particularly the case given our concept set generation procedure, where smaller concept sets are subsets of the larger ones. Again, this behavior is clearly represented in figures 1 and 4.We now evaluate the concept's robustness to distribution shifts. In particular, we follow the approach of [26] in their evaluation of subpopulation shift in Section 4.2., controlling the degree of imbalance in the dataset to probe its effect on CBMs.That is, we train and test distributions on mixtures of the same domain but where mixture weights differ between train and test. The domain comprises dog and cat images segregated by indoor and outdoor environments. In this case, pictures of outdoor cats and indoor dogs make up the minority groups, and we control the proportion of such samples while keeping |X| fixed at 1700.To align with the insights of Theorem 2, we manually verify that the concept set excludes environmentrelated concepts to reduce the expected confounder bias induced by the shift. Indeed, we observe that the norm of the min-max scaled projection of the concepts "indoor" and "outdoor" in our concept set ||(⟨c i , z 1 ⟩, . . . , (⟨c i , z k ⟩)|| 2 has an average norm of 0.80, small compared to the interconcept similarity, with an average of 1.65.Our results in figure 2 show that the concept representation yields a substantial increase in performance 7 , with bigger improvements for more pronounced distribution shifts. This effect is also seen for other output models, such as k-nearest neighbors and decision trees, suggesting the concept representation effectively reduces the presence of spurious features and thus confirming that concept representations are more robust to spurious correlations. Out-of-distribution generalization of concept embeddings Finally, we assess the robustness of operating with the concept embedding in terms of out-of-distribution generalization. To that end, we use domain generalization datasets from Section 4.1. in MetaShift.The datasets we use consist of three tasks: dog vs. cat, bus vs. truck, and elephant vs. horse. Each of these tasks is tested on instances from one of the two classes, in particular, on images of dogs with shelves, trucks with airplanes, and horses with barns. However, for each task, we have four different training datasets, differing by the domain in which the tested class appears. For example, in the dog vs. cat dataset, we have training sets of dogs with bags or boxes, dogs with benches or bikes, dogs with boats or surfboards, and dogs with cabinets or beds (see figure 3 for details on the other three tasks). Importantly, each of the four datasets for each class corresponds to a different degree of out-of-distribution generalization challenge, comprising a varied test bed for robustness (we refer to [26] for further details).Figure 3 shows that for all the 12 OOD tasks, the CBM significantly outperforms the non-bottleneck baseline, typically by an accuracy gap above 10% and even surpassing a 50% increase in accuracy. We further verify the robustness of the OOD predictions of CBMs in CINIC-10 in Table 1 . 
conclusion: 
 In this work, we introduced a novel theoretical framework for understanding the properties of concept sets in Concept Bottleneck Models (CBMs). We demonstrated how these properties affect model performance, particularly in low-data regimes and under distribution shifts. Our empirical results validated these theoretical insights, showing that well-chosen concept sets improve sample efficiency and robustness in real-world scenarios. Our findings not only deepen the understanding of CBMs but also pave the way for designing more effective models. We extend the limitations and open avenues for future work discussed throughout the paper in the Appendices E and F, respectively. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: All the compute resources used are detailed in appendix C.2.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: See appendix G for a discussion of Broader Impacts. In this section, we discuss potential fairness concerns due to biases in concept identification models, which can lead to unfair outcomes. Mitigation strategies include diverse training datasets, bias detection and correction, and comprehensive documentation. On the other hand, we also discuss how concept representations derived from a fair model could help reduce the bias in models trained on biased data. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper does not involve releasing data or models that pose a high risk for misuse. Therefore, no specific safeguards are necessary for the responsible release of data or models in this context. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: We provide the suggested details for the assets we use in Appendix C.1. 
 
 Appendix: This section is divided into the lemmas we require for our proof. We start with the tools that will enable us to properly handle the spurious variables' effect in our data.We start by recovering a very recent lemma on the effect of confounding on the risk of an ordinary least squares estimator from [29] . We present it here for completeness and adapt it to our notation.Consider a standard confounding setting in which the directed acyclic graph involves the covariates X, the targets Y, and the confounder covariates Z. In this setting, Z is a parent of both X and Y, and Y is a child of both X and Z. In addition, we assume a Gaussian distribution and a linear setting, that is:Y|X, Z ∼ N m (β y•x(z) X + β y•z(x) Z, Σ y|x,z )We use Σ T for any random variable T to denote its covariance matrix. The subscripts of the regression coefficients, as in [29] , indicate the relationship between the response (before the dot) and the covariate (after the dot), considering the presence of another variable (within brackets) in the conditional mean.Of course, the confounder is not observed, so we aim to fit the following model, where the underscore con stands for confounded.Y = ω con X + η η ∼ N n (0, I n ),with the least-squares estimator:ωcon = X † Y.However, in practice, due to the confounder,Y|X ∼ N n (A y•x X, B 2 y•z(x) Σ z|x + Σ y|x,z ),where A stand for the regression matrices:A y•x = Σ yx Σ -1 x = B y•x(z) I n + B y•z(x) A z•x Lemma 1.In the above setting, the bias and variance of the least squares estimator ω can be expressed as:Bias Y [ω con |X] = B y•z(x) X ⊤ MA z•x X X ⊤ MX , Var Y [ω con |X] = X ⊤ MΣ y|x MX (X ⊤ MX) 2 ,whereM = I n - 1n1 ⊤ n nis the centering matrix.Proof. See Proposition 2 in [29] .Lemma 1 implies that when both B y•z(x) ̸ = 0 and A z•x ̸ = 0, the estimator βx is biased. Note that the expectation of the bias is proportional to both the effects of Z on X and Y. We defer its computation to Theorem 2 in [29] , but the above observation allows us to state Theorem 2.Theorem 3. In the presence of confounders {z 1 , z 2 , . . . , z k } ∈ X * , given a concept c ∈ X * , the bias in the ordinary least squares estimator satisfies||Bias( fC |X)|| 2 ∝ ||(⟨c, z 1 ⟩, . . . , (⟨c, z k ⟩)|| 2In particular, the classifier f{ c} remains unbiased if and only if c ∈ span(z 1 , z 2 , . . . , z k ) ⊥ .Proof. We can rewrite the lemma 1 by denoting ṽ = v ||v||2 as follows:||Bias Y [ω con |X]|| 2 = ||A z•x || 2 ||B y•z(x) X ⊤ M Ãz•x X X ⊤ MX || 2 ,But ||A z•x || 2 corresponds, in fact, to the regression coefficient of x(z). In our case,A z•x = (⟨c, z i ⟩) k i=1, which completes the proof.Note that our concept identifier will not be perfect in practice, leading us to treat our foundational embedding as noisy covariates. This aligns with the errors-in-variables model [14] . Although the effect of noise across multiple covariates is complex, we can qualitatively conclude that significant noise in any covariate influences the coefficients of all other covariates, resulting in substantial degradation of the overall estimator's accuracy.Mathematically, if x i = x * i + u i represents the observed covariates with noise u i , and y = x * α * + ϵ is the true model, the least-squares estimator α is biased. Specifically, for a single noisy covariate x K , the attenuation effect on the estimated coefficient α K is given by αK = σ * K σ * K +σ 2 u α * K .This indicates that the estimated coefficient α K is shrunk towards zero, with the degree of attenuation increasing with the noise variance σ 2 u . Furthermore, the bias in the estimated coefficient αi of a correctly measured regressor x i is proportional to the bias in the coefficient of the noisy regressor. This is expressed as αi = α * i +β i (α * K -α K ). This interdependence means that noise in any covariate can propagate, affecting all other coefficients (cf. [14] ). Thus, significant noise in any covariate leads to a complex distortion of the entire regression model.The proof of Theorem 1 follows the same backbone as [33] and also relies on the following lemma, the proof of which we reproduce here for completeness. Lemma 2. Let D, Λ ∈ {0, 1} d×d be two diagonal matrices of rank p and q, respectively. Let V ∈ R d×d be an orthogonal matrix and W ∈ R d×d a Haar distributed random matrix.If P = W DW T , Q = V ΛV T , then E W [P QP ] = p d(d -1)(d + 2) [q(d -p)I d×d + [d(p + 1) -2] Q] .Proof. Since V is an arbitrary orthogonal matrix and W is Haar distributed, without loss of generality, we can assume Λ = diag(1 q , 0 d-q ), and D = diag(1 p , 0 d-p ). By definition of the Haar distribution, we can denote U = V T W , also Haar distributed. Therefore,E W [P QP ] = E W ∼Haar W DW T V ΛV T W DW T = V E U ∼Haar U DU T ΛU DU T V T = V E U ∼Haar A T A V T ,where we have defined A = ΛU DU T . Looking closely at the entries of A a quick computation yields, denoting ũi = (u i1 , . . . , u ip ):A =          ⟨ũ 1 , ũ1 ⟩ • • • ⟨ũ 1 , ũd ⟩ . . . . . . . . . ⟨ũ q , ũ1 ⟩ • • • ⟨ũ q , ũd ⟩ 0 • • • 0 . . . . . . . . . 0 • • • 0          .Thus, (A T A) i,r = q k=1 ⟨ũ i , ũk ⟩⟨ũ r , ũk ⟩, and so, E U [A T A] can be readily computed if we have the fourth moments of the entries in U . Indeed,E U (A T A) i,r = q α=1 p j,s=1 E U [u ij u rs u αj u αs ] .Lemma 9 from [8] provides such 4th moments: if i ̸ = r, then E U [(A T A) i,r = 0, and if i = r, thenE U [u ij u is u αj u αs ] = 1 d(d -1)(d + 2) [dδ js + dδ iα + (d -2)δ iα δ js -1] .Consequently, the expectation yields a diagonal matrix with two blocks of eigenvalues:E U (A T A) i,i = p d(d -1)(d + 2) [(d -p)I d×d + [d(p + 1) -2] Λ] . Since E W [P QP ] = V E U (A T A) V T , V V T = I d×d , and V ΛV T = Q, the result follows.Next, we follow the steps of [33] to arrive to Theorem 1 Theorem 4.Let X = R d , C = R |C| , Y = R lAnd assuming that P is an isotropic distribution, where X = {x i } n i=1 ∼ iid P is full rank, and our labels are linear on the covariates, i.e., y i = ω * x i then the risk of the concept-based model R( fC ) is given byR( fC ) = 1 -n d -|C| (d + 2)(d -1) R( fb ) + n 1 d + d -n (d + 2)(d -1) ε,where ε = ||ω * C ⊥ ∥| 2 F , and C ⊥ stands the orthogonal projection operator onto the orthogonal complement of the concept vector's span.Proof. Given a matrix M ∈ R k×p full rank p, we denote M || := M † M the projection onto its column space, and M ⊥ = I d×d -X || the projection into the corresponding orthogonal space.Then, denoting ωC the ordinary mean square estimator of the weights we have:ωC C = Y (CX) † C = ω * XX † C † C = ω * X || C || . Therefore, ωC C -ω * = ω * X || C || -I d×d = ω * X || -I d×d C || + C || -I d×d = -ω * X ⊥ C || + C ⊥ .Using the cyclic property of the trace, the risk is given byR(ω C C) = E X,x ||ω C Cx -ω * x|| 2 = Tr E X,x ω * X ⊥ C || + C ⊥ xx T X ⊥ C || + C ⊥ T ω T * = Tr E X ω * X ⊥ C || + C ⊥ X ⊥ C || + C ⊥ T ω T * .Since projections are idempotent andC ⊥ C || = C || C ⊥ = 0, X ⊥ C || + C ⊥ X ⊥ C || + C ⊥ T = X ⊥ C || C || X ⊥ + X ⊥ C || C ⊥ + C ⊥ C || X ⊥ + C ⊥ C ⊥ = X ⊥ C || X ⊥ + C ⊥ ,and as a consequence, thatR(ω C C) = Tr E X ω * X ⊥ C || X ⊥ + C ⊥ ω T * = Tr ω * E X X ⊥ C || X ⊥ + C ⊥ ω T * .X ⊥ , C || are both projections and since X follows an isotropic distribution according to our assumptions, its right singular vectors, which coincide with the eigenvectors of X ⊥ are Haar distributed. Therefore, we can apply the lemma 2 with p = d -n, q = |C| we obtain thatE X X ⊥ C || X ⊥ = 1 - n d |C|n (d -1)(d + 2) I d×d + 1 - dn (d -1)(d + 2) C || .Recalling C ∥ = I d×d -C ⊥ and rearranging the terms we obtainE X X ⊥ C || X ⊥ + C ⊥ = 1 - n d 1 - n(d -|C|) (d + -1) I d×d + n d + n(d -n) (d + 2)(d -1) C ⊥ .Lastly, we use R(ω t ) = 1 -n d (see [5] ) and our definition ofε := Tr ω * C ⊥ ω T * to conclude that R(ω C C) = 1 -n d -|C| (d + 2)(d -1) R(ω t ) + n 1 d + d -n (d + 2)(d -1)ε,In this section, we expand on specific details of the paper that, albeit non-essential for the main text, might be of interest to specific readers.To ensure that the composition is well defined, we need to impose one of the following two conditions: either for the output probe or for the concept set. Either (1) if concept sets are unordered, then H C must be a complete set of maps under permutation symmetry, that is, for any map g ∈ H C and any permutation σ of C, g • σ ∈ H C , and the learning method is also invariant under feature permutations, which holds for the output methods considered in the paper; alternatively, (2) C is a concept sequence, not a set. In the first case, the composition is well defined since it is equivalent across all orderings of the elements; in the second, ∪ should be substituted by ×.We note that the natural models used as probes-such as linear regression, kernel regression, fully connected neural networks, decision trees, and k-nearest neighbors, among others-constitute parameterized hypothesis spaces that form a complete set of maps under permutation symmetry. Additionally, the learning methods employed are invariant under feature permutations, provided that isotropic initialization is used and mild assumptions regarding the optimization algorithm and loss function are met. Consequently, these models and their associated learning procedures maintain structural integrity and invariance when input features are permuted, ensuring that the composition remains well-defined across different concept orderings.To elucidate the relevance of the properties in Definition 1 that distinguish Concept sets from other sets of characteristic functions, it is helpful to consider non-concept characteristic functions. We begin with a specific example before advancing to a more formal characterization.Humans tend to develop concepts that are relevant to their areas of interest, which are indicative of their underlying task T . Despite being exposed to a wide range of occurrences, individuals do not cultivate concepts outside their domain of interest. For instance, consider filmography-related concepts such as a "Jump Cut," where two sequential shots of the same subject are captured from slightly varying camera positions, or a "Dutch Tilt," involving the intentional tilting of the camera to create a sense of disorientation. According to Definition 1, people not interested in filmography would not incorporate these characteristic functions into their concept set. This omission occurs because such characteristics add negligible expressiveness to their existing concept set, meaning that the parameter N 0 approaches infinity without significantly enhancing model-aware inductive bias. Consequently, N 1 becomes less than N 0 , which does not satisfy the definition.In more abstract terms, a characteristic function c that does not contribute additional valuable information beyond the existing concept set C for the task T exhibits low expressiveness, indicated by a large N 0 , without a corresponding increase in N 1 . This scenario arises when the target variables are conditionally independent of c given C. Examples include concepts that are irrelevant to the task at hand (e.g., the presence of tinted glass when predicting attributes of a Model X vehicle) or concepts that are entirely redundant with those already present in C.Moreover, low expressiveness can result when the output model is incapable of capturing the correlation introduced by c. For example, a characteristic function c could aid in clustering the input distribution into two concentric spheres, but a linear model would fail to take advantage of this structure effectively. Furthermore, even if c provides information that is theoretically representable, the inductive bias of the learning method may disfavor the optimal hypothesis corresponding to this representation. In such cases, despite the presence of informative characteristic functions, N 0 remains large, indicating low expressiveness.We expand on the flexibility of Concept-Based Models (CBMs), highlighting properties that can facilitate future advancements.Consider the objective of learning a target function f * : X → Y. In a CBM framework, this involves a concept representation C * : X → R C followed by a mapping f * C : R C → Y from concepts to targets. By maintaining a fixed concept set C and its associated representation R C , we allow the replacement of the concept mapping estimator Ĉ with an alternative C without altering the probe fC . This substitution is viable as long as the concept representation R C remains consistent in dimensionality and semantic meaning. For example, upgrading from a CLIP-based concept representation to a more advanced CLIP2 preserves the probe's applicability. However, probes are not interchangeable between fundamentally different concept representations (e.g., raw CLIP vs. CLIP2) due to potential discrepancies in metrics or dimensionality. This emphasizes the role of R C as a stable interface with fixed characteristics. Furthermore, CBMs facilitate the harmonization of datasets with varying features or modalities X 1 , . . . , X k (such as images from different sensors). By projecting each input X i into the common concept space R C through mappings C * i : X i → R C , CBMs ensure semantic consistency across diverse datasets. This unified representation simplifies the integration and analysis of multi-modal data, leveraging the fixed semantic meaning of the concept set.The primary objective of our method and experiments is to illustrate and validate our theoretical insights, which remain agnostic to the concept sampling method. Although large language models (LLMs) are utilized for concept generation in our experiments, this choice does not compromise the validity or generality of our theoretical contributions. Our theoretical insights are independent of the concept generation method, which emphasizes the versatility and applicability of our insights regardless of concepts being derived from LLMs, human experts, structured knowledge bases, or a combination thereof.We employ LLMs to streamline the process by reducing the need for extensive human expertise and to provide task-specific concepts flexibly. LLMs have been shown to be valuable samplers/generators, especially as part of a more complex system designed to be robust against potential lower-quality samples (e.g., [4, 17, 34] ), but alternative methods are equally viable. These alternatives include:• Human-Generated Concepts: Concepts manually curated, tailored to specific tasks.• Concept Graphs: Using structured knowledge bases such as ConceptNet [35] to derive relevant concepts. • Correlated Text Corpora: Leveraging patterns and correlations within large text datasets like Wikipedia to identify meaningful concepts. • Hybrid Approaches: Enhancing LLM-generated concepts by conditioning their context on external knowledge sources, such as Concept Graphs or Text Corpora, thus improving their relevance and quality, as mentioned in the main text.We also note that our method can be regarded as a rejection-sampling loop that ensures the quality of the concepts generated and mitigates the potential limitations associated with the reliance on LLMs for concept sampling. It does so by rejecting concepts that do not meet predefined theoretical standards and selecting only those concepts that significantly contribute to the model-aware inductive bias, thereby maintaining the integrity of the concept set.This approach thus fosters the inclusion of only relevant and high-quality concepts, regardless of the base generation method.Datasets For CIFAR10 we use CIFAR-10 python version [25] , and for MetaShift (MIT License) we follow the scripts provided by the MetaShift Repo [26] .Models For generating concept sets, we use GPT 4-turbo-2024-04-09 [2] through the ChatGPT web app. For jointly embedding images and text, we use CLIP ViT-B/32 [32] .The computational resources used are consistent across all experiments and are detailed below to facilitate reproducibility. Specifically, an Azure Machine NC96ads A100 v4 was used with the following specifications:GPU Details:• Type of Compute Workers: A single NVIDIA V100 GPU was used.• Memory: Each NVIDIA V100 GPU is equipped with 80 GiB of memory.• Time of Execution: Each experiment runs in less than 5 hours on a single GPU.The total computing time between experiments was approximately 20 hours. No further computing was required for the project, except for dummy runs intended to verify the code's correct functioning on an M2 Pro MacBook Pro with 32 GiB of memory.Additional System Information:• CPU: AMD EPYC 7V13 64-Core Processor with 96 CPUs at 3.09 GHz.• RAM: 866 GiB total, 23 GiB used, 832 GiB free, 61 GiB swap memory.For the generation of concept sets, instead of keeping or discarding a concept before generating a new one, we first generated a pool of concepts, which we then sampled sequentially and filtered the subset of interest. To generate the initial pool, we started by providing the following prompt to GPT 4-turbo-2024-04-09:I am building a classifier between {Class_Names} on the {Dataset_Name} dataset. I want to use a concept-bottleneck model to predict these classes.To that end, I want you to propose a set of {N} concepts for each class that can help me differentiate between {Class_Names} for the concept-bottleneck model.Propose only concepts that can be identified from an image without sound or video.From the result of this prompt, we trimmed the concepts (e.g., "animal with floppy ears" → "floppy ears") to make them more suitable for CLIP embedding. The resulting initial pool of concepts for each experiment is provided below in the detailed description.The dataset used in this experiment is CIFAR-10, which consists of 10 classes: Airplane, Automobile, Bird, Cat, Deer, Dog, Frog, Horse, Ship, and Truck.The train sizes evaluated are [40, 80, 160, 320, 640, 1280, 2560, 5120 , 10000] samples, and the test size is fixed at the full 10,000 test samples.Three concept set sizes are evaluated: 20 concepts, 30 concepts, and 50 concepts.The filtering method described in Section 5 is used, which iteratively draws one concept for each class, the one that minimizes the empirical risk in five seeds over a 50/50 CIFAR-10 training set split. The entropy is estimated through 100 bins, and a lower threshold of 0.02 ensures that not all activations are essentially equivalent.C.5 Detailed description: Robustness to distribution shiftsThe dataset used in this experiment is MetaShift, focusing on the "Cat vs. Dog" setting, as described in [26] . The percentages of minority classes evaluated are [0, 0.01, 0.07, 0.13]. The random seeds used for this evaluation are [42, 43, 44, 45, 46, 47, 48, 49, 50, 51] .The embedding model used is CLIP ViT-B/32. The preprocessing pipeline is the same as in the above experiment.The evaluated output models include a linear regressor, a decision tree, and nearest neighbors, all with the standard hyperparameters from sklearn and trained on one hot encoded label.The initial set of concepts generated by GPT-4 from which we sample is: Sharp, pointy ears; Floppy ears; Rounded ears; Pointy ears; Thin tail with a tapering end; Bushy tail; Curly tail; Almond-shaped eyes; Round eyes; Fine, soft fur; Smooth short fur; Curly fur; Wiry fur; Short, pointed snout; Long, narrow snout; Flat snout; Fine whiskers; Thick whiskers; Slender and agile body; Large body; Compact paws; Large paws; Grooming behavior; Arching back stretch; Wagging tail.The filtering method described in Section 5 is used, which iteratively draws a concept and keeps it if it decreases the empirical risk in five seeds (threshold of 0). We used a 70/30 split for empirical risk estimation. The entropy is estimated through 10 bins, and a lower threshold of 0.1 ensures that not all activations fall into the same bucket.In this appendix, we discuss additional experiments to illustrate our theoretical insights further by evaluating concept bottleneck models (CBMs) on additional datasets and baselines. Specifically, we discuss:1. Data-Efficiency Experiments on three datasets: CUB-200-2011 [37] , Food-101 [7] , and the Describable Textures Dataset (DTD) [9] , to evaluate the performance of CBMs across varying sample sizes.2. Out-of-Distribution Generalization on the CINIC-10 dataset [11] , to assess the robustness of CBMs to distribution shifts.Comparison with Label-Free Concept Bottleneck Models [30] on CIFAR-10, benchmarking our method against a relevant baseline from the literature. [37] in Figure 4a , Food-101 [7] in Figure 4c , and DTD [9] in Figure 4b . This figure illustrates the performance of both models across varying data availability, highlighting the increased data efficiency of CBMs in the low sample regime and the effect of misspecification in the large sample regime (see Theorem 1).To evaluate the data efficiency of our CBM approach, we conducted experiments on three diverse datasets.• CUB-200-2011 [37] : A fine-grained dataset containing 200 classes of bird species, with 11,788 images annotated with 312 binary attributes (concepts).• Food-101 [7] : A dataset with 101 food categories comprising 101,000 images.• Describable Textures Dataset (DTD) [9] : A texture database with 47 classes and 5,640 images, annotated with attributes describing the textures.For each dataset, we compared the performance of:• Baseline: A linear classifier trained directly on the CLIP [32] image embeddings.• Our CBM: A concept bottleneck model where we first predict concepts from the image embeddings and then use these predicted concepts to classify the images.We varied the number of training samples to assess performance in different sample size regimes.For each training size, we randomly sampled the corresponding number of examples (with balanced classes) and trained the models five times with different random seeds to obtain averaged results.The results are summarized in Figure 4 . We observe the following trends:• Small Sample Regime: In the low-data regime (< 10 samples per class), our CBM outperforms the baseline in all three datasets. This supports our theoretical insight from Theorem 1, which predicts that in the small sample regime, the first term of the risk dominates, and the structured approach of the CBM leads to increased sample efficiency.• Large Sample Regime: In the larger-data regime, the baseline begins to outperform the CBM. This reversal is explained by the increasing influence of the approximation error term, encapsulated in the ε coefficient in our theoretical analysis. As the sample size grows, the information loss due to the bottleneck becomes more significant, determining the asymptotic performance gap between the CBM and the baseline.These results reaffirm the insights of Theorem 1, demonstrating how the trade-off between sample efficiency and misspecification manifests itself in practice across different data sets. The CBM's advantage in low-data settings highlights its potential for applications where labeled data are very scarce (e.g., rare diseases).D.2 Out-of-Distribution Generalization on CINIC-10To evaluate the robustness of CBMs to distribution shifts, we conducted an out-of-distribution (OOD) generalization experiment using the CINIC-10 dataset [11] . CINIC-10 is derived from both CIFAR-10 [25] and ImageNet [18] , providing a testbed for OOD evaluation.• Training Data: We trained models on a subset of the CIFAR-10 training set, with 750 images across 10 classes.• Test Data: We evaluated the models in ImageNet images that belong to subclasses of the original CIFAR-10 classes to introduce a distribution shift between the training and test data.We compared the performance of the baseline linear classifier trained on CLIP image embeddings against our CBM, using predicted concepts for classification.The results are presented in Table 1 . Our CBM demonstrates superior OOD generalization performance compared to the baseline. This improved OOD performance aligns with our previous results on the 12 datasets from the MetaShift collection, as discussed in Figure 3 . The CBM's reliance on intermediate concepts, which can be more stable under distribution shifts and potentially remove spurious features and confounders, as suggested by Theorem 2, contributes to its robustness.Model Accuracy (%) Vanilla 70.4 ± 1.2 CBM 78.8 ± 0.7 Table 1 : Out-of-distribution generalization comparison on between a linear probe on the CLIP [32] embedding and our CBM method. We compared our curation of concept sets with the Label-Free Concept Bottleneck Model [30] (LF-CBM) method on the CIFAR-10 dataset.For a fair comparison of the effect of the concept set selection, we made the following modifications.• Concept Set Selection: We used the same sampling mechanism for concept selection, sampling concepts c i ∼ L(c | C T ) using a fixed language model L and context C T (i.e., prompt). • Image Embeddings: Both methods used the CLIP ViT-B/32 model to obtain image embeddings. • Classifier Architecture: A linear classifier (probe) was trained on top of the concept embeddings.We varied the training sample sizes and averaged the results over five random seeds.Figure 5 illustrates the performance comparison between these two approaches, which highlights the critical role of concept set curation through the consistent performance gap of more than 7.3% across all training set sizes and up to 17.7%.These results highlight the relevance of considering the properties of concept sets when using CBMs, reinforcing the value of our theoretical contributions. The CBM Assumption We make the implicit assumption that human concepts have predictive power for ML models, as discussed in Section 3.Concepts as a linear space Although the assumption that concepts correspond to directions in a high-dimensional space holds empirically (e.g., for the CLIP embedding [21, 41, 6] ), it may break when inspected closely. For example, this assumption cannot capture hierarchical relationships between concepts. Investigating alternative representations and methods to identify and utilize hierarchical concepts would enhance the robustness and interpretability of CBMs.Input distribution for Theorem 1 We assume that the inputs are distributed isotropically for analytical tractability. Although it might not hold in some real-world distributions, this assumption includes all distributions whose density depends only on the distance to the origin, thereby being quite flexible. Additionally, we observe in section 6 that the qualitative behavior in real-world tasks aligns with the results from the theorem derived under these assumptions.Interaction of effects The proposed theory addresses the analysis of in-domain generalization, the impact of confounding, and error-in-variables separately. Still, one could explore considering all of them simultaneously and their interactions. Integrating these aspects into a unified theoretical framework remains an open challenge and could provide a more comprehensive understanding of CBMs.Scalability to massive datasets The method for estimating the impact on the risk of adding a new concept can become computationally expensive for large-scale datasets. For such cases, numerical methods for solving linear equations, such as EigenPro [1] , or other risk estimation methods, should be considered to improve efficiency without compromising accuracy.Inheritance of the identifier's bias CBMs may inherit biases present in the training data or external knowledge sources, as discussed in Appendix G. More research is needed to mitigate potential biases and guarantee equitable outcomes.Transference of Concept Properties Future work could further explore the CBM assumption that beneficial inductive biases for humans extend to specific output models. This could involve investigating how different model architectures and training paradigms impact the transferability of these biases.Operationalizing Concepts Considering concepts through the lens of our characterization provides a principled approach to operationalizing them. Methods to generate concept sets based on their ability to decrease entropy or enhance separability could be developed for unsupervised settings, potentially leveraging statistical measures and techniques like the finite neural tangent kernel for deeper analysis.Derivation from Models Concepts can be extracted from trained models during a 'model sleeping' phase, where latent representations are analyzed and ranked according to their efficacy in reducing complexity and enhancing task performance. This approach could provide insight into the most informative concepts learned by the model.Learning Conventional meta-learning and transfer learning methods often integrate datasets with shared input features and targets. A concept-based representation could facilitate data transfer across diverse input spaces and enhance the interpretability, generalizability, and robustness of the model to data shifts. Leveraging large-language models (LLMs) to identify relevant concepts for a target task from a pool of knowledge datasets offers a novel pathway for knowledge transfer.Hierarchical Concept Structures Introducing a hierarchical structure of concepts as initially explored by [31, 36] could provide a more nuanced understanding and representation of the data, mirroring human cognitive processes. Although challenging to achieve with foundational models, this approach could be explored by recursively distilling the most valuable concepts from successive layers, enhancing the model's ability to capture complex relationships.Broader Implications and Ethical Considerations Future research should also consider the broader implications and ethical considerations of using concept-based models. This includes addressing potential biases, ensuring fairness, and evaluating the impact of these models in various real-world applications.Although our main contributions can be considered foundational research and raise no immediate fairness concerns, discussing the presence of biases in concept identification models for practical use cases is relevant. These models have been shown to inherit and propagate societal biases [3] , potentially leading to unfair or discriminatory representations that will affect the resulting concept representations.Several strategies exist to mitigate these risks. First, we should ensure that we use models whose training datasets are diverse and representative, thoroughly evaluated for bias, and employ techniques to detect and correct biases. In particular, we can focus on models that stress transparency by providing comprehensive documentation of datasets and detailing bias detection and correction efforts.However, provided that we used a model with solid guarantees of fairness, our conclusions suggest that concept representations arising from such models can help reduce the bias inherited by trained models on potentially biased datasets.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Justification: Our research does not involve human subjects. We use publicly available datasets, CIFAR-10 and MetaShift, which do not include issues with privacy, consent, and deprecated datasets to the best of our knowledge. Furthermore, our methodology is thoroughly documented in appendix C.2, promoting reproducibility and transparency, and we provide the code to ensure access to research artifacts. We discuss societal impacts and, in particular, potential biases in appendix G.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024).We assume static tasks for simplicity, but we could admit the superclass of multi-step tasks, arguably more typical for humans. Also, for simplicity, we consider the effect of a new concept on a single task. Still, one might want to consider the distribution of human tasks and compute the expected improvement in risk across all tasks.Interestingly, if we accept these properties for concepts, we could investigate what the ML models that most align with the human predictive model are, and thus provide plausible hypotheses for the potential architecture of the human brain.Code can be found at https://github.com/maxruizluyten/theoretical-concepts or https:// github.com/vanderschaarlab/theoretical-concepts.Plus, if the concept set is appropriately chosen, the ε itself should be small.Even in this sample regime, where ε is the dominating term. 


Decision: After a fruitfuful discussion, the reviewers agreed that studying the properties of concepts sets is a very significant - and so far understudied - research question, and that the paper does a good job at defining and analyzing critical properties for concept sets.  The empirical analysis, including the new results provided in the rebuttal, seem sufficient to confirm the theoretical findings.  All in all, this is a solid and insightful contribution.

I encourage the authors to improve the notation and to integrate all suggestions provided by the reviewers.

Reviews: review: paper_summary: paper_summary: This paper addresses an important research question in CBM — understanding the properties of concept sets and their connection to the performance of CBMs.
A theoretical framework for concept sets is proposed, focusing on two desiderata for concepts: expressiveness and model-aware inductive bias. 
Their theoretical analysis covers under what conditions the concept representation-based predictions outperform raw feature representation-based predictions.
Empirical evaluation with two datasets confirms their theoretical insights that well-chosen concept sets improve sample efficiency and robustness under distribution shifts.
strength_weakness: strength_weakness: Notations are very loosely defined:
* Notations in introduction are used without being defined; for instance, $f, g, \theta, \mathcal{H}$. 
* in line 104, the definition of function f as a concatenation of a mapping $\hat{g}_m$ and a set $[c_1, \dots, c_m]$ is awkward. 
* what is $d$ in Theorem 1?
* in line 154, please clarify that $x$ is not a raw input (e.g., image), but a feature representation output from a backbone foundation model. 

Limited experiments:
* Evaluated only with two datasets.
* No performance comparison with other CBM methods, given the same number of concepts and training set size.
* No demonstration and anlysis on the actual results of generated concept sets

Please increase the fonts in the figures for visibility.
questions: questions: * in lines 135-136, `This flexibility means we can replace the underlying ... while keeping the output model unchanged.` Could you please elaborate on this? I reckon the output model should also be changed when the coupled concept identification model is changed.
* in lines 137-139, `The concept set serves as a stable communication interface ... potentially harmonizing datasets and modalities`. Please extend these statements and explain the broader potential impact of this perspective using concept representations. 
* how do you determine the thresholds in concept generation? (i.e., $\Omega_m$, $R_m$).
limitations: limitations: Limitations are described in Appendix C.
paper_summary: paper_summary: This paper presents theoretical contributions related to CBM, which delves into the impact that the choice of concept set has on CBM performance. It identifies advantageous conditions for CBMs, offering an orthogonal and meaningful perspective compared to most other works on CBMs.
strength_weakness: strength_weakness: - The multi-step approach introduced in Sec.5.2 seems to be difficult and brings uncertainty from LLMs, which to some extent limits the practicality and generality.
- It would be better if more baselines and datasets were provided in the experiment part. Additionally, due to the costly training procedure, this paper only incorporates the concept representations from foundational multimodal models. This is reasonable but complicates comparisons with other CBMs.
questions: questions: None.
limitations: limitations: Yes.
paper_summary: paper_summary: This paper provides a theoretical analysis of properties of concept sets in CLIP-based CBMs. Specifically, the authors focus on the effect of concept sets on the empirical performance of CBMs in the low-resource regime and under distribution shifts.  Towards this, the authors identify two characteristics of concept sets that help improve CBM performance: the size of CBMs and the degree of misspecification. The authors validate their findings on two datasets: CIFAR-10 (for evaluating image classifier performance) and MetaShift (for evaluating distribution shift).
strength_weakness: strength_weakness: _(This work is outside my area of expertise; I have slight empirical familiarity with CBMs, but I cannot comment on the mathematical correctness of the proofs. Most of my comments are in the questions section)._

__Lacking experimental evaluation__: We have much better datasets than CIFAR-10 to measure the efficacy of an image classifier. I recommend the authors look at LaBO's `[1]` experimental evaluation section for a more comprehensive set of experiments.

Overall, I'm recommending a __Weak Accept__. Theoretical research in the properties of CLIP based CBMs is deeply desired and relevant to the NeurIPS community. I haven't given a higher score because it's hard to make informed opinions based on the current evaluation setup.
questions: questions: Questions while reading the paper:
- L23: I think CBMs can be motivated with a better example. Here is another example: A “Tesla model X” did not exist when CLIP was trained, yet we can make a reasonably accurate classifier with a concept bottleneck: {SUV, T logo, gull wing doors, (lack of) exhaust pipe}. 
- L99: What is P here?
- L106: (Definition 1) What is a non-trivial instantiation of a set that is rejected by this definition (ie: a set which is not a concept set)?  
- L154: I understand that the theoretical justification necessitates linearity, but empirical studies suggest that the final CLIP activation is based on a hierarchical composition of neuron activations `[5]`. Can such relationships be captured by the linear model?
-  L248: I agree that removing redundant concepts is important. However, in practice, redundant concepts seem to help improve performance (`[4]` identifies almost 3000 concepts for some datasets).
- L267: I recommend the authors try out more datasets than just CIFAR10 `[6]`. I think following the experimental section for LaBO `[1]`, one of the paper's cited, would be a good idea here.I recommend testing in domain generalization on CINIC-10 `[7]` as well.
-  L275: The appendix mentions using ViT B-32 while this section mentions using ViT L-14. The provided code shows references to both ViT B-32 (for CLIP embedding generation) and ViT L-14 (for querying DINO features; which I'm assuming isn't part of this paper). A clarification of which model was used in which context would be beneficial! 


`[5]`: https://distill.pub/2021/multimodal-neurons/

`[6]`: https://arxiv.org/pdf/1806.00451

`[7]`: https://arxiv.org/abs/1810.03505


-----
Increasing my score to __Accept__ after discussions with authors.
limitations: limitations: The authors have adequately addressed limitations in the Appendix. I appreciate the inclusion of a broader impacts section!

Comments: comment: Dear Reviewer,

I would appreciate if you could comment on the author's rebuttal, in light of the upcoming deadline.

Thank you,
Your AC
All the LaTeX formulations are correct this time, even though I didn't make any changes...sorry for the confusion. Thank you for your reply and I will take your feedback into account.
Dear Reviewer,

Thank you for your continued engagement and the thoughtful follow-up. We are pleased that the additional experimental results addressed most of your concerns.

Regarding the performance discrepancy you observed with Label-free CBM using the ViT-B/32 backbone on CIFAR-10, this is indeed primarily due to differences in training size. As discussed in our global response, we also made adjustments to the concept set in the fifth code block of the `GPT_conceptset_processor.ipynb` file from the available Label-Free CBM repository, specifically modifying the concept set sampler $c_i \\sim L(c | C_T)$ to ensure a fair comparison between Label-free CBM and our method. Nonetheless, this modification led to a slight improvement in the performance of Label-free CBM on CIFAR-10, where we achieved an accuracy of $86.79\\%$, which aligns closely with your results. 

To clarify and avoid any confusion, we will add a final data point to Figure 2 in the attached PDF, showing the performance on the full CIFAR-10 dataset. Here, our method achieves an accuracy of $92.23\\%$, thus maintaining an advantage over the baseline comparable to previous data points.

You are correct about the typo in the figure labels; the left figure in the second row should be labeled "Figure 1c." We have corrected this in the revised document.

Regarding your feedback on using LaTeX formatting, we apologize for any readability issues you encountered. On our end, the equations render correctly, so we are not entirely sure what specific formatting challenges you experienced. However, we fully appreciate the importance of clarity and are more than willing to reformat the content using markdown or any other format you prefer. If you could provide more details or specify your preferred format, we would happily make the necessary adjustments to ensure the content is as accessible as possible.

We hope that these clarifications address all your remaining concerns. We also hope that the improvements and additional results presented across the rebuttal will prompt you to consider raising your evaluation of our work.

Thank you again for your valuable feedback and time.
Thanks for the authors' response. Most of my concerns have been addressed and I'm glad to see the authors had supplemented some empirically results to better show the effectiveness. By the way, I have also tried to run Label-free CBM with VIT-B/32 backbone on CIFAR10 and the result is about 86.5%, a bit higher than that in Figure 2 in the rebuttal PDF (a typo here, Figure 2 should be Figure 2b I think, and the left one should be Figure 2a not 2c). Could this discrepancy be due to differences in training size?

I have read the comments and responses from the other reviewers and currently have no further questions. However, I found the responses difficult to read due to the extensive use of LaTeX formatting. It would be helpful to use markdown formatting in the rebuttal period for improved readability.
Dear Reviewer,

Once more, thank you very much for your thoughtful and constructive review. We are pleased your main concerns were addressed and grateful for your increased acceptance score.
Thank you for the response! I think the additional studies address my main concern regarding evaluation setup. I'm increasing my score to recommend Acceptance.