RI: Small: Heuristic Search Algorithms for Probabilistic Graphical Models

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

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.