RI: Small: Anytime Algorithms and Bounds for Probabilistic Graphical Models

概率图形模型在科学和工程中被用来解决困难的问题，包括自动推理和决策、计算机视觉、计算生物学和遗传学以及数据挖掘。然而，精确的推论通常在计算上是困难的，需要近似或界限。虽然已经取得了重大进展，但许多现实世界的问题仍然遥不可及。许多技术需要一组特定于问题的定制和选择，这些定制和选择必须事先做出，几乎没有指导或自动化。我们的研究将提高概率图形模型的性能，并使这些技术得到更广泛的应用。研究人员通过他们的本科和研究生教学，以及通过向研究人员和公众提供他们的软件来支持教育和多样性。本研究的目标是开发用于图形模型的下一代近似、随时推理技术和算法。在启发式搜索框架的启发下，调查人员将为消息传递、振动和采样算法创建改进的统一方案。这些新算法试图有效地管理包含概率关系和确定性关系的混合模型，以及基于图和特定于上下文的独立关系。它们将对结果和算法的准确性提供有意义的界限，同时简化或自动化对问题实例的任何所需调整，优化复杂性和准确性之间的内在权衡。该算法将扩展到最具挑战性的任务(即最大和乘积任务)，例如用于最优决策的最大期望效用查询。调查人员将与领域专家合作，将他们的算法应用于规划和计算蛋白质设计等应用程序。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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. Our research will both improve the performance of probabilistic graphical models and will make these techniques more widely available. The investigators support education and diversity through their undergraduate and graduate teaching, and through making their software available to researchers and to the public.The goal of this research is to develop the next generation of approximate, anytime inference techniques and algorithms for graphical models. Informed by the framework of heuristic search, the investigators will create improved unified schemes for message-passing, vibrational and sampling algorithms. These new algorithms seek to effectively manage models containing mixtures of probabilistic and deterministic relationships, as well as both graph-based and context-specific independence relationships. They will provide meaningful bounds on the results and the accuracy of the algorithms, while simplifying or automating any required tuning to the problem instance, optimizing the inherent trade-offs between complexity and accuracy. The algorithms will be extended to the most challenging tasks (i.e., max-sum-product tasks) such as maximum expected utility queries for optimal decision-making. The investigators will collaborate with domain experts to apply their algorithms to applications such as planning and computational protein design.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.