Can Transformers Reason in Fragments of Natural Language? (2022)

Abstract: State-of-the-art deep-learning-based approaches to Natural Language Processing (NLP) are credited with various capabilities that involve reasoning with natural language texts. %However, reasoning in this setting is often ill-defined and shallow. In this paper we carry out a large-scale empirical study investigating the detection of formally valid inferences in controlled fragments of natural language for which the satisfiability problem becomes increasingly complex. We find that, while transformer-based language models perform surprisingly well in these scenarios, a deeper analysis reveals that they appear to overfit to superficial patterns in the data rather than acquiring the logical principles governing the reasoning in these fragments.

## introduction the recent success of neural networks in a range of tasks connected with logical inference in natural language is remarkable. foremost among such systems are those employing transformer-based language models @xcite optimised on large corpora in an unsupervised manner @xcite and then further fine-tuned on taskspecific datasets @xcite . however, concerns persist regarding so-called "data-set artefacts" @xcite @xcite . have netural networks really acquired the principles of reasoning with natural language, or are they merely responding to superficial patterns in the data? in fact, two strands of research may be discerned in recent work on natural language inference (nli). the first formulates the central task as follows: given a pair of sentences in some natural language, a premise, p and a hypothesis, h, determine whether p (i) entails or (ii) contradicts (i.e. entails the negation of) h; or (iii) p is neutral with respect to h. for example, the premise a person rides his bicycle in the sand beside the reasoning pattern of interest (e.g. chaining) is this collection of sentences satisfiable or contradictory? ocean is taken to entail the hypothesis a person is on a beach. the primary issue is the possibility of learning such a mapping on the basis of some data set consisting of many such sentence pairs, each tagged with the a 'correct' (i.e. gold standard) label as determined by human judgement, typically obtained by crowd-sourcing. examples include the rte dataset @xcite and the (much larger) @xcite . neural-network models achieve impressive accuracy on this task @xcite . the nature of the challenge here is (deliberately) mixed: on the one hand, solving the nli problem requires a grasp of the meaning of various closed-class words (a, not, . . . ) together with an appreciation of the semantics of the grammatical constructions involved. on the other hand, almost all the entailments or contradictions encountered rely on common sense knowledge (for example, that racing a bicycle involves riding it), which it is the job of the system to acquire. the supposition is that these pieces of commonsense knowledge mediate the entailment of the hypothesis (or its negation) from the premise. the logical basis of the inferences, so reconstructed, is typically straightforward, amounting to simple syllogism-like inferences; but the mediating commonsense knowledge is coded in 'soft' form, matching the approximate, probabilistic nature of natural language inference. the operative notion of inference thus eludes a formal definition @xcite ,ultimately resulting in debatable labels @xcite . thesecond strand of research investigates the ability of neural networks to recognize formally valid entailments in sensu stricto, but nevertheless couched in fragments of natural language. examples include @xcite ; @xcite ; @xcite and @xcite . here the focus is on learning the (potentially complex) inferential patterns inherent in the logical syntax of the closed-class words and grammatical constructions defining the fragment of language under investigation. for example, the premises every doctor who is not a philosopher is a baker, john is a doctor and john is not a baker entail the hypothesis john is a philosopher. no commonsense knowledge is required here: the given premises either entail the given hypothesis formally, or they do not. since entailment in a formally defined fragment of language is a matter of mathematical fact, not human judgement, inferential problems may be constructed artificially, using random sampling over a grammar, with the correct answers determined by an automated theorem prover (atp). the question is not whether neural networks can be trained to mimic human annotators' judgements, but rather, whether they can learn the logical principles governing language in question. note that, because it is formal validity rather than commonsense plausibility that is at issue here, inference tasks of interest typically involve not a single premise p , but rather, a collection of premises. individual sentences seldom yield any non-trivial formal entailments. these two strands of research reflect a difference in motivation. the former aims to understand inferences apparently performed by humans in everyday linguistic settings-inferences which are necessarily messy and approximate in character. from a formal point of view, many of the alleged entailments or contradictions are in fact judgements of probability. thus, for example the premise alice is holding a dog does not, logically speaking, contradict the hypothesis alice is holding a cat, even assuming that no dog is a cat; yet such labellings abound in nli datasets, reflecting the judgements made by (and instructions given to) the human annotators who generate them. by contrast, the second (strictly logical) strand of research is motivated principally by a desire to understand the rule-based character of natural language syntax and semantics, and in particular, by the question of whether a neural network can learn the rules in question. in this paper, we report on a large-scale empirical study to investigate whether transformer-based language models can learn the logical syntax of natural language. specifically, we consider performance on the problem of determining the satisfiability (logical consistency) of sets of english sentences featuring the determiners every, some, no, the negative adverb not, and relative clauses, in the context of a vocabulary of count nouns and transitive verbs. importantly, the sentences in question are drawn from various different fragments of english, each characterized by a particular range of the grammatical constructions investigated. in each case, data sets-both for training and evaluation-are artificially generated in order to test the system's grasp of the underlying logic. figure 1 illustrates the approach, giving an example problem instance for the very simplest of the fragments considered. we find that state-of-the-art deep learning-based approaches achieve impressive performance on this task. however, in-depth analysis of their generalisation capabilities reveals a more nuanced pattern, suggesting a tendency to overfit to the parameters that control the data generation, rather than learning the underlying logical principles. ## fragments of language by a fragment of a natural language, we understand a collection of sentences forming a naturally delineated subset of that language, and equipped with a truth-conditional semantics commanding the assent of its native speakers. for example, consider the fragment of natural language corresponding to the classical syllogistic given to us by @xcite . in its english-language version, it consists of the sentence forms every p is a q no p is a q some p is a q some p is not a q, with schematic variables p and q substituted by common (count) nouns. this fragment, which we here denote s, can be used to formulate examples such as the one shown in figure 1 . for present purposes, we may consider the truth conditions of an english sentence to be given by translation to a formal language such as first-order logic, in a way which uncontroversially reconstructs the operative notion of logical entailment. thus, for example, the sentence forms s correspond to the respective logical forms ∀x(p(x) → ±q(x)) and ∃x(p(x) ∧ ±q(x)), @xmath0. an argument in s is regarded as valid precisely when the first-order translations of its premises entail-in the familiar logical sense-the first-order translation of its conclusion. consider now the argument: some artist hates no beekeeper; every beekeeper hates some artist; therefore some artist is not a beekeeper. this argument is again intuitively valid (though this takes a little thought to see). on the other hand, it cannot be sensibly cast in the syllogistic, because it so obviously hinges on intrinsically relational information. (observe the alternation of subject and object of the verb hates in the two premises.) is there, then, a larger fragment of english in which it might be expressed? take the relational syllogistic, denoted r, to be the fragment of english obtained by adding to s the sentence-forms: no p rs every/any q some p does not r every/any q, where p and q are common count nouns and r a transitive verb. as with s, so too with r: the truthconditions of sentences can be captured by translation to first-order logic in a way which faithfully reconstructs the intuitive notion of validity. for example, "some artist hates no beekeeper" may be rendered as ∃x(artist(x) ∧ ∀y(beekeeper(y) → ¬hate(x, y))), and so on. under these semantics, argument (1) is confirmed as a valid argument in the fragment r. there are other ways to extend the fragment s, of course. one (very modest) such extension is actually featured in the works of @xcite ). let us say that the extended classical syllogistic, denoted s + , is the fragment of english which adds to s the sentence-forms every non-p is a q some non-p is a q no non-p is a q some non-p is not a q, corresponding to the first-order formulas ∀x(¬p(x) → ±q(x)) and ∃x(¬p(x) ∧ ±q(x)). as we might say, s + adds 'noun-level negation' to s. following in the same vein, we can extend r with noun-level negation, yielding sentences such as "no non-carpenter admires any non-artist" and so on. we call this fourth fragment the extended relational syllogistic, denoted r + . again, translation into first-order logic is completely standard. let l be a fragment of some natural language. a set of l-sentences is said to be satisfiable if there is a structure making the logical translations of these sentences true. the satisfiability problem for l, denoted sat(l), is the problem of determining whether a given finite set of sentences of l is satisfiable. provided l is equipped with a mechanism for sentence negation (as are all the fragments considered here), any procedure for solving sat(l) immediately yields a procedure for recognizing logical entailments in l, since an argument is valid just in case its premises together with the negation of its conclusion is not satisfiable. therefore, we have no use for the familiar classification of natural language inference problems as entailment, contradiction and neutral (and still less the four-way classification of @xcite ): the satisfiability problem is as general as we need. as the fragment l becomes more expressive, the corresponding satisfiability problem sat(l) will, in general, become more increasingly difficult. however, as we shall see, the details of the resulting trade-off between expressiveness and ease of inference are rather intricate. the focus of the present paper is whether neural networks can learn to solve problems such as sat(l) for various fragments l such as s, s + , r and r + . we remark that the approach taken here is parallel to that taken with respect to the fragments grl and rcl in @xcite . there are two notable differences, however, firstly, the fragments considered here are, from a grammatical point of view, more basic, and less clearly a natural language version of propositional logic clauses. in particular, grl includes the 'sentence' if carrot and not steak then apples; and even the more natural rcl is limited to the constructions every x who is (not) a y is (not) a z. to allow comparison between this work and the present study we consider the minimal extension of s by means of relative clauses, thus allowing the additional sentence-forms denote this fragment by s r . similarly, denote by s rn the same fragment additionally allowing negative relative clauses, such as "every o who is not a p is a q" and so on. the fragment s rn is actually an extension of rcl. an important motivation for the rather more general approach taken here is that the satisfiability problem sat(l) for various fragments l of english may be studied from a purely complexity-theoretic point of view. thus, for example, it is known that the problems sat(s), sat(s + ) and sat(r) are nlogspace-complete, while sat(r + ) is exp- @xcite . similarly, the satisfiability problems for grl and rcl are easily seen to be nptime-complete, as is the problem sat(s rn ); by contrast, the problem sat(s r ) is ptime-complete (pratt-hartmann, 2014, theorem 7). the question naturally arises as to whether the ability of neural networks to learn to solve these various satisfiability problems correlates with these complexity-theoretic differences. ## random problems in this section we outline the construction of collections of sets of formulas in the fragments s + , r, r + , s r and s rn , in which each generated set is labelled as satisfiable or unsatisfiable. (the fragment s is not interestingly different from s + , and will not be considered in the experiments reported here.)these collections are partitioned into training and evaluation sets, enabling us to test the ability of neural networks to learn to recognise satisfiability under a range of conditions. any sentence in s + translates to a formula having either of the forms ∀x(±p(x) → ±q(x)) or ∃x(±p(x) ∧ ±q(x)). we may thus generate a sentence of s + pseudo-randomly by selecting a universal sentence with probability p u , a negated subject with probability p s and a negated object with probability p ō, and then choosing p and q at random from some collection of n nouns. by carrying out this process s times, we obtain a random set φ of s + -sentences (|φ| = s). for definiteness, we set p @xmath1.5 and p @xmath2.8. in addition, we remove any inconsistent sentences, such as "some p is not a p." in choosing the various parameters, we fix n/@xmath3.8, which, as we have empirically established, keeps the proportion of sat-isfiable instances at roughly 50%. collections of such problem instances are created for various values of s. the ratio n/@xmath4.8 corresponds (for s + ) roughly to the critical region of sat problems studied in @xcite , where it was shown that learning on data from this region is more effective than learning from uniformly sampled data. however, we need to be wary of assuming that such instances are difficult-an issue addressed in section 4. for r + , we proceed similarly, generating s sentences at random over a fixed collection of n nouns and v transitive verbs. every sentence in r + is either a sentence in s + or translates to a formula having one of the forms ∀x(±p(x) → γ) or ∃x(±p(x) ∧ γ), where γ is either ∀y(±q(y) → ±r(x, y)) or ∃y(±q(y)∧±r(x, y)). call sentences in r + \ s + relational sentences. we may thus generate a sentence of r + pseudo-randomly by choosing to produce a relational sentence with probability p r . if we choose to produce a non-relational sentence (i.e. a sentence in s + ), we proceed as above; otherwise a negated verb is chosen with probability p v, a universally quantified γ with probability p uu ; the other parameters, n, v, p u , p s and p o are interpreted as before. by setting p @xmath5, we guarantee that every generated relational sentence has a non-negated subject and a non-negated object, and hence is a sentence of r. by repeating this process s times, we obtain an set φ of sentences in r + (or r). when generating instances of sat(r), we thus set p @xmath6.2, p @xmath7, p @xmath8.5 and p @xmath9.8; in addition, we fix n/@xmath10.6 and v/@xmath11.15, which, as we have empirically established, keeps the ratio of satisfiable to non-satisfiable instances at roughly 50%. likewise, when generating instances of sat(r + ), we set p @xmath12.5, with the other parameters as for r; however, we adjust n/s to 0.64 in order to maintain the ratio of satisfiable to non-satisfiable instances. finally, for fragments with relative clauses, s r and s rn , in addition to the parameters introduced for s + , we control the probability of negated relative clauses by the parameter p r. by setting p @xmath13, and hence is a sentence of s r . we additionally set p ō = 0.5 and p @xmath14.8, and for s rn , we set p @xmath15.5. we empirically establish that setting (n -0.225)/@xmath16.59 yields a probability of satisfiability of approximately 0.5 frag. templates example sentence some carpenter is not a dentist. r all of s and: every/some p rs every/some q. every artist chases some beekeeper. some p does not r every/any q. some beekeeper does not chase any artist. no p rs every/any q. no beekeeper bewitches any artist. ## constructed problems one attractive feature of the fragments s, s + and r is that their satisfiable sets of formulas admit of a simple graph-theoretic characterization. this gives us an additional means of creating data sets comprising challenging problem instances. we illustrate with s. let a set φ of s-sentences be given, and let p 1 , . . . , p n be the common nouns (predicates) occurring in φ. now let v be the set of expressions p i (x) or ¬p i (x) (1 ≤ @xmath17. we call the elments of v literals and let the variables ℓ and m range over v . if ℓ ∈ v , denote by l the opposite literal obtained by adding or removing the negation sign as appropriate. now let e be the set of ordered pairs of literals (ℓ, m) such that φ contains a sentence formalized as either ∀x(ℓ → m) or as ∀x( @xmath18. thus, it can be shown (pratt-hartmann and moss, 2009, sec. 3) that a set of sformulas φ is satisfiable if and only if φ contains no sentence ∃x(ℓ ∧ m) such that either: (i) ℓ ⇒ φ l; this gives us controlled way to generate hard problem instances. consider the fragment s + . we begin by simply constructing a forbidden configuration having a given size, d. to obtain an unsatisfiable problem instance φ of size s, we then add sd random sentences, checking (using a simple algorithm) that doing so does not create any smaller forbidden configurations. to obtain a satisfiable problem instance of size s, we reverse one of the implications in the forbidden configuration, and check that the added sd random sentences do not cause an unsatisfiability. in effect, d is a guaranteed difficulty level; it yields a lower bound on the proof length required to establish unsatisfiability. at the same time, the satisfiable and unsatisfiable instances thus generated are not easily distinguished by any superficial characteristics. we denote the problem sat(s + ) constructed as just described with d in a specified range as sat (s + [•,•] ). thus, for example, in s + [2,6] , unsatisfiable problem instances have 2 ≤ @xmath19. for r, the corresponding characterization of unsatisfiability in terms of forbidden configurations involves several cases (pratt-hartmann and moss, 2009, sec. 4). for simplicity, we generate difficult instances by focusing on just one of these types of forbidden configuration, which we call an ∀∀configuration. we begin by constructing an ∀∀configuration of specific size 6d (for @xmath20. (such a collection of sentences is always unsatisfiable.) to obtain an unsatisfiable problem instance of size s, we add s -6d randomly generated sentences, again checking that the resulting unsatisfiability is due entirely to the forbidden configuration. satisfiable instances are then obtained by reversing one of the implications in the ∀∀-configuration, and checking that this does not lead to unsatisfiability. denote the problem sat(r) constructed as just described with d in a specified range as sat(r •,• ). for example, in r 1,2 , inconsistent problem instances are inconsistent because of ∀∀-configurations of size 6 or 12. it is not possible to characterize sat(r + ) in terms of forbidden configurations in this simple way. as a substitute, we use the proof-lengths of the proofs found by the atp as a rough guide to difficulty. to generate difficult instances of r + , therefore, we first generate random instances as in sec. 3; we then filter out those unsatisfiable in-stances with short proof-lengths (as reported by the atp), and then remove satisfiable instances at random to preserve the proportion of satisfiable instances overall. ## experimental setup in the following study, we investigate whether neural networks, and in particular state-of-the-art transformer-based language models @xcite can learn to perform satisfiability checks on examples representing the selected fragments. first, we investigate whether they can do so in principle, by optimising and evaluating classifiers on training and evaluation data drawn from the same distribution. second, in an attempt to understand whether they reliably learn the underlying logical principles that govern (un-)satisfiability, we evaluate their generalisation capabilities on out-ofdistribution evaluation data. we do so by altering various parameters of the training and evaluation data generation to control the structure of the generated problem instances. more specifically, we cast the problem of determining satisfiability as binary text classification and conduct experiments with three transformer based language models, roberta, xlnet and electra @xcite @xcite .which are further described in the appendix. we employ pre-trained language models because initial experiments showed that these tend to converge faster compared to training from scratch, despite the fact that their pre-training objectives bears little similarity to the task at hand. following @xcite , we represent each problem in plain english text prepended by the special [cls] token as input to the language model. the text is embedded using the language model, and the embedding of the [cls] token, as output by the final layer of the language model, is projected into a two-dimensional space, representing the odds of the problem being satisfiable. during inference, we pick the highest logit as the model's prediction and during training we minimise the cross-entropy loss between the logits and the expected class, thus optimising the parameters of the language model to produce the expected prediction conditioned on the input. we keep the choice of hyper-parameters (detailed in appendix) consistent across experiments. ## results and analysis we report and analyse the results of the conducted empirical study. for all results we measure the error as a confidence interval at α = 0.05, using asymptotic normal approximation and omit reportage for brevity, as all measures are in the range of at most two percent points. we average results obtained for all three language models. transformers perform well on random examples in all fragments. to seek evidence for the first question we train and evaluate separate models on randomly generated problems instances of each of the five fragments. the results are reported the first row of to investigate whether this performance generalises with the size of the problem instances, we generate evaluation sets with 30 ≤ @xmath21. note that we are constrained to problems of the size of up to 512 tokens, as a technical constraint of the pre-trained language model, hence we do not investigate generalisation capabilities to problems beyond 45 (37 for s r , s rn ) sentences. the remainder of transformers are not robust to distribution shifts. moving on to the second question, we investigate whether the optimised models truly pick up the reasoning patterns as intended or rather overfit to their training data as an artefact of the configuration of parameters controlling the stochastic generation. approximating the "hardness" of a problem instance by its proof length l, we find that for all fragments, the overwhelming majority (ranging from 29% in s to 86% in s rn ) of contradictory examples have short proof lengths of 12 or less, indicating that random problems are, in fact, unsatisfiable for trivial reasons which are easy to show (see also histogram in appendix). thus, we collect "hard" examples by (over-) generating a large body of examples and then filtering by proof length and refer to them as random hard problem instances. naturally, in this way we can only capture the hardness of inconsistent examples, therefore the evaluation focuses on those. when comparing the (out-of-distribution) performance of models on "easy" and "hard" nonsatisfiable problem instances with proof length of at least 42 ( transformers seem unable to reliably learn the distinct reasoning patterns. finally, as determining non-satisfiability for the fragments s + and r involves detection of one of a handful of forbidden configurations, we generate data that exposes precisely these forbidden configurations. the four top rows of this reinforces the previous point that these models appear to have learned to identify problems that have proofs with similar structure to those in their training data rather than learning to solve the problem in a more general sense. when we both optimise and evaluate models on the constructed datasets, we find that they are capable of learning these inconsistency patterns well, and generalise to harder problems unseen during training: the roberta model optimised on s + with chain lengths between two and six performs just as well on evaluation data with chain lengths of up to 10 ( ## related work and conclusion the work reported in this paper represents a continuation of various studies carried out on "challenge sets", proposed to investigate the ability of (optimised) neural networks to perform different kinds of reasoning. such studies range from monotonicity entailments @xcite to probing lexical knowledge @xcite to logical connectives @xcite or verb symmetry @xcite . these studies are related to ours, in that they seek to isolate capabilities of interest and perform controlled experiments using synthetic datasets. they have in common that models optimised on crowd-sourced datasets, such as mnli, @xcite , perform poorly on the challenge set data exhibiting the elicited phenomenon, but fine-tuning the optimised model on portions of these data improves the performance. however, as @xcite show, good scores after the fine-tuning probably stem from the fact that the investigated model has learned to adapt to the regularities of the challenge set rather than learning a general notion of the investigated phenomenon. our analysis is similar: transformerbased neural networks perform well on randomly generated data, but this performance is brittle, and the models overfit to the problem space as set out by the dataset generation method. they do not generalise well to examples outside of that space, suggesting that they do not generalise systematically @xcite , i.e. they struggle to identify a finite set of rules and to apply them repeatedly. similar to our findings, research on systematic generalisation suggests that neural net-works tend to generalise without systematicity in supervised learning scenarios @xcite @xcite , although these studies, unlike ours, did not concern pre-trained models. one might argue that it is unfair to expect a statistical model that relies on correlations to learn patterns that are not obviously present in the data. however, it seems that such claims are being made in the literature @xcite . while we observe that models optimised on constructed examples generalise well to harder problems unseen during training, we also show that this capability appears not to transfer to examples that are only superficially different. thus, in our experiments, similar to @xcite , we find that the optimised models are not able to reliably disentangle and acquire the different reasoning patterns required to successfully complete the task of determining satisfiability. our study highlights one of the issues with empirically postulating neural networks various capabilities by means of good performance on challenge sets. they have only negative predictive power @xcite : while low performance indicates the lack of a capability, the converse does not necessarily hold. this can be taken as a motivation to develop formal verification methods for neural networks @xcite , or investigate worst-case bounds for different phenomena @xcite . our formulated task naturally allows us to expand the scope of the controlled experiments: for example, by increasing the closed-class vocabulary. another possible avenue is to focus on improving the systematic generalisation of neural approaches, for example by providing the formulas required to prove that a set of sentences is unsatisfiable as additional supervision signal, or by relying on modular or model-based approaches @xcite .