RI: Medium: Sentential Decision Diagrams

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

Logical and probabilistic reasoning are now routinely used in various fields of computer science and engineering, including artificial intelligence in particular. These modes of reasoning currently underlie systems that perform automated diagnosis, planning, software and hardware verification, web information extraction, bioinformatics, vision and robotics. This project aims at advancing the state of the art in logical and probabilistic reasoning, to allow scientists and engineers to learn and reason with much larger models than is currently possible. The project is based on a particular computational paradigm, known as knowledge compilation, which transforms knowledge into forms that facilitate their efficient processing by reasoning and learning algorithms. The results expected from this project will provide domain-independent, highly scalable, tools and techniques for addressing computational problems that arise in healthcare, industrial automation, and information management. The project will also provide a context for training graduate students in the computational paradigm of knowledge compilation, and will target the integration of this paradigm into computer science curricula. More specifically, the project aims to develop a new framework for knowledge compilation based on the recently discovered Sentential Decision Diagram (SDD). The SDD is a target compilation language, which generalizes the Ordered Binary Decision Diagram (OBDD) that has been quite influential in many areas of computer science and engineering. This project has two parts. The first part is concerned with developing the SDD compilation language further, both theoretically and practically. On the theoretical side, there is a number of pending of questions relating to lower and upper bounds on SDDs, in addition to questions that must be answered to fully understand their relation to OBDDs. On the practical side, the SDD package needs to be extended to enhance its scalability and to provide new functionality that is needed for fully exploiting SDDs in a wider spectrum of applications. The second part of the project is concerned with a more recent discovery: The probabilistic SDD (PSDD). This compilation language aims at inducing probability distributions over propositional theories, in a very principled and efficient manner. Our objective here is to develop PSDDs into a mature tool, with a corresponding public package, for learning tractable probabilistic models under massive logical constraints, and for compiling probabilistic graphical models into PSDDs for the purpose of more scalable probabilistic reasoning.