Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
61,274 characters · 11 sections · 29 citation commands
Learning Causal Representations from General Environments: Identifiability and Intrinsic Ambiguity
Artificial intelligence (AI) has achieved tremendous success in various domains in the past decade bengio2013representation,silver2016mastering,bubeck2023sparks. However, current approaches are largely based on learning the statistical structures and relationships in the data that we observe. As a result, it is not surprising that these approaches often capture spurious statistical dependencies between different features, resulting in poor performance in the presence of test distribution shift ovadia2019can,koh2021wilds or adversarial attacks akhtar2018threat,wang2023adversarial.
In view of these pitfalls, a recent line of work has explored the problem of causal representation learning scholkopf2021toward, the task of learning the causal relationships between high-level latent variables underlying our low-level observations. Notably, it is widely believed in cognitive psychology that humans take a causal approach to distill information from the world and make decisions to achieve their goals shanks1988associative,dunbar2004causal,holyoak2011causal. As a result, there is reason to believe that learning causal representations has the potential to significantly improve the power of AI, especially on tasks where performance lags far behind human level geirhos2020shortcut.
Despite such promise, a crucial challenge in causal representation learning is the identifiability of the data generating process; in other words, given the data that we observe, can we uniquely identify the underlying causal model. It has been shown that given observational data (i.e., i.i.d. data generated from a single environment), the model is already non-identifiable in strictly simpler settings where the latent variables are known to be independent locatello2019challenging,locatello2020sober, or where there is no mixing function and one directly observes the latent variables silva2006learning. A natural question that arises is what types of data do we need to acquire to make identification possible.
One line of works assumes access to counterfactual data locatello2020weakly,von2021self,brehmer2022weakly, where some form of weak supervision is typically required. A common assumption here is that one observes data in pairs, where each pair of data is related via sharing part of the latent representation. However, such data is hard to acquire since it requires direct control on the latent representation.
Another line of works ahuja2023interventional,von2023nonparametric,buchholz2023learning,varici2023general instead considers an interventional setting, where the learner observes data generated from multiple different environments. This is arguably a much more realistic setup and reflects common practices in robotics lippe2023biscuit and genomics lopez2023learning,tejada2023causal applications. However, a vast majority of identifiability guarantees assume that each environment corresponds to single-node, hard interventions, which is defined as interventions that isolate a single latent variable from its causal parents. Again, this is quite a restrictive assumption because of two reasons. First, since the latent variables are unknown and need to be learned from data, it is unclear how to perform interventions that only affect one variable. Second, even if one can perform single-node interventions, it may not be feasible to artificially remove causal effects in the data generating processes. This issue is ubiquitous in real-world applications as pointed out in campbell2007interventionist,eberhardt2014direct,eronen2020causal. Motivated by these challenges, we instead consider the following two settings:
We make the following contributions:
We consider the standard setup of causal representation learning from multiple environments $E\in\mathfrak{E}$. Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be the ground-truth causal graph which is directed and acylic (DAG), where $\mathcal{V}=[d]$ and $\mathcal{E}$ describes the causal relationship between different nodes. Each node corresponds to a latent variable ${\bm{z}}_i\in\mathbb{R}$.
For any node $i$, we let $\mathrm{pa}_{\mathcal{G}}(i)$, $\mathrm{ch}_{\mathcal{G}}(i)$, $\mathrm{ans}_{\mathcal{G}}(i)$ and $\mathrm{nd}_{\mathcal{G}}(i)$ to be the set of all parents, children, ancestors and non-descendants of $i$ in $\mathcal{G}$ respectively. We also define $\overline{\mathrm{pa}}_{\mathcal{G}}(i)=\mathrm{pa}_{\mathcal{G}}(i)\cup\{i\}$ and similarly for $\overline{\mathrm{ch}}_{\mathcal{G}}(i),\overline{\mathrm{ans}}_{\mathcal{G}}(i)$ and $\overline{\mathrm{nd}}_{\mathcal{G}}(i)$. Assuming that all probability distributions have continuous densities, the joint density of the latent variables ${\bm{z}}$ can then be written as
where $p_i^E$ is the (unknown) latent generating distribution from environment $E$ at node $i$. Here for a given vector ${\bm{v}}$, we write ${\bm{v}}_i={\bm{e}}_i^\top{\bm{v}}$, and let ${\bm{v}}_S = \left({\bm{v}}_i: i\in S\right)\in\mathbb{R}^{|S|}$.
The causal graph model with density given by (ref) necessarily enjoys the following property:
The latent variables ${\bm{z}}$ are unknown to the learner. Instead, the learner has access to observations ${\bm{x}}\in\mathbb{R}^n$ ($n\geqslant d$) from all environments $E\in\mathfrak{E}$ that are related to the latent ${\bm{z}}$ via an injective mixing function ${\bm{g}}$:
The main assumption here that the mixing function is the same across all environments:
In causal representation learning, the goal of the learner is to 1) recover the inverse of the mixing function ${\bm{h}} = {\bm{g}}^{-1}$ (often called the unmixing function) which allows recovering the latent variables given any observations, and, 2) recover the underlying causal graph $\mathcal{G}$. In the remaining part of this paper, we refer to $({\bm{h}},\mathcal{G})$ as the causal model to be learned. Obviously, there would be some ambiguities in learning $({\bm{h}},\mathcal{G})$. For example, choosing a different permutation of the nodes in the causal graph would lead to a different model, and so does element-wise transformations on each component ${\bm{h}}_i$ of ${\bm{h}}$.
A line of recent works show that the ground-truth model can be identified up to these ambiguities in various settings, assuming access to single-node hard interventions seigal2022linear,von2023nonparametric,varici2023general. On the other hand, some weaker notions of identifiability have also been proposed and studied in the literature seigal2022linear,varici2023score,liang2023causal for single-node soft interventions. Here, we provide a generic definition of single-node soft interventions that we will rely on in this paper.
We note that soft interventions are very different from hard interventions, since they do not remove causal relationships between latent variables. The goal of this paper is to address the following question:
One may expect that identifiability with soft interventions is not much different from hard interventions, since soft interventions can approximate hard interventions with arbitrary accuracy. However, we will show that this is not the case. At a high level, hard intervention is more powerful than soft intervention because it is capable of isolating a latent variable from its direct cause while soft interventions is not, so soft interventions can sometimes fail to identify the true causal relationship from a mixture of causal effects.
To quantify what kind of ambiguities may arise, we can define the surrounding set for each node in a causal graph $\mathcal{G}$ as follows:
In other words, the effect of $j$ on its child set $\mathrm{ch}_{\mathcal{G}}(j)$ is dominated by the effect of $i$. Intuitively, if there exists some $i\in\mathrm{sur}_{\mathcal{G}}(j)$, then ambiguities may arise for the causal variable at node $j$, since any effect of $j$ on any of its child $k$ can also be interpreted as an effect of $i$. In (ref) we discuss a three-node example to further illustrate such ambiguities.
(ref) naturally induces the following relationship between causal models:
In other words, $\sim_{\mathrm{sur}}$ requires that the causal graph to be exactly the same up to some permutation of nodes, but allows each latent variable ${\bm{v}}_i$ to be entangled with ${\bm{z}}_{\mathrm{sur}_{\mathcal{G}}(i)}$. Although not obvious from definition, one can actually check that $\sim_{\mathrm{sur}}$ defines an equivalence relation (see (ref)). Moreover, we will show later that $\sim_{\mathrm{sur}}$ is in general the best that we can hope for in our problem setting.
In this section, we consider learning causal models from general environments. Specifically, we assume that the environments $E_k, k\in[K]$ share the same causal graph, but the dependencies between connected nodes (latent variables) are completely unknown, and, in contrast with existing literature on single-node interventions, we impose no similarity constraints on the environments. We begin our investigation of identifiability in this setting in the context of linear causal models with a linear mixing function.
Formally, we assume the following generative model in $K$ distinct environments $\mathfrak{E}=\left\{E_k: k\in[K]\right\}$ with data generating process
where the matrix ${\bm{A}}_k$ satisfies $({\bm{A}}_k)_{ij}\neq 0$ if and only if $j\to i$ in $\mathcal{G}$. We refer to $({\bm{A}}_k,\bm{\Omega}_k)$ as the weight matrices of latent variables ${\bm{z}}$ in the environment $E_k$. It is easy to see that (ref) in our general setup translates into the following assumption:
Let ${\bm{B}}_k = \bm{\Omega}_k^{-\frac{1}{2}}({\bm{I}}-{\bm{A}}_k), k\in[K]$, then we have $\epsilon = {\bm{B}}_k{\bm{z}} = {\bm{B}}_k{\bm{H}}{\bm{x}}$. Since in the linear case, there is an easy to see one-to-one correspondence between the matrix ${\bm{H}}$ and the un-mixing function ${\bm{x}}\mapsto{\bm{H}}{\bm{x}}$, we abuse the notation and write $({\bm{H}},\mathcal{G})$ to represent the model instead of $({\bm{h}},\mathcal{G})$. Using ${\bm{h}}_i$ to denote the $i$-th row of ${\bm{H}}$, the following lemma translates (ref) the the linear setting:
We also need to make the following assumption on noise.
The non-gaussianity of the noise vectors is a typical assumption in causal discovery within linear models comon1994independent,silva2006learning and is always assumed in the LinGAM setting shimizu2006linear. The assumption that all components have a different distribution is not so standard, but is quite natural in real-world scenarios.
For each node $i\in[d]$ of $\mathcal{G}$, we use ${\bm{w}}_{k}(i)$ to be the weight vector of environment $E_k$ at node $i$, i.e., ${\bm{w}}_k(i) = \left(({\bm{A}}_k)_{ij}:j\in\mathrm{pa}_{\mathcal{G}}(i)\right) \in \mathbb{R}^{\left\vert\mathrm{pa}_{\mathcal{G}}(i)\right\vert}$. In other words, the structural equation for node $i$ in environment $k$ is of the form:
To obtain our identifiability result, the main assumption we need to make is the non-degeneracy of the weights at each node:
This assumption is quite mild since it only requires the weight vectors to be in general positions, and it holds with probability $1$ if the weights at each node are sampled from continuous distributions. Moreover, as shown in (ref), it is equivalent to the following assumption.
In the following, we state our main result in this section, which shows that $K=d$ non-degenerate environments suffices for the model to be identifiable up to $\sim_{\mathrm{sur}}$.
The proof of (ref) is given in (ref). In the next section, we will introduce an algorithm, LiNGCReL, that provably recovers the ground-truth up to $\sim_{\mathrm{sur}}$.
To the best of our knowledge, this is the first identifiability guarantee in the literature for causal representation learning from general environments. Remarkably, while the fact that existing works seigal2022linear,zhang2023identifiability focus on single-node interventions seem to suggest that learning from diverse environments is hard, our result indicates that such diversity is actually helpful. Specifically, we show that in the worst case, $\Theta(d^2)$ interventions are required for identifying the ground-truth model under $\sim_{\mathrm{sur}}$:
A formal version and the proof of (ref) can be found in (ref). On the other hand, by having $d$ single-node interventions per node, (ref) can be satisfied as long as the weights are in general positions, so in this case we have $({\bm{H}},\mathcal{G})\sim_{\mathrm{sur}}(\hat{{\bm{H}}},\hat{\mathcal{G}})$ by (ref). Therefore, (ref) together imply that $\Theta(d^2)$ single-node interventions are necessary and sufficient for identification up to $\sim_{\mathrm{sur}}$.
Given that (ref) only guarantees identification up to $\sim_{\mathrm{sur}}$ that is strictly weaker than full identification, one might naturally ask whether (ref) can be further improved. Our last theorem in this section indicates that $\sim_{\mathrm{sur}}$ is indeed the best one can hope for in our setting, even assuming access to single node, soft intervention.
In this section, we describe Linear Non-Gaussian Causal Representation Learning (LiNGCReL), an algorithm that provably recovers the underlying causal graph and latent variables up to $\sim_{\mathrm{sur}}$ in the infinite-sample limit. At this point, it is instructive to recall the celebrated LiNGAM algorithm shimizu2006linear for linear causal graph discovery. Different from their setting, we only observe some unknown linear mixture of the latent variables. Hence, running linear ICA as in LiNGAM only gives us ${\bm{M}}_k={\bm{B}}_k{\bm{H}}$ rather than the weight matrix ${\bm{B}}_k$ itself.
The key idea in our approach is an effect cancellation scheme that allows us to determine the \enquote{remaining degree of freedom} (RDF) of any node (a.k.a. latent variable) given any subset of its ancestors. This scheme allows us to not only find a topological order of the nodes, but also figure out direct causes by tracking the changes of the RDF. In the following, we present the main steps of LiNGCReL in more details.
Suppose that we are given samples of observations ${\bm{X}}^{(k)}=\left\{{\bm{x}}_i^{(k)}\right\}_{i=1}^N, k\in[K]$ where ${\bm{x}}_i^{(k)}$ is the $i$-th sample from the $k$-th environment.
Step 1. Recover the matrices ${\bm{M}}_k={\bm{B}}_k{\bm{H}}$ Since $\epsilon = {\bm{B}}_k{\bm{z}} = {\bm{B}}_k{\bm{H}}{\bm{x}}$ in the $k$-th environment, so we can use any identification algorithm for linear ICA to recover the matrix ${\bm{M}}_k$. Then we properly rearrange the rows of ${\bm{M}}_k$ so that all ${\bm{M}}_k{\bm{x}}, k=1,2,\cdots,K$ correspond to the same permutation of noise variables. This step is quite standard and details can be found in (ref).
Step 2. Causal representation learning based on ${\bm{M}}_k$ Now we have obtained ${\bm{M}}_k = {\bm{B}}_k{\bm{H}}$, but the unmixing matrix ${\bm{H}}$ is still unknown. We propose (ref) to learn ${\bm{H}}$ and the causal graph $\mathcal{G}$. The main part of (ref) contains a loop that maintains a node set $S$ which, we will show later, is ancestral, i.e., $i\in S \Rightarrow \mathrm{ans}_{\mathcal{G}}(i)\subseteq S$. In each round the algorithm finds a new node $i\notin S$ such that $\mathrm{ans}_{\mathcal{G}}(i)\subseteq S$, and a subroutine Identify-Parents ((ref)) is used to find all parents of $i$. After that, we append $i$ into $S$ and continue until $S$ contains all nodes in $\mathcal{G}$. Finally, the rows of the mixing matrix ${\bm{H}}$ is obtained by intersections of properly-chosen row spaces of ${\bm{M}}_k$.
Both (ref) and (ref) include a crucial step, which we call it orthogonal projection, as described in (ref). At a high level, it helps determine the minimal RDF for ${\bm{z}}_i$ after fixing the latent variables ${\bm{z}}_S$, and this exactly corresponds to the number of parents of ${\bm{z}}_i$ that are not in ${\bm{z}}_S$. We provide a simple example in (ref) to illustrate why this approach works.
The following result states that (ref) can recover the ground-truth causal model up to $\sim_{\mathrm{sur}}$:
The full proof of (ref) is given in (ref). It crucially relies on the following two propositions that reveal how (ref) and the subroutine (ref) work.
In this section, we present our experimental setup and results for LiNGCReL. Note that LiNGCReL as described in the previous section only works in the population regime. When the number of samples is limited, two main challenges in implementing LiNGCReL are to accurately compute the dimension of a subspace (line 6 of (ref) and line 8 of (ref)), and to find a vector in the intersection of multiple subspaces (line 20, (ref)). Due to space limit, the implementation details are described in (ref).
Experimental setup. We generate the independent noise variables from generalized Gaussian distributions $p_{\beta}(x)\propto \exp\left(-\left\vertx\right\vert^{\beta}\right)$ with parameters $\beta_k = 0.2 k^2, k=1,2,\cdots,d$, multiplied by normalization constants to make their variances equal to $1$. The ground-truth causal graph is generated by first fixing a total order of the vertices, say $1,2,\cdots,d$, then add directed edges $i\to j (i<j)$ according to i.i.d. Bernoulli($p$) distributions, where $p\in(0,1)$. The non-zero entries of matrices ${\bm{B}}_k$ and ${\bm{H}}$ are all generated independently from Gaussian distributions. For simplicity, we focus on the case $n=d$ since recovery of the latent graphs only requires information from $d$ components of ${\bm{x}}$.
Metrics of estimation error. Since causal representation learning seeks to learn both the causal graphs and the latent variables, for each output of our algorithm we first check if it exactly recovers the ground-truth causal graph. Then, recall that the latent variables and the observations are related by ${\bm{z}} = {\bm{H}}{\bm{x}}$, given any output unmixing matrix $\hat{{\bm{H}}}$ from (ref), we define the relative estimation error $\Delta_i$ for ${\bm{z}}_i$ as the solution of the following optimization problem:
where signed permutation is allowed here since the noise distribution in our experiments is symmetric and the order of latent variables ${\bm{z}}_i, i=1,2,\cdots,d$ does not matter. We refer to the errors $\Delta_i$ defined in (ref) as the SNA error. The SNA error measures how much of the row $\hat{\hat{{\bm{h}}}}_i$ that we learn is contained in the span of the ground-truth rows ${\bm{h}}_j, j\in\overline{\mathrm{sur}_{\mathcal{G}}}(i)$. Indeed, recall that given any observation ${\bm{x}}$, the ground-truth latent variable is ${\bm{z}} = {\bm{H}}{\bm{x}}$ while our algorithm outputs $\hat{{\bm{v}}}_i = \hat{\hat{{\bm{h}}}}_i^\top{\bm{x}}$, so the SNA error essentially captures whether the recovered latent variable is close to some linear mixture of latent variables in the effect-dominating set of $i$. When the SNA error is zero for some node $i$, we know that the recovered latent variable at node $i$ is exactly a linear mixture of the ground-truth latent variables in $\overline{\mathrm{sur}_{\mathcal{G}}}(i)$, according to (ref).
We also define the true error for estimating each latent variable. Formally, let $\hat{\hat{{\bm{H}}}}$ be the unmixing matrix that corresponds to the solution of (ref), then we define the true estimation error $\tilde{\Delta}_i$ of ${\bm{z}}_i$ as
Results. We randomly sample $100$ causal models with size $d=5$, $30$ causal models with size $d=8$ ad $30$ causal models of size $d=10$. In light of (ref), for each $d\in\{5,8,10\}$, we sample data from $K=d$ randomly chosen environments; for $d=5$ we also consider $K=20$ to study how different choices of $K$ can affect the result. We run LiNGCReL for each model with different sample sizes, compute the SNA error and true error of the obtained solution from (ref) respectively for each latent variable, and check whether the ground-truth causal graph is exactly recovered.
(ref) shows how the average SNA error (over all latent variables) and the accuracy of graph recovery changes when sample size grows. We can see LiNGCReL successfully recovers about $80\%$ of all models within each category, and the median of the average SNA error is smaller than $1\%$. Moreover, by comparing (ref) with (ref), one can observe that if we fix the total number of samples but choose a larger $K$ (i.e., fewer samples per environment), LiNGCReL can still achieve the same level of performance compared with the choice $K=d$. Intuitively, this is because $K \gg d$ vectors sampled from an $r (r\leqslant d)$ dimensional subspace are unlikely to approximately lie in an ($r-1$)-dimensional subspace, so that the calculation of line 6 of (ref) and line 8 of (ref) can be more accurate. We leave a better and quantitative understanding of the trade-off between $d$ and $K$ to future work.
SNA error v.s. true error. To understand the implication of our theory, we dive deeper by looking into the learning outcome of LiNGCReL on a specific model, of which the causal graph is shown in (ref).
In (ref), we list the surrounding set of each node and the corresponding SNA error and true error. We can see that if $\mathrm{sur}_{\mathcal{G}}(i)=\emptyset$, the two errors equal and both are small, but if $\mathrm{sur}_{\mathcal{G}}(i)\neq\emptyset$, the true error is much larger than the SNA error. This indicates that LiNGCReL indeed learns the ground-truth model up to $\sim_{\mathrm{sur}}$, as (ref) predicts.
While (ref) guarantees identifiability with general environments, it only applies to linear causal models. In this section, we show that if we have access to single-node soft interventions, then we can identify general non-parametric causal models up to $\sim_{\mathrm{sur}}$. To obtain our identifiability result, we also require that the environments are non-degenerate in the following sense:
The following lemma shows how (ref) is related to (ref) in the linear setting:
Now we are ready to state our main result in this section:
Previous works on the identifiability of non-parametric causal models typically require that all the joint distributions are supported on the whole space $\mathbb{R}^d$ von2023nonparametric,liang2023causal,varici2023general. In contrast, we only assume that the densities have common and unknown support across all interventions.
(ref) can be regarded as a soft-intervention version of von2023nonparametric, which assumes access to hard interventions and only need two paired interventions per node. While they are able to show full identifiability, we show in the following that identifiability up to $\sim_{\mathrm{sur}}$ is the best we can hope for with soft interventions.
This paper studies the limit of learning identifiable causal representations using data from multiple environments. When hard interventions are not available, we provide theory and algorithm for identification up to SNA, and also show that SNA is an intrinsic ambiguity in our setting.
It is interesting to further investigate the setting where we do not assume that the causal model is linear. Moreover, it is important to understand the concrete form of available interventions in real-world applications. For instance, it is suggested that for single-cell genomics, the intervention is sometimes a "mixture" of hard and soft interventions, and sometimes can even reverse the direction of an edge tejada2023causal. Modelling such more complicated interventions appears to be crucial to reveal the underlying causal mechanisms in real-world problems.
This paper presents work whose goal is to advance the field of Machine Learning and in particular the sub-field Causal Representation Learning. There are many potential societal consequences of our work, especially as it pertains to building more reliable machine learning models, none which we feel must be specifically highlighted here.
\printbibliography