RI: Medium: Sentential Decision Diagrams

逻辑和概率推理现在经常用于计算机科学和工程的各个领域，特别是包括人工智能。这些推理模式目前是执行自动诊断、规划、软件和硬件验证、网络信息提取、生物信息学、视觉和机器人技术的系统的基础。该项目旨在推进逻辑和概率推理的最新技术，使科学家和工程师能够学习和推理比目前可能的更大的模型。该项目基于一种特定的计算范式，称为知识汇编，它将知识转化为通过推理和学习算法进行有效处理的形式。该项目的预期结果将提供独立于领域的，高度可扩展的工具和技术，用于解决医疗保健，工业自动化和信息管理中出现的计算问题。该项目还将为培训研究生提供知识汇编的计算范式的背景，并将把这种范式纳入计算机科学课程。更具体地说，该项目旨在根据最近发现的句子决策图（SDD）开发一个新的知识汇编框架。SDD是一种目标编译语言，它推广了在计算机科学和工程的许多领域都很有影响力的有序二元决策图（OBDD）。这个项目有两个部分。第一部分是关于SDD编译语言的进一步发展，包括理论和实践。在理论方面，除了必须回答以充分理解其与OBDD的关系的问题之外，还有一些与SDD的下限和上限有关的悬而未决的问题。在实践方面，SDD包需要扩展，以增强其可扩展性，并提供在更广泛的应用中充分利用SDD所需的新功能。该项目的第二部分涉及一个更新的发现：概率SDD（PSDD）。这种编译语言旨在以一种非常原则和有效的方式在命题理论上归纳概率分布。我们的目标是将PSDDs开发成一个成熟的工具，并提供相应的公共软件包，用于在大量逻辑约束下学习易于处理的概率模型，并将概率图形模型编译成PSDDs，以实现更可扩展的概率推理。

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.