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.