Abduction is about finding extensions to a knowledge base that are suficient to imply a given entailment. Specifically, in the context of description logics (DPs), we consider an ontology of background knowledge, an axiom s.t. ̸|= (called the observation), and we want to compute a suitable set ℋ of axioms called hypothesis such that ∪ ℋ |= [1]. Abduction as a reasoning problem has a long history [2] and has several applications: for example, it can be used to explain missing entailments of an ontology [3, 4, 5], to repair incomplete knowledge bases [6], and to provide possible explanations for unexpected observations [7]. We consider the special case of TBox abduction in the lightweight description logic ℰℒ, where the observation is an ℰℒ concept inclusion 1 ⊑ 2 and the background knowledge is an ℰℒ TBox . To avoid useless answers, abduction problems usually come with further restrictions on the solution space and/or minimality criteria that help sort the chaf from the grain. We argue that existing minimality notions sufer from certain limitations, and introduce connection minimality as a new notion that overcomes the limitations of earlier notions. Furthermore, we developed and evaluated a method to compute connection-minimal solutions in practice. Our criterion follows Occam's razor by rejecting hypotheses that use concept inclusions unrelated to the problem at hand. To illustrate, consider the following TBox about relationships in academia: ∃employment.ResearchPosition ⊓ ∃qualification.Diploma ⊑ Researcher, ∃writes.ResearchPaper ⊑ Researcher, Doctor ⊑ ∃qualification.PhD, Professor ≡ Doctor ⊓ ∃employment.Chair, FundsProvider ⊑ ∃writes.GrantApplication }.
entailment include the following
ℋ1 = {PhD ⊑ Diploma, Chair ⊑ ResearchPosition} ℋ2 = {Doctor ⊑ FundsProvider, GrantApplication ⊑ ResearchPaper}.
We argue that ℋ1 is preferable over ℋ2, because ℋ2 is less linked to the observation. Indeed, for any two concepts 1 and 2 such that a entails 1 ⊑ ∃writes.2, a hypothesis {Doctor ⊑ 1, 2 ⊑ ResearchPaper} could be created (consider for instance that a additionally entails Poet ⊑ ∃writes.Poetry), since neither 1 nor 2 need to be connected to either Professor or Researcher. Our new minimality notion discards ℋ2, and favors ℋ1 as connection-minimal.
Intuitively, for an observation 1 ⊑ 2, connection minimality only accepts those hypotheses which ensure that every CI in the hypothesis is connected to both 1 and 2 in . The definition of connection minimality is based on the following ideas: 1 Hypotheses for the abduction problem have to create a connection between 1 and 2, in the form of a concept that satisfies ∪ ℋ |= 1 ⊑ , ⊑ 2. 2 To ensure that Occam’s razor is followed, we want this connection to be based on concepts 1 and 2 for which we already have |= 1 ⊑ 1, 2 ⊑ 2. 3 We additionally want to make sure that the connecting concepts are not more complex than necessary, and that ℋ only contains CIs that directly connect parts of 2 to parts of 1 by closely following their structure.
We call a connecting concept: A concept connects 1 to 2 in if and only if |= 1 ⊑ and |= ⊑ 2. Note that if |= 1 ⊑ 2 then both 1 and 2 are connecting concepts from 1 to 2, and if ̸|= 1 ⊑ 2, it means no concept connects them.
In the above example, we would use a |= 1 ⊑ 1 and a |= 2 ⊑ 2 where
1
2
=
=
∃qualification.PhD ⊓ ∃employment.Chair
∃qualification.Diploma ⊓ ∃employment.ResearchPosition ⊓ Researcher
from which we construct the hypothesis ℋ1 by linking the fillers of the existential restrictions.
In the full paper, we define the connection between 1 and 2 formally using a relaxed notion
of homomorphism between the description trees of 2 and 1. We show that this notion of
minimality is deeply connected with the generation of prime-implicates in first-order logic [
We implemented a prototype of our method consisting of two components: a Java component
that takes care of preprocessing, translation into first-order logic, and construction of the
hypotheses from prime implicates, and a first-order reasoning component that uses a modified
version of the theorem prover SPASS [
Acknowledgments: This work was supported by the Deutsche Forschungsgemeinschaft (DFG), Grant 389792660 within TRR 248.