Escaping the Curse of Dimensionality in Estimating Multivariate Transfer Entropy

Multivariate transfer entropy (TE) is a model-free approach to detect causalities in multivariate time series. It is able to distinguish direct from indirect causality and common drivers without assuming any underlying model. But despite these advantages it has mostly been applied in a bivariate setting as it is hard to estimate reliably in high dimensions since its definition involves infinite vectors. To overcome this limitation, we propose to embed TE into the framework of graphical models and present a formula that decomposes TE into a sum of finite-dimensional contributions that we call decomposed transfer entropy. Graphical models further provide a richer picture because they also yield the causal coupling delays. To estimate the graphical model we suggest an iterative algorithm, a modified version of the PC-algorithm with a very low estimation dimension. We present an appropriate significance test and demonstrate the method’s performance using examples of nonlinear stochastic delay-differential equations and observational climate data (sea level pressure).

Figure 1

Estimated TE between all subprocesses $X$, $Y$, $Z$, $W$ for an example process [a discrete-time sampling of Eq. (5) that will be analyzed later] with true coupling structure given by the black arrows. If we truncate the infinite past vectors used in the common definition of TE at 15 lags, the estimation dimension is 61. The true TE of all gray and red links is zero, since they do not represent direct couplings. So of the four estimates of comparable size marked in red boxes, only the link $Y\to W$ is a correctly identified coupling.

Figure 2

Causal interactions in a multivariate process $\mathbf{X}$. (a) Time series graph (see definition in text). The boxes mark different sets of conditions for the CMI between $X_{t-\tau }$ at $\tau =2$ and $Y_t$ (marked by the black dots): the terms in Eq. (1) use the infinite set ${\mathbf{X}}_t^{-}\setminus X_t^{-}\cup X_{t-\tau }^{-}$ (gray dotted line). But only the finite set ${\mathcal{S}}_{Y_t,X_{t-\tau }}$ (red dashed line) is needed to satisfy Eq. (2). ${\mathcal{S}}_{Y_t,X_{t-\tau }}$ must be chosen so that it separates the skipped infinite conditions $({\mathbf{X}}_t^{-}\setminus X_t^{-}\cup X_{t-\tau }^{-})\setminus {\mathcal{S}}_{Y_t,X_{t-\tau }}$ from $Y_t$ in the graph (for a formal definition of paths and separation, see 13). The even smaller set of parents ${\mathcal{P}}_{Y_t}$ (blue box, gray nodes) separates $Y_t$ from the past of the whole process ${\mathbf{X}}_t^{-}\setminus {\mathcal{P}}_{Y_t}$, which is used in the algorithm to estimate the graph. (b) Process graph, which aggregates the information in the time series graph for better visualization (labels denote the lags).

Figure 3

Iterative steps in the analysis of model Eq. (5), time series length $T=1000$, integration time step $dt=0.01$, sampling interval $\Delta s=100$, MI and CMI estimated using $k=100$. The label ($n.i$) indicates the iteration step. (0.0) shows the MI process graph. With an initial $n_0=3$ the next step (3.0) (see the Supplemental Material [11]) with three conditions is already almost identical to the converged graph in step (3.1), where the values in the boxes denote the estimate $\widehat{I^{\mathrm{DTE}}}$ of TE via Eq. (3) with ${\tau }^{*}$ chosen such that $I(X_{t-{\tau }^{*}-1};Y_t|{\mathcal{S}}_{Y_t,X_{t-{\tau }^{*}-1}})$ has declined below significance. Incorrect links and lag labels are in red.

Figure 4

Analysis of time series of mean sea level pressure with $T=1268$ using the same threshold as before and ${\tau }_{\max }=10$. (0.0) depicts the process graph for MI. The iteration converges in step (2.1); step (2.0) and the lag functions are shown in the Supplemental Material [11]. Labels are as in Fig. 3.