Learning Discrete Latent Variable Structures with Tensor Rank Conditions

We appreciate your careful review and suggestions and would like to thank you for your positive assessment of our work.

Q1: I wonder if some assumptions are a bit strong such as the faithfulness assumption and the three pure child assumption and I wonder how they play into practical scenarios.

A1: We would like to mention that to render the identifiability of the latent variable structure, we introduce the assumptions of the three pure children and faithfulness.

Regarding the three-pure child assumption, it is a commonly used condition, well-studied in both linear and discrete models, as demonstrated by Silva et al., 2006, Kummerfeld and Ramsey, 2016, and Chen et al., 2024 (more related works can be found in the introduction of our manuscript). It is worth noting that the pure child assumption is often valid when data is collected through questionnaires, which is a common practice in fields such as social science, psychology, and medical science. For a more detailed discussion of the three-pure children assumption, please refer to the general response.

Regarding the faithfulness assumption, it plays a significant role in constraint-based methods, ensuring that the learned structure accurately represents a causal graph. It is considered a standard assumption, which is known to hold in simple systems such as linear Gaussian models [Meek (1995)]. This concept has been extensively discussed in the literature [Spirtes et al., 2000; Spirtes and Glymour, 1991].

We appreciate your comments and will discuss these assumptions further in the revision.

Q2: How does this paper compare to works like [1] where rank constraint is also used in a non-linear setting?

A2: We would like to clarify that there are two main differences compared to [1].

First, the tensor rank condition in our work can capture more d-separation information among observed variable sets. For example, the graphical implications of tensor rank allow us to infer the d-separation among any pair of variables within the variable set $\mathbf{X}_p$, whereas the rank of the probability table only infers the d-separation between two variables (or vectors). In particular, when only two-way tensors are considered, [1] can be seen as a specific case of our approach.

Second, in [1], the observed variables are continuous, making the recovery of the distribution of discrete variables untestable. Additionally, the model in [1] does not allow for 'triangle structures' among the latent variables. In contrast, our work does not require the recovery of the distribution of discrete variables and allows for any dependence among latent variables. Furthermore, [1] assumes that the cardinality of latent support is the same, whereas our work allows for different cardinalities of latent support (see Appendix F).

Reference:

[1] Kong, Lingjing, et al. "Learning Discrete Concepts in Latent Hierarchical Models." arXiv preprint arXiv:2406.00519 (2024).

Thank you for your insightful and valuable questions and for spending the time and effort on this review. We will respond to these issues point by point.

Q1: Allowing edges between observed variables: ... I think you can be more open about it, e.g., what are the challenges, what are the missing pieces?

A1: One of the challenges in impure structure is accurately identifying the number of latent variables. As shown in Figure 1 in our attached PDF, the rank constraints over the probability tensor can be equal by the graphical implication of tensor rank, hindering the identification of latent variables. Although we can detect the absence of edges between pairs of variables (as in the structure described in Sec. 7), a careful search strategy is still required, along with proper assumptions on the cardinality of latent support, to distinguish these equivalent classes. We will address this issue in our future work.

Q2: Structural constraints in the literature: I think you need to be more direct and provide exact requirements/structural constraints and results. ... Can you elaborate on the similarities and differences between the roles of these assumptions?

A2: In the linear non-Gaussian model, Cai et al. and Xie et al. show that the identification of the measurement model only relies on the two-pure children assumption, due to the availability of higher-order statistics from non-Gaussianity. However, in the linear Gaussian model, the three-pure children assumption is necessary, due to the indistinguishable equivalence classes in two-pure condition by Tetrad constraints (as noted by Silva et al. and Kummerfeld et al.). Interestingly, when only four-way tensors are considered in discrete models, the tensor rank condition serves as a 'nonlinear' version of the Tetrad constraints, resulting in similar structural limitations. Moreover, for discrete latent variable models, Gu and Dunson (2023) and Gu (2022) address only partial structures and their identifiability. For instance, they focus on either measurement models (under the same three-pure children assumption) or pyramid structures, without providing a comprehensive approach for all possible structures. We will include this discussion in the `Related Works' Section.

Q3: In Appendix D, ... a similar discussion for the other assumptions is missing. For instance, in the example in Section 7, the possibility of working on an impure structure is explained but failure cases (and why they happen) are not explained.

A3: The three-pure children assumption is a sufficient condition that ensures the identifiability of latent variables using the tensor rank condition over a four-way tensor (see more details in the general response). A similar reasoning applies in linear Gaussian latent variable models (e.g., Silva et al. and Kummerfeld et al.).

In the presence of an impure structure, the latent variable may not be correctly identified (see A1). Additionally, impure structures can arise when the collected variables have direct causal relationships. For example, in a questionnaire survey, the observed variables ‘occupations' and ‘income' may exhibit an impure structure because the attributes of different occupations can directly impact income.

Q4: Support of latent variables: … all latent variables have the same number of categories, with extensions provided in Appendix F”. ... If this is indeed the case, then I suggest the authors explicitly state it in the main paper.

Q4: Thank you for your careful observation. We will add the following illustrations to Section 4 to avoid confusion.

"For simplicity, we focus on the case where all latent variables have the same number of categories. The result can be directly extended to cases with different numbers of categories by sequentially testing the cardinality of the latent support (see details in Appendix F)."

Q5&6: I see that the definitions of metrics are in Appendix I. It would have been nicer to squeeze them into the main paper.

A5&6: Thank you for your suggestion. We will move the real-world application section into the appendix and add the details of evaluation metrics into the simulation experiment section.

Q7&8: I think your method should be able to handle an arbitrary number of children as long as there are at least 3. …. Perhaps starting from 1k would show the limits of the approach and help us to understand the performance better.

A7&8: Due to limited space, please see our response in the `Supplementary Experiments' part of the general response section.

Q9: Definition 2.1 (Discrete LSM): Is this a proper name?

A9: Thank you for your constructive suggestion. We will revise "discrete LSM" to "three-pure discrete LSM (abbreviated as discrete 3PLSM) in the revision."

Q10: Theorem 4.7: Please be careful when using $p$ in notations.

A10: We have revised them to $L_q$ and $X_p$ to avoid confusion.

Q11: Conclusion Section 8: Overall, I liked this conclusion. That being said, being more direct and recalling the main structural assumptions would have been good.

A11: We have added a recall of the three-pure children assumption and revised the last paragraph in the conclusion as follows:

"However, the proposed method can hardly be applied to high-dimensional discrete data and only applies to pure-children structures. Therefore, relaxing these restrictions and making them scalable to high-dimensional real-world datasets and more general structural constraints, such as impure structures and hierarchical structures, would be a meaningful future direction."

Q12: Typos etc.

A12: Thank you very much for your careful review. We have corrected these issues in the revision.

We sincerely thank the reviewer for their careful review and thoughtful suggestions, which have been very instructive. We will incorporate these discussions in the revision to improve our manuscript. If any explanations remain unclear, we welcome further discussion.

We appreciate your valuable comments and suggestions and thank you for your positive assessment of our work.

Q1: For the sufficient observation assumption, it seems that the cardinality of the observed variable support can be equal to the cardinality of the latent support, as discussed in Remark F.4. Could you clarify this?

A1: Thank you for your suggestion. You are correct. We only require the cardinality of the observed variables to equal that of the latent variables. We will revise this in the revision.

Q2: Why is the Three-Pure Child Variable Assumption required? In my opinion, the tensor rank condition can test the d-separation relations between only two observed variables, as shown in Figure 1. Thus, one can learn the causal cluster from a two-pure child variable assumption. Please correct me if I am wrong. If this assumption does not hold, what happens to the output of your algorithm?

A2: Thanks for raising these critical questions. If there are only two pure-measured children for each latent variable, it can result in an indistinguishable structure. For instance, as shown in the proof of Proposition 4.3, the tensor rank condition for a three-variable probability tensor leads to equivalence classes (Fig. 4 (a) $\sim$ (c)). However, with the four-way tensor, the cluster cannot be identified due to the structure illustrated in Fig. 5. Thus, the three-pure measured variable assumption is a sufficient condition to ensure the identification of the measurement model. If this assumption is not met, our algorithm may output a causal structure where the number of latent variables is smaller than the true number. However, to test the conditional independence (CI) relations among the latent variables, only two pure children for each latent variable are necessary (See Theorem 4.7). Thus, given the causal cluster with only two pure children for each latent variable, the CI relations can be tested, and the structure model remains identifiable. One can see more discussions in the general response.

Q3: In Proposition F.3, is easily confused with the concept of the cardinality of the support of a single latent variable. It is recommended to change the expression like r.

A3: Thank you for your suggestion. We have revised it in the revision.

Q4: typo: In Figure 2(b), LVM should be LSM.

A4: Thank you for your suggestion. We have corrected it in the revision.

Thanks for your careful and valuable comments. We will respond to these issues point by point.

Q1: [1] proposes a structure learning algorithm for measurement model with discrete latent variables, under what seems to be a weaker set of assumptions. In particular [1] does not require each latent variable to have at least three pure children and does not require that each observed variable has only one latent parent. Those assumptions seem quite strong. In particular, [1] seems to obtain a stronger result under similar, if not weaker, assumptions, and this paper does not cite [1].

A1: Thank you for pointing us to this interesting work. We would like to discuss its connection with our work.

The main difference is that the identifiability of [1] requires to assume that the "Mixture Oracle" is known (i.e., the mixture model over $\mathbf{X}$ is identifiable), without discussing how to obtain it, especially in discrete data while we do not require such an assumption. We would like to argue that the requirement of the Mixture Oracle may lead to a weaker identifiability result than ours due to the strict conditions in obtaining the Mixture Oracle. For instance, [2] indicates that a sufficient and necessary condition for identifying the parameters of a discrete mixture model is the presence of $2K-1$ strongly separate variables, where $K$ is the number of mixture components. This structural condition is more stringent than compared to our requirements. The reason is that identifying the mixture model requires learning the latent distribution $P(\mathbf{L})$, while our method does not rely on this. Furthermore, as discussed in Sec. 6 in [1], learning mixture models is a nontrivial problem. The author in [1] uses the approximate method, such as the K-means algorithm, to estimate the number of mixture components $k(S)$ for all $S \subset X$, which can affect the accuracy of the estimates in practice. Meanwhile, the K-means algorithm cannot be directly used in the discrete data, we thus do not include it in our baselines.

Q2: The technique used in [1] to identify causal structure is also similar in flavor, and also relies on studying the rank of joint probability tensor (through numbers k(S)). Considering that [1] operates under a significantly more general setup while relying on similar techniques and ideas, could the authors please clarify what is the main novelty of this paper compared to [1]?

A2: We would like to clarify the following points:

Identification based on Tensor Decomposition. Roughly speaking, [1] depends on unique tensor decomposition (actually, a technology of parameter estimation) and requires partial information from a Mixture Oracle. However, it is difficult to obtain the Mixture Oracle and unbiased parameter estimates. In contrast, our theoretical approach focuses on tensor rank constraints across different sets of variables, without directly relying on unique tensor decomposition or any prior information about the Mixture Oracle.

Specifically, in [1], the identification of the measurement model relies on unique tensor decomposition, such as the generalized Kruskal's theorem. To construct such a tensor, we require partial information from a Mixture Oracle, such as $k(S)$, where $k(S) = dim(Pa(S))$ according to observation 2.7 in [1]. It is important to note that $k(S)$ for any subset $S \subset X$ cannot be estimated from the tensor rank. As demonstrated by the graphical implications of tensor rank, the tensor rank is determined by the cardinality of the conditional set. That is, $Rank(P(S)) \neq dim(Pa(S)) = k(S)$. For example, consider a structure $L_1 \to L_2$, $X_1$ is children of $L_1$ and $\{X_2, X_3\}$ are children set of $L_2$. In this case, the tensor rank of the joint probability tensor over $S = \{X_1, X_2, X_3\}$ is $|supp(L_2)|$. According to the mixture oracle in [1], it requires that $k(S) = |supp(L_1, L_2)|$. In contrast, our theoretical result does not directly rely on the unique decomposition of tensors, but rather examines tensor rank constraints over various variable sets. A key challenge with the decomposition-based method is the difficulty in obtaining unbiased parameter estimates. Our method avoids this issue by focusing on the number of parameters, specifically the cardinality of latent support, making it a more practical solution.

Novelty. In our paper, we propose a statistically testable method, termed the tensor rank condition, which establishes the connection between tensor rank and d-separation among observed variables. The tensor rank condition is applicable to general discrete causal models and is not restricted to measurement models. This represents one of our main contributions compared to [1]. Based on the tensor rank condition, we provide an identification algorithm that can determine the causal structure of discrete latent structure models with a theoretical guarantee. Unlike [1], our algorithm offers a solution for discrete latent variable models without requiring any prior knowledge about the mixture model, thereby elegantly eliminating the need for a mixture oracle. Moreover, our method offers a theoretical guarantee and is simple and efficient due to the testability of the tensor rank condition.

Acknowledgements. Thank you for raising the constructive questions, which have inspired us to further explore discrete latent variable models. We will incorporate these discussions in the revised version, specifically in the 'Related Works' section. If you believe your concerns have been addressed, we kindly request that you consider adjusting your initial score accordingly. If any explanations remain unclear, we are open to further discussion.

Reference:

[1]. Kivva B, Rajendran G, Ravikumar P, et al. Learning latent causal graphs via mixture oracles.

[2]. Tahmasebi B, Motahari S A, Maddah-Ali M A. On the identifiability of finite mixtures of finite product measures.

I believe authors misunderstood points 3 and 4 in my comment above. I do not claim that (*) is obtained via minimal rank decomposition, as authors aim to refute in their response. 3 and 4 above use that any vector has a unique decomposition in a basis in a linear space.

To give a simplified example: Let $a_1, a_2 \in R^n$ be linearly independent and $b_1, b_2 \in R^m$ be linearly independent, then vectors $a_1\otimes b_1, a_2\otimes b_1, a_1\otimes b_2, a_2\otimes b_2$ are all linearly independent (as vectors in $R^{nm}$) and for a vector $T = \alpha_1 a_1\otimes b_1 +\alpha_2 a_2\otimes b_2 +\alpha_3 a_3\otimes b_3$ one can uniquely recover this decomposition if $a_i$ and $b_i$ are known, even if it tensor has smaller rank (say, 2).

One can recover vectors $P(X_i|pa(X_i))$ by looking at minimum rank decompositions of triples of variables and use it to recover necessary decompositions of $P(S|Pa(S))$ (and hence get mixture oracle), as I outlined above.

Please feel free to reach out if something is still not clear.

Thank you very much for your response. Please allow us to take a little time to clarify further.

We want to argue that $supp(Pa(S))$ cannot be directly estimated even under Assumption 2.4 and the three-pure children assumption when the latent structure is unknown and the subset $S$ has different latent variables.

We agree that in your example, when we known the three observed $X_i$, $X_j$ and $X_k$ is the pure children of $L$, the $supp(Pa(S))$ can be recovered through the tensor decomposition. However, when $S$ has different latent variables and the unknown causal structure, the minimum rank tensor decomposition does not necessary correspond to the $supp(Pa(S))$ and it will produce multiple equivalence class as we discussed in the proof of Prop. 4.3 in our paper, such that $supp(Pa(S))$ can not be identified.

Consider the structure in Fig. 4(c) in our paper, without loss generality, let $L_2 \to L_1, L_2 \to L_3$, $L_1 \to X_j, L_2 \to X_i$ and $L_3 \to X_k$. Let $S = \{X_i, X_j, X_k\}$. As such, we will have the following decomposition:

where the vectors $\sum_{L_2} P(X_j, L_2|L_1=i)$ and $\sum_{L_3} P(X_k, L_3|L_1=i)$ also are linear independent. In this case, we can find a unique decomposition (based on Kruskal's theorem), but not follow the form of (*), i.e., $P(S) \ne \sum_{\ell \in supp(Pa(S))} P(S|Pa(S) = \ell) P(Pa(S) = \ell)$.

Moreover, in our work, the conditional independence between latent variables can be tested by the tensor rank condition (Theorem 4.7), without assuming the existence of the mixture model and recovering the distribution of latent variables.

We are very grateful for your patient response. Please feel free to reach out if you have any further questions.

I am grateful for your response.

However, we want to argue that without knowing the structure information we will have different basis when we probe at different triples and we do not know which one is the "correct".

It is actually easy to identify the "correct" one. Let's fix $X_i$ and look at triples with different $X_j, X_k$. If minimum rank decomposition has more than d components we can immediately refute triple as incorrect, which handles your concern about uniqueness of the decomposition. By Kruskal's theorem, those triples that admit decomposition of rank at most d will have a unique decomposition. Decompose all such tensors and compile a list of first-mode components for each of them. Note that $P(X_i|L = \ell) = \sum_{t} P(X_i|L = \ell, Pa(X_i) = t) P(Pa(X_i) = t| L = \ell) = \sum_{t} P(X_i| Pa(X_i) = t) P(Pa(X_i) = t| L = \ell)$ and all $P(Pa(X_i) = t| L = \ell)$ are non-negative. This means that each vector of the form $P(X_i|L = \ell)$ belongs to the convex hull of the "correct" set of vectors $P(X_i| Pa(X_i) = t)$. Since all P(X_i| Pa(X_i) = t) are linearly independent by assumption 2.4, they are the unique "defining directions" of the convex cone formed by all first mode components of tensor decompositions of $P(X_i, X_j, X_k)$ with a fixed $i$. Note also that there is no ambiguity about the direction (sign) of the vectors in the decomposition, as we expect every vector participating in the decomposition to have positive entries. Note that no structure information is used, and one do not need to assume that all latent variables have the same support, etc.

Moreover, we want to show that, without the structure information, $Pa(X_i|Pa(X_i))$ may not be identifiable due to violation of the unique decomposition condition.

By assumptions of this paper, the triples of variables $X_i, X_j, X_k$ which are of interest to construct "mixture oracle" have unique decomposition of rank at most $d$ ($d$ here can be replaced with the size of the support of observed variables, so knowledge of $d$ is not needed). All other triples can be ignored.

Please let me know if you have any questions.

Dear Reviewer tR91,

Thank you for your effort and your time. We would like to argue that by fixing $X_i$ and looking at triples with different $X_j, X_k$, we may not be able to figure out that the triple is incorrect.

For example, consider a simple structure $L_1 \to L_2 \to L_3$, where each latent varaible has three pure children, corresponding to $X_{123}$, $X_{456}$, and $X_{789}$, respectively. When we fix $X_1$ and look at any $X_j, X_k \in \overline{X_1}$, one can see that there is still a minimum rank decomposition with d components (where d represents the cardinality of latent support). This is because any three observed variables can be d-separated by only one latent variable in this structure (see the proof of Prop. 4.3). For instance, let $X_j=X_4$ and $X_k = X_7$, which is the example in the previous response. Thus, we cannot check if the basic $P(X_j|L)$ is actually $P(X_j|Pa(X_j))$ from the decomposition.

Please let us take this opportunity to highlight our contributions, in order to situate this work in the rich literature:

1. We introduce a statistically testable tool, termed the tensor rank condition , which establishes a connection between rank constraints and d-separation relations within a discrete model.
2. Utilizing the tensor rank condition, we achieve the identification of the measurement model under the three pure children assumption.
3. Furthermore, based on the tensor rank condition, we complete the identification of the structural model, requiring only two pure children for each latent variable.

In [1], the authors leverage information from a mixture oracle and perform tensor decomposition to identify the measurement model, recovering the distribution to learn the latent variable structure. However, the identification approach in this work relies on the existence of a mixture oracle, and estimating the mixture oracle is a non-trivial task.

Most importantly, we want to emphasize that the tensor rank condition is not restricted to any specific mixture model and does not rely on information from such models. The discrete causal structure can be discovered using the tensor rank condition, which allows for identifying edges between observed variables and even permits causal directions from observed to latent variables. We believe that the tensor rank condition opens up new research directions and offers promising avenues for developing search algorithms for latent variable researchers.

Moreover, as we discussed in the general response, the three pure children assumption is merely a sufficient condition for identifying the measurement model by tensor rank. We also explored potential extensions to more general conditions, such as impure structures or hierarchical structures, for identifiability. We discussed that the tensor rank condition has the capacity to handle these cases, which we outline as directions for future work.

If you have further feedback, we hope to read it and hope for the opportunity to respond to it. We highly appreciate your engagement in the discussion.