CRII: RI: Efficient Structure Learning and Approximation of Networks of Causally Interacting Processes

网络的研究在许多科学领域都很重要：神经科学，微生物学，社会科学和经济学，仅举几例。 这些领域的一个主要挑战是确定网络中的因果影响。 实验可以直接确定因果影响。 然而，与被动地记录网络中的活动并从这些观察结果中推断影响相比，它可能成本更高，实用性更低。 有许多方法可以从观测数据中识别相关性，尽管识别因果关系通常需要专业知识或强大的建模假设。 为了从网络时间序列数据中提取相关信息以方便人类分析，需要一种计算效率高、统计鲁棒的因果推理方法，本研究旨在显著推进时间序列之间因果影响的推理技术。 该研究开发了新的和有效的算法来学习和近似最近提出的概率图模型的结构：有向信息图。 该算法找到网络拓扑的最佳或接近最佳的近似，具有用户控制的稀疏水平，如图中的边数或执行的计算量。 近似的质量是用Kullback-Leibler散度来衡量的。 这项工作还涉及证明算法的正确性，并开发出一些变体，这些变体可以找到对噪声或有限数据具有鲁棒性的可证明良好的近似值。 为了实现这些目标，该项目为定向信息开发了新的界限。

The study of networks is important in numerous scientific domains: neuroscience, microbiology, social science, and economics, to name a few. A major challenge in these fields is to identify causal influences in the networks. Experimentation can directly determine causal influences. However, it can be more costly and less practical than passively recording activity in the network and inferring influences from those observations. There are numerous methods that can identify correlations from observational data, though identifying causal relationships often requires expert knowledge or strong modeling assumptions. There is a need for computationally efficient and statistically robust causal inference methods to extract relevant information from network time-series data to facilitate human analysis.This research aims to significantly advance the state of the art in inferring causal influences between time-series. The research develops new and efficient algorithms to learn and approximate the structure of a recently proposed probabilistic graphical model: the directed information graph. The algorithms find optimal or near-optimal approximations of the network topology that have user-controlled sparsity levels, such as the number of edges in the graph or the amount of computation performed. The quality of approximation is measured using Kullback-Leibler divergence. The work also involves proving correctness of the algorithms and developing variations that find provably-good approximations which are robust to noisy or limited data. To achieve these goals, the project develops new bounds for directed information.