CIF: Small: Collaborative Research: Inference of Information Measures on Large Alphabets: Fundamental Limits, Fast Algorithims, and Applications

CIF：小型：协作研究：大字母表上信息测量的推断：基本限制、快速算法和应用

• 批准号: 1527105
• 负责人: Yihong Wu
• 金额: $ 25万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2017-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527105&HistoricalAwards=false
• 关键词: CIF; Small; Collaborative; Research; Inference

A key task in information theory is to characterize fundamental performance limits in compression, communication, and more general operational problems involving the storage, transmission and processing of information. Such characterizations are usually in terms of information measures, among the most fundamental of which are the Shannon entropy and the mutual information. In addition to their prominent operational roles in the traditional realms of information theory, information measures have found numerous applications in many statistical modeling and machine learning tasks. Various modern data-analytic applications deal with data sets naturally viewed as samples from a probability distribution over a large domain. Due to the typically large alphabet size and resource constraints, the practitioner contends with the difficulty of undersampling in applications ranging from corpus linguistics to neuroscience. One of the main goals of this project is the development of a general theory based on a new set of mathematical tools that will facilitate the construction and analysis of optimal estimation of information measures on large alphabets. The other major facet of this project is the incorporation of the new theoretical methodologies into machine learning algorithms, thereby significantly impacting current real-world learning practices. Successful completion of this project will result in enabling technologies and practical schemes - in applications ranging from analysis of neural response data to learning graphical models - that are provably much closer to attaining the fundamental performance limits than existing ones. The findings of this project will enrich existing big data-analytic curricula. A new course dedicated to high-dimensional statistical inference that addresses estimation for large-alphabet data in depth will be created and offered. Workshops on the themes and findings of this project will be organized and held at Stanford and UIUC. A comprehensive approximation-theoretic approach to estimating functionals of distributions on large alphabets will be developed via computationally efficient procedures based on best polynomial approximation, with provable essential optimality guarantees. Rooted in the high-dimensional statistics literature, our key observation is that while estimating the distribution itself requires the sample size to scale linearly with the alphabet size, it is possible to accurately estimate functionals of the distribution, such as entropy or mutual information, with sub-linear sample complexity. This requires going beyond the conventional wisdom by developing more sophisticated approaches than maximal likelihood (?plug-in?) estimation. The other major facet of this project is translating the new theoretical methodologies into highly scalable and efficient machine learning algorithms, thereby significantly impacting current real-world learning practices and significantly boosting the performance in several of the most prevalent machine learning applications, such as learning graphical models, that rely on mutual information estimation.

信息理论的关键任务是表征压缩，通信以及涉及信息的存储，传输和处理的更通用的操作问题中的基本绩效限制。这种特征通常是在信息度量方面，其中最基本的是香农熵和相互信息。除了它们在信息理论的传统领域中的突出作用外，信息度量还发现了许多统计建模和机器学习任务中的许多应用。各种现代数据分析应用程序涉及从大型域上的概率分布中自然视为样本的数据集。由于通常具有较大的字母大小和资源限制，因此从业者争辩说，在从语料库语言学到神经科学等的应用中，难以实现采样。该项目的主要目标之一是基于一组新的数学工具的一般理论的发展，该工具将有助于构建和分析大型字母内信息测量的最佳估计。该项目的另一个主要方面是将新的理论方法纳入机器学习算法，从而显着影响当前的现实世界学习实践。 该项目的成功完成将导致启用技术和实用方案 - 在从分析神经响应数据到学习图形模型的应用中 - 事实证明，这些计划比获得基本绩效限制要比现有方案更接近。该项目的发现将丰富现有的大数据分析课程。 将创建和提供一项专门针对高维统计推断的新课程，该课程将在深入的深度估算中进行估算。该项目主题和发现的研讨会将在斯坦福大学和UIUC举行。将通过基于最佳多项式近似的计算有效程序来开发一种全面的近似理论方法来估计大型字母上的分布功能，并具有可证明的基本最佳保证。我们的主要观察结果是植根于高维统计文献，但虽然估计分布本身需要与字母大小线性缩放，但可以准确估算分布的功能，例如熵或相互信息，且具有亚线性样品复杂性。这需要超越传统观点，而不是开发更多的复杂方法，而不是最大可能性（？插件？）估计。该项目的另一个主要方面是将新的理论方法转化为高度可扩展，高效的机器学习算法，从而显着影响当前的现实世界学习实践，并显着提高依赖相互信息估计的几种最普遍的机器学习应用程序，例如最普遍的机器学习应用程序，例如学习图形模型。