Abstract
We present \(\mathcal {ALC}^\mathsf {ME}\), a probabilistic variant of the Description Logic \(\mathcal {ALC}\) that allows for representing and processing conditional statements of the form “if E holds, then F follows with probability p” under the principle of maximum entropy. Probabilities are understood as degrees of belief and formally interpreted by the aggregating semantics. We prove that both checking consistency and drawing inferences based on approximations of the maximum entropy distribution is possible in \(\mathcal {ALC}^\mathsf {ME}\) in time polynomial in the domain size. A major problem for probabilistic reasoning from such conditional knowledge bases is to count models and individuals. To achieve our complexity results, we develop sophisticated counting strategies on interpretations aggregated with respect to the so-called conditional impacts of types, which refine their conditional structure.
This work was supported by the German Research Foundation (DFG) within the Research Unit FOR 1513 “Hybrid Reasoning for Intelligent Systems”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge (2003)
Baader, F., Ecke, A.: Extending the description logic ALC with more expressive cardinality constraints on concepts. In: Proceedings of the 3rd Global Conference on Artificial Intelligence (GCAI), pp. 6–19. EasyChair (2017)
Baader, F., Horrocks, I., Sattler, U.: Description logics. In: van Harmelen, F., Lifschitz, V., Porter, B. (eds.) Handbook of Knowledge Representation. Elsevier, Amsterdam (2007)
Baader, F., Koopmann, P., Turhan, A.-Y.: Using ontologies to query probabilistic numerical data. In: Dixon, C., Finger, M. (eds.) FroCoS 2017. LNCS (LNAI), vol. 10483, pp. 77–94. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66167-4_5
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Van den Broeck, G., Taghipour, N., Meert, W., Davis, J., De Raedt, L.: Lifted probabilistic inference by first-order knowledge compilation. In: Proceedings of the 22th International Joint Conference on Artificial Intelligence (IJCAI), pp. 2178–2185. AAAI Press (2011)
Halpern, J.Y.: An analysis of first-order logics of probability. Artif. Intell. 46(3), 311–350 (1990)
Kern-Isberner, G.: Conditionals in Nonmonotonic Reasoning and Belief Revision. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44600-1
Kern-Isberner, G., Thimm, M.: Novel semantical approaches to relational probabilistic conditionals. In: Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning (KR), pp. 382–392. AAAI Press (2010)
Lutz, C., Schröder, L.: Probabilistic description logics for subjective uncertainty. In: Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 393–403. AAAI Press (2010)
Paris, J.B.: Common sense and maximum entropy. Synthese 117(1), 75–93 (1999)
Paris, J.B.: The Uncertain Reasoner’s Companion: A Mathematical Perspective. Cambridge University Press, Cambridge (2006)
Peñaloza, R., Potyka, N.: Towards statistical reasoning in description logics over finite domains. In: Moral, S., Pivert, O., Sánchez, D., Marín, N. (eds.) SUM 2017. LNCS (LNAI), vol. 10564, pp. 280–294. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67582-4_20
Pratt, V.R.: Models of program logics. In: Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 115–122. IEEE Computer Society (1979)
Rudolph, S., Krötzsch, M., Hitzler, P.: Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog. Logical Methods Comput. Sci. 8(1), 38 (2012)
Thimm, M., Kern-Isberner, G.: On probabilistic inference in relational conditional logics. Logic J. IGPL 20(5), 872–908 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Wilhelm, M., Kern-Isberner, G., Ecke, A., Baader, F. (2019). Counting Strategies for the Probabilistic Description Logic \(\mathcal {ALC}^\mathsf {ME}\) Under the Principle of Maximum Entropy. In: Calimeri, F., Leone, N., Manna, M. (eds) Logics in Artificial Intelligence. JELIA 2019. Lecture Notes in Computer Science(), vol 11468. Springer, Cham. https://doi.org/10.1007/978-3-030-19570-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-030-19570-0_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-19569-4
Online ISBN: 978-3-030-19570-0
eBook Packages: Computer ScienceComputer Science (R0)