CIF: Small: Towards Structural Information

由于能够高速、多样、大量地获取各种自然和工程过程的数据，因此需要获得新的见解，并将原始数据转化为特定于环境的知识，作为结构信息，这对工程和科学的进一步发展至关重要。该项目追求信息论基础，受到信息论在为相对简单的随机过程类（如马尔可夫过程或遍历序列）相关问题建立基本限制方面的巨大成功的启发。许多现实世界的领域表现出的复杂性违反了用于推导这些基本结果的假设。例如，数据库通常具有很强的结构相关性，而这些底层数据结构通常不适合在经典的信息理论框架中进行表述。在其他情况下，数据可解释性本身就是一个问题：例如，没有产品推荐与负面推荐是不同的。许多分析任务的结果，包括推理和推荐，不容易用传统的信息论形式化来建模。尽管存在这些挑战，但该项目认为，在当今的应用程序中，当处理规模、速度和复杂性的数据时，受信息理论启发的形式化是至关重要的，在这些应用程序中，来自临时分析的解决方案的可靠性可能会受到质疑。作为该项目的一部分开发的工具将用于生物和社会网络的表征以及开发强大的普及通信基础设施等领域。数据越来越多地以各种形式出现，其数量呈指数级增长。大多数此类数据是多维的，依赖于上下文；因此，需要新颖的结构理论和高效的算法来提取有意义的信息。通常，这些新类型数据的数据库采用“数据结构”的形式，而“数据结构”又传递数据的“形状”。数据本身由植入结构中的标签组成，通常是局部相关的。本项目旨在量化这种多模态数据结构所传达的信息，具体目标如下：(1)发现具有相关标签的广泛多模态数据结构的信息内容的基本限制。一旦达到这个目标，该项目将设计渐近最优的无损和有损压缩算法来达到这些限制。(2)为图压缩（带有相关标签）和图数据挖掘开发类似Lempel-Ziv的算法。(3)理解具有马尔可夫场描述的局部相互依赖、约束和相互作用的大型系统的结构特性。最后，(4)分析结构信息在噪声信道上的流动。

With the ability to acquire data at high velocity, variety, and volume on diverse natural and engineered processes, comes the need to derive novel insights and translate raw data into context-specific knowledge as structural information, of crucial importance for further advances in engineering and science. This project pursues an information theoretic foundation, inspired by the great success of information theory in establishing fundamental limits for problems related to relatively simple classes of random processes (such as Markov processes or ergodic sequences). Many real-world domains exhibit complexities that violate assumptions used to derive these fundamental results. For example, data bases often have strong structural correlations, and these underlying data structures often do not lend themselves naturally to formulation in the classical information-theoretic framework. In yet other cases, data interpretability is itself an issue: as an example, the absence of a product recommendation is distinct from a negative recommendation. The outcome of many analytics tasks, including inference and recommendation, is not easily modeled by traditional information theory formalisms. These challenges notwithstanding, this project posits that formalisms inspired by information theory are critical when dealing with data at scale, speed, and complexity in today's applications, where reliability of solutions from ad-hoc analytics can be questioned. Tools developed as part of the project will be used in areas such as the characterization of biological and social networks, and development of robust pervasive communications infrastructure.Data is increasingly available in various forms and it appears in exponentially increasing amounts. Most of such data is multidimensional and context dependent; thus it necessitates novel structural theory and efficient algorithms to extract meaningful information. Typically, a database for these new types of data is in the form of a "data structure," which in turn conveys a "shape" of the data. The data itself consist of labels implanted in the structure, often locally correlated. This project aims to quantify the information conveyed by such multimodal data structures, via the following specific goals: (1) Discover fundamental limits of information content for a wide range of multimodal data structures with correlated labels. Once this goal is met, the project will devise asymptotically optimal lossless and lossy compression algorithms achieving these limits. (2) Develop Lempel-Ziv like algorithms for graph compression (with correlated labels) and graph data mining. (3) Understand structural properties of large systems with local mutual dependencies, constraints, and interactions often described by Markov fields. Finally, (4) Analyze flow of structural information over a noisy channel.