Learning Symbolic Rules for Reasoning in Quasi-Natural Language
Authors: Kaiyu Yang
Jia Deng
Venue: ICLR 2022 Submitted (2022)

Abstract: Symbolic reasoning, rule-based symbol manipulation, is a hallmark of human intelligence.  However, rule-based systems have had limited success competing with learning-based systems outside formalized domains such as automated theorem proving. We hypothesize that this is due to the manual construction of rules in past attempts. In this work, we ask how we can build a rule-based system that can reason with natural language input but without the manual construction of rules. We propose MetaQNL, a "Quasi-Natural" language that can express both formal logic and natural language sentences, and MetaInduce, a learning algorithm that induces MetaQNL rules from training data consisting of questions and answers, with or without intermediate reasoning steps. Our approach achieves state-of-the-art accuracy on multiple reasoning benchmarks; it learns compact models with much less data and produces not only answers but also checkable proofs.

Under review as a conference paper at ICLR 2022
LEARNING SYMBOLIC RULES FOR REASONING IN QUASI-NATURAL LANGUAGE
Anonymous authors
Paper under double-blind review
ABSTRACT
Symbolic reasoning, rule-based symbol manipulation, hallmark of human intelligence. However, rule-based systems have had limited success competing with learningbbased systems outside formalized domains such as automated theorem proving. We hypothesize that this is due to the manual construction of rules in past attempts. In this work, we ask how we can build rule-based system that can reason with natural language input but without the manual construction of rules. We propose MetaQNL, a "Quasi-Naturaa" language that can express both formal logic and natural language sentences, and Metalnduce, learning algorithm that induces MetaQNL rules from training data consisting of questions and answers, with or without intermediate reasoning steps. Our approach achieves state-of-the- art accuracy on multiple reasoning benchmarks; it learns compact models with much less data and produces not only answers but also checkable proofs.
INTRODUCTION
Symbolic caaooning--ule-aane symbol manipulation-iss a core component of human intelli- gence (Mercier & Sperber, (017). It has been core part of computer science research, and has achieved significant success in domains such as software verification (Darvas et al., (2055) and theorem proving (Kovács Voronkov 2013) McCune [997). However, such success has been restricted to domains amenable to rigid, precise formalization. It remains a challenge how to translate such success into "informal" domains such as reasoning with common sense knowledge and natural language input. Prior attempts to build rule-based systems, which rely manually constructed rules, have achieved limited success and tended to produce brittle systems.
Deep learning provides attractive alternative that easily sidestep the question of representation. deep network can be trained to perform a reasoning task by directly predicting the answer without explicit symbol manipulation (Clark et al. 2020). However, deep networks can require large amount of training data and can suffer from poor generalization. More importantly, unlike symbolic systems, deep network is black box that is hard to interpret, inspect, and verify. Such lack of interpretability can be undesirable in certain applications, especially those critical to safety and security.
In this work, we ask how to build rule-based system that reasons symbolically but can work with natural language and handle domains difficult to formalize. Such a system would perform reasoning by explicit symbol manipulation based on known rules, therefore more interpretable and verifiable, but at the same time flexible enough to handle natural language input.
At a glance, this may appear a large departure from the conventional wisdom that suuning-based sys- tems, particularly deep networks, are far superior to rule-based systems, as history has demonstrated repeatedly. However, we hypothesize that this conventional wisdom is incorrect because it assumes false dichotomy between using learning and using rules; rule-based systems underperformed not because they were rule-based, but because hypothesize learning rules from data is key to building effective rule-based systems, but it may require a different kind of learning than gradient descent.
difficult to construct rules manually. Further, we
The goal of this work is thus to develop method that automatically learns symbolic rules from data to enable rules based reasoning with natural language. This poses two main questions. First, what is the system of rules-thh basic structures that define what symbols and manipulations allowed-

---

Under review as a conference paper at ICLR 2022
If something is strong, then likes cats
sosmething (X), then it
The elephant is big
[A] is DX]
elephant likes cats
[X]
[A] is [Y]
[A] [
elephant
things are [4]
The elephant strong
[A] [2]
Big tall things are strong
Figure 1:
An example proof with 4 assumptions, 1 goal, and 2 rule applications. Each rule have multiple premises and one conclusion. Both the premises and the conclusion have variables that bind to concrete sentences when the rule is applied.
that it is compatible with not only formal logic but also natural language? Second, what is the learning algorithm that induces a set of rules from training data?
In this work, we take initial steps toward answering both questions. We propose MetaQNL, formal symbolic system we call a "Quasi-Natura" Language", which is compatible with not only rigorous logical inference but also natural language expressions. We also propose Metalnduce, a learning algorithm that induces MetaQNL rules from training data that consists of questions and answers, with or without intermediate reasoning steps.
Meta Symbolic System in Quasi-Natural Language. In MetaQNL, sentence is se- quence of words and variables ("The elephant is [X]"). They also include ordinary En- glish sentences without variables. A rule consists of multiple sentences
its premises ("The e elephant is [X]", "If something is [X] then it [Y]") and one sentence as its conclusion ("The elephant [Y]"). When applying the rule in reasoning, variables substi- tuted with concrete sentences ([x] - st stng,,, [Y] + 1 like cats). Therefore, rules capture abstract knowledge that is independent of specific instances the above rule holds whether [Y] is "likes cats" or "is sleepy". Such abstraction is essential for reasoning in both humans and machines (Marcus & Davis 2020).
Fig. illustrates how sentences and rules are used in reasoning. Starting from known sentences (assumptions), we apply rules to derive new sentences until the goal is reached. At each step, we substitute the variables in a rule with concrete sentences. This process resembles Metamath (Megill Wheeler, 2019), formal language developed for formalizing mathematical proofs, where each step also consists of selecting theorem and instantiating it with suitable substitution. So refer to the reasoning process as theorem proving and the result in Fig. I as a proof. It is worth noting that reasoning in MetaQNL is interpretable by design: it is transparent about what rules are assumed; it produces not only an answer, but also a proof that can be mechanically checked against the rules.
Assumptions and the goal are usually given when applying our system to specific task. To solve the task, two issues remain: (1) Rule induction: What is the set of rules? (2) Theorem proving: How to apply the rules to find a proof? Theorem proving has been studied extensively in classical Al (Robinson& & Voronkov 2001) and more recently with deep learning (Alemi et al. 2016 Yang & 2019 | Bansal et al.] 2019), and we can adapt existing algorithms such as forward chaining and backward chaining (Russell & Norvig 2002). In this work, we simply use existing provers and focus instead on the more challenging problem of rule induction.
MetaInduce: Algorithm to Learn MetaQNI. Rules. Rule induction be formulated discrete optimization problem that seeks minimum set of rules that are consistent with training examples. Note that it important to seek small number of rules because we always have trivial solution that consists of one rule per example but is unlikely to generalize. This optimization is challenging due to the discrete, combinatorial search space.
We introduce Metalnduce, general method for learning MetaQNL rules. It encodes the problem as a maximum satisfiability (MAX-SAA SAT) problem, which can be solved efficiently by off-the-shell solvers (De Moura & Bjömnrr 2008). Our method consists of 3 steps. First, given training example, a rule proposer proposes a set of concrete rules (rules without variables) as candidates. This set can be overcomplete and inaccurate. These rules used to prove the example using existing provers chaining. Second, we generate abstract rules from concrete rules via a
such as forward/backwe symbolic procedure called anti-unification (Plotkin 1970, Kutsia al. 2014). Third, we encode the proof paths in MAX-SAV and solve for subset of all rules using a MAX-SAT solver.
Overview of Results. We benchmark our method on 2 tasks: learning compositional instructions and logical reasoning. For learning compositional instructions, our method not only achieves 100% accuracy two standard benchmarks: MiniSCAN (Lake al. 2019) and SCAN (Lake & Baroni
2

---

Under review as a conference paper at ICLR 2022
2018), but also recovers precisely the ground truth rules. For logical reasoning, method achieves state of the art on the RuleTaker dataset (Clark et al.) (2020). Compared to existing methods, our approach learns compact models with much less data, and produces not only answers but also checkable proofs. On RuleTaker, our approach learns a model that has only 2869 symbols but is competitive with prior approach that uses neural network with 11 billion parameters.
RELATED WORK
Symbolic reasoning. Symbolic reasoning has been studied extensively in classical AI, such as theorem proving (Kovács & Voronkov 2013 Robinson & Voronkov 200T). An open problem is to perform symbolic reasoning in domains without a natural formalization, such as natural images or texts. One common approach is to manually construct a formal system (e.g., based on first-order logic with manually defined functions and predicates), then perform semantic parsing to translate images or texts into formalized statements as input a reasoning module operating clean formal world.
For example, to judge whether one statement implies another, Mineshima et al. (2015) use semantic parser to convert both statements into higher-order logic (with predefined predicates). and then run an automated theorem prover. Semantic parsing is still far from reliable; therefore, researchers have developed techniques for learning it jointly with the reasoning module (Mao et al.) [0188] Saparov & Mitchell |021] Dai et al. 2019 Li et al. 2020). In contrast, our approach does not require semantic parser, because rules in MetaQN are directly applicable to natural language.
Natural Logic (McAllester & Givan 1993 MacCartney & Manning 2007: Angeli et al. 2016) is class of symbolic systems defined using the syntax of natural language, bypassing semantic parsing. Compared our system, Natural Logic is more specialized because it is a specific logic committed to a set of predefined rules (namely seven set-theoretical relations), which restrict the type of reasoning it can perform to monotonicity reasoning (Icard III & Moss] 2014). In contrast, our system has no such restrictions because is not specific logic but a meta leta-language with minimal structure such that it can instantiate various types of reasoning, just as MetaMath is a meta-language that can describe a variety of mathematical logics (Megill & W Wheeler 2019).
None of these works discussed so far learn rules from data; they instead use a predefined formal system that is already specialized and already encodes substantial amount of prior knowledge. In contrast, MetaQNL is almost "knowledge- free" in the sense that it imposes the weakest possible structure on the permitted rules and lets the specific rules emerge from data through learning.
Reasoning with neural networks. Neural networks can perform "soft" reasoning the space of continuous vectors without manipulating discrete symbols explicitly. Prior works have used transformer-basee
(Vaswani et al., 2017) language models for soft reasoning (Polu & Sutskever 2020; Saha et al. 2020 Tafjord et al. 2020 Gontier et al. 2020 Talmor et al. 2020). CClar et al. (2020) finetune a pretrained transformer to classify whether the goal is provable from the assumptions, encoding them as sentences in constrained natural language. (Saha et al. (2020) and Tafjord et al. (2020) go one step further to generate proofs in addition to yes/no answers. Bostrom et al. (2021)
generate conclusions from premises in unconstrained natural language.
Instead of using a generic transformer, researchers have also added inductive biases to the neural archi- tecture. Many are inspired by symbolic reasoning and are often called neuro-symbolic architectures. Rocktäschel & Riedel (2017) introduce Neural Theorem Provers (NTPs). Given the assumptions and the goal in first-order logic, they use backward chaining to recursively construct a neural network. However, NTPs only work for formalized inputs and do not scale due to exponentially many proof paths in backward chaining. |Weber et al.] (2019) extend NTPs to natural language by extracting symbols from sentences using an off-the-shelf named entity recognizer. Minervini et al. (2020) make NTPs more scalable by dynamically pruning unpromising proof paths backward chaining.
Researchers have also attempted to embed symbolic structures such as logic formulas into continuous vectors while preserving logical operations (Grefenstette/ 2013 Kathryn & Mazaitis 2018 Lee et al. [016,|Schaar al. 2019). For example, tensor product representations (TPRs) (Smolensky 1990) represent symbols as tensors and perform variable binding/unbinding via tensor operations such as inner/outer product. Dong et al. (2018) propose Neural Logic Machines (NLMs) a neuro-symbolic architecture based on continuous approximation of logical inference. Predicates are represented as tensors; rules are neural operators that map tensors to tensors.
3

---

Under review as a conference paper at ICLR 2022
Cingillioglu & Russo 22200) propose an end-to-end neural architecture called unification networks to learn rules with variables from concrete examples. However, their system of rules is significantly less general than ours: their variables can only bind to a single word, whereas our variables bind to arbitrary sentences. In addition, their system does not support multistep chained reasoning. All reasoning is done in a single step: producing a conclusion in the form of an answer ("yes/no", number, etc.) given a number of premises consisting of a question and a set of supporting facts.
Unlike these prior works, we learn symbolic rules instead of weights in neural network. Further, during inference, we generate symbolic proofs whose correctness with respect to the induced rules guaranteed and can be mechanically checked. [Saha et al. (2020) and Tafjord et al. (2020) also generate proofs, but their proofs are natural language texts whose correctness is neither guaranteed nor mechanically checkable- their approach trains neural networks to directly predict both answers and proofs, but does not expose system of rules against which proof can be checked.
Rule induction. Inductive logic programming (ILP) learns rules in first-order logic programs such as Prolog and Datalog (Plotkin, 1972 Muggleton [991] Cropper & Dumančić] (020). Extending it to natural language is non-trivial -arttiivillpprriilllly due to the need for predefined ontology of objects and predicates, as well as perfect semantic parser, both of which are infeasible. Unlike ILP, we learn rules in MetaQNL, which can express not only logic programs but also natural language sentences. And our experiments show that MetaQNL can solve tasks that are not easily solvable by ILP.
For learning rules, our MctaInduce algorithm draws inspiration from existing ILP approaches. They encode proofs either boolean satisfiability problem solvable by off-the-shelf SAT solvers (Raghothaman et al. 2019) or a differentiable function amenable to gradient descent (Yang) al. 2017: Evans & Grefenstette 2018 Si et al.) 2019). Compared to these approaches, our rule space is different and more complex. Our rules consist of sentences with variables, whereas rules in ILP are typically Horn clauses in first-order logic. Further, ILP often imposes strong syntactic con- straints on what rules are valid, e.g., using rule templates (Evans & Grefenstette/ 2018 Raghothaman al. 2019). or restricting to binary predicates (Evans & Grefenstette 2018). These constraints are critical to good performance but are domain-dependen and difficult to get right (Cropper & Dumančid 2020). Over-constraining the rule space makes the system less expressive, less generally applicable, and more brittle in the presence of noise. Another difference is that we minimize the number of rules in order to generalize, which is unnecessary for ILP due to stronger syntactic constraints.
Our space of rules includes a rich hierarchy from abstract rules to concrete rules, making the search space much larger. In contrast, most ILP works assume function-free first-order logic such as Datalog. Their variables can only be instantiated with concrete entities, making their rule space much simpler.
RNNLogic (Qu et al. 202T) learns first-order rules for knowledge base completion. They generate rules using RNNs, which is feasible because they require that rules can be expressed as a sequence of predicates. The strong syntactic constraint makes it less suitable for more general reasoning. Beyond first-order logic, Nye et (2020) learn rules for a string rewriting system. MetaQNL is more general because it can be applied to not only string rewriting but also other forms of reasoning (see Sec. 5
3 METAQNL: A SYMBOLIC SYSTEM IN QUASI-NATURAL LANGUAGE
MetaQNL. quasi-natural because it has formal syntax compatible with natural language. Like in natural language, sentence in MetaQNL is simply sequence of tokens. There are 3 different types of wokess-words, variables, and special symbols. Taking the sentence "$FALSES The elephant
likes [x]" as example, "The", "elephant" and "likes" are words. MetaQNL treats words as symbols and does not assume any prior knowledge about their meaning. " [[x]" is a variable-2 a placeholder that binds concrete sentences in reasoning. "$FALSE$" is special symbol. They are useful for encoding the structures of specific tasks, which will become more clear in Sec. 5 In this paper, we delimit special symbols with $. Sentences without variable are called concrete sentences, e.g., "$FALSEE The elephant likes catss".
Definition (Sentence). Let Ew, E.,, E, be vocabularies of words, variables, and special symbols respectively; they disjoint and countable. Let Σ = En U U. U E.. then any t E E is token. A sentence s = (t1, tn) E Σx is a non-empty sequence of tokens. concrete sentence is a sentence without any variable, ie.., Vi, l4 & E,..
4

---

Under review as a conference paper at ICLR 2022
MetaQNL expresses permitted reasoning steps through rules. A rule has multiple sentences as its premises ("The elephant "x]","I scmething [X] then it [X]") and one sentence as the conclusion ("The elephant [Y]"). Intuitively, the conclusion should follow from the premises regardless of what values the variables take. Concrete rules are rules without variables.
Definition 2 (Rule). rule takes the form of pi:p.i....i T C, where pL, pı,P2,.... .2....................... PP E Ex are premises, and E Σx is the conclusion. It is concrete all premises and the conclusion are concrete.
In reasoning, we instantiate rules with concrete rules by substituting all variables with concrete sentences. Given the rule 11 = "The elephant [x]; If scmething [x], then it [Y] }- The elephant [Y]", we can instantiate with the substi- tution [[X] + is strong, [Y] + likes cats), deriving the concrete rule r2 "The elephant is strong; If something is strong, then it likes cats + The elephant likes cats". In such cases, we say 11 is more general than r2.
or vice versa, r2 an instance of rı.
Definition 3 (Substitution). Let Et, U be the set of sentences with only words and variables (without special symbols). A substitution a is a function from Σn to Σt Substitutions can be extended be functions tokens, sentences, and rules. Given token t E, applying the substitution a produces a sentence ot.
ol s((t) itt E.: It. it E E..
(o(t)
Given sentence = (t1, t2.,t,..... .ts....,,,,,,,, ),), applying a produces as (ot1, r Prip2i.... ........... .P + c, applying a produces or = op::oppi........... opn + ac.
Given rule
We are abusing notations to treat a token and a single-token sentence interchangeably. Also, (81, 82,..., 8n) denotes concatenation when are sentences. Substitution is defined as a func- tion on all variables E,, but in practice it only involves a few. For example, the substitution is strong, [Y] likes cats) only involves two variables. In such cases, we think of it as being the identity function for other variables, c.g., or [2] = [2]. This convention makes it easier composite substitutions as function composition.
[[X]
As in the example before, applying a substitution to sentences/rules makes them more specific. introduces partial order among sentences/rules. It is straightforward to verify that the relation S defined below is a partial order. We leave the proof to Appeeddix
Definition 4 (Partial order among sentences and rules). Let $1 and be two sentences, is an instance of 82 (denoted by 81 S 82) if and only if there exists a substitution a such that 81 082- In this case, we also say is more general than $1, Similarly, given two rules and r2, is an instance of r2 (or T2 more general than T1, denoted by r1 S T2) if and only if Ba, r1 or2-
subtlety in the definition is judging whether two rules are equal. For a MetaQNL rule. premises are unordered, and variable renaming does not matter. In more jargonized words, rule equality is defined modulo premise reordering and a-conversion.
In reasoning (Fig. D.. the prover is given set of rules M, multiple concrete sentences A as assump- the goal. It iteratively instantiates concrete rules from M and applies
tions, and one sentence them to generate a proof g. Similar to Prolog, 9 may have variables (The elephant [X]). ). and the prover succeeds if it proves any instance of (E.g.. The elephant likes vegetables).
Definition 5 (Proof). A proof P = EV, is a directed acyclic graph whose vertices V are concrete sentences or concrete rules. For each concrete rule P1: Pn F c V, must satisfy two conditions: (I)r connects to its conclusion E V via an edge (r, E E; (2) For each premise Pi. we have p. E V and (pi,r) E E. Besides these edges, there cannot be any other edge in E. Also, there can be multiple sentences without inbound edges (the proof's 's assumptions), but there is only one sentence without outbound edges (the proof's ss goal).
( (Theorem proving). Given a set of rules M (r1, r2....,rkk concrete sentences A {a1, 02...., On } as assumptions, and sentence g as the goal. The theorem prover tries find a proof P such that: (1) P's assumptions are A. (2) P's goal is an instance of g. (3) Every rule r in P is instance of rule in M.
Definition 6
5

---

Under review as a conference paper at ICLR 2022
4 METAINDUCE: LEARNING METAQNL RULES FROM DATA
Problem setup and loss function. Rule induction is a machine learning problem where the model consists of rules rather than continuous weights. The problem setup is familiar: Given training set Dusin and a test set Dust, the goal is to use Durin find a model that performs well not only on Dusin itself but also on Dust- For MetaQNL specifically, the training set Duain = {Durin D Pusinn consists of a set of provable examples Dit and a set of unprovable examples Dunin They both contain training ( examples in the form of 9.). where A; is set of assumptions and 9: is the goal. A model M is consistent with a provable example (A,.
Ditain if go is provable from A, using rules in M. Similarly, M is consistent with an unprovable example (Ai, gi) E "D 'D if 9: cannot be proved from A, In other words, provable examples are positive examples demonstrating sound logical inference, whereas unprovable examples are negative examples demonstrating unsound inference.
Given only Danin. we need to find a model consistent with as many examples in Die as possible. However, is not sufficient to optimize the consistency with training data, because there trivial model that performs perfectly in training but fails in testing one rule per example. That is, given example (A,.)) 9t) E iainn if A; {a1, 02,.................... ... as ). it provable using the rule 01; a2; ag gi-
Thus we need to penalize the model complexity. While other choices are possible, here we measure model complexity as the number of rules. We minimize loss function that evaluates both model complexity and consistency with training data:
[(M) |M (t,, A- D mman:
where [M] is the number of rules; (MM, D and (MM, Driin) are the number of prov- able/unprovable examples consistent with M respectively. A and X are hyperparameters control- ling the trade-off between three terms.
The optimization problem is challenging. Given M. even a single evaluation of L(M) is computa- tionally expensive: [M is trivial, but (M, Pittin) and ([M, Punin) require running the prover on all training examples. Furthermore, it is much harder to find the optimal M due to the combinatorial and non -on-differentiabee search space. We introduce Metalnduce, a general method for learning rules in M by encoding Equation aa maximum satisfiability (MAX-SAT) problem, which can be solved efficiently by off-the-shelf solvers.
Algorithm 1: Metalnduce: A general method for learning MetaQNL rules from data.
Input :Training data Dirain = {(A,; ):)) A; is set of assumptions; 9i is the goal.
Output:A AA model M consisting of a set of rules
M 4 Ø
for j < to mam_mmppppppppppppp saa_epoohs do for i 4 1 to n do candidates
prropose_rules(pmiine prove (As Dr. candidates M)
rules + abstract_rules ()
M + perune_rules (rules)
Overview of MetaInduce. Metalnduce is outlined in Algorithm I Similar to SGD for training neural networks, MetaInduce goes through the training data for several epochs; during an epoch, processes one example per iteration. Given an example (A;, 9;) (either provable or unprovable), it first relies on a rule proposer for generating candidate rules that are concrete and potentially useful for proving 9i from A, Then it runs an existing prover to search for proofs, using both the candidate rules and existing rules in the model. At the end of each epoch, MetaInduce abstracts all concrete rules used in the proof's into rules with variables. Then it performs rule seininng-sllettngg M as subset of the rules minimizing the loss (Equation] T.. Next, we explain each step in more detail.
Rule proposal. The rule proposer is dataset-dependent and allows incorporating prior knowledge about a particular task. However, a good rule proposer alone- if not embedded in Metalnduce is not sufficient for learning rules. First, the rule proposer only generates concrete rules. It is up to MetaInduce to abstract them into rules with variables. Second, the rule proposer generates rules useful for single training example, whereas MetaInduce learns rules useful for the entire dataset.

---

Under review as a conference paper at ICLR 2022
[X] and round and [V]
[X] and and [2] and [W]
round
round
(er, Ver) ((m Am))
green big heavy
light
round
round
(b) Encoding as boolean constraint a proof with paths from assumptions to the conclusion. Each concrete rule cr, corresponds to a boolean variable. The proof is disjunction of all paths; each path a conjunction of concrete rules.
(a) Examples of anti-unifying two concrete rules into more abstract rules. Anti-unification may have multiple solutions that are not comparable with each other.
Third, the rule proposer does not have to be accurate. MetaInduce can reliably learn correct rules even if most candidate rules are wrong (see Sec. 5
Theorem proving. Theorem proving in MetaQNI. is relatively straightforward, thanks to existing algorithms such as forward/backward chaining. Forward chaining starts with the assumptions and applies rules derive new sentences until the goal reached. Conversely, backward chaining starts with the goal and applies rules in the reverse direction until all assumptions are satisfied. We implement forward chaining using the Rete algorithm for fast rule matching (Doorenbos) (995) and
the basic backward chaining algorithm from a standard textbook (Russell & Norvig, 20022. The
prover returns proof' containing all different paths to the goal up to predefined depth limit.
Rule abstraction. The proofs contain only concrete rules (Definition 55. and we have to generalize them into rules with variables. We use symbolic procedure called anfi-unification (Plotkin 1970) to find general rules given concrete one. Given two rules 71 and r2, anti- unffuuciiiaion attempts to find the most specific rule r such that 71 S. r and r2 S r (analogous to the lowest common ancestor two nodes in a tree; see Fig. 2a for examples). It does so by recursively matching the beginning of two sentences. Please see Appendix B for details.
Let I' be the set of all concrete rules in the proofs. To augment I' with general rules, iteratively anti-unify rules in I' and add the result back, until no new rule can be generated. We denote the result by rV, which has not only concrete rules but also their generalizations.
Rule pruning with MAX-SAT. Rule pruning selects M as subset of I' by encoding all proofs as MAX-SAT problem, whose solution corresponds
set of rules that approximately minimize the loss function in Equation] I We encode each rule r E I" using a boolean variable (also denoted r). 1 means the rule should be included in M.. For any concrete rule E I, we have an additional boolean variable cr. cr = 1 means cr is necessary for proving the training examples. We impose 3 different types of constraints on these boolean variables:
Data consistency: For the ith training example, its proof P. may have many paths from the assumptions to the goal, but the example is provable as long as at least one of them is valid. For provable examples (those in Ditin). we encode P. disjunction of proof paths. Each path is valid if and only if all concrete rules along the path are valid. So we encode a proof path as a conjunction of all er boolean variables it contains (see Fig. 2b). Analogously, for unprovable examples (those in D D. we simply take the negation of the previous boolean formula to encourage the absence of a valid proof. Finally, a good model not necessarily consistent with every training example. So P. is encoded as a soft constraint with weight X+ or X-
Model complexity: To minimize the number of rules, we add soft constraint -r of weight 1 for each boolean variables. It encourages
O.
Rules instantiation: Each concrete rule cr must be an instance of a rule r. Let r1, r...... Th E T be the set of all rules in I' such that ri. er can be instantiated only if at least one of them is in the model. Therefore, we add a hard constraint cr + Ti V T2 V ... V rk-
Given a set of boolean constraints, each with weight, a MAX-SAT solver finds an assignment of boolean variables to minimize the combined weights of violated constraints, which equals to Equation | for the specific constraints above. Therefore, running an off-the-shelf MAX-SAT solver on these constraints gives us set of rules that minimizes our loss function.
5 EXPERIMENTS
We instantiate Meta and Metalnduce on two tasks: learning compositional instructions in MiniS- CAN (Lake et al. 2019 /SCAN (Lake & Baroni 2018) and logical reasoning in RuleTaker (Clark
7

---

Under review as a conference paper at ICLR 2022
Not only does Metalnduce learn rules achieving state-of-the-art prediction accuracy on all datasets, but it uses only a minor fraction of training data. Further, the rules recovered by Metalnduce match precisely with the ground truth rules of MiniSCAN and SCAN.
et al. 2020).
MiniSCAN. The data was introduced for studying seo-shot learning of compositional instructions. For example, given "dax - RED", "wif f GREEN", and "dax fep RED RED RED", we should learn "wif fep - GREEN GREEN GREEN". MiniSCAN consists of only 14 training examples (see Appendix C). Humans achieve an average accuracy of 84.3%, whereas state-of-the-art machine learning methods have reached 100% (Chen et al. 2020; Liu et al. 2020).
Each example in MiniSCAN consists of input sequence and an output sequence y. For example, dax pер and = RED RED RED. In training, we treat each input/output pair as provable example (A,, g+) Pitain with empty assumptions A, Ø and the goal 9: "x SMAPS TOS y". e.g. "dax fep $MAPS_TO TOS RED RED RED". In testing, we use "r $MAPS_ TO$ [Y]" as the goal, where [Y] is a placeholder to be filled by the prover. The prover succeeds if proves a goal with any [Y]. We do not include any unprovable examples, i.e., D Ø.
We use a rule proposer independent of specific training examples. It generates all concrete rules with < 2 premises by combining the 14 sentences in the training data in all possible ways, leading to 1288 candidate rules. With backward chaining as the prover and 73 (De Moura & Björner 2008) as the MAX-SAT solver, MetaInduce successfully recovers all 7 ground truth rules of MiniSCAN and achieves 100% prediction accuracy. Here is one example of learned rules: " [[A] $MAPS_ _
[B] T [A] fep $MAPS_TOS [B] [B] [B]". See Appendix C for more examples.
SCAN. As a standard benchmark for compositional generalization, SCAN is similar to MiniSCAN in format but much larger in scale. It consists of 21K examples of translating simplified natural language into action sequences. For example, "jump - JUMP", "jump twice ce + JUMP JUMP". State of the art has reached 100% accuracy on 4 different data splits: s simple, length, addprim_jump
and addprime tar__tuu___eeeee left (Liu et al. 2020 Nye et al.) 2020 Chen et al. 2020)..
We apply our method to SCAN similarly MiniSCAN except for the rule proposer. SCAN much larger; it is not feasible to generate all concrete rules exhaustively up to a certain number of premises. Therefore, we filter the rules using prior knowledge about compositional generalization: The meaning of long sequence depends on the meaning of its subsequences. For example. "Jump $MAPS _o JUMP H jump twice $MAPS __SS JUMP JUMP" is valid rule, since jump is subsequence of jump twice (more examples in Appendix D). In contrast, "look $MAPS_TOR __TO_________ LOOK + jump twi ce $MAPS_TOS __sss__T_____ JUMP JUMP" is not valid rule. Note that similar assumptions are also made in prior works (Nye al. 2020 Liu et al. (020)).
Trained only on the 400 shortest examples, MetaInduce achieves 100% testing accuracy and recov- ers the 20 ground truth rules of SCAN on all 4 splits (simple e, length. h, addprim_jumg and addprim ttuutuuun____ee _ef Here is one learned rule: [A] $MAPS TOS [B]: [C] $MAPS __TO
[D] + [A] after [C] $MAPS TOS [D] [B] ". Others are in Apppendix D The hyperparam-
eter X is tuned on 1000 validation examples. The validation accuracy is fairly robust w.r.t. different
x (Table 1.
Table 1: Validation accuracies on the ength split of SCAN with different = oo means encoding data consistency hard constraints.
0.32
0.64
1.28
2.56
5.12
10.24
#Rules learned Accuracy 85.9
16
17
20
20
20
20
20
90.3
100.0
100.0
100.0
100.0
100.0
Logical reasoning on RuleTaker. The RuleTaker dataset tests logical reasoning in synthetic English sentences. It consists of data examples similar to the one in Fig. [ The original RukeT is generated with the closed-word
assumption (CWA)-it assumes a sentence is false it is not provable. Tafjord et al. (2020) introduces version of RuleTaker with the open-world assumption (OWA). Under OWA, a sentence can be proved, disproved, or neither. We benchmark on the OWA version.
Some examples in RuleTaker meant to be disproved: If "The elephant is tall" is true, then "The elephant is not tall" should be false. We add special symbols $TRUE$ or $ $FALSES before sentences, so that the previous example can be disproved using the rule "STRUE$
8

---

Under review as a conference paper at ICLR 2022
Table Answer predicting accuracies on the OWA version of RuleTakkr. The model is trained on D5 or D3, and tested on D5 (proof depth I 5). Columns correspond to different proof depths within the test data, N/A means there no proof since the test example can be neither proved nor disproved.
Train
Model
N/A
0
2
3
All
ProofWriter
99.9
100.0
99.3
99.7
99.2
99.1
98.8
99.6
D3
Ours
99.4
100.0
100.0
99.7
98.9
98.9
98.6
99.4
Proo/Writer
99.9
100.0
99.3
99.7
99.2
99.1
98.8
99.6
D5
Ours
99.6
100.0
100.0
100.0
100.0
99.4
99.1
99.7
The el ephant is tall H SFALSE$ The elephant is not tall". For each exam- ple to be proved, we add it to the set of provable examples D and its negation to unprovable examples Dinin Conversely, for each example to be disproved, we add it to Dimin and its negation to Puriin For examples that can be neither proved nor disproved, we add itself and its negation to D Diainn
RuleTaker includes ground truth proofs providing concrete rules such as "$TRUEŞ The elephant is tall t $FALSES The elephant is not tall" but not any abstraction that allows generalizing beyond the specific examples. Our rule proposer simply generates these ground truth concrete rules, whereas Metalnduce tries to learn general rules such as "$TRUE$ [X] is [Y] F $FALSES [x] is not [Y]". And we use simple heuristics for filtering invalid rules generated by anti-unification. Please see AAppendix [ for details and example rules generated by the rule proposer. All experiments are on machines with GPUs, 32GB RAM, and four Intel Xcon Silver 4114 CPUs. We run Metalnduce for 5 epochs random subset of 10000 training examples, which takes about 20 hours. We use forward chaining as the prover and a depth limit of 7. The hyperparameters X+ and X are tuned on validation data.
We compare our method with ProofWriter (Tafjord et al. 2020 a state-of-the-an art method that also uses ground truth proofs. Following their setup, we test DS (a subset of RuleTaker with proof depths < 5) and train separate models on DS and D3 (proof depths < 3). Training on D3 is for evaluating the model's generalization longer proofs. Results are in Table Metalnduce achieves state-of-the-an accuracy and is competitive with ProofWriter.
MetaInduce learns significantly more compact models with much less training data. For example, the model trained on D3 with X = A = 1.28 using only 14% of the training data has only 79 rules and total of 2869 symbols, but achieves test accuracy of 99.4. 4. comparison, ProofWriter has an accuracy of 99.6 and is based on T5- B1B (Raffel et al. 2020). which has 11 billion parameters.
The rules learned by MetaInduce enable reasoning that not in the ground truth proofs. For exam- ple, it learns the rule "$TRUE$ if something [B] then it [C]: STRUEŞ [A] [B] H $TRUEŞ [A] [C]". During inference, the rule instantiated to "STRUES young then it be cold; $TRUE$ all furry thing be young + STRUES all
something be
furry thing be cold". This pattern of reasoning makes sense but has never appeared in
the grond truth proofs in RuleTaker.
LIMITATIONS AND OPEN QUESTIONS
First of all, our approach is far from mature. Substantial further development is needed for handling real-world natural language. Our experiments are neither large-scale nor real-world. They are small and synthetic, but serve as proof of concept for very novel approach at an early stage.
Metalnduce does not yet scale to millions of training examples, which may be necessary to learn enough rules to handle the complexity of real-world natural language. The current bottleneck is anti-unification. which can be possibly addressed through better methods for generalizing concrete rules to rules with variables.
MetaInduce is meta algorithm that permits many variations of its components. This provides many open questions and opportunities for integration with deep learning. For example, the rule proposer or theorem prover can be deep network instead of a manually crafted heuristic.
In its current form, MetaQNL does not allow uncertainty, which is necessary for robustness to noisy input and for commonsense reasoning, where many statements are not categorical. How to introduce uncertainty to MetaQNL is an open research question. One possibility is to associate probabilities with sentences and rules, and further define how probabilities propagate through inference.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Alex A Alemi, François Chollet, Niklas Een, Geoffrey Irving, Christian Szegedy, and Josef Urban Deepmath deep sequence models for premise selection. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
Gabor Angeli, Neha Nayak, and Christopher D Manning. Combining natural logic and shallow reasoning for question answering. In Annual Meeting of the Association for Computational Linguistics (ACL), 2016.
Kshitij Bansal, Christian Szegedy, Markus Rabe, Sarah Loos, and Viktor Toman. Learning to reason in large theories without imitation. arXiv preprint arXiv: arXiv: 10501, 2019.
Kaj Bostrom, Xinyu Zhao, Swarat Chaudhuri, and Greg Durrett. Flexible generation of natural language deductions. In Conference on Empirical Methods in Natural Language Processing (EMNLPP, 2021.
Xinyun Chen, Chen Liang, Adams Wei Yu, Dawn Song, and Denny Zhou. Compositional generaliza- tion via neural-symbolic stack machines. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Nuri Cingillioglu and Alessandra Russo. Learning invariants through soft unification. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Peter Clark, Oyvind Tafjord, and Kyle Richardson. Transformers as soft reasoners over language. In International Join! Conference on Artificial Intelligence (IJCAI), 2020.
Andrew Cropper and Sebastijan Dumančić. Inductive logic programming at 30: new introduction. arXiv preprint N.Xiv:2008.09912., 2020.
Wang- Zhou Dai, Qiuling Xu, Yang Yu, and Zhi-Hua Zhou. Bridging machine learning and logical reasoning by abductive learning. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Ádám Darvas, Reiner Hähnle, and David Sands. A theorem proving approach analysis of secure information flow. In International Conference on Security in Pervasive Computing (SPC), 2005.
Leonardo De Moura and Nikolaj Bjømer. Z3: An efficient smt solver. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 2008.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In International Conference on Learning Representations (ICLR). 2018.
Robert B Doorenbos. Production matching for large learning systems. Technical report, Carnegie Mellon University, 1995.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1-64, 2018.
Nicolas Gontier, Koustuv Sinha, Siva Reddy, and Chris Pal. Measuring systematic generalization in neural proof generation with transformers. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Edward Grefenstette.
Towards a formal distributional semantics: Simulating logical calculi with 2013.
tensors. arXiv preprint
Thomas F Icard III and Lawrence S Moss. Recent progress monotonicity. In Linguistic Issues in Language Technology (LiLT), 2014.
William W Cohen Fan Yang Kathryn and Rivard Mazaitis. Tensorlog: Deep learning meets proba- bilistic databases. Journal of Artificial Intelligence Research, 1:1-15, 2018.
Laura Kovács and Andrei Voronkov. First-order theorem proving and vampire. In International Conference Computer Aided Verification (CAV), 2013.
10

---

Under review as a conference paper at ICLR 2022
Temur Kutsia. Unification with sequence variables and flexible arity symbols and its extension with patter--trma pp. 290-304, 2002.
Temur Kutsia, Jordi Levy, and Mateu Villaret. Anti-unification for unranked terms and hedges. Journal of Automated Reasoning. 02:155-190, 2014.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of Sequuence-t--sqqeence recurrent networks. In International Conference on Machine Learning (ICML), 2018.
Brenden M Lake, Tal Linzen, and Marco Baroni. Human few-shot learning of compositional instructions, In Annual Meeting of the Cognitive Science Society (CogSci), 2019.
Moontac Lee, Xiaodong Hc, Wen-tau Yih, Jianfeng Gao, Li Deng, and Paul Smolensky. Reasoning in vector space: An exploratory study of question answering. In International Conference Learning Representations (ICLR), 2016.
Qing Li, Siyuan Huang, Yining Hong, Yixin Chen, Ying Nian Wu, and loop neural-symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning. In International Conference on Machine Learning (ICML), 2020.
Zhu. Closed
Qian Liu, Shengnan An, Jian- Lou, Bei Chen, Zeqi Lin, Yan Gao. Bin Zhou, Nanning Zheng, and Dongmei Zhang. Compositional generalization by learning analytical expressions. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Bill MacCartney and Christopher Manning. Natural logic for textual inference. In ACL-PASCAL Workshop on Textual Entailment and Paraphrasing, 2007.
Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B Tenenbaum, and Jiajun Wu. The neuro- symbolic concept leamner Interpreting scenes, words, and sentences from natural supervision. In International Conference Learning Representations (ICI.R, 2018.
Gary Mareus and Ernest Davis. Insights for ai from the human mind. Communications of the ACM, 64:38-41 41,8-41,220 2020.
David McAllester and Robert Givan. Taxonomic syntax for first order inference. Journal of the ACM (JACM), 40:246-283. 1993.
William McCune. Solution of the robbins problem. Journal of Automated Reasoning, 19:263-276. 1997.
Norman D. Megill and David A. Wheeler. Metamath: A computer language for mathematical proofs. 2019.
Hugo Mereier and Dan Sperber. The enigma of reason. Harvard University Press, 2017.
Pasquale Minervini, Matko Bošnjak, Tim Rocktäschel, Sebastian Riedel, and Edward Grefenstette. Differentiable reasoning on large knowledge bases and natural language. In AAAI Conference on Artificial Intelligence, 2020.
Koji Mineshima, Pascual Martinez-Gómez, Yusuke Miyao, and Daisuke Bekki. Higher-order logical inference with compositional semanties. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2015.
Stephen Muggleton. Inductive logic programming. New Generation Computing, 8:295-318, 1991.
Maxwell Nye, Armando Solar-Lezama, Joshua B Tenenbaum, and Brenden M Lake. Learning compositional rules via neural program synthesis. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Gordon Plotkin. note on inductive generalization. Machine Intelligence, 5:153-163, 1970.
Gordon Plotkin. Automatic methods of inductive inference. PhD thesis, The University of Edinburgh, 1972.
11

---

Under review as a conference paper at ICLR 2022
Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03:0 03,30, 2020.
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. Runlogic: Learn- ing logic rules for reasoning on knowledge graphs. In International Conference on Learning Representations (ICLR), 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research (JMLR), 21:1-67, 2020.
Mukund Raghothaman, Jonathan Mendelson, David Zhao, Mayur Naik, and Bernhard Scholz. Provenance- guided synthesis of datalog programs. In Symposium on Principles of Programming Languages (POPL), 2019.
Alan JA Robinson and Andrei Voronkov. Handbook of automated reasoning, volume 1. 2001.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Stuart Russell and Peter Norvig. Artificial intelligence: modern approach. 2002.
Swarnadeep Saha, Sayan Ghosh, Shashank Srivastava, and Mohit Bansal. Prover: Proof generation for interpretable reasoning over rules. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020.
Abulhair Saparov and Tom M Mitchell. generative symbolic model for more general natural language understanding and reasoning. arXiv preprint arXiv:2105.02486 2021.
Imanol Schlag, Paul Smolensky, Roland Fernandez, Nebojsa Jojic. Jürgen Schmidhuber, and Jianfeng Gao. Enhancing the transformer with explicit relational encoding for math problem solving. arXiv preprint arXiv:1910.00 1910.06611 2019.
Xujie Si, Mukund Raghothaman, Kihong Heo, and Mayur Naik. Synthesizing datalog programs using numerical relaxation. In International Joint Conference on Artificial Intelligence (IJCAI), 2019.
Paul Smolensky. Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artificial Intelligence, 46:159.216, 1990.
Oyvind Tafjord, Bhavana Dalvi Mishra, and Peter Clark. Proofwriter: Generating implications, proofs, and abductive statements over natural language. arXiv preprint 2.ti::2012.10044 2020.
Alon Talmor, Yanai Elazar, Yoav Goldberg, and Jonathan Berant. olmpics-on what language model pre-training captures. Transactions of the Association for Computational Linguistics (TACL), 743-758, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems (NeurIPS), 2017.
Leon Weber, Pasquale Minervini, Jannes Münchmeyer, Ulf Leser, and Tim Rocktäschel. NIprolog: Reasoning with weak unification for question answering in natural language. In Annual Meeting of the Association for Computational Linguistics (ACL), 2019.
Fan Yang. Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning, In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Kaiyu Yang and Jia Deng. Learning to prove theorems via interacting with proof assistants. In International Conference on Machine Learning (ICML), 2019.
Gonzague Yernaux and Wim Vanhoof. Anti-unification in constraint logic programming. Theory and Practice of Logic Programming, 19:773-788 77973-7-9,977 2019.
12

---

Under review as a conference paper at ICLR 2022
A PARTIAL ORDER AMONG SENTENCES AND RULES
Here we prove that the I in Definition of the main paper is indeed a partial order relation.
Definition (Sentence length). The length of a sentence + (t1, ,t,) E D is length(s) = n. Lemma (Substitutions are noncontractive). Applying substitutions does not make sentence shorter. In other words, for any sentence s = (2......... (a) E E+ and substitution a Eg + Et. we have length(as) 2 n. Further, length(or) = n if and only if maps all tokens in s to sentences of length 1, i... Vi, leeeggh(hoo)) =.
Proof. For any substitution Eg Σ and variable v E,, d(u) E Et, is sentence. Therefore, for any loken & E Σ, length(at) 2 1 (Definition 3). For any sentence = (t1, 12. i2..... ........,,)) (n). we have length(ars) Si=1 length n. And the equality holds if and only vi, length(ol.) 1.
Theorem (Partial order among sentences), If sentence equality is defined modulo a-conversion, then the S in Definition is a partial order among sentences. In other words,
1. Vs E E+ ,35.. S..
2. Vsi $2 E Σt, if S 82 and $2 $1, then 81 82 modulo a-conversion.
3. V81, 82, Σt, if 82 and 82 S 83, then 81 S 83.
Proof. We prove the 3 statements separately.
1. Let e be the identity substitution mapping any variable to itself, i.e., Ve E Σ,, e(u) = v. According to Definition 3 also maps any token itself (Vi E E, et = t), and therefore any sentence to itself (v's E Σ+ = s). Applying Definition we have Vs E Σ+ 8 S 8.
2. Given two sentences $1 (t1, f2......... tn), $2 (t',, 12.................... ................................ ,ttr)) such that 81 < $2 and 82 I $1, there exist substitutions a., ip such that $1 = 082 and 82 = 4ps (Definition and Vi, length(ypt,) 1. According to Definition 3 we derive Vi, t, = at, and & şt,- If t, is not a variable, f stt ti, i.e., all non-variable tokens in 81 and $2 are identical. If is variable, t must also be variable because otherwise & = at,, would not be a variable. Therefore, both a and و are just renaming variables. And it is straightforward to verify that they cannot map different variables to the same. In other words, o and op are conveerrso,,,; modulo a-conversion.
Applying Lemma to them separately leads
length (ot))
$2
3. Given three sentences 81, 82, and 83 such that 81 S 82 and 82 S 83, there exist substitutions a and &p such that $ı 022 and $2 (ps3. Let μ = a yp be the function composite of and p. j is also a substitution and $1 = 183. Therefore, $1 I 83.
Theorem (Partial order among rules). The in Definition 4 is partial order among rules. In other words,
1. For any rule r, r S
2. For any two rules in and r2, if S 12 and r2 S Tı, then rı 12 modulo a-conversion.
3. For any three rules Tı, 12 and r3, rf I T2 and r2 I rs, then rı S r3.
Proof. Similar to the proof of Theorem
Definition 8 (Strictly partial order among sentences/rules). Let $1 and 82 be two sentences, 8y is strictly more general than $1 (denoted by $1 $2) if and only if $1 S 82 and $1 # 82 modulo a-conversion. Similarly, if ri and 12 are rules, rı < T2 if and only if ri I r2 and Ti # r2 modulo a-conversion.
13

---

Under review as a conference paper at ICLR 2022
hello [X]
[X] hello
you [
are M
hello hello
hello hello hello
hello hello hello hello
How are you ?
? you are how
Figure 3: The minimal complete set of unifiers of two sentences can be empty, finite, infinite (e.g..
"hello [x] and [[X] hello"). The minimal complete set of anti-unifiers non-emply and finite.
B UNIFICATION AND ANTI-UNIFICATION OF SENTENCES AND RULES
Unification and anti-unification (Plotkin 1970, Robinson & Voronkov 200T are basic symbolic procedures in formal logie that useful for theorem proving and logic programming (Russell & Norvig 2002] Yernaux Vanhoof 2019). In MetaQNL, unification is used in backward chaining. and anti-unification is used abstract concrete rules into rules with variables. We adapt existing problem setups and algorithms from formal logic to MetaQNI.. The algorithms we use for MetaQNL. do not have theoretical guarantees in formal logie, but they work well in practice.
Unification. Given two sentences (or two rules), unification aims to find substitutions mapping them to the same sentence (or rule). Such substitutions are called unifiers. We extend unification to MetaQNL by adapting prior work, especially the unification algorithm developed by Kutsia (2002) for a variant of first-order logic with sequence variables and flexible arity symbols.
Definition 9 (Unifier). substitution E,, + Et is unifier two sentences 82 E Σ+ ifand only if 08 082. Similarly, it is a unifier of two rules rı and T2 if and only if ar = 012.
Two sentences may have multiple unifiers. Taking 81 = [X] is [Y], $2 = The elphant [2] example, their unifiers include
[[X] + The elephant, [2] + is [Y]}, ip
[X] + The elephant, [Y] + tall, [2] + is tall]. etc. Both a and are valid unifiers, but they lead to different sentences when applied: σs1 The elephant is [Y], 181 = The elephant is tall. We prefer a to because it is more general; it does not introduce any new information not in 8 and 82. In contrast, we cannot infer the "tall" in p. This is the intuition behind the concept of "most general unifiers".
Definition 10 (Most general unifier). Let the substitution a be unifier of sentencens 81 and $2, it is most general unifier if and only if there is unifier yp of sı and 82 such that σs < (08)-
In unification, we want to compute set of most general unifiers, and we want the set to be minimal and complete, Below we define these concepts for sentences.
Definition 11 (Complete set of unifiers). Let be a set of unifiers of sentences 81 and 82, U is complete if and only if for any unifier ip of and 82, there exists unifier E U, such that 4p81 S 088-
Definition 12 (Minimal set of unifiers). Let'l be a set of unifiers of sentences s1 and s2 U is minimal if and only for any a, & E U. 428 I σsi implies a = (modulo a-conversion).
Definition 13 (Minimal complete set of unifiers). Let U be a set of unifiers of sentences 81 and 82, U a minimal complete set of unifiers if and only if it both minimal and complete.
The definitions for rules are parallel. Given two sentences (or two rules), the unification problem to compute a minimal complete set of unifiers. The result can be empty (c.g., unifying "hello world" and "how are you"), finite ("hello [x]" and " [YY] world"), or infinite ("hella [x]" and " [X] hello", 3 Left).
Anti-unification. Given two sentences (or two rules), anti-unification aims to generalize them into a single sentence (or rule). Anti-unification has also been studied in formal logic (Plotkin) 1970 Kutsia et al. 2014). We extend MetaQNL by adapting prior work. For simplicity, define anti-unification only for sentences, but it applies to rules as well.
Definition 14 (Anti-unifier). Given two sentences s and 82, their anti-unifier is a triple (8,01, 02) of sentence and two subsitutions oi, a2 such that 018 81 and a22 82.
14

---

Under review as a conference paper at ICLR 2022
Definition 15 (Most specific anti-unifier). Let (s, 01, 02) be anti-unifier of sentencens $1 and 82. is a most specific anti unifier if and only if there no substitution i, of and og such that
1. =
= o0
2. yp8 <8
3. (ps, oi 222 is also an anti-unified of $ı and 82
Definition 16 (Complete set of anti-unifiers). Let A be set of anti-unifiers of sentences Si and $2. A is complete if and only if any anti-unifier (s, ; (1, 02) of 81 and 82, there exists a substitution and an anti-unifier (p88, 1 0/2 such that σı - 0 p, 02 o2 sp
Definition (Minimal set of anti-unifiers). Let A set of anti-umifiers of sentences 51 and 82, A is minimal and only if for any (s, (1,0),2) (s', 0
A. if there exists substitution &p such that
1. 5 4p
2. = oi 0 -2
then yp must be an a-conversion, i.e. ys= (modulo a-conversion).
Definition 18 (Minimal complete set of anti-unifiers), Let A be a set of anti-unifier of sentences $1 and $2 A is minimal complete set of anti-umifiers if and only if it is both minimal and complete.
Given sentences (or two rules), the anti- untfiiaiiiatoonn problem is compute minimal complete set of anti unifiers. Unlike unification, the result anti-um inti-unffication must non-empty and finite (Fig.
Theorem Anti-uniiiiation is finitary). Let A be a minimal complete set of anti anti-unifiers of sentences and 82, then A is non-emply and finite.
Proof. For any sentences and 82, have trivial anti-unifier [X]]_11,0) (2) where 01 [X] }1} and 02 = [[X] - 52). Since A is complete, apply Definition 16 and we will know A must be non-empty.
For any anti-unifier (s, 90, (22) E A, we have ø1s = 81 (Definition 14p. Apply Lemma] to derive length(s) < length((p1s) length(sz)) (s1). Therefore, the length of bounded. Also, cannot have non-variable tokens besides those in 81, so its vocabulary is also bounded. There are finite number of different sentences that take (modulo a-conversion). Therefore, A must also be finite.
Our current anti-unification algorithm is adapted from Kutsia et al. (2014). It recursively matches the beginning of two sentences. Let 81 and be sentences, and is a more general sentence in their anti-unifier. $1 and 82 start with the same word w, s should also start with w. Otherwise, should start with a variable corresponding to some prefixes of s and s2. The algorithm searches for all such prefixes and anti-unifies the remaining parts of the sentences recursively.
C DETAILS OF MINISCAN EXPERIMENTS
The 14 MiniSCAN (Lake et al. 2019) training examples represented as sentences in MetaQNL ($MAPS_TTT TO$ is special symbol):
15

---

Under review as a conference paper at ICLR 2022
dax
$MAPS_TOS RED
lug
SMAPS_TOS BLJE
wif $MAPS_TOS GREEN
zup
$MAPS_TOS
YELLOW
dax fep $MAPS_TOS
RED RED RED
lug fep
$MAPS_TOS
BLUE BLUE BLUE
wif blicket dax
$MAPS_TOS
GREEN RED GREEN
lug blicket wif
$MAPS_TOS
BLUE GREEN BLUE
dax kiki lug
$MAPS_TOS
BLUE RED
lug kiki wif
$MAPS_TOS
GREEN BLUE
lug fep kiki wif
$MAPS_TOS
GREEN BLUE BLUE BLUE
lug kiki wif fep
$MAPS_TOS
GREEN GREEN GREEN BLUE
wif kiki dax blicket lug
$MAPS RED BLUE RED GREEN
wif blicket dax kiki lug
$MAPS_TOS
BLUE GREEN RED GREEN
The 10 testing examples:
zup fep
$MAPS_TO$
YELLOW YELLOW YELLOW
zup blicket lug
$MAPS_TOS
YELLOW BLUE YELLOW
zup kiki dax
$MAPS_ _
RED YELLOW
zup fep kiki lug
$MAPS_TOS _
BLUE YELLOW YELLOW YELLOW
wif kiki zup fep
$MAPS_TOŞ
YELLOW YELLOW YELLOW GREEN
lug kiki wif blicket zup
$MAPS_TOS
GREEN YELLOW GREEN BLUE
zup blicket wif kiki dax fep
$MAPS_ _0$
RED RED RED YELLOW GREEN YELLOW YELLOW YELLOW YELLOW YELLOW YELLOW YELLOW
zup blicket zup kiki zup fep
$MAPS_TON _
dax blicket zup
$MAPS_ TO$
RED YELLOW RED YELLOW GREEN
wif kiki zup
2MAPS_TOS
The rule proposer generates candidates 1288 concrete rules with premises, by combining the 14 training sentences in all possible ways. Below are some examples. Note that most candidate rules wrong.
lug fep SMAPS_TOS BLUE BLUE BLUE } dax $MAPS_TOR RED
dax kiki lug $MAPS TOS BLUE RED; wif $MAPS_TO TO$ GREEN T lug kiki wif $MAPS_ TOS
GREEN BLUE
lug $MAPS_TOR BLUE; dax fep $MAPS_TOR TOS RED RED RED
T dax SMAPS_TOW RED
MetaInduce learns 7 rules corresponding to the ground truth rules of MiniSCAN:
T dax
RED
T lug $MAPS_TOS BLUE
T wif $MAPS_TOS GREEN
H zup $MAPS_TOS YELLOW
[A] $MAPS_TON TOS [B]
T [A] fep SMAPS_TOW [B] [B] [B]
[A] $MAPS_TOS [B]; [C] 2MAPS_TOS [D]
H [A] kiki [C] $MAPS_ _OO [D] [B]
[A] $MAPS_TOS TO$ [B] [C] $MAPS_TOS [D] } [A] blicket [C] $MAPS_TOS [B] [D] [B]
16

---

Under review as a conference paper at ICLR 2022
D DETAILS OF SCAN EXPERIMENTS
Some examples in SCAN Lake & Baroni 2018):
walk
$MAPS_TOP _TO
WALK
jump
$MAPS_TOS
JUMP
turn right
$MAPS_TO$
RIGHT
jump after turn left
$MAPS_TOS
LEFT JUMP
walk right
$MAPS_TO TOS
RIGHT WALK
walk after run
$MAPS_TO$
RUN WALK
turn left twice
$MAPS_TO$
LEFT LEFT
turn opposite left
$MAPS_TOR
LEFT LEFT
turn around right
$MAPS_ TOŞ
RIGHT RIGHT RIGHT RIGHT
walk around left
$MAPS_TOS
LEFT WALK LEFT WALK LEFT WALK LEFT WALK
The rule proposer similar before, but with an additional filtering heuristic based on composition- ality (see Sec. (). Below are some examples of the candidate rules it generates. Note that many of them are wrong because the premises are not sufficient to deduce the conclusion.
run SMAPS_TOS RUN + walk after run $MAPS_TOS RUN WALK
walk $MAPS_TON TOS WALK; run $MAPS_ __ RUN + walk after run SMAPS_TOS RUN WALK
SMAPS_TON RUN - jump twice after run twice SMAPS_TOS
RUN RUN JUMP JUMP
twice $MAPS TO$ RUN RUN T jump twice after run twice $MAPS_ RUN RUN JUMP JUMP
MetaInduce learns 20 rules corresponding the ground truth rules of SCAN:
17

---

Under review as a conference paper at ICLR 2022
T walk SMAPS_TOS WALK
+ look SMAPS_TOS LOOK
T run $MAPS_TOS RJN
H jump SMAPS_TOS JUMP
T turn right $MAPS_TOS RIGHT
+ turn left $MAPS_TOS LEFT
turn opposite left SMAPS_TOS
LEFT LEFT
turn opposite right SMAPS_TOS
RIGHT RIGHT
turn around left $MAPS_TOS
LEFT LEFT LEFT LEFT
H turn around right $MAPS_TOS RIGHT RIGHT RIGHT RIGHT
[A] $MAPS_ TOS [B] H [A] left $MAPS_TO TOS LEFT [B]
[A] SMAPS_TOL [B] T [A] right SMAPS_TOW RIGHT [B]
[A] $MAPS_TOS
[B] F [A] opposite left $MAPS_TOS
LEFT LEFT [B]
[A]
$MAPS_ TOS [B] T [A] opposite right SMAPS_ TOS
RIGHT RIGHT [B]
[A]
$MAPS_TOS [B] [A] around left SMAPS_TO$
LEFT [B] LEFT [B] LEFT [B] LEFT [B]
[A]
$MAPS_ TOS
[B]
[A] around right $MAPS_
RIGHT [B] RIGHT [B] RIGHT (B] RIGHT [B]
[A]
$MAPS_
[B]
H [A] twice $MAPS_TOŞ [B] [B]
[A]
$MAPS TOS
[B]
T [A] thrice $MAPS_ TO$ [B] [B] [B]
[A] $MAPS_ TO [B] ;
[C]
$MAPS TO$ [D]
T [C] and [A] SMAPS_ _os [D] [B]
[A] $MAPS_TOS TO$ [B]; [C]
$MAPS_TOS [D] T [A] after [C] IMAPS_TOS [D] [B]
E DETAILS OF RULETAKER EXPERIMENTS
Rule proposer.
If something is strong, then likes cats
elephant is big
The elephant likes
elephant
elephant strong
tall things strang
Figure 4: RuleTaker contains ground truth proofs in the form of directed acyclic graphs from the assumptions the conclusion. The nodes in the graph are concrete sentences without variables.
Fig. 4 shows the form of ground truth proofs in Rake.. For this specific example, our rule proposer would generate 2 candidate rules helow:
18

---

Under review as a conference paper at ICLR 2022
STRUES The elephant is big; STRUES The elephant is tall;
STRUES Big tall things are strong;
STRUES The elephant is strong
STRUES The elephant is strong; STRUES If something is strong then it likes cats; STRUES The elephant likes cats
Learned rules. Below example rules learned RuleTaker:
STRUE$ the [A] likes the [B];
STRUES the [A] is [C];
STRUES if someone is [C] and they like the [B] then the [D];
STRUEŞ the [D]
STRUES the [A] does not see the [B];
+ $FALSES the [A] sees the [B]
STRUES the [A] [B] the [C];
STRUES the [C] [D];
STRUES if somecne [3] the [C] and the [C] [D] then they need the [E]:
STRUES the [A] needs the [E]
$TRUE$ [A] is [B];
$TRUES [A] is [C];
$TRUE$ [B] , [C] things are [E];
$TRUE$ [A] is (E]
STRUES the [A] is [B];
STRUES the [A] is [C];
STRUES if someone is [C] and [B] then they chase the [D]:
STRUES the [A] chases the [D]
STRUES [A] is [B]:
T $FALSE$ [A] is not [B]
F HEURISTICS FOR CONSTRAINING THE SPACE OF RULES
We use a few simple and general heuristics for constraining the space rules and pruning invalid rules generated by anti-unification.
19

---

Under review as a conference paper at ICLR 2022
First, merge multiple variables that always appear together. For example, the [A] [B] and [D] [E] in the rule below can merged.
[C]
STRUE$ [A] [B]
[C]
then [D] [E];
STRUEŞ [A] [B] [C];
STRUE$
[D] [E]
So the rule becomes:
STRUES If [A] then [B];
STRUES [A];
STRUES [B]
A variable in rule is called a arree variable, if it appears only once. For example, the rule
If something is red, then tomorrow will be sunny;
[X] is red;
Tomorrow will be sunny
contains a free variable [X]. We require that rule cannot contain free variables in its conclusion. Because they would allow arbitrary conclusions formed by substituting them with other sentences. For example, the rule below not allowed because the free variable [x] in the conclusion:
STRUES Today is sunny;
STRUES Tommorow is [X]
In addition, a rule cannot contain a premise made of one single free variable. Because this premise
can be satisfied by any sentence, and there is point including it in the rule. For example, the rule
below is not allowed because of the free variable [X]:
$TRUE$ [X];
$TRUES If [A] then [B]]
$TRUES [A];
STRUES [B]
Finally, for RuleTaker, only consider rules with more than free variable.
20


Reviews:
[{"review_id": "vsnyod7rm9k", "reviewer": "Reviewer_v7TB", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths:\n1) this is indeed novel research problem - using a learning system together with a maxsat solver to make logical inference and identify rules.  There is a spectrum where on one end logical inference instances fully in natural language, and on the other end they are fully symbolic, and this paper falls somewhere inbetween.\n2) The paper is generally well-written, and mathematical part of the paper seems to be correct.\n\nWeakness:\n\nI fail to see the real contributions in this paper.  The only novelty seems to me is MetaQNL and MetaInduce can solve formal systems as well as systems represented in quasi natural languages.  However, are there actual applications that can potentially benefit from this problem formulation?\nOne of the major claims of this paper is it can produces checkable proofs, but isn't Proofwriter also capable of generating proofs which seemed more impressive because it is a fully neural system without any explicit encodings of rules and has the potential of working with real languages.  I get that proofwriter has billions of parameters and MetaInduce learns a system with much fewer parameters, but then what is the difference between this and combinatorial optimization?\n\nFurthermore, I failed to see a way to scale up this method.  In the end, it depends on a maxsat solver, which will become intractable quickly when there are more rules.\n\nIn summary, if the authors can present a real-world application that can potentially benefit from their system while other learning systems fail to do so and evaluate their method on a small real-world dataset, I would be less concerned.\n\nSmall comments and questions:\n1) Would appreciate a few citations to support the claim \"At a glance, this may appear a large departure from the conventional wisdom that learning-based systems, particularly deep networks, are far superior to rule-based systems, as history has demonstrated repeatedly.\"  The authors need to be specific what on tasks.  For example, NNs are far behind SAT solvers on propositional formulas (GQSAT as an example for learning-based system).\n2) I fail to understand why rule proposers need to generate concrete rules, aren't all the rules already included in MetaQNL systems?", "summary_of_the_paper": "This paper proposes a symbolic system in Quasi-Natural Language, MetaQNL, which is compatible with both logical inference and quasi natural language expressions, and where the basic building blocks are sentences and rules. The authors also propose MetaInduce, which learns to generalize a set of rules that explains the examples in MetaInduce.\n\nMetaInduce consists of three mains steps:\n1) a rule proposer proposes a set of concrete rules as candidates for each individual example. This set may not be fully correct and may not be the minimal explanations, and they are used to prove the example using forward/backward chaining.\n2) the authors apply a symbolic procedure called anti-unification to generate abstract rules from concrete rules.\n3) and finally, proof paths are encoded in MAX-SAT and a subset of all rules are solved using a MAX-SAT solver to find minimal possible explanations\n\nThis paper evaluates its methods on two synthetic datasets, and the authors claim to learn compact models with much less data, and produces answers as well as proofs", "summary_of_the_review": "In short, while I acknowledge this work is novel, its setting is not very practical.  This paper would benefit from presenting a potential real-world application, or else some theoretical generalization results on how well their systems can learn.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "egVauJudI_u", "reviewer": "Reviewer_CPsz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros: \n- The learning algorithm is interesting and the problem of automatically discovering prepositions from examples is important for ATP in formal or informal languages.\n- The paper clearly defines the terms used and explains the methods and experiments well.\n\nCons:\n- As the authors pointed out, the experiments are neither large-scale nor real-world. One result of this is existing methods already achieve good performance, and it's not clear that the proposed method results in better performance.\n- None of the components (theorem prover, rule abstraction, rule pruning) are novel individually.\n\nQuestions:\n1) Are TRUE FALSE and MAPS_TO the only special symbols? It would be helpful to state this. \n2) Are there any unprovable examples in SCAN?\n3) The number of rules and symbols learned by MetaInduce is hard to compare with the number of learned parameters in ProofWriter. Is there a better metric to compare the two methods on? \n4) What are the advantages to using the proposed symbol system instead of first order logic? ", "summary_of_the_paper": "This paper proposes an algorithm that learns rules from natural language data, and a symbolic system for manipulating these rules, where existing provers can be applied. The objective is to maximize the number of examples in a test set that are consistent with the proposed mode while minimizing the number of rules in the model. The algorithm consists of three steps - given a training example, it proposes concrete rules, abstracts concrete rules into rules with variables, and prunes the resulting rules. ", "summary_of_the_review": "The paper proposes an interesting solution to an important problem, but as-is the experimental settings and results are not compelling. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JoRDRqUmoAq", "reviewer": "Reviewer_9uxa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the idea is novel and I like the paper presentation. However, I have some concerns regarding its ability to work with real natural language and the reproducibility of the proposed approach.\n\nMAJOR CONCERN 1:\nI have a concern that the rule proposer and the anti-unification require very well-formed of the sentences to be working well. \n\nAs we can see with the example on page 7 figure (a) about anti-unification, the sample shows very simple rules. I wonder how it will work when the sentence is really complicated with real natural language? Also the experiments in RuleTaker only with synthetically generated sentences in a very controlled language, could you please  demonstrate your results with complicated sentences beyond synthetic texts, I think the paraphrased datasets within the RuleTakers even not really natural language but that could be a good exercise for your methods to test on.\n\n\nMAJOR CONCERN 2:\nI worry about reproducibility as the source code is not open but the details explanation of the proposed approaches are missing. For example, from the paper I don't know how the rule proposer work and how the anti-unification is implemented with quasi-natural language. I would suggest to provide very detailed about the methods, with the current information I doubt that people can reimplement your work and reproduce what you have demonstrated.\n\nMAJOR CONERN 3:\nIn the RuleTaker example, it is known that Transformers are good at generalisation when they are trained on queries with depth 3 or greater. Yet transformers are not good at generalisation when it is trained on lower depth queries. Could you please provide comparison results with Transformers when it is trained at lower depths? \nOther minor comments:\n\n\n\"In contrast, our approach does not require a semantic parser, because rules in MetaQNL are directly applicable to natural language.\" ---> This is a strong statement, it requires a support with real natural language examples rather than synthetically generated sentences in the experiments.\n\n\nDefinition 6: what happen if there is no proof for a goal and the goal is proved via the close world assumption?\n\n", "summary_of_the_paper": "The work proposes two new concepts:\n+ MetaQNL: a symbolic system in Quasi-Natural Language. Instead of representing rules in a formal symbolic format such as first order logic rules, in MetaQNL, a rule is represented in a Quasi-Natural Language format which includes words, variables and control symbols. Since the rules are represented in an informal representation. An interesting property of the MetaQNL representation is that it allows to perform backward or forward inference by substitution of variables with sentences. The authors assume that texts can be translated into the MetaQNL format and thus solving the reasoning problems with text input is possible via mining rules from text and backward/forward reasoning with the Quasi-Natural Language.\n+ To mine rule from text, the authors proposes an algorithm called MetaInduce. MetaInduce iterates through the training data several time to build a compact set of rules that trades complexity to prediction accuracy. It is a bottom up rule induction approach where it includes a Rule proposer which propose a concrete rule from a training example and an anti-unification module to abstract the concrete rule with more generalised rules. A pruning process based on MAX-SAT is used to prune the set of rules such that it optimise the regularised objective.", "summary_of_the_review": "The paper proposes a new concept called quasi-language which allows representing rules in an new informal format that still allows to perform forward or backward reasoning while it is assumed to be mined easily from texts. The experimental results with some datasets with synthetically generated texts show that the methods work very well and advance state-of-the-art results. \nHowever, I doubt the application of the work with natural language input, I explicitly request to perform more experiments with paraphrased datasets in RuleTaker (MAJOR CONCERN 1). I also have a concern about reproducibility as the presentation lacks details of the core components of the proposed algorithm (MAJOR CONCERN 2). I also requested an additional experiment regarding the training data with low depth queries to check the ability of generalization of the proposed approaches. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7s9vVGYza3d", "reviewer": "Reviewer_7F3Z", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I liked the scope of this paper, the importance, and non-triviality of the problem, and the novelty of the proposed approach. In my view, it certainly adds a dimension to the literature on symbolic rule learning. The idea of MetaQNL is simple yet effective to handle the natural language inputs within a formal symbolic system. The idea behind MetaInduce is also quite natural. Although there are some weaknesses of the proposed approach, I still feel this is a novel idea and has the potential to yield something big in the future. \n\n__Strength__\n\n- A well-written paper.\n- A very nice literature survey and positioning of the work relative to the prior art.\n- An important problem in the broad space of AI.\n\n__Weakness__\n\n- Time complexity of each of the three steps in MetaInduce is not discussed. It will be good to shed some light on this. \n- As stated in the limitation section, the proposed approach is far from mature but serves as proof of concept.  It does not scale to millions of training examples.", "summary_of_the_paper": "Traditional research on symbolic reasoning assumes input data are already translated into a format that complies with the formalism of the underlying system. A major struggle for symbolic reasoning is to handle the data coming in a natural form (e.g. images/text) and perform reasoning on the same. Inspired by this challenge, this paper undertakes the problem of converting text inputs into the format of a system formalism. \n\nThe formalism is also proposed by this paper and is called MetaQNL. The framework of MetaQNL is designed keeping in mind the specific need of operating directly on natural language sentences. This formalism supports the natural language sentences with variables within them. This trick alleviates the need of using a semantic parser to parse natural language sentences for the purpose of logical reasoning. Thus, MetaQNL, by design, is conducive to working with natural language inputs. \n\nNext, this paper proposes an algorithm to induce rules from natural language inputs within the MetaQNL framework. This paper doesn’t worry about performing actual deductive reasoning/theorem proving and instead proposes to use existing provers and instead focus on the more challenging problem of rule induction. MetaInduce algorithm draws inspiration from existing ILP approaches. MetaInduce encodes the rule induction problem as a maximum satisfiability (MAX-SAT) problem, which can be solved efficiently by off-the-shelf solvers. The proposed method consists of 3 steps. \n\n1. Given a training example, a rule proposer proposes a set of concrete rules as candidates. This set can be overcomplete/inaccurate. \n2. It generates abstract rules from concrete rules via a symbolic procedure called anti-unification. This is essentially a process of aligning common substring segments across two or more strings.\n3. It encodes the proof paths in MAX-SAT and solves for a subset of all rules using a MAX-SAT solver. \n\nThis paper benchmarks the proposed method on 2 tasks - learning compositional instructions and logical reasoning. For learning compositional instructions, it works on two standard benchmarks: MiniSCAN and SCAN and recovers precisely the ground truth rules. For logical reasoning, the proposed method achieves SOTA on the RuleTaker dataset. \n\n", "summary_of_the_review": "See my comments in the main review.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper describes a system for learning rules in a quasi-NL format: roughly Horn clauses where a predicate p(X1,...,Xk) is replaced by a natural language pattern interleaving ground tokens and variables.  The method is to propose ground sentences - using one of several task-specific approaches - use anti-unification of pairs to variabilize, and then find a minimal theory from these proposed pairs by reduction to maxsat.

Pros:
 - QNL is a neat idea, and makes symbolic rule-learning possible to some NLP tasks
 - The use of maxsat is novel in rule-learning AFAIK

Cons:
 - Unification is a highly simplified model of the NL task of cross-document co-reference
 - It's unclear if maxsat process will work in the presence of noise, or how well it scales
 - The datasets use clean text generated from templates or synthetic grammars
 - Experimentally, the generality of the system is not well demonstrated, because there are differences in how it is applied: eg a subset of short examples for scan, input engineering ($TRUE, $FALSE) for RuleTaker, plus the "heuristics for filtering invalid rules generated by anti-unification”
 - It's not clear if this work really speaks to the main "point" of the SCAN and RuleTaker datasets.  These are both the kind tasks that symbolic systems would be expected to do well, and are used as ANN benchmarks because ANNs perform in unexpected ways: worse than one would expect for SCAN, and better for RuleTaker.  They are important for understanding ANNs but I'm not certain what the research benefit is of using them for symbolic methods as a benchmark.
Decision: Reject