Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
80,939 characters · 32 sections · 72 citation commands
Variable-lag Granger Causality and Transfer Entropy for Time Series Analysis
\orcid{0000-0003-3131-0370} \email{[email removed]}
\email{[email removed]}
\email{[email removed]}
\ccsdesc[500]{Information systems Spatial-temporal systems} \ccsdesc[500]{Information systems Data mining} \ccsdesc[300]{Computing methodologies Cooperation and coordination}
Inferring causal relationships from data is a fundamental problem in statistics, economics, and science in general. The gold standard for assessing causal effects is running randomized controlled trials which randomly assign a treatment (e.g., a drug or a specific user interface) to a subset of a population of interest, and randomly select another subset as a control group which is not given the treatment, thus attributing the outcome difference between the two groups to the treatment. However, in many cases, running such trials may be unethical, expensive, or simply impossible Varian7310. To address this issue, several methods have been developed to estimate causal effects from observational data pearl2000causality,Spirtes1993.
In the context of time series data, a well-known method that defines a causal relation in terms of predictability is Granger causality granger1969investigating. $X$ Granger-causes $Y$ if past information on $X$ predicts the behavior of $Y$ better than $Y$'s past information alone Arnold:2007:TCM:1281192.1281203. In this work, when we refer to causality, we mean specifically the predictive causality defined by Granger causality. The key assumptions of Granger causality are that 1) the process of effect generation can be explained by a set of structural equations, and 2) the current realization of the effect at any time point is influenced by a set of causes in the past. Similar to other causal inference methods, Granger causality assumes unconfoundedness and that all relevant variables are included in the analysis granger1969investigating,peters2017elements.
There are several studies that have been developed based on Granger causality liu2012sparse,atukeren2010relationship,peters2013causal.
Granger causality is typically studied in the context of linear structural equations. Transfer Entropy has been developed as a non-linear extension of Granger causality schreiber-prl00,lee2012transfer,PhysRevLett.103.238701.
The typical operational definitions atukeren2010relationship and inference methods for inferring Granger causality, including the common software implementation packages MLSourcecode,RSourcecode, assume that the effect is influenced by the cause with a fixed and constant time delay.
However, the assumption of an effect is fixed-lag influenced by the cause still exists in both Granger causality and transfer entropy.
This assumption of a fixed and constant time delay between the cause and effect is, in fact, too strong for many applications of understanding natural world and social phenomena. In such domains, data is often in the form of a set of time series and a common question of interest is which time series are the (causal) initiators of patterns of behaviors captured by another set of time series. For example, who are the individuals who influence a group's direction in collective movement? What are the sectors that influence the stock market dynamics right now? Which part of the brain is critical in activating a response to a given action? In all of these cases, effects follow the causal time series with delays that can vary over time FLICAtkdd. The fact that one time series can be caused by multiple initiators and these initiators can be inferred from time series data FLICAtkdd,Arnold:2007:TCM:1281192.1281203.
To address the remaining gap, we introduce the concepts Variable-lag Granger causality and Variable-lag Transfer Entropy and methods to infer them in time series data. We prove that our definitions and the proposed inference methods can address the arbitrary-time-lag influence between cause and effect, while the traditional operationalizations of Granger causality, transfer entropy, and their corresponding inference methods cannot. We show that the traditional definitions are indeed special cases of the new relations we define. We demonstrate the applicability of the newly defined causal inference frameworks by inferring initiators of collective coordinated movement, a problem proposed in FLICAtkdd, as well as inferring casual relations in other real-world datasets.
We use Dynamic Time Warping (DTW) sakoe1978dynamic to align the cause $X$ to the effect time series $Y$ while leveraging the power of Granger causality and transfer entropy. In the literature, there are many clustering-based Granger causality methods that use DTW to cluster time series and perform Granger causality only for time series within the same clusters yuan2016deep,Peng:2007:SSI:1288552.1288557. Previous work on inferring causal relations using both Granger causality and DTW has the assumption that the smaller warping distance between two time series, the stronger the causal relation is sliva2015tools. If the minimum distance of elements within the DTW optimal warping path is below a given distance threshold, then the method considers that there is a causal relation between the two time series. However, their work assumes that Granger causality and DTW run independently. In contrast, our method formalizes the integration of Granger causality and DTW by generalizing the definition of Granger causality itself and using DTW as an instantiation of the optimal alignment requirement of the time series.
In addition to the standard uses of Granger causality and transfer entropy, our methods are capable of:
We also prove that when multiple time series cause the behavioral convergence of a set of time series then we can treat the set of these initiating causes in the aggregate and there is a causal relation between this aggregate cause (of the set of initiating time series) and the aggregate of the rest of the time series. We provide many experiments and examples using both simulated and real-world datasets to measure the performance of our approach in various causality settings and discuss the resulting domain insights. Our framework is highly general and can be used to analyze time series from any domain.
Granger causality has inspired a lot of research since its introduction in 1969 granger1969investigating. Recent works on Granger causality has focused on various generalizations for it, including ones based on information theory, such as transfer entropy schreiber-prl00,shibuya-kdd09 and directed information graphs 7273888. Recent inference methods are able to deal with missing data iseki-aaai19 and enable feature selection Sun2015. Granger causality has even been explored as a method to offer explainability of machine learning models schwab-aaai19. However, none of them study tests for Variable-lag Granger causality, as we formalize and propose in this work.
Many causal inference methods assume that the data is {\em i.i.d.} and rely on knowing a mechanism that generates that data, e.g., expressed through causal graphs or structural equations pearl2000causality. In time series data, there are two ways in which time series can be {\em i.i.d.}: 1) the points of one time series are independent of other points in the same time series, 2) one time series is independent of another time series. Obviously, in most time series, the values of the consecutive time steps violate the {\em i.i.d.} assumption (the first way). In causal inference, the field focuses on the independent between two time series in the second way.
Another set of causal inference methods relax this strong {\em i.i.d} assumption, and instead assume independence between the cause and the mechanism generating the effect janzing2010causal,scholkopf2012causal,shajarisales2015telling. Specifically, knowing a distribution of random variable of cause $X$ never reveals information about the structural function $f(X)$ and vice versa. This idea has been used in the context of times series data shajarisales2015telling by relying on the concept of Spectral Independence Criterion (SIC). If a cause $X$ is a stationary process that generates the effect $Y$ via linear time invariance filter $h$ (mechanism), then $X$ and $h$ should not contain any information about each other but dependency between them and $Y$ exists in spectral sense.
There is a framework of causal inference in malinsky2018causal based on conditional independence tests on time series generated from some discrete-time stochastic processes that allows unknown latent variables. However, the approach in malinsky2018causal still assumes that data points at any time step have been generated from some structural vector autoregression (SVAR). The recent work in griveau2019efficient models causal relation between time series as a form of polynomial function and uses a stochastic block model to find a causal graph. Both works, however, still have the assumption of fixed-lag influence from causes to effects.
Besides, no method studies a causal structure that is unstable\footnote{Unstable causal structures means a relation between effect and causes can be changed overtime. In other words, given time series $X$ causes $Y$, $Y(t)=f(X_1,\dots,X_{t-1})$ and $Y(t')=f'(X_1,\dots,X_{t-1})$ where $t\neq t'$, $f$ and $f'$ might not be the same. } overtime doi:10.1098/rsta.2011.0613.
Moreover, Transfer Entropy, which is considered to be a non-linear extension of Granger causality schreiber-prl00,lee2012transfer,PhysRevLett.103.238701, still has the fixed-lag assumption.
In our work, we also relax the stationary assumption of time series.
This paper is an extension of our conference proceeding VLGranger. In our previous work VLGranger, we formalized VL-Granger causality and proposed a framework to infer a causal relation using BIC and F-test as main criteria to infer whether $X$ causes $Y$.
In this work, we formalize Variable-Lag Transfer Entropy, which is a non-linear extension of Granger-causality. We investigate the challenge of generalizing Transfer Entropy by relaxing its fixed-lag assumption. Then, we propose a framework to infer VL-Transfer Entropy causal relations.
Moreover, we extend our work on VL-Granger Causality and propose to use a Bayesian Information Criterion difference ratio or BIC difference ratio, which is a normalized BIC, as a main criterion. There is evidence that BIC performs better than other model-selection criteria in general raffalovich2008model,granger2004forecasting,atukeren2010relationship. We also add two new real-world datasets and additional experiments in this current work.
Let $X=(X(1),\dots,X(t),\dots)$ be a time series. We will use $X(t)\in \mathbb{R}$ to denote an element of $X$ at time $t$. Given two time series $X$ and $Y$, it is said that $X$ Granger-causes granger1969investigating $Y$ if the information of $X$ in the past helps improve the prediction of the behavior of $Y$, over $Y$'s past information alone Arnold:2007:TCM:1281192.1281203. The typical way to operationalize this general definition of Granger causality atukeren2010relationship is to define it as follows:
This definition assumes that, for all $t>0$, $Y(t)$ can be predicted by the fixed linear combination of $a_1Y(1),\dots,a_{t-\Delta}Y(t-\Delta)$ and $b_1X(1),\dots,b_{t-\Delta}X(t-\Delta)$ with some fixed $\Delta>0$ and every $a_i,b_i$ is a fixed constant over time atukeren2010relationship,Arnold:2007:TCM:1281192.1281203. However, in reality, two time series might influence each other with a sequence of arbitrary, non-fixed time lags. For example, Fig. (ref)(a2.) has $X$ as a cause time series and $Y$ as the effect time series that imitates the values of $X$ with arbitrary lags. Because $Y$ is not affected by $X$ with a fixed lags and the linear combination above can change over time, the standard Granger causality tests cannot appropriately infer Granger-causal relation between $X$ and $Y$ even if $Y$ is just a slightly distorted version of $X$ with some lags. For a concrete example, consider a movement context where time series represent trajectories. Two people follow each other if they move in the same trajectory. Assuming the followers follow leaders with a fixed lag means the followers walk lockstep with the leader, which is not the natural way we walk. Imagine two people embarking on a walk. The first starts walking, the second catches up a little later. They may walk together for a bit, then the second stops to tie the shoe and catches up again. The delay between the first and the second person keeps changing, yet there is no question the first sets the course and is the cause of the second's choices where to go. Fig. (ref) illustrates this example.
Here, we propose the concept of variable-lag Granger causality, VL-Granger causality for short, which generalizes the Granger causal relation of Definition (ref) in a way that addresses the fixed-lag limitation. We demonstrate the application of the new causality relation for a specific application of inferring initiators and followers of collective behavior.
In order to make Definition (ref) fully operational for this more general case (and to find the optimal constants values), we need a similarity function between two sequences which will define the optimal alignment. We propose such a similarity-based approach in Definition (ref). Before defining this approach, we show that VL-Granger causality is the proper generalization of the traditional operational definition of Granger causality stated in Definition (ref). Clearly, assuming that all delays are less than $\delta_{max}$, if all the delays are constant, then $r^*_{YX}(t)=r_{YX}(t)$.
We must also show that the variance of $r^*_{YX}(t)$ is no greater than the variance of $r_{YX}(t)$.
According to Propositions (ref) and (ref), VL-Granger causality is the generalization of the Def. (ref) and always has lower or equal variance.
Of a particular interest is the case when there is an explicit similarity relation defined over the domain of the input time series. The underlying alignment of VL-Granger causality then should incorporate that similarity measure and the methods for inferring the optimal alignment for the given similarity measure.
Note, here the $\mbox{sim}$ similarity function does not have to be a distance function that obeys, among others, a triangle inequality. It can be any function that quantitatively compares the two time series. For example, it may be that when one time series increases the other decreases. We provide a more concrete and realistic example in the application setting below.
Adding this similarity measure to Definition (ref) allows us to instantiate the notion of the optimal alignment $P^*$ as the one that maximizes the similarity between $X$ and $Y$:
where $\tilde{X}(t)=X(t-\Delta_t)$ for any given $P$ and $\Delta_t \in P$. With that addition, if $X\prec Y$, then $X$ VL-Granger-causes $Y$. This allows us to operationalize VL-Granger causality by checking for variable-lag emulation, as we describe in the next section.
In this section, we demonstrate an application of the VL-Granger causal relation to finding initiators of collective behavior. The Variable-lag emulation concept corresponds to a relation of following in the leadership literature FLICAtkdd. That is, $X\prec Y$ if $Y$ is a {\em follower} of $X$. We are interested in the phenomenon of group convergence to a consensus behavior and answering the question of which subset of individuals, if any, initiated that collective consensus behavior. With that in mind, we now define the concept of an initiator and provide a set of subsidiary definitions that allow us to formally show (in Proposition (ref)) that initiators of collective behavior are indeed the time series that VL-Granger-cause the collective pattern in the set of the time series. In order to do this, we generalize our two-time series definitions to the case of multiple time series by defining the notion of an aggregate time series, which is consistent with previous Granger causality generalizations to multiple time series siggiridou2016granger,doi:10.1098/rsta.2011.0613,chen2004analyzing.
Given a set of time series $\mathcal{U}=\{U_{1},\dots,U_{n}\}$ , and a set of time series $\mathcal{X}\subseteq\mathcal{U}$, we can define an aggregate time series as a time series of means at each step:
In order to identify the state of reaching a collective consensus of a time series, while allowing for some noise, we adopt the concept of $\epsilon$-convergence from doi:10.1137/100791671.
We are finally ready to state the main connection between initiation of collective behavior and VL-Granger causality.
We have now shown that a subset of time series are initiators of a pattern of collective behavior of an entire set if that subset VL-Granger-causes the behavior of the set. Thus, VL-Granger causality can solve the {\sc Coordination Initiator Inference Problem}\xspace FLICAtkdd, which is a problem of determining whether a pattern of collective behavior was spurious or instigated by some subset of initiators and, if so, finding those initiators who initiate collective patterns that everyone follows.
In this section, we generalize our concept of VL-Granger causality to the non-linear extension of Granger causality, Transfer Entropy lee2012transfer,PhysRevLett.103.238701. Given two time series $X$ and $Y$, and a probability function $p(\cdot)$, the Transfer Entropy from $X$ to $Y$ is defined as follows:
Where $H(\cdot\mid\cdot)$ is a conditional entropy, $k,l$ are lag constants, $Y_{t-1}^{(k)}=Y(t-1),\dots,Y(t-k)$, and $X_{t-1}^{(l)}=X(t-1),\dots,X(t-l)$.
One of the most common types of entropy is Shannon entropy 6773024, based on which the function $H(\cdot)$ is defined as
Based on this function, the Shannon transfer entropy BEHRENDT2019100265,lee2012transfer is:
Typically, we infer whether $X$ causes $Y$ by comparing $\mathcal{T}_{X\xrightarrow{} Y}$ and $\mathcal{T}_{Y\xrightarrow{} X}$. If $\mathcal{T}_{X\xrightarrow{} Y}>\mathcal{T}_{Y\xrightarrow{} X}$, then we state that $X$ causes $Y$. However, transfer entropy is also limited by the fixed-lag assumption. Equation (ref) shows a comparison between $Y(t)$ and $Y_{t-1}^{(k)}$ and $X_{t-1}^{(l)}$ and no variable lags are allowed. Therefore, we formalize the Variable-lag Transfer Entropy or VL-Transfer entropy function as below:
Where $\tilde{X}_{t-1}^{(l)}=X(t-1-\Delta_{t-1}),\dots,X(t-l-\Delta_{t-l})$ for a given $P$, $\Delta_t \in P$, and , $\Delta_t > 0$.
Hence, Variable-lag Transfer Entropy function generalizes the transfer entropy function. To find an appropriate $P$, we can use $P^*$ in Eq. (ref) that is a result of alignment of time series $X$ along with $Y$. The $P^*$ in Eq. (ref) represents a sequence of time delay that matches the most similar pattern of time series $X$ with the pattern in time series $Y$ where the pattern of $X$ comes before the pattern of $Y$.
Given a target time series $Y$, a candidate causing time series $X$, a threshold $\sigma$, a significance threshold $\alpha$ (or other threshold if we do not use statistical testing), the max lag $\delta_{max}$, and the linear flag $linearFLAG$, our framework evaluates whether $X$ variable-lag causes $Y$, $X$ fixed-lag causes $Y$ or no conclusion of causation between $X$ and $Y$ using either Granger causality or Transfer Entropy, which is a non-linear extension of Granger causality. In Algorithm (ref), users can set either $linearFLAG=true$ to run Granger causality or $linearFLAG=false$ for Transfer Entropy. \\
For $linearFLAG=true$, in Algorithm (ref) line 2-3, we have a fix-lag parameter $FixLag$ that controls whether we choose to compute the normal Granger causality ($FixLag=true$) or VL-Granger causality ($FixLag=false$). For $linearFLAG=false$, in the line 5-6, we compute Transfer Entropy if $FixLag=true$. Otherwise, we compute whether $X$ causes $Y$ w.r.t. VL-Transfer Entropy.
We present the high level logic of the algorithm. However, the actual implementation is more efficient by removing the redundancies of the presented logic.\\
For $linearFLAG=true$, first, we compute Granger causality (line 2 in Algorithm (ref)) using a function in Section (ref). The flag $fixLagResult=true$ if $X$ Granger-causes $Y$, otherwise $fixLagResult=false$. Second, we compute VL-Granger causality (line 3 in Algorithm (ref)). The flag $VLResult=true$ if $X$ VL-Granger-causes $Y$, otherwise, $VLResult=false$. Third, in line 4 in Algorithm (ref), based on the work in atukeren2010relationship, we use the Bayesian Information Criteria (BIC) to compare the residual of regressing $Y$ on $Y$ past information, $r_Y$, with the residual of regressing $Y$ on $Y$ and $X$ past information $r_{YX}$. We use $v_1 \ll v_2$ to represent that $v_1$ is less than $v_2$ with statistical significance by using some statistical test(s) or criteria. If $BIC(r_Y)\ll BIC(r_{YX})$, then we conclude that the prediction of $Y$ using $Y,X$ past information is better than the prediction of $Y$ using $Y$ past information alone. For this work, to determine $BIC(r_Y)\ll BIC(r_{YX})$, we use Bayesian Information Criterion difference ratio (see Section (ref)). If $BIC(r_Y)\ll BIC(r_{YX})$, then $VLflag=true$, otherwise, $VLflag=false$. \\
For $linearFLAG=false$, first, we compute Transfer Entropy causality (line 5 in Algorithm (ref)) using a function in Section (ref). The flag $fixLagResult=true$ if $X$ causes $Y$ in Transfer Entropy, otherwise, $fixLagResult=false$. Second, we compute VL-Transfer-Entropy causality (line 6 in Algorithm (ref)). The flag $VLResult=true$ if $X$ causes $Y$ in VL-Transfer Entropy, otherwise, $VLResult=false$. To determine whether $X$ causes $Y$ in Transfer Entropy, we use the Transfer Entropy Ratio (see Section (ref)).
In line 7, if the normal Transfer Entropy ratio is less than the VL-Transfer Entropy ratio, then $VLflag=true$, otherwise, $VLflag=false$. \\
Note that $VLflag=true$ when the result of variable-lag version is better than the fixed-lag version in both Granger causality and Transfer Entropy.
Using the results of $fixLagResult$, $VLResult$, and $VLflag$, we proceed to report the conclusion of causal relation between $X$ and $Y$ w.r.t. the following four conditions.
{0pt} \IncMargin{1em} \begin{algorithm2e} \caption{Time-lag test function} \SetKwInOut{Input}{input}\SetKwInOut{Output}{output} \Input{ $X,Y$, $\sigma$, $\gamma$ (or $\alpha$), $\delta_{max}$, $linearFLAG$ } \Output{$XCausesY$}
\end{algorithm2e}\DecMargin{1em}
Note that we assume the maximum lag value $\delta_{\max}$ is given as an input, as it is for all definitions of both Granger causality and Transfer Entropy. For practical purposes, a value of a large fraction ({\em e.g., } half) of the length of the time series can be used. However, there is, of course, a computational trade-off between the magnitude of $\delta_{\max}$ and the time it takes to compute both Granger causality and Transfer Entropy.
Next, we describe the details of the VL-Granger function used in Algorithm (ref): line 1-2. Given two time series $X$ and $Y$, a threshold $\gamma$ (or a significance level $\alpha$ if we use F-test), the maximum possible lag $\delta_{max}$, and whether we want to check for variable or fixed lag $FixLag$, Algorithm (ref) reports whether $X$ causes $Y$ by setting $GrangerResult$ to be true or false, and by reporting on two residuals $r_{Y}$ and $r_{YX}$.
First, we compute the residual $r_Y$ of regressing of $Y$ on $Y$'s information in the past (line 1). Then, we regress $Y(t)$ on $Y$ and $X$ past information to compute the residual $r_{YX}$ (line 2). If $BIC(r_{YX}) \ll BIC(r_{Y})$, then $X$ Granger-causes $Y$ and we set $GrangerResult=true$ (line 7). If $FixLag$ is true, then we report the result of typical Granger causality. Otherwise, we consider VL-Granger causality (lines 3-5) by computing the emulation relation between $X^{DTW}$ and $Y$ where $X^{DTW}$ is a version of $X$ that is reconstructed through DTW and is most similar to $Y$, captured by $DTWReconstructionFunction(X,Y)$ which we explain in Section (ref).
Afterwards, we do the regression of $Y$ on $X^{DTW}$'s past information to compute residual $r_{DTW}$ (line 4). Finally, we check whether $BIC(r_{DTW}) \ll BIC(r_{Y})$ (line 6-9) (see Section (ref)). If so, $X$ VL-Granger-causes $Y$. Additionally, after running $DTWReconstructionFunction(X,Y)$, we might check the condition $simValue\geq\sigma$ in order to claim that whether $X$ VL-Granger-causes $Y$ and ${X \preceq Y}$.
In the next section, we describe the details of how to construct $X^{DTW}$ and how to estimate the emulation similarity value $simValue$.
{0pt} \IncMargin{1em} \begin{algorithm2e} \caption{VLGrangerFunc} \SetKwInOut{Input}{input}\SetKwInOut{Output}{output} \Input{$X,Y$, $\delta_{max}$, $\sigma$, $\gamma$ (or $\alpha$), $FixLag$ } \Output{ $GrangerResult$,$r_{Y},r_{YX}$}
\end{algorithm2e}\DecMargin{1em}
In this work, we propose to use Dynamic Time Warping (DTW) sakoe1978dynamic, which is a standard distance measure between two time series. DTW calculates the distance between two time series by aligning sufficiently similar patterns between two time series, while allowing for local stretching (see Figure (ref)). Thus, it is particularly well suited for calculating the variable lag alignment.
Given time series $X$ and $Y$, Algorithm (ref) reports reconstructed time series $X^{DTW}$ based on $X$ that is most similar to $Y$, as well as the emulation similarity $simValue$ between the two series. First, we use $DTW(X,Y)$ to find the optimal alignment sequence $\hat{P}=(\Delta_1,\dots,\Delta_t,\dots)$ between $X$ and $Y$, as defined in Definition (ref). Efficient algorithms for computing $DTW(X,Y)$ exist and they can incorporate various kernels between points Mueen:2016:EOP:2939672.2945383,sakoe1978dynamic. Then, we use $\hat{P}$ to construct $X^{DTW}$ where $X^{DTW}(t)=X(t-\Delta_t)$. However, we also use cross-correlation to normalize $\Delta_t$ since DTW is sensitive to a noise of alignment (Algorithm (ref) line 3-5).
Afterwards, we use $X^{DTW}$ to predict $Y$ instead of using only $X$ information in the past in order to infer a VL-Granger causal relation in Definition (ref). The benefit of using DTW is that it can match time points of $Y$ and $X$ with non-fixed lags (see Figure (ref)). Let $\hat{P}=(\Delta_1,\dots,\Delta_t,\dots)$ be the DTW optimal warping path of $X,Y$ such that for any $\Delta_t \in \hat{P}$, $Y(t)$ is most similar to $X(t-\Delta_t)$.
In addition to finding $X^{DTW}$, $DTWReconstructionFunction$ estimates the emulation similarity $simValue$ between $X,Y$ in line 3. For that, we adopt the measure from FLICAtkdd below:
where $0<\mathrm{s}(\hat{P})\leq 1$ if $X\preceq Y$, $-1\leq \mathrm{s}(\hat{P})<0$ if $Y\preceq X$, otherwise zero. Since the $\mathrm{sign}(\Delta_t)$ represents whether $Y$ is similar to $X$ in the past ($\mathrm{sign}(\Delta_t) >0$) or $X$ is similar to $Y$ in the past ($\mathrm{sign}(\Delta_t) <0$), by comparing the sign of $\mathrm{sign}(\Delta_t)$, we can infer whether $Y$ emulates $X$. The function $\mathrm{s}(\hat{P})$ computes the average sign of $\mathrm{sign}(\Delta_t)$ for the entire time series. If $\mathrm{s}(\hat{P})$ is positive, then, on average, the number of times that $Y$ is similar to $X$ in the past is greater than the number of times that $X$ is similar to some values of $Y$ in the past. Hence, $\mathrm{s}(\hat{P})$ can be used as a proxy to determine whether $Y$ emulates $X$ or vice versa. We use dtw R package giorgino2009computing for our DTW function. For more details regarding DTW, please see Appendix (ref).
{0pt} \IncMargin{1em} \begin{algorithm2e} \caption{ DTWReconstructionFunction} \SetKwInOut{Input}{input}\SetKwInOut{Output}{output} \Input{ $X,Y$} \Output{ $X^{DTW}$, $simValue$}
\end{algorithm2e}\DecMargin{1em}
Given $RRSS$ is a restricted residual sum of squares from a regression of $Y$ on $Y$ past, and $T$ is a length of time series, the BIC of null model can be defined below.
For unrestricted model, given $URSS$ is an unrestricted residual sum of squares from a regression of $Y$ on $Y,X$ past, and $T$ is a length of time series, the BIC of alternative model can be defined below.
We use the Bayesian Information Criterion difference ratio as a main criteria to determine whether $X$ Granger-causes $Y$ or determining $BIC_1(r_{YX}) \ll BIC_0(r_{Y})$ in Algorithm (ref) line 6, which can be defined below:
The ratio $\mathrm{r}(\cdot,\cdot)$ is within $[-\infty,1]$. The closer $\mathrm{r}(\cdot,\cdot)$ to $1$, the better the performance of alternative model is compared to the null model. We can set the threshold $\gamma\in[0,1]$ to determine whether $X$ Granger-causes $Y$, i.e. $\mathrm{r}(BIC_0(r_{Y}),BIC_1(r_{YX}))\geq \gamma$ implies $X$ Granger-causes $Y$. Other options of determining $X$ Granger-causes $Y$ is to use F-test or the emulation similarity $simValue$.
Given time series $X,Y$, and the maximum possible lag $\delta_{max}$, and whether we want to check for variable or fixed lag $FixLag$, Algorithm (ref) reports whether $X$ causes $Y$ by setting $TransEResult$ to be true or false, and by reporting on two transfer entropy values: $\mathcal{T}_{X\xrightarrow{} Y}$ and $\mathcal{T}_{Y\xrightarrow{} X}$.
First, if $FixLag$ is true, then we compute the transfer entropy (line 1) using RTransferEntropy($X,Y$) BEHRENDT2019100265. If $FixLag$ is false, then, we reconstructed $X^{DTW}$ using $DTWReconstructionFunction(X,Y)$ in Section (ref) (line 2). We compute the VL-transfer entropy (line 3) using RTransferEntropy($X^{DTW},Y$).
If the ratio $\mathcal{T}(X,Y)_\textrm{ratio}>1$ (Section (ref)), then $X$ causes $Y$ and we set $TransEResult=true$ (line 5), otherwise, $TransEResult=false$ (line 6).
{0pt} \IncMargin{1em} \begin{algorithm2e} \caption{VLTransferEFunc} \SetKwInOut{Input}{input}\SetKwInOut{Output}{output} \Input{$X,Y$, $\delta_{max}$, $FixLag$ } \Output{ $TransEResult$,$\mathcal{T}_{X\xrightarrow{} Y}$,$\mathcal{T}_{Y\xrightarrow{} X}$}
\end{algorithm2e}\DecMargin{1em}
Additionally, the work by Dimpfl and Peter (2013) dimpfl2013using proposed the approach to perform the Markov block bootstrap on transfer entropy so that the results can be calculated the p-value of significance tests. The approach preserves dependency within time series while performing bootstrapping. We also integrated this option of bootstrapping analysis in our framework.
To determine whether $X$ Transfer-Entropy-causes $Y$, we can use the Transfer Entropy Ratio below.
The VL-Transfer Entropy Ratio is defined below:
Where $\mathcal{T}^\text{VL}_{X\xrightarrow{} Y}$ and $\mathcal{T}^\text{VL}_{Y\xrightarrow{} X}$ are Transfer Entropy values from VL-Transfer Entropy (Algorithm (ref) line 3). $\mathcal{T}(X,Y)_\textrm{ratio}$ greater than $1$ implies that $X$ causes $Y$ in Transfer Entropy. The higher $\mathcal{T}(X,Y)_\textrm{ratio}$, the higher the strength of $X$ causing $Y$. The same is true for $\mathcal{T}^\text{VL}(X,Y)_\textrm{ratio}$.
We measured our framework performance on the task of inferring causal relations using both simulated and real-world datasets. The notations and symbols we use in this section are in Table (ref).
We tested the performance of our method on synthetic datasets, where we explicitly embedded a variable-lag causal relation, as well as on biological datasets in the context of the application of identifying initiators of collective behavior, and on other two real-world casual datasets.
We compared our methods, VL-Granger causality (VL-G) and VL-Transfer entropy (VL-TE), with several existing methods: Granger causality with F-test (G) atukeren2010relationship, Copula-Granger method (CG) liu2012sparse, Spectral Independence Criterion method (SIC) shajarisales2015telling, and transfer entropy (TE) BEHRENDT2019100265.
In this paper, we explore the choice of $\delta_{max}$ in $\{0.1T,0.2T,0.3T,0.4T\}$ for all methods to analyze the sensitivity of each method, where $T$ is the length of time series, and set $\gamma=0.5$ as default unless explicitly stated otherwise\footnote{In VL-Granger causality, the threshold $\gamma=0.5$ implies that the time series $X$ causes $Y$ if the residuals of perdition by the VL-Granger can be reduced compared against the residuals of the null model (using $Y$ past to predict $Y$) at least half. We set the $\gamma=0.5$ for a pairwise time series X because we know they have either a strong signal of causation or no causation. }.
The main purpose of the synthetic data is to generate settings that explicitly illustrate the difference between the original Granger causality, transfer entropy methods and the proposed variable-lag approaches. We generated pairs of time series for which the fixed-lag causality methods would fail to find a relationship but the variable-lag approach would find the intended relationships.
We generated a set of synthetic time series of 200 time steps. We generated two sets of pairs of time series $X$ and $Y$. First, we generated $X$ either by drawing the value of each time step from a standard normal distribution $\mathcal{N}(0,1)$ with zero mean and a variance at one ($X(t)\sim\mathcal{N}$) (normal model) or by Auto-Regressive Moving Average model (ARMA or A.) with $X(t)= 0.2X(t-1) + \epsilon_X$ where $\epsilon_X\sim\mathcal{N}(0,1)$.
The first set we generated was of explicitly related pairs of time series $X$ and $Y$, where $Y$ emulates $X$ with some time lag $\Delta =5$ ($X\prec Y$). Specifically, $Y(t)= X(t-\Delta) + 0.1\epsilon_Y$ where $\epsilon_Y\sim\mathcal{N}(0,1)$.
One way to ensure lag variability is to “turn off" the emulation for some time. For example, $Y$ remains constant between 110th and 170th time steps imitating the $X$ at 100th time step. This makes $Y$ a variable-lag follower of $X$. Figure (ref) shows examples of the generated time series that has $Y$ remains constant for a while. We generated time series for each generator model 15 times.
The second set of time series pairs $X$ and $Y$ were generated independently and as a result have no causal relation. We used these pairs to ensure that our method does not infer spurious relations. We generated time series for each generator model 15 times.
Hence, we have 15 datasets of normal model with $X\prec Y$, 15 datasets of normal model with $X\nprec Y$, 15 datasets of ARMA model with $X\prec Y$, 15 datasets of ARMA model with $X\nprec Y$, and 15 datasets where $X$ is from normal model, and $Y$ is from ARMA model s.t. $X\nprec Y$. In total, we have 75 datasets for the pairwise-level simulation. See Appendix (ref) for the code we used to generated the datasets.
We set the significance level for both F-test and bootstrapping test of transfer entropy at $\alpha=0.05$. For the bootstrapping of transfer entropy, we set the number of bootstrap replicates as 100 times. We considered there to be a causal relation only if $\mathrm{r}(BIC_0(r_{Y}),BIC_1(r_{YX}))\geq \gamma$ for our method.
For the task of causal prediction, we define the true positive (TP) when the ground truth is $X\prec Y$ and a method reports that $X\prec Y$. The true negative (TN) is when both the ground truth and predicted result agree that $X\nprec Y$. The false positive (FP) is when the ground truth is $X\nprec Y$, but the method predicted that $X\prec Y$. The false negative (FN) is the ground truth is $X\prec Y$, but the method disagrees. The accuracy is the TP and TN cases divided by the number of total pairs of time series. The true positive rate (TPR) is the number of TP cases divided by the number of TP and FN cases. The false positive rate (FPR) is the number of FP cases divided by the number of FP and TN cases.
We report the result in the form of the receiver operating characteristic (ROC) curves. The results of methods are compared against each other using their area under a curve (AUC).
This experiment explores the ability of causal inference methods to retrieve {\em multiple} causes of a time series $Y_{ij}$, which is generated from multiple time series $X_i,X_j$. Fig. (ref) shows the ground truth causal graph we used to generate simulated datasets. The edges represent causal directions from the cause time series (e.g. $X_1$) to the effect time series (e.g. $Y_1$). $Y_{ij}$ represents the time series generated by $agg(\{X'_i,X'_j\})$, where $X_i\prec X'_i$ and $X_j\prec X'_j$ with some fixed lag $\Delta = 5$. The task is to infer edges of this causal graph from the time series. We generated time series for each generator model 15 times. We set $\gamma=0.3$ in this experiment due to the weak signal of $X$ causes $Y$ when there are multiple causes of $Y$. There are also two generators for $X_1,X_2,X_3$: normal distribution and ARMA model.
For the task of causal graph prediction, a TP case is a case when both when both the ground truth and predicted result agree that there is a causal edge from $X_i$ to $Y_j$ in the graph. A TN case is a case when both when both the ground truth and predicted result agree that there is no causal edge from $X_i$ to $Y_j$ in the graph. A FP is a case when there is no edge in a ground truth casual graph, but a method predicted that there is the edge. A FN is a case when there is an edge from $X_i$ to $Y_j$ in a ground truth casual graph, but a method predicted that there is no edge from $X_i$ to $Y_j$. We report precision, recall, and F1 score for all methods. The precision ($prec$) is a ratio between a number of TP cases and a number of TP+FP cases. The recall ($rec$) is a ratio between a number of TP cases and a number of TP+FN cases. The F1 score $F=2*prec*rec/(prec+rec)$.
For the parameter setting, since the the time delay between causes and effects is 5 time steps for all datasets in this section, methods with the $\Delta_{max}$ parameter have $\Delta_{max}=10$.
See Appendix (ref) for the code we used to generated the datasets.
We used the dataset of golden shiners (Notemigonus crysoleucas) that is publiclly available. The dataset has been collected for the study of information propagation over the visual fields of fish strandburg2013visual. A coordination event consists of two-dimensional time series of fish movement that are recorded by video. The time series of fish movement are around 600 time steps. The number of fish in each dataset is around 70 individuals, of which 10 individuals are “informed" fish who have been trained to go to a feeding site. Trained fish lead the group to feeding sites while the rest of the fish just follow the group. We represent the dataset as a pair of aggregated time series: $X$ being the aggregated time series of the directions of trained fish and $Y$ being the aggregated time series of the directions of untrained fish (see Fig. (ref)). The task is to infer whether $X$ (trained fish) is a cause of $Y$ (the rest of the group).
We used another publicly available dataset of animal behavior, the movement of a troop of olive baboons (Papio anubis). The dataset consists of GPS tracking information from 26 members of a troop, recorded at 1 Hz from 6 AM to 6 PM between August 01, 2012 and August 10, 2012. The troop lives in the wild at the Mpala Research Centre, Kenya crofoot2015data,strandburg2015shared. For the analysis, we selected the 16 members of the troop that have GPS information available for 10 consecutive days, with no missing data. We selected a set of trajectories of lat-long coordinates from a highly coordinated event that has the length of 600 time steps (seconds) for each baboon. This known coordination event is on August 02, 2012 in the morning, with the baboon ID3 initiating the movement, followed by the rest of the troop FLICAtkdd. Again, the goal is to infer ID3 (time series $X$) as the cause of the movement of the rest of the group (aggregate time series $Y$) (see Fig. (ref)).
This dataset consists of information regarding a gas consumption by a gas furnace box2015time. $X$ is time series of gas consumption rate and $Y$ is time series of $CO_2$ rate produced by a gas furnace (see Fig. (ref)). Both $X,Y$ have 296 time steps.
This dataset consists of information regarding eruption durations and intervals between eruption events at Old Faithful geyser azzalini1990look. $X$ is time series of eruption duration and $Y$ is time series of the interval between current eruption and the next eruption (see Fig. (ref)). Both $X,Y$ have 298 time steps.
The main cost of computation in our approach is DTW. We used the “Windowing technique” for the search area of warping keogh2001derivative. The main parameter for windowing technique is the maximum time delay $\delta_{max}$. Hence, the time complexity of VL-G is $\mathcal{O}(T\delta_{max})$. The time complexity of TE can be at most $\mathcal{O}(T^3)$ shao2014accelerating, which makes VL-TE has the same time complexity. However, with the work by Kontoyiannis and Skoularidou in kontoyiannis2016estimating, the convergence rate of TE approximation can be reduced to $\mathcal{O}(1/\sqrt{T})$ if time series are generated with a Markov-chain property of a given lags. Table (ref) shows the running time of our approach on time series with the varying length ($T\in \{5000,20000\}$) and maximum time delay ($\delta_{max} \in \{0.05T,0.1T,0,2T\}$).
We report the results of our proposed approaches and other methods on both synthetic and real-world datasets. We also explore how the performance of the methods depends on the basic parameter, $\delta_{\max}$.
Figure (ref) shows the ROC curves from the results of inferring causal relations and directions. According to the AUC values, all variable-lag methods perform better than their original methods (e.g. VL-G vs. G, VL-TE vs. TE).
The result also shows that our method, VL-Transfer entropy with bootstrapping, VL-TE (boots), performed better than the rest of other methods. The second best method is VL-Granger causality (VL-G), which has the AUC value almost the same as VL-TE (boots). For transfer entropy results, the bootstrapping methods (both VL-TE (boots) and TE (boots) ), performed better than their original version. This indicates that the bootstrapping approach increases the performance of transfer entropy methods in this task.
Moreover, we also investigated the sensitivity of varying the value of the $\delta_{max}$ parameter for all methods. We aggregated the accuracy of inferring causal direction from various cases that have the same $\delta_{max}$ value and report the result. The result in Fig. (ref) shows that VL-TE (boots), VL-G, TE (boots), and G can maintain the high accuracy (>0.9) throughout the range of the values of $\delta_{max}$.
Table (ref) shows the result of causal graph inference. The VL-G performed the best overall with the highest F1 score. This result reflects the fact that our approaches can handle complicated time series in causal inference task better than the rest of other methods. VL-TE also performed better than TE.
In addition, we aggregated $X=agg(\{X_1,X_2,X_3\})$ and $Y=agg(\{Y_1,Y_2,\dots,Y_{123}\})$, then we measured the ability of methods to infer that $X$ is a cause of $Y$. The results, which are in the “Group: $X\prec Y$" column in Table (ref), show that G, CG and SIC performed well in this task, while the rest of methods failed to infer causal relations. Note that VL-G also performed well when we relaxed the $\gamma$ from 0.3 to 0.01. This is due to the fact that the aggregated group time series have a complicated casual relation between $X=agg(\{X_1,X_2,X_3\})$ and $Y=agg(\{Y_1,Y_2,\dots,Y_{123}\})$, which implies that the causal signal is not strong. Hence, we need to relaxed the $\gamma$ to capture the causal relation.
Comparing transfer entropy methods, the bootstrapping approach decreaseed the performance to detect causal relations compared to their original version. This is also due to the weak signal of causal relation in the complicated datasets.
Overall, the simple original Granger causality performed well in both tasks. Moreover, due to the causal relations in simulation datasets are highly linear, hence, we expect the linear model (e.g. VL-G, G) should perform better than the non-linear approaches (e.g. TE, VL-TE).
Table (ref) shows results of inferring causal relations in real-world datasets. For VL-G, it performed better than G. However, BIC difference ratio failed to infer causal relations of gas furnace and old faithful geyser datasets but F-test successfully inferred causal relations in all datasets. Typically, a causal relation that has a high BIC difference ratio can also be detected to have a causal relation by F-test but not vise versa. This suggests that gas furnace and old faithful geyser have weak causal relations. For G, the method cannot detect fish and Old faithful geyser datasets. This suggests that both datasets have a high-level of variable lags that a fixed-lag assumption in G has an issue. For CG, SIC, and TE, they failed in one dataset each. This implies that some dataset that a specific approach failed to detect a causal relation has broke some assumption of a specific approach. Lastly, VL-TE was able to detect all causal relations.
For the old faithful geyser dataset, both G and TE failed to detect a causal relation while both VL-G and VL-TE successfully inferred a causal relation. This implies that this dataset has a high-level of variable lags that broke a fix-lag assumption of G and TE.
Lastly, the transfer entropy methods with bootstrapping almost failed to detect anything. This is due to the weak signal of causal relations in real-world datasets.
To compare the performance of VL-G and G, we simulated 100 datasets of $X \prec Y$ with variable lags. Since $X \prec Y$, a higher BIC difference ratio implies a better result. Fig. (ref) shows the results of BIC difference ratio for VL-G and G. Obviously, VL-G has a higher BIC difference ratio than G's. This suggests that VL-G was able to capture stronger signal of $X$ causes $Y$.
To compare the performance of VL-TE and TE, we also simulated 100 datasets of $X \prec Y$ with variable lags. Since $X \prec Y$, a higher transfer entropy ratio implies a better result. Fig. (ref) shows the results of transfer entropy ratio for VL-TE and TE. Obviously, VL-TE has a higher transfer entropy ratio than TE's. This suggests that VL-TE was able to capture stronger signal of $X$ causes $Y$.
In this work, we proposed a method to infer Granger and transfer entropy causal relations in time series where the causes influence effects with arbitrary time delays, which can change dynamically. We formalized a new Granger causal relation and a new transfer entropy causal relation, proving that they are true generalizations of the traditional Granger causality and transfer entropy respectively. We demonstrated on both carefully designed synthetic datasets and noisy real-world datasets that the new causal relations can address the arbitrary-time-lag influence between cause and effect, while the traditional Granger causality and transfer entropy cannot. Moreover, in addition to improving and extending Granger causality and transfer entropy, our approach can be applied to infer leader-follower relations, as well as the dependency property between cause and effect. Note that, in simulation datasets, we did not include nonlinear datasets in our analysis. We expect that the linear measures (e.g. VL-Granger and Granger) should outperform the non-linear measures (Transfer Entropy and VL-Transfer Entropy) in the linear datasets, while the non-linear measures should outperform linear measures in non-linear datasets.
We have shown that, in many situations, the causal relations between time series do not have a lock-step connection of a fixed lag that the traditional Granger causality and transfer entropy assume. Hence, traditional Granger causality and transfer entropy missed true existing causal relations in such cases, while our methods correctly inferred them. Our approach can be applied in any domain of study where the causal relations between time series is of interest. The R-CRAN package entitled VLTimeCausality is provided at ShareSourcecode. See Appendix (ref) for the example of how to use the package.