The relation between Granger causality and directed information theory: a review <s> 2) Prediction based approach in the Gaussian case: <s> Abstract Measures of linear dependence and feedback for multiple time series are defined. The measure of linear dependence is the sum of the measure of linear feedback from the first series to the second, linear feedback from the second to the first, and instantaneous linear feedback. The measures are nonnegative, and zero only when feedback (causality) of the relevant type is absent. The measures of linear feedback from one series to another can be additively decomposed by frequency. A readily usable theory of inference for all of these measures and their decompositions is described; the computations involved are modest. <s> BIB001 </s> The relation between Granger causality and directed information theory: a review <s> 2) Prediction based approach in the Gaussian case: <s> Abstract Measures of linear dependence and feedback for two multiple time series conditional on a third are defined. The measure of conditional linear dependence is the sum of linear feedback from the first to the second conditional on the third, linear feedback from the second to the first conditional on the third, and instantaneous linear feedback between the first and second series conditional on the third. The measures are non-negative and may be expressed in terms of measures of unconditional feedback between various combinations of the three series. The measures of conditional linear feedback can be additively decomposed by frequency. Estimates of these measures are straightforward to compute, and their distribution can be routinely approximated by bootstrap methods. An empirical example involving real output, money, and interest rates is presented. <s> BIB002 </s> The relation between Granger causality and directed information theory: a review <s> 2) Prediction based approach in the Gaussian case: <s> In this paper we propose causality measures based on the Kullback Information Criterion. These causality measures are applicable in a general context which contains, as special cases, the stationary autoregressive case, considered by GEWEKE, and qualitative models. Estimators of these measures and test procedures are proposed. The nesting of the hypotheses and the asymptotic independence of the test statistics are carefully studied. <s> BIB003 </s> The relation between Granger causality and directed information theory: a review <s> 2) Prediction based approach in the Gaussian case: <s> Preface to the Second Edition. Preface to the First Edition. Acknowledgments for the Second Edition. Acknowledgments for the First Edition. 1. Introduction and Preview. 1.1 Preview of the Book. 2. Entropy, Relative Entropy, and Mutual Information. 2.1 Entropy. 2.2 Joint Entropy and Conditional Entropy. 2.3 Relative Entropy and Mutual Information. 2.4 Relationship Between Entropy and Mutual Information. 2.5 Chain Rules for Entropy, Relative Entropy, and Mutual Information. 2.6 Jensen's Inequality and Its Consequences. 2.7 Log Sum Inequality and Its Applications. 2.8 Data-Processing Inequality. 2.9 Sufficient Statistics. 2.10 Fano's Inequality. Summary. Problems. Historical Notes. 3. Asymptotic Equipartition Property. 3.1 Asymptotic Equipartition Property Theorem. 3.2 Consequences of the AEP: Data Compression. 3.3 High-Probability Sets and the Typical Set. Summary. Problems. Historical Notes. 4. Entropy Rates of a Stochastic Process. 4.1 Markov Chains. 4.2 Entropy Rate. 4.3 Example: Entropy Rate of a Random Walk on a Weighted Graph. 4.4 Second Law of Thermodynamics. 4.5 Functions of Markov Chains. Summary. Problems. Historical Notes. 5. Data Compression. 5.1 Examples of Codes. 5.2 Kraft Inequality. 5.3 Optimal Codes. 5.4 Bounds on the Optimal Code Length. 5.5 Kraft Inequality for Uniquely Decodable Codes. 5.6 Huffman Codes. 5.7 Some Comments on Huffman Codes. 5.8 Optimality of Huffman Codes. 5.9 Shannon-Fano-Elias Coding. 5.10 Competitive Optimality of the Shannon Code. 5.11 Generation of Discrete Distributions from Fair Coins. Summary. Problems. Historical Notes. 6. Gambling and Data Compression. 6.1 The Horse Race. 6.2 Gambling and Side Information. 6.3 Dependent Horse Races and Entropy Rate. 6.4 The Entropy of English. 6.5 Data Compression and Gambling. 6.6 Gambling Estimate of the Entropy of English. Summary. Problems. Historical Notes. 7. Channel Capacity. 7.1 Examples of Channel Capacity. 7.2 Symmetric Channels. 7.3 Properties of Channel Capacity. 7.4 Preview of the Channel Coding Theorem. 7.5 Definitions. 7.6 Jointly Typical Sequences. 7.7 Channel Coding Theorem. 7.8 Zero-Error Codes. 7.9 Fano's Inequality and the Converse to the Coding Theorem. 7.10 Equality in the Converse to the Channel Coding Theorem. 7.11 Hamming Codes. 7.12 Feedback Capacity. 7.13 Source-Channel Separation Theorem. Summary. Problems. Historical Notes. 8. Differential Entropy. 8.1 Definitions. 8.2 AEP for Continuous Random Variables. 8.3 Relation of Differential Entropy to Discrete Entropy. 8.4 Joint and Conditional Differential Entropy. 8.5 Relative Entropy and Mutual Information. 8.6 Properties of Differential Entropy, Relative Entropy, and Mutual Information. Summary. Problems. Historical Notes. 9. Gaussian Channel. 9.1 Gaussian Channel: Definitions. 9.2 Converse to the Coding Theorem for Gaussian Channels. 9.3 Bandlimited Channels. 9.4 Parallel Gaussian Channels. 9.5 Channels with Colored Gaussian Noise. 9.6 Gaussian Channels with Feedback. Summary. Problems. Historical Notes. 10. Rate Distortion Theory. 10.1 Quantization. 10.2 Definitions. 10.3 Calculation of the Rate Distortion Function. 10.4 Converse to the Rate Distortion Theorem. 10.5 Achievability of the Rate Distortion Function. 10.6 Strongly Typical Sequences and Rate Distortion. 10.7 Characterization of the Rate Distortion Function. 10.8 Computation of Channel Capacity and the Rate Distortion Function. Summary. Problems. Historical Notes. 11. Information Theory and Statistics. 11.1 Method of Types. 11.2 Law of Large Numbers. 11.3 Universal Source Coding. 11.4 Large Deviation Theory. 11.5 Examples of Sanov's Theorem. 11.6 Conditional Limit Theorem. 11.7 Hypothesis Testing. 11.8 Chernoff-Stein Lemma. 11.9 Chernoff Information. 11.10 Fisher Information and the Cram-er-Rao Inequality. Summary. Problems. Historical Notes. 12. Maximum Entropy. 12.1 Maximum Entropy Distributions. 12.2 Examples. 12.3 Anomalous Maximum Entropy Problem. 12.4 Spectrum Estimation. 12.5 Entropy Rates of a Gaussian Process. 12.6 Burg's Maximum Entropy Theorem. Summary. Problems. Historical Notes. 13. Universal Source Coding. 13.1 Universal Codes and Channel Capacity. 13.2 Universal Coding for Binary Sequences. 13.3 Arithmetic Coding. 13.4 Lempel-Ziv Coding. 13.5 Optimality of Lempel-Ziv Algorithms. Compression. Summary. Problems. Historical Notes. 14. Kolmogorov Complexity. 14.1 Models of Computation. 14.2 Kolmogorov Complexity: Definitions and Examples. 14.3 Kolmogorov Complexity and Entropy. 14.4 Kolmogorov Complexity of Integers. 14.5 Algorithmically Random and Incompressible Sequences. 14.6 Universal Probability. 14.7 Kolmogorov complexity. 14.9 Universal Gambling. 14.10 Occam's Razor. 14.11 Kolmogorov Complexity and Universal Probability. 14.12 Kolmogorov Sufficient Statistic. 14.13 Minimum Description Length Principle. Summary. Problems. Historical Notes. 15. Network Information Theory. 15.1 Gaussian Multiple-User Channels. 15.2 Jointly Typical Sequences. 15.3 Multiple-Access Channel. 15.4 Encoding of Correlated Sources. 15.5 Duality Between Slepian-Wolf Encoding and Multiple-Access Channels. 15.6 Broadcast Channel. 15.7 Relay Channel. 15.8 Source Coding with Side Information. 15.9 Rate Distortion with Side Information. 15.10 General Multiterminal Networks. Summary. Problems. Historical Notes. 16. Information Theory and Portfolio Theory. 16.1 The Stock Market: Some Definitions. 16.2 Kuhn-Tucker Characterization of the Log-Optimal Portfolio. 16.3 Asymptotic Optimality of the Log-Optimal Portfolio. 16.4 Side Information and the Growth Rate. 16.5 Investment in Stationary Markets. 16.6 Competitive Optimality of the Log-Optimal Portfolio. 16.7 Universal Portfolios. 16.8 Shannon-McMillan-Breiman Theorem (General AEP). Summary. Problems. Historical Notes. 17. Inequalities in Information Theory. 17.1 Basic Inequalities of Information Theory. 17.2 Differential Entropy. 17.3 Bounds on Entropy and Relative Entropy. 17.4 Inequalities for Types. 17.5 Combinatorial Bounds on Entropy. 17.6 Entropy Rates of Subsets. 17.7 Entropy and Fisher Information. 17.8 Entropy Power Inequality and Brunn-Minkowski Inequality. 17.9 Inequalities for Determinants. 17.10 Inequalities for Ratios of Determinants. Summary. Problems. Historical Notes. Bibliography. List of Symbols. Index. <s> BIB004 </s> The relation between Granger causality and directed information theory: a review <s> 2) Prediction based approach in the Gaussian case: <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> BIB005 </s> The relation between Granger causality and directed information theory: a review <s> 2) Prediction based approach in the Gaussian case: <s> Advances in recording technologies have given neuroscience researchers access to large amounts of data, in particular, simultaneous, individual recordings of large groups of neurons in different parts of the brain. A variety of quantitative techniques have been utilized to analyze the spiking activities of the neurons to elucidate the functional connectivity of the recorded neurons. In the past, researchers have used correlative measures. More recently, to better capture the dynamic, complex relationships present in the data, neuroscientists have employed causal measures-most of which are variants of Granger causality-with limited success. This paper motivates the directed information, an information and control theoretic concept, as a modality-independent embodiment of Granger's original notion of causality. Key properties include: (a) it is nonzero if and only if one process causally influences another, and (b) its specific value can be interpreted as the strength of a causal relationship. We next describe how the causally conditioned directed information between two processes given knowledge of others provides a network version of causality: it is nonzero if and only if, in the presence of the present and past of other processes, one process causally influences another. This notion is shown to be able to differentiate between true direct causal influences, common inputs, and cascade effects in more two processes. We next describe a procedure to estimate the directed information on neural spike trains using point process generalized linear models, maximum likelihood estimation and information-theoretic model order selection. We demonstrate that on a simulated network of neurons, it (a) correctly identifies all pairwise causal relationships and (b) correctly identifies network causal relationships. This procedure is then used to analyze ensemble spike train recordings in primary motor cortex of an awake monkey while performing target reaching tasks, uncovering causal relationships whose directionality are consistent with predictions made from the wave propagation of simultaneously recorded local field potentials. <s> BIB006 </s> The relation between Granger causality and directed information theory: a review <s> 2) Prediction based approach in the Gaussian case: <s> The ability to identify directional interactions that occur among multiple neurons in the brain is crucial to an understanding of how groups of neurons cooperate in order to generate specific brain functions. However, an optimal method of assessing these interactions has not been established. Granger causality has proven to be an effective method for the analysis of the directional interactions between multiple sets of continuous-valued data, but cannot be applied to neural spike train recordings due to their discrete nature. This paper proposes a point process framework that enables Granger causality to be applied to point process data such as neural spike trains. The proposed framework uses the point process likelihood function to relate a neuron's spiking probability to possible covariates, such as its own spiking history and the concurrent activity of simultaneously recorded neurons. Granger causality is assessed based on the relative reduction of the point process likelihood of one neuron obtained excluding one of its covariates compared to the likelihood obtained using all of its covariates. The method was tested on simulated data, and then applied to neural activity recorded from the primary motor cortex (MI) of a Felis catus subject. The interactions present in the simulated data were predicted with a high degree of accuracy, and when applied to the real neural data, the proposed method identified causal relationships between many of the recorded neurons. This paper proposes a novel method that successfully applies Granger causality to point process data, and has the potential to provide unique physiological insights when applied to neural spike trains. <s> BIB007
Following definition 1 and focusing on the quadratic risk ], Geweke introduced the following indices for the study of Gaussian stationary processes BIB001 , BIB002 : Geweke demonstrated the efficiency of these indices for testing Granger causality and instantaneous coupling (bivariate and multivariate cases). Furthermore, in the bivariate case, Geweke showed that: where I ∞ (x A ; x B ) is the mutual information rate. This relationship that was already sketched out in  , is nothing but Eq. (34) . Indeed, in the Gaussian case, stem from the knowledge that the entropy rate of a Gaussian stationary process is the logarithm of the asymptotic power of the one-step-ahead prediction BIB004 . Likewise, we can show that and In the multivariate case, conditioning on the past of the side information, i.e. x n−1 C , in the definition of F x A ↔x B x C , a decomposition analagous to Eq. (62) holds, and is exactly that given by Eq. (44). 3) The model-based approach : In a more general framework, we examine how a model-based approach can be used to test for Granger causality, and how directed information comes into play. Let us consider a rather general model in which x V (t) is a multivariate Markovian process that statisfies: where V is a function belonging to some functional class F , and where w V is a multivariate i.i.d. sequence, the components of which are not necessarily mutually independent. Function f θ might (or might not) dependon θ, a multidimensional parameter. This general model includes as a particular case, linear multivariate autoregressive with moving average (ARMA) models, and nonlinear ARMA models; f θ can also stand for a function belonging to some reproducing kernel Hilbert space, which can be estimated from the data  , BIB005 ,  . Using May 5, 2014 DRAFT the partition A, B, C, this model can be written equivalently as: where the functions f .,θ. are the corresponding components of f θ . This relation can be used for inference in a parametric setting: the functional form is assumed to be known and the determination of the function is replaced by the estimation of the parameters θ A,B,C . This can also be used in a nonparametric setting, in which case the function f is searched for in an appropriate functional space, such as an rkHs associated to a kernel  . In any case, for studying the influence of x A to x B relative to V , two models are required for x B : one in which x B explicitly depends on x A , and the other one in which x B does not depend on x A . In the parametric setting, the two models can be merged into a single model, in such a way that some components of the parameter θ B are, or not, zero, which dependis whether A causes B or not. The procedure then consists of testing nullity (or not) of these components. In the linear Gaussian case, this leads to the Geweke indices discussed above. In the nonlinear (nonGaussian) case, the Geweke indices can be used to evaluate the prediction in some classes of nonlinear models (in the minimum mean square error sense). In this latter case, the decomposition of the mutual information, Eq. (62), has no reason to remain valid. Another approach base relies on directly modeling the probability measures. This approach has been used recently to model spiking neurons and to infer Granger causality between several neurons working in the class of generalized linear models BIB006 , BIB007 . Interestingly, the approach has been used either to estimate the directed information BIB006 or to design a likelihood ratio test BIB003 , BIB007 . Suppose we wish to test whether 'x A Granger causes x B relative to V ' as a binary hypothesis problem, as in section IV-B1. Forgetting the problem of instantaneous coupling, the problem is then to choose between the hypotheses: where the existence of causality is entirely reflected into the parameter θ. To be more precise, θ 0 should be seen as a restriction of θ 1 when its components linked to x A are set to zero. As a simple example using the model approach discussed above, consider the simple linear Gaussian model where w B (t) is an i.i.d. Gaussian sequence, and θ A , θ B , θ C are multivariate impulse responses of appropriate dimensions. Define θ 1 = (θ A , θ B , θ C ) and θ 0 = (0, θ B , θ C ). Testing for Granger causality is then equivalent to testing θ = θ 1 ; furthermore, the likelihood ratio can be implemented due to the Gaussian assumption. The example developed in BIB006 , BIB007 , assumes that the probability that neuron b (b ∪ A ∪ C = V ) sends a message at time t (x b (t) = 1) to its connected neighbors is given by the conditional probability where U is some decision function, the output of which belongs to [0; 1], A represents the subset of neurons that can send information to b, and Eb represents external inputs to b. Defining this probability for all b ∈ V completely specifies the behavior of the neural network V . The problem is a composite hypothesis testing problem, in which parameters defining the likelihoods have to be estimated. It is known that tere is no definitive answer to this problem  . An approach that relies on an estimation of the parameters using maximum likelihood can be used. Letting Ω be the space where parameter θ is searched for and Ω 0 the subspace where θ 0 lives, then the generalized loglikelihood ratio test reads: where θ T i denotes the maximum likelihood estimator of θ under hypothesis i. In the linear Gaussian case, we will recover exactly the measures developed by Geweke. In a more general case, and as illustrated in section IV-B1, as the the maximum likelihood estimates are efficient, we can conjecture that the generalized log likelihood ratio will converge to the causal conditional transfer entropy rate if sufficiently relevant conditions are imposed on the models (e.g., Markov processes with recurrent properties). This approach was described in BIB003 in the bivariate case.