Deep deductive reasoning is a hard deep learning problem

1.Introduction

Deductive reasoning over formal logics is arguably the central computational task in symbolic Artificial Intelligence (AI) [9]. A given formal logic usually carries a formal semantics that is often model-theoretic and as such defines in mathematically precise terms the notion of logical consequence. In symbolic form, given a logical theory K (in symbolic AI – more precisely in the subfield of Knowledge Representation – often called a knowledge base, i.e., a set of logical formulas over the formal logic), we write K⊧F if F is a logical formula over the same language and F is a logical consequence of K, meaning that F can be derived from K by deductive reasoning.

An important aspect of Knowledge Representation (KR) research is to find correct and scalable algorithms for deductive reasoning over KR-relevant logics. However, the mathematical definitions often do not easily translate into algorithms. Indeed, algorithms for more expressive logics tend to be so involved that they often need correctness proofs. Furthermore, they tend to be of high computational complexity, if the problem of computing logical consequences is at all decidable. Indeed, some prominent logics, such as first-order predicate logic, are not decidable but only semi-decidable, and some higher-order logics, including some non-monotonic logics of importance to KR, are not even semi-decidable [12]. Among the decidable logics are many from the Description Logics family [4] that are relevant for KR-based data management, and some of which have become W3C standards for the Semantic Web research field [20]. Their complexities can be very high, e.g., the OWL 2 DL standard is based on the Description Logic SROIQ and has N2EXPTIME11 worst-case complexity [23]. In this paper we will mostly focus on expressive logics of relevance to KR, i.e., logics expressed over languages with variables such as first-order predicate logic. Propositional logic, which is computationally much more friendly,22 is of course also important for many computer science applications, but less relevant for our interests.

Deep Deductive Reasoning (DDR) [14] refers to the training and then executing of deep learning (DL) systems to perform deductive reasoning. There are several reasons why the study of DDR is a worthwhile undertaking. Fundamentally, DDR presents us with a set of related problems of differing difficulty, at scales that can be chosen arbitrarily, and with mostly easy-to-obtain training data, and thus makes it possible to explore the capabilities and limitations of DL in what is similar to a controlled laboratory setting. A different perspective on the problem is motivated from a cognitive science viewpoint, in that KR and DL can be understood as simple formal abstractions of cognition, respectively, the human brain: And while we humans are capable of performing deductive reasoning, we would like to understand if and how this can be done with DL systems. A third perspective is more applied: DDR, if it could be made to work with high accuracy and at scale, may lead to improvements over conventional deductive reasoning algorithms through better tolerance of errors and noise in the data (which conventional algorithms do not handle well) and to improved reasoning speed (in the light of high computational complexities). At the same time, capturing deductive reasoning in DL systems opens avenues for neurosymbolic architectures that truly combine learning and reasoning, without the need to recourse to hybrid architectures.

The rest of the paper is organized as follows. In Section 2, we will give a brief overview of existing DDR research. In Section 3 we will discuss theoretical limitations on DDR that can be derived from the literature. In Section 4 we report on some of our failed attempts to improve DDR, which we include to emphasize how difficult the problem is, and in order to aid other researchers by reporting on paths that appear to be dead ends. In Section 5 we conclude.

2.Brief literature review

There are a number of particularly important features when assessing DDR approaches and systems:

We note, in particular, that none of the current systems is both generative and able to transfer. Furthermore, scalability is generally below many requirements in practice. The exception may be [54] – however this system makes use of only small TBoxes (which are the actual logical axioms), i.e., only the ABox (essentially, the non-axiom facts) is large.

While it is not our focus herein, we would like to mention that some studies have focused on investigating reasoning within propositional logic. For instance, in [47] efforts were made to fine-tune GPT-2 and GPT-3 to emulate resolution rules applicable to propositional logic programs, and in [18] the issue of entailment within propositional logic is addressed.

Also related is research in automated theorem proving involving DL, which can be categorized into two main groups. Firstly, there are hybrid approaches that combine neural network encodings with conventional deduction methods [28,29,34]. Secondly, there exist fully deep learning-based models such as the one proposed by [45], which presents a DNN architecture customized for automated proof synthesis, estimating the probability of applying an inference rule at each step of the proof. Additionally, in [10,46], a graph neural network-based model is proposed for the classification and resolution of SAT problems.

OVerall it seems fair to say that, at present, research results do not yet meet realistic application requirements, in particular for KR applications.

3.Theoretical limitations

Deductive reasoning problems have a long history as complete problems for complexity classes, and those in knowledge representation tend to possess high complexity. Therefore it is natural to think that DDR is subject to severe theoretical limitations, but is this true?

Deep learning can be studied through several abstract models. The most direct and literal is the analytic model (see e.g., [6,52]), in which neural networks are a class of functions of real variables, studied in terms of approximation, convergence, etc., with computational considerations kept to a minimum. An advantage of this point of view is its ability to see specifics of different architectures that would be washed out in other models, letting us more often compare predictions against empirical results. However, it is not well suited to study hardness in absolute terms: typically one can prove facts such as rapid convergence-in-probability of stochastic gradient descent, or lack thereof, but this only concerns the performance of one algorithm (e.g., stochastic gradient descent) at a time.

The other obvious model is boolean circuit computation [50]. We represent neural networks as discrete functions acting on boolean vectors, and so all considerations are quite different. Typically some proxy such as “majority threshold circuits of constant depth” (TC0 circuits) is used for neural networks [51], which are, after all, structured like big circuits, with inputs feeding forward to outputs, and threshold gates are indeed similar in spirit to neurons. However, a “reduction” is implicit between the neural architecture and the abstraction, which makes differences between architectures invisible.44 The facts that this model represents are different at a more basic level too: phenomena of floating-point representation and rounding error, for example, are implicitly taken into account, which are ignored in the analytic model. Could these differences be purely a priori, and in fact the practical limitations implied by the two systems are similar? The state of the art in both is too undeveloped to know, but we can mention one “coincidence”: in both models, a small fixed number of layers seems to provide a lot of expressiveness. MLPs with one hidden layer can uniformly approximate continuous functions on a compact domain55 [6]. And no one has yet proven that TC0 circuits of three layers do not solve all problems in EXPTIME [51].

The circuit model is more germane to the study of DDR, because deductive reasoning problems are discrete, but there is another issue that bears mentioning. Whereas a Turing machine has a finite number of states, a circuit family, with enough circuits to process inputs of any length, is an infinite one [51] because a different circuit is required for each input length. It is thus possible to decide some nonrecursive languages with circuits. This feature, called “nonuniformity”, is a plague on lower-bound proofs; proving problems too hard for circuits is generally harder than proving them too hard for Turing machines with similar resource bounds. We do not understand whether this reflects a significant phenomenon or just a gap in our knowledge.

When a decision (classification) problem is not in a nonuniform complexity class, such as TC0, this means that no family of small circuits of the appropriate type can perform the classification correctly. Assuming the often-assumed analogy between circuits and neural networks [51], it would say the problem is hard in a way that has nothing to do with training – no matter how well we can train our networks, there is no correct network to be found by training. Therefore we might get better bounds if we modeled neural networks instead by uniform families of threshold circuits, which have an efficient procedure that generates the circuits, a process that is potentially analogous to training. One well-studied notion of uniformity is efficient decidability of the “direct connection language” which fully describes a circuit family,66 but this represents the extent to which a network’s structure has a simple mathematically-regular “plan”; intuitively this has nothing in common with the kind of constructiveness in networks trained by backpropagation.77 For the special case of DDR, we may fall back on a blunter notion: we may model a pair of training algorithm and neural architecture as a circuit family generated by a Turing machine, the action of this Turing machine encompassing both generation of training data and the learning procedure. This model is more appropriate for DDR than for most deep learning problems, since we know how to write a program to generate ground truth in the form of sets of valid axioms. Neural networks conceived this way have serious limitations. For instance: suppose we want to use a polynomial-time88 procedure to train a reasoning network for an EXPTIME-hard description logic problem, such as “ALC subsumption with respect to a general TBox” [39]. Suppose we generate training data deterministically using a reasoner program, and we demand perfect accuracy from the trained network. If we can generate the data in less than exponential time (strictly, time O(2no(1))), then by pipelining the two processes we will end up with a deterministic algorithm that does ALC subsumption testing in less than exponential time, which is impossible. The takeaway is that for hard logic tasks we cannot both learn efficiently and generate quality training data efficiently – at least one of these steps must be a bottleneck.

We have neglected the issue that deep learning is inherently random and fuzzy. Since most known facts about hardness of logic concern exact decision problems, with no provision for error, the easiest type of limitations to prove are those of exactly-correct networks. These results mostly just confirm the intuition that deep learning has to be random or fuzzy. Sometimes, though, results do generalize to the fuzzy case. Suppose we want to train, in polynomial time and from a polynomial amount of data, a network that does SROIQ reasoning with merely approximate correctness.99 Then no polynomial-space procedure can generate our training samples. If it could, then there would be a PSPACE algorithm for SROIQ,1010 which is impossible because SROIQ satisfiability is N2EXPTIME-hard.

For deep learning in general, one might argue that we do not have a computational model for the knowledge in a dataset of arbitrary real-world examples because thinking about the example generator as a Turing machine is misleading – we do not know whether the universe can be modeled as a Turing machine.1111 Even for DDR, perhaps the bottleneck really is just the uninsightful ways we can automatically generate ground truth, and if we trained on example deductions made by human experts we could do better.1212 If this is so, then perhaps we ought to model neural networks as if training data is arbitrary. This approximation made, the only circuit-based limits to their power are non-uniform ones, but there is now no possibility of stochastic models performing better than exact ones, since randomness and error tolerance give no advantage to nonuniform computers.1313 It is almost trivial to prove that 2EXPTIME-hard problems do not have polynomial-size circuits. So SROIQ reasoning is out of reach even with the most ideal training set and unlimited time to train stochastically.

Weaker logics provide more interesting problems. It is widely conjectured, though hard to prove (it implies P ≠ NP), that NP-hard problems do not have polynomial-size circuits. If this is the case, then regardless of our assumptions about training, no neural architecture whose operation, once trained, involves a polynomial number of calculations can solve the SAT problem for Boolean formulas, which are vastly less expressive than e.g., SROIQ.

One pertinent compromise model between uniform and nonuniform is exact learning [2,30], in which circuits are constructed by a Turing machine with query access to the target function, and an oracle that can provide counterexamples for incorrect circuits. From an AI perspective, this corresponds to active learning with ideal data available but limited computational resources. Klivans, Kothari, and Oliveira show [32, Theorem 8] implies1414 that if there exists an algorithm to exact-learn all functions learnable by a particular class of circuits (i.e., an “architecture”) in polynomially many queries, then there are functions computable in almost polynomial time1515 that cannot be represented by this architecture. The takeaway from this is that, insofar as exact learning is a good abstraction, there is a tradeoff between the generalization capacity of an architecture and guarantees of efficient learning, and many deductive reasoning problems are hard enough to bring this tradeoff into play.

Overall, the verdict of theory (as of the time of writing) is that the limitations of deep learning for logic problems are not well understood. Since these problems occur at many levels of the complexity hierarchy, they provide an interesting bellwether for the hardness of deep learning in general. Indeed, all the results we have been able to cite above have been excessively general; if there is something particularly challenging for practical neural systems about reasoning, as compared to other computationally hard tasks, this remains to be explained by future research.

4.Practical hardness

In principle, DDR should represent a deep learning problem that is readily investigated. Using symbolic reasoners it is straightforward to produce vast amounts of training data algorithmically. Given the promises of deep learning as a cure-all for all manner of complex problems, it should be expected that, at least for simple logics, solutions for DDR should be findable without too much hassle. It turns out that this is not the case at all, even when staying within the bounds of the theoretical limitations discussed above. In this section, we report on two of our investigations, and their (relative) failures. Given the frequent emphasis in published research on positive results, we take this opportunity to discuss negative results, i.e., failure to solve DDR in some settings.

4.1.LSTMs for EL+ reasoning

We briefly discuss the investigation reported in detail in [13] regarding the use of LSTMs for EL+ DDR. We have looked at a number of different approaches using LSTMs that naturally lead to generative but non-transferable systems. To already state the result: as reported in [13], we obtained DDR that was just a little bit better than random guessing, but for larger knowledge bases. We now recap in more detail what we investigated.

It was our intention to avoid, as much as possible, embeddings or any distance adjustments that might help the system learn answers based on embedding similarity without first learning the reasoning structure.1616 In fact, a primary feature of our network is its lack of complexity. We take a very simple logic, reason over knowledge bases in that logic, and then extract so-called supports from the reasoning steps, mapping the reasoner supports back to sets of the original knowledge base axioms. This allows us to encode the input data in terms of only knowledge base statements. Essentially, such a support consists, for each reasoning step in a symbolic reasoner, of the set of axioms (in the original knowledge base) that allow to draw the inferences for this reasoning step.1717 Support also provides an intermediate answer that might improve results when provided to the system. We experimented with three different LSTM architectures with identical input and output dimensionalities. One architecture, which we call “Deep”, does not train with support data but has a hidden layer the same size as the supports we have defined. Another architecture, called “Piecewise”, trains two separate half-systems, one with knowledge bases and one with supports from the reasoner.1818 The last system, called “Flat”, simply learns to map inputs directly to outputs for each reasoning step. We will discuss in detail each part of the system in the following sections, then provide some results.

EL+ is a lightweight and highly tractable description logic. A typical reasoning task in EL+ is a sequential process with a fixed endpoint, making it a perfect candidate for sequence learning. Unlike RDF(S), which reasons over instance data in triple format (ABox in description logic terminology [23]), EL+ reasoning occurs on the predicate level (TBox in description logic terminology [23]). Thus we will have to train the system to actually learn the reasoning patterns and logical structure of EL+ directly from encoded knowledge bases. More information about EL+ can be found in [7,31].

LSTMs are a type of recurrent neural network that work well with data that has long-term dependencies [26]. We choose to use an LSTM to learn the reasoning patterns of EL+ because LSTMs are designed to learn sequence patterns. The network is kept as simple as possible to achieve the outputs we require and maximize transparency. For the piecewise system, depicted in Fig. 1 (top), we use two separate flat single LSTMs that have the number of neurons matching first the support shape, and later the output shape. The deep system shown in Fig. 1 (middle) is constructed to match this shape so that the two will be comparable, it simply stacks the LSTMs together so that it can train without supports. We also train a flat system, shown in Fig. 1 (bottom), that has the same input and output shape but lacks the internal supports. We have done this three ways because we can compare the behavior of the systems with support against the flat system as a baseline, and then see whether the piecewise training is helping. All designs treat the reasoning steps as the sequence to learn, so the number of LSTM cells is defined by the maximum reasoning sequence length. We train our LSTMs using regression on mean squared error to minimize the distances between predicted answers and correct answers.

Fig. 1.

Piecewise architecture (top); deep architecture (middle); flat architecture (bottom).

We would like to emphasize the distinction between our method, which we prefer to call an encoding, and a traditional embedding. Our encoding adds no additional information to the names beyond the transformation from integer to scaled floating point number. (It can be directly reversed with a slight loss of precision due to integer conversion.) The semantics of each encoded predicate name with regards to its respective knowledge base is structural in relation to its position in the 4-tuple (just like it would be in an EL+ axiom) and its semantics is not related to the other non-equal predicate names within the same 4-tuple.

Every data set we use has a fixed number of names that it can contain for both roles and concepts, and every concept or role has an arbitrary number of name identifiers. Identifier labels are stripped and the concept and role numbers are shuffled around and substituted with random integers to remove any possibility of the names injecting a learning bias. These labels are remembered for later retrieval for output but the LSTMs do not see them. Knowledge bases have a maximum number of role and concept names that are used to scale all of the integer values for names into a range of [−1,1]. To enforce disjointness of concepts and roles, we map all concepts to (0,1] and all roles to [−1,0). Each of the six possible normalized axiom forms is encoded into a 4-tuple based on the logical encodings defined in Table 2.

To input knowledge bases into the LSTM, we first apply the encoding defined in the previous section to each of its statements then concatenate each of these encodings end-to-end to obtain a much longer vector. For instance, C1⊑∃R1.C2, R1⊑R2 might translate to [0.0,0.5,−0.5,1.0,0.0,−0.5,−1.0,0.0]. This knowledge base vector is then copied the same number of times as there are reasoning steps and stuck together once again along a new dimension. Experiments are repeated hundreds or thousands of times, filling up the tensor that is given to the LSTM to learn. Because some of the randomness can cause ragged data, any tensor dimensions that are not the same length as the maximum are padded with zeros.

Table 2

Translation rules: c = number of possible concept names r = number of possible role names

KB statement		Vectorization
CX ⊑ CY	→	[0.0,Xc,Yc,0.0]
CX ⊓ CY ⊑ CZ	→	[Xc,Yc,Zc,0.0]
CX ⊑ ∃RY.CZ	→	[0.0,Xc,−Yr,Zc]
∃RX.CY ⊑ CZ	→	[−Xr,Yc,Zc,0.0]
RX ⊑ RY	→	[0.0,−Xr,−Yr,0.0]
RX ∘ RY ⊑ RZ	→	[−Xr,−Yr,−Zr,0.0]

As already mentioned (and we will not replicate the results tables from [13]), our attempts failed in so far as we only managed to do a little bit better than a random guesser. Of course this does not mean that the problem is not solvable, but it appears that a-priori reasonable set-ups do not readily solve it.

5.Conclusions

We have presented the state of the art in DDR, discussed theoretical limitations, and argued that (even within the theoretical limits) it is a hard deep learning problem in practice based on our own prior experiences.

For the theoretical limitations, we have shown that very expressive logics are out of bounds (with 100% accuracy), and even NP-complete ones may be out of bounds (depending on how the P vs. NP problem will be addressable eventually). Of course, this does not mean that investigating DDR for NP-complete or harder logics should not be done, but it does mean that any DDR system for such logics will always be approximate; however it can of course still be useful [25,43].

In terms of practical hardness, we note that there is currently no well-performing system even for the comparatively simple polynomial logic EL+. While there is a high accuracy system for OWL 2 RL (which is polynomial in terms of reasoning towards facts, or ABox reasoning), it has low scalability and no transfer or generative ability [27]. For the even less expressive logic RDF(S), we have good systems that are either generative and non-transferable at low scalability [35,36], or are transferable but non-generative at medium scalability [16]. High scalability systems are either of low accuracy [41] or limited logical expressivity ([53] uses large ABoxes but small TBoxes). We have further reported, in Section 4, on some of our failed attempts to improve the state of the art.

As for practical usefulness, it should be mentioned that RDFS is a prominent logic in the context of Knowledge Graphs, Ontologies, and the Semantic Web [20], and that a generative system capable of transfer and scalability up to non-trivial input sizes with high accuracy (say, even inputs of about 106 triples would already find applications – the non-generative transferable system in [16] allows input sizes of 103 triples) could have very significant impact and practical applications in knowledge graph-based data management. In particular, such a system – based on deep learning – would be much more easily combinable with other deep learning systems that perform other tasks relevant to the practice of knowledge graph based data management [21].

Deep Deductive Reasoning at scale, and with logics more expressive than RDFS, would of course open up many more opportunities by providing a path to a deep integration of symbolic formal logical reasoning within deep learning systems [3] – in contrast to approaches that use deep learning and separate symbolic reasoners in more of a hybrid systems fashion requiring clearly defined interactions between the separate components (e.g., [37]), and corresponding mapping between vector and symbolic components.

As such, DDR remains a highly interesting area of research, where practical applications seem within grasp. However we have also seen that the right approaches have not been found yet. To advance, it requires new ideas, and investigations on a broad front, with many different deep learning architectures and approaches.