Compacting boolean formulae for inference in probabilistic logic programming

Theofrastos Mantadelis*, Dimitar Shterionov, Gerda Janssens

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

Knowledge compilation converts Boolean formulae for which some inference tasks are computationally expensive into a representation where the same tasks are tractable. ProbLog is a state-of-the-art Probabilistic Logic Programming system that uses knowledge compilation to reduce the expensive probabilistic inference to an efficient weighted model counting. Motivated to improve ProbLog’s performance we present an approach that optimizes Boolean formulae in order to speed-up knowledge compilation. We identify 7 Boolean subformulae patterns that can be used to re-write Boolean formulae.We implemented an algorithm with polynomial complexity which detects and compacts 6 of these patterns. We employ our method in the inference pipeline of ProbLog and conduct extensive experiments. We show that our compaction method improves knowledge compilation and consecutively the overall inference performance. Furthermore, using compaction reduces the number of time-outs, allowing us to solve previously unsolvable problems.

Original languageEnglish
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Proceedings
EditorsMiroslaw Truszczynski, Francesco Calimeri, Giovambattista Ianni
PublisherSpringer Verlag
Pages425-438
Number of pages14
ISBN (Print)9783319232638
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event13th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2015 - Lexington, United States
Duration: 27 Sep 201530 Sep 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9345
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2015
CountryUnited States
CityLexington
Period27/09/1530/09/15

Fingerprint Dive into the research topics of 'Compacting boolean formulae for inference in probabilistic logic programming'. Together they form a unique fingerprint.

  • Cite this

    Mantadelis, T., Shterionov, D., & Janssens, G. (2015). Compacting boolean formulae for inference in probabilistic logic programming. In M. Truszczynski, F. Calimeri, & G. Ianni (Eds.), Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Proceedings (pp. 425-438). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9345). Springer Verlag. https://doi.org/10.1007/978-3-319-23264-5_35