The relation between Granger causality and directed information theory: a review <s> Consider a cost function <s> Preparations. Unbiasedness. Equivariance. Global properties. Large-sample theory. Asymptotic optimality. Author index. Subject index. <s> BIB001 </s> The relation between Granger causality and directed information theory: a review <s> Consider a cost function <s> We propose a method of analysis of dynamical networks based on a recent measure of Granger causality between time series, based on kernel methods. The generalization of kernel-Granger causality to the multivariate case, here presented, shares the following features with the bivariate measures: (i) the nonlinearity of the regression model can be controlled by choosing the kernel function and (ii) the problem of false causalities, arising as the complexity of the model increases, is addressed by a selection strategy of the eigenvectors of a reduced Gram matrix whose range represents the additional features due to the second time series. Moreover, there is no a priori assumption that the network must be a directed acyclic graph. We apply the proposed approach to a network of chaotic maps and to a simulated genetic regulatory network: it is shown that the underlying topology of the network can be reconstructed from time series of node's dynamics, provided that a sufficient number of samples is available. Considering a linear dynamical network, built by preferential attachment scheme, we show that for limited data use of the bivariate Granger causality is a better choice than methods using L1 minimization. Finally we consider real expression data from HeLa cells, 94 genes and 48 time points. The analysis of static correlations between genes reveals two modules corresponding to well-known transcription factors; Granger analysis puts in evidence 19 causal relationships, all involving genes related to tumor development. <s> BIB002 </s> The relation between Granger causality and directed information theory: a review <s> Consider a cost function <s> Granger causality considers the question of whether two time series exert causal influences on each other. Causality testing usually relies on prediction, i.e., if the prediction error of the first time series is reduced by taking measurements from the second one into account, then the latter is said to have a causal influence on the former. In this paper, a nonparametric framework based on functional estimation is proposed. Nonlinear prediction is performed via the Bayesian paradigm, using Gaussian processes. Some experiments illustrate the efficiency of the approach. <s> BIB003
where e stands for an error term. Let a predictor of x B (n) be defined formally as , where A and B are subsets of V , and f is a function between appropriate spaces, chosen to minimize the risk with e(n) ∶= x B (n + 1) − x B (n + 1). Solvability may be granted if f is restricted to an element of a given class of functions, such as the set of linear functions. Let F be such a function class. Define: R F B(n + 1) A n is therefore the optimal risk when making a one-step-ahead prediction of the multivariate signal x B from the past samples of the multivariate signal x A . We are now ready to measure the influence of the past of a process on the prediction of another. To be relatively general and to prepare comments on the structure of the graph, this can be done for subsets of V . We thus choose A and B to be two disjoint subsets of V , and we define C ∶= V (A ∪ B) (we use to mean substraction of a set). We study causality from x A to x B by measuring the decrease in the quality of the prediction of x B (n) when excluding the past of x A . May 5, 2014 DRAFT Let R F B(n + 1) V n be the optimal risk obtained for the prediction of x B from the past of all of the signals grouped in x V . This risk is compared to R F B(n + 1) (V A) n , where the past of x A is omitted. Then, for the usual costs functions, we have necessarily: A natural first definition for Granger causality is: This definition of Granger causality depends on the cost g chosen as well as on the class F of the functions considered. Usually, a quadratic cost function is chosen, for its simplicity and for its evident physical interpretation (a measure of the power of the error). The choice of the class of functions F is crucial. The result of the causality test in definition 1 can change when the class is changed. Consider the very simple example of x n+1 = αx n +βy 2 n +ε n+1 , where y n and ε n are Gaussian independent and identically distributed (i.i.d.) sequences that are independent of each other. The covariance between x n+1 and y n is zero, and using the quadratic loss and the class of linear functions, we conclude that y does not Granger cause x, because using a linear function of x n , y n to predict x would lead to the same minimal risk as using a linear function of x n only. However, y n obviously causes x n , but in a nonlinear setting. The definition is given using the negative of the proposition. If by using the positive way, i.e., R F B(n+1) V n < R F B(n + 1) (V A) n , Granger proposes to say that x A is a prima facie cause of x B relative to V , prima facie can be translated as 'at a first glance'. This is used to insist that if V is enlarged by including other measurements, then the conclusion might be changed. This can be seen as redundant with the mention of the relativity to the observation set V , and we therefore do not use this terminology. However, a mention of the relativity to V must be used, as modification of this set can alter the conclusion. A very simple example of this situation is the chain x n → y n → z n , where, for example, x n is an i.i.d. sequence, y n+1 = x n + ε n+1 , z n+1 = y n + η n+1 , ε n , η n being independent i.i.d. sequences. Relative to V = {x, z}, x causes z if we use the quadratic loss and linear functions of the past samples of x (note here that the predictor z n+1 must be a function of not only x n , but also of x n−1 ). However, if we include the past samples of y and V = {x, y, z}, then the quality of the prediction of z does not deteriorate if we do not use past samples of x. Therefore, x does not cause z relative to V = {x, y, z}. The advantage of the prediction-based definition is that is leads to operational tests. If the quadratic loss is chosen, working in a parameterized class of functions, such as linear filters or Volterra filters, or even working in reproducing kernel Hilbert spaces, allows the implementation of the definition BIB002 , BIB003 ,  . In such cases, the test needed can be evaluated efficiently from the data. From a theoretical point of view, the quadratic loss can be used to find the optimal function in a much wider class of functions: the measurable functions. In this class, the optimal function for the quadratic loss is widely known to be the conditional expectation BIB001 . When predicting x B from the whole observation set V , the optimal predictor is written as May 5, 2014 DRAFT elimination of A from V to study its influence on B leads to the predictor These estimators are of little use, because they are too difficult, or even impossible, to compute. However, they highlight the important of conditional distributions p(x B (n + 1) x n V ) and p(x B (n + 1) x n B , x n C ) in the problem of testing whether x A Granger causes x B relative to V or not.