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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Probabilistic facts can be ground or non-ground. [11] proves that finitely many groundings of non-ground probabilistic facts are sufficient to compute probabilities. That is why we restrict our discussion to programs with ground probabilistic facts.
- 2.
When it is clear from the context we use the term ProbLog to refer to either the language or the system. Otherwise we state it explicitly.
- 3.
More details for the algorithm and the full complexity analysis can be found at: https://lirias.kuleuven.be/bitstream/123456789/500398/5/appendix.pdf.
References
Aloul, F.A., Markov, I.L., Sakallah, K.A.: Faster SAT and smaller BDDs via common function structure. In: ICCAD, pp. 443–448 (2001)
Bacchus, F., Winter, J.: Effective preprocessing with hyper-resolution and equality reduction. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 341–355. Springer, Heidelberg (2004)
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35(8), 677–691 (1986)
Chen, W., Swift, T., Warren, D.S.: Efficient top-down computation of queries under the well-founded semantics. JLP 24(3), 161–199 (1995)
Darwiche, A.: A compiler for deterministic, decomposable negation normal form. In: AAAI/IAAI, pp. 627–634. AAAI Press/MIT Press (2002)
Darwiche, A., Marquis, P.: A knowledge compilation map. JAIR 17, 229–264 (2002)
De Raedt, L., Kimmig, A., Toivonen, H.: ProbLog: a probabilistic Prolog and its application in link discovery. In: IJCAI, pp. 2468–2473. AAAI Press (2007)
Fierens, D., Van den Broeck, G., Renkens, J., Shterionov, D.S., Gutmann, B., Thon, I., Janssens, G., De Raedt, L.: Inference and learning in probabilistic logic programs using weighted boolean formulas. TPLP 15(3), 358–401 (2015)
Hintsanen, P.: The most reliable subgraph problem. In: Kok, J.N., Koronacki, J., Lopez de Mantaras, R., Matwin, S., Mladenič, D., Skowron, A. (eds.) PKDD 2007. LNCS (LNAI), vol. 4702, pp. 471–478. Springer, Heidelberg (2007)
Kimmig, A., Costa, F.: Link and node prediction in metabolic networks with probabilistic logic. In: Berthold, M.R. (ed.) Bisociative Knowledge Discovery. LNCS, vol. 7250, pp. 407–426. Springer, Heidelberg (2012)
Kimmig, A., Demoen, B., De Raedt, L., Santos Costa, V., Rocha, R.: On the implementation of the probabilistic logic programming language ProbLog. TPLP 11, 235–262 (2011)
Kowalski, R.A.: Predicate logic as programming language. In: IFIP Congress, pp. 569–574 (1974)
Lagniez, J., Marquis, P.: Preprocessing for propositional model counting. In: AAAI, pp. 2688–2694 (2014)
Mantadelis, T., Demoen, B., Janssens, G.: A simplified fast interface for the use of CUDD for binary decision diagrams (2008). http://people.cs.kuleuven.be/theofrastos.mantadelis/tools/simplecudd.html
Mantadelis, T., Janssens, G.: Dedicated tabling for a probabilistic setting. In: ICLP (Technical Communications), LIPIcs, vol. 7, pp. 124–133 (2010)
Mantadelis, T., Janssens, G.: Variable compression in ProbLog. In: Fermüller, C.G., Voronkov, A. (eds.) LPAR-17. LNCS, vol. 6397, pp. 504–518. Springer, Heidelberg (2010)
Mantadelis, T., Janssens, G.: Nesting probabilistic inference (2011). CoRR, abs/1112.3785
Mantadelis, T., Rocha, R., Kimmig, A., Janssens, G.: Preprocessing boolean formulae for BDDs in a probabilistic context. In: Janhunen, T., Niemelä, I. (eds.) JELIA 2010. LNCS, vol. 6341, pp. 260–272. Springer, Heidelberg (2010)
Moldovan, B., van Otterlo, M., Moreno, P., Santos-Victor, J., De Raedt, L.: Statistical relational learning of object affordances for robotic manipulation. In: ILP, p. 6 (2012)
Mostow, J.: Towards automated development of specialized algorithms for design synthesis: knowledge compilation as an approach to computer-aided design. Res. Eng. Des. 1(3–4), 167–186 (1990)
Namioka, Y., Tanaka, T.: Knowledge compilation for interactive design of sequence control programs. In: IEA/AIE, pp. 363–368 (1996)
Narodytska, N., Walsh, T.: Constraint and variable ordering heuristics for compiling configuration problems. In: IJCAI, pp. 149–154 (2007)
Panda, S., Somenzi, F.: Who are the variables in your neighborhood. In: ICCAD, pp. 74–77 (1995)
Rauzy, A., Châtelet, E., Dutuit, Y., Bérenguer, C.: A practical comparison of methods to assess sum-of-products. Reliab. Eng. Syst. Saf. 79(1), 33–42 (2003)
Shterionov, D., Mantadelis, T., Janssens, G.: Pattern-based compaction for ProbLog inference. In: ICLP (Technical Communications), pp. 1–4 (2013)
Shterionov, D., Janssens, G.: Implementation and performance of probabilistic inference pipelines. In: Pontelli, E., Son, T.C. (eds.) PADL 2015. LNCS, vol. 9131, pp. 90–104. Springer, Heidelberg (2015)
Valiant, L.G.: Why is Boolean complexity theory difficult? In: London Mathematical Society Symposium on Boolean Function Complexity, pp. 84–94 (1992)
Vlasselaer, J., Meert, W.: Statistical relational learning for prognostics. In: Belgian-Dutch Conference on Machine Learning, pp. 45–50 (2012)
Acknowledgments
We want to thank the anonymous reviewers for their comments and help to improve our paper. Theofrastos Mantadelis is funded by the Portuguese Foundation for Science and Technology (FCT) within the projects SIBILA NORTE-07-0124-FEDER-000059 and UID/EEA/50014/2013. Dimitar Shterionov is funded by KU Leuven within the project GOA 13/010.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Mantadelis, T., Shterionov, D., Janssens, G. (2015). Compacting Boolean Formulae for Inference in Probabilistic Logic Programming. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2015. Lecture Notes in Computer Science(), vol 9345. Springer, Cham. https://doi.org/10.1007/978-3-319-23264-5_35
Download citation
DOI: https://doi.org/10.1007/978-3-319-23264-5_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23263-8
Online ISBN: 978-3-319-23264-5
eBook Packages: Computer ScienceComputer Science (R0)