AF: Small: Complexity of Representations for 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.