Natural Language Deduction with Incomplete Information (2022)

Abstract: A growing body of work studies how to answer a question or verify a claim by generating a natural language “proof:” a chain of deductive inferences yielding the answer based on a set of premises. However, these methods can only make sound deductions when they follow from evidence that is given. We propose a new system that can handle the underspecified setting where not all premises are stated at the outset; that is, additional assumptions need to be materialized to prove a claim. By using a natural language generation model to abductively infer a premise given another premise and a conclusion, we can impute missing pieces of evidence needed for the conclusion to be true. Our system searches over two fringes in a bidirectional fashion, interleaving deductive (forward-chaining) and abductive (backward-chaining) generation steps. We sample multiple possible outputs for each step to achieve coverage of the search space, at the same time ensuring correctness by filtering low-quality generations with a round-trip validation procedure. Results on a modified version of the EntailmentBank dataset and a new dataset called Everyday Norms: Why Not? Show that abductive generation with validation can recover premises across in- and out-of-domain settings.

## introduction substantial prior work in domains like question answering @xcite @xcite , textual entailment @xcite @xcite , and other types of reasoning @xcite deals with making inferences from stated information, where we draw conclusions and answer questions based on textual context provided directly to a model. however, a growing body of research studies the problem of reasoning given incomplete information, especially for tasks labeled as commonsense reasoning @xcite . current approaches in these domains often work through latent reasoning by large language models @xcite , with only a few explicitly materializing the missing knowledge @xcite @xcite @xcite . however, making knowledge explicit is critical to make reasoning processes explainable: it allows users to critique those explanations and allows systems to reuse inferred knowledge across scenarios @xcite . the materialization of new knowledge is naturally formulated as abduction: generating an explanation given a premise and a conclusion. abductive reasoning as a text generation task is fundamentally challenging, as it is an underspecified task with a large search space of valid generations, hence why prior work has framed it as a multiple-choice problem @xcite . nevertheless, the freeform generation setting is the one that real-world explainable reasoning systems are faced with. in this paper, we develop an approach that combines abductive reasoning with multistep deductive reasoning. we build on recent discrete search-based approaches that construct entailment filter v pop, sample deduc+ons pop, sample premises abduc+ve fringe deduc+ve fringe t s 4 5 h / l y 4 s w m c m m a x 5 p + c h h 0 f f i 4 n y p n p f n y 5 e k y j 6 k e y 9 l f e y v 4 w e o c m b q s r q s s k u h m c q o 8 r v r e 7 d n x + x + e c x q f 7 3 i r e y d a k 5 d 6 f c o p k l e s j a i k p 5 6 f t r l 6 h 8 s z a x m 1 j z o 9 k t w n 2 t x t k 5 2 n i y m m g l a r 3 s 5 j c y 5 t p e i h b 0 4 g 5 6 6 9 t a w 6 f n 9 2 k 1 w z y s 4 l 7 g n r d a p g x r 2 3 8 j k a r z g j s c g x q 0 i m l t o w t o q 4 p j i r z b g l g s q i z 9 c e d b u m u u c e k y 7 j y w b n m w p o r 1 z t u m i l u 9 m r o k c i r e a p z z 6 u 2 n v y 8 j 9 t m e j / 0 u l p g c e s h h h 1 k z 8 w k c o y z w 3 h l b m s 2 u i b h d l v s 0 i 8 r r x h q x 7 e u c f y u 0 / e b z 2 7 y t u b 9 u t 9 t f w 0 j q m a b s a t u a m w e a a t 8 a i 6 o a s w + n y 0 z d c k 2 o 9 + r j f 0 8 s q q a + u e k 7 b v + v u v 3 x k z c @xmath0,@xmath1 our input is a set of incomplete premise facts and a goal; our algorithm searches forward from the premises and backwards from the goal to build a proof that entails the goal and recovers a missing premise through a combination of deductive and abductive inferences. figure 1 shows an example. to constrain the model's generation, we incorporate a validation criterion to test the consistency of each logical inference. we call this new system adgv (abduction and deductive generation with validation, figure 2 ). at its core, adgv follows a similar heuristic search to @xcite , iteratively generating conclusions and adding them to the search frontier, but incorporates abductive steps (analogous to backward-chaining) to make the search two-sided. we evaluate on a new task variant that requires recovering a missing premise from a subset of textual evidence and a goal. we use two datasets: entailmentbank @xcite and everyday norms: why not?, a new dataset that we construct that requires combining information about situations with general principles. we assess both coverage of held-out premises on our test examples and step validity of the steps used to construct them, thereby establishing the ability of adgv to recover premises as well as construct entailment trees reaching the goal of the original example. although our approach can reconstruct premises with a high validity rate, achieving high coverage has significant headroom for future work. our contributions are: (1) introduction of a new task for natural language understanding, recovering a premise in an underspecified entailment tree, along with a new dataset, everyday norms: why not?; (2) a new abductive step model and adgv inference method, which combines forward and backward search; (3) new validation techniques that improve step validity in these models. ## problem description we study the task of generating a natural language proof tree t that entails a goal g given a set of textual evidence @xmath2. . . x n }. unique to our work, we remove one of the pieces of textual evidence x m creating an underspecified setting where a deduction system operating over stated premises @xcite cannot build an entailment tree capable of reaching the goal. the task is then to prove the goal g while also recovering x m , which requires searching backwards from the goal to generate missing information. an overview of our abductive reasoning system can be seen in figure 2 . note that there is a trivial solution to this problem, which is to immediately assume that x @xmath3, leading to a vacuous proof. there is no easy way to rule out this solution, as it is hard to come up with a first-order principle for what makes an atomic premise. in existing datasets like entailmentbank @xcite , premises can be low-level definitions ("revolving around means orbiting") or more complex process descriptions ("photosynthesis means producers / green plants convert from carbon dioxide and water and solar energy into carbohydrates and food and oxygen for themselves"). other past work @xcite has use large language models to determine atomicity, but this also fails to yield a consistent principle beyond preferring statements that are attested in large web corpora. as a result, we will use our search procedure to iteratively unroll a goal into simpler statements in an attempt to recover the specific premise x m with some tree that we find. we will evaluate according to two criteria. our first criterion is recall of the missing premise at some point along the search process, using a scoring metric e(x ′ i , x m ) ∈ r to determine if a generated premise x ′ i is logically equivalent to x m . our second criterion is validity of the tree that yields x m , judged according to human ratings. ## methods our approach is based on two generative modules called step models. new in this work, we additionally introduce an abductive step model s @xmath4. . . x n , c). this model is meant to "reverse" the behavior of the forward model in a similar fashion as backwardchaining in prolog @xcite . specifically, it takes a conclusion statement c as well as one premise x and generates a hypothesis x ′ . the generated hypothesis, x ′ , constitutes a new piece of information that the step model infers is necessary to make the original conclusion c true. this operation can then be chained repeatedly to uncover more general and abstract information. we find in our work that setting @xmath5. deductive inferences in the domains we consider may be lexically underspecified, but typically represent a clear logical operation. however, abduction does not. an example can be seen in figure 3 : the abductive model can produce multiple valid generations at varying levels of specificity. determining the truth of these generations is extremely challenging as in other work that tries to generate intermediate unstated inferences @xcite @xcite ## everyday norms: why not? to evaluate our method, we need data consisting of entailment trees t as shown in figure 4 . entailmentbank @xcite is the only existing dataset suitable for this evaluation; however, it is limited to the elementary science domain and we found that step models can often elide minor steps such as synonym replacements, making many instances easy to solve. we collect a new english-language dataset called everyday norms: why not? (enwn) describing why an action is or isn't appropriate given a set of circumstances and a set of assumed norms. enwn consists of 100 entailment trees annotated by the first two authors of this paper. each example considers a unique situation, providing an ethical judgement and its justification in the form of an entailment tree. premise statements include both information about a situation as well as ethical norms. intermediate steps are written to be similar in form to those in the entailmentbank dataset, with the exception that all steps have two input statements. examples are given in figure 4 and appendix b. enwn trees are slightly larger than entailmentbank trees, with an average of 4.71 steps in comparison to entailmentbank's 4.26. anecdotally, we note that most steps in enwn cannot be easily elided as they do not involve premises expressing trivial identities, such as "green is a color," which occur often in entailmentbank. ## experimental setup we evaluate our models on the premise recovery task according to the two criteria stated previously, recall of missing premises and validity. recall of missing premises, which we refer to as coverage, is defined using our recovery scoring e(x m , x ′ ) ≥ 0.7. an example only has to produce one tree containing the missing premise to be counted towards the coverage metric. we use human evaluation to evaluate validity. we evaluate on the english-language entailment-bank @xcite test set and our new everyday norms: why not? (enwn) dataset. to control for tree depth, our test examples are produced by slicing each full entailment tree into treelets and removing a single premise from each treelet. slicing trees allows us to create settings of varying difficulty (deeper treelets being more difficult) and since each treelet has at least two premises we can generate many individual examples. for our evaluations in we compare various models, including end-to-end (e2e), deductive only (dg), abductive only (ag), abductive and deductive (adg), and finally our full model, abductive and deductive with validation (adgv). we now proceed to describe these models. ## results as our chief goal is to infer missing premises, we begin with premise recovery (coverage) results, shown for all baselines and our best models across both datasets in ## conclusion in this work, we tackle the generation of missing premise statements in textual reasoning through the use of abduction. we introduce a new system capable of abductive and deductive step generation, which yields inferred missing premises while building a proof showing its reasoning. furthermore, we propose a novel validation method that reduces hallucination and other common failure modes in end-to-end and stepwise searches. future work can improve our system by scaling up the models used, plus using additional notions of validation as discussed in the error analysis. we believe our overall framework can be a promising foundation for future reasoning systems.