Probabilistic reasoning and learning for answer set programming
File(s)
Author(s)
Tuckey, David
Type
Thesis
Abstract
Answer Set Programming (ASP) is a specific type of logic programming capable of solving complex combinatorial problems. ASP programs may accept multiple models, thus supporting two notions of entailment: brave and cautious. Therefore, the Distribution Semantics (DS) (underpinning Probabilistic Logic Programming (PLP)) is not directly applicable to Probabilistic Answer Set Programming (PASP). Among few proposed semantics, the Credal Semantics (CS) has regained attention. However, no solver has been proposed for inference and learning under the CS. This semantics has the property of allowing uncertainty on computed probabilities, stemming from the brave and cautious entailment in ASP.
This thesis provides four main contributions. We propose the Probabilistic Approximate SOlver for the Credal Semantics (PASOCS), the first solver for PASP under the CS. It leverages large computation clusters and showcases 10 folds speedups. We then introduce the CredalFOIL system, the first system for structure learning under the CS, capable of learning normal clauses. This system solves a new class of learning task: the notion of coverage of examples is defined based on their “lower” and “upper” probability. This, although appropriate for the CS and PASP, makes the system not easily applicable in real-world scenarios.
We therefore introduce, as third contribution of this thesis, a novel semantics called Incomplete Knowledge Semantics (IKS), which introduces a notion of optimism in order to support probabilistic inference in the presence of uncertainty. Our IKS allows the user to “control” the probabilities of queries as a function of a given level of optimism, selecting the probability distribution that best matches the user’s context. Finally, we propose a new learning task for the IKS, and present the exact learner Probabilistic Abductive Inductive Learning (PAIL). PAIL demonstrates the impact that the different levels of optimism have on the learning of optimal solutions.
This thesis provides four main contributions. We propose the Probabilistic Approximate SOlver for the Credal Semantics (PASOCS), the first solver for PASP under the CS. It leverages large computation clusters and showcases 10 folds speedups. We then introduce the CredalFOIL system, the first system for structure learning under the CS, capable of learning normal clauses. This system solves a new class of learning task: the notion of coverage of examples is defined based on their “lower” and “upper” probability. This, although appropriate for the CS and PASP, makes the system not easily applicable in real-world scenarios.
We therefore introduce, as third contribution of this thesis, a novel semantics called Incomplete Knowledge Semantics (IKS), which introduces a notion of optimism in order to support probabilistic inference in the presence of uncertainty. Our IKS allows the user to “control” the probabilities of queries as a function of a given level of optimism, selecting the probability distribution that best matches the user’s context. Finally, we propose a new learning task for the IKS, and present the exact learner Probabilistic Abductive Inductive Learning (PAIL). PAIL demonstrates the impact that the different levels of optimism have on the learning of optimal solutions.
Version
Open Access
Date Issued
2023-06
Date Awarded
2024-01
Copyright Statement
Creative Commons Attribution NonCommercial Licence
License URL
Advisor
Russo, Alessandra
Broda, Krysia
Publisher Department
Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)