The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> There occurs on some occasions a difficulty in deciding the direction of causality between two related variables and also whether or not feedback is occurring. Testable definitions of causality and feedback are proposed and illustrated by use of simple two-variable models. The important problem of apparent instantaneous causality is discussed and it is suggested that the problem often arises due to slowness in recording information or because a sufficiently wide class of possible causal variables has not been used. It can be shown that the cross spectrum between two variables can be decomposed into two parts, each relating to a single causal arm of a feedback situation. Measures of causal lag and causal strength can then be constructed. A generalisation of this result with the partial cross spectrum is suggested. <s> BIB001 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> A generalization of information theory is presented with the aim of distinguishing the direction of information flow for mutually coupled statistical systems. The bidirectional communication theory refers to two systems. Two directed transinformations are defined which are a measure of the statistical coupling between the systems. Their sum equals Shannon's transinformation. An information flow diagram explains the relation between the directed transinformations and the entropies of the sources. An extension to a group of such systems has also been proposed. The theory is able to describe the informational relationships between living beings and other multivariate complex systems as encountered in economy. An application example referring to group behavior with monkeys is given. <s> BIB002 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> A simple formulation is given for the notion of feedback between two stationary stochastic processes in terms of the canonical representation of the joint process. The definition presented here has an equivalent formulation in terms of filtering theory, and provides statistical criteria for the detection of feedback. A simulation example is presented and an application to the United Kingdom unemployment-gross domestic product relation is described. <s> BIB003 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> In this note the relationship between alternative concepts of noncausality is analyzed using the tool of conditional independence among a-fields. (For the reader who is unfamiliar with this technique, the Appendix sketches the proofs and the basic technical apparatus, along with some basic motivations.) Furthermore, the relationship between the concepts of noncausality and transitivity is made explicit in order to facilitate, in econometric modelling, the use of results already obtained in sequential analysis. <s> BIB004 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <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> BIB005 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <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> BIB006 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <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> BIB007 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> New measures are proposed for mutual and causal dependence between two time series, based on information theoretical ideas. The measure of mutual dependence is shown to be the sum of the measure of unidirectional causal dependence from the first time series to the second, the measure of unidirectional causal dependence from the second to the first, and the measure of instantaneous causal dependence. The measures are applicable to any kind of time series: continuous, discrete, or categorical. <s> BIB008 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> It is shown that the "usual definition" of a discrete memoryless channel (DMC) in fact prohibits the use of feedback. The difficulty stems from the confusion of causality and statistical dependence. An adequate definition of a DMC is given, as well as a definition of using a channel without feedback. A definition, closely based on an old idea of Marko, is given for the directed information flowing from one sequence to another. This directed information is used to give a simple proof of the well-known fact that the use of feedback cannot increase the capacity of a DMC. It is shown that, when feedback is present, directed information is a more useful quantity than the traditional mutual information. <s> BIB009 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <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> BIB010 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> Analysis of observational temperature records for the Northern and Southern hemispheres indicates a statistical relationship in which Northern Hemisphere temperature depends on temperature in the Southern Hemisphere. This pattern, which has strengthened over time, can be explained by the climatic effects of anthropogenic trace gases and tropospheric sulphate aerosols. A similar statistical patternis produced by model simulations of the historical atmosphere. <s> BIB011 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> An information theoretic measure is derived that quantifies the statistical coherence between systems evolving in time. The standard time delayed mutual information fails to distinguish information that is actually exchanged from shared information due to common history and input signals. In our new approach, these influences are excluded by appropriate conditioning of transition probabilities. The resulting transfer entropy is able to distinguish effectively driving and responding elements and to detect asymmetry in the interaction of subsystems. <s> BIB012 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> A general definition of causality is introduced and then specialized to become operational. By considering simple examples a number of advantages, and also difficulties, with the definition are discussed. Tests based on the definitions are then considered and the use of post-sample data emphasized, rather than relying on the same data to fit a model and use it to test causality. It is suggested that a bayesian viewpoint should be taken in interpreting the results of these tests. Finally, the results of a study relating advertising and consumption are briefly presented. <s> BIB013 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> Part I. Basic Concepts: 1. Introduction: why nonlinear methods? 2. Linear tools and general considerations 3. Phase space methods 4. Determinism and predictability 5. Instability: Lyapunov exponents 6. Self-similarity: dimensions 7. Using nonlinear methods when determinism is weak 8. Selected nonlinear phenomena Part II. Advanced Topics: 9. Advanced embedding methods 10. Chaotic data and noise 11. More about invariant quantities 12. Modeling and forecasting 13. Chaos control 14. Other selected topics Appendix 1. Efficient neighbour searching Appendix 2. Program listings Appendix 3. Description of the experimental data sets. <s> BIB014 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> An information-theoretic approach for studying synchronization phenomena in experimental bivariate time series is presented. "Coarse-grained" information rates are introduced and their ability to indicate generalized synchronization as well as to establish a "direction of information flow" between coupled systems, i.e., to discern the driving from the driven (response) system, is demonstrated using numerically generated time series from unidirectionally coupled chaotic systems. The method introduced is then applied in a case study of electroencephalogram recordings of an epileptic patient. Synchronization events leading to seizures have been found on two levels of organization of brain tissues and "directions of information flow" among brain areas have been identified. This allows localization of the primary epileptogenic areas, also confirmed by magnetic resonance imaging and pasitron emission tomography scans. <s> BIB015 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> A paper recently published in Nature finds that there is sufficient evidence to identify the effects of human activity on global temperature. The study is based on northern and southern hemispheres' time series temperature from 1865 to 1994 and the econometric technique applied is Granger causality analysis. In this note, we make some critical remarks on the conclusions of this study which seem to be rather inconsistent from a methodological point of view. It is shown that a more accurate application of Granger causality analysis to this problem may not allow the same strong and unambiguous conclusions. <s> BIB016 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> We discuss a recently proposed quantity, called transfer entropy, which uses time series data to measure the amount of information transferred from one process to another. In order to understand its foundation, merits, and limitations, we review some aspects of information theoretic functionals. While for symbol sequences these measures have an intuitive interpretation, their application to continuous state processes and, in particular, their estimation from finite data sets is problematic. For mutual information, finite length scale estimates converge from below and can thus be used to reject the assumption that the observed processes are independent. However, mutual information does not provide any directional information. Conversely, transfer entropy does resolve the directionality of information exchange but no similar monotonic convergence seems to hold. Thus, only in the case of zero transfer entropy in one direction we can reliably infer an asymmetry of the information exchange. <s> BIB017 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> There is an increasing interest in studying control systems employing multiple sensors and actuators that are geographically distributed. Communication is an important component of these distributed and networked control systems. Hence, there is a need to understand the interactions between the control components and the communication components of the distributed system. In this paper, we formulate a control problem with a communication channel connecting the sensor to the controller. Our task involves designing the channel encoder and channel decoder along with the controller to achieve different control objectives. We provide upper and lower bounds on the channel rate required to achieve these different control objectives. In many cases, these bounds are tight. In doing so, we characterize the "information complexity" of different control objectives. <s> BIB018 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> The identification of effective connectivity from time-series data such as electroencephalogram (EEG) or time-resolved function magnetic resonance imaging (fMRI) recordings is an important problem in brain imaging. One commonly used approach to inference effective connectivity is based on vector autoregressive models and the concept of Granger causality. However, this probabilistic concept of causality can lead to spurious causalities in the presence of latent variables. Recently, graphical models have been used to discuss problems of causal inference for multivariate data. In this paper, we extend these concepts to the case of time-series and present a graphical approach for discussing Granger-causal relationships among multiple time-series. In particular, we propose a new graphical representation that allows the characterization of spurious causality and, thus, can be used to investigate spurious causality. The method is demonstrated with concurrent EEG and fMRI recordings which are used to investigate the interrelations between the alpha rhythm in the EEG and blood oxygenation level dependent (BOLD) responses in the fMRI. The results confirm previous findings on the location of the source of the EEG alpha rhythm. <s> BIB019 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> The directed transfer function (DTF) has been proposed as a measure of information flow between the components of multivariate time series. In this paper, we discuss the interpretation of the DTF and compare it with other measures for directed relationships. In particular, we show that the DTF does not indicate multivariate or bivariate Granger causality, but that it is closely related to the concept of impulse response function and can be viewed as a spectral measure for the total causal influence from one component to another. Furthermore, we investigate the statistical properties of the DTF and establish a simple significance level for testing for the null hypothesis of no information flow. <s> BIB020 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> We introduce graphical time series models for the analysis of dynamic relationships among variables in multivariate time series. The modelling approach is based on the notion of strong Granger causality and can be applied to time series with non-linear dependences. The models are derived from ordinary time series models by imposing constraints that are encoded by mixed graphs. In these graphs each component series is represented by a single vertex and directed edges indicate possible Granger-causal relationships between variables while undirected edges are used to map the contemporaneous dependence structure. We introduce various notions of Granger-causal Markov properties and discuss the relationships among them and to other Markov properties that can be applied in this context. Examples for graphical time series models include nonlinear autoregressive models and multivariate ARCH models. <s> BIB021 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> In this paper, we will present and review the most usual methods to detect linear and nonlinear causality between signals: linear Granger causality test (Geweke in J Am Stat Assoc 77:304–313, 1982) extended to direct causality in multivariate case (LGC), directed coherence (DCOH, Saito and Harashima in Recent advances in EEG and EMG data processing, Elsevier, Amsterdam, 1981), partial directed coherence (PDC, Sameshima and Baccala 1999) and nonlinear Granger causality test of Baek and Brock (in Working Paper University of Iowa, 1992) extended to direct causality in multivariate case (partial nonlinear Granger causality, PNGC). All these methods are tested and compared on several ARX, Poisson and nonlinear models, and on neurophysiological data (depth EEG). The results show that LGC, DCOH and PDC are not very robust in relation to nonlinear linkages but they seem to correctly find linear linkages if only the autoregressive parts are nonlinear. PNGC is extremely dependent on the choice of parameters. Moreover, LGC and PNGC may give misleading results in the case of causality on a spectral band, which is illustrated by our neurophysiological database. <s> BIB022 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> Abstract This study uses a Granger causality time series modeling approach to quantitatively diagnose the feedback of daily sea surface temperatures (SSTs) on daily values of the North Atlantic Oscillation (NAO) as simulated by a realistic coupled general circulation model (GCM). Bivariate vector autoregressive time series models are carefully fitted to daily wintertime SST and NAO time series produced by a 50-yr simulation of the Third Hadley Centre Coupled Ocean–Atmosphere GCM (HadCM3). The approach demonstrates that there is a small yet statistically significant feedback of SSTs on the NAO. The SST tripole index is found to provide additional predictive information for the NAO than that available by using only past values of NAO—the SST tripole is Granger causal for the NAO. Careful examination of local SSTs reveals that much of this effect is due to the effect of SSTs in the region of the Gulf Steam, especially south of Cape Hatteras. The effect of SSTs on NAO is responsible for the slower-than-expone... <s> BIB023 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> The systematic inference of biologically relevant influence networks remains a challenging problem in computational biology. Even though the availability of high-throughput data has enabled us to use probabilistic models to infer the plausible structure of such networks, their true interpretation of the biology of the process is questionable. In this work, we propose a probabilistic network inference methodology, based on the Directed information criterion, which incorporates the biology of transcription within the framework, so as to enable experimentally verifiable inference. We use a publicly available embryonic kidney microarray dataset to demonstrate our results on the regulation of the Gata2/Gata3 genes. <s> BIB024 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> We discuss some problems encountered in inference of directionality of coupling, or, in the case of two interacting systems, in inference of causality from bivariate time series. We identify factors and influences that can lead to either decreased test sensitivity or false detections and propose ways to cope with them in order to perform tests with high sensitivity and a low rate of false positive results. <s> BIB025 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> We propose a method to discover couplings in multivariate time series, based on partial mutual information, an information-theoretic generalization of partial correlation. It represents the part of mutual information of two random quantities that is not contained in a third one. By suitable choice of the latter, we can differentiate between direct and indirect interactions and derive an appropriate graphical model. An efficient estimator for partial mutual information is presented as well. <s> BIB026 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> In this work, we consider a source coding model with feed-forward. We analyze a system with a noiseless, feed-forward link where the decoder has knowledge of all previous source samples while reconstructing the present sample. The rate-distortion function for an arbitrary source with feed-forward is derived in terms of directed information, a variant of mutual information. We further investigate the nature of the rate-distortion function with feed-forward for two common types of sources- discrete memory- less sources and Gaussian sources. We then characterize the error exponent for a general source with feed-forward. The results are then extended to feed-forward with an arbitrary delay larger than the block length. <s> BIB027 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> A coding theorem is proved for a class of stationary channels with feedback in which the output Y_n = f(X_{n-m}^n, Z_{n-m}^n) is the function of the current and past m symbols from the channel input X_n and the stationary ergodic channel noise Z_n. In particular, it is shown that the feedback capacity is equal to $$ \limp_{n\to\infty} \sup_{p(x^n||y^{n-1})} \frac{1}{n} I(X^n \to Y^n), $$ where I(X^n \to Y^n) = \sum_{i=1}^n I(X^i; Y_i|Y^{i-1}) denotes the Massey directed information from the channel input to the output, and the supremum is taken over all causally conditioned distributions p(x^n||y^{n-1}) = \prod_{i=1}^n p(x_i|x^{i-1},y^{i-1}). The main ideas of the proof are the Shannon strategy for coding with side information and a new elementary coding technique for the given channel model without feedback, which is in a sense dual to Gallager's lossy coding of stationary ergodic sources. A similar approach gives a simple alternative proof of coding theorems for finite state channels by Yang-Kavcic-Tatikonda, Chen-Berger, and Permuter-Weissman-Goldsmith. <s> BIB028 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> Motif discovery for the identification of functional regulatory elements underlying gene expression is a challenging problem. Sequence inspection often leads to discovery of novel motifs (including transcription factor sites) with previously uncharacterized function in gene expression. Coupled with the complexity underlying tissue-specific gene expression, there are several motifs that are putatively responsible for expression in a certain cell type. This has important implications in understanding fundamental biological processes such as development and disease progression. In this work, we present an approach to the identification of motifs (not necessarily transcription factor sites) and examine its application to some questions in current bioinformatics research. These motifs are seen to discriminate tissue-specific gene promoter or regulatory regions from those that are not tissue-specific. There are two main contributions of this work. Firstly, we propose the use of directed information for such classification constrained motif discovery, and then use the selected features with a support vector machine (SVM) classifier to find the tissue specificity of any sequence of interest. Such analysis yields several novel interesting motifs that merit further experimental characterization. Furthermore, this approach leads to a principled framework for the prospective examination of any chosen motif to be discriminatory motif for a group of coexpressed/coregulated genes, thereby integrating sequence and expression perspectives. We hypothesize that the discovery of these motifs would enable the large-scale investigation for the tissue-specific regulatory role of any conserved sequence element identified from genome-wide studies. <s> BIB029 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> We provide for the first time a formulation of non-linear, nonstationary causality in terms of mutual information. We provide two fundamental mutual information identities; the first relating Granger type causality to Sims type causality. The second providing a decomposition of mutual information into a sum of Granger and Sims type terms. We also develop asymptotic relations that emerge under strict stationarity and generalise earlier work of Geweke. We relate our work in general with earlier developments. <s> BIB030 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> Two directed information measures have been used extensively in literature to evaluate the direction of information flow between two time series. The relationship between these two measures, however, has not been established as to date. In this letter, we derive a formula that defines the relationship between these two measures. We also offer some insights into the interpretation of these measures and their relationship, which are verified through simulations. <s> BIB031 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> In this paper, we introduce a general framework for treating channels with memory and feedback. First, we prove a general feedback channel coding theorem based on Massey's concept of directed information. Second, we present coding results for Markov channels. This requires determining appropriate sufficient statistics at the encoder and decoder. We give a recursive characterization of these sufficient statistics. Third, a dynamic programming framework for computing the capacity of Markov channels is presented. Fourth, it is shown that the average cost optimality equation (ACOE) can be viewed as an implicit single-letter characterization of the capacity. Fifth, scenarios with simple sufficient statistics are described. Sixth, error exponents for channels with feedback are presented. <s> BIB032 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> This paper deals with the study of interacting systems networks. More precisely, we consider the problem of inferring the circulation of information between network nodes. To take into account feedback between signals, as well as instantaneous interaction, we show that the adequate measures of information flow are the directed information and the causal conditional directed information. We relate the framework based on directed information theory to the theory of Granger causality in multivariate time series. An important result of the paper is the proof that linear implementation of Granger causality and directed information theory are equivalent in the Gaussian case. This is proved for the bivariate analysis as well as for the multivariate analysis, for which we extend some of Geweke’s results. The relations between directed information and transfer entropy are provided. A simulation illustrates the main results obtained in the paper through the problem of inferring effective connectivity in a network. <s> BIB033 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <s> Directed information theory deals with communication channels with feedback. When applied to networks, a natural extension based on causal conditioning is needed. We show here that measures built from directed information theory in networks can be used to assess Granger causality graphs of stochastic processes. We show that directed information theory includes measures such as the transfer entropy, and that it is the adequate information theoretic framework needed for neuroscience applications, such as connectivity inference problems. <s> BIB034 </s> The relation between Granger causality and directed information theory: a review <s> B. A historical viewpoint <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> BIB035
In his Nobel prize lecture in 2003, Clive W. Granger mentioned that in 1959, Denis Gabor pointed out the work of Wiener to him, as a hint to solve some of the difficulties he met in his work. Norbert Wiener's paper is about the theory of prediction  . At the end of his paper, Wiener proposed that prediction theory could be used to define causality between time series. Granger further developed this idea, and came up with a definition of causality and testing procedures  , BIB001 . In these studies, the essential stones were laid. Granger's causality states that a cause must occur before the effect, and that causality is relative to the knowledge that is available. This last statement deserves some comment. When testing for causality of one variable on another, it is assumed that the cause has information about the effect that is unique to it; i.e. this information is unknown to any other variable. Obviously, this cannot be verified for variables that are not known. Therefore, the conclusion drawn in a causal testing procedure is relative to the set of measurements that are available. A conclusion reached based on a set of measurements can be altered if new measurements are taken into account. Mention of information theory is also present in the studies of Granger. In the restricted case of two Gaussian signals, Granger already noted the link between what he called the 'causality indices' and the mutual information (Eq. 5.4 in  ). Furthermore, he already foresaw the generalization to the multivariate case, as he wrote in the same paper: "In the case of q variables, similar equations exist if coherence is replaced by partial coherence, and a new concept of 'partial information' is introduced." Granger's paper in 1969 does not contain much new information, but rather, it gives a refined presentation of the concepts. May 5, 2014 DRAFT During the 1970's, some studies, e.g.  , BIB003 ,  , appeared that generalized along some of the directions Granger's work, and related some of the applications to economics. In the early 1980's, several studies were published that established the now accepted definitions of Granger causality BIB013 , BIB004 ,  . These are natural extensions of the ideas built upon prediction, and they rely on conditional independence. Finally, the recent studies of Dalhaus and Eichler allowed the definitions of Granger causality graphs  , BIB020 , BIB021 . These studies provide a counterpart of graphical models of multivariate random variables to multivariable stochastic processes. In two studies published in 1982 and 1984 BIB005 , BIB006 , Geweke, another econometrician, set up a full treatment of Granger causality testing for the Gaussian case, which included the idea of feedback and instantaneous coupling. In BIB005 , the study was restricted to the link between two time series (possibly multidimensional). In this study, Geweke defined an index of causality from x to y; It is the logarithm of the ratio of the asymptotic mean square error when predicting y from its past only, to the asymptotic mean square error when predicting y from its past and from the past of x. Geweke also defined the same kind of index for instantaneous coupling, and showed, remarkably, that the mutual information rate between x and y decomposes as the sum of the indices of causality from x to y and from y to x with the index of instantaneous coupling. This decomposition was shown in the Gaussian case, and it remains valid in any case when the indices of causality are replaced by transfer entropy rates, and the instantaneous coupling index is replaced by an instantaneous information exchange rate. This link between Granger causality and directed information theory was further supported by  ,  (without mention of instantaneous coupling in  ), and the generalization to the nonGaussian case by BIB034 (see also BIB035 for related results). However, prior to these recent studies, the generalization of Geweke's idea to some general setting was reported in 1987, in econometry by Gouriéroux et al. BIB007 , and in engineering by Rissannen&Wax BIB008 . Gouriéroux and his co-workers considered a joint Markovian representation of the signals, and worked in a decision-theoretic framework. They defined a sequence of nested hypotheses, whether causality was true or not, instantaneous coupling was present or not. They then worked out the decision statistics using the Kullback approach to decision theory  , in which discrepancies between hypotheses are measured according to the Kullback divergence between the probability measures under the hypotheses involved. In this setting, the decomposition obtained by Geweke in the Gaussian case was evidently generalised . In BIB008 , the approach taken was closer to Geweke's study, and it relied on system identification, in which the complexity of the model was taken into account. The probability measures were parameterized, and an information measure that jointly assessed the estimation procedure and the complexity of the model was used when predicting a signal. This allowed Geweke's result to be extended to nonlinear modeling (and hence the nonGaussian case), and provided an information-theoretic interpretation of the tests. Once again, the same kind of decomposition of dependence was obtained by these authors. We will see in section III that the decomposition holds due to Kramers causal conditioning. These studies were limited to the bivariate case BIB007 , BIB008 . In the late 1990's, some studies began to develop in the physics community on influences between dynamical systems. A first route was taken that followed the ideas of dynamic system studies for the prediction of chaotic systems. To determine if one signal influenced another, the idea was to consider each of the signals as measured states of two different dynamic systems, and then to study the master-slave relationships between these two systems May 5, 2014 DRAFT (for examples, see  ,  ). The dynamics of the systems was built using phase space reconstruction BIB014 . The influence of one system on another was then defined by making a prediction of the dynamics in the reconstructed phase space of one of the processes. To our knowledge, the setting was restricted to the bivariate case. A second route, which was also restricted to the bivariate case, was taken and relied on information-theoretic tools. The main contributions were from Paluš and Schreiber BIB012 , BIB015 , with further developments appearing some years later BIB017 , BIB025 , BIB026 . In these studies, the influence of one process on the other was measured by the discrepancy between the probability measures under the hypotheses of influence or no influence. Naturally, the measures defined very much resembled the measures proposed by Gouriéroux et. al BIB007 , and used the concept of conditional mutual information. The measure to assess whether one signal influences the other was termed transfer entropy by Schreiber. Its definition was proposed under a Markovian assumption, as was exactly done in BIB007 . The presentation by Paluš BIB015 was more direct and was not based on a decision-theoretic idea. The measure defined is, however, equivalent to the transfer entropy. Interestingly, Paluš noted in this 2001 paper the closeness of the approach to Granger causality, as per the quotation: "the [latter] measure can also be understood as an information theoretic formulation of the Granger causality concept." Note that most of these studies considered bivariate analysis, with the notable exception of BIB026 , in which the presence of side information (other measured time series) was explicitely considered. In parallel with these studies, many others were dedicated to the implementation of Granger causality testing in fields as diverse as climatology (with applications to the controversial questions of global warming) and neuroscience; see  , BIB011 ,  , BIB016 , BIB019 , BIB020 , BIB022 , BIB023 , to cite but a few. In a very different field, information theory, the problem of feedback has lead to many questions since the 1950's. We will not review or cite anything on the problem created by feedback in information theory as this is not within the scope of the present study, but some information can be found in BIB010 . Instead, we will concentrate on studies that are directly related to the subject of this review. A major breakthrough was achieved by James Massey in 1990 in a short conference paper BIB009 . Following the (lost?) ideas of Marko on bidirectional information theory that were developed in the Markovian case BIB002 , Massey re-examined the usual definition of what is called a discrete memoryless channel in information theory, and he showed that the usual definition based on some probabilistic assumptions prohibited the use of feedback. He then clarified the definition of memory and feedback in a communication channel. As a consequence, he showed that in a general channel used with feedback, the usual definition of capacity that relies on mutual information was not adequate. Instead, the right measure was shown to be directed information, an asymmetrical measure of the flow of information. These ideas were further examined by Kramer, who introduced the concept of causal conditioning, and who developed the first applications of directed information theory to communication in networks  . After some years, the importance of causal conditioning for the analysis of communication in systems with feedback was realized. Many studies were then dedicated to the analysis of the capacity of channels with feedback and the dual problem of rate-distortion theory BIB018 , BIB032 , DRAFT BIB027 , BIB028 . Due to the rapid development in the study of networks (e.g., social networks, neural networks) and of the afferent connectivity problem, more recently many authors made connections between information theory and Granger causality  , BIB030 ,  , BIB033 ,  , BIB034 , BIB035 . Some of these studies were restricted to the Gaussian case, and to the bivariate case. Most of these studies did not tackle the problem of instantaneous coupling. Furthermore, several authors realized the importance of directed information theory to assess the circulation of information in networks BIB031 , BIB024 , BIB029 .