Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-18T02:30:18.452Z Has data issue: false hasContentIssue false
  • English
  • Français

Constraint-Based Inference in Probabilistic Logic Programs

Published online by Cambridge University Press:  10 August 2018

ARUN NAMPALLY ,
TIMOTHY ZHANG  and
C. R. RAMAKRISHNAN
ARUN NAMPALLY
Affiliation:
Department of Computer Science, Stony Brook University, Stony Brook, NY 11794 (e-mail: [email protected], [email protected], [email protected])
TIMOTHY ZHANG
Affiliation:
Department of Computer Science, Stony Brook University, Stony Brook, NY 11794 (e-mail: [email protected], [email protected], [email protected])
C. R. RAMAKRISHNAN
Affiliation:
Department of Computer Science, Stony Brook University, Stony Brook, NY 11794 (e-mail: [email protected], [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Probabilistic Logic Programs (PLPs) generalize traditional logic programs and allow the encoding of models combining logical structure and uncertainty. In PLP, inference is performed by summarizing the possible worlds which entail the query in a suitable data structure, and using this data structure to compute the answer probability. Systems such as ProbLog, PITA, etc., use propositional data structures like explanation graphs, BDDs, SDDs, etc., to represent the possible worlds. While this approach saves inference time due to substructure sharing, there are a number of problems where a more compact data structure is possible. We propose a data structure called Ordered Symbolic Derivation Diagram (OSDD) which captures the possible worlds by means of constraint formulas. We describe a program transformation technique to construct OSDDs via query evaluation, and give procedures to perform exact and approximate inference over OSDDs. Our approach has two key properties. Firstly, the exact inference procedure is a generalization of traditional inference, and results in speedup over the latter in certain settings. Secondly, the approximate technique is a generalization of likelihood weighting in Bayesian Networks, and allows us to perform sampling-based inference with lower rejection rate and variance. We evaluate the effectiveness of the proposed techniques through experiments on several problems.

Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 18 , Special Issue 3-4: 34th International Conference on Logic Programming , July 2018 , pp. 638 - 655
Copyright
Copyright © Cambridge University Press 2018 

References

Bellodi, E., Lamma, E., Riguzzi, F., Costa, V. S., and Zese, R. 2014. Lifted variable elimination for probabilistic logic programming. Theory and Practice of Logic Programming 14, 4–5, 681–695.Google Scholar
Braz, R. D. S., Amir, E., and Roth, D. 2005. Lifted first-order probabilistic inference. In 19th International Joint Conference on Artificial intelligence. 1319–1325.Google Scholar
Bryant, R. E. 1992. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys 24, 3, 293–318.Google Scholar
Costa, V. S., Page, D., Qazi, M., and Cussens, J. 2002. CLP(BN): Constraint logic programming for probabilistic knowledge. In 19th Conference on Uncertainty in Artificial Intelligence. 517–524.Google Scholar
Cussens, J. 2000. Stochastic logic programs: Sampling, inference and applications. In 16th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann, 115–122.Google Scholar
den Broeck, G. V., Taghipour, N., Meert, W., Davis, J., and Raedt, L. D. 2011. Lifted probabilistic inference by first-order knowledge compilation. In 20th International Joint Conference on Artificial Intelligence. 2178–2185.Google Scholar
Fierens, D., den Broeck, G. V., Bruynooghe, M., and Raedt, L. D. 2012. Constraints for probabilistic logic programming. In NIPS Probabilistic Programming Workshop. 1–4.Google Scholar
Fung, R. M. and Chang, K.-C. 1990. Weighing and integrating evidence for stochastic simulation in bayesian networks. In 5th Conference on Uncertainty in Artificial Intelligence. 209–220.Google Scholar
Geman, S. and Geman, D. 1984. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence 6, 6, 721–741.Google Scholar
Hastings, W. K. 1970. Monte carlo sampling methods using markov chains and their applications. Biometrika 57, 1, 97–109.Google Scholar
Holzbaur, C. 1992. Metastructures versus attributed variables in the context of extensible unification. In 4th International Symposium on Programming Language Implementation and Logic Programming. 260–268.Google Scholar
Kam, T., Villa, T., Brayton, R., and Sangiovanni-Vincentelli, A. 1998. Multivalued decision diagrams: Theory and applications. Multiple-Valued Logic 4, 9–62.Google Scholar
Kazemi, S. M., Kimmig, A., den Broeck, G. V., and Poole, D. 2016. New liftable classes for first-order probabilistic inference. In 30th International Conference on Neural Information Processing Systems. 3125–3133.Google Scholar
Kersting, K., Raedt, L. D., and Raiko, T. 2006. Logical hidden Markov models. Journal of Artificial Intelligence Research 25, 2006.Google Scholar
Mansinghka, V., Roy, D., Jonas, E., and Tenenbaum, J. 2009. Exact and approximate sampling by systematic stochastic search. In 12th International Conference on Artificial Intelligence and Statistics. 400–407.Google Scholar
Michels, S., Hommersom, A., Lucas, P. J., Velikova, M., and Koopman, P. W. 2013. Inference for a new probabilistic constraint logic. In 23rd International Joint Conference on Artificial Intelligence. 2540–2546.Google Scholar
Milch, B., Zettlemoyer, L. S., Kersting, K., Haimes, M., and Kaelbling, L. P. 2008. Lifted probabilistic inference with counting formulas. In 23rd AAAI Conference on Artificial Intelligence. 1062–1068.Google Scholar
Moldovan, B., Thon, I., Davis, J., and Raedt, L. D. 2013. MCMC estimation of conditional probabilities in probabilistic programming languages. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty. 436–448.Google Scholar
Nampally, A. and Ramakrishnan, C. R. 2015. Constraint-based inference in probabilistic logic programs. In 2nd International Workshop on Probabilistic Logic Programming. 46–56.Google Scholar
Nampally, A. and Ramakrishnan, C. R. 2016. Inference in probabilistic logic programs using lifted explanations. In Technical Communications of 32nd International Conference on Logic Programming. 15:1–15:15.Google Scholar
Nitti, D., Laet, T. D., and Raedt, L. D. 2016. Probabilistic logic programming for hybrid relational domains. Machine Learning 103, 3, 407–449.Google Scholar
Poole, D. 2003. First-order probabilistic inference. In 18th International Joint Conference on Artificial Intelligence. 985–991.Google Scholar
Raedt, L. D., Kimmig, A., and Toivonen, H. 2007. ProbLog: a probabilistic Prolog and its application in link discovery. In 20th International Joint Conference on Artifical Intelligence. 2462–2467.Google Scholar
Riguzzi, F. 2011. MCINTYRE: A Monte Carlo algorithm for probabilistic logic programming. In 26th Italian Conference on Computational Logic (CILC2011). 25–39.Google Scholar
Riguzzi, F. and Swift, T. 2011. The PITA system: Tabling and answer subsumption for reasoning under uncertainty. Theory and Practice of Logic Programming 11, 4–5, 433–449.Google Scholar
Sarna-Starosta, B. and Ramakrishnan, C. R. 2007. Compiling constraint handling rules for efficient tabled evaluation. In Practical Aspects of Declarative Languages (PADL). 170–184.Google Scholar
Sato, T. and Kameya, Y. 1997. PRISM: a language for symbolic-statistical modeling. In 15th International Joint Conference on Artificial Intelligence. 1330–1339.Google Scholar
Sato, T. and Kameya, Y. 2001. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research 15, 391–454.Google Scholar
Shachter, R. D. and Peot, M. A. 1990. Simulation approaches to general probabilistic inference on belief networks. In 5th Conference on Uncertainty in Artificial Intelligence. 221–234.Google Scholar
Swift, T. and Warren, D. S. 2010. Tabling with answer subsumption: Implementation, applications and performance. In Logics in Artificial Intelligence: 12th European Conference (JELIA). 300–312.Google Scholar
Tamaki, H. and Sato, T. 1986. OLD resolution with tabulation. In 3rd International Conference on Logic Programming. Springer, 84–98.Google Scholar
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 1

Download Nampally supplementary material(File)
File 1.5 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 2

Download Nampally supplementary material(File)
File 40.2 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 3

Download Nampally supplementary material(File)
File 1.9 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 4

Download Nampally supplementary material(File)
File 2.4 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 5

Download Nampally supplementary material(File)
File 4.2 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 6

Download Nampally supplementary material(File)
File 22.7 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 7

Download Nampally supplementary material(File)
File 11.4 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 8

Download Nampally supplementary material(File)
File 11.4 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 9

Download Nampally supplementary material(File)
File 10 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 10

Download Nampally supplementary material(File)
File 36.9 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 11

Download Nampally supplementary material(File)
File 31.6 KB
Supplementary material: File

Nampally supplementary material

Nampally supplementary material 12

Download Nampally supplementary material(File)
File 4.3 KB
Supplementary material: PDF

Nampally supplementary material

Nampally supplementary material 13

Download Nampally supplementary material(PDF)
PDF 82.1 KB