BIGDATA: F: Open-World Foundations for Big Uncertain Data

由于需要从大量文本数据中学习，自然语言处理、信息提取、数据库和人工智能的努力正在共同建立大规模的知识库。这些系统不断地在网络上爬行，从文本中提取关系数据，并且已经用数百万个实体和数十亿个元组填充了它们的数据库。大规模概率知识库正在彻底改变我们访问数据的方式。现在，科学家们经常使用它们来建立出版物的知识库，执法部门经常使用它们从暗网中提取信息，而搜索引擎的常规用户也经常使用它们来发现他们的结果中增加了结构化的信息。这样的知识库本质上是概率性的：从原始文本到结构化数据，一系列统计机器学习技术将概率与数据库元组联系起来。这个项目重新审视了这些系统背后的语义，并提供了一个更充分的基础框架。特别是，概率数据库的封闭世界假设，即数据库中不存在的事实概率为零，显然与它们的日常使用相冲突，并阻碍了这一领域的进展。更具体地说，这个项目开发了一个基于开放世界假设的新的语义基础，即数据库中不存在的事实是可能的，但具有未知的概率。设计了在这种情况下查询应答的基本算法，包括精确算法和近似算法。此外，在深入的理论组成部分，该项目研究了数据和领域复杂性的基本问题，这些问题是关于大不确定数据的开放世界推理所特有的。最后，它开发了机器学习和数据挖掘中的概念验证应用程序，以及加强开放世界推理的额外知识表示层。开发的语义在某些元组概率不精确已知时提供了有意义的答案。开发的算法允许有效的查询回答，即使在对开放世界进行推理时，对于可处理的查询，数据库大小在时间上是线性的。这个项目在基本的语义层面上提供了一个科学的飞跃。它还为培养本科生和研究生在数据库、人工智能、理论和机器学习等学科方面提供了一个背景，并将把概率知识库整合到计算机科学课程中。

Driven by the need to learn from vast amounts of text data, efforts throughout natural language processing, information extraction, databases, and AI are coming together to build large-scale knowledge bases. These systems continuously crawl the web to extract relational data from text, and have already populated their databases with millions of entities and billions of tuples. Large-scale probabilistic knowledge bases are revolutionizing the way we access data. They are now routinely used by scientists to build knowledge bases of publications, by law enforcement to extract information from the dark web, and by regular search engine users who find their results augmented with structured information. Such knowledge bases are inherently probabilistic: to go from raw text to structured data, a sequence of statistical machine learning techniques associate probabilities with database tuples. This project revisits the semantics underlying such systems, and provide a more adequate foundational framework. In particular, the closed-world assumption of probabilistic databases, that facts not in the database have probability zero, clearly conflicts with their everyday use, and obstructs the progress in this area.More specifically, this project develops a new semantic foundation based on the open-world assumption, that facts not in the database are possible, but have unknown probability. It designs the basic algorithms for query answering in this setting, both exact and approximate. Moreover, in a deep theoretical component, this project studies fundamental questions of data and domain complexity that are unique to open-world reasoning about big uncertain data. Finally it develops proof-of-concept applications in machine learning and data mining, and additional knowledge-representation layers that strengthen open-world reasoning. The developed semantics provide meaningful answers when some tuple probabilities are not precisely known. The developed algorithms allow for efficient query answering, even when reasoning about the open world, in time linear in the database size for tractable queries. This project provides a scientific leap at the fundamental, semantic level. It also provides a context for training undergraduate and graduate students in subjects spanning databases, artificial intelligence, theory, and machine learning, and will target the integration of probabilistic knowledge bases into computer science curricula.