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.