AF: Small: Complexity of Representations for Inference

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

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.