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

概率图模型广泛应用于科学和工程领域，用于解决难题、理解大型数据集或对复杂现象进行预测。从图形模型中进行预测或决策涉及具有挑战性的P-困难计算问题，并且高度要求有效的近似方法。最有用的近似不仅应该给出准确的估计，而且（1）具有严格和保守的误差界限，（2）可以不断改进，以节省内存和可预测的方式（“随时”属性）来换取增加的准确性。这样的算法应该让我们能够解决简单的问题，并提供强有力的准确性证明，同时也能识别更难的问题，并提供进一步改进的明确指导。不幸的是，大多数最先进的方法，包括确定性变分方法和基于蒙特卡罗的方法，往往不能完全满足这些标准。 本计画旨在发展新一代具有紧密非渐近置信限及随时性的推理工具。基于将变分推理与Monte Carlo的非渐近界联系起来的几个关键见解，PI推导出一系列强大的方法，这些方法自然地整合并联合收割机结合了这两种方法的优势，为更可靠的推理提供了新的基础。该项目还为先进的蒙特卡罗方法（如退火重要性采样（AIS））开发了新的非渐近误差界，在此基础上，研究人员构建了基于最先进AIS的高效估计和边界。这些方法在各种应用领域进行了广泛的测试，并为从业者提供了实用的指导和开源软件包。新的强大的随时、错误感知的推理工具将在不同的应用领域中更可靠地使用图形模型，大大扩展我们对大型数据集和复杂现象的推理能力。

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.