×

zbMATH — the first resource for mathematics

Negative probabilities in probabilistic logic programs. (English) Zbl 1404.68034
Summary: We consider probabilistic logic programs (PLPs) for non-extreme distributions. We show that in the relational case with fixed populations, PLPs cannot represent many non-extreme distributions, even using negations. We introduce negative rule probabilities in PLPs, and show they make the language strictly more expressive. In addition, they render negations unnecessary: negations in PLPs can be translated to rules with negative probabilities, thus avoiding the problem of logical inconsistency. Furthermore, this translation keeps the PLP size compact (assuming the number of negations per rule is small). This translation algorithm also allows algorithms for exact inference that do not support negations to be applicable to PLPs with negations.
The noise probabilities for non-exclusive rules are difficult to interpret and unintuitive to manipulate. To alleviate this we define “probability-strengths”, an alternative representation for probabilistic values, which results in an intuitive additive algebra for combining rules. For acyclic propositional PLPs we prove what constraints on the strengths allow for proper distributions on the non-noise variables and allow for all non-extreme distributions to be represented. We show how arbitrary CPDs can be converted into this form in a canonical way.

MSC:
68N17 Logic programming
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Software:
CP-logic; PRISM; ProbLog
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apt, K. R.; Bezem, M., Acyclic programs, New Gener. Comput., 9, 3-4, 335-363, (1991) · Zbl 0744.68034
[2] Buchman, D.; Schmidt, M. W.; Mohamed, S.; Poole, D.; de Freitas, N., On sparse, spectral and other parameterizations of binary probabilistic models, J. Mach. Learn. Res., 22, 173-181, (2012)
[3] De Raedt, L.; Kimmig, A.; Toivonen, H., Problog: a probabilistic prolog and its application in link discovery, (Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI-2007, (2007)), 2462-2467
[4] Dıez, F. J.; Galán, S. F., An efficient factorization for the noisy MAX, Int. J. Intell. Syst., 18, 2, 165-177, (2003) · Zbl 1028.68164
[5] Domingos, P.; Kok, S.; Lowd, D.; Poon, H.; Richardson, M.; Singla, P., Markov logic, (Raedt, L. D.; Frasconi, P.; Kersting, K.; Muggleton, S., Probabilistic Inductive Logic Programming, (2008), Springer New York), 92-117 · Zbl 1137.68531
[6] Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, (ICLP/SLP, vol. 88, (1988)), 1070-1080
[7] Jha, A.; Suciu, D., Probabilistic databases with markoviews, Proc. VLDB Endow., 5, 11, 1160-1171, (2012)
[8] Kisynski, J.; Poole, D., Lifted aggregation in directed first-order probabilistic models, (Proc. Twenty-first International Joint Conference on Artificial Intelligence, IJCAI-09, Pasadena, California, (2009)), 1922-1929
[9] Koller, D.; Friedman, N., Probabilistic graphical models: principles and techniques, (2009), MIT Press
[10] Kowalski, R., Logic for Problem Solving, revisited. BoD-Books on Demand, 2014.
[11] Lauritzen, S. L., Graphical models, (1996), Oxford University Press USA · Zbl 0907.62001
[12] Meert, W.; Vennekens, J., Inhibited effects in CP-logic, (European Workshop on Probabilistic Graphical Models, (2014), Springer), 350-365 · Zbl 1443.68180
[13] Poole, D., The independent choice logic for modelling multiple agents under uncertainty, Artif. Intell., 94, 7-56, (1997), special issue on economic principles of multi-agent systems · Zbl 0902.03017
[14] Poole, D., Abducing through negation as failure: stable models in the independent choice logic, J. Log. Program., 44, 1-3, 5-35, (2000) · Zbl 0957.68013
[15] Richardson, M.; Domingos, P., Markov logic networks, Mach. Learn., 62, 107-136, (2006)
[16] Sato, T.; Kameya, Y., PRISM: a symbolic-statistical modeling language, (Proceedings of the 15th International Joint Conference on Artificial Intelligence, IJCAI-97, (1997)), 1330-1335
[17] Sato, T.; Kameya, Y., New advances in logic-based probabilistic modeling by PRISM, (De Raedt, L.; Frasconi, P.; Kersting, K.; Muggleton, S., Probabilistic Inductive Logic Programming, LNCS, vol. 4911, (2008), Springer), 118-155 · Zbl 1137.68617
[18] Van den Broeck, G.; Meert, W.; Darwiche, A., Skolemization for weighted first-order model counting, (2013)
[19] Vennekens, J.; Denecker, M.; Bruynooghe, M., CP-logic: a language of causal probabilistic events and its relation to logic programming, TPLP, 9, 3, 245-308, (2009) · Zbl 1179.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.