Knowledge Compilation Approaches to Probabilistic Answer Set Programming

• Grant number: 25/17392-6
• Support Opportunities: Scholarships in Brazil - Master
• Start date: October 01, 2025
• End date: July 31, 2027
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Denis Deratani Mauá
• Grantee: Dayana Isabel Agudo Guiracocha
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 22/02937-9 - Neural inductive logic programming, AP.PNGP.PI

Abstract

Probabilistic Logic Programming combines the ability of logic programming for expressing certain knowledge with the ability to capture uncertainty of probability theory. Importantly, probabilistic logic programs allow programs to be learned from data by gradient descent.There are current two approaches to implementing probabilistic logic programs.One, taken by ProbLog, is to limit expressivity to stratified programs. This simplifies the semantics and subsequent computations but prevents the modeling of non-deterministic computations and rich additional constructs such as aggregators and constraints. Stratified programs facilitate knowledge compilation, a process that obtains a Boolean circuit representation of the program semantics, which is then used to produce inferences and perform parameter learning. The other approach, taken by NeurASP, is to allow the full expressivity of Answer Set Programming. Due to the increased complexity, this approach is currently only implemented as an enumerative scheme that for each probabilistic choice calls an Answer Set Programming solver to resolve the logical part. This limits its uses to programs with few probabilistic choices.This MSc research will investigate knowledge compilation approaches for Probabilistic Answer Set Programming. This including several substeps, from logic program to Boolean formula to Boolean circuit to a parameterized Arithmetic Circuit that can finally obtain probabilistic inferences and perform parameter learning. The developed implementation will be evaluated in challenging applications such as question answering and planning.