CIF: Small: Towards Structural Information

Purdue University, West Lafayette IN

Investigators

Abstract

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.