Efficient rule-based reasoning and rules discovery from big data in many-valued settings

Thesis

Many critical applications, such as healthcare and security, demand robust decision-making capable of combining expert knowledge with the power of data-driven solutions. However, traditional logic systems often struggle with the inherent uncertainty and multifaceted nature of information in these domains. This thesis addresses this challenge by exploring the integration of symbolic and sub-symbolic reasoning methodologies.

While conventional logic operates with binary truth values (true/false), real-world data is often paired with degrees of truth or uncertainty. This work introduces MV-Datalog and MV-Datalog+-, novel extensions of, respectively, the classic and existential Datalog, specifically designed for reasoning with many-valued data. We introduce the concept of minimal fuzzy models in which each fact assumes the lowest possible truth assignments. This semantic naturally extends the typical minimal model semantics usually employed in logic programming. We prove the existence and efficient computability of unique minimal fuzzy models for MV-Datalog via a linear programming approach. For MV-Datalog+-, we introduce the practice-oriented notion of preferred fuzzy models for efficiently solving data entailment tasks in those settings requiring the use of existential variables. We demonstrate the effectiveness of MV-Datalog by tackling a link detection problem on large-scale, many-valued data.

Moving beyond specific semantics, the thesis also presents a novel optimization technique for reasoning within the Datalog+-Piece-Wise Linear and Warded fragment. We prove that programs in this fragment can be efficiently rewritten into a linear normal form, where each rule's body contains at most one intensional atom. We provide an efficient linearization algorithm and extend the theoretical results to allow reusing the linearization algorithm to maintain its beneficial properties in many-valued settings. We explain and show through experiments on synthetic scenarios how the properties of the linearized programs can be used to improve space and time efficiency during CQAns.

This thesis further introduces a patented framework designed to streamline the generation and curation of logical rules by automating the discovery, assessment, and application of association rules within both crisp and many-valued settings. The framework encompasses a suite of methodologies for data preparation, rule mining, evaluation and autonomous application. In addition, the system facilitates the incorporation of expert human reviews and allows for fine-tuning through an extensive array of input parameters. Notably, the mined rules can be used to refine and expand the initial dataset, enhancing the framework’s effectiveness. The practicality and effectiveness of this system are demonstrated through its deployment in a real-world industrial scenario.

Authors: Sferrazza, S

• DOI: 10.5287/ora-mn5a2yv58
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: machine learning; logic programming; uncertainty in AI; Datalog+-; Lukasiewicz logic; uncertainty; fuzzy logic programming; Datalog; ontological reasoning; artificial intelligence; logic transformations; fuzzy logic