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.