权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

III: Small: Scalable Probabilistic Inference for Large Knowledge Bases

III：小：大型知识库的可扩展概率推理

基本信息

批准号：
1614738
负责人：
Dan Suciu
金额：
$ 50万
依托单位：
University of Washington
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-07-15 至 2020-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1614738&HistoricalAwards=false
关键词：
III Small Scalable Probabilistic Inference

项目摘要

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.

今天，大型知识库是从网页、期刊文章、新闻故事等大型文本语料库中自动构建的。建设分两个主要阶段进行。首先，在文本语料库上计算几个数据库查询，以提取候选数据项；结果数据称为因子图，可以认为是一个非常大、噪声、不确定、冗余和不一致的数据库。其次，在因子图上执行复杂的概率推理，以产生一个大型的概率知识库。这两个阶段的计算成本都很高，但到目前为止，只有第一个阶段受益于数据库查询处理技术的进步。该项目为概率推理任务开发了新的数据库处理技术。这些新技术有理论上的保证，要么是对概率推理的运行时间的绝对保证，要么是以运行时间和概率推理的精度之间的权衡的形式。该项目追求的主要技术被称为提升的概率推理，它包括在查询的结构上归纳地计算SQL查询的概率的算法，而不必首先使查询基础来计算大因子图。取消推理是非常有效的，但仅对某些查询可能。该项目有四个推力。首先，它将抽样与提升推理相结合，为任何查询提供高效的近似概率推理；该算法可以推入数据库引擎，因此可以立即从现代并行查询处理器中提供的所有优化中受益。其次，该项目研究了对称数据库上的查询求值的复杂性，这是一个具有很高实用价值的特例，因为它很容易扩展到任意大的域。在第三个推力中，该项目将Lift推理技术扩展到带有否定的查询，将概率推理与解析相结合；这是必要的，因为知识库中的软约束几乎总是有否定的。最后，项目开发了一个系统原型和基准测试。