Abstract
Several different semantics have been proposed for conditional knowledge bases \(\mathcal {R}\) containing qualitative conditionals of the form “If A, then usually B”, leading to different nonmonotonic inference relations induced by \(\mathcal {R}\). For the notion of c-representations which are a subclass of all ranking functions accepting \(\mathcal {R}\), a skeptical inference relation, called c-inference and taking all c-representations of \(\mathcal {R}\) into account, has been suggested. In this article, we develop a 3-phase compilation scheme for both knowledge bases and skeptical queries to constraint satisfaction problems. In addition to skeptical c-inference, we show how also credulous and weakly skeptical c-inference can be modelled as constraint satisfaction problems, and that the compilation scheme can be extended to such queries. We further extend the compilation approach to knowledge bases evolving over time. The compiled form of \(\mathcal {R}\) is reused for incrementally compiling extensions, contractions, and updates of \(\mathcal {R}\). For each compilation step, we prove its soundness and completeness, and demonstrate significant efficiency benefits when querying the compiled version of \(\mathcal {R}\). These findings are also supported by experiments with the software system InfOCF that employs the proposed compilation scheme.
Similar content being viewed by others
References
Adams, E.: Probability and the logic of conditionals. In: Hintikka, J., Suppes, P. (eds.) Aspects of Inductive Logic, pp 265–316, North-Holland (1966)
Adams, E.: The Logic of Conditionals. D. Reidel, Dordrecht (1975)
Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, United Kingdom (1998)
Beierle, C., Eichhorn, C., Kern-Isberner, G.: Skeptical inference based on c-representations and its characterization as a constraint satisfaction problem. In: FoIKS-2016, Volume 9616 of LNCS, pp 65–82. Springer (2016)
Beierle, C., Eichhorn, C., Kern-Isberner, G., Kutsch, S.: Skeptical, weakly skeptical, and credulous inference based on preferred ranking functions. In: Kaminka, G.A., Fox, M., Bouquet, P., Hüllermeier, E., Dignum, V., Dignum, F., van Harmelen, F. (eds.) Proceedings 22nd European Conference on Artificial Intelligence, ECAI-2016, Volume 285 of Frontiers in Artificial Intelligence and Applications, pp 1149–1157. IOS Press (2016)
Beierle, C., Eichhorn, C., Kern-Isberner, G., Kutsch, S.: Properties of skeptical c-inference for conditional knowledge bases and its realization as a constraint satisfaction problem. Ann. Math. Artif. Intell. 83(3-4), 247–275 (2018)
Beierle, C., Eichhorn, C., Kutsch, S.: A practical comparison of qualitative inferences with preferred ranking models. KI – Künstliche Intelligenz 31(1), 41–52 (2017)
Beierle, C., Kern-Isberner, G.: Semantical investigations into nonmonotonic and probabilistic logics. Ann. Math. Artif. Intell. 65(2-3), 123–158 (2012)
Beierle, C., Kern-Isberner, G., Sauerwald, K., Bock, T., Ragni, M.: Towards a general framework for kinds of forgetting in common-sense belief management. KI – Künstliche Intelligenz 33(1), 57–68 (2019)
Beierle, C., Kern-Isberner, G., Södler, K.: A declarative approach for computing ordinal conditional functions using constraint logic programming. In: Tompits, H., Abreu, S., Oetsch, J., Pührer, J., Seipel, D., Umeda, M., Wolf, A. (eds.) Applications of Declarative Programming and Knowledge Management, Volume 7773 of LNAI, pp 175–192. Springer (2013)
Beierle, C., Kutsch, S.: Comparison of inference relations defined over different sets of ranking functions. In: Antonucci, A., Cholvy, L., Papini, O. (eds.) S.mbolic and Quantitative Approaches to Reasoning with Uncertainty - 14th European Conference, ECSQARU 2017, Lugano, Switzerland, July 10–14, 2017, Proceedings, Volume 10369 of Lecture Notes in Computer Science, pp 225–235 (2017)
Beierle, C., Kutsch, S.: Computation and comparison of nonmonotonic skeptical inference relations induced by sets of ranking models for the realization of intelligent agents. Appl. Intell. 49(1), 28–43 (2019)
Beierle, C., Kutsch, S., Sauerwald, K.: Compilation of conditional knowledge bases for computing c-inference relations. In: Ferrarotti, F., Woltran, S. (eds.) Foundations of Information and Knowledge Systems - 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14-18, 2018, Proceedings, Volume 10833 of LNCS, pp 34–54. Springer (2018)
Ben Amor, N., Dubois, D., Gouider, H., Prade, H.: Preference modeling with possibilistic networks and symbolic weights: A theoretical study. In: Kaminka, G.A., Fox, M., Bouquet, P., Hüllermeier, E., Dignum, V., Dignum, F., van Harmelen, F. (eds.) ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016), Volume 285 of Frontiers in Artificial Intelligence and Applications, pp 1203–1211. IOS Press (2016)
Benferhat, S., Dubois, D., Prade, H.: Possibilistic and standard probabilistic semantics of conditional knowledge bases. J. Log. Comput. 9(6), 873–895 (1999)
Benferhat, S., Dubois, D., Prade, H.: Possibilistic and standard probabilistic semantics of conditional knowledge bases. J. Logic Comput. 9(6), 873–895 (1999)
Byrne, R.M.: Suppressing valid inferences with conditionals. Cognition 31, 61–83 (1989)
Carlsson, M., Ottosson, G., Carlson, B.: An open-ended finite domain constraint solver. In: PLILP’97, Volume 1292 of LNCS, pp 191–206. Springer (1997)
Cayrol, C., Dubois, D., Touazi, F.: Symbolic possibilistic logic: Completeness and inference methods. J. Log. Comput. 28(1), 219–244 (2018)
Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. 17, 229–264 (2002)
Darwiche, A., Marquis, P.: Compiling propositional weighted bases. Artif. Intell. 157(1–2), 81–113 (2004)
de Finetti, B.: La prévision, ses lois logiques et ses sources subjectives. Ann. Inst. H. Poincaré 7(1), 1–68 (1937). English translation in Studies in Subjective Probability, ed. H. Kyburg and H.E. Smokler, 1974, 93–158. New York: Wiley & Sons
Dubois, D., Prade, H.: Conditional objects as nonmonotonic consequence relationships. Special Issue on Conditional Event Algebra, IEEE Transactions on Systems Man and Cybernetics 24(12), 1724–1740 (1994)
Dubois, D., Prade, H.: Possibility theory and its applications: Where do we stand? In: Kacprzyk, J., Pedrycz, W. (eds.) Springer Handbook of Computational Intelligence, pp 31–60. Springer, Berlin (2015)
Dupin de Saint-Cyr, F., Lang, J., Schiex, T.: Penalty logic and its link with dempster-shafer theory. In: de Mántaras, R.L., Poole, D. (eds.) UAI ’94: Proceedings of the Tenth Annual Conference on Uncertainty in Artificial Intelligence, Seattle, Washington, USA, July 29-31, 1994, pp 204–211. Morgan Kaufmann (1994)
Eichhorn, C., Kern-Isberner, G., Ragni, M.: Rational inference patterns based on conditional logic. In: McIlraith, S., Weinberger, K. (eds.) Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), pp 1827–1834. AAAI Press (2018)
Eiter, T., Lukasiewicz, T.: Complexity results for structure-based causality. Artif Intell. 142(1), 53–89 (2002)
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.) Scalable Uncertainty Management - 8th International Conference, SUM 2014, Oxford, UK, September 15-17, 2014. Proceedings, Volume 8720 of LNAI, pp 162–175. Springer (2014)
Gärdenfors, P.: Knowledge in Flux: Modeling the Dynamics of Epistemic States. MIT Press, Cambridge (1988)
Goldszmidt, M., Pearl, J.: On the Relation Between Rational Closure and System-Z. UCLA Computer Science Department (1991)
Goldszmidt, M., Pearl, J.: Qualitative probabilities for default reasoning, belief revision, and causal modeling. Artif. Intell. 84(1–2), 57–112 (1996)
Isberner, M., Kern-Isberner, G.: Plausible reasoning and plausibility monitoring in language comprehension. Int. J Approx. Reas. 88, 53–71 (2017)
Kern-Isberner, G.: Conditionals in Nonmonotonic Reasoning and Belief Revision, Volume 2087 of LNAI. Springer (2001)
Kern-Isberner, G.: A thorough axiomatization of a principle of conditional preservation in belief revision. Ann. of Math. and Artif. Intell. 40(1-2), 127–164 (2004)
Kern-Isberner, G., Eichhorn, C.: Structural inference from conditional knowledge bases. Stud. Logica. 102(4), 751–769 (2014)
Knuth, D.E., Bendix, P.B.: Simple word problems in universal algebra. In: Leech, J. (ed.) Computational Problems in Abstract Algebra, pp 263–297. Pergamon Press (1970)
Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell. 44, 167–207 (1990)
Lehmann, D.J., Magidor, M.: What does a conditional knowledge base entail? Artif. Intell. 55(1), 1–60 (1992)
Leopold, T., Kern-Isberner, G., Peters, G.: Belief revision with reinforcement learning for interactive object recognition. In: Proceedings 18th European Conference on Artificial Intelligence, ECAI’08 (2008)
Lewis, D.: Counterfactuals. Harvard University Press, Cambridge (1973)
Lukasiewicz, T.: Weak nonmonotonic probabilistic logics. Artif. Intell. 168(1-2), 119–161 (2005)
Makinson, D.: General patterns in nonmonotonic reasoning. In: Gabbay, D.M., Hogger, C.J., Robinson, J.A. (eds.) Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3, pp 35–110. Oxford University Press (1994)
Marquis, P.: Consequence finding algorithms. In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, pp 41–145. Springer (2000)
Minock, M., Kraus, H.: Z-log: Applying system-Z. In: Proceedings of the 8th European Conference on Logics in AI, JELIA 2002, Volume 2424 of LNAI, pp 545–548. Springer (2002)
Nute, D.: Topics in Conditional Logic. D. Reidel Publishing Company, Dordrecht (1980)
Paris, J.: The Uncertain Reasoner’S Companion – A Mathematical Perspective. Cambridge University Press (1994)
Pearl, J.: System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In: Parikh, R. (ed.) Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning About Knowledge (TARK1990), pp 121–135. Morgan Kaufmann Publishers Inc., San Francisco (1990)
Pinkas, G.: Reasoning, nonmonotonicity and learning in connectionist networks that capture propositional knowledge. Artif. Intell. 77(2), 203–247 (1995)
Sperner, E.: Ein Satz über Untermengen einer endlichen Menge. Math. Z. 27 (1), 544–548 (1928)
Spohn, W.: Ordinal conditional functions: A dynamic theory of epistemic states. In: Harper, W., Skyrms, B. (eds.) Causation in Decision, Belief Change, and Statistics, II, pp 105–134. Kluwer Academic Publishers (1988)
Spohn, W.: The Laws of Belief: Ranking Theory and Its Philosophical Applications. Oxford University Press, Oxford (2012)
Wason, P.C.: Reasoning about a rule. Q. J. Exper. Psychol. 20(3), 273–281 (1968)
Wilhelm, M., Kern-Isberner, G., Finthammer, M., Beierle, C.: A generalized iterative scaling algorithm for maximum entropy model computations respecting probabilistic independencies. In: Ferrarotti, F., Woltran, S. (eds.) Foundations of Information and Knowledge Systems - 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14-18, 2018, Proceedings, Volume 10833 of LNCS, pp 379–399. Springer (2018)
Acknowledgements
This work was supported by DFG Grant BE 1700/9-1 given to Christoph Beierle as part of the priority program “Intentional Forgetting in Organizations” (SPP 1921). Kai Sauerwald is supported by this Grant. We thank the anonymous reviewers for their valuable hints and comments that helped us to improve the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Beierle, C., Kutsch, S. & Sauerwald, K. Compilation of static and evolving conditional knowledge bases for computing induced nonmonotonic inference relations. Ann Math Artif Intell 87, 5–41 (2019). https://doi.org/10.1007/s10472-019-09653-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-019-09653-7
Keywords
- Conditional
- Conditional knowledge base
- c-representation
- Skeptical c-inference
- Weakly skeptical c-inference
- Credulous c-inference
- Constraint satisfaction problem
- Knowledge base compilation
- Knowledge base modification
- Incremental compilation