Combining machine learning with logic-based expert systems in order to get the best of both worlds are becoming increasingly popular. However, to what extent machine learning can already learn to reason over rule-based knowledge is still an open problem. In this paper, we explore how symbolic logic, defined as logic programs at a character level, is learned to be represented in a high-dimensional vector space using RNNbased iterative neural networks to perform reasoning. We create a new dataset that defines 12 classes of logic programs exemplifying increased level of complexity of logical reasoning and train the networks in an end-to-end fashion to learn whether a logic program entails a given query. We analyse how learning the inference algorithm gives rise to representations of atoms, literals and rules within logic programs and evaluate against increasing lengths of predicate and constant symbols as well as increasing steps of multi-hop reasoning.
There has been increasing interest and attempts at combining
machine learning with logic-based expert systems in order
to get the best of both worlds: have an end-to-end trainable
system that requires little data to learn how to reason, possibly
using existing background knowledge, and is interpretable
by humans
A crucial component in existing logic-based expert
systems is the ability to iteratively use a given knowledge base.
Framed as multi-hop reasoning, these tasks require an agent
to process information over several steps to reach a
conclusion. This paradigm of reasoning has been performed by
neural networks in domains such as story comprehension
with Dynamic Memory Networks
Another important aspect of machine learning that allows
scalability is learning dense distributional representations
such as word embeddings
This paper provides the following contributions, (i) a new synthetic dataset consisting of 12 various classes of normal logic programs, (ii) an iterative neural inference network to learn end-to-end different reasoning tasks and (iii) analysis of how these networks represent logic programs and handle multi-hop reasoning. Our implementation is publicly available online at https://github.com/ nuric/deeplogic. 1: Facts 2: Unification
3: 1 Step e(l). i(u). n(d). v(h,y). p(n). ? e(l). 1 ? i(d). 0 o(V,V). i(x,z). y(w,d). p(a,b). t(A,U). ? o(d,d). 1 ? o(b,d). 0 g(L,S) :- x(S,L). x(a,m). y(X) :- r(X). p(h). s(t,v). ? g(m,a). 1 ? g(a,m). 0 4: 2 Steps x(G,B) :- k(G,B). k(Z,V) :- g(Z,V). g(k,k). e(k,s). p(L,G) :- v(G,L). ? x(k,k). 1 ? x(k,s). 0 5: 3 Steps p(P,R) :- b(R,P). b(A,L) :- a(A,L). a(W,F) :- v(F,W). v(t,i). l(D) :- t(D). ? p(t,i). 1 ? p(i,t). 0 6: Logical AND f(P,U) :- b(P) , p(U). b(x). p(x). p(y). e(y,v). ? f(x,x). 1 ? f(y,x). 0 7: Logical OR e(D,X) :- n(D,X). e(D,X) :- w(D,X). e(w,y). n(n,j). w(t). ? e(n,j). 1 ? e(i,j). 0
A normal logic program
A L1; : : : ; Ln (n 0) (1)
where A is an atom and each Li is a literal. A literal is either
an atom (a positive literal) or a negated atom of the form
not A where not is negation by failure
r(X): q(a): As in equation 2, the is replaced with :- and the negation by failure not with while maintaining the same semantics. When there are no body literals we omit the implication entirely, equation 3.
f (C; Q) = 1 if C ` Q 0 otherwise f (C; not Q) = 1 f (C; Q) We define the logical reasoning process as an inference function f , equation 4, that given a normal logic program (without function symbols) as context C 2 C and a ground atom as query Q 2 Q returns f1; 0g = B depending on whether the context entails the query C ` Q or not. We can now define negation by failure not Q using the outcome of the corresponding positive ground query Q, equation 5.
f (C; Q) , p(QjC) In order to learn the reasoning process, we define an auxiliary objective for the neural network and consider the inference function f to be the conditional probability of the query given the context, equation 6. This approach renders the problem, from a machine learning perspective, as a binary classification problem and allows training using standard cross-entropy loss.
Inspired by the bAbI dataset
Each task is generated using a fixed procedure from which samples are drawn. For constants and predicates we use the lower case English alphabet and for variables upper case. The length of the character sequences that make up predicates, constants and variables can be of arbitrary length (only examples of length 1 are shown) but we generate lengths up to 2 for the training dataset and longer lengths for test data. The arity of the atoms are selected randomly between 1 and 2. For every sample we also generate irrelevant rules as noise that always have different predicates and random structure while still preserving the semantics of the task.
Facts The simplest task consists only of facts. There is only one successful case in which the query appears in the context and can fail in 3 different ways: (i) the constant might not match (shown in Table 1), (ii) the predicate might not match or (iii) the query might not be in the context at all. These failures can cascade and a query can fail for multiple reasons with equal probability.
Unification These tasks contain rules with empty bodies and an atom with variables in the head. The intended objective is to emphasise the semantics of unification between different p(X; Y ) and same variables p(X; X). The query succeeds if the corresponding variables unify and fail otherwise. The failure case in which same variables do not match different constants is in Table 1.
N Step Deduction One prominent feature of logical reasoning is the application of rules that contain literals in the body. These tasks cover the case when there is a single positive atom in the body. All such rules contain only variables and chains of arbitrary steps can be generated. For the training dataset, we generate up to 3 steps, samples in Table 1. The query succeeds when the body of the last rule in the chain is grounded with the same constant as in the query. We occasionally swap the variables p(X; Y ):-q(Y; X): to emphasise the variable binding aspect of rules which can happen at any rule in the chain or not at all. The failure cases are covered when the swapped constants do not match or when the final body literal in the chain fails due to reasons covered in the first task. 8: Transitivity 9: 1 Step NBF 10: 2 Step NBF 11: AND NBF
Logical AND Building upon the previous deduction tasks, we create rules with 2 body literals to capture the logical ^ semantics in rules, sample in Table 1. The reasoning engine now has to keep track of and prove both body literals to succeed. A failure occurs when one randomly selected body literal fails for reasons similar to the first task.
Logical OR Having multiple matching heads captures the semantics of _ in logic programming by creating several possible paths to a successful proof, sample in Table 1. In this task we branch the query predicate 3 ways, 2 implications and 1 ground rule. The query succeeds when any of the rules succeed and fail when all the matching rules fail.
Transitivity Based on the previous 2 tasks, the transitive case covers existential variable binding. It requires the model to represent the conjunction of the body literals of a rule and match multiple possible facts. The case succeeds when the inner variable unifies with the ground instances or fails otherwise. We expect an reasoning engine to solve the previous 2 tasks in order to solve this one, sample in Table 2.
N-Step Deduction with Negation These tasks introduce the concept of negation by failure. The body literal of the first rule in the chain is negated and a chain of arbitrary length is generated. For the training dataset we only generate proof chains of length 2, samples in Table 2. The query succeeds when the negated body atom fails; the swapped variables do not match the constants, or the body literal of the final rule in the chain fails for reasons similar to the first task. The query fails whenever the negated body atom succeeds following the semantics described by equation 5.
Logical AND with Negation After introducing negation by failure, we consider negation together with logical ^ and randomly negate one of the body literals, sample in Table 2. As such, the query succeeds when the negated body atom fails and the other literal succeeds. The query can fail when either body literal fails similar to the non-negated case.
Logical OR with Negation Finally, we consider negation together with the logical _ case and negate the body literal of one rule. The query succeeds when any matching rule except the negated one succeeds and fails if the negated rule succeeds while other matching rules fail, sample in Table 2.
In this section we describe a RNN-based iterative neural
network for learning the inference function f , equation 4.
Broadly, we call networks that learn logical reasoning,
Neural Reasoning Networks and the objective is to learn how
C ` Q is computed solely from examples. The primary
challenge for these networks is to have a fixed network
architecture that must process all the tasks unlike tree based
recurrent networks
Design We can consider the logic program context a
readonly memory and the proof state a writable memory
component. In a similar fashion to Prolog’s backward chaining
algorithm
Multi-task DMN rule
IMA considered a variant of Memory Networks, designed to suit the logical reasoning process in which the recurrent component is iterated over literals to perform reasoning, a graphical overview is shown in Figure 1.
The inputs to the network are two sequences of characters c0C ; : : : ; cCm and c0Q; : : : ; cnQ for context and query respectively. The principle motivation behind having character level inputs rather than symbol tokens is to constrain the network to learn sub-symbolic representations that could potentially extend to previously unseen literals. We pre-process the context sequence to separate it into literals and obtain an input tensor IC 2 NR L m0 of characters encoded as positive integers where R is the number of rules, L number of literals and m0 the length of the literals. The query is a single ground positive atom encoded as a vector I Q 2 Nn. This pre-processing allows the network to consider each literal independently when iterating over rules giving it finer control over the reasoning process.
ht = GRU (O[I::t]; ht 1)
(7)
Each literal is embedded using a recurrent neural network that
processes only the characters of that literal I::t, equation 7
where O[I::t] is the one-hot encoding of the characters. We
use a gated recurrent unit (GRU)
In order for the network to propagate the state unchanged, we append a null sentinel = !0 which allows the network to ignore the current reasoning step by carrying over the state. We also append a blank rule () that acts as a learnable parameter and is often attended when no other rule is suitable.
The iterative step consists of attending to the rules, computing a new state using each rule and updating the old state. The network is iterated for T steps, fixed in advance, with the initial state s0 2 Rd set to the query vector s0 = q. cait = [st ; q ; ri ; (st ri)2 ; st ri] it =
(W 1 d2 (U d2 dcait + b d2 ) + b1) At any time step t, we compute a feature vector cait 2 R5d for every head of a rule ri = Ci0 using the current state st 2 Rd, equation 8 where [; ] is the concatenation operator. We also experiment with embedding rules using another GRU over literals h0ij = GRU (Cij ; h0i;j 1) and take the final state ri = h0iL as the representation of the rule. To compute the final attention vector it, we use a two layer feed-forward network, equation 9 where is the sigmoid function. We also experiment with the softmax formulation of the attention vector it after the two layer feed-forward network. uij = GRU (Cij ; uit(j 1)) t
R st+1 = X i t t iuiL (8) (9) (10) (11) To apply a rule, we use another recurrent neural network that processes every literal of every rule Cij . The initial hidden state ui0 = st is set to the current state st, then for t every rule a GRU is used to compute the new hidden state uitj , equation 10. Finally, the new state st+1 becomes the weighted sum of the final hidden states uitL, equation 11. We call the inner GRU unifier as it needs to learn unification between variables and constants as well as how each rule interacts with the current state.
We carry out experiments on individual tasks with variations
on our model. As a baseline, we use a LSTM
Training We use two training regimes: curriculum
learning
We generate 4 test sets of increasing difficulty: validation, easy, medium and hard which have up to 2, 4, 8 and 12 characters for predicates and constants as well as added number of irrelevant rules respectively. Each test set consists of 10k generated logic programs per task and results for the best single training run out of 3 for each model with state size d = 64 on the easy set are shown in Table 3.
We observe that all iterative models perform better than the baseline except for task 8, transitivity which all models fail at. We speculate the reason is that the models have not seen existential variable binding for more than 2 character constants and fail to generalise in this particular case. We note that the curriculum training regime has no benefit for any model most likely because we introduce new, unseen tasks with each iteration such that models with prior training have no advantage, ex. solving OR in 2 iterations does not improve the solution for AND in 3 iterations. Embedding literals seems to provide an advantage over embedding rules since all IMA models outperform both DMN and MAC when we consider the mean accuracy over every test set. We postulate literal embeddings give a finer view and allow for better generalisation over increasing lengths as embedding rules with literals (lit+rule) also degrades the performance. Although our variant IMA performs the best on all the test sets, all models quickly degrade in mean accuracy as the difficulty increases. We speculate that a finite sized state vector stores limited information about unseen unique sequences of increasing lengths and analyse this behaviour further in the next section.
Figure 2 portrays the attention maps produced by IMA
with softmax attention. Although by default models converge
to backward chaining, by (i) reversing the direction of the
unifier GRU, equation 10, and (ii) skipping task 2, we can
create a bias towards ground facts that have a matching
constant. This approach encourages our model IMA with rule
embeddings (lit+rule) to converge to forward chaining
Since models are trained in an end-to-end fashion, the representations for logical constructs that help perform reasoning must also be learned. In this section, we scrutinise the learnt representations of the embedding GRU, equation 7 for IMA and the rule embeddings of DMN.
An important assumption made in the dataset is that every
predicate and constant combination is unique. We expect this
setup to create a formation that would allow every literal to
be differentiated. As such, we observe a lattice like structure
when the embeddings of single and double character atoms
are visualised in 3 dimensions using principle component
analysis (PCA), Figure 3. The first two components select
the predicate and the final the constant to uniquely identify
the literal with a clear distinction between single and double
character predicates. This arrangement is in contrast with
distributional representations that exploit similarities between
entities such as in natural language embeddings
As the embedding sizes are finite, we also expect a saturation in the embedding space as the length of the literals increase. We capture this phenomenon by repeating the character p 64 times and observe a converging pattern shown in Figure 4. We take note how odd and even length predicates converge to their own respective point suggesting that the embeddings produced by the GRU, equation 7, learn parity.
If we take structurally different literals we observe a preference towards whether literals are negated or grounded then the arity of the atoms, Figure 5a. We believe this clustering captures the literal semantics available in the dataset within 4 major clusters (grey lines). Furthermore, if we look at the rule embeddings learnt by DMN, we notice a similar clustering based on rule structure with again groundedness, negation, arity and number of body literals as learnt distinguishing features, Figure 5b. The multiple points within a cluster correspond to different predicates following a similar ordering, for example predicate p is often the upper most point.
To evaluate multi-hop reasoning, we generate logic programs that require increasing number of steps of deduction.
While the training data contains up to 3 steps, we generate up to 32 steps and the networks are run for n + 1 iterations.
We obtain similar results to other recurrent neural network
based systems
We speculate that with each iteration step the state representation degrades eventually losing information since models tend to produce noisy attention maps or state transformations.
Our IMA model with softmax attention maintains the highest accuracy most likely due to the sparsity created by the softmax operation.
To evaluate generalisation to unseen symbols, we take task 3 and generate increasing character lengths of random predicate or constant symbols up to 64, well beyond the training dataset length of 2. Although we observed that literal embeddings can saturate, models can cope with longer randomly generated predicate or constant symbols, Figure 7a, since looking at only a few characters can determine uniqueness. This reflects on our intuition that looking at portions of sequences might be enough to determine equality rather than memorising them entirely, ex. looking at last few digits of phone numbers to check if they are same.
In order to understand how the embedding and state dimensions d affect the models, we experimented with sizes 32, 48, 64, 96 and 128 running each curriculum training session 3 times for our IMA model. Figure 7b shows that increasing the dimension size does not contribute to a clear increase in mean accuracy over all tasks and the drop in accuracy across easy, medium and hard test sets follow a similar pattern for every dimension. Despite the initial increase beyond d = 32, we get the highest upper bound in accuracy with d = 64, for which the individual results are in Table 3.
We designed the tasks to be of increasing difficulty building on previously seen problems such as unification before deduction. We expected models trained using an iterative scheme would generalise better as the network depth would increase gradually. However, when we average the mean (a) Structurally different literals first cluster by whether they are (b) Rule embeddings form clusters based on their structure with a negated or grounded then by arity (grey lines added as visual aids); distinction between negated and non-negated rules (grey line added from IMAsm. as visual aid), from DMN. accuracy for all dimensions, for all 3 runs of IMA with softmax attention across the test sets, we do not discern any advantage for curriculum training over multi-task training beyond the validation set. Figure 7c shows a similar decrease in performance across the test sets for both training regimes.
We believe this result stems from introducing new tasks with each iteration and models not having any incentive to abstract subtasks until the next set of unseen tasks are incorporated into the training dataset.
Given the simple, unit test like nature of the logic programs generated, the lack of robust results for iterative neural networks further encourages a combination of machine learning and symbolic systems rather than encompassing one with the other. In this section, we try to provide additional discussion and insight into why one might or might not learn symbolic reasoning from scratch using iterative neural networks.
Whilst the basic logic programs presented in this paper
can all be solved using existing symbolic systems such as
Prolog
Although a 64 dimensional vector can in theory encode a lot of information, in practice neural networks trained using back-propagation do not seem to have any guarantees on how efficiently they will learn representations in a vector space.
We speculate that this creates an accumulative noise with each iteration which eventually degrades the performance.
On the other hand, the learnt continuous representations scale to very long previously unseen symbols, Figure 7a, which is a desirable property of neuro-symbolic systems.
Attention mechanisms allow state-of-the-art memory
based networks to address and operate an external
memory
However, we speculate such an attention mechanism will
become the bottleneck when there are large numbers,
possibly hundreds of matching rules such as in knowledge base
completion tasks since it will try to aggregate all matching
(a) The models can cope, in particular IMA (b) Mean accuracy over all tasks against in- (c) Mean accuracy of training regimes applied
with literal embeddings, when predicate and creasing embedding dimension d shows no to IMAsm against test sets across all
dimenconstant symbols of increasing length are ran- clear increase beyond d = 64. sions show no advantage of curriculum
traindomly generated. ing for generalisation.
rules in a single step. An explicit strong supervision of the
attention mechanism, similar to the original DMN
Lack of abstraction between seemingly related tasks limits the performance on unseen logic programs. During curriculum training, we noticed models which solve tasks 1, 2 and 3 have no advantage on solving task 4 because the final state representation from task 3 specifically looks for a ground instance such as p(a) to complete the task. However, in task 4 the model needs to match another rule p(X):- and iterate once more. When presented with task 4, models most likely have to adjust the intermediate state representation to check for the second rule case; as a result Figure 7c can also be interpreted as the lack of abstraction over increasingly complex tasks in the dataset since curriculum learning provides no clear advantage. In other words, the neural models do not seem to learn a reasoning process that is general enough to be compared to existing symbolic systems; consequently we were unable to run them on existing logic program benchmarks or against Prolog.
There have been many attempts to combine symbolic
reasoning with machine learning techniques under the name
neuralsymbolic systems
Following the above mentioned works, Neural Theorem
Provers
Learning similarities between constants can be used to
perform link-prediction tasks
Neural Reasoning Networks can be seen as interpreters
of logic programs as rules can act like instructions. This
perspective reflects on systems such as Neural Program
Interpreters
We presented a new synthetic dataset and provided insights into how machine learning might encompass symbolic reasoning, defined as logic programs using RNN-based iterative neural networks. Fully differentiable models trained end-toend have their inherent disadvantages: they seem to lose track when the number of iterations is increased and the embedding space is limited in capacity. However, such networks might still hold the key to incorporate symbolic prior knowledge into a continuous space by understanding how that embedding space is organised to store symbolic information.
Since such neural networks provide a differentiable but approximate reasoning engine over logic programs, in the future we hope to induce rules using continuous embeddings of logical rules by propagating gradients back to the context. However, initially if possible, a more robust neural reasoning network must be learned, one that is comparable in performance to existing logic-based expert systems.