CRII: RI: Anytime Inference with Confidence Bounds for Graphical Models

CRII：RI：图形模型的随时推理与置信界限

• 批准号: 1565796
• 负责人: Qiang Liu
• 金额: $ 15.77万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-04-01 至 2018-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1565796&HistoricalAwards=false
• 关键词: CRII; RI; Anytime; Inference; Confidence

Probabilistic graphical models are widely used throughout science and engineering to solve difficult problems, understand large data sets, or make predictions about complex phenomena. Making predictions or decisions out of graphical models involves challenging #P-hard computational problems, and efficient approximation methods are highly demanded. The most useful approximations should give not only accurate estimates, but also (1) come with tight and conservative error bounds and (2) can be improved continuously to trade time for increased accuracy in a memory efficient and predictable way (an "anytime" property). Such algorithms should allow us to solve easy problems with strong certificates of accuracy, and also identify harder problems together with clear guidance for further improvement. Unfortunately, most state-of-the-art methods, including deterministic variational methods and Monte Carlo-based methods, often do not fully satisfy these criteria. This project aims to develop a new generation of inference tools with tight non-asymptotic confidence bounds and anytime property. Based on several key insights that connect variational inference with non-asymptotic bounds of Monte Carlo, the PI derives a spectrum of powerful methods that naturally integrate and combine the advantages of these two approaches, providing a new foundation for more reliable inference. The project also develops novel non-asymptotic error bounds for advanced Monte Carlo methods such as annealed importance sampling (AIS), based on which the researchers construct highly efficient estimates and bounds built on the state-of-the-art AIS. The approaches are tested extensively on various application domains, and provide practical guidance and open source packages for practitioners. The new powerful anytime, error-aware inference tools will lead much more reliable use of graphical models across different application domains, greatly expanding our ability of reasoning over large datasets and complex phenomena.

概率图形模型在整个科学和工程中广泛使用，以解决困难问题，了解大数据集或对复杂现象做出预测。从图形模型中做出预测或决策涉及挑战＃P-HARD计算问题，并且高度要求有效的近似方法。最有用的近似值不仅应给出准确的估计值，而且（1）具有紧密而保守的误差范围，（2）可以连续改善以交易时间以增加记忆效率和可预测的方式（“随时”属性）。这样的算法应该使我们能够使用强大的准确性证书解决简单问题，并确定更困难的问题，并明确指导进一步改进。不幸的是，大多数最先进的方法，包括确定性变分方法和基于蒙特卡洛的方法，通常无法完全满足这些标准。 该项目旨在开发新一代的推理工具，具有紧密的非肿瘤信心范围和任何时间属性。基于几种关键见解，这些见解将变异推理与蒙特卡洛的非质子界界联系起来，PI得出了一系列强大的方法，这些方法自然地整合并结合了这两种方法的优势，为更可靠的推断提供了新的基础。该项目还为先进的蒙特卡洛方法（例如退火重要性采样（AIS））开发了新型的非反应误差范围，研究人员构建了基于先进的AIS建立的高效估计和界限。这些方法在各个应用程序领域进行了广泛的测试，并为从业者提供了实用的指导和开源包。随时随地，新功能的推理工具将引导对不同应用程序域上图形模型的更可靠使用，从而大大扩展了我们对大型数据集和复杂现象的推理能力。