$\operatorname{SE}(\Delta\hat{q}):=\frac{1}{r}\sqrt{\sum_{i=1}^{r}\left(\Delta\hat{q}_{i}-\overline{\Delta\hat{q}}\right)}.$

Figure 7: Example plots aggregating max-min gaps across multiple settings.
Left is ID, right is nonID. Bottom plots are zoomed versions of top plots.
Dashed lines represent choices of $\tau$ at 0.01 (red), 0.03 (green) and 0.05
(blue).

Finally, we check

$\overline{\Delta\hat{q}}+1.65\operatorname{SE}(\Delta\hat{q})<\tau.$

If this quantity holds, we reject the null hypothesis with 95% confidence, and
we return the result that the query is identifiable. If not, we fail to reject
the null hypothesis and we return the result that the query is not
identifiable.

Figure 8: NCM estimation results for ID graphs when setting the number of
observed samples to 1000000 and the number of dimensions for each multi-
dimensional binary covariate (any variable which is not $X$ or $Y$) to 20. The
graphs displayed in the plot correspond to the same graphs as a, b, c, d in
Fig. 4. Plot in log scale.

We showed the results of three different values of $\tau$ ($0.01,0.03,0.05$)
in Fig. 4 (main paper). Here, we try to understand how $\tau$ can be
determined more systematically by running a preliminary round of
identification experiments and observing the percentiles of the resulting
gaps; see Fig. 7. Note that most gaps in the ID case fall below the $0.03$
line by the end of training process, while most gaps in the nonID case stay
above it. This can be used to motivate a particular choice of $\tau$.

###  B.5 Additional Results

To demonstrate the potential of NCMs to scale to larger settings, we provide
additional estimation results on higher dimensional data in Fig. 8. We use the
same canonical SCM architecture but probabilistically map the value of each
binary variable which is not $X$ or $Y$ to a 20-dimensional binary vector,
such that there exists a deterministic mapping from each covariate’s
20-dimensional binary vectors to the original binary value (that is, the
original binary value is recoverable from the 20-dimensional mapped vector).
This preserves ATE and TV while increasing the difficulty of the NCM’s
optimization problem by testing the NCM’s ability to learn in high-dimensional
spaces. In this more challenging high-dimensional setting, the NCM maintains
superior or equal performance when compared to WERM.

###  B.6 Other Possible Architectures

In Sec. 4, we provided one possible architecture of the NCM (Eq. 2), which
produced the empirical results discussed in Sec. 5. These results show that,
in principle, training a proxy model can be used to solve the identification
and estimation problems in practice.

Still, other architectures may be more suitable and perform more efficiently
than the one shown in Eq. 2 in larger, more involved domains. In such
settings, it may be challenging to match the distributions well enough to
reach the correct identification result, or to lower the error on estimating
the query of interest. While Corol. 4 guarantees the correct result with
perfect optimization, this is rarely achieved in practice. It’s certainly not
fully understood how optimization errors on the learning of $P(\mathbf{V})$
will affect the performance of identification/estimation of Layer 2
quantities.

Naturally, the framework developed here to support proxy SCMs is not limited
to the architecture in Eq. 2. For instance, as discussed in Footnote 10, there
are alternative methods of learning $P(\mathbf{V})$ such as by minimizing
divergences, performing variational inference, generative adversarial
optimization, to cite a few prominent choices. Some of these methods may be
more scalable and robust to optimization errors. See Appendix D.1 for a
discussion on how the theory generalizes for other architectures.

Further, we note that if $\mathbf{V}$ comes from continuous domains, there are
many ways the architecture of the NCM could be augmented accordingly. As
discussed in Footnote 11, one could replace the Gumbel-max trick in the
architecture in Eq. 2 with a model that directly computes a probability
density given a data point. Some of the alternative architectures mentioned
above may work as well.

We believe this leads to an exciting research agenda that is to understand the
tradeoffs involved in the choice of the architectures and how to properly
optimize NCMs for specific applications.

##  Appendix C Examples and Further Discussion

In this section, we complement the discussion provided in the main paper
through examples. Specifically, in Sec. C.1, we discuss what expressiveness
means and provide examples to show why it’s insufficient to perform cross-
layer inferences. In Sec. C.2, we provide an intuitive discussion on why
causal diagrams are able to perform cross-layer inferences and basic examples
illustrating the structural constraints encoded in such models, which can be
seen as an inductive bias as discussed in the body of the paper. In Sec. C.3,
we exemplify how this inductive bias can be added to NCMs such that they are
capable of solving ID instances. In Sec. C.4, we discuss possible reasons why
one would prefer to perform ID through neural computation instead the
machinery of the do-calculus.

###  C.1 Expressiveness Examples

In this section, we try to clarify through examples the notion of
expressiveness, as shown in Thm. 1, and discuss the reasons it alone is not
sufficient for performing cross-layer inferences.

######  Example 1.

Consider a study on the effects of diet ($D$) on blood pressure ($B$),
inspired by studies such as [2]. $D$ and $B$ are binary variables such that
$D=1$ represents a high-vegetable diet, and $B=1$ represents high blood
pressure. Suppose the true relationship between $B$ and $D$ is modeled by the
SCM $\mathcal{M}^{*}=\\{\mathbf{U},\mathbf{V},\mathcal{F},P(\mathbf{U})\\}$,
where

$\mathcal{M}^{*}:=\begin{cases}\mathbf{U}&:=\\{U_{D},U_{DB},U_{B1},U_{B2}\\},\text{
all binary}\\\ \mathbf{V}&:=\\{D,B\\}\\\
\mathcal{F}&:=\begin{cases}f_{D}(U_{D},U_{DB})&=\neg U_{D}\wedge\neg U_{DB}\\\
f_{B}(D,U_{B1},U_{B2})&=((\neg D\oplus U_{B1})\vee U_{DB})\oplus
U_{B2}\end{cases}\\\
P(\mathbf{U})&:=\begin{cases}P(U_{D}=1)=P(U_{DB}=1)=P(U_{B1}=1)=P(U_{B2}=1)=\frac{1}{4}\\\
\text{ all }U\in\mathbf{U}\text{ are independent}\end{cases}\end{cases}$ (30)

The set of exogenous variables $\mathbf{U}$ affects the set of endogenous
variables $\mathbf{V}$. For example, $U_{DB}$ is an unobserved confounding
variable that affects both diet and blood pressure (ethnicity, for example),
while the remaining variables in $\mathbf{U}$ represent other factors
unaccounted for in the study. $\mathcal{F}$ describes the relationship between
the variables in $\mathbf{V}$ and $\mathbf{U}$, and $P(\mathbf{U})$ describes
the distribution of $\mathbf{U}$.

$U_{D}$ | $U_{DB}$ | $U_{B1}$ | $U_{B2}$ | $D$ | $B$ | $P(\mathbf{U})$
---|---|---|---|---|---|---
0 | 0 | 0 | 0 | 1 | $\neg D$ | $p_{0}=81/256$
0 | 0 | 0 | 1 | 1 | $D$ | $p_{1}=27/256$
0 | 0 | 1 | 0 | 1 | $D$ | $p_{2}=27/256$
0 | 0 | 1 | 1 | 1 | $\neg D$ | $p_{3}=9/256$
0 | 1 | 0 | 0 | 0 | 1 | $p_{4}=27/256$
0 | 1 | 0 | 1 | 0 | 0 | $p_{5}=9/256$
0 | 1 | 1 | 0 | 0 | 1 | $p_{6}=9/256$
0 | 1 | 1 | 1 | 0 | 0 | $p_{7}=3/256$
1 | 0 | 0 | 0 | 0 | $\neg D$ | $p_{8}=27/256$
1 | 0 | 0 | 1 | 0 | $D$ | $p_{9}=9/256$
1 | 0 | 1 | 0 | 0 | $D$ | $p_{10}=9/256$
1 | 0 | 1 | 1 | 0 | $\neg D$ | $p_{11}=3/256$
1 | 1 | 0 | 0 | 0 | 1 | $p_{12}=9/256$
1 | 1 | 0 | 1 | 0 | 0 | $p_{13}=3/256$
1 | 1 | 1 | 0 | 0 | 1 | $p_{14}=3/256$
1 | 1 | 1 | 1 | 0 | 0 | $p_{15}=1/256$
Table 1: Truth table showing induced values of $\mathcal{M}^{*}$ for Example
1. Probabilites in $P(\mathbf{U})$ are labeled from $p_{0}$ to $p_{15}$ for
convenience.

This SCM $\mathcal{M}^{*}$ induces three collections of distributions
corresponding to the layers of PCH with respect to $\mathbf{V}$. These can be
summarized in Table 1. For example, a layer 1 quantity such as $P(B=1\mid
D=1)$, the probability of someone having high blood pressure given a high-
vegetable diet, can be computed as

$\displaystyle P(B=1\mid D=1)$ $\displaystyle=$
$\displaystyle\frac{P(D=1,B=1)}{P(D=1)}$ (31) $\displaystyle=$
$\displaystyle\frac{p_{1}+p_{2}}{p_{0}+p_{1}+p_{2}+p_{3}}=\frac{54}{144}=0.375.$
(32)

A layer 2 quantity such as $P(B=1\mid do(D=1))$, the probability from
$\mathcal{M}^{*}$ of someone having high blood pressure when intervened on a
high-vegetable diet, can be computed as

$\displaystyle P(B=1\mid do(D=1))$ $\displaystyle=$ $\displaystyle
p_{1}+p_{2}+p_{4}+p_{6}+p_{9}+p_{10}+p_{12}+p_{14}$ (33) $\displaystyle=$
$\displaystyle\frac{120}{256}=0.46875.$ (34)

Layer 3 quantities can also be computed, for example, $P(B_{D=1}=1\mid
D=0,B=1)$. Given that an individual has high blood pressure and a low-
vegetable diet, this quantity represents the probability that they would have
high-blood pressure had they instead eaten a high-vegetable diet. This can be
computed as

$\displaystyle P(B_{D=1}=1\mid D=0,B=1)$
$\displaystyle=\frac{P(B_{D=1}=1,D=0,B=1)}{P(D=0,B=1)}=\frac{p_{4}+p_{6}+p_{12}+p_{14}}{p_{4}+p_{6}+p_{8}+p_{11}+p_{12}+p_{14}}=\frac{48}{78}\approx
0.6154.$ (35)

Following the construction in the proof for Thm. 1, we will show the (somewhat
tedious) construction of the corresponding NCM that induces the same
distributions. First, we build a simple canonical SCM from Def. 10 to match
the functionality in $\mathcal{M}^{*}$. We build
$\mathcal{M}_{\operatorname{\textsf{CM}}}=\langle\mathbf{U}_{\operatorname{\textsf{CM}}},\mathbf{V},\mathcal{F}_{\operatorname{\textsf{CM}}},P(\mathbf{U}_{\operatorname{\textsf{CM}}})$
such that

$\mathcal{M}_{\operatorname{\textsf{CM}}}:=\begin{cases}\mathbf{U}_{\operatorname{\textsf{CM}}}&:=\\{R_{D},R_{B}\\},\mathcal{D}_{R_{D}}=\\{0,1\\},\mathcal{D}_{R_{B}}=\\{0,1,2,3\\}\\\
\mathbf{V}&:=\\{D,B\\}\\\
\mathcal{F}_{\operatorname{\textsf{CM}}}&:=\begin{cases}f^{\operatorname{\textsf{CM}}}_{D}(R_{D})&=R_{D}\\\
f^{\operatorname{\textsf{CM}}}_{B}(D,R_{B})&=\begin{cases}0&\text{ if
}R_{B}=0\\\ D&\text{ if }R_{B}=1\\\ \neg D&\text{ if }R_{B}=2\\\ 1&\text{ if
}R_{B}=3\end{cases}\end{cases}\end{cases}$ (36)

Looking at Table 1, we mimic the same distributions of $\mathcal{M}^{*}$ in
$\mathcal{M}_{\operatorname{\textsf{CM}}}$ by choosing

$P(\mathbf{U}_{\operatorname{\textsf{CM}}})=P(R_{D},R_{B})=\begin{cases}p_{5}+p_{7}+p_{13}+p_{15}=16/256&R_{D}=0,R_{B}=0\\\
p_{9}+p_{10}=18/256&R_{D}=0,R_{B}=1\\\ p_{8}+p_{11}=30/256&R_{D}=0,R_{B}=2\\\
p_{4}+p_{6}+p_{12}+p_{14}=48/256&R_{D}=0,R_{B}=3\\\
p_{1}+p_{2}=54/256&R_{D}=1,R_{B}=1\\\ p_{0}+p_{3}=90/256&R_{D}=1,R_{B}=2\\\
0&\text{otherwise.}\end{cases}$ (37)

We state the following useful neural network functions defined in the proof of
Thm. 1:

  * •

$\hat{f}_{\operatorname{\textsc{AND}}}(x_{1},\dots,x_{n})=\sigma\left(\sum_{i=1}^{n}x_{i}-n\right)$

  * •

$\hat{f}_{\operatorname{\textsc{OR}}}(x_{1},\dots,x_{n})=\sigma\left(\sum_{i=1}^{n}x_{i}-1\right)$

  * •

$\hat{f}_{\operatorname{\textsc{NOT}}}(x)=\sigma\left(-x\right)$

  * •

$\hat{f}_{\geq z}(x)=\sigma\left(x-z\right)$

For this appendix, $\sigma$ will be the binary step activation function.
$\hat{f}_{\operatorname{\textsc{AND}}}$,
$\hat{f}_{\operatorname{\textsc{OR}}}$, and
$\hat{f}_{\operatorname{\textsc{NOT}}}$ compute the bitwise AND, OR, and NOT
of the inputs (if binary) respectively. $\hat{f}_{\geq z}$ will output 1 if
its input is greater than or equal to $z$ and will output 0 otherwise.

We begin the construction of our NCM
$\widehat{M}=\langle\widehat{\mathbf{U}},\mathbf{V},\widehat{\mathcal{F}},P(\widehat{\mathbf{U}})$
as follows:

$\widehat{M}:=\begin{cases}\widehat{\mathbf{U}}&:=\\{\widehat{U}\\},\mathcal{D}_{\widehat{U}}=[0,1]\\\
\mathbf{V}&:=\\{D,B\\}\\\
\widehat{\mathcal{F}}&:=\begin{cases}\hat{f}_{D}(\widehat{U})&=\text{ ?}\\\
\hat{f}_{B}(D,\widehat{U})&=\text{ ?}\end{cases}\\\
P(\widehat{\mathbf{U}})&:=P(\widehat{U})\sim\operatorname{Unif}(0,1)\end{cases}$

We must then construct the neural networks in $\widehat{\mathcal{F}}$. With
the goal of reproducing the behavior of
$\mathcal{M}_{\operatorname{\textsf{CM}}}$, we first start by converting a
uniform distribution into $P(R_{D},R_{B})$. We can accomplish this by dividing
the $[0,1]$ interval into chunks for each individual value of
$(R_{D}=r_{D},R_{B}=r_{B})$ with the size of $P(R_{D}=r_{D},R_{B}=r_{B})$. For
instance, considering values of $P(R_{D},R_{B})$ in the order in Eq. 37, the
interval $[0,16/256)$ would correspond to $(R_{D}=0,R_{B}=0)$, the interval
$[16/256,34/256)$ would correspond to $(R_{D}=0,R_{B}=1)$, and so on. In this
case, $\widehat{U}$ would be broken into six intervals corresponding to the 6
cases of Eq. 37: $[0,16/256)$, $[16/256,34/256)$, $[34/256,64/256)$,
$[64/256,112/256)$, $[112/256,166/256)$, and $[166/256,1)$. For the sake of
convenience, we will label these $I_{1}$ to $I_{6}$ respectively

We can check if $U$ is contained within an interval like $[16/256,34/256)$
with the following neural network function:

$\displaystyle\hat{f}_{I_{2}}=\hat{f}_{[16/256,34/256)}(u)=\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{\geq
16/256}(u),\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
34/256}(u)\right)\right)$ (38)

Observe that $f_{I_{1}}$ to $f_{I_{6}}$ provide a one-hot encoding of the
location of $\widehat{U}$. Mapping this encoding to $R_{D}$ and $R_{B}$ is
simply multiplying the corresponding values of $r_{D}$ and $r_{B}$ as weights
to the encoding:

$\displaystyle\hat{f}_{R_{D}}(u)$
$\displaystyle=0\cdot\hat{f}_{I_{1}}(u)+0\cdot\hat{f}_{I_{2}}(u)+0\cdot\hat{f}_{I_{3}}(u)+0\cdot\hat{f}_{I_{4}}(u)+1\cdot\hat{f}_{I_{5}}(u)+1\cdot\hat{f}_{I_{6}}(u)$
(39) $\displaystyle\hat{f}_{R_{B}}(u)$
$\displaystyle=0\cdot\hat{f}_{I_{1}}(u)+1\cdot\hat{f}_{I_{2}}(u)+2\cdot\hat{f}_{I_{3}}(u)+3\cdot\hat{f}_{I_{4}}(u)+1\cdot\hat{f}_{I_{5}}(u)+2\cdot\hat{f}_{I_{6}}(u)$
(40)

Note that $\hat{f}_{R_{D}}$ and $\hat{f}_{R_{B}}$ are indeed neural networks,
and this final layer does not contain an activation function.

Since $D=R_{D}$ in $\mathcal{M}_{\operatorname{\textsf{CM}}}$, we can already
construct

$\displaystyle\hat{f}_{D}(u)=\hat{f}_{R_{D}}(u).$ (41)

The function $\hat{f}_{B}$ is somewhat more involved since it must take $D$ as
an input. Since $R_{B}$ is not a binary variable, we first convert it to
binary form to simplify the mapping. We can accomplish this by using the same
strategy of obtaining the one-hot encoding of $R_{B}$. For instance, to check
if $R_{B}=1$, we can build the neural network function

$\displaystyle\hat{f}_{=1}(r_{B})=\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{\geq
1}(r_{B}),\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
2}(r_{B})\right)\right).$ (42)

The encoding is formed with $\hat{f}_{=0}$, $\hat{f}_{=1}$, $\hat{f}_{=2}$,
and $\hat{f}_{=3}$.

Using this, we can construct $\hat{f}_{B}(u)$ following the desired properties
in Eq. 36:

$\displaystyle\hat{f}_{B}(d,u)=\hat{f}_{\operatorname{\textsc{OR}}}\left(\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{=1}(r_{B}),d\right),\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{=2}(r_{B}),\hat{f}_{\operatorname{\textsc{NOT}}}(d)\right),\hat{f}_{=3}(r_{B})\right)$
(43)

where $r_{B}=\hat{f}_{R_{B}}(u)$.

$\widehat{U}$ | $D$ | $B$ | $P(\mathbf{U})$
---|---|---|---
$[0,16/256)$ | 0 | 0 | $q_{0}=16/256$
$[16/256,34/256)$ | 0 | $D$ | $q_{1}=18/256$
$[34/256,64/256)$ | 0 | $\neg D$ | $q_{2}=30/256$
$[64/256,112/256)$ | 0 | 1 | $q_{3}=48/256$
$[112/256,166/256)$ | 1 | $D$ | $q_{4}=54/256$
$[166/256,1)$ | 1 | $\neg D$ | $q_{5}=90/256$
Table 2: Truth table showing induced values of $\widehat{M}$ for Example 1.
Probabilites in $P(\mathbf{U})$ are labeled from $q_{0}$ to $q_{5}$ for
convenience.

With $\hat{f}_{D}$ and $\hat{f}_{B}$ defined, our construction of
$\widehat{M}$ is complete.

We can now verify that the distributions induced by $\widehat{M}$, as
represented in Table 2, matches the distributions induced by
$\mathcal{M}^{*}$. Consider the same three queries from Eqs. 31, 33, and 35:

$P^{\widehat{M}}(B=1\mid
D=1)=\frac{P^{\widehat{M}}(D=1,B=1)}{P^{\widehat{M}}(D=1)}=\frac{q_{4}}{q_{4}+q_{5}}=\frac{54}{144}=0.375$
$P^{\widehat{M}}(B=1\mid do(D=1))=q_{1}+q_{3}+q_{4}=\frac{120}{256}=0.46875$
$\displaystyle P^{\widehat{M}}(B_{D=1}=1\mid D=0,B=1)$
$\displaystyle=\frac{P^{\widehat{M}}(B_{D=1}=1,D=0,B=1)}{P^{\widehat{M}}(D=0,B=1)}=\frac{q_{3}}{q_{2}+q_{3}}=\frac{48}{78}\approx
0.6154$

This demonstrates that the NCM is indeed expressive enough to model this
setting on all three layers of PCH. While a more basic model might be fitted
to answer $L_{1}$ queries (such as $P(B=1\mid D=1)$), a well-parameterized NCM
is expressive enough to represent distributions on higher layers.
$\blacksquare$

Example 1 shows a scenario where the expressiveness of the NCM class allowed
us to fit an NCM instance that could completely match a complex SCM and answer
any question of interest. However, we also highlight that expressiveness alone
does not necessarily mean that the NCM can solve any causal problem.
Experimental data, data from layer 2, can be difficult to obtain in practice,
so it would be convenient if we could fit a model $\widehat{M}$ only on
observational data from layer 1, then deduce the same causal results using
$\widehat{M}$ as if it were the true SCM, $\mathcal{M}^{*}$. Unfortunately,
Corol. 1 states that this deduction typically cannot be made no matter the
expressiveness of the model. The next example will illustrate this point more
concretely.

######  Example 2.

$D$ | $B$ | $P(D,B)$
---|---|---
0 | 0 | $34/256$
0 | 1 | $78/256$
1 | 0 | $90/256$
1 | 1 | $54/256$
Table 3: Observational distribution $P(\mathbf{V})$ induced by
$\mathcal{M}^{*}$ from Example 1.

Consider the same study of the effects of diet on blood pressure in Example 1
in which the two variables are described by the SCM, $\mathcal{M}^{*}$, in Eq.
30.

While in the previous example we were able to construct NCM $\widehat{M}$
which matched $\mathcal{M}^{*}$’s behavior on all three layers of the PCH,
this was contingent on having access to the true SCM. This is unlikely to
happen in practice. Instead, we typically only have partial information from
the SCM. In many cases, we may only have observational data from layer 1. The
data in Table 3 exemplifies the aspect of $\mathcal{M}^{*}$ we may have access
to.

Naturally, we should construct an NCM such that matches on the given observed
dataset. The NCM $\widehat{M}$ from Example 1 will indeed induce the same
observational data $P(\mathbf{V})$, but there are several other ways we could
construct a model that fits such criterion. For illustration purposes,
consider four NCMs $\widehat{M}_{1}$, $\widehat{M}_{2}$, $\widehat{M}_{3}$,
and $\widehat{M}_{4}$ such that
$\widehat{M}_{i}=\langle\widehat{\mathbf{U}},\mathbf{V},\widehat{\mathcal{F}}_{i},P(\widehat{\mathbf{U}})\rangle$
is defined as follows:

$\begin{cases}\widehat{\mathbf{U}}&:=\\{\widehat{U}_{D},\widehat{U}_{B}\\},\mathcal{D}_{\widehat{U}_{D}}=\mathcal{D}_{\widehat{U}_{B}}=[0,1]\\\
\mathbf{V}&:=\\{D,B\\}\\\
\widehat{\mathcal{F}}_{i}&:=\\{\hat{f}_{D}^{i},\hat{f}_{B}^{i}\\}\\\
P(\widehat{\mathbf{U}})&:=\widehat{U}_{D},\widehat{U}_{B}\sim\operatorname{Unif}(0,1),\widehat{U}_{D}\mathbin{\mathchoice{\hbox
to0.0pt{\hbox{\set@color$\displaystyle\perp$}\hss}\kern 3.46875pt{}\kern
3.46875pt\hbox{\set@color$\displaystyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\textstyle\perp$}\hss}\kern 3.46875pt{}\kern
3.46875pt\hbox{\set@color$\textstyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\scriptstyle\perp$}\hss}\kern 2.36812pt{}\kern
2.36812pt\hbox{\set@color$\scriptstyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\scriptscriptstyle\perp$}\hss}\kern 1.63437pt{}\kern
1.63437pt\hbox{\set@color$\scriptscriptstyle\perp$}}}\widehat{U}_{B}\end{cases}$

We use two variables in $\widehat{\mathbf{U}}$ with the intent of simplifying
some of the expressions, but it is feasible to construct NCMs with the same
behavior using one uniform random variable, similar to Example 1.

Concretely, we construct $\widehat{\mathcal{F}}_{1}$ such that
$\widehat{M}_{1}$ has no unobserved confounding,

$\widehat{\mathcal{F}}_{1}:=\begin{cases}\hat{f}^{1}_{D}(u_{d})&=\begin{cases}1&u_{d}\geq\frac{112}{256}\\\
0&\text{otherwise}\end{cases}\\\
\hat{f}^{1}_{B}(d,u_{b})&=\begin{cases}1&(d=0)\wedge(u_{b}\geq\frac{34}{112})\\\
1&(d=1)\wedge(u_{b}\geq\frac{90}{144})\\\
0&\text{otherwise}\end{cases}\end{cases}$ (44)

The corresponding neural network for $\widehat{\mathcal{F}}_{1}$ can be seen
as

$\displaystyle\hat{f}^{1}_{D}(u_{d})$ $\displaystyle=\hat{f}_{\geq
112/256}(u_{d})$ (45) $\displaystyle\hat{f}^{1}_{B}(d,u_{b})$
$\displaystyle=\hat{f}_{\operatorname{\textsc{OR}}}\left(\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{\operatorname{\textsc{NOT}}}(d),\hat{f}_{\geq
34/112}(u_{b})\right),\hat{f}_{\operatorname{\textsc{AND}}}\left(d,\hat{f}_{\geq
90/144}(u_{b})\right)\right).$ (46)

$\widehat{\mathcal{F}}_{2}$ is constructed such that the causal direction of
$D$ and $B$ in $\widehat{M}_{2}$ is reversed, i.e.,

$\widehat{\mathcal{F}}_{2}:=\begin{cases}\hat{f}^{2}_{D}(b,u_{d})&=\begin{cases}1&(b=0)\wedge(u_{d}\geq\frac{34}{124})\\\
1&(b=1)\wedge(u_{d}\geq\frac{78}{132})\\\ 0&\text{otherwise}\end{cases}\\\
\hat{f}^{2}_{B}(u_{b})&=\begin{cases}1&u_{b}\geq\frac{124}{256}\\\
0&\text{otherwise}\end{cases}\end{cases}$ (47)

The corresponding neural network for $\widehat{\mathcal{F}}_{2}$ can be
written as

$\displaystyle\hat{f}^{2}_{D}(b,u_{d})$
$\displaystyle=\hat{f}_{\operatorname{\textsc{OR}}}\left(\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{\operatorname{\textsc{NOT}}}(b),\hat{f}_{\geq
34/124}(u_{d})\right),\hat{f}_{\operatorname{\textsc{AND}}}\left(b,\hat{f}_{\geq
78/132}(u_{d})\right)\right)$ (48) $\displaystyle\hat{f}^{2}_{B}(u_{b})$
$\displaystyle=\hat{f}_{\geq 124/256}(u_{b}).$ (49)

$\widehat{\mathcal{F}}_{3}$ is constructed such that
$P^{\widehat{M}_{3}}(B=1\mid do(D=1))$ is maximized, namely,

$\widehat{\mathcal{F}}_{3}:=\begin{cases}\hat{f}^{3}_{D}(u_{d})&=\begin{cases}1&u_{d}\geq\frac{112}{256}\\\
0&\text{otherwise}\end{cases}\\\
\hat{f}^{3}_{B}(d,u_{b},u_{d})&=\begin{cases}1&(d=1)\wedge(u_{b}<\frac{34}{112})\wedge(u_{d}<\frac{112}{256})\\\
1&(u_{b}\geq\frac{34}{112})\wedge(u_{d}<\frac{112}{256})\\\
1&(d=1)\wedge(u_{b}<\frac{54}{144})\wedge(u_{d}\geq\frac{112}{256})\\\
0&\text{otherwise}\end{cases}\end{cases}$ (50)

The corresponding neural network for $\widehat{\mathcal{F}}_{3}$ can be
written as

$\displaystyle\hat{f}^{3}_{D}(u_{d})$ $\displaystyle=\hat{f}_{\geq
112/256}(u_{d})$ (51) $\displaystyle\hat{f}^{3}_{B}(d,u_{b},u_{d})$
$\displaystyle=\hat{f}_{\operatorname{\textsc{OR}}}\begin{cases}\hat{f}_{\operatorname{\textsc{AND}}}\left(d,\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
34/112}(u_{b})\right),\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
112/256}(u_{d})\right)\right)\\\
\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{\geq
34/112}(u_{b}),\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
112/256}(u_{d})\right)\right)\\\
\hat{f}_{\operatorname{\textsc{AND}}}\left(d,\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
54/144}(u_{b})\right),\hat{f}_{\geq 112/256}(u_{d})\right).\end{cases}$ (52)

Finally, $\widehat{\mathcal{F}}_{4}$ is constructed such that
$P^{\widehat{M}_{4}}(B=1\mid do(D=1))$ is minimized,

$\widehat{\mathcal{F}}_{4}:=\begin{cases}\hat{f}^{4}_{D}(u_{d})&=\begin{cases}1&u_{d}\geq\frac{112}{256}\\\
0&\text{otherwise}\end{cases}\\\
\hat{f}^{4}_{B}(d,u_{b},u_{d})&=\begin{cases}1&(d=0)\wedge(u_{b}\geq\frac{34}{112})\wedge(u_{d}<\frac{112}{256})\\\
1&(d=1)\wedge(u_{b}<\frac{54}{144})\wedge(u_{d}\geq\frac{112}{256})\\\
0&\text{otherwise}\end{cases}\end{cases}$ (53)

The corresponding neural network for $\widehat{\mathcal{F}}_{4}$ can be
written as

$\displaystyle\hat{f}^{4}_{D}(u_{d})$ $\displaystyle=\hat{f}_{\geq
112/256}(u_{d})$ (54) $\displaystyle\hat{f}^{4}_{B}(d,u_{b},u_{d})$
$\displaystyle=\hat{f}_{\operatorname{\textsc{OR}}}\begin{cases}\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{\operatorname{\textsc{NOT}}}(d),\hat{f}_{\geq
34/112}(u_{b}),\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
112/256}(u_{d})\right)\right)\\\
\hat{f}_{\operatorname{\textsc{AND}}}\left(d,\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
54/144}(u_{b})\right),\hat{f}_{\geq 112/256}(u_{d})\right).\end{cases}$ (55)

Even though the functions of these NCMs are constructed in very different
ways, one can verify that they indeed induce the same layer 1 as shown in
Table 3.

Despite this match, they all disagree on a simple layer 2 quantity such as
$P(B=1\mid do(D=1))$; to witness note that

$\displaystyle P^{\widehat{M}_{1}}(B=1\mid do(D=1))$ $\displaystyle=P(B=1\mid
D=1)=\frac{54}{144}=0.375$ (56) $\displaystyle P^{\widehat{M}_{2}}(B=1\mid
do(D=1))$ $\displaystyle=P(B=1)=\frac{132}{256}\approx 0.5156$ (57)
$\displaystyle P^{\widehat{M}_{3}}(B=1\mid do(D=1))$
$\displaystyle=\frac{166}{256}\approx 0.6484$ (58) $\displaystyle
P^{\widehat{M}_{4}}(B=1\mid do(D=1))$ $\displaystyle=\frac{54}{256}\approx
0.2109$ (59)

Without further information, it’s not possible to distinguish which model (if
any) is the correct one. Naïevely, choosing an arbitrary model is likely to
result in misleading results, even if the model can reproduce the given
$L_{1}$ data with high fidelity.

In practice, depending on the chosen model, the conclusion of the study could
be dramatically different. For instance, someone who fits models
$\widehat{M}_{1}$ or $\widehat{M}_{4}$ may conclude that a high-vegetable diet
is beneficial for lowering blood pressure, while someone who fits model
$\widehat{M}_{2}$ may conclude that it has no effect at all. Someone who fits
model $\widehat{M}_{3}$ may even conclude that eating more vegetables is
harmful for regulating blood pressure.

$\blacksquare$

###  C.2 Structural Constraints Embedded in Causal Bayesian Networks

In this section, we provide an example to illustrate the inductive bias
embedded in causal diagrams, building on the more comprehensive treatment
provided in [5, Sec. 1.4].

######  Example 3.

Consider the following two SCMs:

$\mathcal{M}_{1}:=\begin{cases}\mathbf{U}&:=\\{U_{X},U_{Y}\\},\text{ all
binary}\\\ \mathbf{V}&:=\\{X,Y\\},\text{ all binary}\\\
\mathcal{F}_{1}&:=\begin{cases}f^{1}_{X}(U_{X})&=U_{X}\\\
f^{1}_{Y}(X,U_{Y})&=X\oplus U_{Y}\end{cases}\\\
P(\mathbf{U})&:=P(U_{X}=1)=\frac{1}{2},P(U_{Y}=1)=\frac{1}{4},U_{X}\mathbin{\mathchoice{\hbox
to0.0pt{\hbox{\set@color$\displaystyle\perp$}\hss}\kern 3.46875pt{}\kern
3.46875pt\hbox{\set@color$\displaystyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\textstyle\perp$}\hss}\kern 3.46875pt{}\kern
3.46875pt\hbox{\set@color$\textstyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\scriptstyle\perp$}\hss}\kern 2.36812pt{}\kern
2.36812pt\hbox{\set@color$\scriptstyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\scriptscriptstyle\perp$}\hss}\kern 1.63437pt{}\kern
1.63437pt\hbox{\set@color$\scriptscriptstyle\perp$}}}U_{Y}\end{cases}$
$\mathcal{M}_{2}:=\begin{cases}\mathbf{U}&:=\\{U_{X},U_{Y}\\},\text{ all
binary}\\\ \mathbf{V}&:=\\{X,Y\\},\text{ all binary}\\\
\mathcal{F}_{2}&:=\begin{cases}f^{2}_{X}(Y,U_{X})&=Y\oplus U_{X}\\\
f^{2}_{Y}(U_{Y})&=U_{Y}\end{cases}\\\
P(\mathbf{U})&:=P(U_{X}=1)=\frac{1}{4},P(U_{Y}=1)=\frac{1}{2},U_{X}\mathbin{\mathchoice{\hbox
to0.0pt{\hbox{\set@color$\displaystyle\perp$}\hss}\kern 3.46875pt{}\kern
3.46875pt\hbox{\set@color$\displaystyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\textstyle\perp$}\hss}\kern 3.46875pt{}\kern
3.46875pt\hbox{\set@color$\textstyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\scriptstyle\perp$}\hss}\kern 2.36812pt{}\kern
2.36812pt\hbox{\set@color$\scriptstyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\scriptscriptstyle\perp$}\hss}\kern 1.63437pt{}\kern
1.63437pt\hbox{\set@color$\scriptscriptstyle\perp$}}}U_{Y}\end{cases}$

Note that both $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ induce the same $L_{1}$
distributions.

For example, in both models, $P(Y=1)=\frac{1}{2}$, and $P(Y=1\mid
X=1)=\frac{3}{4}$. However, even without making any computation, it seems
intuitive from the structure of the functions and noise that a causal query
like $P(Y=1\mid do(X=1))$ would have different answers in both models. First,
note that $f^{2}_{Y}$ in $\mathcal{M}_{2}$ does not have $X$ as an argument,
and there are no other variables in $\mathbf{V}$, so intervening on $X$ would
have no causal effect on $Y$. In other words, the constraint
$P^{\mathcal{M}_{2}}(Y=1\mid do(X=1))=P(Y=1)$ is implied. More subtly in the
case of $\mathcal{M}_{1}$, we note that $X$ directly affects $Y$ and there is
no unobserved confounding between $X$ and $Y$. This means that the observed
association between $X$ and $Y$ must be due to the causal effect (i.e.
$P^{\mathcal{M}_{1}}(Y=1\mid do(X=1))=P(Y=1\mid X=1)$). The relationship
between $X$ and $Y$ in these two cases can be seen graphically, as shown in
Fig. 9.

$X$$Y$ (a) Graph for $\mathcal{M}_{1}$.

$X$$Y$ (b) Graph for $\mathcal{M}_{2}$.

Figure 9: Causal diagrams for SCMs in Example 3. A directed edge from $A$ to
$B$ indicates that $A$ is an argument of the function for $B$.

$\blacksquare$

As illustrated in the previous example, and discussed more formally in [5],
these equality constraints across distributions arise from the qualitative
structural properties of the SCM such as which variable is an argument of
which function, and which variables share exogenous influence. In fact, these
constraints are invariant to the details of the functions and the distribution
of the exogenous variables.

Moreover, there are exponentially many constraints implied by an SCM in the
collection of $L_{1}$ and $L_{2}$ distributions, which can be parsimoniously
represented in the form of a causal bayesian network (Def. 15)121212This is a
generalization of the notion of markov compatibility used in $L_{1}$ models,
such as bayesian networks [53]. In our case, there are multiple distributions
of different nature, observational and experimental, and the constraints are
among them (i.e., not conditional independences).  In fact, the graphical
component of this object provides an intuitive interpretation for these
constraints. It can be shown that the closure of such constraints entails the
do-calculus [5, Thm. 5], which means that all identifiable effects can be
computed from them (due to the completeness shown in [43]).

$D$$B$ Figure 10: Causal diagram $\mathcal{G}$ of $\mathcal{M}^{*}$ from
Example 1

Revisiting Examples 1 and 2 and applying the definition of causal diagram
(Def. 12), we can see from the structure of $\mathcal{M}^{*}$ that the causal
diagram $\mathcal{G}$ in Fig. 10 is induced. If we had this information, we
could immediately eliminate $\widehat{M}_{2}$ from Example 2 as a possible
model. The reason is that we can read off from diagram $\mathcal{G}$ that $B$
cannot be an argument of $f_{D}$.

With an SCM-like structure, the NCM naturally induces its own structural
constraints. Def. 7 in the main paper shows how to construct an NCM to fit the
same constraints entailed by a given causal diagram from another SCM. In some
way, the original model induces mark in the collection of observational and
experimental distributions. In the case of the NCM, these constraints are used
as input, inductive bias to constrain its functions. This is powerful because
any inferences performed on a $\mathcal{G}$-constrained NCM will automatically
satisfy the constraints of $\mathcal{G}$.

###  C.3 Solving Identification through NCMs

(a) In the identifiable case, all NCMs that are $\mathcal{G}$-consistent and
$L_{1}$-consistent with $\mathcal{M}^{*}$ will also match in $Q$.

(b) In the non-identifiable case, there could exist two NCMs,
$\widehat{M}_{1}$ and $\widehat{M}_{2}$, that are both
$\mathcal{G}$-consistent and $L_{1}$-consistent but still disagree in $Q$.

Figure 11: A visual representation of the ID problem. Here, $Q$ is a query of
interest, and $\widehat{Q}_{i}$ is the answer for that query induced by NCM
$\widehat{M}_{i}$. The goal is to check if all NCMs that are
$\mathcal{G}$-consistent and $L_{1}$-consistent are also consistent in $Q$.

The notion of identification requires that a certain effect is identifiable by
all (unobserved) SCMs compatible with the corresponding structural
constraints. This was extended to NCMs through Def. 8; see also Fig. 11. In
fact, Alg. 1 helps to solve the neural identification problem such that if
there are two NCMs compatible with the constraints but with different
predictions for the causal effect, it will return “FAIL”. Otherwise, it will
returns the estimation of the query in every ID case. Note that identification
of an effect does not require that the NCM and the true SCM have the same
functions, just the effects need to match. The following two examples
illustrate both positive and negative instances of such operation.

######  Example 4.

Consider once again the study of diet on blood pressure introduced in Example
1. Suppose we are particularly interested in the $L_{2}$ expression of
$Q=P(B=1\mid do(D=1))$, the causal effect of diet on blood pressure. The true
SCM $\mathcal{M}^{*}$ is not available, but $L_{1}$ data ($P(\mathbf{v})$)
presented in Table 3 is (as shown Example 2). Furthermore, we are informed by
a doctor that the two variables follow the relation specified by the causal
diagram $\mathcal{G}$ in Fig. 10. Is $Q$ identifiable from $P(\mathbf{v})$ and
$\Omega(\mathcal{G})$, where $\Omega(\mathcal{G})$ is the set of all
$\mathcal{G}$-constrained NCMs?

Unfortunately, the answer is no for this particular case. To see why, example
2 provides 4 NCMs whose $L_{1}$ distributions match $P(\mathbf{v})$ but
disagree on $Q$. Even though $\widehat{M}_{2}$ can be eliminated as a possible
proxy since it is not $\mathcal{G}$-consistent, the other three models are
compatible with $\mathcal{G}$, so we still cannot pinpoint the correct answer
for $Q$.

Running Alg. 1 on this setting would result in the algorithm generating two
sets of parameters, $\bm{\theta}^{*}_{\min}$ and $\bm{\theta}^{*}_{\max}$,
that minimize and maximize $Q$. The behaviors of an NCM with these parameters
may reflect the behaviors of $\widehat{M}_{3}$ and $\widehat{M}_{4}$ from
Example 2, and they do not agree on $Q$. $\blacksquare$

######  Example 5.

Suppose now we return to the data collection process and we receive new
information about a third variable, sodium intake ($S$) ($S=1$ represents a
high sodium diet, $0$ otherwise).

With the introduction of $S$ in the endogenous set $\mathbf{V}$,
$\mathcal{M}^{*}$ can be written as follows:

$\mathcal{M}^{*}:=\begin{cases}\mathbf{U}&:=\\{U_{D},U_{DB},U_{S},U_{B}\\},\text{
all binary}\\\ \mathbf{V}&:=\\{D,S,B\\}\\\
\mathcal{F}&:=\begin{cases}f_{D}(U_{D},U_{DB})&=\neg U_{D}\wedge\neg U_{DB}\\\
f_{S}(D,U_{S})&=\neg D\oplus U_{S}\\\ f_{B}(S,U_{B})&=(S\vee U_{DB})\oplus
U_{B}\end{cases}\\\
P(\mathbf{U})&:=\begin{cases}P(U_{D}=1)=P(U_{DB}=1)=P(U_{S}=1)=P(U_{B}=1)=\frac{1}{4}\\\
\text{ all }U\in\mathbf{U}\text{ are independent}\end{cases}\end{cases}$ (60)

As reflected in the updated $\mathcal{M}^{*}$, diet only affects blood
pressure through sodium content, which tends to be higher in low-vegetable
diets. Note that the $L_{1}$, $L_{2}$, and $L_{3}$ distributions relating $D$
and $B$ are unchanged with this modification of $\mathcal{M}^{*}$. In this
case, the query of interest is evaluated as

$\displaystyle P(B=1\mid do(D=1))$ $\displaystyle=P\left((S_{D=1}\vee
U_{DB})\oplus U_{B}=1\right)$ $\displaystyle=P\left(((\neg 1\oplus U_{S})\vee
U_{DB})\oplus U_{B}=1\right)$ $\displaystyle=P\left((U_{S}\vee U_{DB})\oplus
U_{B}=1\right)$ $\displaystyle=\frac{120}{256}=0.46875,$ (61)

which matches the result in Eq. 33.

$D$ | $S$ | $B$ | $P(D,S,B)$
---|---|---|---
0 | 0 | 0 | $13/256$
0 | 0 | 1 | $15/256$
0 | 1 | 0 | $21/256$
0 | 1 | 1 | $63/256$
1 | 0 | 0 | $81/256$
1 | 0 | 1 | $27/256$
1 | 1 | 0 | $9/256$
1 | 1 | 1 | $27/256$
Table 4: Updated observational distribution $P(\mathbf{V})$ induced by
$\mathcal{M}^{*}$ for Example 5. $D$$S$$B$ Figure 12: Causal diagram
$\mathcal{G}$ of $\mathcal{M}^{*}$ with additional $S$ variable for Example 5

This is just the computation of the distribution from Nature’s perspective. As
the previous examples, we do not have access to the true model
($\mathcal{M}^{*}$), just the observational distribution $P(\mathbf{v})$, as
shown in Table 4. We do have access to the updated causal diagram as shown in
Fig. 12.

The addition of the new variable and the refinement of the model change the
identifiability status of the query $Q=P(B=1\mid do(D=1))$. No matter how Alg.
1 chooses the parameters for $\bm{\theta}^{*}_{\min}$ and
$\bm{\theta}^{*}_{\max}$, $\widehat{M}$ will always induce the same result for
$Q$ as long as it induces the correct $P(\mathbf{v})$. Specifically, through
standard do-calculus derivation we would obtain:

$\displaystyle P(B=1\mid do(D=1))$
$\displaystyle=\sum_{s\in\mathcal{D}_{S}}P(s\mid do(D=1))P(B=1\mid do(D=1),s)$
Marginalization $\displaystyle=\sum_{s\in\mathcal{D}_{S}}P(s\mid
do(D=1))P(B=1\mid do(D=1),do(s))$ Rule 2
$\displaystyle=\sum_{s\in\mathcal{D}_{S}}P(s\mid do(D=1))P(B=1\mid do(s))$
Rule 3 $\displaystyle=\sum_{s\in\mathcal{D}_{S}}P(s\mid D=1)P(B=1\mid do(s))$
Rule 2 $\displaystyle=\sum_{s\in\mathcal{D}_{S}}P(s\mid
D=1)\sum_{d\in\mathcal{D}_{D}}P(B=1\mid d,do(s))P(d\mid do(s))$
Marginalization $\displaystyle=\sum_{s\in\mathcal{D}_{S}}P(s\mid
D=1)\sum_{d\in\mathcal{D}_{D}}P(B=1\mid d,do(s))P(d)$ Rule 3
$\displaystyle=\sum_{s\in\mathcal{D}_{S}}P(s\mid
D=1)\sum_{d\in\mathcal{D}_{D}}P(B=1\mid d,s)P(d)$ Rule 2

Finally, we can replace the corresponding probabilities with the actual
values, i.e.,

$\displaystyle P(B=1\mid do(D=1))$ $\displaystyle=P(S=0\mid D=1)P(B=1\mid
D=0,S=0)P(D=0)$ $\displaystyle+P(S=0\mid D=1)P(B=1\mid D=1,S=0)P(D=1)$
$\displaystyle+P(S=1\mid D=1)P(B=1\mid D=0,S=1)P(D=0)$
$\displaystyle+P(S=1\mid D=1)P(B=1\mid D=1,S=1)P(D=1)$
$\displaystyle=\left(\frac{108}{144}\right)\left(\frac{15}{28}\right)\left(\frac{112}{256}\right)+\left(\frac{108}{144}\right)\left(\frac{27}{108}\right)\left(\frac{144}{256}\right)$
$\displaystyle+\left(\frac{36}{144}\right)\left(\frac{63}{84}\right)\left(\frac{112}{256}\right)+\left(\frac{36}{144}\right)\left(\frac{27}{36}\right)\left(\frac{144}{256}\right)$
$\displaystyle=\frac{15}{32}=0.46875$ (62)

On the other hand, any $\mathcal{G}$-constrained NCM that induces
$P(\mathbf{v})$ will produce the same result, matching Eq. 62. For instance,
consider the following NCM construction:

$\widehat{M}:=\begin{cases}\widehat{\mathbf{U}}&:=\\{\widehat{U}_{DB},\widehat{U}_{S}\\},\mathcal{D}_{\widehat{U}_{DB}}=\mathcal{D}_{\widehat{U}_{S}}=[0,1]\\\
\mathbf{V}&:=\\{D,S,B\\}\\\
\widehat{\mathcal{F}}&:=\begin{cases}\hat{f}_{D}(u_{DB})&=\begin{cases}1&u_{DB}\geq\frac{112}{256}\\\
0&\text{otherwise}\end{cases}\\\
\hat{f}_{S}(d,u_{S})&=\begin{cases}1&(d=0)\wedge(u_{S}\geq\frac{1}{4})\\\
1&(d=1)\wedge(u_{S}\geq\frac{3}{4})\\\ 0&\text{otherwise}\end{cases}\\\
\hat{f}_{B}(b,u_{DB})&=\begin{cases}1&(s=0)\wedge\left((\frac{52}{256}\leq
u_{DB}<\frac{112}{256})\vee(u_{DB}\geq\frac{220}{256})\right)\\\
1&(s=1)\wedge\left((\frac{28}{256}\leq
u_{DB}<\frac{112}{256})\vee(u_{DB}\geq\frac{148}{256})\right)\\\
0&\text{otherwise}\end{cases}\end{cases}\\\
P(\widehat{\mathbf{U}})&:=\widehat{U}_{DB},\widehat{U}_{S}\sim\operatorname{Unif}(0,1),\widehat{U}_{DB}\mathbin{\mathchoice{\hbox
to0.0pt{\hbox{\set@color$\displaystyle\perp$}\hss}\kern 3.46875pt{}\kern
3.46875pt\hbox{\set@color$\displaystyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\textstyle\perp$}\hss}\kern 3.46875pt{}\kern
3.46875pt\hbox{\set@color$\textstyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\scriptstyle\perp$}\hss}\kern 2.36812pt{}\kern
2.36812pt\hbox{\set@color$\scriptstyle\perp$}}{\hbox
to0.0pt{\hbox{\set@color$\scriptscriptstyle\perp$}\hss}\kern 1.63437pt{}\kern
1.63437pt\hbox{\set@color$\scriptscriptstyle\perp$}}}\widehat{U}_{S}\end{cases}$
(63)

The corresponding neural network for $\widehat{\mathcal{F}}$ can be written as

$\displaystyle\hat{f}_{D}(u_{DB})$ $\displaystyle=\hat{f}_{\geq
112/256}(u_{DB})$ (64) $\displaystyle\hat{f}_{S}(d,u_{S})$
$\displaystyle=\hat{f}_{\operatorname{\textsc{OR}}}\left(\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{\operatorname{\textsc{NOT}}}(d),\hat{f}_{\geq
1/4}(u_{S})\right),\hat{f}_{\operatorname{\textsc{AND}}}\left(d,\hat{f}_{\geq
3/4}(u_{S})\right)\right)$ (65) $\displaystyle\hat{f}_{B}(s,u_{DB})$
$\displaystyle=\hat{f}_{\operatorname{\textsc{OR}}}\begin{cases}\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{\operatorname{\textsc{NOT}}}(s),\hat{f}_{\geq
52/256}(u_{DB}),\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
112/256}(u_{DB})\right)\right)\\\
\hat{f}_{\operatorname{\textsc{AND}}}\left(\hat{f}_{\operatorname{\textsc{NOT}}}(s),\hat{f}_{\geq
220/256}(u_{DB})\right)\\\
\hat{f}_{\operatorname{\textsc{AND}}}\left(s,\hat{f}_{\geq
28/256}(u_{DB}),\hat{f}_{\operatorname{\textsc{NOT}}}\left(\hat{f}_{\geq
112/256}(u_{DB})\right)\right)\\\
\hat{f}_{\operatorname{\textsc{AND}}}\left(s,\hat{f}_{\geq
148/256}(u_{DB})\right).\\\ \end{cases}$ (66)

Note that $\widehat{M}$ follows the format of a $\mathcal{G}$-constrained NCM
defined in Def. 7. Additionally, one can verify that $\widehat{M}$ induces the
same $L_{1}$ quantities shown in Table 4. Applying the mutilation procedure on
$\widehat{M}$ to compute the query,

$\displaystyle P^{\widehat{M}}(B=1\mid do(D=1))$
$\displaystyle=P(S_{D=1}=0)P\left(\left(\frac{52}{256}\leq
U_{DB}<\frac{112}{256}\right)\vee\left(U_{DB}\geq\frac{220}{256}\right)\right)$
$\displaystyle+P(S_{D=1}=1)P\left(\left(\frac{28}{256}\leq
U_{DB}<\frac{112}{256}\right)\vee\left(U_{DB}\geq\frac{148}{256}\right)\right)$
$\displaystyle=\left(\frac{96}{256}\right)P(S_{D=1}=0)+\left(\frac{192}{256}\right)P(S_{D=1}=1)$
$\displaystyle=\left(\frac{96}{256}\right)P\left(U_{S}<\frac{3}{4}\right)+\left(\frac{192}{256}\right)P\left(U_{S}\geq\frac{3}{4}\right)$
$\displaystyle=\frac{72}{256}+\frac{48}{256}=\frac{120}{256}=0.46875.$

This result indeed matches Eq. 61. We further note $\widehat{M}$ is
constructed to fit $P(\mathbf{v})$ and not necessarily to match
$\mathcal{M}^{*}$. This is evident when comparing the inputs and outputs of
the functions in $\widehat{\mathcal{F}}$ to those from $\mathcal{M}^{*}$.
Still, due to the structural constraints encoded in the NCM, it so happens
that $\widehat{M}$ also matches in our $L_{2}$ query of interest even though
it is only constructed to match only on layer 1. It is remarkable that
incorporating these family of constraints into the NCM structure allows one to
successfully perform cross-layer inferences.

$\blacksquare$

Thm. 4 is powerful because it says that performing the identification task in
the class of NCMs will yield the correct result, even if the true model can be
any SCM. We note that this is not the case for every class of models, even if
a model from that class can be both $L_{1}$-consistent and
$\mathcal{G}$-consistent with the true model. In particular, the expressivity
of the NCM allows for this result, and using a less expressive model may
produce incorrect results. We illustrate this with the following examples.

######  Example 6.

Suppose we attempt to identify $P(B=1\mid do(D=1))$ from the problem in
Example 4 using a less expressive model class such as the set of all Markovian
models. Recall that the given observational $P(\mathbf{V})$ is shown in Table
3, and the given causal diagram $\mathcal{G}$ is shown in Fig. 10. An example
model from the class of Markovian models that achieve $L_{1}$ and
$\mathcal{G}$ consistency with $\mathcal{M}^{*}$ is $\widehat{M}_{1}$ from
Example 2.

Note that due to the lack of unobserved confounding in Markovian models, the
induced value for $P(B=1\mid do(D=1))$ for any $L_{1}$ and
$\mathcal{G}$-consistent Markovian model including $\widehat{M}_{1}$ is
$P(B=1\mid do(D=1))=P(B=1\mid D=1)=\frac{54}{144}=0.375$. Since all models
from this class (Markovian) agree on the same value for this quantity, the
conclusion reached is that it must be identifiable. However, this is clearly
not the case, as we know the true value, $P^{\mathcal{M}^{*}}(B=1\mid
do(D=1))=0.46875$. In this case, the reason we reach the wrong result is that
the true model is not Markovian, and the set of all Markovian models is not
expressive enough to account for all possible SCMs. $\blacksquare$

More interestingly, another example using a different class of models follows.

######  Example 7.

Consider a special class of SCMs which, given variables $\mathbf{V}$ and the
graph $\mathcal{G}$, take the following structure.

$\widehat{M}=\begin{cases}\widehat{\mathbf{U}}&:=\\{\widehat{U}_{\mathbf{C}}:\mathbf{C}\in
C^{2}(\mathcal{G})\\},\mathcal{D}_{\widehat{U}}=[0,1]\text{ for all
}\widehat{U}\in\widehat{\mathbf{U}},\\\ \widehat{\mathbf{V}}&:=\mathbf{V},\\\
\widehat{\mathcal{F}}&:=\left\\{\hat{f}_{V}(\mathbf{pa}_{V},\mathbf{u}_{V})=\left(\underset{x\in\mathbf{pa}_{V}}{\bigoplus}x\right)\oplus\left(\underset{u_{i}\in\mathbf{u}_{V}}{\bigoplus}\mathbbm{1}(a_{V,i}\leq
u_{i}<b_{V,i})\right):V\in\mathbf{V}\right\\},\\\
&a_{V,i},b_{V,i}\in[0,1],a_{V,i}\leq b_{V,i},\\\ &\mathbf{pa}_{V}\text{ is the
set of parents of }V\text{ in }\mathcal{G},\\\
&\mathbf{u}_{V}=\\{\widehat{U}_{\mathbf{C}}:\mathbf{C}\in
C^{2}(\mathcal{G})\text{ such that }V\in\mathbf{C}\\},\\\
P(\widehat{\mathbf{U}})&:=\widehat{U}\sim\operatorname{Unif}(0,1)\text{ for
all }\widehat{U}\in\widehat{\mathbf{U}}.\end{cases}$ (67)

Here, $C^{2}(\mathcal{G})$ denotes the set of all $C^{2}$-components of
$\mathcal{G}$. The $\oplus$ operator denotes bitwise XOR, with the larger
version representing the bitwise XOR of all elements of a set (0 if empty).

$X$$Y$

Figure 13: Causal diagram $\mathcal{G}$ of $\mathcal{M}^{*}$ from Example 7

$X$ | $Y$ | $P(X,Y)$
---|---|---
0 | 0 | $p_{0}$
0 | 1 | $p_{1}$
1 | 0 | $p_{2}$
1 | 1 | $p_{3}$

Table 5: General observational distribution $P(\mathbf{V})$ induced by
$\mathcal{M}^{*}$ from Example 7. We assume positivity (i.e. $p_{i}>0$ for all
$i$).

We may opt to use a model like this for its simplicity, since having fewer
parameters allows for easier optimization. Suppose we try to use this model
class to decide if $P(Y\mid do(X))$ is identifiable in the case where the true
model, $\mathcal{M}^{*}$, induces the graph $\mathcal{G}$ in Fig. 13. We are
given $\mathcal{G}$ along with $P(\mathbf{v})$, which can be represented as
shown in Table 5. If we construct a model $\widehat{M}$ from Eq. 67, it would
have the following form.

$\widehat{M}=\begin{cases}\widehat{\mathbf{U}}&:=\\{\widehat{U}_{XY}\\},\mathcal{D}_{\widehat{U}_{XY}}=[0,1],\\\
\widehat{\mathbf{V}}&:=\\{X,Y\\}\\\
\widehat{\mathcal{F}}&:=\begin{cases}\hat{f}_{X}(\widehat{u}_{XY})&=\mathbbm{1}(a_{X}\leq\widehat{u}_{XY}<b_{X}),\\\
\hat{f}_{Y}(x,\widehat{u}_{XY})&=x\oplus\mathbbm{1}(a_{Y}\leq\widehat{u}_{XY}<b_{Y})\end{cases}\\\
P(\widehat{\mathbf{U}})&:=U_{XY}\sim\operatorname{Unif}(0,1).\end{cases}$

The parameters we choose to fit $P(\mathbf{V})$ are the values of
$a_{X},b_{X},a_{Y},b_{Y}$. However, note that there in order for $\widehat{M}$
to attain $L_{1}$-consistency with $\mathcal{M}^{*}$, we must have:

  1. 1.

$b_{X}-a_{X}=p_{2}+p_{3}$.

  2. 2.

($a_{X}-a_{Y}=p_{1}$ and $b_{Y}-a_{X}=p_{2}$) or ($b_{Y}-b_{X}=p_{1}$ and
$b_{X}-a_{Y}=p_{2}$)

2 implies $b_{Y}-a_{Y}=p_{1}+p_{2}$, so in all cases, $P^{\widehat{M}}(Y=1\mid
do(X=0))=p_{1}+p_{2}$ and $P^{\widehat{M}}(Y=1\mid do(X=1))=p_{0}+p_{3}$. In
other words, since $P^{\widehat{M}}(Y\mid do(X))$ matches for all models from
this class that are $L_{1}$ and $\mathcal{G}$-consistent, the conclusion
reached is that it must be identifiable.

However, suppose $\mathcal{M}^{*}$ takes the following form:

$\mathcal{M}^{*}=\begin{cases}\mathbf{U}&:=\\{U_{X},U_{Y}\\},\mathcal{D}_{U_{X}}=\mathcal{D}_{U_{Y}}=\\{0,1\\},\\\
\mathbf{V}&:=\\{X,Y\\}\\\ \mathcal{F}&:=\begin{cases}f_{X}(u_{X})&=u_{X},\\\
f_{Y}(x,u_{Y})&=u_{Y},\end{cases}\\\
P(\mathbf{U})&:=\begin{cases}P(U_{X}=0,U_{Y}=0)&=p_{0}\\\
P(U_{X}=0,U_{Y}=1)&=p_{1}\\\ P(U_{X}=1,U_{Y}=0)&=p_{2}\\\
P(U_{X}=1,U_{Y}=1)&=p_{3}\end{cases}\end{cases}$

One can quickly verify that $\mathcal{M}^{*}$ does indeed induce the
$P(\mathbf{V})$ in Table 5 and $\mathcal{G}$ from Fig. 13. Note that in this
$\mathcal{M}^{*}$, $P(Y=1\mid do(X=0))=P(Y=1\mid do(X=1))=p_{1}+p_{3}$. In
fact, this means there is a complete mismatch from any possible choice of
$\widehat{M}$. Like shown in Example 4, $P(Y\mid do(X))$ is actually a non-
identifiable query when $\mathcal{G}$ takes the form in Fig. 13. Simply put,
$\mathcal{M}^{*}$ could be an SCM for which the model class in Eq. 67 is not
expressive enough to capture.

$\blacksquare$

###  C.4 Symbolic versus Optimization-based Approaches for Identification

In this section, we discuss the relationship between current approaches to
causal identification/estimation versus the new, neural/optimization-based
approach proposed in this work.

The problem of effect identification has been extensively studied in the
literature, and [54] introduced the do-calculus (akin to differential or
integral calculus), a set of symbolic rules that can be applied to any
expression and evaluate whether a certain invariance across interventional
distributions hold given local assumptions encoded in a causal diagram.
Multiple applications of the rules can be combined to search for a reduction
from a target effect to the distributions in which data is available. There
exist algorithms capable of utilizing the structural constraints encoded in
the causal diagram, based on what is known as c-component factorization [64],
to find a symbolic expression of the $L_{2}$ query in terms of the $L_{1}$
distribution efficiently (for more general tasks, see, e.g., [43, 13]). We
call this approach symbolic since it aims to find a closed-form expression of
the target effect in terms of the input distributions.

Alternatively, one could take an optimization-based route to tackle the
identification problem, such as in Alg. 1 discussed in Sec. 3. This approach
entails a search through the space of possible structural models while trying
to maximize/minimize the value of the target query subject to the constraints
found in the inputted data. We call this an optimization-based approach. These
two approaches are indeed linked as evident from Thm. 2, which establishes a
duality saying that the identification status of a target query is shared
across symbolic and optimization-based approaches.

We discuss next some of the possible trade-offs and synergies between these
two families of methods. We start with the symbolic approach and re-stating
the definition of identification [55], with minor modifications to highlight
its model-theoretic perspective regarding the space of SCMs:

######  Definition 17 (Causal Effect Identification).

Let $\Omega^{*}$ be the space containing all SCMs defined over endogenous
variables $\mathbf{V}$. We say that a causal effect $P(\mathbf{y}\mid
do(\mathbf{x}))$ is identifiable from the observational distribution
$P(\mathbf{v})$ and the causal diagram $\mathcal{G}$ if
$P^{\mathcal{M}_{1}}(\mathbf{y}\mid
do(\mathbf{x}))=P^{\mathcal{M}_{2}}(\mathbf{y}\mid do(\mathbf{x}))$ for every
pair of models $\mathcal{M}_{1},\mathcal{M}_{2}\in\Omega^{*}$ such that
$\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ both induce $\mathcal{G}$ and
$P^{\mathcal{M}_{1}}(\mathbf{v})=P^{\mathcal{M}_{2}}(\mathbf{v})$
$\blacksquare$

$\bm{\Omega}^{*}$$\mathcal{M}^{1}$$\mathcal{M}^{2}$($\mathcal{L}_{1}$)ObservationalDistributionsData$P^{\mathcal{M}_{1}}(\mathbf{V}){=}P^{\mathcal{M}_{2}}(\mathbf{V})$($\mathcal{L}_{2}$)InterventionalDistributionsQuery$P^{\mathcal{M}_{1}}(\mathbf{Y}|do(\mathbf{x}))=$$P^{\mathcal{M}_{2}}(\mathbf{Y}|do(\mathbf{x}))$?Structural
ConstraintsCausal Diagram$\mathcal{G}$ Figure 14: $P(\mathbf{Y}\mid
do(\mathbf{x}))$ is identifiable from $P(\mathbf{V})$ and $\mathcal{G}$ if for
all SCM $\mathcal{M}^{1},\mathcal{M}^{2}$ (top left) such that
$\mathcal{M}^{1},\mathcal{M}^{2}$ match in $P(\mathbf{V})$ (bottom left) and
$\mathcal{G}$ (top right), then they also match in the target distribution
$P(\mathbf{Y}\mid do(\mathbf{x}))$ (bottom right).

Fig. 14 provides an illustration of the many parts involved in this
definition. In words, an interventional distribution $Q=P(\mathbf{Y}\mid
do(\mathbf{x}))$ is said to be identifiable if for all SCMs in $\Omega^{*}$
(top-left) that share the same causal diagram $\mathcal{G}$ (top-right), and
induce the same probability distribution $P(\mathbf{V})$ (bottom-left), they
generate the same distribution to the target query $Q$ (bottom-right). In
fact, identifiability can be understood as if the details of the specific form
of the true SCM $\mathcal{M}^{*}$ – its functions and probability distribution
over the exogenous variables – are irrelevant, and the constraints encoded in
the causal diagram are sufficient to perform the intended cross-layer
inference from the source to the target distributions.

One important observation that follows is that, operationally, symbolic
methods do not work directly in the $\Omega^{*}$ space, but on top of the
constraints implied by the true SCM on the causal diagram. There are a number
of reasons for this, but we note that if all that is available about
$\mathcal{M}^{*}$ are the constraints encoded in $\mathcal{G}$, it is somewhat
expected and reasonable to operate directly on those, instead of considering
the elusive, underlying structural causal model. Further, we already know
through the CHT that we will never be able to recover $\mathcal{M}^{*}$
anyways, so one could see it as unreasonable to consider $\mathcal{M}^{*}$ as
the target of the analysis. Still, even if we wanted to refer directly to
$\mathcal{M}^{*}$, practically speaking, searching through the space
$\Omega^{*}$ is a daunting task since each candidate SCM
$\mathcal{M}=\langle\mathcal{F},P(\mathbf{U})\rangle\in\Omega^{*}$ is a
complex, infinite dimensional object. Note that the very definition of
identification (Def. 17) does not even mention the true SCM $\mathcal{M}^{*}$,
since it is completely out of reach in most practical situations. The task
here is indeed about whether one can get by without having to know much about
the underlying collection of mechanisms and still answer the query of
interest. (In causal terminology, an identification instance is called non-
parametric whenever no constraints are imposed over the functional class
$\mathcal{F}$ or exogenous distribution $P(\mathbf{U})$.

The full causal pipeline encompassing both tasks of effect identification and
estimation is illustrated in Fig. 15. Note that the detachment with respect to
the true Nature, alluded to above, is quite prominent in the figure. The very
left part contains $\mathcal{M}^{*}$, which is abstracted away in the form of
the causal diagram $\mathcal{G}$ and through its marks imprinted into the
observational distribution $P(\mathbf{V})$. The symbolic methods takes the
pair $\langle\mathcal{G},P(\mathbf{V})\rangle$ as input (instead of the
unobservable $\langle\mathcal{F}^{*},P^{*}(\mathbf{U})\rangle$), and attempt
to determine whether the target distribution $Q$ can be expressed in terms of
the available input distributions. Formally, the question asked is about
whether there exists a mapping $f$ such that

$\displaystyle Q=f_{\mathcal{G}}(P(\mathbf{V})).$ (68)

UnobservedRealityCausal IdentificationCausal Estimation$\mathcal{M}^{*}$Space
of AllSCMs ($\Omega^{*}$)$P^{*}(\mathbf{V})$Space ofObs.
Distributions$\mathcal{G}^{*}$Space ofCausal DiagramsQuery $P^{*}(Y\mid
do(X))$ID from $\langle\mathcal{G}^{*},P^{*}(\mathbf{V})\rangle?$Task
1NoYesSamplingDataset $D^{*}(\mathbf{V})$$P^{*}(Y\mid
do(X))=f(P^{*}(\mathbf{V}))$Causal EstimandFit Estimand $f$using Data
$D^{*}(\mathbf{V})$Task 2EmpiricalDistribution Figure 15: Causal Pipeline with
unobserved SCM $\mathcal{M}^{*}$ in the left, generating both $\mathcal{G}$
and $P(\mathbf{v})$, which is taken as input for the identification task (1),
which generates input to the estimation task (2).

The decision problem regarding the existence of $f(.)$ is certainly within the
domain of causal reasoning since it takes an arbitrary causal diagram as
input, which encodes causal assumptions about the underlying SCM, and reason
through causal axioms on whether this is sufficient to perform the intended
cross-layer inference. Causal reasoning is nothing more than the manipulation
and subsequent derivation of new causal facts from known causal invariances.
Whenever this step is successfully realized, one can then ignore the causal
invariances (or assumptions) entirely, and simply

$\mathcal{M}^{*}=\langle\mathcal{F}^{*},P^{*}(\mathbf{U})\rangle$(unobserved
truth)$\mathcal{M}=\langle\mathcal{F},P(\mathbf{U})\rangle$$\mathcal{M}^{\prime}=\langle\mathcal{F}^{\prime},P^{\prime}(\mathbf{U})\rangle$Space
of All SCMs ($\Omega^{*}$)Space of SCMs thatinduce $\mathcal{G}^{*}$ and
$P^{*}(\mathbf{V})$($\Omega^{*}(\mathcal{G}^{*},P^{*}(\mathbf{V}))$) Figure
16:  In the case where $Q$ is identifiable, any two SCMs in
$\Omega^{*}(\mathcal{G}^{*},P^{*}(\mathbf{V}))$ – the space of SCMs matching
$\mathcal{M}^{*}$ in $P^{*}(\mathbf{V})$ and $\mathcal{G}^{*}$ – will also
match $\mathcal{M}^{*}$ in $Q$.

try to evaluate the r.h.s. of Eq. 68 to compute $Q$.

We note that in most practical settings, only a dataset with samples collected
from $P(\mathbf{V})$ is available, say $D(\mathbf{V})$, as opposed to the
distribution itself. This entails the second task that asks for a
computationally and statistically attractive way of evaluating the r.h.s. of
Eq. 68 from the finite samples contained in the dataset $D(\mathbf{V})$. Even
though the l.h.s. of Eq. 68 is a causal distribution, the evaluation is
complete oblivious to the semantics of such quantity and is entirely about
fitting $f$ using the data $D(\mathbf{V})$ in the best possible way.

We now turn our attention to the optimization-based approach as outlined in
Alg. 1 (Sec. 3) and note that it will have a very different interpretation of
the identifiability definition. In fact, instead of avoiding the SCM
altogether and focusing on the causal diagrams’ constraints, as done by the
symbolic approach, it will put the SCM at the front and center of the
analysis. Fig. 16 illustrates this point by showing the space of all SCMs
called $\Omega^{*}$ (in dark gray). The true, unknown SCM $\mathcal{M}^{*}$ is
shown as a black dot and generates the pair
$\langle\mathcal{G}^{*},P^{*}(\mathbf{V})$, the latter is taken as the input
of the identification analysis. The approach will then focus on the set of
SCMs that have the same interventional constraints as $\mathcal{G}^{*}$ (Def.
5) and that also have the capability of generating the same observational
distribution $P^{*}(\mathbf{V})$ (Def. 4). This subspace is called
$\Omega^{*}(\mathcal{G}^{*},P^{*}(\mathbf{V}))$ and marked in light gray.
Since $\mathcal{M}^{*}$ is almost never inferrable, the optimization-approach
will search for two SCMs
$\mathcal{M},\mathcal{M}^{\prime}\in\Omega^{*}(\mathcal{G}^{*},P^{*}(\mathbf{V}))$
such that the former will try to maximize the target query ($Q_{max}$), while
the latter minimizes it ($Q_{min}$). Two candidate SCMs for this job are shown
in the figure. Whenever the search ends and two of such SCMs are discovered,
they will predict exactly the same interventional distribution (i.e.,
$Q_{min}=Q_{max}$) if $Q$ is identifiable. This is because by the definition
of identifiability (Def. 17), all SCMs in the light gray area will necessarily
exhibited the same interventional behavior.

$\mathcal{M}^{*}=\langle\mathcal{F}^{*},P^{*}(\mathbf{U})\rangle$(unobserved
truth)$\mathcal{M}=\langle\mathcal{F},P(\mathbf{U})\rangle$$\mathcal{M}^{\prime}=\langle\mathcal{F}^{\prime},P^{\prime}(\mathbf{U})\rangle$Space
of All SCMs ($\Omega^{*}$)Space of SCMs thatinduce $\mathcal{G}^{*}$ and
$P^{*}(\mathbf{V})$($\Omega^{*}(\mathcal{G}^{*},P^{*}(\mathbf{V}))$) Figure
17:  In the case where $Q$ is non-identifiable, there exist two SCMs in
$\Omega^{*}(\mathcal{G}^{*},P^{*}(\mathbf{V}))$ (the space of SCMs matching
$\mathcal{M}^{*}$ in $P^{*}(\mathbf{V})$ and $\mathcal{G}^{*}$) that do not
match $\mathcal{M}^{*}$ in $Q$.

On the other hand, the situation is qualitatively different when considering
non-identifiable effects. To understand how, the first observation comes from
the contrapositive of Def. 17, which says that non-identifiability implies
there exists (at least) two SCMs $\mathcal{M},\mathcal{M}^{\prime}$ within the
$\Omega^{*}(\mathcal{G}^{*},P^{*}(\mathbf{V}))$ subspace that share the
constraints as in $\mathcal{G}^{*}$ and generate the same observational
distribution ($P(\mathbf{V})=P^{\prime}(\mathbf{V})$), but induce different
interventional distributions($P(Y|do(X))\neq P^{\prime}(Y|do(X))$). The
optimization-based approach will try to exploit precisely this fact, searching
for non-identifiability witnesses, possibly different than the true
$\mathcal{M}^{*}$. Those are illustrated as red dots and hollow circles in
Fig. 17. Still, this is all that is needed to determine whether an effect is
not identifiable. In practice, each distribution
$\mathcal{Q},\mathcal{Q}^{\prime}$ will only be approximations and it may be
hard to detect non-identifiability depending on how close they are from each
other. This is indeed what leads to the probabilistic nature of such
identifiability statements when using optimization-based methods (as discussed
in Appendix B), as opposed to the deterministic ones entailed by the do-
calculus and symbolic family.

By and large, both approaches take the causal assumptions and try to infer
something about the unknown, target quantity $P^{*}(Y|do(X=x))$ that is
defined by the unobserved $\mathcal{M}^{*}$. In the case of the symbolic
approach, the structural assumptions encoded in the causal diagram
$\mathcal{G}$ are used, while an optimization-based approach will use
constraints encoded through the scope of the functions and independence among
the exogenous variables $\mathbf{U}$. Evaluating $P^{*}(Y\mid do(X=x))$ is
possible in identifiable cases, which means that our predictions will match
what the true $\mathcal{M}^{*}$ would say, while the assumptions would be too
weak in others cases, and non-identifiability will take place, which means we
are unable to make any statement about $\mathcal{M}^{*}$ without strengthening
the assumptions.

After having understood the different takes of both approaches to the problem
of identification, we consider again the entire pipeline shown in Fig. 15. We
note that the two tasks, identification and estimation, are both necessary in
any causal analysis, but they are usually studied separately in the symbolic
literature. Symbolic methods returns the identifiability status of a query and
include the mapping $f$ whenever the effect is identifiable. The target
quantity can then be evaluated by standard statistical methods (plug-in) or
more refined learning procedures, e.g., multi-propensity score/inverse
probability weighting [31], empirical risk minimization [32], and double
machine learning [33].

On the other hand, the optimization-based framework proposed here is capable
of identifying and estimating the target quantities in an integrated manner.
As shown through simulations (Sec. 5), given the sampling nature of the
optimization procedure, the performance of the method relies not only on the
causal assumptions, but also on accurate optimization, which may require a
large amount of samples and computation for training.

In practice, one may consider a hybrid approach where a symbolic algorithm for
the identification step is ran first, since it is deterministic and always
returns the right answer, and then the estimation step is performed through an
NCM. With this use case in mind, we define Alg. 4 in Fig. 18 (left) as this
hybrid alternative to the more pure Alg. 1. In some sense, this approach
combines the best of both worlds – it relies on an ideal ID algorithm, which
is correct with probability one, and the powerful computational properties of
neural networks, which may perform well and scale to complex settings, for
estimation. We illustrate this using the two figures in Fig. 18 (right).

1

Input : causal query $Q=P(\mathbf{y}\mid do(\mathbf{x}))$, $L_{1}$ data
$P(\mathbf{v})$, and causal diagram $\mathcal{G}$

Output : $P^{\mathcal{M}^{*}}(\mathbf{y}\mid do(\mathbf{x}))$ if identifiable,
FAIL otherwise

2 if  _symbolicID( Q)_ then

$\textnormal{{$\widehat{M}$}}\leftarrow\textnormal{{NCM(}}\textnormal{\emph{{{$\mathbf{V}$}},
{{$\mathcal{G}$}}}}\textnormal{{)}}$

// from Def. 7

$\textnormal{{$\bm{\theta}^{*}$}}\leftarrow\arg\min_{\bm{\theta}}D(P^{\textnormal{{$\widehat{M}$}}(\bm{\theta})}(\mathbf{v}),\textnormal{{$P(\mathbf{v})$}})$

// for some divergence $D$

3 return
$P^{\textnormal{{$\widehat{M}$}}(\textnormal{{$\bm{\theta}^{*}$}})}(\mathbf{y}\mid
do(\mathbf{x}))$

4

5else

6 return FAIL

Algorithm 4 Identifying queries with a symbolic ID procedure and then
estimating with NCMs.

(a) Neural ID + Neural Estimation (Alg. 1)

(b) Symbolic ID + Neural Estimation (Alg. 4)

Figure 18: (Left panel) Algorithm for solving identification problem with
symbolic solvers and estimation with NCMs. (Right) Schematic illustrating
differences between Alg. 1 (a) and Alg. 4 (b).

After all, the NCM approach provides a cohesive framework that unifies both
the causal and the statistical components involved in evaluating
interventional distributions. In the case of the hybrid approach, we note that
the causal reasoning is shifted to the symbolic identification methods. It is
remarkable but somewhat unsurprising that neural methods, which are the state-
of-the-art for function approximations, are capable of performing the
statistical step required for causal estimation. More interestingly, we
demonstrate in this work that neural nets (and proxy SCMs, in general) are
also capable of performing causal reasoning, such as in the inferences
required to solve the ID problem. Many other works have studied using neural
networks as an estimation tool, as listed in the introduction, but to the best
of our knowledge, our work is the first one that utilizes neural networks to
provide a complete solution within the neural framework to the identification
problem, and causal reasoning more broadly.

In addition to showing that neural nets are also capable of performing causal
reasoning, there are other implications for using a proxy SCM in place of the
true SCM, as opposed to abstracting the true SCM entirely. Firstly, the
generative capabilities of proxy SCMs, like the NCM, can be useful if the user
desires a source of infinite data, which is a quite common use case found in
the literature. Secondly, it provides quick estimation results for multiple
queries via the mutilation procedure without the need for retraining. Whenever
we apply a symbolic approach we need to derive (and then train) a specialized
estimand, which can be time consuming. Thirdly, working in the space of SCMs
tends to provide straightforward interpretation of the causal problems using
its semantics, which implies that it has the potential to be more easily
extensible to other related problems. One may be interested in generalizations
of the ID problem such as identifying other types of queries or identifying
and fusing from different sources and experimental conditions [4, 6, 43], such
as in reinforcement learning. In general, extending the line of reasoning of
Alg. 1 to other identification cases is much simpler than deriving a new
symbolic solution under different constraints.

##  Appendix D Generalizations

###  D.1 NCMs with other Functions and Noise Distributions (Proofs)

For the sake of concreteness and simplicity of exposition, the NCM from Def. 3
specifically uses $\operatorname{Unif}(0,1)$ noise for the variables in
$\mathbf{U}$ and MLPs as functions. This leads to easy implementation and
concrete examples for discussion (as in Appendix C).

We note that these are not meant to be limitations for the NCM framework. The
NCM object can be extended to use other function or noise types, provided they
exhibit certain properties. We will henceforth refer to specific versions of
the NCM with their particular implementation of the noise and functions (e.g.,
Def. 3 will be called NCM-FF-Unif).

Consider a more general version of the NCM below:

######  Definition 18 (NCM (General Case)).

A Neural Causal Model (for short, NCM) $\widehat{M}(\bm{\theta})$ over
variables $\mathbf{V}$ with parameters
$\bm{\theta}=\\{\theta_{V_{i}}:V_{i}\in\mathbf{V}\\}$ is an SCM
$\langle\widehat{\mathbf{U}},\mathbf{V},\widehat{\mathcal{F}},\widehat{P}(\widehat{\mathbf{U}})\rangle$
such that

  * •

$\widehat{\mathbf{U}}\subseteq\\{\widehat{U}_{\mathbf{C}}:\mathbf{C}\subseteq\mathbf{V}\\}$,
where each $\widehat{U}$ is associated with some subset of variables
$\mathbf{C}\subseteq\mathbf{V}$;

  * •

$\widehat{\mathcal{F}}=\\{\hat{f}_{V_{i}}:V_{i}\in\mathbf{V}\\}$, where each
$\hat{f}_{V_{i}}$, parameterized by $\theta_{V_{i}}\in\bm{\theta}$, maps
values of $\mathbf{U}_{V_{i}}\cup\mathbf{Pa}_{V_{i}}$ to values of $V_{i}$ for
some $\mathbf{Pa}_{V_{i}}\subseteq\mathbf{V}$ and
$\mathbf{U}_{V_{i}}=\\{\widehat{U}_{\mathbf{C}}:\widehat{U}_{\mathbf{C}}\in\widehat{\mathbf{U}},V_{i}\in\mathbf{C}\\}$;

Furthermore, a NCM $\widehat{M}(\bm{\theta})$ should have the following
properties:
(P1) For all $\widehat{U}\in\widehat{\mathbf{U}}$, $\widehat{U}$ has a well-
defined probability density function $P(\widehat{U})$ (i.e. its cumulative
density function is absolutely continuous).
(P2) For all functions $\hat{f}_{V_{i}}\in\widehat{\mathcal{F}}$ and all
functions $g:\mathbb{R}\rightarrow\mathbb{S}$, where
$\mathbb{S}\subset\mathbb{R}$ is a countable set, there exists
parameterization $\theta^{*}_{V_{i}}$ such that
$\hat{f}_{V_{i}}(\cdot;\theta^{*}_{V_{i}})=g$ (universal representation).
$\blacksquare$

We can use these properties to prove a more general version of Thm. 1. We
first state the following result to aid the proof.

######  Fact 5 (Probability Integral Transform [11, Thm. 2.1.10]).

For any random variable $X$ with a well-defined probability density function
$P(X)$, there exists a function $f:\mathcal{D}_{X}\rightarrow[0,1]$ such that
$f(X)$ is a $\operatorname{Unif}(0,1)$ random variable. $\blacksquare$

The generalized proof follows.

######  Theorem 5 (NCM Expressiveness).

For any SCM
$\mathcal{M}^{*}=\langle\mathbf{U},\mathbf{V},\mathcal{F},P(\mathbf{U})\rangle$,
there exists a NCM
$\widehat{M}(\bm{\theta})=\langle\widehat{\mathbf{U}},\mathbf{V},\widehat{\mathcal{F}},\widehat{P}(\widehat{\mathbf{U}})\rangle$
s.t. $\widehat{M}$ is $L_{3}$-consistent w.r.t. $\mathcal{M}^{*}$.
$\blacksquare$

###### Proof.

Lemma 2 guarantees that there exists a canonical SCM
$\mathcal{M}_{\operatorname{\textsf{CM}}}=\langle\mathbf{U}_{\operatorname{\textsf{CM}}},\mathbf{V},\mathcal{F}_{\operatorname{\textsf{CM}}},P(\mathbf{U}_{\operatorname{\textsf{CM}}})\rangle$
that is $L_{3}$-consistent with $\mathcal{M}^{*}$. Hence, to construct
$\widehat{M}$, it suffices to show how to construct
$\mathcal{M}_{\operatorname{\textsf{CM}}}$ using the architecture of a NCM.

Following Def. 18, we choose
$\widehat{\mathbf{U}}=\\{\widehat{U}_{\mathbf{V}}\\}$. By property P1 and Fact
5, there exists a function $g^{U}$ such that $g^{U}(\widehat{U}_{\mathbf{V}})$
is a $\operatorname{Unif}(0,1)$ random variable.

Using the construction in Lem. 5, there must also exist a function $g^{R}$
such that

$P(g^{R}(g^{U}(\widehat{U_{\mathbf{V}}})))=P(\mathbf{U}_{\operatorname{\textsf{CM}}})$
(69)

To choose the functions of $\widehat{\mathcal{F}}$, consider each
$\hat{f}_{V_{i}}\in\widehat{\mathcal{F}}$. Combining the above results, there
must exist

$g_{V_{i}}=f_{V_{i}}^{\operatorname{\textsf{CM}}}\left(\mathbf{pa}_{V_{i}},g^{R}\left(g^{U}(\widehat{U}_{\mathbf{V}})\right)\right)$
(70)

By property P2, we can choose parameterization $\theta^{*}_{V_{i}}$ such that
$\hat{f}_{V_{i}}(\cdot;\theta^{*}_{V_{i}})=g_{V_{i}}$.

By Eqs. 69 and 70, the NCM $\widehat{M}$ is constructed to match
$\mathcal{M}_{\operatorname{\textsf{CM}}}$ on all outputs. Hence, for any
counterfactual query $\bm{\upvarphi}$, we have

$\mathcal{M}_{\operatorname{\textsf{CM}}}\models\bm{\upvarphi}\Leftrightarrow\widehat{M}\models\bm{\upvarphi}$

and therefore

$\mathcal{M}^{*}\models\bm{\upvarphi}\Leftrightarrow\widehat{M}\models\bm{\upvarphi}.$

∎

The general $\mathcal{G}$-constrained version of the NCM follows the same
procedure as Def. 7.

######  Definition 19 ($\mathcal{G}$-Constrained NCM (General Case)).

Let $\mathcal{G}$ be the causal diagram induced by SCM $\mathcal{M}^{*}$.
Construct NCM $\widehat{M}$ as follows. (1) Choose $\widehat{\mathbf{U}}$ s.t.
$\widehat{U}_{\mathbf{C}}\in\widehat{\mathbf{U}}$ if and only if $\mathbf{C}$
is a $C^{2}$-component in $\mathcal{G}$. Each $\widehat{U}_{\mathbf{C}}$ has
its own distribution $P(\widehat{U}_{\mathbf{C}})$ independent of other
variables in $\widehat{\mathbf{U}}$, but it is shared as input to the
functions of all variables in $\mathbf{C}$. (2) For each variable
$V_{i}\in\mathbf{V}$, choose $\mathbf{Pa}_{V_{i}}\subseteq\mathbf{V}$ s.t. for
every $V_{j}\in\mathbf{V}$, $V_{j}\in\mathbf{Pa}_{V_{i}}$ if and only if there
is a directed edge from $V_{j}$ to $V_{i}$ in $\mathcal{G}$. Any NCM in this
family is said to be $\mathcal{G}$-constrained. $\blacksquare$

We prove a general version of Thm. 3 similarly.

######  Theorem 6 (NCM $L_{2}$-$\mathcal{G}$ Representation).

For any SCM $\mathcal{M}^{*}$ that induces causal diagram $\mathcal{G}$, there
exists a $\mathcal{G}$-constrained NCM
$\widehat{M}(\bm{\theta})=\langle\widehat{\mathbf{U}},\mathbf{V},\widehat{\mathcal{F}},\widehat{P}(\widehat{\mathbf{U}})\rangle$
that is $L_{2}$-consistent w.r.t. $\mathcal{M}^{*}$. $\blacksquare$

###### Proof.

Fact 3 states that there exists a $\mathcal{G}$-canonical SCM
$\mathcal{M}_{\operatorname{\textsf{GCM}}}=\langle\mathbf{U}_{\operatorname{\textsf{GCM}}},\mathbf{V},\mathcal{F}_{\operatorname{\textsf{GCM}}},P(\mathbf{U}_{\operatorname{\textsf{GCM}}})\rangle$
that is $L_{2}$-consistent with $\mathcal{M}^{*}$. Hence, to construct
$\widehat{M}$, we can simply show how to construct
$\mathcal{M}_{\operatorname{\textsf{GCM}}}$ using the architecture of a NCM.

Following Def. 19, we choose
$\widehat{\mathbf{U}}=\\{\widehat{U}_{\mathbf{C}}:\mathbf{C}\in\mathbb{C}(\mathcal{G})\\}$,
where $\mathbb{C}(\mathcal{G})$ is the set of all $C^{2}$-components of
$\mathcal{G}$. Denote
$\widehat{\mathbf{U}}_{V}=\\{\widehat{U}_{\mathbf{C}}:\mathbf{C}\in\mathbb{C}(\mathcal{G})\text{
s.t. }V\in\mathbf{C}\\}$.

By property P1 and Fact 5, there exists a function $g_{V}^{U}$ such that
$g_{V}^{U}(\widehat{\mathbf{U}}_{V})$ is a $\operatorname{Unif}(0,1)$ random
variable for each $V\in\mathbf{V}$.

Using the construction in Lem. 5, there must also exist a function $g_{V}^{R}$
such that

$P(g_{V}^{R}(g_{V}^{U}(\widehat{\mathbf{U}}_{V})))=P(\mathbf{R}_{V})$ (71)

for each $V\in\mathbf{V}$.

To choose the functions of $\widehat{\mathcal{F}}$, consider each
$\hat{f}_{V_{i}}\in\widehat{\mathcal{F}}$. Combining the above results, there
must exist

$g_{V_{i}}=f_{V_{i}}^{\operatorname{\textsf{GCM}}}\left(\mathbf{pa}_{V_{i}},g_{V_{i}}^{R}\left(g_{V_{i}}^{U}(\widehat{\mathbf{U}}_{V})\right)\right)$
(72)

By property P2, we can choose parameterization $\theta^{*}_{V_{i}}$ such that
$\hat{f}_{V_{i}}(\cdot;\theta^{*}_{V_{i}})=g_{V_{i}}$.

By Eqs. 71 and 72, the NCM $\widehat{M}$ is constructed to match
$\mathcal{M}_{\operatorname{\textsf{CM}}}$ on all outputs. Hence,
$\widehat{M}$ must be $L_{2}$-consistent with $\mathcal{M}^{*}$. ∎

The remaining results, including Corol. 1, Thm. 2, Thm. 4, Corol. 2, Corol. 3,
and Corol. 4 can be proven for NCMs with minimal changes to the proofs for
NCMs.

###  D.2 Pearl’s Causal Hierarchy and Other Classes of Models

As developed in the paper, we note that the expressiveness power of NCMs is
one desirable features of this class as models, which makes them comparable to
the SCM class when considering the PCH’s capabilities. Broadly speaking,
neural networks are well understood to be maximally expressive due to the
Universal Approximation Theorem [14]. We note that Theorem 1 follows the same
spirit when considering causal inferences, i.e., NCMs is a data structure
built from neural networks that are maximally expressive on _every_
distribution in _every_ layer of the PCH generated by the underlying SCM
$\mathcal{M}^{*}$, and which has the potential of acting as a proxy under some
conditions. This capability is not shared across all neural architectures, and
to understand how this discussion extends to these other classes, we define
expressivity more generally (Fig. 19):

######  Definition 20 ($L_{i}$-Expressiveness).

Let $\Omega^{*}$ be the set of SCMs and $\Omega$ be a model class of interest.
We say that $\Omega$ is $L_{i}$ expressive if for all
$\mathcal{M}^{*}\in\Omega^{*}$, there exists $\mathcal{M}\in\Omega$ s.t.
$L_{i}(\mathcal{M}^{*})=L_{i}(\mathcal{M})$. $\blacksquare$

It should be emphasized that expressiveness on layers higher than Layer 1 is a
highly nontrivial property (e.g., Example 1 in Appendix C.1 shows the
complications involved in constructing an NCM to replicate another SCM on all
3 layers). Even a model class that is $L_{2}$-expressive can represent far
more settings than model classes that are only $L_{1}$-expressive, since there
are many more ways in which SCMs can differ on $L_{2}$ than on $L_{1}$.
Theorem 1 states that NCMs are $L_{3}$-expressive, which leads to the
question: what model classes are not $L_{3}$-expressive?

SCMs ($\Omega^{*}$)NCMsModel Class
($\Omega$)$\mathcal{M}^{*}$$\mathcal{M}$$L_{i}$-Expressive:PCH$\mathcal{L}_{1}^{*}$$\mathcal{L}_{2}^{*}$$\mathcal{L}_{3}^{*}$
Figure 19: The SCM class $\Omega^{*}$ is shown in the l.h.s. and another class
(non-SCM) $\Omega$ class is shown in the r.h.s.. If we consider
$M^{*}\in\Omega^{*}$ that generates a specific PCH, $\Omega$ is $L_{i}$
representative if there is a model $M\in\Omega^{*}$ that exhibit the same
behavior under $L_{i}$.

Many neural model classes are $L_{1}$-expressive, which can be seen as the
property of modeling an unique probability distribution over a set of observed
variables. Additionally, this model should be generative, i.e., one should be
able to draw samples from the model’s fitted distribution. Model classes that
have this property include variational models with normalizing flows [59],
which are generative models and are proven to be able to fit any data
distribution. It is also believed that popular generative models like
generative adversarial networks [20] have this property as well.

Interesting enough, being generative does not imply being causal or
counterfactual. For instance, these model classes are not well defined for
valuating any causal distributions. A model from one of these classes that is
fitted on $P(\mathbf{V})$ can only provide samples from $P(\mathbf{V})$. On
the other hand, distributions like $P(\mathbf{V}_{\mathbf{x}})$, the
distribution of $\mathbf{V}$ under the intervention
$do(\mathbf{X}=\mathbf{x})$ for some $\mathbf{X}\subseteq\mathbf{V}$, are
entirely different distributions from Layer 2 of the PCH. A model fitted on
$P(\mathbf{V})$ cannot output samples from $P(\mathbf{V}_{\mathbf{x}})$, and
it certainly cannot output samples from _every_ Layer 2 or Layer 3
distributions. These models, therefore, are not even $L_{2}$-expressive, let
alone $L_{3}$-expressive.

It is somewhat natural, and perhaps obvious, that model classes that are not
defined on higher layers cannot be expressive on higher layers. Still, we can
also consider this property on model classes proposed by other deep learning
works which include a causal component. Works such as [66] and [61] have had
great success estimating higher layer quantities like average treatment
effects under backdoor/conditional ignorability conditions [55, Sec. 3.3.1].
Perhaps these models can always succeed at modeling Layer 2 expressions as
long as the ground truth can be modeled by an SCM that also meets those same
backdoor conditions. However, since there are SCMs that do not fit the
backdoor setting, we cannot say that these models are $L_{2}$ or
$L_{3}$-expressive. We illustrate this point by providing an example (Example
5) in Appendix C.3, where the NCM estimates a causal quantity in a setting
that does not meet the backdoor condition.

In some way, these works and most of the literature are concerned with
estimating causal effects that are identifiable from observational data
$P(V)$, usually in the form of the backdoor formula, which means that the
“causal reasoning” already happened outside the network itself. In other
words, a causal distribution $Q=P(\mathbf{Y}|do(\mathbf{X}=\mathbf{x}))$ being
identifiable means that there exists a function $f$ such that $Q=f(P(V))$. The
causal “inference” means determining from causal assumptions (for example the
causal diagram $G$) whether $Q$ is identifiable, or whether $f$ exists.
Whenever this is the case, and $f$ has a closed-expression, the inference is
done, and the task that remains is to estimate $f$ efficiently from finite
samples obtained from $P(V)$.

Even though many existing works do not have the $L_{2}$ or
$L_{3}$-expressiveness properties, this is not to say that the NCM is the only
model class that is expressive enough to represent all the three layers of the
PCH. Consider the following example of a model class artificially constructed
to be $L_{2}$-expressive:

######  Definition 21 ($L_{2}$-Expression Wrapper).

Let $M^{L_{1}}$ be an $L_{1}$-expressive model class such as a normalizing
flow model. Denote $M^{L_{1}}_{P}$ as a model from this class fitted on
distribution $P$. For a collection of $L_{2}$ distributions $\mathbf{P}^{*}$,
define $L_{2}$-expression wrapper
$M^{L_{2}}:=\\{M^{L_{1}}_{P}:P\in\mathbf{P}^{*}\\}$. $\blacksquare$

It is fairly straightforward to show that the $L_{2}$-expression wrapper is
$L_{2}$-expressive. For any SCM $\mathcal{M}^{*}$, we can simply construct
$L_{2}$-expression wrapper $M^{L_{2}}$ with
$\mathbf{P}^{*}=L_{2}(\mathcal{M}^{*})$. Then, for any $L_{2}$-query $Q$,
$M^{L_{2}}$ answers $Q$ by providing the distribution of $M^{L_{1}}_{Q}$. In
other words, we could simply train a generative model for every $L_{2}$
distribution of an SCM, and collectively, these models induce all $L_{2}$
distributions of the SCM.

Although expressive, this model is highly impractical for most practical uses.
First, there are typically too many distributions in Layer 2 to effectively
learn all of them. A new distribution would be created for every possible
intervention of every subset of variables. In fact, this amount grows
exponentially with the number of variables, and in continuous cases, it is
infinite.

Second, unlike the NCM data structure (Def. 7), there is no clear way to
incorporate the constraints of a CBN in the expression wrapper. Without these
constraints, it is obvious that the expression wrapper suffers from the same
limitations from the CHT as NCMs (Corol. 1). Suppose we are given
$P(\mathbf{V})$ from true SCM $\mathcal{M}^{*}$, but we are interested in the
distribution $P(\mathbf{V}_{\mathbf{x}})$. We could guarantee an expression
wrapper $M^{L_{2}}$ such that
$M^{L_{1}}_{P(\mathbf{V})}=P^{\mathcal{M}^{*}}(\mathbf{V})$, but
$M^{L_{1}}_{P(\mathbf{V}_{\mathbf{x}})}$ could be any distribution over
$\mathbf{V}$ that is consistent with $\mathbf{x}$, and we would not be able to
guarantee that it matches $P^{\mathcal{M}^{*}}(\mathbf{V}_{\mathbf{x}})$.

Attempting to incorporate the constraints of a CBN in an expression wrapper
would scale poorly and be difficult to realize in practice. Consider the
following example.

######  Example 8.

$D$$S$$B$ Figure 20: Causal diagram $\mathcal{G}$ of $\mathcal{M}^{*}$ from
Example 5.

Consider the same setting from Example 5, where we would like to evaluate a
query like $Q=P(B=1\mid do(D=1))$ given $P(\mathbf{V})$ and the graph
$\mathcal{G}$ (displayed again in Fig. 20 for convenience). If we were using
the expression wrapper, we would need an estimator for each of the $L_{1}$ and
$L_{2}$ distributions such
$P(\mathbf{V}),P(\mathbf{V}_{D=1}),P(\mathbf{V}_{S=1})$, and so on.

However, unlike the NCM, the expression wrapper does not automatically
incorporate the constraints implied by $\mathcal{G}$. Here is a list of some
constraints used in the do-calculus derivation in Example 5:

  1. 1.

$P(B\mid do(D),S)=P(B\mid do(D,S))$

  2. 2.

$P(B\mid do(D,S))=P(B\mid do(S))$

  3. 3.

$P(S\mid do(D))=P(S\mid D)$

  4. 4.

$P(D\mid do(S))=P(D)$

  5. 5.

$P(B\mid do(S),D)=P(B\mid S,D)$

This list is not exhaustive, and there are more constraints induced by
$\mathcal{G}$. This list is also compressed, since intervening on different
values for the same variables result in different distributions. Note that
even with just 3 binary variables, the number of constraints is quite long
when enumerated.

Maintaining all of these constraints while fitting all of the desired
distributions is the key difficulty of using the $L_{2}$-expression wrapper.
While fitting $P(\mathbf{V})$, the expression wrapper would have to also
generate some other distributions from layer 2 like $P(\mathbf{V}_{D=1})$,
keeping constraints in mind. One cannot make such a choice arbitrarily. For
instance, setting $P(\mathbf{V}_{D=1})$ to $P(\mathbf{V})$, but with all
values of $D$ set to 1, would still violate constraint 3 from the above list.
This would be infeasible for any tractable optimization procedure.
$\blacksquare$

This illustrates the benefits of the properties of the NCM. Not only is the
NCM $L_{3}$-expressive, a non-trivial property to achieve, but it also is
easily able to incorporate structural constraints.

##  Appendix E Frequently Asked Questions

  1. Q1.

Why are the sets of noise variables for each function not necessarily
independent in the SCM and NCM?
Answer. Each structural causal model includes a set of observed (endogenous)
and unobserved (exogenous) variables, $\mathbf{V}$ and $\mathbf{U}$,
respectively. The set $\mathbf{U}$ accounts for the unmodeled sources of
variation that generate randomness in the system. On the one hand, an
exogenous variable $U\in\mathbf{U}$ could affect all endogenous variables in
the system. On the other hand, each $U_{i}\in\mathbf{U}$ could affect only one
observable $V_{i}\in\mathbf{V}$ and be independent to all other variables in
$\mathbf{U}\setminus\\{U_{i}\\}$. These two represent opposite sides of a
spectrum, where the former means zero assumptions on the presence of
unobserved confounding, while the latter represents the strongest assumption
known as Markovianity. We operate in between, allowing for all possible cases,
which is represented in the causal diagram through bidirected edges.

In the context of identification, Markovianity is usually known as the lack of
unobserved confounding. As shown in Corol. 3, the identification problem
becomes trivial and causation is always derivable from association in this
case, i.e., _all_ layer 2 queries are computable from layer 1 data. In
practice, identification becomes somewhat more involved in non-Markovian
settings. Example 4 in Appendix C shows a case where a causal query is not
identifiable even in a 2 variable case. More discussion and examples can be
found in [5, Sec. 1.4].

  2. Q2.

How come the true SCM cannot be learned from observational data? If the
functions are universal approximators, this seems to be easily accomplished.
Answer. This is not possible in general, as highlighted by Corol. 1. The issue
is that the learned model, $\widehat{M}$, could generate the distribution of
observational data perfectly yet still differ in interventional distributions
from the true SCM, $\mathcal{M}^{*}$. Searching for (or randomly choosing)
some SCM that matches the observational distribution will almost surely fail
to match the interventional distributions. Since the true SCM,
$\mathcal{M}^{*}$, is unobserved, one would not be able to determine whether
the inferences made on the learned model $\widehat{M}$ preserve the validity
of the causal claims. See Example 2 in Appendix C for a more detailed
discussion.

  3. Q3.

Why are feedforward neural networks and uniform distributions used in Def. 3?
Would these results not hold for other function approximators and noise
distributions?
Answer. We implemented in the body of the paper NCMs with feedforward neural
networks and uniform distributions for the sake of clarity of exposition and
presentation. The results of the NCM are not limited to this particular
architecture choice, and other options may offer different benefits in
practice. A general definition of the NCM is introduced in Def. 18, and the
corresponding results in this generalized setting are provided in Appendix
D.1.

  4. Q4.

What is a causal diagram? What is a CBN? Is there any difference between these
objects?
Answer.  A causal diagram $\mathcal{G}$ is a non-parametric representation of
an SCM in the form of a graph, which follows Def. 12, such that nodes
represent variables, a directed edge from $X$ to $Y$ indicates that $X$ is an
input to $f_{Y}$, and a bidirected edge from $X$ to $Y$ indicates that there
is unobserved confounding between $X$ and $Y$. The causal diagram
$\mathcal{G}$ is strictly weaker than the generating SCM $\mathcal{M}^{*}$.
Talking about the diagram itself is usually ill-defined, since it is relevant
in the context of the constraints it imposes over the space of distributions
generated by $\mathcal{M}^{*}$ (both observed and unobserved).

A Causal Bayesian Network (CBN, Def. 15) is a pair consisting of a causal
diagram $\mathcal{G}$ and a collection of layer 2 (interventional)
distributions $\mathbf{P}^{*}$, where the distributions follow a set of
constraints represented in the diagram (i.e., they are “compatible”).
Remarkably, the causal diagram induced by any SCM, along with its induced
layer 2 distributions, together form a valid CBN (Fact 2). Causal diagrams and
the constraints encoded in CBNs are often the fuel to causal inference methods
(e.g., do-calculus) and used to bridge the gap between layer 1 and layer 2
quantities. We refer readers to Appendix C.2 for a further discussion on these
inductive biases and their motivation, and [5, Sec. 1.3] for further
elaborations.

  5. Q5.

Based on the answer to Q4, it is not entirely clear what an NCM really
represents. Is an NCM a causal diagram? Or is it an SCM? Or should I think
about it in a different way?
Answer An NCM is not a causal diagram, and although an NCM is technically an
SCM, by definition, it may be helpful to think of it as a separate data
structure. As discussed above, SCMs contain strictly more information than
causal diagrams. Still, NCMs without $\mathcal{G}$-consistency (Def. 5) do not
even ascertain the constraints represented in $\mathcal{G}$ about layer 2
distributions. So, even though an NCM seems to appear like an SCM, it is an
“empty” data structure on its own. Whenever we impose
$\mathcal{G}$-consistency, NCMs may have the capability of generating
interventional distributions, contingent on $L_{1}$-consistency and the
identifiability status of the query.

More broadly, we think it is useful to think about an NCM as a candidate for a
proxy model for the true SCM. Unlike the SCM, the NCM’s concrete definitions
for functions and noise allow the NCM to be optimized (via neural optimization
procedures) for learning in practical settings. One additional difference
between the NCM and SCM is their purpose in causal inference. The SCM data
structure is typically used to represent reality, so in some sense, the SCM
has all information of interest from all layers of the PCH. Of course, this
reality is unobserved, so the SCM is typically unavailable for use. The NCM is
then trained as a proxy for the true SCM, so it has all of the functionality
of an SCM while being readily available. However, unlike the SCM, the
“quality” of the information in the NCM is dependent on the amount of input
information. If an NCM is only trained on data from layer 1, the Neural CHT
(Corol. 1) says that distributions induced by the NCM from higher layers will,
in general, be incorrect. For that reason, while the NCM has the same
interface as the SCM for the PCH, the NCM’s higher layers may be considered
“underdetermined”, in the sense that they do not contain any meaningful
information about reality.

  6. Q6.

Why do you assume the causal diagram exists instead of learning it? What if
the causal diagram is not available?
Answer.  As implied by the N-CHT (Corol. 1), cross-layer inferences cannot be
accomplished in the general case without additional information. In other
words, the causal diagram assumption is out of necessity. In general, one
cannot hope to learn the whole causal diagram from observational data either.
However, it is certainly not the case that the causal diagram will always be
available in real world settings. In such cases, other assumptions may be
necessary which may help structural learning, or perhaps the causal diagram
can be partially specified to a degree that allows answering the query of
interest (see also Footnotes 7 and 8).

  7. Q7.

Are NCMs assumed to be acyclic?
Answer. We assume for this work that the true SCM $\mathcal{M}^{*}$ is
recursive, meaning that the variables can be ordered in a way such that if
$V_{i}<V_{j}$, then $V_{j}$ is guaranteed to not be an input to $f_{V_{i}}$.
This implies that the causal diagram induced by $\mathcal{M}^{*}$ is acyclic,
so $\mathcal{G}$-constrained NCMs (from Def. 7) must also be recursive. That
said, not all works make the recursive assumption, so the general definition
of NCMs does not need to be constrained a priori.

  8. Q8.

Why is $\mathcal{M}^{*}$ assumed to be an SCM instead of an NCM in the
definition for neural identifiability (Def. 8)?
Answer. $\mathcal{M}^{*}$ indicates the ground truth model of reality, and we
assume that reality is modeled by an SCM, without any constraints in the form
of the functions or probability over the exogenous variables. The NCM is a
data structure that we constructed to solve causal inference problems, but the
inferences of interest are those from the true model. For this reason, several
results were needed to connect the properties of NCMs to those from SCMs,
including Thm. 2 (showing that NCMs can encode the same constraints as SCMs’
causal diagrams) and Thm. 3 (showing that NCMs can represent any
$\mathcal{G}$-consistent SCM on layer 2). These results are required to show
the validity (or meaning) of the inferences made from the NCM, which otherwise
would have no connection to the true model, $\mathcal{M}^{*}$.

Naturally, checking for identifiability within the space of NCMs defeats the
purpose of the work since the model of interest is not (necessarily) an NCM.
Conveniently, however, the expressiveness of the NCM (as shown in Thm. 3)
shows that if two SCMs agree on $P(\mathbf{V})$ and $\mathcal{G}$ but do not
agree on $P(\mathbf{y}\mid do(\mathbf{x}))$, then there must also be two NCMs
that behave similarly. This means that attempting to check for identifiability
in the space of NCMs will produce the correct result, which is why Alg. 1 can
be used. Still, interestingly, this may no longer be the case within a less
expressive model class (see Example 7 in Appendix C.3).

  9. Q9.

What is the purpose of Thm. 3 if we already have Thm. 1?
Answer. While Thm. 1 shows that NCMs (from Def. 3) can express any SCM on all
three layers of the PCH, it does not make any claims about
$\mathcal{G}$-constrained NCMs (Def. 7). In fact, a $\mathcal{G}$-constrained
NCM is obviously incapable of expressing any SCM that is not
$\mathcal{G}$-consistent. Thm. 3 emphasizes that even when encoding the
structural constraints in $\mathcal{G}$ (CBN-like), NCMs are still capable of
expressing any SCM that is also compatible with $\mathcal{G}$. If this
property did not hold, it would not always be possible to use the NCM as a
proxy for the SCM, since there may be some SCMs that are
$\mathcal{G}$-consistent, but there does not exist an NCM that matches the
corresponding distributions.

One important subtlety of Thm. 3 is that the expressiveness is described after
applying the constraints of $\mathcal{G}$. It may be relatively simple to use
a universal approximator to construct a model class that can express any SCM
on layer 2, such as the $L_{2}$-expression wrapper (Def. 21 from Appendix
D.2). However, the $L_{2}$-expression wrapper does not naturally enforce the
constraints of $\mathcal{G}$. Incorporating such constraints is nontrivial,
and even if the constraints were applied, the model class may no longer retain
its expressiveness. Thm. 3 shows that the NCM is the maximally expressive
model class that still respects the constraints of $\mathcal{G}$.

  10. Q10.

The objective function in Eq. 5 is not entirely clear. What role does
$\lambda$ play?
Answer. The purpose of Alg. 2 is to solve the optimization problem in lines 2
and 3 of Alg. 1. The goal can be described in two parts: maximize/minimize a
query of interest, like $P(\mathbf{y}\mid do(\mathbf{x}))$, while
simultaneously learning the observational distribution $P(\mathbf{V})$. This
is a nontrivial optimization problem, and there are many different ways to
approach it. The proposed method penalizes both of these quantities in the
objective. The first term of Eq. 5 attempts to maximize log-likelihood, while
the second term attempts to maximize/minimize $P(\mathbf{y}\mid
do(\mathbf{x}))$. Certainly, we do not want the optimization of the second
term to affect the optimization of the first term, since we need accurate
learning of $P(\mathbf{V})$ to make any deductions on the identifiability
status of $P(\mathbf{y}\mid do(\mathbf{x}))$ and subsequent estimation of it.

Further, the hyperparameter $\lambda$ is used to balance the amount of
attention placed on maximizing/minimizing $P(\mathbf{y}\mid do(\mathbf{x}))$.
If $\lambda$ is too small, then the term would be ignored, and the
optimization of $P(\mathbf{y}\mid do(\mathbf{x}))$ could fail even in non-ID
cases. On the other hand, if $\lambda$ is too large, the optimization
procedure might attempt to maximize/minimize $P(\mathbf{y}\mid
do(\mathbf{x}))$ at the expense of learning $P(\mathbf{V})$ properly, which
may result in incorrect inferences in ID cases. Our solution starts $\lambda$
at a large value to allow the optimization to quickly find parameters that
maximize/minimize $P(\mathbf{y}\mid do(\mathbf{x}))$, and then it lowers
$\lambda$ as training progresses so that $P(\mathbf{V})$ is learned accurately
by the end of training.

  11. Q11.

Why would one want, or prefer, to solve identifiability using NCMs? Would it
not be easier to use existing results (e.g., do-calculus) to determine the
identifiability of a query, then use the NCM for estimation?
Answer. We provide a more detailed discussion on this topic in Appendix C.4.
In summary, when solving causal problems like identification or estimation, we
introduced a new framework using NCMs where one can construct a proxy model to
mimic the true SCM via neural optimization. Meanwhile, existing works focus on
solving the problems at a higher-level of abstraction with the causal diagram,
ignoring the true SCM. We call these works “symbolic” since they directly use
the constraints of the causal diagram to algorithmically derive a solution. We
are not deciding for the causal analyst which method to use when comparing
symbolic and optimization-based methods. For instance, we developed Alg. 4 as
an alternative to Alg. 1 for researchers who would prefer to use a symbolic
approach for identification while using an NCM for estimation.

We note that the identification and estimation tasks typically appear together
in practice, and it is remarkable that the proxy-model framework with NCMs is
capable of solving the entire causal pipeline. In some sense, the
identification task provides the causal reasoning required to perform
estimation. Once a query is determined to be identifiable, the estimation task
is only a matter of fitting an expression. It may be somewhat unsurprising
that the expressiveness of neural networks along with its strong optimization
results allow it to fit any expression, but this work shows, for the first
time, that neural nets are also capable of performing the causal reasoning
required to determine identifiability. We note that Alg. 1 describes a
procedure for solving the ID problem that is unique compared to symbolic
approaches. Our goal with Alg. 1 is to provide insights to alternative
approaches to causal problems under the proxy model framework compatible with
optimization methods.

  12. Q12.

Why would one want to learn an entire SCM to solve the estimation problem for
a specific query? Shouldn’t the efforts be focused on estimating just the
query of interest?
Answer.  Indeed, existing works typically focus on a single interventional
distribution and also abstract out the SCM, as shown in Fig. 15. In
particular, solutions to the identification problem typically derive an
expression for the query of interest using the causal diagram, and solutions
to the estimation problem directly evaluate the derived expression.

One of the novelties of this work is the introduction of a method of solving
these tasks using a proxy model of the SCM. Compared to existing methods,
there are a number of reasons one may want to have a proxy model. For
instance, one may want to have generative capabilities of both layer 1 and
identifiable layer 2 distributions rather than simply obtaining a probability
value. We refer readers to Appendix C.4 for a more detailed discussion.

  13. Q13.

It appears that the theory and results only hold if learning is perfect. What
happens if there is error in training?
Answer. This work does not make any formal claims regarding cases with error
in training. Still, one of our goals with the experiments of Sec. 5 is to show
empirically that results tend to be fairly accurate if training error is
minimized to an acceptable degree (i.e., $L_{1}$-consistency nearly holds). A
more refined understanding and detailed theoretical analysis of robustness to
training error is an interesting direction for future work.