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.

概率图形模型在整个科学和工程中都采用了解决困难问题，包括自动推理和决策，计算机视觉，计算生物学和遗传学以及数据挖掘。 但是，精确的推论通常在计算上是棘手的，需要近似或边界。 尽管取得了重大进展，但许多现实世界中的问题仍然遥不可及。许多技术都需要一组针对特定问题的自定义和选择，必须在几乎没有指导或自动化的情况下提前做出。该研究的目的是开发下一代的近似近似值，图形模型的任何时间推理算法。 PI将使用既预先编译并在搜索过程中进行动态重新计算的变异界限来增强其指导启发式功能，从而增强搜索算法的能力。新算法通过利用其边界启发式方法的力量来利用问题的分解（使用和/或搜索），等效性（通过缓存）和修剪无关的子空间来确保紧凑的搜索空间。这些框架还将为选择参数提供自动指导，以优化复杂性和准确性之间的固有权衡，以提供有意义的任何时间界限，同时将这些决策调整为相应的基准和实例。