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

RI：小：概率图形模型的随时算法和界限

基本信息

批准号：
2008516
负责人：
Rina Dechter
金额：
$ 45万
依托单位：
University of California-Irvine
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008516&HistoricalAwards=false
关键词：
RI Small Anytime Algorithms Bounds

项目摘要

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.

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