This paper presents a neural network approach for first-order abductive inference by generalising an existing method from propositional logic to the first-order case. We show how the original propositional method can be extended to enable the grounding of a first-order abductive problem; and we also show how it can be modified to allow the prioritised computation of minimal solutions. We illustrate the approach on a well-known abductive problem and explain how it can be used to perform first-order conditional query answering.
Neurosymbolic research aims to combine neural inference methods with symbolic knowledge formalisms in order to better understand and exploit the cognitive functions of brain and mind. The integration of neural networks and logic programs is a major focus in this field. But, most existing work only deals with neural representations of propositional logic programs – which are not very well suited to applications with complex or incomplete information. Thus, our goal is to develop a connectionist approach for typed abductive logic programs – that are specifically intended for this purpose.
Abductive logic programs extend normal logic programs by allowing the truth of particular literals, called abducibles, to be assumed subject to certain conditions, called integrity constraints, when deciding which instances of a query, or goal, succeed from some program, or theory. Thus, any solution to a first-order abductive problem has two parts: a set of variable bindings, called an answer, denoting a successful instance of the goal; together with a set of abducibles, called an explanation, denoting a set of auxiliary assumptions. In this way, abductive logic programming can be seen as a form of conditional query answering.
This paper presents a neural network approach for firstorder abductive inference. The approach generalises an existing method of Ray & Garcez [9] from propositional logic to the first-order case. Like its predecessor, the approach is based on translating an abductive problem into a neural network such that the fixpoints of the network are in one-to-one correspondence with the solutions of the original problem.
Unlike other methods for neural abduction, such as [3; 10; 2; 13; 7; 12; 8; 1], our approach has the benefits of placing no restrictions on the use of negation or recursion and being able to systematically compute all required solutions.
Our main contributions are twofold: we show how the propositional method can be extended to enable the practical grounding of a first-order abductive problem; and we also show how it can be modified to allow the prioritised computation of minimal solutions. The former extension uses techniques from the field of Answer Set Programming (ASP) [6] to reduce the number of logically redundant clauses and literals in the ground program. The latter modification ensures the hypothesis space is searched in a way that gives higher priority to solutions with fewer abducibles. We illustrate the approach and explain how it can be used to perform first-order conditional query answering.
The rest of the paper is structured as follows: Section 2 recalls the relevant background material; Section 3 presents our approach; and the paper concludes with a summary and directions for future work. 2
Background This section recalls some basic notions of neural networks and logic programs. The definitions closely follow those of Ray & Garcez [9], except that variables are now explicitly typed and may appear in any input to an abductive problem. (Threshold) Neural Networks: A neural network, or just network, is a graph (N; E) whose nodes N are called neurons and whose edges E N N are called connections. Each neuron n 2 N is labelled with a real number t(n) called its threshold and each connection (n; m) 2 E is labelled with a real number w(n; m) called its weight. The state of a network is a function s that assigns to each neuron the value 0 or 1. A neuron is said to be active if its value is 1 and it is said to be inactive if its value is 0. For each state s of the network, there is a unique successor state s0 such that a neuron n is active in s0 iff its threshold is exceeded by the sum of the weights on the connections coming into n from nodes which are active in s. A network is said to be relaxed iff all of its neurons are inactive. A fixpoint of the network is any state that is identical to its own successor state. If a fixpoint t is reachable from an initial state s by repeatedly computing successor states, then t is referred to as the fixpoint of s. 8 wont start(C) f lat battery(C) 9 >>>>>< wwoonntt ssttaarrtt((CC)) snpoafrkuepll(uCg)s dirty(C) =>>>>>
head lights work(c1) :>>>>> sfpuaerlkgapuluggesedmirpttyy((cc32)) ;>>>>> wont start(C) ^ :spark plugs dirty(C) f lat battery(C) ^ head lights work(C) no f uel(C) ^ :f uel gauge empty(C) ^ :broken gauge(C) 8< fnloatf ubaelt(tCer)y(C) =9 : broken gauge(C) ;
car(C) (Typed) Logic Programs: A typed logic program, or just program, is a set of rules of the form H B1 ^ : : : ^ Bn ^ :C1 ^ : : : ^ :Cm in which the H, Bi and Cj are atoms and in which any variable is associated with a unary predicate called its type or domain. The atom to the left of the arrow is called head of the rule, while the literals to the right comprise the body. The head atom H and the positive body atoms Bi are said to occur positively in the rule, while the negated body atoms Cj are said to occur negatively. A rule with no negative body literals is called a definite clause and written H B1 ^ : : : ^ Bn. A rule with no body literals is called a fact and simply written H. A rule with no head literal is called a denial and written B1 ^ : : : ^ Bn. If P is a program, then BP (the Herbrand base of P ) is the set of all atoms built from the predicate and function symbols in P ; and GP (the ground expansion of P ) is the program comprising all well-typed ground instances of the clauses in P . In addition, Ap+ and AP denote, respectively, the sets of ground atoms that occur positively and negatively in GP . A stable model of P is a Herbrand interpretation I BP that coincides with the least Herbrand model of the definite program P I obtained by removing from GP each rule containing a negative literal not in I, and by deleting all of the negative literals in the remaining rules.
Abductive Logic Programs: An abductive logic program [4] is a triple (T; IC; A) where T is a program (the theory), IC is a set of denials (integrity constraints), A is a set of facts (abducibles). Given a conjunction G of literals (goals), the task of ALP is to compute a set of variable substitutions (an answer) and a set of ground abducibles (an explanation) such that there is a stable model of T [ (which, in the terminology of [5], is called a generalised stable model of T ) that satisfies all of the denials in IC and all of the literals in G . To specify an abductive problem, one must state the theory T , goal G, constraints IC, and abducibles A. If needed, the types of any variables can be explicitly given as a set of facts D (domain declarations) with one atom p(X) for every variable X of type p. For convenience, we will refer to the collection of five inputs (T; G; IC; A; D) as a (typed) abductive context. A context is propositional if it contains no variables. When a context has many different solutions it is usual to prefer explanations with the fewest number of abducibles. Intuitively, this corresponds to the principle of Occam’s Razor, which favours the simplest hypotheses that fit the data. In practice, this means that subset-minimal and/or cardinality-minimal explanations are usually required.
Example 2.1. Consider the abductive context in Figure 1.
The theory T describes a collection of three classic cars. It states that a car C wont start if its battery is flat, if its fuel tank is empty, or if its spark plugs are dirty. It also states that the headlights of the first car c1 are working, that the fuel gauge of the second car c2 is showing empty, and that the spark plugs of the final car c3 are dirty. The constraints IC state, firstly, that the battery of a car cannot be flat if the headlights of that car are working and, secondly, that it is impossible for a car to have no fuel if its fuel gauge is not empty and not broken. The abducibles A allow us to assume that any car has a flat battery, has no fuel, and/or has a broken fuel gauge. The goal G asks for which cars C it is possible to show that (1) the car does not start and that (2) the car does not have dirty spark plugs. The domain declarations D assert that all occurrences of the variable C represent cars.
This problem has many solutions. There are two cardinality-minimal solutions which bind C to c2 after abducing no f uel(c2) or f lat battery(c2), respectively. There is one more subset-minimal solution which binds C to c1 after abducing no f uel(c1) and broken gauge(c1). Note that, by the second constraint, no f uel(c1) can only be abduced if broken gauge(c1) is also abduced (at its gauge is not showing empty). Note also, by the first constraint, f lat battery(c1) cannot be abduced (as its headlights work).
More than a hundred non-minimal solutions can be obtained by adding redundant abducibles to the explanations above.
As non-minimal solutions are often of little practical use, this paper will develop a neural approach for preferentially finding minimal solutions of first-order abductive problems.
First order Neural network abduction The approach in this section builds on well-known methods for translating propositional logic programs into neural networks whose fixpoints correspond to stable models. In actual fact, we build upon an extension of these methods proposed by Ray and Garcez [9] for translating propositional abductive contexts into neural networks whose fixpoints correspond to generalised stable models. This is done by rewriting negative literals as abducibles and adding clauses that, when translated into a neural network, perform a systematic search through the space of abductive solutions.
In principle, one could try and solve a first-order problem by applying the method of [9] to the propositional context obtained by taking all possible well-typed ground instances of the abductive inputs. But, in practice, this naive approach is not feasible as it generates neural networks that are too large and take too long to find the minimal solutions.
To address these limitations, we developed an improved
method for more effectively computing the minimal solutions
of first-order problems. The new approach exploits an ASP
system called LPARSE [
Given a typed first-order abductive context, the new method has six main steps: First it introduces new predicates into the language to represent abducibles and negations. Then it translates the typed abductive context into a normal propositional abductive context using LPARSE together with some appropriate pre- and post-processing. Next it rewrites any negative literals in the theory as abducibles subject to some simple integrity constraints that preserve their logical meaning. After that, it adds some clauses that allow the resulting network to compute abductive solutions. At this point, it translates the resulting context into a neural network. Finally it allows the network to compute the abductive solutions in order of minimality. These steps are now described in turn.
STEP 0: Extending the Language The logical transformations used in our method require the introduction of predicates to represent abducibles and negations. For every predicate p in a given abductive context, we assume two new predicates, denoted py and p , which represent the assumption of p and the negation of p, respectively.
STEP 1: Obtaining a Propositional Context
Our approach for translating a typed first-order abductive
context into a normal propositional abductive context uses a
system called LPARSE which, as described in [
Pre-processing: We first turn an abductive context into a logically equivalent program by temporarily employing negative cycles to represent abducibles. This is needed to prevent LPARSE from treating abducibles as undefined domain predicates, which would otherwise be removed from the ground program. Then domain declarations of the form #domain p(V ) are added for each variable V of type p in D (which causes LPARSE to add the atom p(V ) into the body of every clause containing V ). Finally, the goal G is turned into a clause by using a new propositional atom goal as the head.
This is carried out by the function below.
Definition 3.1 ( ). Let X = (T; G; IC; A; D) be a typed abductive context and let G0, A0 and D0 be as follows
G0 = fgoal L1 ^ : : : ^ Ln j L1 ^ : : : ^ Ln = Gg, a a A0 = :a a 2 A
:a D0 = f#domain p(V ) j p(V ) 2 Dg Then Y = (X) is the logic program T [G0 [IC [A0 [D0.
Grounding: The resulting program is now grounded and simplified by LPARSE, as indicated by the function below.
Definition 3.2 ( ). Let Y be a logic program (possibly containing domain declarations). Then Z = (Y ) is the ground logic program obtained by running LPARSE on Y .
Post-processing: After running LPARSE, any surviving ground instances of the negative cycles introduced by the preprocessing phase are converted back into explicit abducibles.
This is done by replacing each cycle of the form a :a and a :a with a bridging clause a ay and making the ground atom ay abducible. It is interesting to note that this re-conversion is not strictly necessary as any negations will be replaced by abducibles and integrity constraints in the next step. But, it is more efficient to exploit the fact that each cycle represents a single abducible in order to avoid the unnecessary introduction of one additional abducible and two additional integrity constraints. The bridging clauses allow to distinguish instances of an atom whose truth is abduced from those whose truth is implied. In addition, any resulting ground instances of the goal clause are added to the theory T1 and their head atom goal becomes the new propositional goal. This process is performed by the function below. define Definition 3.3 ( ). Let Z be any ground logic program and
ZIC = f L1 ^ : : : ^ Ln 2 Zg ZG = fgoal L1 ^ : : : ^ Ln 2 Zg ZA = fa :a 2 Zg [ fa
:a 2 Zg
ZT [ ZG [ fa
ZT = Z n (ZIC [ ZG [ ZA)
Then W = (Z) is the propositional abductive context (T1; G1; IC1; A1; D1) such that
T1 = :a g 2 ZAg ay j fa G1 IC1 A1 D1 = = = = ; fgoalg ZIC fay j fa :a g 2 ZAg
car(c1) > > > > car(c2) > > > > > car(c3) > > > > > wont start(c1) > > > > > wont start(c2) > > > > > wont start(c3) > > > > > wont start(c1) > > > > < wont start(c2)
wont start(c3) > > > > > > > wont start(c1) > > > > > > wont start(c2) > > > > > > wont start(c3) > > > > > spark plugs dirty(c3) > > > > > f uel gauge empty(c2) > > > > : head lights work(c1) 8 > > > < > > 8 f : : goal
g goal goal > goal : wont start(c1) wont start(c2) wont start(c3) ^: ^: ^ : spark plugs dirty(c1) spark plugs dirty(c2) spark plugs dirty(c3) > ; 9 > > > = > > 9 > > > > > > > > > > > > > > > > > > > > > > = > > > > > > > > > > > > > > > > > > > > > > ; f lat battery(c1) head lights work(c1)
^ f lat battery(c2) head lights work(c2)
^ f lat battery(c3) head lights work(c3)
^ no f uel(c1) broken gauge (c1) ^ ^:
f uel gauge empty(c1) ^ : no f uel(c2) broken gauge(c2)
f uel gauge empty(c2) ^ : no f uel(c3) broken gauge (c3) ^
^: broken gauge (c1) broken gauge (c1)
^ broken gauge (c1)
broken gauge (c1) broken gauge (c3)
broken gauge (c3) ^ broken gauge (c3)
broken gauge (c3) ^ : ^ :
f uel gauge empty(c3) f lat battery(c1) f lat battery(c2) f lat battery(c3) no f uel(c1) no f uel(c2) no f uel(c3) spark plugs dirty(c3) > > > > no f uel(c3) > > > > > > > > spark plugs dirty(c1) > > > > f lat battery(c1) > > > > > > > > spark plugs dirty(c2) > > f lat battery(c2) > > > > > > > > > :
f lat battery(c3) > > > > > > > > > > > > > > > ; > > > > > > > > > > > > > > 8 > broken gauge(c1) > > > > > > > > > broken gauge(c2) > > > > > > > > > > broken gauge(c3) > > > > > > > > > > > > no f uel(c1) > > > > = <
no f uel(c2) [ no f uely(c1) no f uely(c2) no f uely(c3) broken gaugey(c1) > > > broken gaugey(c2) > > > > > broken gaugey(c3) > > > > > > > > > = 9 f lat batteryy(c1) f lat batteryy(c2) f lat batteryy(c3) > > > > > > > > > > > > > > > > > ; no f uely(c1); f lat batteryy(c1); broken gaugey(c1); broken gauge (c1) no f uely(c2); f lat batteryy(c2); broken gaugey(c2) no f uely(c3); f lat batteryy(c3); broken gaugey(c3); broken gauge (c3) Example 3.1. The result of applying the above transformation to the abductive context of Example 2.1 is shown in Figure 2 — which, for convenience, also shows, within boxes, the clauses and literals removed by LPARSE. Note that the omitted rules can never be true and the omitted constraints can never be violated.
STEP 2: Obtaining a Definite Theory To avoid potential problems resulting from the unrestricted use of negation in the theory (which could result in networks where some states have no fixpoints) we use a well-known equivalence between negation and abduction which allows us to treat each negative literal :p(t1; : : : ; tn) as an abducible p (t1; : : : ; tn) subject to integrity constraints stating that an atom and its negation cannot both be true or both be false in the same model. Intuitively, we are free to assume the falsity of any atom if it is consistent to do so. As formalised by the function , below, we add such constraints for all ground atoms appearing negatively in the context. For convenience, this function uses some notation for representing the positive form of an expression obtained by replacing all negative literals by their abducible proxies.
Definition 3.4 ( ). Let C = H B1 ^ : : : ^ Bn ^ :C1 ^ : : : ^ :Cm be a clause. Then C is the (definite) clause C = H B1 ^ : : : ^ Bn ^ C1 ^ : : : ^ Cm.
Definition 3.5 ( ). Let W = (T1; G1; IC1; A1; D1) be a propositional abductive context. Then (W ) is the abductive context, (T2; G2; IC2; A2; D2) such that
T2 = G2 = IC2 = fC j C 2 T1g fC j C 2 G1g fC j C 2 IC1g a ^ a :a ^ :a A [ fa j a 2 AT1[IC1[G1 g D1
a 2 AT1[IC1[G1 A2 D2 STEP 3: Adding Clauses for Abduction We now add some extra clauses that, when translated into a neural network, will perform a systematic search through the space of abductive solutions.
As in the method of Ray & Garcez [9], we use a binary counter whose output determines which abducibles are assumed and which are not. In earlier work, the output of this counter followed a simple binary sequence: 000, 001, 010, 011, 100, etc. But, in this paper, we wish to keep the number of abducibles as small as possible for as long as possible.
Thus we use a modified search sequence (called a Banker’s sequence) where the number of true bits increases monotonically: 000, 100, 010, 001, 110, etc.
In fact, we use two cascaded Banker’s sequences, one for pure abducibles ay 2 A2 and one for (the negations of) the negative literals a 2 A2. The clauses which define these counters are formalised in the theory C below. Firstly, C1;n1 denotes a counter with n1 bits a1n1 ; : : : ; a11 bits corresponding to the abducibles ayn1 ; : : : ; ay1. Secondly, C2;n2 denotes a counter with n2 bits a2n2 ; : : : ; a21 bits corresponding to the abducibles an2 ; : : : ; a1. Each counter i has HOLDi and M OV Ei conditions that determine its behaviour when a global next signal is applied to the network. If HOLDi is true, it will keep its current value. If M OV Ei is true, it will advance to the next value in the Banker’s sequence. If neither is true, the counter will reset to zero.
The definition of each counter Ci;n is split into five macros Ci;n to Ci;n that together provide a logical specification of
1 5 the counter state transition table. In brief, bij is true iff the jth bit of counter i is true; cij is true iff bij is true and bij 1 is false; dij is true iff cij is true and cik is false for all k < j; eij is true iff bij is false and bij 1 is true; and alli is true iff all the bits of counter i are true.
C Ci;n Ci;n
1 Ci;n
2 Ci;n
3 Ci;n
4 Ci;n 5 = = = = = = =
C1;n1 [ C2;n2 5 [ Ci;n k such that
where k=1 8 >>> bik > > > n >> [ < bik n ^ j=1 n ^
9 :dij ^ bin k ^ M OV Ei >> > > > > > > = :dij ^ ein k ^ M OV Ei k8=0 >>>>>>>:> bbiikk n jbb=iikk1^^ :HnOeLxtDi 9 ><>>> bin ^ :bij ^ M OV Ei =>>>> > > > > > > > > ; j=0 n ^ bi
j j=0 >>> alli > : n k 1 [ [ k=2 j=0 8 eik >>> ci > k > n >> [ < dik k=1 >>
> i n >:>>> nbakik 1 [ [ > > > > ; 9 > > > > > > > = bik 2 j bj ^ dk ^ M OV Ei i i i i :bk ^ bk 1 i i bk ^ :bk 1 k 1 ^
i i :cj ^ ck ABDki j=1 > dik ^ M OV Ei >>>>> > ; bij bj ^ dk ^ M OV Ei i i next ^ all2 next ^ :all2 :all2 f alse b1k for all k :b2k for all k
The 2nd counter increments until its maximum is reached, whence it resets. The 1st counter holds until the 2nd resets, whence it increments. To preferentially minimise the number of assumed abducibles the outputs a1n1 : : : a11 of the 1st counter are obtained by copying the corresponding bits b1n1 : : : b11. To preferentially maximise the number of atoms assumed false, the outputs a2n2 : : : a21 of the 2nd counter are obtained by negating the corresponding bits b2n2 : : : b21.
As in [9], we advance the counter if a fixpoint f p is reached that violates the goal goal or integrity constraints ic. Previously, this was done by a clock with a constant period determined by worst case propagation delay through the network generated by the program. For efficiency, we now add clauses to detect as soon as a fixpoint is reached. These are given by the theory S below, which uses four new propositions z0; z+; z ; z$ to compare the current state of each atom z (in a set Z of atoms) with their previous states.
In brief, z0 denotes the previous state of z; z+ is true iff the current and previous states are both true; z is true iff they are both false; and z$ is true iff they are the same. The w1-w4 are wait signals that just give the counters enough time to compute their next value before the network decides whether the current abducibles are a solution (in which case the signal soln is activated) or whether another set of abducibles are needed (in which case the signal next is activated). f p indicates when a fixpoint has been reached.
The signal done indicates when all solutions are exhausted.
S SZ
1 SZ
2 SZ 3 = = = =
SZ 1 [ S2Z [ S3Z 8 z0 z >>> z+ [ < z
$ z2Z >>>: zz$ where
9 z ^ z0 >>> :z ^ :z0 = z+ >> > ; z next w1 w2 w3 8 w1 >> w2 > > > >< w3
w4 > > >>>> f p : 8 next >< next
soln >: done ^ z$ ^ ^4 :wi ^ :next >>>>>> ; 9 > = z2Z i=1 :next ^ f p ^ ic :next ^ :goal ^ f p :next ^ goal ^ f p ^ :ic all1 ^ all2 ^ f p > ; 9 > > > > > > =
To properly specify these additional clauses, it is necessary to state the parameters n1, n2 and Z in C and S. This is done by the function below, which defines n1 as the number of abducibles ay, n2 as the number of negations a , and Z as the set of all atoms appearing (positively or negatively) in the context. In addition, this function adds a special atom ic into the head of every integrity constraint, and adds the literal :next into the body of every rule to ensure the network is fully relaxed whenever a new solution is attempted.
The resulting network architecture is summarised in Figure 3.
Definition 3.6 ( ). Let (T2; G2; IC2; A2; D2) be a propositional abductive context with G2 = fgoalg and D2 = ;.
Now let n1 = jfay 2 A2gj, let n2 = jfa 2 A2gj, let Z = AT+2[G2[IC2 [ AT2[G2[IC2 , and let R be the program
R = H B1 ^ : : : ^ Bn ^ :next
j H B1 ^ : : : ^ Bn 2 T2 Now we translate the clauses obtained so far into a network using the method of Ray & Garcez [9], recalled below, which is based on well-known neurosymbolic techniques.
Definition 3.7 ( ). Let P be a logic program, then (P ) is the network (N; E) such that N = [ E = [ r2GP r2GP and for all r = H t(r) = n
1=2 r; H; B1; : : : ; Bn; C1; : : : ; Cm j r = H B1 ^ : : : ^ Bn ^ :C1 ^ : : : ^ :Cm (r; H); (B1; r); : : : ; (Bn; r); (C1; r); : : : ; (Cm; r) j r = H B1 ^ : : : ^ Bn ^ :C1 ^ : : : ^ :Cm
B1^: : :^Bn^:C1^: : :^:Cm 2 GP t(H) = 1=2 t(Bi) = 1=2 t(Cj ) = 1=2 w(r; H) = 1 w(Bi; r) = 1 w(Cj ; r) = 1
STEP 5: Computing Abductive Solutions In the last step, we compute the answers with the neural network. Starting from a relaxed network, we activate the node next. Then, on every other subsequent state, we check whether the network has reached a fixpoint where soln activated. If it has, then the current abducibles are recorded and we see which of the goal rules is activated in order to extract the successful ground instances of the query. If more solutions are required then we activate next in order to seek the next answer. We stop this process when a suitable answer is computed or done is true, meaning the entire search space has been explored. 4
Conclusion and future work We believe that the integration of abductive and inductive inference is necessary to develop improved learning and reasoning approaches. In this paper we presented a neurosymbolic approach for first-order abductive inference. Unlike most other such approaches, we do not impose any restrictions on the use of negation or recursion. However, the ASP grounding procedure assumes that all variables have finite domains, which limits the use of function symbols. We have implemented our method using the C++ programming language and applied it to the abductive context shown in Figure 1.
In this way, we correctly obtained the minimal solutions followed by all of the other non-minimal solutions. Even in this simple example we note that the search time increases significantly if a naive grounding is used in place of our more efficient ASP approach. We also note that the time needed to compute all minimal solutions is significantly less than the time needed to compute all (non-minimal) solutions. In this sense we have improved existing methods of neurosymbolic abduction. However, the complexity of the approach is still exponential in the number of abducibles, which limits its practical use. In future work, we will compare our neural approach with related symbolic approaches and investigate ways of parallelising our method. stable states z $i next current states SZ1
R soln done goal
ic C2,n2
C1,n1
HOLD1 all 2 an22 a12 all 1 a1n1 negative assumptions abducible assumptions