Abstract
While the complexity of the optimization problem to be solved when computing the Maximum Entropy distribution \(P^{*}_{\mathcal {R}}\) of a knowledge base \(\mathcal {R}\) grows dramatically when moving to the relational case, it has been shown that having the weighted conditional impacts (WCI) of \(\mathcal {R}\) available, \(P^{*}_{\mathcal {R}}\) can be computed much faster. Computing WCI in a straightforward manner readily gets infeasible due to the size of the set \(\varOmega \) of possible worlds. In this paper, we propose a new approach for computing the WCI without considering the worlds in \(\varOmega \) at all. We introduce the notion of sat-pairs and show how to determine the set \(\mathcal {CSP}\) of all possible combinations of sat-pairs by employing combinatorial means. Using \(\mathcal {CSP}\) instead of \(\varOmega \) for computing the WCI is a significant performance gain since \(\mathcal {CSP}\) is typically much smaller than \(\varOmega \). For a start, we focus on simple knowledge bases consisting of a single conditional. First evaluation results of an implemented algorithm illustrate the benefits of our approach.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Brualdi, R.A.: Introductory Combinatorics (5th Edition). Pearson (2009)
Darroch, J.N., Ratcliff, D.: Generalized iterative scaling for log-linear models. Annals of Mathematical Statistics 43(5), 1470–1480 (1972)
de Salvo Braz, R., Amir, E., Roth, D.: Lifted first-order probabilistic inference. In: IJCAI-05, pp. 1319–1325. Professional Book Center (2005)
Finthammer, M., Beierle, C.: Using equivalences of worlds for aggregation semantics of relational conditionals. In: Glimm, B., Krüger, A. (eds.) KI 2012. LNCS, vol. 7526, pp. 49–60. Springer, Heidelberg (2012)
Finthammer, M., Beierle, C.: A two-level approach to maximum entropy model computation for relational probabilistic logic based on weighted conditional impacts. In: Straccia, U., Calì, A. (eds.) SUM 2014. LNCS, vol. 8720, pp. 162–175. Springer, Heidelberg (2014)
Fischer, V., Schramm, M.: Tabl - a tool for efficient compilation of probabilistic constraints. Technical Report TUM-19636, Technische Universität München (1996)
Getoor, L., Taskar, B. (eds.): Introduction to Statistical Relational Learning. MIT Press (2007)
Halpern, J.: Reasoning About Uncertainty. MIT Press (2005)
Kazemi, S.M., Buchman, D., Kersting, K., Natarajan, S., Poole, D.: Relational logistic regression. In: Proc. 14th International Conference on Principles of Knowledge Representation and Reasoning (KR-2014) (2014)
Kern-Isberner, G.: Conditionals in Nonmonotonic Reasoning and Belief Revision. LNCS, vol. 2087. Springer, Heidelberg (2001)
Kern-Isberner, G., Beierle, C., Finthammer, M., Thimm, M.: Comparing and evaluating approaches to probabilistic reasoning: Theory, implementation, and applications. Transactions on Large-Scale Data- and Knowledge-Centered Systems 6, 31–75 (2012)
Kern-Isberner, G., Lukasiewicz, T.: Combining probabilistic logic programming with the power of maximum entropy. Artif. Intell. 157(1–2), 139–202 (2004)
Kern-Isberner, G., Thimm, M.: Novel semantical approaches to relational probabilistic conditionals. In: Proc. KR-2010, pp. 382–391. AAAI Press, Menlo Park, CA (2010)
Kern-Isberner, G., Thimm, M.: A ranking semantics for first-order conditionals. In: ECAI-2012, pp. 456–461. IOS Press (2012)
Lukasiewicz, T.: Probabilistic logic programming with conditional constraints. ACM Trans. Comput. Logic 2(3), 289–339 (2001)
Milch, B., Zettlemoyer, L., Kersting, K., Haimes, M., Kaelbling, L.P.: Lifted probabilistic inference with counting formulas. In: AAAI-2008, pp. 1062–1068. AAAI Press (2008)
Nilsson, N.: Probabilistic logic. Artificial Intelligence 28, 71–87 (1986)
Paris, J.: The uncertain reasoner’s companion - A mathematical perspective. University Press, Cambridge (1994)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo, Ca (1988)
Poole, D.: First-order probabilistic inference. In: Gottlob, G., Walsh, T. (ed.), Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), pp. 985–991. Morgan Kaufmann (2003)
Potyka, N., Beierle, C., Kern-Isberner, G.: A concept for the evolution of relational probabilistic belief states and the computation of their changes under optimum entropy semantics. Journal of Applied Logic (2015). (to appear)
Richardson, M., Domingos, P.: Markov logic networks. Machine Learning 62(1–2), 107–136 (2006)
Shore, J., Johnson, R.: Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy. IEEE Transactions on Information Theory, IT-26:26–37 (1980)
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
Finthammer, M., Beierle, C. (2015). Towards a More Efficient Computation of Weighted Conditional Impacts for Relational Probabilistic Knowledge Bases Under Maximum Entropy Semantics. In: Hölldobler, S., , Peñaloza, R., Rudolph, S. (eds) KI 2015: Advances in Artificial Intelligence. KI 2015. Lecture Notes in Computer Science(), vol 9324. Springer, Cham. https://doi.org/10.1007/978-3-319-24489-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-24489-1_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-24488-4
Online ISBN: 978-3-319-24489-1
eBook Packages: Computer ScienceComputer Science (R0)