A theoretical design of concept sets: improving the predictability of concept bottleneck models
Authors: Max Ruiz Luyten
Mihaela van der Schaar
Venue: NeurIPS 2024 poster (2024)
Keywords: Representation Learning
Embedding Approaches
Learning Theory
Neural Abstract Machines
Nonlinear Dimensionality Reduction and Manifold Learning
One-Shot/Low-Shot Learning Approaches
Primary area: other
TL;DR: We present a theoretical analysis of Concept Bottleneck Models, which motivates a principled generation method for concept sets. We empirically verify its impact on CBMs' sample efficiency and robustness.

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.

A Theoretical design of Concept Sets: improving the predictability of concept bottleneck models
Max Ruiz Luyten University of Cambridge Cambridge CB3 OWA mr @cam. ac. uk
Mihaela van der Schaar University of Cambridge Cambridge CB3 OWA mv4720cam. ac. uk
Abstract
Concept-based learning, promising approach in machine learning, emphasizes the value of high-level representations called concepts. However, despite growing interest in cancept-bottlened models (CBMs), there is a lack of clear understand- ing regarding the properties of concept sets and their impact on model performance. In this work, we define concepts within the machine learning context, highlight- ing their core properties: expressiveness and model-aware inductive bias, and we make explicit the underlying assumption of CBMs. We establish theoretical results for guide the design of concept sets that optimize model performance. Specifically, we demonstrate that well-chosen concept sets can improve sample efficiency and iit-of-diitribution robustness in the appropriate regimes. Based these insights, we propose a method to effectively identify informative and non-redundant con- cepts. We validate approach with experiments 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.
models (CBMs), revealing how these properties
Introduction
Concept Bottleneck Models (CBMs) [23] offer compelling trifecta of interpretability [19], interven- ability, and predictability [28]. They are inspired by the power 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 car's action from raw images, CBM first identifies key concepts such as the presence of a semaphore or a pedestrian crossing the road (C X - C), and Tesla Model
learns : C - y' to act based them (g (x:). Indeed, despite never having X, one could reasonably classify them provided they can identify an SUV, a 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,2] 22).
Despite their promise, the predictability of CBMs, particularly in relation to the properties of the concept set C, remains poorly understood. 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-worke applications.
In this paper, we address this gap by systematically investigating the properties of concept sets {cI,..., Cm and their influence on model performance. We answer the following key questions:
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 misspecificcatinn E as primary drivers of the performance of the CBM, where e == || arg min arg min 9Ene ((g C) with H S {f X - C) He S {g C + } 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 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(ğ o C') as the sample size - 0c. Model-awarr inductive bias implies beneficial inductive bias, improving performance in low-sample regimes (n R 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 multimodal foundational models such CLIP [30, 39, 41]. We derive a key theorem (Theorem 1) that compares the expected loss of mancept-based models (R(g C). 9 E arg ge {g o C')) with the baseline counterpart (R(f), f E arg min f The theorem demonstrates that concept-basse set is well chosen by minimizing the size of the concept set |C] while controlling the misspecification term E. 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.
(f)). (e(
models can outperform baseline models if the concept
Based on these insights, we propose method in Section 5 to generate informative and non-redundant concept We also discuss potential failure modes of CBMs and how existing approaches can mitigate them. Finally, we empirically validate our framework in Section with experiments on CIFAR-10 and MetaShift datasets, showing that appropriately designed CBMs outperform traditional models, particularly in low data and distribution shift scenarios.
Contributions.
1. Theoretical Framework for Concept Sets: We introduce a novel theoretical frame- work 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.
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 clear understanding of the design choices that enhance CBM performance.
3. Empirical validation:
We validate our results through experiments on CIFAR-IO 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.
2 Related Work
Incorporation 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 under- standing 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 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 hypothetical set of concepts as C' and a particular concept 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 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 "kitchen utensil", "octopuses" are just excluded from the concept of "fish". As such, concepts lend themselves the fuzzy mathematical formulation of membership functions, a generalization of characteristic functions. Thus, the concept can be unequivocally represented mapping : X + [].
Concepts aid in everyday-task inference Not all membership functions qualify concepts; the missing component is their usefulness in task-specific inference. For a new concept to be valuable, it must improve predictability for subset of tasks relevant to humans. This happen either by capturing new nuances of inputs (for example, new color tones) or integrating different concepts into more comprehensive entity (e.g., grouping animals into families).
Consider a task T, defined as a tuple' (D, f), where D {(1,, ys) aidd P(X, drawn from the data generation process PP( and & is loss function. Define the n-risk of a model class fe on task as the expected loss of a model trained on n samples, R, (fe) =
dataset
ED.,. [(( (D))). w) Consider the output hypothesis spaces He S {g + y} complete under permutation symmetry and the learning algorithm invariant under feature permutations. We refer to Appendix B.1 for a technical discussion of this assumption.
Wee 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 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.
3

---

Definition 1. [Concept set] Let (()) X y be a model trained on the task T = (D, e), and C a preexisting concept set. potentially void, of size m Given a membership function Cm. we denote the conceptualized model fcu(e..) 9m 0o) o , Cmly such that 9m : U {cm) ) y trained on the conceptualized input ((ey(=)))sem)))ee
Then, C U (Cm) is concept set if there exists No S N1 N such that
Ra((f)) Ru(feu(om)) for No S n (expressiveness) (x) > R.(feutem.) for S N1 (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-award awore inductive bias) and better than the smaller concept set in the large-sample domain (expressiveness). 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 9m corresponds to the human model. This definition can be regarded not only as qualifying condition for a membership function be considered concept, but also 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 new concept even take hierarchical approach by unveiling the most relevant concepts identify a given set of already established concepts.
The CBM Assumption An implicit assumption behind concept- maasept-based models that make explicit is that such human concepts will also have predictive power for given ML output model. The output model is conventionally linear for interpretabilityy
Although expressiveness and model-aware inductive bias may not always transfer across different models, it is reasonable to assume that 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 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 highly varied distribution, concepts are unlikely to be entangled with spurious features, which we also test in our insight experiments.
Model agnostic concepts In some cases, may be useful to evaluate the quality of a con- cept set without knowing the output model. We propose using an information- -heoryy metric: Dxi [Pi,P((Y|CU (X)))()))P((((X(X) > O. A new concept should provide significant information on the output.
In the subsequent sections, 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 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.
'Interestingl,, 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.

---

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, will also become apparent in what regimes it is undesirable to bottleneck a model on concepts and potential solutions.
In our analysis, we focus bottleneck models based on multi-modal foundational models, such as CLIP [30, 39, 41].
recently popular approach to concept- anccept-based models, that is, concept
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 related to directions, and is typical to use a linear output layer on top of such representation.
Definition 2 (Risk), Let x, (6) i..dd
P(X) for E [m], and let y = f=((()). Given a loss L: y x y + R. the risk of predictor f trained on the n samples (X,z) is given by
R(f) Ex,x {c (())
(1)
Now, since the output layer is conventionally linear, we may write f*(x w'x and f(z) Wz. We further consider the 12 loss, where the predictor takes the analytical form a Vxt, X representing the Moore- Penrose pseudoinverse of X.
Given concepts are represented by directions in this space, can write set of concepts C as set of dual vectors {c(1) c(() } E X", we can consequently consider our conceptual representation (k)JT, and our overall concept model fc 9e C.
CX with 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 isotropic distribution on the d- dimeenssional input, then the risk of the concept- model R(fc) is given by d
R(fc) = (1-"
() (1-11-++))))) R())) + (3 (d+
d [c)
where E -|w
and C+ stands the orthogonal projection operator onto the orthogonal complement of the concept vector's span.
We note that this result aligns with 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 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 O, the remaining terms directly compare the concept and the baseline risks R(fe), R().). In fact, in this situation, we have a strict benefit for using the concept model, that is, R(fc) < R(f.). Interestingly, provided E se O, 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.c., increased sample efficiency).
Now, let us focus on the setting of spurious features due 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 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 E X Then,
5

---

Theorem 2. In the presence of confounders {z1, 22 22..... 2x7 E 2,, given concept E X,, the bias in the ordinary least squares estimator satisfies
.2....,.11...
|Bias[fo\X)ll (I((e,21), 21), (fe, (x)222
In particular, the classifier f(e) remains unbiased if and only if span(21 21, 22, ..,............................. .,,,,))
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 small cosine similarity), we can expect the bias injected by the spurious feature to be significantly reduced.
4.1 Effect of Errors-in-variable
We must admit that our concept identifier can be imperfect, implying our foundational embedding consists of noisy covariates, requiring an inoriii--aaiaales 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 of single noisy feature žк IKK u, where 2; represents the observed covariate with noise u, and y = x wi + is the actual model, the least-squares estimator w is biased. Specifically, the estimated coefficient for this variable attenuated by wk = a + W-K. Not only the estimated coefficient WK is increasingly shrunk by the noise towards zero, but all the other coefficients W; 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 refers to the properties that a concept set must satisfy, to use such a concept set, required that we have the concept mappings c X - [o, 1][CI, This can be achieved by collecting a dataset X' 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 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 I, although powerful, direct foundational model em- beddings encode information in high-ddimensional 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 decision-making processes for given task. This hinders not only generalization but also the interpretability of the model.
5.1 Concept Identification
First, suppose that we already have a concept C. Let us explicitly describe how to obtain the concept representation using 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 shared space. We can then use the appropriate metric (or similarity measure) in this space compute the degree presence of concept for each given input.
the most common scenario, the distance consists of the cosine similarity, so the textual concepts C. (t.....tte tM }o and the dataset is D {21...., .N computed as
I. }. the concept representation c(x) can be
(x) (Ex(x), (r))))
|[xx())]l
with Fx and Er being the input and text encoders respectively. This the approach that we use in experiment section.

---

5.2 Concept-set Generation
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 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 LLMSs as base-concept samplers.
As shown in Theorem 1, the properties of the set of concepts are crucial for the effectiveness of the should aim balance the following objectives: (I) achieve minimal
embedding. In particular, misspecificatiio E, 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 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 identify them to minimize the error-in error-in-variane in-variable effect.
Motivated by our theoretical desiderata, we propose a multistep approach.
Initial generation of a complete concept set that satisfies (1). To achieve that, we propose employing language model L to sample sufficiently expressive set achieve a sufficiently low misspecification ε, This can be promoted by conditioning the generation on the context task Cy so that concepts ConceptNet and Wikipedia to promote further quality and diversity Cx C Cy. That is,
relevant, which could include external knowledge such as
0 I(cCTT
2. For each concept, we must ensure it can be properly identified and its presence is informative for T. That is, è; should be discarded if the entropy the concept for that task (X)) below given threshold 2m
3. Finally, we should remove redundant concepts.. The approach for this step can vary depending on the output model use. The conceptually most straightforward approach, based on Theorem consists of empirically estimating the risk R(fc) by averaging the mcan square error N 2p=1 MSEffc(; ((Dp)) on tross-validation samples {Dp)p=1
All in all, the concept generation procedure be summarized as follows. Starting from Co 0, while E(C,) > Em we increase our concept set by*
M(a(X)) > Qm R(fc.) -((fc_))))> Rm
C = - Uc,
where q ~ L(c Cr)
conditioned on
There settings where we cannot reach values of below our chosen threshold through any human concept set. For example, this can happen when there is 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 employ concepts additional features. Another is to fit the residuals of the CBM by 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 mutual information penalty to the models trained on the raw input.
"As per Theorem concept that docs not decrease (c.g., if it is spanned by the other concepts orthogonal the target function) will be detrimental to risk since it increases first term. In practice, when the effect on e small, keeping such concept should depend on the number of samples we have. regimes, we should be more aggressive in discarding it than when n grows, and the term e starts to dominate.
sample
'In our experiments, we keep a concept improves the estimated risk, iee. Ri, = 0. or R(fc,) R(fo ,) > and we set the entropy threshold proportionally the number of buckets na used estimate ensure all samples fall into the same bucket (i.e. Ωm L.)
7

---

Empirical Validation
To empirically validate our insights about concept-based representations, we designed series of experiments to validate our analysis'. We aim explore the key insights from our theoretical results, including the ability to effectively leverage scarce datasets and the impact of concept-based representations robustness 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 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-o--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 natural baseline. We primarily use linear output layer top of either the vanilla the concept embedding. Still, we also assess a variety output layers to understand which concept-basee based inductive bias is helpful.
For all experiments, we provide complete description, including the concept sets, in Appendix C.2.
The effects 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 CIFARIO, as we plot in figure
Effect of Sample and Concept Sizes on concept-Modk Performance
Accuracy (%)
75
70-
60
Concept Set Size
Concupt Size
concept
Concept Set Size 30
200 300
600 /00
Train Size
Figure 1: Scaling laws for the number of examples across different concept set sizes. As predicted by Theorem 1, smaller concept sizes 100 benefit the small sample regime, whereas larger concept sizes n > 200 are superior in the larger sample regime. We plot the mean and 1 a bars over ten seeds.
*Code can be found at http:///pw...t.o.ooo////////t//a github. com/ wandrrsshharrbbb/ttttttaa...
https://

---

As we concluded from our interpretation of Theorem 1, we expect the first term, [ (d+2) R(fo) to dominate the risk in the low data regime n + 0, since in that case, the (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 and 4.
& coefficient n (1 d-n
Then, as the number of samples increases substantially + sc, the risks start plateau, and the misspecification, embodied by becomes the dominant term. Thus, we expect larger concept sizes to outperform smaller ones due to a smaller E. This is particularly the case given our concept set generation procedure, where smaller concept sets are subsets of the larger ones. Again, this behavior clearly represented in figures and
Robustness of Concept-embeddings to distribution shifts We now evaluate the concept's bustness 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, train and test distributions 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 environment- related 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 (e( 21),.... ((s, zy )[[ has an average norm of 0.80, small compared to the interconcept similarity, with average of 1.65.
Our results in figure show that the concept representation yields substantial increase in perfor- mance', with bigger improvements for more pronounced distribution shifts. This effect is also seen for other output models, such 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.
Effect Distribution Shifts on Concept-Model Performance
Output Modal
Incresse in accuracy [Cuncept-Ver Vanilla) (%)
12
uneer
6.02
0.04
0.06
0.12
Percentage Minority (less percentage more shift))
Figure 2: Concept representations reduce the effect of distribution shift using the CLIP embed- ding directly, as seen by a more pronounced increase in accuracy on more imbalanced datasets. We plot the mean and 1 bars over 10 seeds.
Plus, if the concept set is appropriately chosen, the e itself should small. EEen in this sample regime, where the dominating term.

---

distribution generalization
Fiitering Version Classes
Vedia rept
dkg
tors
cade Roce
soaae Care
Joar Avd
Peopl
Adp
Test Class and Training Contounder
Figure 3: Concept representations consistently improve the out-of-distribution accuracy compared to directly using the CLIP embedding across different classes and distribution shifts. For three of the horse datasets, the CBM correctly identifies the presence of horse.
generalization of concept embeddings Finally, we assess the robustness of operating with the concept embedding terms of nut-of-distribution generalization. that end, we use domain generalization datasets from Section 4.1. in MetaShift.
The datasets
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 boxes, dogs with benches or bikes, dogs with boats or surfboards, and dogs with cabinets or beds (see figure 3 for details the other three tasks). Importantly, each of the four datasets for each class corresponds distribbitiiiio generalization challenge, comprising varied test bed for robustness (we refer to [26] for further details).
different degree of
Figure 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 50% increase in accuracy. We further verify the robustness of the OOD predictions of CBMs in CINIC-10 in Table 1.
7 Conclusion
In this work, we introduced novel theoretical framework for understanding the properties 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.
Acknowledgments and Disclosure of Funding
We want thank the reviewers. Nicolas Huynh, Paulius Rauba, Kasia Kobalezyk, Tennison Liu, and Andrew Rashbass, for their helpful feedback. Max Ruiz Luyten is supported by AstraZeneca. This work was supported by Microsoft's Accelerate Foundation Models Academic Research initiative.
10

---

References
[1] Amirhesam Abedsoltan, Mikhail Belkin, and Parthe Pandit. Toward large kernel models. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org. 2023.
[2] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt. Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Seemaddtt-Shapinee Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville. Arka Dhar, David Dohan. Steve Dowling. Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou. David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges. Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Eukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo. Lukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning. Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKin- ney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichrr Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen OeKeefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong. Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Ray- mond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang. Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng. Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang. Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong. Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojeiech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. Gpt-4 technical report, 2024.
[3] Sandhini Agarwal, Gretchen Krueger, Jack Clark, Alec Radford, Jong Wook Kim, and Miles Brundage. Evaluating clip: Towards characterization of broader capabilities and downstream implications, 2021.
11

---

[4] Nicolás Astorga, Tennison Liu, Nabeel Seedat, and Mihaela van der Schaar. Partially observable cost-aware active-learing with large language models. In The hhirty-Eightt Annual Conference on Neural Information Processing Systems, 2024.
[5] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. Society for Industrial and Applied Mathematics Journal on Mathematics of Data Science, 167::1667-1180, 2020.
[6] Usha Bhalla, Alex Oesterling, Suraj Srinivas, Flavio P. Calmon, and Himabindu Lakkaraju. Interpreting clip with sparse linear concept embeddings (splice), 2024.
[7] Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food- 101 - mining discriminative components with random forests. In European Conference Computer Vision, 2014.
[8] Sourav Chatterjee and Elizabeth Meckes. Multivariate normal approximation using exchange- able pairs. ALEA Lat. Am. J. Probab. Math. Stat., 4, 01 2007.
[9] M. Cimpoi, S. Maji. I. Kokkinos, S. Mohamed, and A. Vedaldi. Describing textures in the wild. In Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2014.
[10] Jonathan Crabbé and Mihaela van der Schaar. Concept activation regions: A generalized framework for concept-based explanations. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[11] Luke N. Darlow, Elliot Crowley, Antreas Antoniou, and Amos J. Storkey. Cinic-10 is not imagenet or cifar- 10, 2018.
[12] Jessica Echterhoff, An Yan, Kyungtae Han, Amr Abdelraouf, Rohit Gupta, and Julian McAuley. Driving through the concept gridlock: Unraveling explainability bottlenecks in automated driving. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), pages 7346-7355, January 2024.
[13] Michael Eysenck and Mare Brysbaert. Fundamentals of Cognition. Routledge, 01 2018.
[14] Steven Garber and Steven Klepper. Extending the classical normal errors-in-variables model. Econometrica, 48(6))1541-1555 1980.
[15] Joseph Goguen. What concept? In Frithjof Dau, Marie-Laure Mugnier, and Gerd Stumme, editors, Conceptual Structures: Common Semantics for Sharing Knowledge, pages 52-77, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
[16] James A. Hampton. Polymorphous concepts in semantic memory. Journal of Verbal Learning and Verbal Behavior, 18(4):441446) 1979.
[17] Samuel Holt, Max Ruiz Luyten, and Mihaela van der Schaar. L2MAC: Large language model automatic computer for extensive code generation. In The Twelfth International Conference on Learning Representations, 2024.
[18] Addison Howard, Eunbyung Park, and Wendy Kan. Imagenet object localization challenge.
https:/ htttp::/kaagle. com/ competitions competit..onssmmeeet-te maagenet-objecte wetect-oooalizaaiiioo challenge, 2018. Kaggle.
[19] Anna Jobin, Marcello lenca, and Effy Vayena. The global landscape of Al ethics guidelines. Nature Machine Intelligence, 1(9)389-399, September 2019.
[20] Dmitry Kazhdan, Botty Dimanov, Mateja Jamnik, Pietro Liò, and Adrian Weller. Now you me (eme): Concept-based model extraction, 2020.
[21] Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, and Rory sayres. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (TCAV). In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 26677 PMLR, 10-15 Jul 2018.
12

---

[22] Ugne Klimiene, Ricards Marcinkevics, Patricia Reis Wolfertstetter, Ece Ozkan, Alyssia Paschke, David Niederberger, Sven Wellmann, Christian Knorr, and Julia Vogt. Multiview concept bottleneck models applied to diagnosing pediatric appendicitis, 07 2022.
[23] Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5338-5348. PMLR, 13-18 Jul 2020.
[24] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, Michael S Bernstein, and Li Fei-Fei. Visual genome: Connecting language and vision using crowdsourced dense image annotations. International Journal of Computer Vision, 123(1):32-73, May 2017.
[25] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009.
[26] Weixin Liang and James Zou. Metashift: dataset of datasets for evaluating contextual distri- bution shifts and training conflicts. In International Conference on Learning Representations, 2022.
[27] Max Losch, Mario Fritz, and Bert Schiele. Interpretability beyond classification output: Semantic bottleneck networks, 2019.
[28] Andrei Margeloiu, Matthew Ashman, Umang Bhatt, Yanzhi Chen, Mateja Jamnik, and Adrian Weller. Do concept bottleneck models learn as intended?, 2021.
[29] Martina Narcisi, Fedele Greco, and Carlo Trivisano. On the effect of confounding in linear regression models: An approach based on the theory of quadratic forms. Environmental and Ecological Statistics, March 2024.
[30] Tuomas Oikarinen, Subhro Das, Lam M. Nguyen, and Tsui- Wei Weng. Label-free concept bottleneck models. In The Eleventh International Conference on Learning Representations, 2023.
[31] Federico Pittino, Vesna Dimitrievska, and Rudolf Heer. Hierarchical concept bottleneck models for vision and their application to explainable fine classification and tracking. Engineering Applications of Artificial Intelligence, 118: 105674, 2023.
[32] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8748-8763. PMIR, 18-24 Jul 2021.
[33] Adityanarayanan Radhakrishnan, Max Ruiz Luyten, Neha Prasad, and Caroline Uhler. Transfer Learning with Kernel Methods. Nature Communications, 14(1):5570, 2023.
[34] Paulius Rauba, Nabeel Seedat, Max Ruiz Luyten, and Mihaela van der Schaar. Context-aware testing: A new paradigm for tabular model testing. In The Thirly-eighth Annual Conference on Neural Information Processing Systems, 2024.
[35] Robyn Speer, Joshua Chin, and Catherine Havasi. Conceptnet 5.5: an open multilingual graph of general knowledge. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI'I 17, page 4444-4451. AAAI Press, 2017.
[36] Ao Sun, Yuanyuan Yuan, Pingehuan Ma, and Shuai Wang. Fliminating information leakage in hard concept bottleneck models with supervised, hierarchical concept learning. 2024.
[37] C. Wah, S. Branson, Welinder, Perona, and Belongie. The caltech-uesd birds-200-2011 dataset. Technical Report CNS-TR-2011 California Institute of Technology, 2011.
13

---

[38] Dan Wang, Xinrui Cui, and Z. Jane Wang. Chain: Concept-harmonized hierarchical inference interpretation of deep convolutional neural networks, 2020.
[39] An Yan, Wang, Yiwu Zhong, Zexue He, Petros Karypis, Zihan Wang, Chengyu Dong, Amilcare Gentili, Chun-Nan Hsu, Jingbo Shang, and Julian McAuley. Robust and interpretable medical image classifiers via concept bottleneck models, 2023.
[40] Yue Yang, Artemis Panagopoulou, Shenghao Zhou, Daniel Jin, Chris Callison-Burces and Mark Yatskar. Language in bottle: Language model guided concept bottlenecks for interpretable image classification, 2023.
[41] Mert Yuksekgonul, Maggie Wang, and James Zou, Post-hoc concept bottleneck models. In The Eleventh International Conference on Learning Representations, 2023.
14

---

A Proofs for the theoretical results
This section is divided into the lemmas we require for our proof. We start with the tools that will enable us properly handle the spurious variables' effect in our data.
A.1 Effects of confounding spurious feature
We start by recovering a very recent lemma on the effect of confounding on the risk an ordinary least squares estimator from [29]. We present it here for completeness and adapt notation.
A.1.1 Data Generating Process with confounder
Consider standard confounding setting in which the directed acyclic graph involves the covariates X, the targets Y, and the confounder covariates In this setting, Z is a parent of both X and Y, and Y is child of both X and Z. In addition, assume Gaussian distribution and a linear setting, that is:
Y Z No (8yz(z)) X + 2, Mg,,,)
We use Σy for any random variable to denote its covariance matrix. The subscripts of the regression coefficients, 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.
A.1.2 Effect of the confounder on the risk
Of course, the confounder is not observed, so we aim to fit the following model, where the underscore con stands for confounded.
Y Woon X +n 1~ (,,,,,,
with the least- squares estimator:
Weon X
However, in practice, due to the confounder,
Y ~ (A X, B (x) Dzje + Eylz,))
where A stand for the regression matrices:
Ay. En B Byx + Byzz())
Lemma In the above setting, the bias and variance of the least squares estimator io can be expressed as:
M X
Biasy [Weon]] X
B By-((a)
X
X ME MX
Vary [eon X
(X MX)²
where M = I, I is the centering matrix.
Proof. See Proposition 2 in [29].
15

---

Lemma implies that when both zyr # 0 and A.. * 0. the estimator 3g is biased. Note that the expectation of the bias is proportional to both the effects of Z 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ı, 22. . 2x) X,, given concept e X", the bias in the ordinary least squares estimator satisfies
|Bias(fc\))ls I1((,,21), 21), ((c, zx))1l
In particular, the classifier f(c) remains unbiased if and only if span(21, 22, 22,..., 2k)
Proof. We can rewrite the lemma by denoting i = Toll as follows:
MA
Biasy en X = ||A 112 (a)
12:
X
MX
But ||Az,alla corresponds, in fact, the regression coefficient of x(2). our case, Ag
((c, 2.) )=)) which completes the proof.
A.2 Effeet of Grrors-in-variabe
Note that our concept identifier will not be perfect in practice, leading us to treat our foundational embedding noisy covariates. This aligns with the mnors-in-variable 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 z; x + represents the observed covariates with noise ue and y = x"a" + the true model, the least-squares estimator & is biased. Specifically, for single noisy covariate ok JK, the attenuation effect the estimated coefficient ogK is given by okK ok aj. This
indicates that the estimated coefficient o is shrunk towards zero, with the degree of attenuation increasing with the noise variance o.
Furthermore, the bias in the estimated coefficient à; of a correctly measured regressor x; is propor- tional the bias in the coefficient of the noisy regressor. This is expressed as á a ( -a) This interdependence means that noise in any covariate can propagate, affecting all other coefficients (cf. [14]). Thus, significant noise in any covariate leads to complex distortion of the entire regression model.
A.3
Risk of the conceptual representation
The proof of Theorem follows the same backbone as [33] and also relies on the following lemma, the proof of which we reproduce here for completeness.
Lemma Let D,A E {0, 1]ddd be two diagonal matrices of rank p and q, respectively. Let V Rdxd be an orthogonal matrix and W E Raxd Haar distributed random matrix. If W WDWT, Q VAVT, then
Ew [PQP] d(d 1)(d 2) (g(d Taxd (d(p + +1 Q]
Proof. Since V is an arbitrary orthogonal matrix and W is Haar distributed, without loss of generality, can assume A diag(1g, 0a-g). and D diag(1p. (1p. 0s-p). By definition of the Haar distribution, we can denote U VTW, also Haar distributed. Therefore.
Ew [PQP] Ew Haer
[WDW] W WDWT
= VEU-Haaa Haar
(UDUT DUDUT vT
= VVE Haar
A VT.
16

---

where we have defined A = AUDUT. yields, denoting u, (U....... Upp): (uI, ū1)
Looking closely at the entries of A a quick computation
(ūn. ūa)
(āg. ū1)
(āg. id)
A
Thus, Ei= (ūs, (ū,, ux), and so, Ev- (A= A] can be readily computed if we have the fourth moments of the entries in U. Indeed,
Eu [(A A)
Σ
By Juyy urs Mas]
Lemma 9 from [8] provides such 4th moments: if + then Ey Bb((A=A)ii 0, and if then
Ey Majl) d(d l) + [d5j= dōia (d 2) 1].
Consequently, the expectation yields a diagonal matrix with two blocks of eigenvalues:
Ey [AA A) d(d - () + 2) p)) + [d(p 1) A].
p
Since Ew Sw(PPP] = VEu (A) VT, VVT Laxd. and VAVT Q, the result follows.
Next, we follow the steps of [33] to arrive to Theorem
Theorem Let & TR.d T2 , Rd And assuming that P an isotoopic distribution, where X = {ai) mii IP is full rank, and our labels are linear on the covariates, i.e., W.T; then the risk of the concept-based model R(fc) is given by
R(fo) = (1-
d CC (1--n=---111)1
d R(f)) + (1+ (d+ 2)dd)(d-1)
(
(d 2) (d+2)
e,
where E 11 and C+ standy the orthogonal projection operator onto the orthogonal complement of the concept vector's span.
Proof. Given matrix M E Rkxy full rank p, we denote Mll M M the projection onto its column space, and M = Laxd X the projection into the corresponding orthogonal space.
Then, denoting de the ordinary mean square estimator of the weights we have:
wcC = YCCx)C w.xxxttc- wlll!
Therefore,
apC W. wi (xlIc!l Taxd)
wi [xxll laxd) Olll + Oll laxd]
w. [x-c] c-1
Using the cyclic property of the trace, the risk is given by
R( = Ex,x
[| ws
Ex w. (x+cll + + xxd (x+cll+ + wa))
= Tr
Ex w. (x+cll + (x+c)l+04) (x+cll + w.! Tr
17

---

Since projections are idempotent and C' C = 0,
(x-c" + + (x+cl++x+))
r = =x- + - +
xx
and as a consequence, that
R(wcC) = Tr Ex w.
xx + +c w!) Ex x 04 w.)
= Tr Ww
X C'll are both projections and since follows an isotropic distribution according to our assump- tions, its right singular vectors, which coincide with the eigenvectors of X are Haar distributed. Therefore, we can apply the lemma with p n. q |C] we obtain that
C| Ex x- [x+ - (1 (d - 1) 2) laxd + (1- (d -
dn
cil
1)(d (1-
2)
Recalling Cll = Laxd O+ and rearranging the terms we obtain
Ex x + + = =(1- 7) (1 n(d- 2) -1) Iaxd
+ ā n ((d-n) (d+ 2) o+.
Lastly, we use R(we) (1 (1- -)) (see [5]) and our definition of = Tr (waC+t c'w])) conclude that
n-n n R(acC)- = (d (d+ 2)dd R(ar) + + ( + (d + 2) - 1) e,
d- |Cl
18

---

B Extended Discussions
In this section, we expand on specific details of the paper that, albeit non-essential for the main text, might be of interest specific readers.
B.1 Further details the Concept Set definition
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) concept sets are unordered, then He must be complete set of maps under permutation symmetry, that is, for any map g E 'He and any permutation of C, g oo E Hcc and the learning method also invariant under feature permutations, which holds for the output methods considered in the paper; alternatively, (2) C' is 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, U should be substituted by X.
We note that the natural models used as probes-suee as linear regression, kernel regression, fully connected neural networks, decision trees, and k-nearest neighbors, among others constitute parame- terized 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.
B.2 Non-Concept characteristic functions
To elucidate the relevance of the properties in Definition 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 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 wide range of occurrences, individuals do not cultivate concepts outside their domain of interest. For instance, consider himograpphy-elatee 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 I, people not interested 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 No approaches infinity without significantly enhancing model-aware inductive bias. Consequently, N1 becomes less than No. which does not satisfy the definition.
In more abstract terms, a characteristic function that does not contribute additional valuable information beyond the existing concept set C for the task TT exhibits low expressiveness, indicated by large No, without corresponding increase in Ni. This scenario arises when the target variables are conditionally independent
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, characteristic function 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 e 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, No remains large, indicating low expressiveness.
B.3 Concepts as a stable communication interface
We expand on the flexibility of Concept-Based Models (CBMs), highlighting properties that can facilitate future advancements.
19

---

Consider the objective of learning a target function f :X - y. In a CBM framework, this involves concept representation e" X Re followed by a mapping fC Re + y from concepts to targets. By maintaining fixed concept set C and its associated representation Re, we allow the replacement of the concept mapping estimator e with an alternative C without altering the probe fc- This substitution is viable long as the concept representation Re remains consistent in dimensionality and semantic meaning. For example, upgrading from a CLIP-based concept representation
advanced CLIP2 preserves the probe's s applicability.
However, probes are not interchangeable between fundamentally different concept representations (e.g., raw CLIP vs. CLIP2) due to potential discrepancies in metrics dimensionality. This emphasizes the role of Re as stable interface with fixed characteristics.
Furthermore, CBMs facilitate the harmonization of datasets with varying features or modalities . Xx (such as images from different sensors). By projecting each input X; into the common concept space Re through mappings ? X; + Re, 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.
B.4 Use of Large Language Models for Concept Generation
The primary objective of method and experiments is illustrate and validate our theoretical insights, which remain agnostic to the concept sampling method. Although large language models (LLMs) are utilized for concept generation 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 combination thereof.
B.4.1 Alternative Concept Sampling
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 be valuable samplers/generators. especially as part of 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-Generate Concepts: Concepts manually curated, tailored to specific tasks.
Concept Graphs: Using structured knowledge bases such ConceptNet [35] derive
relevant concepts.
Correlated Text Corpora: Leveraging patterns and correlations within large text datasets like Wikipedia to identify meaningful concepts.
Hybrid Approaches: Enhancing LLM -LM--generteed 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.
B.4.2 Quality Control through Rejection Sampling
We also note that our method can be regarded as a rejection-sanpling loop that ensures the quality of the concepts generated and mitigates the potential limitations associated with the reliance on L.LMs 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.
20

---

Experiment details
C.1
Assets used
Datasets For CIFARIO we use CIFAR-10 python version [25], and for MetaShift (MIT License)
follow the scripts provided by the MetaShift Repo [26].
Models For generating concept sets, we use GPT 1uurbo-2024-04099 [2] through the ChatGPT web app. For jointly embedding images and text, we use CLIP ViT-B/32 [32].
C.2
Compute Resources Used for the Experiments
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 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.
C.3
Concept set generation before filtering
For the generation of concept sets, instead of keeping or discarding a concept before generating new one, we first generated pool of concepts, which then sampled sequentially and filtered the subset of interest. To generate the initial pool, we started by providing the following prompt to GPT nurbo-2024-04-09.
I am building a classifier between (Class_Names) on the (Dataset_Name) dataset. I want to a concept-bottleneet model predict these classes.
To that end, want you to propose set (N} concepts for each class that can help me differentiate between concept-bottleneck model.
for the
Propose only concepts that can 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 provided below in the detailed description.
C.4 Detailed description: Effects of concept and sample sizes
Dataset information
The dataset used in this experiment CIFAR-10, 10, which consists of 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.
21

---

Configuration
The embedding model used CLIP ViT-B/32. The preprocessing pipeline utilizes torchvi- sion.transform in several steps. It begins by resizing the image to 224x224 pixels with bicubic interpolation, ensuring smooth resizing. then performs a center crop retain the central 224x224 pixels. focusing on the most significant part of the mage. The image is then converted to tensor, scaling the pixel values from [0. 255] [0.0, 1.0]. Finally, the tensor is normalized using specific mean and standard deviation values for each RGB channel, standardizing the input data.
The output models evaluated are based on linear regression the one-hot encoded labels, with coefficients determined using an exact solver.
The random seeds used for this evaluation are [42, 43, 44, 45, 46, 47, 48, 50, 51].
Unfiltered Concept Set
The initial pool of concepts generated by GPT-4 from which we sample described in Section 5 is:
Airplane: Fixed wings, Jet engines, Propellers, Cockpit windows, Landing gear, Tail fin, Airplane fuselage, Winglets, Long. narrow wings, Round windows, Brightly colored livery, Nose cone, Smooth metallic body, Horizontal stabilizers, Underwing pods, Delta wings, Commercial airline logos, Contrails, Navigation lights, Turbofan engines.
Automobile:
Four wheels, Headlights, Tail lights, Rearview mirrors, Grille, Doors, Win- dows, Bumpers, Roof rack, Alloy wheels, License plate, Windshield wipers, Exhaust pipe, Hood, Trunk, Side mirrors, Car brand logos, Spoiler, Roof antenna, Fog lights.
Bird: Feathers, Beak, Wings, Tail feathers, Claws, Perching behavior, Colorful plumage, Small size, Sharp eyesight, Nesting. Beady eyes, Flight patterns, Hollow bones, Singing or chirping, Flapping wings, Broad wingspan, Crest or crown, Scaly legs, Bird nest, Smooth beak.
Cat: Sharp, pointy ears, Rounded eyes, Fine, soft fur, Short, pointed snout, Fine whiskers, Slender and agile body, Compact paws, Grooming behavior, Arching back stretch, Re- tractable claws, Slit pupils, Purring. Curved claws, Lithe movement, Long tail, Flexible spine, Night vision, Whisker pads, Silent movement, Playful behavior.
Deer: Antlers, Slender legs, Hooves, Brown fur, White tail, Large ears, Doe eyes, Grazing behavior, Spotted coat, Small tail, Rounded snout, White underbelly, Graceful movement, Herd behavior, Muzzle, Alert posture, Small antlered males, Thin, long legs, Winter coat, Sleek body.
Dog: Floppy ears, Bushy tail, Curly tail, Almond-shaped eyes, Smooth short fur, Curly fur, Wiry fur, Long, narrow snout, Thick whiskers, Large body, Large paws, Wagging tail, Barking, Droopy ears, Loyal posture, Collar, Panting, Playful behavior, Sniffing, Guarding behavior.
Frog: Smooth, moist skin, Webbed feet, Bulging eyes, Long hind legs, Jumping, Sitting posture, Wide mouth, Green color, Camouflaged skin, Sticky tongue, Croaking, Slender fingers, Tadpolc stage, Water habitat, Streamlined body, Short front legs. Bug catching, Wide head, Swimming ability, Amphibious nature.
Mane, Tail, Hooves, Long legs, Galloping, Large eyes, Long snout, Strong build, Grazing behavior, Smooth coat, Upright ears, Bridle, Saddle, Neighing, Herd behavior, Museular body, White blaze, Erect posture, Speed, Stirrup.
Horse:
Hull, Deck, Sails, Masts, Bow, Stern, Portholes, Lifeboats, Anchor, Smokestacks, Rigging, Cabins, Cargo containers, Radar, Funnels, Bridge, Naval flag, Propeller, Sailors, Lifebuoys.
Ship:
Large wheels, Cargo bed, Cab, Grille, Headlights, Side mirrors, Exhaust pipe, Large size, Rearview mirrors, Mud flaps, Trailer hitch, Step-up rails, Heavy-duty tires, Flatbed, Bull bars, Utility lights, Roof lights, Storage compartments, Ladder racks, Commercial decals.
Truck:
22

---

Filtered Concept Sets
Three concept set sizes are evaluated: 20 concepts, 30 concepts, and 50 concepts.
The filtering method described in Section 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 lower threshold of 0.02 ensures that not all activations are essentially equivalent.
C.5 Detailed description: Robustness to distribution shifts
Dataset Information
The dataset used 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].
Configuration
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 linear regressor, a decision tree, and nearest neighbors, all with the standard hyperparameters from sklearn and trained on hot encoded label.
Unfiltered Concept Set
The initial set of concepts generated by GPT-4 from which we sample is: Sharp, pointy cars; 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.
Filtered Concept Sets
The filtering method described Section used, which iteratively draws a concept and keeps it decreases the empirical risk in five seeds (threshold of 0). We used 70/30 split for empirical risk estimation. The entropy is estimated through bins, and lower threshold of 0.1 ensures that not all activations fall into the same bucket.
C.6 Detailed description: Out-of-distribution generalization
Dataset information
The datasets used in this experiment are the MetaShift domain generalization datasets; see [26]. That is,
Cat vs. Dog The "Cat vs. Dog" dataset has the following four different training configurations, all evaluated on the same test set that contains images of dogs shelf.
Configuration 1: Cat on sofa or bed, and Dog in a cabinet or bed.
Configuration 2: Cat on sofa or bed, and Dog in a bag or box.
Configuration 3: Cat on a sofa or bed, and Dog on bench or with a bike.
Configuration Cat on sofa or bed, and Dog on boat or with a surfboard.
Bus vs. Truck The "Bus vs. Truck" dataset has the following four different training configurations, all evaluated on the same test set containing images of trucks with airplanes.
Configuration 1: Bus with clock traffic light, and Truck with fence.
Configuration 2: Bus with clock traffic light, and Truck with bike mirror.
23

---

Configuration 3: Bus with clock or traffic light, and Truck with flag or tower.
Configuration 4: Bus with clock or traffic light, and Truck with traffic light or dog.
Elephant vs. Horse The "Elephant Horse" dataset has the following four different training configurations, all evaluated on the same test set containing images of horses a barn.
Configuration 1: Elephant with fence rock, and Horse in dirt or with trees.
Configuration 2: Elephant with fence rock, and Horse with fence helmet.
Configuration 3: Elephant with fence or rock, and Horse with car or wagon.
Configuration 4: Elephant with fence or rock, and Horse with statue or cart.
Configuration
The embedding model used is CLIP ViT-B/32. The preprocessing pipeline is the same in the two previously descrihed experiments.
The output model consists of linear regression the one-hot encoded labels, with coefficients determined using an exact solver.
Unfiltered Concept Set
The initial pool of concepts generated by GPT-4 from which sample described in Section 5 is:
Cat vs. Dog: sharp, pointy ears; floppy ears; rounded ears; pointy cars; thin tail with 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.
Long and tall; Multiple axles; Trailer; Large, continuous rows of windows; Passenger seating; Cargo space; Grille and large headlights; Cargo doors; Passenger doors and emergency exits; Commercial text and logos; Public transit text and logos; Uniform vehicle color scheme; Varied vehicle color scheme; Air conditioning units; Visible cargo.
Bus vs. Truck:
Elephant vs. Horse: large overall size; thick skin texture: large and fan-shaped ears; tusks; trunk; wispy tail with sparse hair; bulky and robust body build; mane; small eyes relative to body size, placed more to the side of the head; large, round feet with visible toenails; short and thick neck; thick legs; uniform color without markings.
Filtered Concept Sets
We used the same approach as in the distribution shift experiments described above.
24

---

D Additional Experiments
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:
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.
3. Comparison with Label-Free Concept Bottleneck Models [30] on CIFAR-10, bench- marking our method against a relevant baseline from the literature.
D.1 Data-Efficiency Experiments
(a) Performance comparison of linear probe the CLIP representation vs. our CBM across dif- ferent training sizes on the CUB-200 200-2011 dataset.
(b) Performance comparison of linear probe the CLIP representation vs. our CBM across dif- ferent training sizes on the Food-101 dataset.
Sample offictency Food101 deteset
Jccenoy N0
Crobediingg Moodl
Tha 3104
(c) Performance comparison of a linear probe on the CLIP representation vs. our CBM across dif- ferent training sizes the DTD dataset.
Figure 4: Comparison of a linear probe on the CLIP [32] representation against our CBM across different training sizes for three datasets: LUB-200-2011 [37] in Figure 4a, Food- 101d-10110 [7] in Figure 4c, and DTD [9] in Figure 4b. This figure illustrates the performance 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 I).
D.1.1 Experimental Setup
To evaluate the data efficiency of our CBM approach, 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.
25

---

Describable Textures Dataset (DTD) [9]: A texture database with 47 classes and 5,640 images, annotated with attributes describing the textures.
For each dataset, 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 examples (with balanced classes) and trained the models five times with different random seeds to obtain averaged results.
D.1.2 Results and Discussion
The results are summarized in Figure 4. We observe the following trends:
Small Sample Regime: In the low-data regime (< 10 samples per class), 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:
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 low-data settings highlights its potential for applications where labeled data are very scarce (e.g., rare diseases).
D.2
Out-of-Distribation Generalization on CINIC-10
D.2.1
Experimental Setup
To evaluate the robustness of CBMs to distribution shifts, we conducted an out-of-distributio (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 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- classes introduce a distribution shift between the training and test data.
We compared the performance of the baseline linear classifier trained CLIP image embeddings against our CBM, using predicted concepts for classification.
D.2.2 Results and Discussion
The results are presented in Table 1. Our CBM demonstrates superior OOD generalization perfor- mance compared 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, suggested by Theorem 2, contributes to its robustness.
26

---

Model
Accuracy (%)
Vanilla
70.4 = 1.2
CBM
78.8 + 0.7
Table 1: out-of-distribution generalization comparison on CINIC-10 [11] between linear probe the CLIP [32] embedding and our CBM method.
D.3
Comparison with Label-Free Concept Bottleneck Models
D.3.1
Experimental Setup
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 q ~ L(e Cr) using fixed language model L and context Cr (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.
D.3.2 Results and Discussion
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.
Label-Free CBM CIFAR-10
85-
Accuracy
73
Embeddlng Modeel
Label Free
80
500 3000
1000
2000
2500
Train Size
Figure 5: Performance comparison between our concept set curation method and the Label-Free Concept Bottleneck Model (LF-CBM) [30] on CIFAR-10 10 [25]. The results demonstrate a consistent performance gap, with our method outperforming IF-CBM by more than 7.3% across all training set sizes and reaching up to 17.7%. This comparison underscores the impact of effective concept set selection in concept bottleneck models, validating the importance of our theoretical insights.
27

---

comprehensive understanding of E Extended Limitations
E.1 Notable assumptions
The CBM Assumption We make the implicit assumption that human concepts have predictive power for ML models, discussed in Section 3.
Concepts as linear space Although the assumption that concepts correspond to directions in 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 identify and utilize hierarchical concepts would enhance the robustness and interpretability of CBMs.
Input distribution for Theorem 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.
E.2 Other limitations
Interaction of effects The proposed theory addresses the analysis of in-domain generalization, the impact of confounding. and error-i--variables separately. Still, one could explore considering all of them simultaneously and their interactions. Integrating these aspects into unified theoretical framework remains open challenge and could provide CBMs.
Scalability to massive datasets The method for estimating the impact on the risk of adding new concept can become computationally expensive for large-scale datasets. For such cases, numerical methods for solving linear equations, such 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 external knowledge sources, as discussed in Appendix G. More research is needed to mitigate potential biases and guarantee equitable outcomes.
F Extended Future Work
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 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.
Meta-L Learning and Transfer 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 interpretabilliyy generalizability; and robustness of the model to data shifts. Leveraging large-language models (LLMs) to identify
28

---

relevant concepts for a target task from pool of knowledge datasets offers 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 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-bass based models. This includes addressing potential biases, ensuring fairness, and evaluating the impact of these models in various real-world applications.
G Broader Impacts
Although our main contributions can be considered foundational research and raise no immediate faireess 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 discriminatory representations that will affect the resulting concept representations.
Several strategies exist mitigate these risks. First, should ensure that training datasets are diverse and representative, thoroughly evaluated for bias, and employ techniques to detect and correct biases. In particular, can focus models that stress transparency by providing comprehensive documentation of datasets and detailing bias detection and correction efforts.
models whose
However, provided that we used 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.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the claims, which we tried to sum- marize neatly in the "Contributions" box. The contributions are well-delimited, emphasizing the theoretical framework, theoretical results and insights, and method for concept set generation. The corresponding proof and empirical validation of the theoretical results on CIFAR-10 and various MetaShift datasets experiments supports the claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In addition the assumptions discussed in the main text throughout sections 3, 4, 5, we discuss the main assumptions and further limitations in section E.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
30

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The specific claims are stated in the main text statement of the results, and both the statements and full proofs provided in the Appendix A.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the required details for reproducibility can be found either in the main text in appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
31

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
Code included as supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips..
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cc/public/guu celicc/ggiess/. /tteggguiide//oecmmmiiiiii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The main setting is introduced for each experiment in the paper's core, and the full details are described in appendix or in the code in the supplemental material.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Figures and 2 include 1 bars over 10 seeds, and we detail this in the corresponding captions. For figure 3, we use the full training data, and the regressor is computed exactly, so we plot the obtained accuracies without uncertainty estimations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

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 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 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
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 the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https : /ttpr//eerppp.eeeeee ec/ cc/public hewoolii//thhssuuuiiieooee ines?
Answer: [Yes]
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 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 NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
33

---

Justification: See appendix G for discussion of Broader Impacts. In this section, we discuss potential fairness concerns due biases 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 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 (c.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 tied to particular applications, let alone deployments. However, if there is 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 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 unintentional) misuse of the technology.
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 system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not involve releasing data models that pose high risk for misuse. Therefore, no specific safeguards are necessary for the responsible release of data 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification:
We provide the suggested details for the assets we use in Appendix C.I.
34

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets. Instead, builds on existing datasets (CIFAR-10 and MetaShift) and focuses on theoretical and empirical improvements in concept bottleneck models (CBMs) without introducing new datasets or models.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/coodemmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
35

---

Answer:
[NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
36


Reviews:
[{"review_id": "soOho4KdEx", "reviewer": "Reviewer_7Ykd", "summary": "This paper addresses an important research question in CBM — understanding the properties of concept sets and their connection to the performance of CBMs.\nA theoretical framework for concept sets is proposed, focusing on two desiderata for concepts: expressiveness and model-aware inductive bias. \nTheir theoretical analysis covers under what conditions the concept representation-based predictions outperform raw feature representation-based predictions.\nEmpirical evaluation with two datasets confirms their theoretical insights that well-chosen concept sets improve sample efficiency and robustness under distribution shifts.", "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.\n* 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. \n* how do you determine the thresholds in concept generation? (i.e., $\\Omega_m$, $R_m$).", "limitations": "Limitations are described in Appendix C.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Studying the properties of concept sets and how to effectively find a good concept set satisfying the properties, ultimately improving the utility of CBMs, is a very interesting and important research question.\nThe two proposed properties of concept expressiveness and model-aware inductive-bias are intuitive and well-defined. \nEspecially, their observation on connecting them to improved data efficiency is interesting.\nThe proposed theoretical framework naturally reveals the regimes on which it is undesirable to have a concept bottleneck and leads to a principled solution based on the theoretical insights.", "weaknesses": "Notations are very loosely defined:\n* Notations in introduction are used without being defined; for instance, $f, g, \\theta, \\mathcal{H}$. \n* 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. \n* what is $d$ in Theorem 1?\n* 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. \n\nLimited experiments:\n* Evaluated only with two datasets.\n* No performance comparison with other CBM methods, given the same number of concepts and training set size.\n* No demonstration and anlysis on the actual results of generated concept sets\n\nPlease increase the fonts in the figures for visibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. We are glad you find the research question important and the insights interesting. \n## Notation\nWe agree with all the suggestions and have incorporated them. Specifically: \n* Changes in the introduction:\n\t* We remove $\\\\theta$. \n\t* L22: we introduce $\\\\hat{g}$ with \"[...] a CBM first identifies key concepts such as the presence of a semaphore or a pedestrian crossing the road ($C: \\\\mathcal{X}\\\\rightarrow\\\\mathcal{C}$), and learns $\\\\hat{g}:\\\\mathcal{C}\\\\rightarrow\\\\ \\\\mathcal{Y}$ to act based on them $(\\\\hat{g}\\\\circ C)(x)$\". \n\t* L33: we define $\\\\mathcal{H},\\\\mathcal{H_C}$: \"[...] the degree of misspecification $\\\\varepsilon$ as key drivers of the CBM performance, where $\\\\varepsilon=|| \\\\text{arg min}\\_{f\\\\in\\\\mathcal{H}} \\\\ell(f) - \\\\text{arg min}\\_{g\\\\in\\\\mathcal{H_C}} \\\\ell(g\\\\circ C)||$, with $\\\\mathcal{H}\\\\subseteq \\\\{f:\\\\mathcal{X}\\\\rightarrow\\\\mathcal{C}\\\\}, \\\\mathcal{H_C}\\\\subseteq \\\\{g:\\\\mathcal{C}\\\\rightarrow\\\\mathcal{Y}\\\\}$ the hypotheses spaces.\"\n\t* L48: the additions \"concept-based models ($\\\\mathcal{R}(\\\\hat{g}\\\\circ C)$, $\\\\hat{g}\\\\in \\\\text{arg min}\\_{g\\\\in\\\\mathcal{H_C}} \\\\ell(g\\\\circ C)$)\" and \"baseline counterpart ($\\\\mathcal{R}(\\\\hat{f}), \\\\hat{f}\\\\in\\\\text{arg min}\\_{f\\\\in\\\\mathcal{H}} \\\\ell(f)$)\" further clarify $\\\\hat{g}$ and $\\\\hat{f}$.\n* L104: we thank you for pointing out this detail since there was a technical condition missing: either (1) if concept sets are unordered, then $\\\\mathcal{H_C}$ must be a complete set of maps under permutation symmetry, and the learning method invariant under feature permutations, which holds for the output methods considered in the paper; or (2) $\\\\mathcal{C}$ is a concept sequence, not a set. In the first case, the composition is well-defined since it is equivalent across concept reorderings; in the second, $\\\\cup$ should be substituted by $\\\\times$. We make this explicit in L101 by adding, \"Consider the output hypothesis spaces $\\\\mathcal{H_C}\\\\subseteq\\\\{g:\\\\mathcal{C}\\\\rightarrow \\\\mathcal{Y}\\\\}$ complete under permutation symmetry and the learning algorithm invariant under feature permutations. We refer to Appendix B for a technical discussion of this assumption.\". We correspondingly added Appendix B with an extension of the above discussion, including the full alternative definition and what methods satisfy assumption (1).\n* We update Thm 1's statement to \"Under the above setting and assuming that $\\\\mathbb{P}$ is an isotropic distribution on the $d-$dimensional input\" to introduce $d$ unambiguously.\n* To avoid confusion, we will denote the CLIP embedding space as $\\\\bar{\\\\mathcal{X}}$, and we modify L149 to \"[...] input space $\\\\bar{\\\\mathcal{X}}$ as the joint embedding space of inputs and concepts from a foundational model [...]\".\n* We increased the figures' fonts. This is shown in the new figures; previous ones have been modified correspondingly.\n## New experiments\nThe experiments in our paper aim to illustrate the theoretical insights, and we believe the current experiments serve that purpose well. However, in agreement with your comment, we have run experiments on additional datasets and a new baseline to further validate our insights. We refer to the \"Global Response\" for details. We also included throughout appendices C.4-6 filtered concept sets from our experiments.\n## Concepts as a stable interface\n> This flexibility means 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. Additionally, concepts can act as common representations across different feature sets, potentially harmonizing datasets and modalities.\n\nWe welcome the opportunity to expand on these observations, which cover exciting properties that could lead to impactful future works. \n\nSuppose we aim to learn $f^*:\\\\mathcal{X}\\\\rightarrow \\\\mathcal{Y}$, and let us consider a CBM counterpart, with the concept representation $\\\\mathfrak{C}^*:\\\\mathcal{X}\\\\rightarrow \\\\mathcal{R}\\_{\\\\mathcal{C}}$, followed by a mapping $f\\_\\\\mathcal{C}^*:\\\\mathcal{R}\\_{\\\\mathcal{C}}\\\\rightarrow \\\\mathcal{Y}$ from concepts to targets. By keeping the concept set $\\\\mathcal{C}$ fixed (and thus the representation $\\\\mathcal{R}\\_{\\\\mathcal{C}}$), we can replace an estimator of the concept mapping $\\\\hat{\\\\mathfrak{C}}$ by another $\\\\tilde{\\\\mathfrak{C}}$ while the probe $\\\\hat{f}\\_\\\\mathcal{C}$ remains effective, only affected by a distribution shift. E.g., if we train the probe on a CLIP-based concept representation and migrate to a new CLIP2, our probe will remain applicable to the updated and more precise embedding. However, a probe cannot be swapped from the CLIP raw representations to the ones from CLIP2 since they will have different metrics or even dimensionality. That is, the concept representation $\\\\mathcal{R}\\_{\\\\mathcal{C}}$ is a stable interface with fixed dimensionality and meaning.\n\nFurthermore, suppose we have datasets with different features or modalities $\\\\mathcal{X}_1, \\\\dots,\\\\mathcal{X}_k$ (e.g., images from different sensors or angles). In that case, we can use a common concept set $\\\\mathcal{R}\\_{\\\\mathcal{C}}$ which has fixed semantic meaning, and project all inputs there $\\\\mathfrak{C}^*_i:\\\\mathcal{X}_i\\\\rightarrow \\\\mathcal{R}\\_{\\\\mathcal{C}}$, thereby harmonizing them.\n\nSome readers might be interested in delving deeper into these ideas, so we include a version of the above text in the appendix and refer to it in L139.\n## Thresholds\nWe keep a concept if it improves the estimated risk, i.e., $R_m=0$, or $\\\\hat{\\\\mathcal{R}}(\\\\hat{f}\\_{C_i}) - \\\\hat{\\\\mathcal{R}}(\\\\hat{f}\\_{C_{i-1}})>0$, and we set the entropy threshold proportionally to the number of buckets $n_b$ used to estimate $\\\\Omega$ to ensure not all samples fall into the same bucket (i.e. $\\\\Omega_m=\\\\frac{1}{n_b}$). We will specify this as a footnote in L253.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q5U0NcvSn8", "reviewer": "Reviewer_sfwM", "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.", "questions": "None.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Overall, the theoretical findings are insightful. The authors demonstrate the situations in which the performance of CBMs can be enhanced by well-choosing the concept sets.\n- The framework of the theories is clear. The assumptions are appropriate and not overly restrictive. The definitions are comprehensive and primarily clarify the expressiveness and model-aware inductive-bias, which are two key properties affecting the performance.\n- The empirical results show that the CBMs surpass the foundational embedding models. These results also provide a unique perspective compared to existing works.", "weaknesses": "- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful evaluation and appreciate your recognition of our theory's insightfulness and clarity, as well as our results' unique perspective.\n### The use of LLMs for concept generation\nThe core objective of our method and experiments is to illustrate and validate our theoretical insights, which are agnostic to how concepts are sampled. In fact, we note that the first mention of an LLM as a generator happens in L229 in section 5.2. Consequently, using an LLM for sampling concepts in our experiments does not affect the practicality or generality of our theoretical insights. We employ LLMs to reduce the required human expertise and flexibly supply task-specific concepts, decreasing the barrier to adopting CBMs for new tasks. \n\nAs mentioned, our theory encompasses concept sets that are not dependent on LLMs. Options include human-generated concepts, concept graphs like ConceptNet, or leveraging correlations within text corpora like Wikipedia. Even hybrid approaches could be considered, with the goal of enhancing LLM generation by conditioning their context on external knowledge sources like ConceptNet or Wikipedia, as mentioned in L229-232. \n\nOrthogonally, we also note that the method in section 5.2 can be regarded as a 'rejection-sampling loop' that partially palliates the practical limitations of relying on an LLM. This loop controls the quality of LLM generation through steps 2 and 3 by rejecting concepts that do not align with our theoretical criteria, thereby encouraging only high-quality concepts to be incorporated into the concept set. \n\nTo convey more effectively that this choice does not limit the practicality and generality of our theory and insights, we will include a version of the first two paragraphs above following L232 and a version of the third preceding L254.\n### New experiments\nThe purpose of the experiments in our paper is to illustrate the theoretical insights, and we believe the current experiments serve that purpose well. However, to further validate our insights and in agreement with your comment, we have run experiments on additional datasets and a new baseline. We refer to the 'Global Response' for the new results. \n\n---\nOnce again, we express our gratitude for your comments. We hope that the new experiments and the discussion we incorporate about how our theory is agnostic of the generation method have addressed all your comments, and we look forward to your continued engagement with our research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ahB4G92RxR", "reviewer": "Reviewer_QdnR", "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).", "questions": "Questions while reading the paper:\n- 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}. \n- L99: What is P here?\n- 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)?  \n- 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?\n-  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).\n- 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.\n-  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! \n\n\n`[5]`: https://distill.pub/2021/multimodal-neurons/\n\n`[6]`: https://arxiv.org/pdf/1806.00451\n\n`[7]`: https://arxiv.org/abs/1810.03505\n\n\n-----\nIncreasing my score to __Accept__ after discussions with authors.", "limitations": "The authors have adequately addressed limitations in the Appendix. I appreciate the inclusion of a broader impacts section!", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "__Significance__: A lot of recent work has provided empirical efficacy of using CLIP-based interpretable models for few shot classification [1-4]. In practice, the concepts that achieve a high CLIP activation are often nonsensical. A theoretical understanding of the underlying mechanisms behind CLIP based CBMs are extremely desirable and relevant to the NeurIPS community.\n\n`[1]`: https://arxiv.org/abs/2211.11158\n\n`[2]`: https://arxiv.org/abs/2308.03685\n\n`[3]`: https://arxiv.org/abs/2404.09941\n\n`[4]`: https://arxiv.org/abs/2210.07183", "weaknesses": "_(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)._\n\n__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.\n\nOverall, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your in-depth review and for highlighting this theoretical work's high relevance to the NeurIPS community.\n## New experiments\nThe purpose of the experiments in our paper is to illustrate the theoretical insights, and we believe the current experiments serve that purpose well. However, to validate our insights further, and as per your comment, we have run experiments on additional datasets as suggested, including CINIC-10 for domain generalization. We refer to the 'Global Response' for the new results. \n## Questions\nWe emphasize our gratitude for the careful review shown by the questions posed, notably since each led to valuable improvements. Next, we indicate the resulting improvements to the paper.\n### Clarity\n* We address the ambiguity regarding the meaning of $P$ in L99 with the following modification: \"[...] $\\\\mathcal{D}=\\\\{(x_i, y_i)\\\\sim_{iid} \\\\mathbb{P}(\\\\mathcal{X}, \\\\mathcal{Y})\\\\}$ is a dataset drawn from the data-generating process $\\\\mathbb{P}(\\\\mathcal{X},\\\\mathcal{Y})$ [...]\".\n* Thanks for flagging the model typo. We use ViT B-32; we have updated it in the text in L275-276.\n### Linearity\nIndeed, CLIP embeddings of images $CLIP:\\\\mathcal{X}\\\\rightarrow \\\\bar{\\\\mathcal{X}}$ are non-linear and result from a hierarchical composition of neurons. Our analysis does not assume linearity of such a mapping, but rather linearity of the mapping from the CLIP embedding $\\\\bar{\\\\mathcal{X}}$ to the concept representation, which is consistent with the CLIP objective [2] as stated in L150 (\"where it assumed that concepts can be related to directions\"), as well as linearity\nof the output layers, a standard practice for CBMs [1] and when using CLIP embeddings [2].\n\nWe understand our usage of $\\\\mathcal{X}$ to denote inputs from this embedding space might confuse readers, so we will denote the CLIP embedding space as $\\\\bar{\\\\mathcal{X}}$ throughout the paper and modify L149 to \"To that end, we consider the input space $\\\\bar{\\\\mathcal{X}}$ as the joint embedding space of inputs and concepts from a foundational model [...]\".\n### Redundant concepts\nWe agree that a more nuanced discussion would benefit L248. \n\nAs per Theorem 1, having a concept that does not decrease the misspecification $\\\\varepsilon$, which can happen either 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 of the risk (see L177-178). This is what we mean by a *redundant concept*.\n\nHowever, there will be many cases where the given concept will not be entirely redundant (i.e., only slightly affect $\\\\varepsilon$), and in these cases, the choice of keeping or discarding it will depend on the number of samples we have. Both our theoretical and empirical insights (see L281-293) conclude that in lower sample regimes, we should be more aggressive at discarding slightly *redundant concepts*, and as $n$ grows, we will benefit more from preserving them, as you point out.\n\nWe appreciate that you flagged the importance of providing a more comprehensive discussion of when to \"remove *redundant concepts*\" in L248 and connecting it to the theoretical insights. We have correspondingly included the above discussion as a footnote. \n### Examples\n#### Motivation for CBMs\nYour provided example nicely illustrates how CBMs can exploit the composition of concepts to perform tasks beyond CLIP's training distribution. We have correspondingly added a version of it in line 24. We believe it best to keep the presentation of CBMs in the first paragraph agnostic to the identification method (CLIP) for generality, so we slightly modified it to the following phrasing without discussing CLIP: \"Indeed, despite never having seen a Tesla Model X, someone could reasonably classify them provided they can identify an SUV, a T logo, gull-wing doors, and the absence of exhaust pipes.\" \n#### Non-Concepts\nLet us start with a specific example and then move into a more formal characterization.\n* We humans do not develop some concepts for fields outside our areas of interest (our interest is informative of our underlying task $\\\\mathcal{T}$) despite experiencing occurrences of such concepts. Consider, for example, filmography concepts such as \"Jump cut,\" where two sequential shots of the same subject are taken from camera positions that vary only slightly (or a \"Dutch tilt\"). According to Def. 1, for people not interested in filmography, these characteristic functions would not be included in the concept set because they add negligible expressiveness to their current concept set, i.e., $N_0\\\\rightarrow \\\\infty$ without significantly contributing to the model-aware inductive bias, so $N_1 < N_0$, failing the definition.\n* More abstractly, a characteristic function $c$ that does not provide additional valuable information on top of the existing set $\\\\mathcal{C}$ for $\\\\mathcal{T}$ will have low expressiveness (i.e., large $N_0$) without increasing $N_1$. This can occur when targets are independent of $c$ conditioned on $\\\\mathcal{C}$: e.g., concepts irrelevant to the task (e.g., tinted glass when predicting a Model X) or completely redundant with $\\\\mathcal{C}$. It can also happen when the output model cannot capture the correlation, e.g., $c$ might help cluster the input distribution into two concentrical spheres, but a linear model would not benefit from this. Further still, even if a characteristic function $c$ provides information that can be captured, if the inductive bias of the method disprefers the optimal hypothesis given this representation, once again, $N_0$ will be large. \n\nWe believe this discussion can be valuable to some readers, so we incorporate it in a new appendix and reference it in L109.\n## References\n[1] P. W. Koh et al., \"Concept Bottleneck Models\".\n\n[2] A. Radford et al., \"Learning Transferable Visual Models From Natural Language Supervision\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all reviewers for their thoughtful and insightful feedback. We appreciate their recognition of the relevance and importance of our research on understanding the properties of concept sets and their impact on Concept Bottleneck Models (CBMs). We value their appreciation of the provided theoretical insights, and we are committed to addressing their comments and questions to improve our work based on their feedback.

While we provide individual responses to address specific questions, we would like to share globally the **new results** we obtained during the rebuttal process in response to the reviewers' comments. The primary goal of the experiments in our paper is to illustrate our theoretical insights, and we believe the current experiments effectively fulfill this purpose. However, based on the reviewers' suggestions for a more comprehensive set of experiments encompassing additional datasets and baselines, we have included a new out-of-distribution **(OOD) generalization experiment on CINIC-10** [1] and three new experiments on **sample efficiency on CUB-200-2011** [4], **Food 101** [3], and the **Describable Textures Dataset** [2]. Furthermore, we run an experiment on CIFAR-10 **comparing our method with Label-free Concept Bottleneck Models** [5], a meaningful baseline from the literature. The results, including four plots and a table, are provided in the supplementary PDF. We discuss the results and experimental setup in detail in a new appendix. These additions are referenced in the main text at L274, where we discuss the datasets used, as well as at L293 and L326, to point the reader to the additional experiments.

Next, we include an adapted version of the appendix to discuss the new experiments.
## New Data-efficiency Experiments
Responding to the reviewers' call for more comprehensive evaluations, we conducted three new experiments focusing on the data efficiency of CBMs. These experiments compare the performance of a linear output layer on top of the CLIP representation against our concept-bottleneck counterpart across various sample sizes, averaged over five seeds. The datasets used include CUB-200-2011, Food 101, and the Describable Textures Dataset.

**The results reaffirm the insights from theorem 1**. In the small sample regime, the first term of the risk dominates and predicts increased sample efficiency for the CBM compared to the baseline.

However, as the sample size increases, we observe the gap in performance decreases and even reverses in the large sample regime, which is explained by the fact that
> [...] the $\\varepsilon$ coefficient grows with the number of examples $n$

That is, the information loss resulting from the bottleneck, encapsulated in the $\\varepsilon$, becomes dominant and determines the asymptotic gap between the CBM and the baseline.
## New OOD Experiment on CINIC-10
To further validate the robustness of CBMs to distribution shifts, we conducted an OOD generalization experiment on CINIC-10. This experiment used CIFAR-10 images for training, and ImageNet subclasses from the CINIC-10 test set, conforming to a shifted distribution setting. 

**Results show that CBMs exhibit superior OOD generalization capabilities**, aligning with our previous results on the 12 datasets from the MetaShift collection.
## New Baseline: Comparison with Label-Free Concept Bottleneck Models
We reiterate that the main contributions from our work lie in the theoretical insights, and our method and experiments are tailored to support these insights. Nonetheless, as per reviewer comments, we have run an additional experiment on CIFAR-10, comparing the performance of our method with label-free CBM [5] as a baseline.

For a fairer comparison of the concept set selection mechanisms, we provide both methods with the same sampling mechanism $c_i \sim L(c | C_T)$ by fixing the language model $L$ and the context we feed it $C_T$. We also use VIT-B/32 for both methods. We then use CLIP and a linear probe, as described in [5], to obtain the baseline. We average the results of training the output probes over five seeds for each training size.

The results show that **our CBM consistently outperforms the baseline**.

---
We hope the additional experiments address the reviewers' concerns; we believe these enhancements strengthen our submission and look forward to further feedback.

## References
[1] L. N. Darlow, E. J. Crowley, A. Antoniou, and A. J. Storkey, "CINIC-10 is not ImageNet or CIFAR-10," Oct. 02, 2018, arXiv: arXiv:1810.03505. doi: 10.48550/arXiv.1810.03505.

[2] M. Cimpoi, S. Maji, I. Kokkinos, S. Mohamed, and A. Vedaldi, "Describing Textures in the Wild," in 2014 IEEE Conference on Computer Vision and Pattern Recognition, Jun. 2014, pp. 3606–3613. doi: 10.1109/CVPR.2014.461.

[3] L. Bossard, M. Guillaumin, and L. Van Gool, "Food-101 – Mining Discriminative Components with Random Forests," in Computer Vision – ECCV 2014, D. Fleet, T. Pajdla, B. Schiele, and T. Tuytelaars, Eds., Cham: Springer International Publishing, 2014, pp. 446–461. doi: 10.1007/978-3-319-10599-4_29.

[4] Wah, C., Branson, S., Welinder, P., Perona, P., and Belongie, S., "The Caltech-UCSD Birds-200-2011 Dataset," California Institute of Technology, CNS-TR-2011-001, 2011.

[5] T. Oikarinen, S. Das, L. M. Nguyen, and T.-W. Weng, "Label-free Concept Bottleneck Models," presented at the The Eleventh International Conference on Learning Representations, Sep. 2022.

Meta-review: 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.
Decision: Accept (poster)