Symbolic logic allows practitioners to build systems that perform rule-based reasoning which is interpretable and which can easily be augmented with prior knowledge. However, such systems are traditionally difficult to apply to problems involving natural language due to the large linguistic variability of language. Currently, most work in natural language processing focuses on neural networks which learn distributed representations of words and their composition, thereby performing well in the presence of large linguistic variability. We propose to reap the benefits of both approaches by applying a combination of neural networks and logic programming to natural language question answering. We propose to employ an external, non-differentiable Prolog prover which utilizes a similarity function over pretrained sentence encoders. We fine-tune these representations via Evolution Strategies with the goal of multi-hop reasoning on natural language.   This allows us to create a system that can apply rule-based reasoning to natural language and induce domain-specific natural language rules from training data. We evaluate the proposed system on two different question answering tasks, showing that it complements two very strong baselines – BIDAF (Seo et al., 2016a) and FASTQA (Weissenborn et al.,2017) – and outperforms both when used in an ensemble. We consider the problem of multi-hop reasoning on natural language input. For instance, consider the statements Socrates was born in Athens and Athens belongs to Greece, together with the question Where was Socrates born? There are two obvious answers following from the given statements: Athens and Greece. While Athens follows directly from the single statement Socrates was born in Athens, deducing Greece requires a reader to combine both provided statements using the knowledge that a person that was born in a city, which is part of a country, was also born in the respective country.Most recent work that addresses such challenges leverages deep learning based methods BID41 BID29 BID38 BID30 BID18 BID21 BID17 BID8 , capable of dealing with the linguistic variability and ambiguity of natural language text. However, the black-box nature of neural networks makes it hard to interpret the exact reasoning steps leading to a prediction (local interpretation), as well as the induced model (global interpretation).Logic programming languages like Prolog BID46 , on the other hand, are built on the idea of using symbolic rules to reason about entities, which makes them highly interpretable both locally and globally. The capability to use user-defined logic rules allows users to incorporate external knowledge in a straightforward manner. Unfortunately, because of their reliance on symbolic logic, systems built on logic programming need extensive preprocessing to account for the linguistic variability that comes with natural language BID23 .We introduce NLPROLOG , a system which combines a symbolic reasoner and a rule-learning method with pretrained sentence representations to perform rule-based multi-hop reasoning on natural language input.1 Like inductive logic programming methods, it facilitates both global as well as local interpretation, and allows for straightforward integration of prior knowledge. Similarly to deep learning based approaches, it can be applied to natural language text without the need to transforming it to formal logic.At the core of the proposed method is an external non-differentiable theorem prover which can take similarities between symbols into account. Specifically, we modify a Prolog interpreter to support weak-unification as proposed by BID39 . To obtain similarities between symbols, we utilize sentence encoders initialized with pretrained sentence embeddings BID28 and then fine-tune these for a downstream question answering task via gradient-based optimization methods. Since the resulting system contains non-differentiable components, we propose using Evolution Strategies (ES) BID9 as a gradient estimator BID47 for training the systemenabling us to fine-tune the sentence encoders and to learn domain-specific logic rules (e.g. that the relation is in is transitive) from natural language training data. This results in a system where training can be trivially parallelized, and which allows to change the logic formalism by simply exchanging the external prover without the need for an intricate re-implementation as an end-to-end differentiable function.In summary, our main contributions are: a) we show how Prolog-like reasoning can be applied to natural language input by employing a combination of pretrained sentence embeddings, an external logic prover, and fine-tuning using Evolution Strategies, b) we extend a Prolog interpreter with weak unification based on distributed representations, c) we present Gradual Rule Learning (GRL), a training algorithm that allows the proposed system to learn First-Order Logic (FOL) rules from entailment, and d) we evaluate the proposed system on two different Question Answering (QA) datasets and demonstrate that its performance is on par with state-of-the-art neural QA models in many cases, while having different failure modes. This allows to build an ensemble of NLPROLOG and a neural QA model that outperforms all individual models. We have developed NLPROLOG, a system that is able to perform rule-based reasoning on natural language input, and can learn domain-specific natural language rules from training data. To this end, Figure 3 : Example proof trees generated by NLPROLOG. Each of the two trees shows an application of a transitive rule, the first for the predicate developer and the second for the predicate country. The rule templates are displayed with the most similar predicate. Note the noise introduced by the Open IE process, e.g. QUANT_0_1 and that entities and predicates do not need to match exactly.we have proposed to combine a symbolic prover with pretrained sentence embeddings and to train the resulting system with Evolution Strategies. We have evaluated NLPROLOG on two different QA tasks, showing that it can learn domain-specific rules and produce predictions which complement those of the two strong baselines BIDAF and FASTQA. This allows to build an ensemble of a baseline and NLPROLOG which outperforms all single models.While we have focused on a subset of First Order Logic in this work, the expressiveness of NL-PROLOG could be extended by incorporating a different symbolic prover. For instance, a prover for temporal logic BID27 ) would allow to model temporal dynamics in natural language and enable us to evaluate NLPROLOG on the full set of BABI tasks. We are also interested in incorporating future improvements of symbolic provers, Open IE systems and pretrained sentence representations to further enhance the performance of NLPROLOG. To study the performance of the proposed method without the noise introduced by the Open IE step, it would be useful to evaluate it on tasks like knowledge graph reasoning. Additionally, it would be interesting to study the behavior of NLPROLOG in the presence of multiple WIKIHOP query predicates. else if x is f (x 1 , . . . , x n ), y is f (y 1 , . . . , y n ), and f ∼ f ≥ λ then S := S ∧ f ∼ f return unify(x 1 :: . . . :: x n , y 1 :: . . . :: y n , θ, S ) end else if x is p(x 1 , . . . , x n ), y is p (y 1 , . . . , y n ), and p ∼ p ≥ λ then S := S ∧ f ∼ f return unify(x 1 :: . . . :: x n , y 1 :: . . . :: y n , θ, S ) end else if x is x 1 :: . . . :: x n and y is y 1 :: . . . :: y n then (θ , S ) := unify(x 1 , y 1 , θ, S) return unify(x 2 :: . . . :: x n , y 2 :: . . . :: y n , θ , S ) end else if x is empty list and y is empty list then return (θ, S) else return (failure, 0) fun unify_var (v, o, θ, S) if {v/val} ∈ θ then return unify(val, o, θ, S) else if {o/val} ∈ θ then return unify(var, val, θ, S) else return ({v/o} + θ, S) Algorithm 1: The weak unification algorithm in Spyrolog without occurs check A.2 RUNTIME OF PROOF SEARCHThe worst case complexity vanilla logic programming is exponential in the depth of the proof BID34 . However, in our case this is a particular problem because weak unification requires the prover to attempt unification between all entity/predicate symbols.To keep things tractable, NLPROLOG only attempts to unify symbols with a similarity greater than some user-defined threshold λ. Furthermore, in the search step for one statement q, for the rest of the search, λ is set to λ := max(λ, S) whenever a proof for q with success score S is found. Due to the monotonicity of the employed aggregation functions, this allows to prune the search tree without losing the guarantee to find the proof yielding the maximum success score. We found this optimization to be crucial to make the proof search scale for the studied wikihop predicates.
We introduce NLProlog, a system that performs rule-based reasoning on natural language by leveraging pretrained sentence embeddings and fine-tuning with Evolution Strategies, and apply it to two multi-hop Question Answering tasks.
{"src": "scitldr-AIC_train", "paper_id": "ByfXe2C5tm"}