Counting Strategies for the Probabilistic Description Logic ALC^ME Under the Principle of Maximum Entropy

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Contributors

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.

Details

Original languageEnglish
Title of host publicationLogics in Artificial Intelligence - 16th European Conference, JELIA 2019, Proceedings
EditorsFrancesco Calimeri, Nicola Leone, Marco Manna
PublisherSpringer, Berlin [u. a.]
Pages434-449
Number of pages16
ISBN (print)9783030195694
Publication statusPublished - 2019
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science, Volume 11468
ISSN0302-9743

Conference

Title16th European Conference on Logics in Artificial Intelligence
Abbreviated titleJELIA 2019
Conference number16
Duration7 - 11 May 2019
LocationUniversity of Calabria
CityRende
CountryItaly

External IDs

Scopus 85065981675
ORCID /0000-0002-4049-221X/work/142247947

Keywords

Keywords

  • Aggregating semantics, Domain-lifted inference, Principle of maximum entropy, Probabilistic description logics

Library keywords