Use of Prior Knowledge to Discover Causal Additive Models with Unobserved Variables and its Application to Time Series Data

Causal additive noise models with unobserved variables (CAM-UV) pmlr-v161-maeda21a ; maeda2021discovery are defined as the equation below:

where $V=\{V_{i}\}$ is the set of observed or unobserved variables, $X=\{X_{i}\}$ the set of observed variables, $U=\{U_{i}\}$ is the set of unobserved variables, $N_{i}$ is the external effect on $V_{i}$, $opa(V_{i})\subset X$ is the set of observed direct causes (observed parents) of $V_{i}$, $upa(V_{i})\subset U$ is the set of unobserved direct causes (unobserved parents) of $V_{i}$, and $f_{i,j}$ is a nonlinear function. Additionally, Assumption 1 is imposed on CAM-UV.

Time-series causal additive noise models with unobserved variables (TS-CAM-UV) are stationary discrete-time structural causal models that can be described as below:

where $t$ and $s$ are time indices, $m$ is a natural number, $V=\{V_{i}^{t}\}$ is the set of observed or unobserved variables, $X=\{X_{i}^{t}\}$ is the set of observed variables, $U=\{U_{i}^{t}\}$ is the set of unobserved variables, $f_{i,t,j,s}$ is a nonlinear function, the noise variables $N_{i}^{t}$ are jointly independent, $opa(V_{i}^{t})\subset X$ is the set of direct causes of $V_{j}^{t}$, and $upa(V_{i}^{t})\subset U$ is the set of direct causes of $V_{j}^{t}$.

The stationarity of time-series causal relationships is assumed as the following: The causal relationship of the variable pair $(V^{t-\epsilon}_{i},V^{t}_{j})$ is the same as that of all the time shifted pairs $(V^{t^{\prime}-\epsilon}_{i},V^{t^{\prime}}_{j})$. The causal effect of $V^{s}_{j}$ on $V^{t}_{i}$ is called a lagged effect if $s<t$ holds, and is called a contemporaneous effect if $t=s$ holds. It is also assumed that there is a natural number $r$ as the maximum time lag such that the longest time lag of the direct causal effects does not exceed $r$. While it is true that the cause precedes the effect in time, if the time slice of the data analyzed are not sufficiently short, the cause and effect may appear to occur simultaneously. This type of causal effect, where the time difference between the cause and effect is shorter than the time slice of data, is referred to as a contemporaneous effect.

The identifiability of CAM-UV is discussed in pmlr-v161-maeda21a ; maeda2021discovery , and this section briefly presents it. When the causal relationship is linear, an observed variable $X_{j}$ being an indirect cause of an observed variable $X_{i}$, even if there is an unobserved variable $U_{k}$ in the causal path such that the causal relationship is $X_{j}\rightarrow U_{k}\rightarrow X_{i}$, the residual when regressing $X_{i}$ on $X_{j}$ becomes independent of $X_{j}$. However, in the case of a non-linear causal relationship, the residual when regressing $X_{i}$ on $X_{j}$ cannot be independent of $X_{j}$. This is referred to as cascade additive noise models (CANMs) ijcai2019p223 . Therefore, in the case of non-linear causal relationships, compared to linear ones, there are more instances where causal relationships cannot be identified using only regression and independence tests. Before discussing the cases where causal relationships cannot be identified in CAM-UV, we define unobserved causal paths (UCPs) and unobserved backdoor paths (UBPs) which are illustrated in Fig. 1 and used in the lemmas in this section.

The identifiability of CAM-UV is based on Lemmas 1–3 shown below. They show that it is possible to identify the direct causal relationship between two variables if they do not have a UCP or a UBP, otherwise it is impossible to identify the direct direct causal relationship but possible to identify the presence of a UCP or a UBP. This is due to the fact that when the causal relationship is non-linear, if the parent of an observed variable $X_{i}$ is an unobserved variable $U_{j}$, the ancestral variables of $U_{j}$ cannot be removed from $X_{i}$ by regression. Lemma 1 is about the condition of variable pair $(X_{i},X_{j})$ having a UCP or a UBP. Lemma 2 is about the condition of variable pair $(X_{i},X_{j})$ not having a UBP, a UCP, or a direct causal relationship. Lemma 3 is about the condition that $X_{j}$ is a direct cause of $X_{i}$, and they do not have a UCP or a UBP. Please refer to maeda2021discovery for the proofs of the lemmas.

The identifiability of causality in TS-CAM-UV is the same as in CAM-UV. Lemmas 4–6 on identifiability in TS-CAM-UV correspond to Lemmas 1–3 on identifiability in CAM-UV.

This section proposes a method called CAM-UV using prior knowledge (CAM-UV-PK). This method is for discovering causal additive models with unobserved models defined in Section 3.1. In addition to the arguments of the CAM-UV algorithm, the CAM-UV-PK algorithm requires an argument ${\mathbf{T}}$ that is a list of ordered variable pairs. If a ordered variable pair $(X_{i},X_{j})$ is included in ${\mathbf{T}}$, it means that it is assumed that $X_{i}$ cannot be a direct or indirect cause of $X_{j}$.

The CAM-UV algorithm and CAM-UV-PK algorithm output causal graphs with directed edges and undirected dashed edges. Directed edges indicate variable pairs having direct causal relationships, and undirected dashed edges indicate variable pairs having UCPs or UBPs. For example, Figure 2-(a) shows a true causal graph, and Figure 2-(b) shows the causal graph generated by the CAM-UV algorithm. $X_{2}$ and $X_{3}$ have a UBP ($X_{2}\leftarrow U_{1}\rightarrow X_{3}$), so they are connected with an undirected dashed path in Figure 2-(b). $X_{4}$ and $X_{9}$ have a UCP ($X_{4}\rightarrow U_{7}\rightarrow X_{9}$), so they are also connected with an undirected dashed path in Figure 2-(b).

The CAM-UV-PK algorithm incorporates restriction using prior knowledge ${\mathbf{T}}$ into the process of causal inference in the CAM-UV algorithm. The CAM-UV algorithm has two-step algorithm pmlr-v161-maeda21a ; maeda2021discovery . The first step determines the directed edges, and the second one determines the undirected dashed edges. There is no difference in the second step between the CAM-UV-PK algorithm and the CAM-UV algorithm. The first step of the CAM-UV-PK algorithm is listed in Algorithm 1. Lines 14–16 in Algorithm 1 are added to the CAM-UV algorithm. This part of the algorithm refers to the prior knowledge ${\mathbf{T}}$ to avoid considering unnecessary causal candidates. The method extracts the candidates of the direct causes (parents) of each variable (lines 2–34) and determines the direct causes of each variables (lines 35–41). The method identifies the most endogenous variable $X_{b}$ in each $K\in\{K|K\subseteq X,|K|=t\}$. When $X_{i}=x_{b}$ is satisfied, $X_{i}$ maximizes $\savestack{\tmpbox}{\stretchto{\scaleto{\scalerel*[\widthof{\text{p-HSIC}}]{\kern-0.6pt\bigwedge\kern-0.6pt}{\rule[-505.89pt]{4.30554pt}{505.89pt}}}{}}{0.5ex}}\stackon[1pt]{\text{p-HSIC}}{\tmpbox}(X_{i}-G_{1}(M_{i}\cup K\setminus\{X_{i}\}),\{X_{j}-G_{2}(M_{j})|X_{j}\in K\setminus\{X_{i}\}\})$. In lines 14–16 which are newly added in CAM-UV-PK, the method checks whether there exists $X_{j}\in K\setminus\{X_{i}\}$ that cannot be a direct or indirect cause of $X_{i}$ according to the prior knowledge ${\mathbf{T}}$. If $(X_{j},X_{i})\in{\mathbf{T}}$ is satisfied, the method stops checking whether $X_{i}$ is endogenous to $K\setminus\{X_{i}\}$. Therefore, this check prevents incorrect inference of causal relationships.

This section proposes a method called the time-series CAM-UV (TS-CAM-UV) algorithm. The TS-CAM-UV algorithm uses as prior knowledge the assumption, called time priority, that effect does not precede its cause in time. The TS-CAM-UV algorithm uses the CAM-UV-PK algorithm, and the prior knowledge of time priority is used for the argument of the CAM-UV-PK, ${\mathbf{T}}$.

The TS-CAM-UV algorithm first creates data with $q\times(r+1)$ variables where $q$ is the number of the variables of original data, and $r$ is the maximal considered time lag given as an argument. Let ${\mathbf{X}_{t}}=\{X^{t}_{1},\cdots,X^{t}_{q}\}$ denote the variables in original data. The TS-CAM-UV algorithm creates data with variables $\mathbf{X}^{\rm new}=\{X^{t}_{1},\cdots,X^{t}_{q},X^{t-1}_{1},\cdots,X^{t-1}_{q},\cdots,X^{t-r}_{1},\cdots,X^{t-r}_{q}\}$. Therefore, the number of the new samples decreases to $n-r$ where $n$ denotes the number of original data. Then, the TS-CAM-UV algorithm creates a list of ordered variables $K=\{(X^{t}_{i},X^{t^{\prime}}_{j})|t>t^{\prime},0\leq i\leq q,0\leq j\leq q,\}$.

The TS-CAM-UV algorithm uses $\mathbf{X}^{\rm new}$ and $K$ for the arguments of CAM-UV-PK ${\mathbf{X}}$ and ${\mathbf{T}}$, respectively. Then, CAM-UV-PK outputs a causal graph of the $q$ variables with $r$ time lag.

We examined the performance of CAM-UV-PK compared to CAM-UV using simulated data. We compared and evaluated the performance of CAM-UV-PK with prior knowledge ranging from 0 to 4. The CAM-UV algorithm is the same as the CAM-UV-PK algorithm with no input of prior knowledge. We performed 100 experiments using artificial data with each sample size $n\in\{100,200,\cdots,900,1000\}$ to compare our method to existing methods. In each experiment, the samples are created as follows:

• •

  The number of observed variables is 10.

• •

  The number of the observed variable pairs having unobserved common causes is 4.

• •

  The number of observed variable pairs having unobserved causal intermediate variables is 2.

• •

  The number of the observed variable pairs having direct causal effects is 10.

• •

  Variable pairs having unobserved common causes, unobserved intermediate causal variables, or direct causal relationships were randomly selected under the restriction that the set of variable pairs with unobserved common causes, the set of variable pairs with unobserved intermediate causal variables, and the set of variable pairs with direct causal relationships were mutually disjoint.

• •

  The causal effect of $V_{j}$ on $V_{i}$ is determined as follows:

  $$\left(\sin\left(a_{1}\left(V_{j}+b_{1}\right)\right)\right)^{3}c_{1}+\left(\frac{1}{1+\exp(-a_{2}(V_{j}+b_{2}))}-0.5\right)c_{2}$$

  (11)

  where $a_{1}$, $a_{2}$, $b_{1}$, $b_{2}$, $c_{1}$, and $c_{1}$ are constants that take random value for each $(i,j)$. Constants $a_{1}$ and $a_{2}$ are taken from $U(9,11)$, $b_{1}$ and $b_{2}$ are taken from $U(-0.1,0.1)$, and $c_{1}$ and $c_{2}$ are taken from $U(3,5)$. This function is also used in experiments to validate the TS-CAM-UV algorithm in the next section so that causal effects do not converge or diverge over time.

The arguments of TS-CAM-UV, $\alpha$ (significance level for independence test) and $d$ (maximal number of variables to examine causality for each step) are set to 0.01 and 2, respectively.

We compared the performance of the identification of direct causal relationships. We used precision, recall, and F-measure as the evaluation measures. True positive (TP) is the number of true directed edges that a method correctly infers in terms of their positions and directions. Precision represents the TP divided by the number of estimations, and recall represents the TP divided by the number of all the true directed edges. Furthermore, F-measure is defined as $\text{F-measure}=2\cdot\text{precision}\cdot\text{recall}/(\text{precision}+\text{recall})$. In each experiment, out of the ten variable pairs with direct causal relationships, four were excluded from the evaluation. These four causal relationships were used as prior knowledge in CAM-UV-PK.

Fig. 3 shows the results of the identification of direct causal relationships. The figure plots the average of precision, recall, and F-measure. It can be seen that precision and F-measure increase with the number of prior knowledge. The CAM-UV algorithm is the CAM-UV-PK algorithm without prior knowledge, and this has the lowest precision and F-measure. The number of prior knowledge does not significantly affect recall.

The above experimental results of the CAM-UV-PK algorithm confirm that the number of prior knowledge improves the precision and F-measure of the identification of direct causal relationships.

We examined the performance of TS-CAM-UV compared to LPCMCI and VarLiNGAM using simulated data and real-world data. For LPCMCI, two methods of conditional independence test were used for the comparison: Partial correlation test (ParCorr) and Gaussian process regression and a distance correlation test on the residuals (GPDC). ParCorr assumes linear additive noise models, and GPDC assumes nonlinear additive noise models.