This paper introduces relaxed abduction, a novel non-standard reasoning task for description logics. Although abductive reasoning over description logic knowledge bases has been applied successfully to various information interpretation tasks, it typically fails to provide adequate (or even any) results when confronted with spurious information or incomplete models. Relaxed abduction addresses this aw by ignoring such pieces of information automatically based on a joint optimization of the sets of explained observations and required assumptions. We present a method to solve relaxed abduction over EL+ TBoxes based on the notion of multi-criterion shortest hyperpaths.
Abduction was introduced in the late 19th century by Charles Sanders Pierce
as an inference scheme aimed at deriving potential explanations for some
observation [
Due to its hypothetical nature, an abduction problem typically does not have a single solution but a collection of alternative answers A1; A2; : : : ; Ak among which optimal solutions are selected by means of a preference order . We denote Ai being not worse than Aj by Ai Aj , indi erence (Ai Aj ^ Aj abbreviated by Ai ' Aj , and strict preference (Ai Aj ^ Ai 6' Aj ) by Ai Then a (normal) preferential abduction problem can be de ned as follows: Ai ) is
A .
j De nition 1 (Preferential abduction problem PAP = (T ; A; O; A)). Given a set of axioms T called the theory, a set of abducible axioms A, a set O of axioms representing observations such that T 6j= O, and a (not necessarily total) order relation A P(A) P(A), determine all A-minimal sets A A such that T [ A is consistent and T [ A j= O.
Typical preference orders over sets include subset-minimality (Ai sAj $ Ai Aj ), minimum cardinality (Ai cAj $ jAi j jAj j), and weighting-based orders de ned by a function w that assigns numerical weights to subsets of A (Ai wAj $ w(Ai ) w(Aj )). The rst two orders prefer a set A over any of its supersets, this monotonicity property is formalized in Def. 2.
De nition 2 (Monotone and anti-monotone order). An order ( ) over sets is monotone (strictly monotone) for set inclusion if and only if S0 S implies S0 S (S0 S implies S0 S). Conversely, ( ) is anti-monotone (strictly anti-monotone) for set inclusion if and only if S0 S implies S0 S (S0 S implies S0 S).
Applications of abductive information interpretation using a formal domain
model include media interpretation [
This aw rests on the requirement that every single observation oi 2 O be entailed by an admissible solution. It severely restricts the practical applicability of logic-based abduction to real-world industrial applications where an evergrowing amount of sensor data almost inevitably generates pieces of information that the model cannot account for. We therefore extend logic-based abduction in Sect. 2 to handle such cases in a more exible yet formally sound way, and propose a method to solve such extended abduction problems expressed in the description logic E L+ in Sect. 3. Section 4 contrasts our proposal with relevant related work on logics and abduction, and we conclude in Sect. 5.
While for very simple models it is possible to identify and remove spurious information in a preprocessing step, this is not feasible for reasonably complex models since the (ir-)relevance of a piece of information depends on the interpretation and is thusly not known beforehand. We therefore propose a general approach based on the intuition that spurious and missing information are two complementary facets of information imperfection and should thus be treated similarly: In addition to assuming information as needed based on the set of abducibles A, relaxed abduction ignores observations from O during hypotheses generation if required. This intuition is formalized in the next de nition. De nition 3 (Relaxed abduction problem RAP = (T ; A; O; A; O)). Given a set of axioms T called the theory, a set of abducible axioms A, a set O of axioms representing observations such that T 6j= O, and two (not necessarily total) order relations A P(A) P(A) and O P(O) P(O), determine all -minimal tuples (A; O) 2 P(A) P(O) such that T [ A is consistent and T [ A j= O. The order is de ned based on A and O as follows: { (A; O) ' (A0; O0) $ A 'A A0 ^ O 'O O0 { (A; O) (A0; O0) $ (A A A0 ^ O O O0) _ (A A A0 ^ O O O0) { (A; O) (A0; O0) $ ((A; O) (A0; O0)) _ ((A; O) ' (A0; O0))
Intuitively, a good solution will have high expressive power regarding the observations while being as non-assumptive as possible, which suggests to chose A monotone and O anti-monotone for set inclusion, respectively. The following example uses one such combination to solve the problem presented in Ex. 1. Example 2 (Sensitivity to irrelevant data (cont.)). Using inclusion as order criterion over sets, we let A A A0 $ A A0 and O O O0 $ O O0. As intended, the resulting order gives rise to the minimal solution which explains all observations but the vibrations and only requires to assume the diagnosis, namely a uctuating power supply.
O Proposition 1 (Conservativeness). A A is a solution to the preferential abduction problem PAP = (T ; A; O; A) if and only if (A; O) is a solution to the relaxed abduction problem RAP = (T ; A; O; A; O) for an arbitrary order that is anti-monotone for set inclusion.
Proof. Assume A solves PAP. Then T [ A is consistent, T [ A j= O, and A is A-minimal. As O is anti-monotone for set inclusion O is naturally Ominimal; (A; O) is therefore -minimal and thus solves RAP.
Conversely if (A; O) solves RAP then T [A is consistent, T [A j= O, and (A; O) is -minimal. Assume A0 A A s. t. A0 A, T [ A0 is consistent, T [ A0 j= O. Then (A0; O) (A; O), contradicting -minimality of (A; O). tu
Conservativeness states that, under natural conditions, relaxed abduction is guaranteed to reproduce all (if any) solutions of the corresponding standard abduction problem. Since A and O will typically represent competing optimization objectives, it is convenient to treat relaxed abduction as a bi-criterion optimization problem. -minimal solutions then correspond to Pareto-optimal points in the space of all combinations (A; O) meeting the logical requirements of a solution (consistency and entailment) as shown next.
Proposition 2 (Pareto-optimality of RAP). Let RAP = (T ; A; O; A; O) be a relaxed abduction problem. (A ; O ) is a solution to RAP if and only if it is a Pareto-optimal element (subject to A and O) of the candidate space f(A; O) 2 P(A) P(O) j T [ A j= O ^ T [ A 6j= ?g.
Proof. If (A ; O ) solves RAP, then T [ A is consistent and T [ A j= O holds. (A ; O ) is thus an element of the explanation space (ES), furthermore (A ; O ) must be -minimal. Now assume (A ; O ) is not Pareto-optimal for ES, and let (A0; O0) 2 ES such that (w. l. o. g.) A0 A A and O0 O O . Then (A0; O0) (A ; O ), contradicting -minimality of (A ,O ). Thus, (A ; O ) is a Pareto-optimal element of the explanation space.
Analogously, let (A0; O0) be a Pareto-optimal element of ES. To show that the tuple is -minimal, let (A ; O ) be a solution to RAP such that (A ; O ) (A0; O0). Then w. l. o. g. A A0 and O O O0, contradicting Pareto-optimality of (A0; O0). Conclusively, (A0;AO0) must be -minimal and therefore solves RAP. tu
The next section presents an approach to solving relaxed abduction for E L+ that explicitly addresses the bi-criterial nature of the problem. 3
Solving Relaxed Abduction for E L+
The description logic E L+ is a member of the E L family of lightweight DLs for
which subsumption can be tested in PTime [
In contrast to other work such as [
A v > sets of DL axioms just like T . In our experience the axiom-oriented representation provides greater exibility and information reuse as well as being easier to understand for non-expert users; we furthermore conjecture without formal proof that the concept-based de nition is subsumed by the axiom-based one.3 Since the rules shown in Fig. 1 constitute a sound and complete proof system for E L+, any normalized axiom set can be represented equivalently as a hypergraph whose vertices are all axioms of type (NF1) and (NF3) over the concept and role names used in the axiom set (corresponding to all statements admissible as premise or conclusion in a derivation step). The hyperedges are induced by instantiations of the rules (CR1)-(CR6); for example an instantiation of (CR4) that derives C v F from C v 9r:D and D v E using the axiom 9r:E v F induces a hyperedge e = (T (e); h(e); w(e)) with T (e) = fC v 9r:D; D v Eg, h(e) = C v F , and w(e) = 9r:E v F .
This correspondence can be extended to relaxed abduction problems as
follows: Both T and A contain arbitrary E L+ normal form axioms that can justify
3 First observe that T j= A1 u u An v O as required in [
; bDeea rneiltaixoend a4bd(uIcntidouncperdobhleymp.eTrghreawpehigHhtRedAhPy)p.eLrgertaRphAHPR=AP(T=; A(V;;OE;) iAnd;ucOed) by RAP is de ned by V = f(A v B); (A v 9r:B) j A; B 2 NC>; r 2 NRg where V> = f(A; A); (A; >) j A 2 NC>g V denotes the set of terminal states, and E the set of all hyperedges e = (T (e); h(e); w(e)) s. t. there is an axiom ax 2 T [ A justifying the derivation of h(e) 2 V from T (e) V due to one of (CR1)-(CR6). The edge weight w(e) = (A; O) is de ned by A = (faxg if ax 2 A; , O = (fh(e)g if h(e) 2 O; .
otherwise otherwise
;
Note that the size of HRAP is bounded polynomially in jNCj and jNRj. Checking whether a concept inclusion D v E (C v 9r:D) is derivable corresponds to checking if in the graph there exists a hyperpath from V> to the vertex D v E (C v 9r:D). Intuitively, there is a hyperpath from X to t if there is a hyperedge connecting some set of nodes Y to t, and each yi 2 Y is reachable from X via a hyperpath; Def. 5 formalizes this intuitive picture.
VX ;t = ftg [ Syi 2T (e) VX ;yi , and E De nition 5 (Hyperpath). pX ;t = (VX ;t ; EX ;t ) is a hyperpath in H = (V; E) from X to t if and only if (i) t 2 X and pX ;t = (ftg; ;), or (ii) there is an edge e 2 E such that h(e) = t; T (e) = fy1; : : : ; yk g, pX ;yi are hyperpaths from X to yi , V EX ;t = feg [ Syi 2T (e) EX ;yi . 3.2
Hyperpath Search for Relaxed Abduction
This section presents an algorithm for solving a relaxed abduction problem RAP
by determining bi-criterion shortest hyperpaths. The graph algorithm extends
a label-correcting algorithm for nding bi-criterion shortest paths in graphs,
which is one of the most e cient algorithms known for this problem [
Algorithm 1: Label correcting construction of H RAP Data : RAP = (T ; A; O; A; O), a relaxed abduction problem over NC> and
NR.
Result : HRAP , the induced hypergraph.
// initialization 1 foreach r 2 NR do 2 R (r) ;; 3 foreach C 2 NC> do 4 S (C) f> : f(;; ;)g; C : f(;; ;)gg;
// propagation
5 repeat
6 changed false;
7 foreach ax 2 T [ A do
8 else if ax = 9r:A2 v B then // CR4
9 foreach A1 2 NC> s. t. S(A1) 3 A2 : LA1;A2 do
10 foreach A 2 NC> s. t. R(r) 3 (A; A1) : LA;r;A1 do
11 L ;;
12 if S(A) 3 B : LA;B then L LA;B;
13 L join(L, meet(LA1;A2 , LA;r;A1 , ax, A v B));
14 if L 6= L then
15 S(A) (S(A) n fB : LA;Bg) [ fB : L g;
16 changed true;
17 until changed = false;
Proposition 3 (Correctness). The set of all solutions to a relaxed
abduction problem RAP = (T ; A; O; A; O) is given by the -minimal closure of
MP(HRAP ) under component-wise union (A; O) ] (A0; O0) := (A [ A0; O [ O0).
Proof. Due to space limitations we can only present an outline of the proof here.
Following the argumentation in [
Input : L1, L2, two label sets; just, concl, two normal form axioms.
Output : The label set produced by the meet-operator . 1 result f(A1 [ A2; O1 [ O2) j (A1; O1) 2 L1; (A2; O2) 2 L2g; 2 if just 2 A then result f(A [ fjustg; O) j (A; O) 2 resultg; 3 if concl 2 O then result f(A; O [ fconclg) j (A; O) 2 resultg; 4 return result; Function join(L1, L2)
Input : L1, L2, two label sets.
Output : The label set produced by the join-operator . 1 result L1 [ L2; 2 result remove-dominated(result, 3 return result;
A,
O); V . This can be proven inductively based on the correctness of the operators > and , which can easily be established in a case-by-case analysis. The terminal closure of Sv2V label(v) under component-wise union is based on the intuition that, having proved two statements a and b, we can obviously prove a ^ b by joining the two proofs (corresponding to the operator). Graphically, this can be seen as adding a dedicated vertex > such that any other v 2 V is connected to > by a hyperedge (fvg; >; f;; ;g), and determining the label of this node that intuitively represents anything that can be derived at all. tu
Since the node labels may grow exponentially in the size of A and O for
general preference orders such as set inclusion, it is worthwhile investigating
the bene t of our method as compared to the following simple brute-force
approach: Iterating over all pairs (A; O) 2 P(A) P(O), collect all (A; O) such
that T [ A j= O holds and nally drop all -dominated tuples among them.
This approach obviously requires 2jAj+jOj entailment tests, each set passing this
test is consequently tested for -minimality. We argue that the our approach is
superior to the brute-force method due to three aspects:
1. In contrast to the uninformed search outlined above, the approach proposed
in this paper realizes an informed search as it does not generate all possible
(A; O)-pairs haphazardly but only those for which the property T [ A j= O
actually holds, without requiring any additional entailment tests. The net
e ect of this property depends on the model T as well as on A and O;
problems having only few solutions at all will obviously bene t most.
2. Dropping -dominated labels for O and A being (anti-)monotone for set
inclusion reduces the worst-case size of node labels from by at least a factor of
O(pjAj jOj). This can be justi ed as follows: Fixing a set A A, the sets
Oi O that constitute the (non-dominated) label entries (A ; Oi ) must form
an antichain w. r. t. set inclusion. The maximum size of such an antichain is
given by jOj according to Sperner's theorem [
A0(l) = A0(l 1) + 12 1) = 32 A(l 1) = ( 32 )l 1 ; given by A(n; l) A(l the expected label size is thus O(1:5jAj+jOj).
Other choices for A and O can lead to more substantial savings; since the preference orders are used as a pruning criterion during solution generation this may however turn the approach into an approximate one. For instance if the assumption and observation sets are not compared by set inclusion but by cardinality, the maximum label size is reduced to jAj jOj { dependent on the order of rule application the algorithm may however fail to nd the optimal solutions. In a more complex setting, assigning numerical weights to observations and abducibles allows to drop only solutions that are signi cantly worse than others, or to compute bounds on the maximum score a partial solution may still achieve, and use this value as a pruning criterion. 4 Fbonn2r cm !p14b n2bictn2 choldps4tn2hna2t =2mmp22n n .p m . Letting m := b n2 c, this yields the estimate 5 This recurrence can be understood as follows: Assume the vectors are arranged in a (n l)-matrix, sorted by the rst component. A randomly chosen vector v starts with 1 or 0 with probability 0:5 each. In the former case, v cannot be dominated by any vector starting with a 0, i. e. the "lower half" of the table is ruled out instantly, and its probability of being dominated by another vector starting with 1 is given by the expected number of maxima among the remaining dn=2e vectors divided by their number, taken together v is maximal with probability A(dn=2e; l 1)=dn=2e. If v starts with 0, we can similarly determine its probability of being maximal to be A(n; l 1)=n. Summing up these probabilities and and multiplying the result by the number n of original vectors yields the expected number of maxima given above.
While abductive reasoning naturally addresses the problem of missing observations, there are to the authors' best knowledge no other approaches providing a formally sound solution to logic-based abduction with incomplete models.
The idea of considering abduction as a multi-criteria optimization problem
is also central to [
O-minimal and the A-minimal solution in our approach, respectively.
However, intermediary Pareto-optimal combinations are not considered in their
approach which is furthermore limited to propositional Bayes nets. The algorithm
presented in [
[
We have introduced relaxed abduction, a novel non-standard reasoning task for description logics. Relaxed abduction extends logic-based abduction to a general and formally sound framework for interpreting spurious information w. r. t. incomplete models. We have presented an algorithm for relaxed abduction over E L+ knowledge bases based on the notion of Pareto-optimal hyperpaths in the derivation graph, and motivated its superiority to a straightforward enumeration approach despite the inherent exponential growth of node labels. The proposed algorithm is straightforwardly extensible to other DLs for which subsumption can be decided by completion such as E L++ which supports nominals and thus ABox abduction. The very general notion of relaxed abduction allows for several interesting specializations resulting from di erent choices for and : A O Approximate solutions can for example be generated very e ciently (i. e. with linear label size) if we use set cardinality as a dominance criterion. More elaborate schemes based on weights assigned to the axioms allow for early and even lossless pruning of suboptimal partial solutions while also reducing label sizes.