III: Small: Scalable Probabilistic Inference for Large Knowledge Bases

如今，大型知识库是从大型文本语料库（如网页、期刊文章、新闻故事）中自动构建的。 工程分两个主要阶段进行。 首先，在文本语料库上计算几个数据库查询，以提取候选数据项;所得到的数据称为因子图，可以认为是一个非常大的、嘈杂的、不确定的、冗余的和不一致的数据库。其次，对因子图进行复杂的概率推理，以产生一个大型的概率知识库。 这两个阶段都是计算昂贵的，但只有第一阶段受益于数据库查询处理技术的进步。 这个项目为概率推理任务开发了新的数据库处理技术。 这些新技术都有理论上的保证，或者是对概率推理的运行时间的绝对保证，或者是在运行时间和概率推理的精度之间进行权衡。该项目所追求的主要技术被称为提升概率推理，它包括根据查询的结构归纳计算SQL查询的概率的算法，而不必首先将查询作为基础来计算大因子图。 提升推理非常有效，但仅适用于某些查询。 该项目有四个重点。 首先，它将采样与提升推理相结合，为任何查询提供有效的近似概率推理;该算法可以在数据库引擎中推出，因此可以立即受益于现代并行查询处理器中的所有优化。 其次，该项目研究了对称数据库上的查询评估的复杂性，这是一个具有高度实际重要性的特殊情况，因为它很容易扩展到任意大的域。 在第三个推力中，该项目通过将概率推理与分辨率相结合，将提升推理技术扩展到具有否定的查询;这是必要的，因为知识库中的软约束几乎总是具有否定。 最后，本项目开发了系统原型和基准测试。

Large Knowledge Bases are constructed today automatically from large corpora of text, like Web pages, journal articles, news stories. The construction proceeds in two major stages. First, several database queries are computed on the corpora of text, to extract candidate data items; the resulting data, called a factor graph, can be thought of as a very large, noisy, uncertain, redundant, and inconsistent database. Second, a complex probabilistic inference is performed on the factor graph to produce a large, probabilistic knowledge base. Both stages are computationally expensive, but only the first stage has benefited so far from advances in database query processing techniques. This project develops new database processing techniques for the probabilistic inference task. These new techniques have theoretical guarantees, either in the form of absolute guarantees on the runtime of the probabilistic inference, or in the form of a trade-off between the run time and the precision of the probabilistic inference.The main technique pursued by the project is called lifted probabilistic inference, and consists of algorithms that compute the probability of a SQL query inductively on the structure of the query, without having to first ground the query to compute the large factor graph. Lifted inference is very efficient, but possible only for some queries. The project has four thrusts. First, it combines sampling with lifted inference for efficient approximate probabilistic inference for any query; this algorithms can pushed in the database engine, and can therefore benefit immediately from all optimizations available today in modern, parallel query processors. Second, the project studies the complexity of query evaluation on symmetric databases, a special case of high practical importance, since it scales easily to arbitrarily large domains. In the third thrust, the project extends lifted inference techniques to queries with negations by combining probabilistic inference with resolution; this is necessary because soft constraints in knowledge bases almost always have negations. Finally, the project develops a system prototype and benchmarks.