权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Complexity of Representations for Inference

AF：小：推理表示的复杂性

基本信息

批准号：
2006359
负责人：
Paul Beame
金额：
$ 35万
依托单位：
University of Washington
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-08-01 至 2024-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006359&HistoricalAwards=false
关键词：
AF Small Complexity Representations Inference

项目摘要

The use of computers to store data, and calculate results based on that data, is familiar. However, people also use computers to reason; that is, to take what is known to be true about the world and infer logical consequences of these properties. Sometimes, information about the world is measured in terms of probabilities rather than certainties. In this case, the goal is to infer the probability that a particular property of the world follows as a consequence; i.e., computers are used for probabilistic inference as well as logical inference. Finally, there is the process of using observations about the world to infer properties of the world that are not directly measurable. All of these kinds of inference have become increasingly widespread and important computational applications, including critically important ones of verifying the correctness of software and hardware. In these inference problems, one can represent the information for inference in a variety of different ways and, in developing inference methods, one must consider both the complexity of computing these representations and the efficiency of making inferences from them. This project focuses on analyzing specific representations and associated inference methods that have the potential to improve the overall efficiency of inference and permit efficient inference in a wider variety of situations where it is needed.This project will analyze the strengths and limitations of logical inference based on semi-algebraic representations, which are representations in which information is expressed as polynomial inequalities. In particular, the project will analyze semi-algebraic reasoning as a higher-degree generalization of cutting-planes reasoning and as a dynamic generalization of sum-of squares reasoning, which already captures the best algorithms known for a wide range of NP-hard optimization problems, such as those based on semi-definite programming. This project will also focus on the analysis and methods for sum-product-complement networks, a representation that permits efficient weighted-model counting, a cornerstone of methods for exact probabilistic inference. This will build on methods for less powerful sum-product networks and branching programs, which sum-product-complement networks generalize. Finally, this project will develop stronger and more general analytical tools for understanding the capabilities of algorithms for inductive inference that are themselves expressed as restricted branching programs.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.

使用计算机存储数据并基于该数据计算结果是熟悉的。然而，人们也使用计算机进行推理;也就是说，采取已知的关于世界的真实情况，并推断这些属性的逻辑结果。有时，关于世界的信息是用概率而不是概率来衡量的。在这种情况下，目标是推断世界的特定属性作为结果的概率;即，计算机用于概率推理以及逻辑推理。最后，还有一个过程，即利用对世界的观察来推断世界上不可直接测量的属性。所有这些类型的推理已经成为越来越广泛和重要的计算应用，包括验证软件和硬件正确性的至关重要的应用。在这些推理问题中，人们可以以各种不同的方式表示用于推理的信息，并且在开发推理方法时，必须考虑计算这些表示的复杂性和从它们进行推理的效率。本课题主要分析能够提高推理的整体效率，并在需要的情况下进行有效推理的特定表示法和推理方法。本课题将分析以多项式不等式表示信息的半代数表示法为基础的逻辑推理的优点和局限性。特别是，该项目将分析半代数推理作为切割平面推理的更高程度的概括和平方和推理的动态概括，它已经捕获了广泛的NP难优化问题的最佳算法，例如基于半定规划的算法。该项目还将侧重于和-积-补网络的分析和方法，这是一种允许有效加权模型计数的表示法，是精确概率推理方法的基石。这将建立在不太强大的和积网络和分支程序的方法上，和积补网络推广了这些方法。最后，该项目将开发更强大和更通用的分析工具，用于理解归纳推理算法的能力，这些算法本身表示为受限分支程序。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。