Provably Learning Concepts by Comparison

We are profoundly thankful for your insightful feedback and the time you have dedicated to reviewing our work. Your suggestions have been invaluable in helping us improve the manuscript. In response, we have carefully revised the presentation, with particular focus on enhancing the clarity and accessibility of our theoretical results. Please kindly find our point-by-point responses below.

Q1: Real-world examples of how the data-generating process may be instantiated.

A1: Thank you very much for your constructive suggestion. We fully agree that providing real-world examples of the generative process will greatly aid readers in understanding the theory. While we have illustrated different types of variables throughout the manuscript (e.g., Fig. 1, lines 86, 229-236), your suggestion made us realize that a standalone, complete example would make it easier for readers to follow. Therefore, we have added the following example in the preliminaries:

“ (Line 119) Example 1. Consider images of animals in an aquarium, where the observed variables $\mathbf{x}$ represent image pixels. The different animal types (e.g., “shark” and “turtle”) correspond to classes $c$. Class-dependent concepts might include attributes like “predator,” “sleek body,” and “ocean” (see, e.g., Fig. 1), while class-independent concepts could be “lighting” and “position.” The hidden generative process of each image depends on all of these concepts, though only some are specific to each class.”

Thank you again for this valuable input, which has helped us make the theoretical framework more accessible to readers.

Q2: Why is there a distinction between classes and concepts? Both appear to be unobserved --- unless the classes are indeed observed and this is the difference?

A2: Great point. You are correct: in our framework, the classes are observed, while the concepts remain latent. We have clarified this distinction further in the preliminaries to make it clearer for readers. Meanwhile, the class variables serve as “higher-level” elements relative to the concepts, with each class associated with multiple underlying concepts. This naturally forms a compositional structure that may be helpful for tasks such as compositional generalization and novel class discovery.

Q3: What is the type of class variable $\mathbf{c}$?

A3: Thank you for reviewing the paper so carefully, and we apologize for any confusion. In the updated manuscript, we have clarified that $\mathbf{c}$ is a real-valued surrogate variable representing the object’s class. The partial derivative serves as a technical tool to capture the dependency structure between classes and concepts in the general nonlinear case. For practical cases involving only discrete values, a mask can be used to model this structure instead. In light of your constructive comment, we have emphasized this clarification in the updated manuscript to prevent potential confusion.

Q4: Theorem 1 refers to "estimated latent concepts" --- what is the estimation procedure? If it is an identifiability result, why do we need to refer to estimated concepts at all?

A4: Thanks for raising this point. Indeed, the work studies identifiability theory and thus is analogous to the estimator. The proposed theory does not specify a particular algorithm or estimator but rather addresses the conditions under which latent concepts can be identified from observations. In the identifiability literature, terms like "estimated latent concepts" or "estimated latent variables" are commonly used to describe the identifiability objective (e.g., [Hyvärinen & Morioka, 2016; Khemakhem et al., 2020; Sorrenson et al., 2020; Lachapelle et al., 2022; Hyvärinen et al., 2024]). As such, the specific estimation procedure is introduced later in the experimental setup. To clarify, we have added the following explanations next to Theorem 1 and in the preliminaries:

“(Line 193) It is worth noting that the identifiability theory remains agnostic to the choice of estimator, provided the marginal distributions of the observations are matched. The results demonstrate that for any pair of classes, the unique concepts specific to each class can be disentangled from the other concepts.”

“(Line 136) Since identifiability is one of the main concerns, the theory is agnostic to estimators and the goal is to fit the marginal distribution $p(\mathbf{x})$ with model (learner) $\hat{f}$ and estimated variables $\hat{\mathbf{z}}$ to achieve certain identifiability.”

Dear Reviewer Z5MD,

Thank you very much for taking the time to provide your thoughtful feedback. We hope our responses have addressed your concerns. As the discussion period nears its end, we warmly welcome any further input you may have and would be more than happy to engage in discussions.

Best wishes,

Authors of Submission8461

• Q1.3: What is the meaning of "identifiable up to a subspace-wise invertible transformation"?

• A1.3: Thanks for the comment. By "identifiable up to a subspace-wise invertible transformation," we mean that variables can be identified up to an invertible mapping between subspaces instead of the entire space. This objective is prevalent in the identifiability literature [Kong et al., 2022; Lachapelle et al., 2022; Li et al., 2023; Zheng & Zhang et al., 2023; Hyvärinen et al., 2024], where it is sometimes referred to as "subspace-wise" or "block-wise" identifiability.

  To avoid any potential confusion, we have added the following definitions in the preliminary section for a more comprehensive coverage of the related background:

  “(Line 138) We introduce several identifiability objectives (Hyvärinen & Morioka, 2017; Lachapelle et al., 2022; Zheng et al., 2022; Kong et al., 2022; Hyvärinen et al., 2024) that are common in the literature as follows:”

  “(Line 141) Definition 1 (Element-wise Identifiable). The set of latent variables $\mathbf{z} \subseteq \mathbb{R}^n$ are element-wise identifiable if there exists an invertible function $h_i: \mathbb{R} \rightarrow \mathbb{R}$ and a permutation $\pi$ s.t. $\hat{\mathbf{z}}_i = h_i(\mathbf{z}\_{\pi(i)})$.”

  “(Line 143) Definition 2 (Subspace-wise Identifiable). The set of latent variables $\mathbf{z} \subseteq \mathbb{R}^n$ are subspace-wise identifiable if there exists an invertible function $h: \mathbb{R}^n \rightarrow \mathbb{R}^n$ s.t. $\hat{\mathbf{z}} = h(\mathbf{z})$.”

  To further enhance clarity, we also reference these definitions in our theorems to assist readers who may be less familiar with this topic. Thank you again for your helpful feedback, which has allowed us to make these details more accessible to a broader audience.

Q2: Assumption of conditional independence seems to be strong.

A2: Thank you for your feedback. In our setting, the relationship between class and concepts makes conditional independence a natural formulation of the problem. For instance, although the concepts "wings" and "feathers" are semantically dependent, they become conditionally independent when given the class variable "bird." This highlights a meaningful form of modularity that aligns with the structure of class-concept relationships in our framework.

Intuitively, some form of modularity in latent variables is essential to recover them individually, and conditional independence is a well-established formulation, frequently used in statistical frameworks like independent component analysis. It is a common assumption in prior work on the identifiability of latent variable models [Hyvärinen & Morioka, 2016; Khemakhem et al., 2020; Sorrenson et al., 2020; Lachapelle et al., 2022; Hyvärinen et al., 2024]. Even in rare cases the latent variables are actually conditionally dependent, we can still make use of some other additional information, such as multiple domains [Zhang et al., 2024].

Moreover, it may be helpful to note that our constraints are, in fact, less restrictive than those in prior works on identifiable concept learning such as [Rajendran et al., 2024]. Whereas previous studies often assume (conditional) independence across all concept variables $\mathbf{z}$, our work allows for arbitrary dependencies among class-independent concepts, thereby accommodating more general scenarios.

In response to your excellent suggestion, we have incorporated examples like the following into the paper to illustrate this:

“(Line 153) The conditional independence provides a form of modularity commonly adopted in prior work on identifiable latent variable models (Hyvärinen & Morioka, 2016; Khemakhem et al., 2020; Sorrenson et al., 2020; Lachapelle et al., 2022; Hyvärinen et al., 2024). It may be particularly suitable in our class-concept framework; for example, while the concepts 'wings' and 'feathers' are related, they become conditionally independent given the class variable 'bird.'”

Thank you once again for your thoughtful feedback, which has helped us enhance the clarity and contextualization of this assumption.

Q3: Can the class vector $\mathbf{c}$ take continuous real values?

A3: Thanks for this observation. You are absolutely correct; the class vector $\mathbf{c}$ can indeed take continuous values. We have highlighted this in the updated manuscript to improve clarity. The derivative serves as a technical tool to represent the dependency structure between classes and concepts in the general nonlinear setting. In practical scenarios where only discrete values are available, a mask can be used to effectively represent the structure. We appreciate your feedback, which has helped us clarify this aspect of the paper.

We deeply appreciate the valuable insights you have shared, which have helped us enhance the quality and clarity of the manuscript. In light of your great feedback, we have carefully revised the manuscript, adding further clarifications and explanations. Please kindly find our detailed response below.

Q1: The main weakness of the paper is its presentation. I list several issues about the presentation as follows.

A1: Thank you very much for your comments, which have nicely inspired us to rewrite some paragraphs to make the messages more explicit for a broader audience. We hope your concerns have been properly addressed, and would be delighted if you find the key messages we aim to deliver interesting and exciting. We provide detailed responses to each of the comments as well as the corresponding updates as follows:

• Q1.1: Lack of a clear definition of what a learner is expected to output and how to measure the performance of a learner.

• A1.1: Thank you for highlighting this point—we truly value the opportunity to clarify our focus. As mentioned in line 136 in the preliminaries, $\hat{z}$ denotes estimated concepts, which represents the output of a learner. Our work centers on identifiability theory, specifically on establishing the conditions under which the latent data-generating process (model) can be identified (up to a certain indeterminacy) from observations. Since our study is grounded in theoretical foundations rather than specific implementation, it is designed to be learner-agnostic and does not specify a performance measure. The specific estimation procedure is thus described later in the experimental setup. In light of the comment, we have also added the following sentence in the preliminary:

  “(Line 137) … the goal is to fit the marginal distribution $p(\mathbf{x})$ with model (learner) $\hat{f}$ and estimated variables $\hat{\mathbf{z}}$ to achieve certain identifiability.”

  Furthermore, we recognize that further emphasizing this scope could be beneficial and have added clarifications throughout the updated manuscript. For example:

  “(Line 193) It is worth noting that the identifiability theory remains agnostic to the choice of estimator, provided the marginal distributions of the observations are matched. The results demonstrate that for any pair of classes, the unique concepts specific to each class can be disentangled from the other concepts.”

  We hope this clarification helps make our task clearer. Thank you once again for your feedback.

• Q1.2: It is confusing what algorithm/estimator a learner uses to get such an estimation.

• A1.2: Thank you for raising this question. As mentioned in our response to Q1.1, our work focuses on the identifiability theory, which is intentionally learner-agnostic. The theory does not specify a particular algorithm or estimator but rather addresses the conditions under which latent concepts can be identified from observations. Therefore, the specific estimation procedure is included in the experimental setup, which is basically a MLE. In the identifiability literature, terms like "estimated latent concepts" or "estimated latent variables" are commonly used to describe the identifiability objective (e.g., [Hyvärinen & Morioka, 2016; Khemakhem et al., 2020; Sorrenson et al., 2020; Lachapelle et al., 2022; Hyvärinen et al., 2024]). We appreciate your feedback and have further highlighted it in the updated manuscript:

  “(Line 136) Since identifiability is one of the main concerns, the theory is agnostic to estimators and the goal is to fit the marginal distribution $p(\mathbf{x})$ with model (learner) $\hat{f}$ and estimated variables $\hat{\mathbf{z}}$ to achieve certain identifiability.”

Dear Reviewer omEm,

Thank you sincerely for your time and thoughtful feedback. Could you please kindly let us know if the concerns have been properly addressed? We believe that the main confusions have been clarified. Specifically, they are related to the common practice in the identifiability literature:

• Identifiability theory is estimator-agnostic, which is standard in the literature. In the updated manuscript, we have added clarifications and highlights throughout the paper to avoid potential confusion;

• Subspace-wise identifiability is widely used in the literature. In the updated manuscript, we have added relevant definitions as background in the preliminary;

• Conditional independence is a common assumption in previous theories, which we have further relaxed. In the updated manuscript, we have added further highlights on it.

To prevent any potential misunderstanding, we have incorporated additional highlights and expanded background definitions in the revised version, following your excellent suggestions.

Moreover, we have conducted new synthetic and real-world experiments to further support our theoretical results (Appendix C.2). Given the significant empirical successes in the literature of concept learning but the limited theoretical exploration, we are committed to providing as many insights as possible to benefit the community.

If you have any further questions or additional feedback, we would be grateful to hear from you.

Thank you again for your efforts and for contributing to the review process.

Best regards,

Authors of Submission8461

We are genuinely grateful for the time you have dedicated and for your insightful comments. In response, we have added several new discussions in the updated manuscript, with a particular focus on comparisons to these prior works. Please find our detailed response below:

Q1: Detailed comparison with earlier works such as [Zheng et al., 2022; Zheng & Zhang, 2023; Kong et al. 2024].

A1: Thank you very much for connecting these seemingly different domains. Since both lines of research explore latent variable models, they indeed share insights toward building identifiability results. As mentioned in the discussion of implications (e.g., lines 372-377), our results might also be of theoretical interest to fields such as disentanglement and causal representation learning:

“(Line 372) Despite being one of the essential pieces on learning the hidden concepts, our proposed theory also sheds light on understanding the latent variable models without additional knowledge, since the formulation is just based on the basic generating process between latent and observed variables. As a result, part of the proposed results might also be of independent interest to other fields such as disentanglement (Hyvärinen et al., 2024), causal representation learning (Schölkopf et al., 2021), object-centric learning (Mansouri et al., 2024), compositional generalization (Du & Kaelbling, 2024), and causal structure learning (Spirtes et al., 2000).”

At the same time, there are some key distinctions:

1. While [Zheng et al., 2022; Zheng & Zhang, 2023; Kong et al., 2024] also consider the identifiability of latent variables, our problem of concept learning differs from theirs. As highlighted in line 63, our work aims to answer the question of which concepts can be reliably recovered in the most general case. Our primary identifiability result is rooted in the cognitive process of learning by comparison: given any pair of classes, the unique concepts corresponding to each class can be identified. This forms the foundation of our local identifiability based on pairwise comparisons and extends to more general cases, including global identifiability. For example, given any two pairs of classes, we can always disentangle latent concepts that represent each class’s unique features.

   In contrast, [Zheng et al., 2022; Zheng & Zhang, 2023; Kong et al., 2022] focus on identifying all latent variables as a complete hidden representation and lack the flexibility to provide insights in a localized manner. If any variables in the considered set do not meet their assumptions, they cannot guarantee identifiability. In fact, it is common for these conditions to be partially unmet. For instance, structural sparsity in [Zheng et al., 2022; Zheng & Zhang, 2023] is rarely satisfied for all latent variables, as verified by [Zheng & Zhang, 2023]. Similarly, [Zheng & Zhang, 2023; Kong et al., 2022] require at least $2n_A+1$ environments for the changing variables, which may be infeasible in certain cases. Therefore, in practical scenarios where assumptions may not hold universally, our approach offers flexible identifiability results through the strategy of learning by comparison, which these previous works do not address.

2. Our technical assumptions also differ in key ways:

   • [Zheng et al., 2022] assumes a sparsity structure between $\mathbf{z}$ and $\mathbf{x}$, disallowing dense Jacobians in the generative function $f$, while our approach places no constraints on $f$.

   • [Zheng & Zhang, 2023] also consider the structural sparsity on the mixing procedure between invariant latent variables and observed variables, while we allow arbitrary mixing structure. Moreover, they require $2n_A+1$ distinct environments for the changing latent variables, which we do not impose.

   • [Kong et al., 2022] addresses domain adaptation with a focus on content-style disentanglement, achieving component-wise identifiability for style variables but also requiring $2n_A+1$ distinct environments.

   Therefore, regarding assumptions on structures, [Zheng et al., 2022; Zheng & Zhang, 2023] assume a sparse structure in the generating function $f$ that maps latent variables $\mathbf{z}$ to observed variables $\mathbf{x}$ ($\mathbf{x} = f(\mathbf{z})$), whereas our approach does not impose any conditions on $f$. Instead, we focus solely on the structure between classes and concepts to determine which concepts can be reliably recovered. Furthermore, [Zheng & Zhang, 2023; Kong et al., 2022] require at least $2n_A+1$ distinct environments, an assumption we do not impose.

Summary: Our work differs both in problem settings and technical conditions. Given the distinct objectives, we do not claim our theory is more general. Instead, our aim is to determine which concepts can be reliably identified with minimal assumptions in a broad setting. Our local identifiability theory can provide meaningful identifiability results with any pair of classes.

Dear Reviewer NXKX,

Thank you very much for your time and thoughtful suggestions. We hope we have adequately addressed your concerns. As the discussion period is nearing its conclusion, please feel free to share any additional feedback. We would be more than delighted to continue the discussion with you.

Best wishes,

Authors of Submission8461

Dear Reviewer NXKX,

We sincerely appreciate your further feedback and suggestion that new real-world experiments could better support the claimed difference. In light of your great suggestions, we have conducted new real-world experiments on more complex scenarios. We would be truly grateful if you could let us know whether these updates adequately address your concerns. We look forward to your feedback and the opportunity to provide further clarifications if needed.

Specifically, we performed experiments on the FFHQ dataset, which comprises $70,000$ human face images. The results, now highlighted in purple, are presented in Figures 12, 13, and 14 in Appendix C.2 of the updated manuscript. These results reveal that many concepts remain entangled after estimation, indicating that the assumptions required for full identifiability in previous theories may not be fully satisfied. However, these class-related concepts are still identifiable as a group, consistent with our theorem based on local or pairwise comparisons. This provides clear real-world evidence of scenarios where our theory offers a potential theoretical foundation, whereas previous guarantees fall short due to the lack of flexibility for local identification.

The detailed discussion is included as follows:

“Additional real-world experiments. To explore scenarios where not all concepts can be identified component-wise, we conduct additional real-world experiments on a more complex scenario, i.e., the FFHQ dataset (Karras et al., 2019). The dataset contains $70,000$ human face images, which is more complicated than the datasets in our other experiments. In addition to the estimation method introduced before, we incorporate a sparsity regularization ($\ell_1$ norm) on the Jacobian of the mixing function $f$, as required by (Zheng et al., 2022; Zheng & Zhang, 2023). Note that the identifiability theory in (Kong et al., 2022) does not require specific regularization during estimation if the task is not domain adaptation.”

“From Figs. 12, 13, and 14, it is evident that some concepts remain entangled and cannot be fully recovered. For instance, for the class ``Age'', concepts like skin, eye, and face shape are all entangled together, suggesting that assumptions in (Zheng et al., 2022; Zheng & Zhang, 2023, Kong et al., 2022) for component-wise identifiability may not be fully satisfied in this scenario. However, these class-related concepts can still be identified as a group, consistent with our theorem based on local or pairwise comparisons. This suggests that, even in complex scenarios where prior theories fail to guarantee identifiability due to assumption violations, our alternative identifiability framework based on pairwise comparisons may still provide an alternative theoretical basis for recovering class-related concepts collectively, even if they remain entangled. This sheds light on the necessity of our alternative identifiability guarantees in some complicated real-world scenarios.”

We believe these new experiments, alongside our existing results on four other real-world datasets, emphasize the significance of our theory in explaining the empirical success of concept learning across diverse settings. We are sincerely grateful for your constructive suggestions, which have significantly enhanced our manuscript. It has truly been a privilege to have you dedicate your time and effort to helping us improve our work.

Thank you once again for your invaluable feedback.

Many thanks,

Authors of Submission8461