RI: Small: Heuristic Search Algorithms for Probabilistic Graphical Models

RI：小：概率图形模型的启发式搜索算法

• 批准号: 1526842
• 负责人: Rina Dechter
• 金额: $ 50万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526842&HistoricalAwards=false
• 关键词: RI; Small; Heuristic; Search; Algorithms

Probabilistic graphical models are employed throughout science and engineering to solve difficult problems, including automated reasoning and decision making, computer vision, computational biology and genetics, and data mining. However, exact inference is often computationally intractable, necessitating approximations or bounds. While significant progress has been made, many real-world problems remain out of reach. Many techniques require a set of problem-specific customizations and choices that must be made in advance, with little guidance or automation.The goal of this research is to develop the next generation of approximate, anytime inference algorithms for graphical models. The PIs will empower search algorithms by strengthening their guiding heuristic functions using variational bounds that are both pre-compiled as well as re-computed dynamically during search. The new algorithms ensure compact search spaces by exploiting the problems' decomposition (using AND/OR search), equivalence (by caching) and pruning irrelevant subspaces using the power of their bounding heuristics. These frameworks will additionally provide automated guidance for selecting parameters to optimize the inherent trade-offs between complexity and accuracy to provide meaningful any-time bounds, while tuning those decisions to the respective benchmarks and instances.

概率图模型在整个科学和工程中用于解决困难的问题，包括自动推理和决策，计算机视觉，计算生物学和遗传学以及数据挖掘。 然而，精确推理通常在计算上是难以处理的，需要近似或界限。 虽然取得了重大进展，但现实世界的许多问题仍然无法解决。许多技术需要一组特定于问题的定制和选择，必须提前，很少的指导或automation.The本研究的目标是开发下一代的近似，随时推理算法的图形模型。PI将通过使用变分边界来增强搜索算法的引导启发式功能，这些变分边界在搜索过程中既经过预编译又经过动态重新计算。新算法通过利用问题的分解（使用AND/OR搜索），等价（通过缓存）和使用其边界算法的能力修剪不相关的子空间来确保紧凑的搜索空间。这些框架还将为选择参数提供自动化指导，以优化复杂性和准确性之间的固有权衡，从而提供有意义的任何时间范围，同时根据相应的基准和实例调整这些决策。