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

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

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.