Universal Estimation of Directed Information

Abstract

Four estimators of the directed information rate between a pair of jointly stationary ergodic finite-alphabet processes are proposed, based on universal probability assignments. The first one is a Shannon--McMillan--Breiman type estimator, similar to those used by Verdú (2005) and Cai, Kulkarni, and Verdú (2006) for estimation of other information measures. We show the almost sure and $L_1$ convergence properties of the estimator for any underlying universal probability assignment. The other three estimators map universal probability assignments to different functionals, each exhibiting relative merits such as smoothness, nonnegativity, and boundedness. We establish the consistency of these estimators in almost sure and $L_1$ senses, and derive near-optimal rates of convergence in the minimax sense under mild conditions. These estimators carry over directly to estimating other information measures of stationary ergodic finite-alphabet processes, such as entropy rate and mutual information rate, with near-optimal performance and provide alternatives to classical approaches in the existing literature. Guided by these theoretical results, the proposed estimators are implemented using the context-tree weighting algorithm as the universal probability assignment. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the utility of directed information estimation in detecting and measuring causal influence and delay.

23 pages, 10 figures, to appear in IEEE Transactions on Information Theory

Cited by in corpus (20)

• Identifying Seizure Onset Zone from the Causal Connectivity Inferred Using Directed Information
• Justification of Logarithmic Loss via the Benefit of Side Information
• Task-driven intra- and interarea communications in primate cerebral cortex
• Information Flow in Computational Systems
• Minimax rates of entropy estimation on large alphabets via best polynomial approximation
• Importance of Small Probability Events in Big Data: Information Measures, Applications, and Challenges
• Posterior Representations for Bayesian Context Trees: Sampling, Estimation and Convergence
• Polynomial methods in statistical inference: theory and practice
• ITENE: Intrinsic Transfer Entropy Neural Estimator
• $k$-NN Estimation of Directed Information
• Stochastic thermodynamics of interacting degrees of freedom: Fluctuation theorems for detached path probabilities
• Inferring ECG from PPG for Continuous Cardiac Monitoring Using Lightweight Neural Network
• Transfer-Entropy-Regularized Markov Decision Processes
• Testing for directed information graphs
• Entropy Rate Estimation for Markov Chains with Large State Space
• Causality Graph of Vehicular Traffic Flow
• Detecting Nonlinear Causality in Multivariate Time Series with Sparse Additive Models
• A Sample Path Measure of Causal Influence
• Causal Structure Identification from Corrupt Data-Streams
• Fundamental Limits of Prediction, Generalization, and Recursion: An Entropic-Innovations Perspective