×

zbMATH — the first resource for mathematics

A concept for the evolution of relational probabilistic belief states and the computation of their changes under optimum entropy semantics. (English) Zbl 1401.68326
Summary: Coping with uncertain knowledge and changing beliefs is essential for reasoning in dynamic environments. We generalize an approach to adjust probabilistic belief states by use of the relative entropy in a propositional setting to relational languages, leading to a concept for the evolution of relational probabilistic belief states. As a second contribution of this paper, we present a method to compute the corresponding belief state changes by considering a dual problem and present first application and experimental results. The computed belief state usually factorizes and we explain how the factorization can be exploited to store the belief state more compactly and to simplify its computation by exploiting equivalences of worlds. Finally, we present results on the computational complexity of determining equivalence classes.

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
03B42 Logics of knowledge and belief (including belief change)
03B48 Probability and inductive logic
68T30 Knowledge representation
Software:
L-BFGS; L-BFGS-B; LBFGS-B
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alchourrón, C.; Gärdenfors, P.; Makinson, D., On the logic of theory change: partial meet contraction and revision functions, J. Symb. Log., 50, 510-530, (1985) · Zbl 0578.03011
[2] Beierle, C.; Kern-Isberner, G., A conceptual agent model based on a uniform approach to various belief operations, (KI-2009, Lecture Notes in Artificial Intelligence, vol. 5803, (2009), Springer), 273-280
[3] Csiszar, I., I-divergence geometry of probability distributions and minimization problems, Ann. Probab., 3, 146-158, (1975) · Zbl 0318.60013
[4] Darwiche, A.; Pearl, J., On the logic of iterated belief revision, Artif. Intell., 89, 1-29, (1997) · Zbl 1018.03012
[5] Delgrande, J. P.; Jin, Y., Parallel belief revision: revising by sets of formulas, Artif. Intell., 176, 2223-2245, (2012) · Zbl 1243.03018
[6] Dubois, D.; Prade, H., Belief change and possibility theory, (Gärdenfors, P., Belief Revision, (1992), Cambridge University Press), 142-182
[7] Finthammer, M.; Beierle, C., Using equivalences of worlds for aggregation semantics of relational conditionals, (KI 2012, Lecture Notes in Artificial Intelligence, vol. 7526, (2012), Springer), 49-60
[8] Finthammer, M.; Beierle, C., Instantiation restrictions for relational probabilistic conditionals, (Hüllermeier, E.; Link, S.; Fober, T.; Seeger, B., Proceedings of 6th International Conference on Scalable Uncertainty Management, Lecture Notes in Artificial Intelligence, vol. 7520, (2012), Springer), 598-605
[9] Finthammer, M.; Beierle, C.; Berger, B.; Kern-Isberner, G., Probabilistic reasoning at optimum entropy with the \scmecore system, (Lane, H. C.; Guesgen, H. W., Proc. FLAIRS-2009, (2009), AAAI Press Menlo Park, CA), 535-540
[10] Fischer, V.; Schramm, M., Tabl - a tool for efficient compilation of probabilistic constraints, (1996), Technische Universität München, Technical Report TUM-19636
[11] Fisseler, J., First-order probabilistic conditional logic and maximum entropy, Log. J. IGPL, 20, 796-830, (2012) · Zbl 1257.68133
[12] Fletcher, R., Practical methods of optimization, (1987), Wiley-Interscience New York, NY, USA · Zbl 0905.65002
[13] Gärdenfors, P.; Rott, H., Belief revision, (Gabbay, D.; Hogger, C.; Robinson, J., Handbook of Logic in Artificial Intelligence and Logic Programming, (1994), Oxford University Press), 35-132
[14] Grove, A.; Halpern, J.; Koller, D., Random worlds and maximum entropy, J. Artif. Intell. Res., 2, 33-88, (1994) · Zbl 0900.68398
[15] Halpern, J. Y., An analysis of first-order logics of probability, Artif. Intell., 46, 311-350, (1990) · Zbl 0723.03007
[16] Halpern, J., Reasoning about uncertainty, (2005), MIT Press
[17] Jaeger, M.; Van den Broeck, G., Liftability of probabilistic inference: upper and lower bounds, (Proceedings of the 2nd International Workshop on Statistical Relational AI, Statistical Relational AI Workshop, Catalina Island, USA, 18 August 2012, (2012))
[18] Katsuno, H.; Mendelzon, A., Propositional knowledge base revision and minimal change, Artif. Intell., 52, 263-294, (1991) · Zbl 0792.68182
[19] Kern-Isberner, G., Conditionals in nonmonotonic reasoning and belief revision, Lecture Notes in Artificial Intelligence, vol. 2087, (2001), Springer · Zbl 0978.03014
[20] Kern-Isberner, G., Linking iterated belief change operations to nonmonotonic reasoning, (Proc. KR-2008, (2008), AAAI Press Menlo Park, CA), 166-176
[21] Kern-Isberner, G.; Lukasiewicz, T., Combining probabilistic logic programming with the power of maximum entropy, Artif. Intell., 157, 1-2, 139-202, (2004), Special Issue on Nonmonotonic Reasoning · Zbl 1085.68170
[22] Kern-Isberner, G.; Thimm, M., Novel semantical approaches to relational probabilistic conditionals, (Proc. KR-2010, (2010), AAAI Press Menlo Park, CA), 382-391
[23] Kersting, K., Lifted probabilistic inference, (Raedt, L. D.; Bessiere, C.; Dubois, D.; Doherty, P.; Frasconi, P.; Heintz, F.; Lucas, P., Proceedings of 20th European Conference on Artificial Intelligence (ECAI-2012), ECCAI, (2012), IOS Press Montpellier, France), Invited Talk at the Frontiers of AI Track
[24] Koller, D.; Friedman, N., Probabilistic graphical models: principles and techniques, (2009), MIT Press
[25] Loh, S.; Thimm, M.; Kern-Isberner, G., On the problem of grounding a relational probabilistic conditional knowledge base, (Proceedings of the 14th International Workshop on Non-monotonic Reasoning (NMR’10), Toronto, Canada, (2010))
[26] Lukasiewicz, T., Probabilistic deduction with conditional constraints over basic events, J. Artif. Intell. Res., 10, 380-391, (1999)
[27] Lukasiewicz, T., Probabilistic logic programming with conditional constraints, ACM Trans. Comput. Log., 2, 289-339, (2001) · Zbl 1171.68762
[28] Niepert, M.; den Broeck, G. V., Tractability through exchangeability: a new perspective on efficient probabilistic inference, (Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27-31, 2014, Québec City, Québec, Canada, (2014), AAAI Press), 2467-2475
[29] Nilsson, N. J., Probabilistic logic, Artif. Intell., 28, 71-88, (1986) · Zbl 0589.03007
[30] Papadimitriou, C. H., Computational complexity, (1994), Addison-Wesley · Zbl 0557.68033
[31] Paris, J., The uncertain Reasoner’s companion - A mathematical perspective, (1994), Cambridge University Press · Zbl 0838.68104
[32] Poole, D., First-order probabilistic inference, (Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI’03, (2003), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 985-991
[33] Potyka, N., Towards a general framework for maximum entropy reasoning, (Proc. FLAIRS-2012, (2012), AAAI Press Menlo Park, CA), 555-560
[34] Potyka, N.; Beierle, C.; Kern-Isberner, G., Changes of relational probabilistic belief states and their computation under optimum entropy semantics, (Timm, I. J.; Thimm, M., KI 2013 Advances in Artificial Intelligence - Proceedings of 36th Annual German Conference on AI, Koblenz, Germany, September 16-20, 2013, Lecture Notes in Computer Science, vol. 8077, (2013), Springer), 176-187
[35] Rott, H., Reapproaching Ramsey: conditionals and iterated belief change in the spirit of AGM, J. Philos. Log., 40, 155-191, (2011) · Zbl 1233.03015
[36] Spohn, W., Ordinal conditional functions: a dynamic theory of epistemic states, (Harper, W.; Skyrms, B., Causation in Decision, Belief Change, and Statistics, II, (1988), Kluwer Academic Publishers), 105-134
[37] Staab, S.; Studer, R., Handbook on ontologies, (2009), Springer · Zbl 1429.68001
[38] Thimm, M.; Kern-Isberner, G., On probabilistic inference in relational conditional logics, Log. J. IGPL, 20, 872-908, (2012), Special Issue on Relational Approaches to Knowledge Representation and Learning · Zbl 1280.68248
[39] Van Den Broeck, G.; Taghipour, N.; Meert, W.; Davis, J.; De Raedt, L., Lifted probabilistic inference by first-order knowledge compilation, (Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI’11, vol. 3, (2011), AAAI Press), 2178-2185
[40] Zhu, C.; Byrd, R. H.; Lu, P.; Nocedal, J., Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM Trans. Math. Softw., 23, 550-560, (1997) · Zbl 0912.65057
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.