Document Open Access Logo

Inference in Probabilistic Logic Programs Using Lifted Explanations

Authors Arun Nampally, C. R. Ramakrishnan

PDF
Thumbnail PDF

File

OASIcs.ICLP.2016.15.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Arun Nampally
C. R. Ramakrishnan

Cite As Get BibTex

Arun Nampally and C. R. Ramakrishnan. Inference in Probabilistic Logic Programs Using Lifted Explanations. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016). Open Access Series in Informatics (OASIcs), Volume 52, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/OASIcs.ICLP.2016.15

Abstract

In this paper, we consider the problem of lifted inference in the context of Prism-like probabilistic logic programming languages. Traditional inference in such languages involves the construction of an explanation graph for the query that treats each instance of a random variable separately. For many programs and queries, we observe that explanations can be summarized into substantially more compact structures introduced in this paper, called "lifted explanation graph". In contrast to existing lifted inference techniques, our method for constructing lifted explanations naturally generalizes existing methods for constructing explanation graphs. To compute probability of query answers, we solve recurrences generated from the lifted graphs. We show examples where the use of our technique reduces the asymptotic complexity of inference.

Subject Classification

Keywords
  • Probabilistic logic programs
  • Probabilistic inference
  • Lifted inference
  • Symbolic evaluation
  • Constraints

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Elena Bellodi, Evelina Lamma, Fabrizio Riguzzi, Vítor Santos Costa, and Riccardo Zese. Lifted variable elimination for probabilistic logic programming. TPLP, 14(4-5):681-695, 2014. Google Scholar
  2. Rodrigo De Salvo Braz, Eyal Amir, and Dan Roth. Lifted first-order probabilistic inference. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, pages 1319-1325, 2005. Google Scholar
  3. Randal E Bryant. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys (CSUR), 24(3):293-318, 1992. Google Scholar
  4. Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. ProbLog: A probabilistic prolog and its application in link discovery. In IJCAI, pages 2462-2467, 2007. Google Scholar
  5. Anton Dries, Angelika Kimmig, Wannes Meert, Joris Renkens, Guy Van den Broeck, Jonas Vlasselaer, and Luc De Raedt. Problog2: Probabilistic logic programming. In ECML PKDD, pages 312-315, 2015. Google Scholar
  6. Kim G. Larsen, Fredrik Larsson, Paul Pettersson, and Wang Yi. Efficient verification of real-time systems: Compact data structure and state-space reduction. In IEEE RTSS’97, pages 14-24, 1997. Google Scholar
  7. Brian Milch, Luke S Zettlemoyer, Kristian Kersting, Michael Haimes, and Leslie Pack Kaelbling. Lifted probabilistic inference with counting formulas. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, pages 1062-1068, 2008. Google Scholar
  8. Antoine Miné. The octagon abstract domain. Higher-Order and Symbolic Computation, 19(1):31-100, 2006. Google Scholar
  9. Arun Nampally and C. R. Ramakrishnan. Inference in probabilistic logic programs using lifted explanations. Technical report, Computer Science Department, Stony Brook University, 2016. URL: http://www.cs.stonybrook.edu/~px/Papers/NR:lifted_tr_2016/.
  10. David Poole. First-order probabilistic inference. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, volume 3, pages 985-991, 2003. Google Scholar
  11. Fabrizio Riguzzi and Terrance Swift. The PITA system: Tabling and answer subsumption for reasoning under uncertainty. TPLP, 11(4-5):433-449, 2011. Google Scholar
  12. Taisuke Sato and Yoshitaka Kameya. PRISM: a language for symbolic-statistical modeling. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, volume 97, pages 1330-1339, 1997. Google Scholar
  13. Taisuke Sato and Yoshitaka Kameya. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research, pages 391-454, 2001. Google Scholar
  14. Daniel R Sheldon and Thomas G. Dietterich. Collective graphical models. In Advances in Neural Information Processing Systems 24, pages 1161-1169, 2011. URL: http://papers.nips.cc/paper/4220-collective-graphical-models.pdf.
  15. Arvind Srinivasan, Timothy Kam, Sharad Malik, and Robert K. Brayton. Algorithms for discrete function manipulation. In International Conference on Computer-Aided Design, ICCAD, pages 92-95, 1990. URL: http://dx.doi.org/10.1109/ICCAD.1990.129849.
  16. Nima Taghipour, Daan Fierens, Jesse Davis, and Hendrik Blockeel. Lifted variable elimination: Decoupling the operators from the constraint language. J. Artif. Intell. Res. (JAIR), 47:393-439, 2013. Google Scholar
  17. Guy Van den Broeck, Nima Taghipour, Wannes Meert, Jesse Davis, and Luc De Raedt. Lifted probabilistic inference by first-order knowledge compilation. In IJCAI, pages 2178-2185, 2011. Google Scholar
  18. Sergio Yovine. Model-checking timed automata. In Embedded Systems, number 1494 in LNCS, pages 114-152, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact