ABox abduction is the reasoning problem to nd explanations for a DL knowledge base (KB) and an observation given as an ABox assertion which does not follow from the KB. The explanations themselves are sets of ABox assertions such that the observation follows from the KB once an explanation set is included in it. One widely employed method to compute the explanations is the Minimal Hitting Set algorithm (MHS). MHS is complete, but it is also NP-complete and widely recognized as ine cient. There are also approximative methods such as MergeXplain (MXP) which are fast, but incomplete. This work describes a hybrid method called MHS-MXP which adopts the divide and conquer heuristics of MXP and applies it on MHS with the aim to make it more e cient at least on a favourable class of inputs of the ABox abduction problem. First experimental implementation is also available.
Abduction was introduced by Peirce [
If one wishes to nd all explanations of an ABox abduction problem, the Reiter's MHS algorithm [10] is the classic method. MHS is complete. In a nutshell, it searches through the space of all possible explanations, starting from the smallest (in terms of cardinality) and continues towards the largest. The MHS algorithm (NP-complete) works on top of a DL solver (whose complexity depends on the particular DL). This approach is useful particularly in cases where there are smaller explanations. However in cases where there is (even a small number of) explanations of larger size this search strategy may be ine cient.
Alternative strategies were explored. Junker's QuickXplain (QXP) [
Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Concept Atomic concept complement intersection existential restriction nominal Axiom
Syntax A :C C u D 9R:C fag
Syntax concept inclusion (GCI) C v D role inclusion (RIA) R v S concept assertion role assertion negated role assertion
C(a) aI 2 CI R(a; b) (aI ; bI ) 2 RI :R(a; b) (aI ; bI ) 62 RI
Semantics AI
I n CI CI \ DI fx j 9y (x; y) 2 RI ^ y 2 CI g faI g Semantics CI RI
DI
SI employ divide and conquer strategy which allows to nd one (QXP) or multiple explanations (MXP) very e ciently. On the other hand, these methods are approximative, i.e., they are not complete.
We base this work on the key observation that when MXP is run repeatedly, with a slightly modi ed inputs, it divides the search space di erently and it may possibly return a di erent set of explanations than in the previous runs. We propose a combined algorithm, dubbed MHS-MXP, that iterates runs of MXP and it uses MHS to steer the search space exploration in such a way that completeness is retained. We also provide a preliminary experimental implementation.
Compared to pure MXP, this approach has the advantage that it is no longer approximative { it is complete. Such a hybrid algorithm may likely have an advantage when compared with MHS, at least on a certain class of inputs. Precise characterization of this class and further optimization of the algorithm is subject to our ongoing work. 2
For simplicity we will introduce ALCHO [
An interpretation is a pair I = ( I ; I ), where I 6= ; is a domain, and the interpretation function I maps each individual a 2 NI to aI 2 I , each atomic concept A 2 NC to AI I , each role R 2 NR to RI I I , and each complex concept according to the right-hand side of Table 1.
An interpretation I satis es an axiom (denoted I j= ) if the respective constraint in Table 1 is satis ed. It is a model of a KB K (denoted I j= K) if I j= for all 2 K. A KB K is consistent, if I j= K for some interpretation I. K entails an axiom (denoted K j= ) if I j= for each I j= K.
In ABox abduction [
assertions. An ABox abduction problem is a pair P = (K; O) such that K is a knowledge base in DL and O is an ABox assertion. An explanation of P (on Abd) is any nite set of ABox assertions E Abd such that K [ E j= O.
In this work we limit the explanations to atomic and negated atomic concept and role assertions; hence Abd fA(a); :A(a) j A 2 NC; a 2 NIg [ fR(a; b); :R(a; b) j R 2 NR; a; b 2 NIg. Note that we do not limit the observations in any way, apart from allowing only one (possibly complex) ABox assertion.
While De nition 1 establishes the basic reasoning frame of abduction, some
explanations may be unintuitive. According to Elsenbroich et al. [
De nition 2 (Minimality). Assume an ABox abduction problem P = (K; O). Given two explanations E and E 0 of P, we say that E is (syntactically) smaller than E 0 if E E 0.1 We further say that an explanation E of P is (syntactically) minimal if there is no other explanation E 0 of P that is smaller than E . 3
We now review rst the complete MHS algorithm and then the faster but approximative MXP algorithm. The hybrid approach that tries to combine \the best of both worlds" is then introduced in Section 4. 1 Note that before we compare two explanations E and E0 of P syntactically, we typically normalize the assertions w.r.t. (outermost) concept conjunction: as CuD(a) is equivalent to the pair of assertions C(a) and D(a), we replace the former form by the latter while possible.
Require: knowledge base K, observation O, set of abducibles Abd Ensure: set SE of all explanations of P = (K; O) of the class Abd 1: M a model M of K [ f:Og 2: if M = null then 3: return "nothing to explain" 4: end if 5: T (V = frg; E = ;; L = fr 7! Abd(M )g) 6: for each 2 L(r) create new -successor n of r 7: SE fg 8: while there is next node n in T w.r.t. BFS do 9: if n can be pruned then 10: prune n 11: else if there is a model M of K [ f:Og [ H(n) then 12: label n by L(n) Abd(M ) 13: else 14: SE SE [ fH(n)g 15: end if 16: for each 2 L(n) create new -succesor n of n 17: end while 18: return SE 3.1
Thanks to Reiter [10] we know that computing all minimal explanations of (K; O)
reduces to nding all minimal hitting sets of the set of models of K [f:Og
(modulo negation). To nd some explanation, we may simply collect in E assertions
that invalidate each such model. Then K [ E [ f:Og is inconsistent and hence
K [ E j= O. The inverse reduction is also easily found.2 Hence disregarding
the time needed to nd the models of K [ f:Og, nding all explanations is
NP-complete [
However we want to draw explanations only from the set of abducibles Abd, as given in De nition 1. It is easily observed, that to nd such explanations it su ces to exclude non-abducibles from the search. In addition, if some of the models contains no abducibles then there are no explanations: Observation 1. The minimal explanations of (K; O) on Abd directly corresponds to the minimal hitting sets of fAbd(M ) j M j= K [ f:Ogg where Abd(M ) = f 2 Abd j M 6j= g.
Observation 2. If Abd(M ) = ; for some M j= K [ f:Og, then (K; O) has no explanations on Abd. 2 For S = fS1; : : : ; Sng let K = fA1 t t Ak v Si j Si 2 S; Si = fA1; : : : ; Akgg [ fS1 u u Sn v Sg. Then the minimal explanations of (K; S(a)) exactly correspond to the to minimal hitting sets of S.
The MHS algorithm, also proposed by Reiter [10], works by constructing a HS-tree. As we are limited by abducibles, in our case a HS tree T = (V; E; L) is a labelled tree in which each node is labelled by Abd(M ) for some model M of K [ f:Og and whose edges are labelled by elements of the parent node's label. If a node n1 2 V has a successor n2 2 V such that L(hn1; n2i) = then n2 is a -successor of n1.
The HS-tree has the property that the node-label L(n) and the union H(n) of the edge-labels on the path from the root r to each node n are disjoint. For each node n such a label can be found as Abd(M ) of any model of K [ f:Og [ H(n) which can be obtained by one call to an external DL reasoner. If no such model M exists then H(n) corresponds to a hitting set. Note that if M exists but Abd(M ) = ;, then in accord with Observation 2 H(n) is not a hitting set.
In addition, pruning is applied during the HS-tree construction in order to
eliminate non-minimal hitting sets. The most obvious case is when a node n
already corresponds to a hitting set H(n) and there is another node n0 with
H(n) H(n0). Any such n0 can be pruned. Also if H(n) = H(n0), even if not
yet a hitting set, one of the nodes is redundant and it can be pruned. Once
completed, a pruned HS-tree (i.e., one on which all pruning conditions were
applied) contains all minimal hitting sets [10]. In addition we also prune nodes
which correspond to undesired explanations [
The resulting algorithm is given in Algorithm 1. This algorithm is sound and
complete [
Theorem 3. The MHS algorithm is sound and complete (i.e., it returns the set SE of all minimal desired explanations of K and O on Abd.)
The fact that MHS explores the search space using breadth- rst search (BFS)
allows to limit the search for explanations by maximum size. The algorithm is
still complete w.r.t. any given target size [
Both QXP [
The essence of QXP is captured in the GetConflict function, which cleverly decomposes C by splitting it into smaller and smaller subsets in such a way that \on the way back" it is always able to reconstruct one minimal con ict, if it only exists. The auxiliary function isConsistent(K) encapsulates calls to an external reasoner; it returns true if K is consistent and false otherwise.
However, QXP only nds one con ict. Its extension MXP, captured in the FindConflicts function, nds as many con icts as possible that can be reconstructed from a one way in which C can be split. During the reconstruction, MXP relies on GetConflict to recover some of the con icts that would be lost due to splitting, which also ensures that it also keeps the important property that if at least one con ict exists, at least one is also found.
Algorithm 2 MXP(B,C) Input: background theory B, set of possibly faulty constraints C Output: a set of minimal con icts 1: if :isConsistent(B) then 2: return "no explanation" 3: else if isConsistent(B [ C) then 4: return ; 5: end if 6: h ; i FindConflicts(B; C) 7: return 8: function FindConflicts(B; C) returns a tuple hC0; i 9: if isConsistent(B [ C) then 10: return hC; ;i 11: else if jCj = 1 then 12: return h;; fCgi 13: end if 14: Split C into disjoint, non-empty sets C1 and C2 15: hC10; 1i FindConflicts(B; C1) 16: hC20; 2i FindConflicts(B; C2) 17: 1 [ 2 18: while :isConsistent(C10 [ C20 [ B) do 19: X GetConflict(B [ C20; C20; C10) 20: X [ GetConflict(B [ X; X; C20) 21: C10 C10nf g where 2 X 22: [ f g 23: end while 24: return hC10 [ C20; i 25: end function 26: function GetConflict(B; D; C) 27: if D 6= ; ^ :isConsistent(B) then 28: return ; 29: else if jCj = 1 then 30: return C 31: end if 32: Split C into disjoint, non-empty sets C1 and C2 33: D2 GetConflict(B [ C1; C1; C2) 34: D1 GetConflict(B [ D2; D2; C1) 35: return D1 [ D2 36: end function
This can be immediately adopted for ABox abduction: in order to nd explanations for an abduction problem P = (K; O) on Abd one needs to call MXP(K [ f:Og; Abd). This observation allows us to adopt the following result from Shchekotykhin et al. [11]: Theorem 4. Assume an ABox abduction problem P = (K; O) and a set of abducibles Abd. If there is at least one explanation Abd of P then calling MXP(K [ f:Og; Abd) returns a nonempty set of explanations of P.
In fact, MXP is thorough in its decomposition of C, which is broken to smaller and smaller subsets until they are consistent with B or until only sets of size 1 remain. This directly implies that all con icts of size 1 will always be found and returned by a single run of MXP. This observation will prove to be useful for our hybrid algorithm.
Observation 5. Given an ABox abduction problem P = (K; O), set of abducibles Abd, and any Abd s.t. j j = 1, if K [ j= O then 2 MXP(K [ f:Og; Abd).
Thus MXP is sound, and if an explanation exists, it always nds at least one (and it nds all of size one). However MXP is still approximative, i.e., it is not complete. Some explanations may be lost, especially in case of abduction problems with multiple partially overlapping explanations.
Example 1. Let K = fA u B v D; A u C v Dg and let O = D(a). Let us ignore negated ABox expressions and start with Abd = fA(a); B(a); C(a)g. There are two minimal explanations of P = (K; O): fA(a); B(a)g, and fA(a); C(a)g. Calling MXP(K [ f:Og; Abd), it passes the initial tests and calls FindConflicts(K [ f:Og; Abd).
FindConflicts needs to decide how to split C = Abd into C1 and C2. Let us assume the split was C1 = fA(a)g and C2 = fB(a); C(a)g. Since both C1 and C2 are now con ict-free w.r.t. K [ f:Og, the two consecutive recursive calls return hC10; ;i and hC20; ;i where C10 = fA(a)g and C20 = fB(a); C(a)g.
In the while loop, GetConflict(K [ f:Og [ fB(a); C(a)g; fB(a); C(a)g; fA(a)g) returns X = fA(a)g while GetConflict(K [ f:Og [ fA(a)g; fA(a)g; fB(a); C(a)g) returns B(a), and hence the rst con ict = fA(a); B(a)g is found and added into .
However, consecutively A(a) is removed from C10 leaving it empty, and thus the other con ict is not found and = ffA(a); B(a)gg is returned. 4
The hybrid algorithm is based on the observation that running MXP multiple times, each time on a slightly modi ed input, results in consecutive extension of the overall con icts that are found. We will show, that the construction of a HS-tree may serve to guide this iterations in such a way, that completeness is achieved.
The combined MHS-MXP algorithm, listed as Algorithm 4, therefore constructs the HS-tree as usual, but in each node n, instead of simply retrieving one model of K [ f:Og [ H(n), it calls FindConflicts.
It starts by checking the consistency of K [ f:Og. We use a modi ed isConsistent function which stores all models in the model cache Mod. This is 14: L(n) 15: for each 16: end if 17: end if 18: end while 19: return SE f 2 Con j 20: function isConsistent(K) 21: if there is M j= K then 22: Mod Mod [ fM g 23: return true 24: else 25: return false 26: end if 27: end function
is desiredg
Require: knowledge base K, observation O, set of abducibles Abd Ensure: set SE of all explanations of P = (K; O) of the class Abd 1: Con fg . Set of con icts 2: Mod fg . Set of cached models 3: if :isConsistent(K [ f:Og) then 4: return "nothing to explain" 5: else if Abd(M ) = ; where Mod = fM g then 6: return SE = ; 7: end if 8: T (V = frg; E = ;; L = ;) . Init. HS-Tree 9: while there is next node n in T w.r.t. BFS do 10: if 6 H(n) for all 2 Con then . Otherwise n is pruned 11: h ; i FindConflicts(K [ f:Og [ H(n); Abd n H(n)) 12: Con Con [ fH(n) [ j 2 g 13: if 6= ; and Abd n Sf 2 j j j = 1g > 1 then . HS-tree is extended under n Abd(M ) n H(n) for some M 2 Mod s.t. M j= H(n)
2 L(n) create new -successor n of n because it will be important to remember the models, even if they are found inside the calls to FindConflicts.
Then the main loop is initiated. For the root node r, FindConflicts is simply called passing K [ f:Og as the background theory and Abd as the set of con icts (as H(n) = ; at this point). The obtained con icts are stored in Con. We then verify if all con icts were already found or the search needs to continue (line 13). From Theorem 4 we know that if no con icts were found in , it means there are no con icts whatsoever. Also from Observation 5 we know that all con icts of size 1 were already found in , which means that any minimal con icts may only possibly remain if at least two abducibles are not present (as singletons) in . If neither of these is true then the HS-tree is extended under r using the model M that was previously found and stored in Mod.
When consecutively any other node n 6= r is visited by the main loop, the node is immediately pruned, if H(n) contains any of the con icts already stored in Con. If not, we now want to use MXP with the goal to explore as much as possible of that part of the space of explanations that extends H(n). Therefore we call FindConflicts passing K [ f:Og [ H(n) as the background theory and Abd n H(n) as the set of con icts. If we are lucky, we might cut o this branch completely (due to Theorem 4 and Observation 5, line 13).
Now in order to extend the HS-tree under n we need a model of K [ f:Og [ H(n). However, we do not need to run another consistency check here, as by design of out algorithm at this point such model is already cached in Mod. Observation 6. For each node n of the HS-tree visited by the main loop of MHS-MXP(K; O; Abd) either H(n) 2 or K [ f:Og [ H(n) is consistent and at least for one M 2 Mod, M j= K [ f:Og [ H(n).
This holds due to FindConflicts was previously called in the parent node n0 of n, and from Observation 5 we know that during that call all possible inconsistent extensions of H(n0) of size 1 were added to . Hence if n was not pruned on line 10, H(n) = H(n0) [ f g must be consistent with K [ f:Og. Moreover, since FindConflicts did not prove f g being a con ict for K [ f:Og [ H(n0), at some point it must have checked the consistency of K [ f:Og [ H(n0) together with f g or some superset thereof with a positive result, and at that point the respective model was added to Mod. 5
We provide a preliminary implementation in Java. It is based on previous
implementations of MHS and MXP [
We rely on OWL API [
The current version has several limitations. Only single atomic ABox observation of the form A(a) is supported. The set of abducibles can not be speci ed yet, instead, all possible ABox assertions of form A(a) are included in the set, for any individual a occurring in the observation O and any atomic concept A occurring in K. Further extension of the implementation and its optimization is ongoing work. The implementation is available online.3 6
MHS-MXP is a new hybrid ABox abduction algorithm for DL. The algorithm builds on the divide and conquer strategy employed by the incomplete MXP and it retains completeness by repetitive runs of MXP while tracking the search space exploration using the HS-tree construction.
The combined MHS-MXP search strategy may likely have an advantage on a certain class of inputs, especially those featuring (even a smaller number of) 3 http://dai.fmph.uniba.sk/~pukancova/mhs-mxp/ explanations of greater size. Exploring such search space with MHS, which relies on breadth- rst search, is rather ine cient.
In the future we would like to characterize the inputs for which MHS-MXP is suitable and also to test this characterization also an empirical evaluation. We would also like to further develop our implementation and explore various possible optimization techniques. For instance, more aggressive model caching can be tried: one does not have to call MXP in every node if there is already a suitable model in cache that can be used to label the node. This however invalidates Observation 6 and additional consistency checks will be required. In addition, con icts that are cached in Con may be used to save consistency checks inside the MXP calls. It would be interesting to implement and empirically test such possible optimization techniques.
Acknowledgments. This work was supported by the Slovak Research and Development Agency under the Contract no. APVV-19-0220 (ORBIS), by the Slovak VEGA agency under Contract no. 1/0778/18 (KATO), and by the EU H2020 programme under Contract no. 952215 (TAILOR). 10. Reiter, R.: A theory of diagnosis from rst principles. Arti cial intelligence 32(1), 57{95 (1987) 11. Shchekotykhin, K.M., Jannach, D., Schmitz, T.: MergeXplain: Fast computation of multiple con icts for diagnosis. In: Proceedings of the Twenty-Fourth International Joint Conference on Arti cial Intelligence, IJCAI 2015, Buenos Aires, Argentina. AAAI Press (2015)